z Sensitivity Analysis and shadow prices Suggestion: Please try to complete at least 2/3 of the homework set by next Thursday 1 Goals of today’s lecture on Sensitivity Analysis z Changes in RHS – motivation from 2 dimensions – shadow prices, and their intervals z Changes in the cost coefficients z Treating shadow prices as real prices – pricing out and reduced costs 2 The DTC Problem K = number of slingshot kits manufactured (in 10s) S = number of stone shields manufactured (in 10s) Maximize Profit z = 3 K + 5 S (in 10s) 2 K + 3 S ≤ 10 Smoothing time: K + 2 S ≤ 6 Delivery time: K + S ≤ 5 Slingshot demand: K ≤ 4 Gathering time: Shield demand: S ≤ Non-negativity: K,S ≥ 0 3 3 S 3 2 gathering time 1 Isoprofit 1 2 3 4 K 4 S 3 K + 2S = 7 2 1 Isoprofit line 1 2 3 4 K 5 On Varying the RHS z Suppose we vary the amount of smoothing time from 0 to 10, and keep all other coefficients the same. z How will the profit change? z Let G(t) be the profit for DTC if smoothing time is t and all other data stays the same. 6 Optimum Profit Profit as a function of Smoothing Time 18 16 14 12 10 8 6 4 2 0 Slope = 0 Slope = 2.5 Slope = 1 Slope = 3 00 2 4 4 5 1/3 6 6.5 8 10 Smoothing Time 7 Shadow price (assume maximization). z The shadow price of the i-th constraint is the increase in the optimum objective value per unit increase of the RHS of the i-th constraint. z The shadow price is the derivative! It is defined based on the math formulation of the LP. z The shadow price of smoothing time is G’(6) = 1. z The shadow price is valid when the RHS changes within an interval: in this case it is valid for smoothing time from 5 1/3 to 6.5, if all other data remains the same. 8 Quick exercises z Using just the shadow price information and the range information, answer the following. – What is the optimum profit if smoothing time changes from 6 to 6.3? – What is the optimum profit if smoothing time changes from 6 to 5.7? – What is the optimum profit if smoothing time changes from 6 to 5? 9 Why are shadow prices valid in intervals? z The shadow price is valid in the interval in which “structure of the optimal solution” stays the same. z In 2 dimensions, this means that the shadow price is valid when the RHS is in an interval in which the same “corner point” solution remain z In multiple dimensions, it means that the shadow price is valid when the RHS changes so long as the optimal basic variables remain optimal. 10 S The shadow price of the “constraint K ≤ 4” is 0. 3 2 gathering time 1 Isoprofit 1 2 3 4 K 11 The Excel Sensitivity Report Name RHS Shadow Price Allowable Allowable Increase Decrease Gathering 10 1 1 1 Smoothing 6 1 0.5 0.67 Delivery 5 0 1E+30 1 Slingshot 4 0 1E+30 2 Shield 3 0 1E+30 1 12 Shadow prices of inequality constraints z If an inequality constraint is not binding for the optimal solution, then its shadow price is 0. 13 Shadow prices and managerial interpretations. z Shadow prices are derivatives. z They have a mathematical interpretation. – If the RHS of smoothing goes from 6 to 6 + ∆, then the objective value increases by ∆, for -2/3 <= ∆ <= .5 z And the shadow prices are useful to managers in sensitivity analysis. z Rule: Get the mathematical interpretation correct first. Then interpret it managerially. 14 Glass Example (from AMP) A manufacturer of glasses needs to determine the optimal mix of 6-oz juice glasses, 10 oz juice glasses, and champagne glasses. The constraints are as follows: z production capacity is limited to 60 hours z storage space is limited to 15,000 sq. ft. z The total demand for 6-oz juice glasses is at most 800 cases. Using data obtained by his assistant, the manufacturer formulated the linear program on the next slide. 15 Glass Example x1 = # of cases of 6-oz juice glasses (in 100s) x2 = # of cases of 10-oz cocktail glasses (in 100s) x3 = # of cases of champagne glasses (in 100s) max 5 x1 + 4.5 x2 + 6 x3 ($100s) 5 x2 + 8 x3 ≤ 60 (prod. cap. in hrs) s.t 6 x1 + 10 x1 + 20 x2 + 10 x3 ≤ 150 (wareh. cap. in 100s of ft2) x1 ≤ 8 (6-0z. glass dem. in 100s of cases) x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 16 Excel Sensitivity Report optimal solution: x1 = 6 3/7 x2 = 4 2/7 x3 = 0 optimal objective value is z = 51 3/7 ($100s) Constraint Shadow Allowable Allowable Name R.H. Side Price Increase Decrease Prod. Cap. 60 11/14 5 1/2 22 1/2 150 1/35 90 22 1E+30 1 4/7 W-house Cap. Juice Cap. 8 0 17 Some Managerial Questions Q. How much should you be willing to pay for two extra hours of production? A. The optimal objective value will increase by 2 × 11/14 = 11/7. This is $1,100/7 = $157 1/7 Q. How much would it cost you if production capacity decreased by 20 hours? By 25 hours? A. Q. How much would you be willing to pay for 50 extra square feet of warehouse space? A. 18 Brief Summary z The shadow price is the unit change in the optimal objective value per unit change in the RHS. z Shadow prices usually (but not always) have economic interpretations that are managerially useful. z Shadow prices are valid in an interval, which is provided by the Excel Sensitivity Report. This assumes that one RHS coefficient changes, but all others stay the same. z Excel provides shadow prices for our LPs** 19 Varying two RHS coefficients at once Q. Suppose that you are offered a package deal of 2 hours of labor plus 350 square feet of warehouse space. What would this deal be worth to you? A. Determine the value of 2 hours of labor and determine the value of 350 sq. ft. and add this two values. (But we are no longer sure if the prices will be valid for these changes.) 20 Next: Varying the Cost Coefficients The same corner point solution stays optimal if cost coefficients are changed only a little. Excel tells how much any one coefficient can change (the others remaining the same) so that the current bfs stays optimal. 21 Y Varying Cost coefficients 30 isoprofit line 20 10 Look for allowable increases and decreases in Excel sensitivity report. just another LP feasible region 10 20 30 40 x 22 Excel Spreadsheets: Varying the Cost coefficients Final Name Reduced Obj. Allowable Allowable Value Cost Coef. Increase Decrease Juice 6 3/7 0.000 5 0.4 4/11 Cocktail 4 2/7 0.000 4.5 2 1/3 Champagne 0 -4/7 6 4/7 1E+30 Champ 2. 0 -10/7 7 10/7 1E+30 The current solution stays optimal if an objective coef varies within its allowable range, and all other data stays constant. 23 Allowable increases and decreases Example: the current optimal solution is: x1 = 6 3/7 x2 = 4 2/7 x3 = 0 This solution remains optimal if c1 increases from 5 to 5.3 but not if it increases to 5.5. (But the optimal solution value will change.) How much can c3 decrease so that the optimal solution remains the same? How much can c3 increase so that the optimal solution remains the same? 24 Treating shadow prices as real prices: pricing out z Suppose that we consider the possibility of producing supersized champagne glasses. – profit = $7 per case – uses 10 hours of labor per 100 cases – uses 2000 sq feet per 100 cases z What would be the impact of producing exactly 100 cases of these glasses? 25 The impact of producing 100 cases of Champ 2 shadow price max 5 x1 s.t 6 x1 10 x1 1 x1 x1 ≥ + 4.5 x2 + 6 x3 + 7 x4 ($100s) + 5 x2 + 8 x3 + 10 x4 ≤ 60 ……11/14 + 20 x2 + 10 x3 + 20 x4 ≤ 150 ……1/35 …….0 ≤ 8 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 Reduced profit of x4 = The value of z goes down by 10/7 if we require x4 to be 1. This number is called the “reduced cost.” 7 - 10 x 11/14 - 20 x 1/35 - 1 x0 = 7 – 55/7 – 4/7 = -10/7 26 Reduced Costs (maximization) z The reduced cost in variable xj is the “increase” in the objective function if we require that xj ≥ 1. z More precisely, it is the shadow price of the constraint xj ≥ 0. – It is valid within a range (but this range is not provided). – It can be computed by “pricing out” z For non-basic variables, reduced costs are nonpositive. The allowable increase is the negative of the reduced cost. – Producing one unit of Champ 2 costs us 10/7. If we were to improve profitability by 10/7, then we would be willing to produce Champ 2. 27 Suppose that the number of production hours of Champ2 were 8. shadow price max 5 x1 s.t 6 x1 10 x1 1 x1 x1 ≥ + 4.5 x2 + 6 x3 + 7 x4 ($100s) + 5 x2 + 8 x3 + 8 10x4x4 ≤ 60 ……11/14 + 20 x2 + 10 x3 + 20 x4 ≤ 150 ……1/35 …….0 ≤ 8 0, x2 ≥ 0, x4 ≥ 0 Reduced profit of x4 = The profit increases by 1/7 if we require x4 to be 1. 7 -- 8 10 x 11/14 - 20 x 1/35 - 1 x0 = 7– - 55/7 44/7 – - 4/7 4/7 == -10/7 1/7 28 On pricing out z Suppose that we consider a variable that is not in the original problem. Suppose that the variable prices out so that its reduced cost is positive. z Then it would be desirable to produce that item. z For example, in the last slide, it would be profitable to produce large champagne glasses. 29 Excel Spreadsheets: The reduced costs Final Name Reduced Obj. Allowable Allowable Value Cost Coef. Increase Decrease Juice 6 3/7 0.000 5 0.4 4/11 Cocktail 4 2/7 0.000 4.5 2 1/3 Champagne 0 -4/7 6 4/7 1E+30 Champ 2. 0 -10/7 7 10/7 1E+30 30 Reduced costs for basic variables are always 0. Pricing Out of x1. shadow price max 5 x1 s.t 6 x1 10 x1 1 x1 x1 ≥ + 4.5 x2 + 6 x3 ($100s) + 5 x2 + 8 x3 ≤ 60 + 20 x2 + 10 x3 ≤ 150 ≤ 8 0, x2 ≥ 0, x3 ≥ 0 Reduced cost of x1 = ……11/14 ……1/35 …….0 5 - 6 x 11/14 - 10 x 1/35 - 1 x0 = 5 – 33/7 – 2/7 = 0 31 Pricing Out of x2 shadow price max 5 x1 s.t 6 x1 10 x1 1 x1 x1 ≥ + 4.5 x2 + 6 x3 ($100s) + 5 x2 + 8 x3 ≤ 60 + 20 x2 + 10 x3 ≤ 150 ≤ 8 0, x2 ≥ 0, x3 ≥ 0 Reduced cost of x2 = ……11/14 ……1/35 …….0 4.5 - 5 x 11/14 - 20 x 1/35 - 0 x0 = 4.5 – 55/14 – 4/7 = 0 32 Exercise Price Out x3 shadow price max 5 x1 s.t 6 x1 10 x1 1 x1 x1 ≥ + 4.5 x2 + 6 x3 ($100s) + 5 x2 + 8 x3 ≤ 60 + 20 x2 + 10 x3 ≤ 150 ≤ 8 0, x2 ≥ 0, x3 ≥ 0 ……11/14 ……1/35 …….0 Reduced cost of x3 = 33 Managerial Interpretations z How much would the price of champagne glasses have to increase before we would start producing champagne glasses. z If we were required to produce 200 cases of champagne glasses, what would be the impact on the overall profit? (Assume for now that the reduced costs and shadow prices remain valid in this interval.) z Suppose our accountant reported that our profit from cocktail glasses was 4 instead of 4.5. Would the optimal solution change? (HINT: Excel) 34 Optimum Profit ShadowProfit pricesas area piecewise constant and function of Smoothing decreasing as the RHS Time increases (Max problems.) 18 16 14 12 10 8 6 4 2 0 Slope = 0 Slope = 2.5 Slope = 1 Slope = 3 00 2 44 5 1/36 6.5 8 10 Smoothing Time 35 Shadow Price Shadow prices areapiecewise constant and Profit as function of Smoothing decreasing as the RHS increases (Max problems.) Time 184 16 143 12 102 8 61 4 20 0 00 2 44 5 1/3 6 6.5 8 10 Smoothing Time 36 Shadow Prices for “≤” constraints are nonnegative. z Having an extra hour of production time “improves” the objective function (or it stays the same). Why? z “Improve” for max problems means “increase”. z “Increase” means shadow price is positive. 37 Shadow Prices for “≥” constraints are nonpositive. z Suppose we require that x3 >= 1. z Making a constraint more restrictive makes the objective value worse (if it changes at all.) z Worse for max problems means decrease. z Decrease means that shadow price is negative. 38 Requiring at least u units of champagne glasses: the shadow price as a function of u 4 0 8 u -1 -2 The problem is infeasible if u ≥ 7.5 39 Summary slide z goal of today’s lecture – understand and utilize the sensitivity analysis report – develop geometric intuition on why sensitivity analysis is the way it is 40