z Sensitivity Analysis 2 – More on pricing out – Effects on final tableaus 1 Partial summary of last lecture z z z z z The shadow price is the unit change in the optimal objective value per unit change in the RHS. The shadow price for a “≥ 0” constraint is called the reduced cost. Shadow prices usually but not always have economic interpretations that are managerially useful. Shadow prices are valid in an interval, which is provided by the Excel Sensitivity Report. Reduced costs can be determined by pricing out 2 Goal for this lecture z Understand sensitivity analysis from an algebraic viewpoint. z How can one use information about tableaus to determine shadow price information and bound information? z An algebraic interpretation of pricing out 3 Running Example z Sarah can sell bags consisting of 3 gadgets and 2 widgets for $2 each. z She currently has 6 gadgets and 2 widgets. z She can purchase bags with 3 gadgets and 4 widgets for $3. z Formulate Sarah’s problem as an LP and solve it. 4 Shadow Prices can be found by examining the initial and final tableaus! maximize subject to z= -3x1 + 2x2 -3x1 + 3x2 +x3 -4x1 + 2x2 + x4 x1, x2, x3, x4 = = ≥ z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 6 2 0 5 The next steps z We will quickly move from the initial tableau to the final tableau. z Then we will interpret coefficients. z This analysis assumes that the initial tableau is in canonical form and that the final tableau is in canonical form. 6 The Initial Basic Feasible Solution z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 Apply the min ratio rule min (6/3, 2/2). The basic feasible solution is x1 = 0, x2 = 0, x3 = 6, x4 = 2 The entering variable is : The leaving variable is: x2 7 The 2nd Tableau z x1 x2 x3 x4 1 -1 3 -2 0 0 0 1 = 2 0 0 -3 3 3 0 1 -3/2 0 = 3 6 0 -4 -2 2 1 0 1/2 1 = 2 1 The basic feasible solution is x1 = 0, x2 = 1, x3 = 3, x4 = 0, z = 2 The next entering variable is The next leaving variable is x1 8 The 3rd Tableau z x1 x2 x3 x4 1 -1 0 0 1/3 0 1/2 1 = 3 2 0 3 1 0 1/3 1 -1/2 -3/2 = 3 1 0 -2 0 1 2/3 0 -1/2 1/2 = 1 3 The optimal basic feasible solution is x1 = 1, x2 = 3, x3 = 0, x4 = 0, z = 3 9 Shadow Price z The shadow price of a constraint is the increase in the optimum objective value per unit increase in the RHS coefficient, all other data remaining equal. z We will next determine the shadow price for constraint 1, gadgets on hand, which is the value of an extra gadget on hand. 10 Initial Tableau z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 Final Tableau z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 -1/2 = 3 bfs z=0 x1 = 0 x2 = 0 x3 = 6 x4 = 2 bfs z=3 x1 = 1 x2 = 3 x3 = 0 x4 = 0 11 Initial Tableau z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 0 + 1 0 Final Tableau z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 1/3 0 1 0 1/3 -1/2 = 1 + 1/3 0 0 1 2/3 -1/2 = 3 2/3 bfs z=0 x1 = 0 x2 = 0 x3 = 7 6 x4 = 2 bfs zz==331/3 xx11==111/3 xx22==332/3 xx33==00 xx44==00 12 On columns of the final tableau z Two columns that are identical in the initial tableau are also identical in the final tableau. z Suppose A and B are columns of the initial tableau, and let A’ and B’ be the corresponding columns of the final tableau. Let ∆ be a constant. – If B = ∆A, then B’ = ∆A’. 13 Determining the Shadow Price z If we increase the RHS of gadgets from 6 to 7, the objective value increases by 1/3. – So the shadow price is 1/3. z We next determine the range for the shadow price. How much can the RHS change so that the basis remains feasible and therefore optimum? 14 Initial Tableau z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 0 + ∆ 0 Final Tableau z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 ∆/3 0 1 0 1/3 -1/2 = 1 + ∆/3 0 0 1 2/3 -1/2 = 3 2∆/3 bfs z=0 x1 = 0 x2 = 0 x3 = 6 + ∆ x4 = 2 bfs zz==33+ ∆/3 xx11==11+ ∆/3 3 2∆/3 xx22==3+ xx33==00 xx44==00 15 The range for the shadow price on gadgets. Choose ∆ so that the final bfs stays non-negative 1 + ∆/3 ≥ 0 Î ∆ ≥ - 3 Sarah’s Tableaus 3 + 2∆/3 ≥ 0 Î ∆ ≥ - 9/2 maximum decrease = 3; Shadow price of constraint 1 is 1/3. maximum increase = ∞. z is permitted to be negative Final Tableau z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 ∆/3 0 1 0 1/3 -1/2 = 1 + ∆/3 0 0 1 2/3 -1/2 = 3 2∆/3 bfs z = 3 + ∆/3 x1= 1 + ∆/3 x2 = 3+ 2∆/3 x3 = 0 x4 = 0 16 Managerial Interpretation z Suppose that Sarah could sell gadgets at $.50. Should she sell any gadgets. If so, how many? z Suppose Sarah could purchase gadgets at $.25. Should she purchase gadgets. If so, how many? 17 Exercise with your neighbor z Work with your neighbor to determine the shadow price of the second constraint, the number of widgets on hand. z Then determine the range for which the shadow price is valid. z True or False: Determining the shadow price in this manner requires that we start with an initial bfs. It would not work without the bfs. 18 Initial Tableau z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 + Final Tableau z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 -1/2 = 3 bfs bfs + 19 On the cost coefficients in the final tableau z Next: how do we figure out reduced costs? z How do we figure out the range for the costs? 20 Initial Tableau z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 0 -4 2 0 1 = 2 z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 -1/2 = 3 21 Initial Tableau z x1 x2 x3 x4 z-row 1 1 3 -2 0 0 = 0 C1 0 -3 3 1 0 = 6 C2 0 -4 2 0 1 = 2 Let us label the rows. z-row 2 z x1 x2 x3 x4 1 0 0 1/3 1/2 The fact generalizes to all bases. = 3 0 1 0 1/3 = -1/2 1 Fact: There exists exists y1 and y2 such that 0 0 1 2/3 = -1/2 3 z-row 2 = z-row 1 + y1 C1 + y2 C2 . 22 1 0 0 1/3 1/2 3 = 1 3 -2 0 0 0 + 0 -3 y1 3 y1 y1 0 6 + 0 -4 y2 2 y2 0 y2 2 This is a system of 6 equations, but only two unknowns. 23 1 0 0 1/3 1/2 3 = 1 3 -2 0 0 0 + 0 -3 y1 3 y1 y1 0 6 + 0 -4 y2 2 y2 0 y2 2 y1 = 1/3 y2 = 1/2 Choose two trivial equations,but and solve This is athe system of 6 equations, only two them. unknowns. 24 1 0 0 1/3 1/2 3 = 1 3 -2 0 0 0 + 0 -3 y1 3 y1 y1 0 6 + 0 -4 y2 2 y2 0 y2 2 y1 = 1/3 y2 = 1/2 You Choose verify twothat trivial the equations, system works and for solve all the This can is athe system of 6 equations, but only two them. other equations. unknowns. 25 z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 y1 0 -4 2 0 1 = 2 y2 z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 -1/2 = 3 Multiplier 26 z x1 x2 x3 x4 1 3 -2 0 0 = 0 0 -3 3 1 0 = 6 y1 0 -4 2 0 1 = 2 y2 Multiplier y1 = 1/3 y2 = 1/2 z x1 x2 x3 x4 1 0 0 1/3 1/2 = 3 0 1 0 1/3 -1/2 = 1 The (simplex) multipliers of the constraints in the the shadow = 0optimal 0 tableau 1 2/3are -1/2 3prices! 27 Implications z We obtain the z-row in the final tableau by adding multiples of the original constraints to the original z-row. z We can easily compute these multiples if we start with a bfs. z Next we explore additional implications 28 Implications of Reduced Costs z Implication 1: We can compute range information for the costs. z How much can we modify the cost of x3 so that the current bfs remains optimal? – Suppose the cost of x3 is ∆. 29 Computing cost ranges for non-basic variables. z x1 x2 x3 x4 1 3 -2 0 -∆ 0 = 0 0 -3 3 1 0 = 6 1/3 0 -4 2 0 1 = 2 1/2 z x1 x2 x3 x4 1 0 0 -∆-1/3 1/3 +1/3 1/2 = 3 Multiplier For the basis to remain optimal, we need: -∆ + 1/3 ≥ 0 Î ∆ ≤ 1/3 30 Exercise to do with your neighbor (3 minutes) z Determine the range on the profit coefficient for x4, so that the basis remains optimal. 31 Pricing Out z x1 x2 x3 x4 x5 1 3 -2 0 0 -1 = 0 0 -3 3 1 0 2 = 6 1/3 0 -4 2 0 1 1 = 2 1/2 -3 Suppose that we add another variable, say x5. Should we produce x5? z x1 x2 x3 x4 1 0 0 1/3 1/2 RHS Multipliers x5 = 32 Simplex Multipliers z Every tableau has an associated set of multipliers, usually called simplex multipliers. z The simplex multipliers for the optimal tableau are the shadow prices. z Pricing out is very valuable algorithmically. We can use it to determine efficiently whether x5 could be an entering variable. – often used in practice 33 Changes in Cost Coefficients for Basic Variables. z Determining the range for cost coefficients for basic variables is more complex. z The final tableau must set the cost coefficients of basic variables to 0. 34 RHS Multiplier z x1 x2 x3 x4 1 3 -2 -2-∆ 0 0 = 0 0 -3 3 1 0 = 6 1/3 0 -4 2 0 1 = 2 1/2 Suppose we add ∆ to the profit coefficient for x2? z x1 x2 x3 x4 RHS 1 0 0 0-∆ 1/3 1/2 = 3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 -1/2 = 3 But now the final basis is no longer in canonical form. 35 Bringing it back to canonical form z x1 x2 x3 x4 RHS 1 0 0 0-∆ 1/3 1/2 = 3 0 1 0 1/3 -1/2 = 1 0 0 1 2/3 -1/2 = 3 z x1 x2 x3 x4 1 0 0 (1+2∆)/3 1/3 (1-∆)/2 1/2 0-∆ 0 1 0 1/3 0 0 1 2/3 Add ∆ times constraint 2 to the objective function. RHS = 3+3∆ 3 -1/2 = 1 -1/2 = 3 36 The range on the profit coefficient z x1 x2 x3 1 0 0 1 0 1/3 0 0 1 2/3 x4 0 (1+2∆)/3 1/3 (1-∆)/2 1/2 0+∆ RHS = 3+3∆ 3 -1/2 = 1 -1/2 = 3 For the basis to remain optimal, we need: (1+2∆)/3 ≥ 0 Î ∆ ≥ -1/2 and (1-∆)/2 ≥ 0 Î ∆ ≤ 1. So -1/2 ≤ ∆ ≤ 1 37 Some (challenging) short-answer questions z Suppose the optimal basis is degenerate. – Is there still a shadow price? – What can happen to the range? z Is it possible that there are two different sets of shadow prices? – Does this occur when there is degeneracy? – Does this occur when there are alternative optima? 38 Summary of Lecture z Using tableaus to determine information z Shadow prices and simplex multipliers z Determining upper and lower bounds on ∆ so that the shadow price remains valid. z Changes in cost coefficients. z The simplex algorithm can determine all shadow prices and reduced costs VERY quickly 39