|
Intro to Linear Programming
Consider the following problem:
To set this problem up for analysis, we define a joint production constraint for each of the inputs. For example, each widget requires 2 units of capital and each flump requires 1 unit of capital, and you only have 50 units of capital. The constraints are expressed as weak inequalities:
Capital: 2W + 1F ≤ 50 Labor: 1W + 2F ≤ 40 Minerals: 0W + 2F ≤ 30
We can visualize this constraint set in output space. The graph shows the three constraints as solid orange, blue and red lines. The shaded area of the graph represents all feasible combinations of Widgets and Flumps that satisfy all three constraints plus the obvious requirements that Widgets and Flumps can't be negative. One feasible solution is to produce nothing at all (W=0, F=0), for zero revenue. We consider alternative feasible solutions that yield positive revenues, marked with black dots at the boundary corners of the feasible solution set, and analyze each of these in turn.
The solution (W=0, F=15): with 30 units of Mineral you can produce a maximum of 15 Flumps for a revenue of $6(15) + $4(0) = $90. The Labor constraint W + 2F ≤ 40 is satisfied with 10 units of Labor left over, and the Capital constraint 2W + F ≤ 50 is satisfied with 35 units of Capital left over
The solution (W=10, F=15): with only 40 units of Labor you could produce either 40 Widgets or 20 Flumps, or any 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. The Capital constraint 2W + F ≤ 50 is satisfied with 15 units of Capital left over.
The solution (W=20, F=10): with only 50 units of Capital you could produce either 25 Widgets or 50 Flumps, or any 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. The Mineral constraint 2F ≤ 30 is satisfied with 10 units of Mineral left over.
The solution (W=25, F=0): with 50 units of capital you oould produce a maximum of 25 Widgets and 0 Flumps for a revenue of $4(25) + $6(0) = $100. The Labor constraint W + 2F ≤ 40 is satisfied with 25 units of Labor left over, and the Mineral constraint 2F ≤ 30 is satisfied with all 30 units of Mineral left over. So by evaluating the various nodes at the corners of the feasible solution set we have identified the revenue-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 will rotate the iso-revenue line slightly but will not affect the solution. 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 ratio rose any higher, the optimal solution would jump to (10,15)
At the optimal solution point the Labor and Capital constraints are binding while 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 a similar 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 the factor and non-negativity 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)?
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
