# Recitation 7

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
1. What number of total orders would make the solution degenerate?
2. What would be the value of an additional part, and how many could they use at that price?
3. What range of returns on the fourth product would make it profitable?
4. What would the new basic solution be if they had an additional 15 parts?
5. 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?
6. What increase in profit on the third product would produce a non-unique solution?
7. What increase in the number of hours in assembly and packing hours would produce an objective function value of 19,800?

Solutions:

1. 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.
2. 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.
3. 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.
4. 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$.
5. 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.
6. 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.
7. 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:

1. What is the cost of production at the moment? What are the current quantities of production?
2. 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?
3. 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?
4. For an additional hour of labor, how much are we willing to pay?
5. 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?
6. What would one more unit of raw material be worth? How many units do we want to buy at this price?
7. 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:

1. 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.
2. 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. 3. 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$).
4. Because the shadow price for labor is 0, we would not pay for labor unless it is free.
5. 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. 6. 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.