Prescriptive Analytics refers to various techniques, which help us in taking a decision. Unlike other techniques discussed so far, they give the “best” decision for a given business objective. Linear Programming, Integer Programming, Game Theory, Simulation, various Heuristic based methods are part of this generic set of techniques.
We start our discussion with Linear Programming, which is the most studied method in Operations Research. The prime motivation for its development was to optimize the military operations in World War II, but was later found to be useful in several other business areas. It is widely used in the following areas, and there are numerous other applications.
Production and Manpower planning
Distribution and Logistics Planning
Investment Portfolio Management
Telecommunications Network Planning
Airline Flight and Crew Scheduling
Linear Programming is used in all cases, where we seek to optimize (maximize or minimize) an Objective, in terms of few DecisionVariables, given set of Constraints .As an example the Decision Variables could be number of units of Model A, B and C to be produced by a Car Manufacturer. The Objective could be to maximize the combined profit from these three models. The constraints could be maximum Manufacturing Capacity of the plant, Total Investment limit, limitation on Manpower etc. The Linear Programming solution would prescribe the optimal mix on the number of units to be produced for the three models.
Why are these problems called Linear Programming? Linearity implies two properties – Linearly Proportional and Linearly Additive. If cost of one car is $10,000, then cost of 100 cars would be $1M. We would not consider possibilities that, with increase in production, cost of 100 car could come down. If 1 model of a car, generates profit of $10,000 and another generates $25,000, then total profit would be 10,000*A + 25,000*B, where A and B are no. of units of the two models. Once again, we would not consider possibility of Cannibalization or other phenomena, where sales of one model starts impacting sales of other model.
We assume that variables could be fractional. Very often the variables refer to objects like units of a product, or number of personnel, which are whole numbers. But we let the solution generate fractional values, and interpret it as work-in-progress, or partially engaged manpower or simply assume the next whole number as solution. Hence if number of beds come as 0.3, then we assume this as work in progress.
However, there are cases, where fractional values certainly do not make sense at all. This translates the problem into an Integer Programming exercise, which is solved differently.
We should note that number of Decision Variables and number of Constraints are crucial in solving a Linear Programming problem. Decision variables are the unknowns, which have to be solved for the Objective Function, with the help of equations, which come from the Constraints imposed. If n is no. of variables and m is no. of equations (constraints), then three scenarios emerge.
n = m, there is a unique solution for this scenario, which may not be the optimum.
n < m, there is either no solution or a unique solution.
n > m, there are infinite number of solutions.
It is the last scenario, which we solve in Linear Programming. Out of infinite no. of solutions, we seek the one which maximizes or minimizes our Objective Function (Profit, Cost, Revenue, Utilization etc).
Let us take a very simple example. A carpenter produces two models of beds – A and B, which provide profit per unit of $20 and $30 respectively. Model A requires 40 hours of woodwork and 10 hrs. of painting. Model B requires 50 hrs. of woodwork and 20 hrs. of painting. The total man hours available for woodwork and painting are 600 and 180 hours respectively in a month. How many units of A and B should he produce in a month to maximize his monthly profit?
The best way to learn Linear Programming is to look at the graphical portrayal of the solution. The two constraints in the above example can be written as follows.
40*X + 50*Y <= 600
10*X + 20*Y <= 180
Where X and Y are number of beds to be produced for model A and B respectively.
In the below picture, X-axis represents X and Y-axis represents Y. The two constraints are plotted as red and blue lines respectively. In addition to them X and Y can not be less than 0 (we can not have negative number of beds), which are represented by the two axes. The solution (feasible number of units of A and B) has to be bounded by these four lines as shown. Where do you think, the maximum profit (20X + 30Y) would occur? The profit for few of the possible solutions are shown. The maximum profit (objective function) 320, occurs at (10, 4), which is one of the corner points of the feasible solution space. The same solution is obtained by Excel’s Solver option as shown in the Example sheet.
This is a crucial finding and for any feasible solution space, the optimum solution lies at one of the corner points. This is not a coincidence, but a characteristic of LP problems. One way to exploit this characteristics is to find objective function value at all the corner points, and chose the maximum value. However in practical cases, where we may have numerous decision variables and constraints, this approach may become very inefficient.
We solve the LP problems more efficiently as below, by an algorithm called, SIMPLEX Algorithm. First we will get introduced to some terminologies and concepts.
Standard Form of Linear Programming (LP) Problems: In order to use a standard algorithm on LP problems, we need to develop a Standard Form of these problems. This is achieved by something called Standard Form of LP, which is achieved by –
Always using a minimization Objective Function – in case we seek to maximize the objective function, we multiply the function by -1
Converting all the constraints as an equality constraint – Usually we may have a constraint as more than or less than a certain value (budget can not exceed certain amount etc.). We convert constraints to equality equations by using additional variables called Slack or Surplus variables as follows.
2X + 3Y <= 5 -> 2X + 3Y + S = 5; where S is a slack variable
2X + 3Y >= 5 -> 2X + 3Y – S = 5; where S is a surplus variable
All variables (slack and surplus included) must be non-negative – This is achieved as follows.
Variable X is split into two variables; x = xP- xN
When X > 0, X = xP and xN is set as zero
When X < 0, -X = xN and xP is set as zero
Hence any LP problem can be converted to its equivalent Standard Form as below with the above transformations.
Set of Linear Constraints always generate, what is known as a Convex Solution space, as shown below. The characteristic of this Convex Space is that any line joining two points within the space, always lies within the space. Hence the shape on left is Convex, while the one on the right is non-convex.
We would state, what we already discussed earlier, in the form of a Theorem.
Theorem: The optimal solution for a Linear Objective function on a Convex Solution space always occurs at one of the Corner Points.
There could be four possibilities with respect to the LP solution as shown below.
The Graphical Solution method is for academic interest only. It can be used only for 2 variables (2D). However in practical cases, analogous solutions would exist in the form of Planes or Hyperplanes. With this illustration by means of a Graphical Method, we move to a more efficient and general purpose technique called "Simplex Algorithm".
LP refers to problems where number of variables (n) > number of equations (m)
We set the n – m excess variables as zero.
Solve uniquely for m remaining non-zero variables, with the help of m equations.
This is called a Basic Feasible Solution (BFS) and the m solved variables are called Basic Variables.
The BFS corresponds to one of the corner points and two neighboring BFS differ in only one variable.
We move from one BFS to other by elementary row operations, where a Basic Variable becomes Non-basic and a Non-basic variable becomes a Basic variable. .
We keep traversing the corner points (neighboring BFS) till there is no improvement in the Objective Function.
The final value of the Objective Function, which can not be improved further, is the Optimum Solution.
The Example Sheet has one LP with three Decision Variables, and it is solved by "Simplex" option in Excel Solver. Please see how the Objective Function, Decision Variables, Constraints and the Simplex Solver option have been set in the example. One would need Excel Add-in to use this option.
The power of Linear Programming emanates from its diverse applications. Please download the Example Sheet and see following two applications in there.
Media Mix Planning: An organization wants to maximize its audience by designing an optimum mix of Print, TV and Radio ads, managing within the constraints on Advertising Cost and others.
Manpower Scheduling: A Car Dealer wants to optimize its mix of full-time and part-time workers, satisfying its hourly requirements of manpower.
These simple examples involving 2 or 3 Decision Variables are easy and can be solved manually or through Excel Solver. However in practical cases, the variables would run into several hundreds or even more. Although the basic steps remain same, the computation becomes too complex for manual calculation or even through simple tools like Excel Solver.
A prominent airline, like American Airlines, employs more than 8000 Pilots and more than 15000 crew members, to fly more than 5000 Aircrafts. It has to maximize its revenue (or profit) by operating within constraints like maximum work hours for pilots or crew members, minimum hourly rate and overtime rates for them, not exceeding certain flight hours for an aircraft in prescribed time and many others. Such a complex problem would need hours of computation on computers to generate the optimum Crew schedule.
Although Linear Programming is the cornerstone of Prescriptive Analytics, one should be informed about several other techniques to gain the complete coverage. Some of them are discussed in detail (please use the links below).