The spreadsheets for the following examples are here.
Example 1: The following linear program determines the most profitable mix of five products for Eagle Manufacturing. Product lines 1 and 3 are priced as a set including two of product 3 and 1 of product 1. They have only 180 of an essential part available. The total of the orders for the current period is 200. There are 280 production hours available, and 420 hours of assembly and packing time.
| Maximize: | 44x_2 + 80x_3 + 50x_4 + 60x_5 |
| Subject to: | 2x_2 + x_3 + 2x_4 + x_5 \le 280 Hours production |
| x_2 + x_3 + x_4 + x_5 \ge 200 Total orders | |
| 2x_1 + 2x_2 + x_3 + 3x_4 + x_5 \le 420 Hours assem and packing | |
| 2x_1 - x_3 = 0 Set constraint | |
| x_1 + x_5 \le 180 Key part | |
| x_1 \ge 0, x_2 \ge 0, x_3 \ge 0, x_4 \ge 0, x_5 \ge 0 |
The optimal tableau:
| x1 | x2 | x3 | x4 | x5 | s1 | p2 | a2 | s3 | a4 | s5 | |
| 4/3 | 1 | 1 | -1/3 | 2/3 | -2/3 | 20 | |||||
| -2/3 | -1 | 1 | -1/3 | -1/3 | 4/3 | 100 | |||||
| 4/3 | 1 | 2 | 2/3 | -1/3 | -2/3 | 160 | |||||
| 1 | 2/3 | 1 | 1/3 | 1/3 | -1/3 | 80 | |||||
| -1/3 | 0 | 1 | -1 | -2/3 | -2/3 | 2/3 | 60 | ||||
| 68/3 | 50 | 100/3 | -140/3 | 80/3 | 18800 |
Sensitivity report for variable cells by Solver
| Name | Final Value | Reduced Cost | Objective Coeff | Alllowable Inc | Allowable Dec |
| x1 | 80 | 0 | 0 | 80 | 34 |
| x2 | 0 | -22.67 | 44 | 22.67 | 1E+30 |
| x3 | 160 | 0 | 80 | 40 | 17 |
| x4 | 0 | -50 | 50 | 50 | 1E+30 |
| x5 | 100 | 0 | 60 | 34 | 20 |
Sensitivity report for constraints by Solver
| Name | Final Value | Shadow Price | Constraint RHS | Allowable Inc | Allowable Dec |
| Hours assem and packing | 420 | 33.33 | 420 | 60 | 180 |
| Set constraint | 0 | -46.67 | 0 | 90 | 30 |
| Key part | 180 | 26.67 | 180 | 30 | 75 |
| Hours production | 260 | 0 | 280 | 1E+30 | 20 |
| Total orders | 260 | 0 | 200 | 60 | 1E+30 |
- What number of total orders would make the solution degenerate?
- What would be the value of an additional part, and how many could they use at that price?
- What range of returns on the fourth product would make it profitable?
- What would the new basic solution be if they had an additional 15 parts?
- The company would like to increase the return on their fifth product. How much could they increase it without changing the set of basic variables?
- What increase in profit on the third product would produce a non-unique solution?
- What increase in the number of hours in assembly and packing hours would produce an objective function value of 19,800?
Solutions:
- The maximum increase in the right-hand-side (RHS) of constraint 2 is \min(-60/(-1)) = 60. Alternatively, by Solver, the allowable increase for total orders is 60.
- The value of an additional part is the value of s_5 in the objective row, namely 80/3. Alternatively, by Solver, the shadow price for key part is 26.67. The maximum increase in the RHS of constraint 5 is \min(20/(2/3), 160/(2/3), 80/(1/3))=30. Alternatively, by Solver, the allowable increase for key part is 30.
- The value of x_4 in the objective row, 50, means selling an addition fourth product would cost 50. To make it profitable, we have to increase the current return by 50. Therefore the range of returns is 100 to infinity.
- If they had an additional 15 parts, the right hand side column in the optimal tableau would become \begin{bmatrix}20-2/3\cdot 15\\ 100+4/3\cdot 15 \\ 160-2/3\cdot 15 \\ 80 - 1/3\cdot 15 \\ 60 + 2/3 \cdot 15 \\ 18800 + 80/3\cdot 15 \end{bmatrix} = \begin{bmatrix}10 \\ 120 \\ 150 \\ 75 \\ 70 \\ 19200 \end{bmatrix}. Therefore the new basic solution would be x_1 = 75, x_2 = 0, x_3 = 150, x_4 = 0, x_5 = 120.
- The maximum increase in the objective function coefficient (OFC) of x_5 is \min((68/3)/(2/3), 50/1, (100/3)/(1/3)) = 34. Alternatively, by Solver, the allowable increase of x_5 is 34.
- The maximum increase in OFC of x_3 is \min((80/3)/(2/3))=40. Alternatively, by Solver, the allowable increase of x_5 is 40.
- If the number of hours in assembly and packing hours had increased by \delta, then the objective function value would increase by 100/3\cdot \delta. To produce an objective function value of 19,800, we have 18,800 + 100/3\cdot \delta = 19,800 and so \delta = 30. Alternatively, by Solver, the shadow price on hours in assembly and packing is 100/3. An additional hour in assembly and packing has value 100/3. So to increase the objective function by 1000, we should increase assembly and packing hours by 1000 / (100/3) = 30.
Example 2: A thousand automobiles need to be produced by Tucker, Inc. in one month using their four production plants. This is a fairly normal demand for Tucker.
Due to technological advances and varying workforce, the plants have varied costs for the production of each car. At each plant, they also use different materials and labor amounts. A labor contract specifies that a minimum of four hundred cars must be produced at the third plant.
Here are some questions to be answered:
- What is the cost of production at the moment? What are the current quantities of production?
- If it cost only eight thousand dollars to produce a car at the second plant, how much will the solution change? For what cost range is the solution valid for the second plant? How much will the cost be for producing one vehicle? By producing one less, how much will you save?
- How much is the union contract costing? What value would it be to reduce the car requirement of 400 to 200 or even to zero cars? What would be the cost of increasing by 200 cars? By 100?
- For an additional hour of labor, how much are we willing to pay?
- By how much does the fourth plant need to reduce its cost in order to be used? By how much does it need its material usage reduced instead?
- What would one more unit of raw material be worth? How many units do we want to buy at this price?
- A CMU spinoff has developed a new, highly automated plant design which will use only 4 units of raw materials and 1 unit of workers and cost Tucker $5,000,000 to install. If this new design replaces the currently unproductive fourth plant about how long would it take to pay for itself in reduced costs?
This table summarizes the situation:
| Plant | Material | Labor | Cost per car in $1,000 |
|---|---|---|---|
| 1 | 3 | 2 | 15 |
| 2 | 4 | 3 | 10 |
| 3 | 5 | 4 | 9 |
| 4 | 6 | 5 | 7 |
There are 4,000 materials units and 3,300 hours of labor that can be allocated among the four plants.
Let x_i denote the number of cars made in plant i:
| Minimize: | 15x_1 + 10x_2 + 9x_3 + 7x_4 |
| Subject to: | x_1+x_2 + x_3 + x_4 = 1,000 Demand |
| x_3 \ge 400 Plant 3 contract | |
| 2x_1 + 3x_2 + 4x_3 + 5x_4 \le 3,300 Labor | |
| 3x_1 +4 x_2 + 5x_3 + 6x_4 \le 4,000 Materials | |
| x_1 \ge 0, x_2 \ge 0, x_3 \ge 0, x_4 \ge 0, x_5 \ge 0 |
Sensitivity report for variable cells by Solver:
| Name | Final Value | Reduced Cost | Objective Coeff | Alllowable Inc | Allowable Dec |
| x1 | 400 | 0 | 15 | 1E+30 | 3.5 |
| x2 | 200 | 0 | 10 | 2 | 1E+30 |
| x3 | 400 | 0 | 9 | 1E+30 | 4 |
| x4 | 0 | 7 | 7 | 1E+30 | 7 |
Sensitivity report for constraints by Solver:
| Name | Final Value | Shadow Price | Constraint RHS | Allowable Inc | Allowable Dec |
| Demand | 1000 | 30 | 1000 | 66.67 | 100 |
| Plant 3 contract | 400 | 4 | 400 | 100 | 400 |
| Labor | 3000 | 0 | 3300 | 1E+30 | 300 |
| Materials | 4000 | -5 | 4000 | 300 | 200 |
Solutions:
- The current quantities of production is x_1 = 400, x_2 = 200, x_3 = 400, x_4 = 0 and the cost of production at the moment is 15\times 400 + 10\times 200 + 9\times 400 + 7\times 0 = 11600 (k$), that is $11,600k.
- Observe that the allowable decrease for x_2 is infinity. If the cost to produce a car at the second plant is decrease by 2, then the basic variables remain the same. Also observe that the allowable increase for x_2 is 2. Therefore the range of the cost for the second plant is from 0 to $12k. The shadow price for demand, $30k, is the cost for producing one vehicle. By producing one less, you save $30k.
- Because the final value of Plant 3 contract is 400 and the shadow price of it is 4, the union contract is costing $1,600,000. Note the allowable decrease is 400. The value of the union contract would be 4\times 200 = 800 (thousand$) to reduce the car requirement of 400 to 200, and the value would be 0 to reduce the car requirement to 0. On the other hand, the allowable increase is 100, the cost of increasing by 200 cars is the same as by 100, which equals 4\times 100 = 400 (thousand$).
- Because the shadow price for labor is 0, we would not pay for labor unless it is free.
- Because the reduced cost for x_4 is 7, the fourth plant needs to reduce its cost by $7,000. Observe that the shadow price of materials is -5. This means a unit of reduction in the material usage (per car) at the 4th plant saves $5k. Currently, we lose $7k for each vehicle produced from the 4th plant. Therefore a reduction of 1.4 in the material usage (per car) in order to make the 4th plant profitable.
- Because the shadow price for raw material is -5, one more unit of raw material is worth $5,000. Because the allowable increase is 300, we want to buy 300 at this price.