|
Intro to Linear Programming
Suppose you are the manager of a factory that produces Widgets, which sell for $4 each, and Flumps, which sell for $6 each. Your objective is to maximize Revenue = 4W + 6F subject to three factor constraints. Each Widget requires 2 units of Capital and 1 unit of Labor to produce. Each Flump requires 1 unit of Capital, 2 units of Labor and 2 units of Minerals to produce. For each week’s production, you have 50 units of Capital, 40 units of Labor and 30 units of Minerals on hand, all paid for, so your challenge is to determine the revenue-maximizing combination of Widgets and Flumps that you can produce each week with this fixed resource endowment.
To set this problem up for analysis, express each of these resource constraints in the following forms, as determined from the production recipes:
Capital: 2W – 1F ≤ 50 Labor: 1W – 2F ≤ 40 Minerals: 0W – 2F ≤ 30
If you set this problem up as a conventional Lagrangean, you get:
maximize L = 4W + 6F + λC[50 – 2W – F] + λL[40 – W – 2F] + λM[30 – 2F]
If a constraint is strictly binding, the bracketed expression representing it equals zero, and its multiplier is non-zero; if it is just-binding, both the bracketed expression and the multiplier equal zero; if it is non-binding, the bracketed expression is non-zero and the multiplier is zero.
Taking the five partial derivatives with respect to W, F, λC, λL and λM and setting them equal to zero implies all the constraints are binding, but there is no unique solution to this problem. You can solve for values W and F from any pair of resource constraints, but you get different solutions depending on which pair of constraints you solve from. This is an over-constrained maximization problem, and the constraints cannot all be binding simultaneously, so you cannot solve this via calculus and algebraic manipulation alone.
To get some insights into this problem, it helps to visualize the resource constraints in output space. The graph above shows the three resource constraints in solid lines. The shaded area of the graph represents all feasible combinations of Widgets and Flumps that satisfy all three constraints plus constraints that Widgets and Flumps must be non-negative. One feasible solution is to produce nothing at all, for zero profit. We consider alternative feasible solutions that yield positive profits, marked with black dots at the boundary corners of the feasible solution set. We analyze these clockwise from the Flumps axis:
You only have 30 units of Mineral, and Flumps require 2 units of Minerals each to produce, so you cannot produce more than 15 Flumps. You could produce 15 Flumps and 0 Widgets for a revenue of $6(15) + $4(0) = $90.
Since you only have 40 units of Labor, you could use it all to produce 40 Widgets and zero Flumps, or else 20 Flumps and zero Widgets, or some intermediate combination of Widgets and Flumps on the line W + 2F = 40, but the Mineral constraint won’t let you produce any more than 15 Flumps in any case, so if you solve the pair of constraints F = 15 (Mineral) and W + 2F = 40 (Labor), you could produce 10 Widgets and 15 Flumps for a revenue of $4(10) + $6(15) = $130.
Since you have 50 units of Capital, you could use it all to produce either 25 Widgets or 50 Flumps, or some intermediate combination of Widgets and Flumps on the line 2W + F = 50, but the Labor constraint W + 2F = 40 costs you 2 Flumps for every Widget you produce, so if you solve the pair of constraints W + 2F = 40 (Labor) and 2W + F = 50 (Capital), you could produce 20 Widgets and 10 Flumps for a revenue of $4(20) + $6(10) = $140. This also satisfies the Mineral constraint 2F ≤ 30 with 10 units of Mineral left over.
With the Capital constraint, you could also produce 25 Widgets and zero Flumps for a profit of $4(25) + $6(0) = $100, and this would satisfy the Labor and Mineral constraints as well, but this solution doesn’t yield as much revenue as 20 Widgets and 10 Flumps. So by evaluating the various nodes at the corners of the feasible solution set we have identified the profit-maximizing feasible combination of Widgets and Flumps as (20,10).
We could superimpose parallel iso-revenue lines on this graph with slopes equal to the output price ratio -$4/$6. The dashed line represents the maximum feasible iso-revenue, which has a unique intersection with the feasible set at the optimal boundary corner: $4(20) + $6(10) = $140. Small variations in the price ratio do not affect the solution. But if the price of Flumps rose from $6 to $8, the slope of the iso-revenue line -$4/$8 would equal the slope of the Labor constraint –1/2, and any solution along the boundary portion of the labor constraint, including the corners (10,15) and (20,10), would yield the same maximum revenue: $4(10) + $8(15) = $4(20) + $8(10) = $160. And if the price of Flumps rose any higher, the optimal solution would switch to (10,15)
The Labor and Capital constraints are binding. The Mineral constraint is non-binding: there are 10 “slack” (left-over) units of Mineral that you might have used to produce 5 more Flumps if only you had additional Capital and Labor too.
If you had just additional Capital, the orange Capital constraint line would shift outward, so the optimal solution node would move southeastward down the Labor constraint line. You would be producing more Widgets and less Flumps, and using even less Mineral. Since the Labor constraint is nearly parallel with the iso-revenue line, each unit of additional Capital would increase your revenues only slightly.
On the other hand, if you had just additional Labor instead, the blue Labor constraint line would shift outward, so the optimal solution node would move northwestward up the Capital constraint line. You would be producing more Flumps and less Widgets, and using more Mineral. This would increase your revenues a lot faster. So the graph suggests that Labor is the limiting factor with the highest implicit scarcity value.
The basic algorithm we used to solve this problem, evaluating sequential nodes until the optimum is found, is called the simplex method. The Solver utility in MS-Excel uses the same approach. Try opening a new worksheet and setting it up as shown here, entering the formulas to calculate revenues and inputs used from the output quantity cells:
Click Tools—Solver to access the Solver utility and specify the cell ranges containing the objective function (total revenue formula), the decision variables (product quantities) and constraints:
The “Add” button brings up the Add Constraint box in which you specify each set of constraints:
Clicking “Solve” yields the solution. You can save the solution with optional Answer, Sensitivity and Limit Reports as separate tabbed worksheets. The Sensitivity Report includes solution values for the Lagrangean multipliers, which represent input shadow prices; these values are copied into the right column of the original worksheet below:
The results verify the graphical solution: the output (20,10) yields maximum revenue $140 from 50 units of Capital, 40 units of Labor and 20 units of Mineral, with 10 units of Mineral left unused.
An input’s shadow price represents the marginal revenue that could be earned from an additional unit of it or, equivalently, the maximum the producer would be willing to pay for an additional unit of it. The shadow prices are decomposed from the output prices: it takes 2 units of Capital (at $0.66667 each) plus 1 unit of Labor ($2.6667) to produce a $4 Widget; and 1 unit of Capital ($0.66667) plus 2 units of Labor (at $2.6667 each) plus 2 units of Mineral (at $0 each) to produce a $6 Flump. Since Mineral is not a limiting factor, its shadow price is zero.
If you understood the 2-product 3-input example above, maybe try out this somewhat larger problem:
Your bakery makes cakes, pies, donuts, strudels, cookies and muffins based on the ingredient table, subject to the input constraints specified at the left of the table, and sells them for the unit prices specified at the bottom of the table. What is this bakery’s profit-maximizing mix of products? Which inputs are limiting factors, and what are their shadow prices? Which types of product don’t get baked, and what would be the shadow costs of making them (i.e., the minimum prices this bakery would have to charge to actually make them)?
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
