338 ACTIVITY 17: Shadow Prices and Penalty Costs

WHY:

This activity is designed to help you discover the meaning of shadow prices (solutions to the dual problem) and penalty costs (increase in value of the objective function when a non-basic variable is allowed to take on positive values). These concepts will prove very useful when doing post-optimality analysis on your major project. It will help you answer "what-if" questions for clients you work with in your future profession.

LEARNING OBJECTIVES:

  1. Discover how to identify the shadow prices and penalty costs from the solution of a linear programming problem.
  2. Understand the role these prices and costs play in post-optimality analysis.
  3. Assess the effectiveness of your team in maximizing learning.

PERFORMANCE CRITERIA:

  1. Quality of the answers to the Critical Thinking Questions.
  2. Quality of the learning experienced by the team.

INFORMATION:

Dual Problem
The dual to an LP problem in standard (unsymmetric primal) form (minimize C'X subject to AX = b, X >= 0) is the LP problem maximize b'Y subject to A'Y <= C.

Symmetric Primal Problem
The symmetric primal problem has the form minimize C'X subject to AX >= b, X >= 0

Symmetric Dual Problem
The symmetric dual problem has the form maximize b'Y subject to A'Y <= C, Y >= 0

Weak Duality Theorem
The weak duality theorem states that if both the primal and dual problems are feasible then b'Y <= C'X for all X >= 0 such that AX = b and for all Y such that A'Y <= C.

Corollary to the Weak Duality Theorem
If Xo = B^(-1)b is the optimal solution for the primal problem then there exists an optimal solution Yo = CB'B^(-1) to its dual and the respective objective function values of these two solutions are equal.

Shadow Prices
The shadow prices for a Linear Programming problem are the solutions to its dual. The ith shadow price is the change in the objective function resulting from a one unit increase in the ith coordinate of b. A shadow price is also the amount that an investor would have to pay for one unit of a resource in order to buy out the manufacturer.

Penalty Costs
Penalty Costs are the amounts the optimal value of the objective function would change for each unit increase in the non-basic variables. They are the negatives of the non-basic bottom row entries in the final tableau.

RESOURCES:

  1. Sections 3.6, 3.7: Strategic Mathematics
  2. Activity 16
  3. 30 minutes

MODEL:

       Problem 1.5, pa. 44                     Problem 1.6, pa. 45
    Minimize     .05x1 + .07x2                 max   10y1 + 300y2 
                                               Subj to:  
  Subject to:  .2x1 + 1.5x2   >= 10                  .2y1 + 30y2 <= .05
               30x1 +  35x2   >= 300                1.5y1 + 35y2 <= .07
                   all xi >= 0                         all yi >= 0

	| 0.2  1.5 |	  | 10 |
Let A = | 30   35  |, b = |300 |, C' = [ 0.05   0.07 ]

Then, it is clear that problem 1.5 is in symmetric primal form and that 1.6 is its symmetric dual. Thus 1.6 is the dual of 1.5 and 1.5 is the dual of 1.6. Since 1.6 is the easiest to solve, we will solve it and read the solution to 1.5 from the optimal tableau for 1.6. The following sequence of tableaus solve 1.6. First we have to change the objective function to

      -min -10y1 - 300y2       and introduce slack variables  y3  and  y4.

		 | 0.2  30  1  0 | 0.05 |
Initial Tableau: | 1.5  35  0  1 | 0.07 |  Pivot on the 30 to get 
		 |----------------------|
		 | 10  300  0  0 |    0 |

  | 0.007  1  0.033  0 | 0.00167 |
  | 1.267  0 -1.167  1 | 0.01167 |
  |------------------------------|
  |   8    0   -10   0 |    -5   |

Pivot on 1.267 to get the following final tableau:  
  
  | 0  1  0.04 -0.01 | 0.00167 |
  | 1  0 -0.92  0.79 | 0.00921 |
  |----------------------------|
  | 0  0 -2.63 -6.32 | -0.5737 |

Thus the maximum price for the pill is 57 cents, with the Vitamin B component selling price set at $0.009 and the Vitamin C component selling price set at $0.0016 per milligram.

Since the identity matrix in the original tableau is in the last two columns and the variables corresponding to these columns do not appear in the objective function, the entries under these columns in the final tableau contain the solution CB'B^(-1) to the dual (1.5) problem. Note that we have to change signs for the dual solution since the original problem was a maximize one. Thus the solution to problem 1.5 is that the mother pays a minimum of 57 cents for a serving of cereal that meets minimum daily requirements, as long as she buys 2.63 ounces of Snap and 6.32 ounces of Crackle.

Note that these values are the shadow prices from the mother's perspective. If the cost per ounce of Crackle went from 5 to 6 cents, the mother's total cost would increase from 57.37 cents to 57.37 + 2.63 = 60 cents. From the pill company's perspective, the shadow prices are the selling prices of the vitamins. If the minimum daily requirement of vitamin C goes from 300 to 301, the pill manufacturer could expect his per pill price to go from 57.37 cents to 57.37 + .16 = 57.53 cents The penalty costs for this problem are the same as the shadow prices, since the slack variables are the non-basic variables and the problem is a maximum one.

Looking at the solution to the Furnco problem (see Activity 16), we see that only finished chairs were made. Suppose that the manager wanted to know what would happen if she made some finished tables as well. Looking at the final tableau from the SIMPLEX printout in Activity 16, we see that the third column corresponds to finished tables. The bottom row entry under this column is -6.7. Thus Furnco would reduce their profit (i.e. increase their cost) by $6.70 for each unfinished table they made. This is a penalty cost.

CRITICAL THINKING QUESTIONS:

These will be provided in class.

Math 338 Activity 17 -- Revised 11/1/98

Return to the List of Activities