Sensitivity Analysis 2Partial summary of last lectureRunning Example (data from lecture 4)Shadow Prices can be found by examining the initial and final tableaus!The Initial Basic Feasible SolutionThe 2nd TableauThe 3rd TableauShadow PricePowerPoint PresentationReduced CostsMore on reduced costsSlide 12Slide 13Slide 14Implications of Reduced CostsSlide 16Slide 17Slide 18Slide 19Slide 20Slide 21More on Pricing OutSlide 23A useful fact from linear algebraSlide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34On varying the RHSSlide 36Summary of LectureSome Extra InsightShadow price vs slack variableSlide 40Shadow price vs slack variableQuick SummaryMIT and James Orlin © 20031Sensitivity Analysis 2–More on pricing out–Effects on final tableausMIT and James Orlin © 20032Partial summary of last lecture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 outMIT and James Orlin © 20033Running Example (data from lecture 4)Sarah can sell bags consisting of 3 gadgets and 2 widgets for $2 each. She currently has 6 gadgets and 2 widgets. She can purchase bags with 3 gadgets and 4 widgets for $3. Formulate Sarah’s problem as an LP and solve it.MIT and James Orlin © 20034Shadow Prices can be found by examining the initial and final tableaus!-3==3 1260x1x2x4x3-4 2 0 1-3 2 00-z001=0maximize z = -3x1 + 2x2 subject to -3x1 + 3x2 +x3 = 6 -4x1 + 2x2 + x4 = 2 x1, x2, x3, x4  0MIT and James Orlin © 20035-3 2 001-3 3 1 0-4 2 0 100The Initial Basic Feasible Solution==26x1x2x4x3-z=0The basic feasible solution is x1 = 0, x2 = 0, x3 = 6, x4 = 2What is the entering variable?x2What is the leaving variable?x42min (6/3, 2/2).3 622Apply the min ratio ruleMIT and James Orlin © 20036-3 2 001-3 3 1 0-4 2 0 100The 2nd Tableau==26x1x2x4x3-z=0The basic feasible solution is x1 = 0, x2 = 1, x3 = 3, x4 = 0, z = 21 0 -100 1 -3/2-2 1 0 1/2 13-2What is the next entering variable?x1What is the next leaving variable?x33MIT and James Orlin © 200371 0 -103 0 1 -3/2-2 1 0 1/2 13-20 0 -1/2-1/311 0 1/3 -1/20 1 2/3 -1/200The 3rd Tableau==31x1x2x4x3-z=-3The optimal basic feasible solution is x1 = 1, x2 = 3, x3 = 0, x4 = 0, z = 3MIT and James Orlin © 20038Shadow Price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.What is the shadow price for constraint 1, gadgets on hand? This is the value of an extra gadget on hand.MIT and James Orlin © 20039-3 2 001-3 3 1 0-4 2 0 100==26x1x2x4x3-z=00 0 -1/2-1/31 0 1/3 -1/20 1 2/3 -1/2 31-3100==x1x2x4x3-z=Initial TableauFinal TableauMIT and James Orlin © 200310Reduced CostsThe reduced cost of a variable x is the shadow price of the “x  0” constraint. It is also the cost coefficient for x in the final tableau.Suppose in the previous example that we required that x3  1? What is the impact on the optimal objective value? What is the resulting solution?By the previous slide, the impact is –1/3.Sarah’s ProblemMIT and James Orlin © 200311More on reduced costsIn a pivot, multiples of constraints are added to the cost row. We will use this fact to determine explicitly how the cost row in the final tableau is obtained.MIT and James Orlin © 200312-3 2 001-3 3 1 0-4 2 0 100==26x1x2x4x3-z=00 0 -1/2-1/31 0 1/3 -1/20 1 2/3 -1/2 31-3100==x1x2x4x3-z=Initial TableauThe cost row in the final tableau is obtained by adding multiples of original constraints to the original cost row.MIT and James Orlin © 200313-3 2 0 01 0-2 1 -1/3 01 -20 0 -1/2-1/31 0 1/3 -1/20 1 2/3 -1/2 31-3-3 2 001-3 3 1 0-4 2 0 100==26x1x2x4x3-z=0100==x1x2x4x3-z=How are the reduced costs in the 2nd tableau below obtained?-1/31Take the initial cost coefficients.Then subtract 1/3 of constraint 1.-1/3MIT and James Orlin © 200314-3 2 0 01 0-2 1 -1/3 01 -20 0 -1/2-1/31 -30 0 -1/2-1/31 0 1/3 -1/20 1 2/3 -1/2 31-3-3 2 001-3 3 1 0-4 2 0 100==26x1x2x4x3-z=0100==x1x2x4x3-z=-1/3-1/21Next: subtract ½ of constraint 2 from these costs.-1/2MIT and James Orlin © 200315Implications of Reduced CostsImplication 1: increasing the cost coefficient of a non-basic variable by  leads to an increase of its reduced cost by .MIT and James Orlin © 2003160 0 -1/2-1/31 0 1/3 -1/20 1 2/3 -1/2 31-3-3 2 001-3 3 1 0-4 2 0 100==26x1x2x4x3-z=0100==x1x2x4x3-z=What is the effect of adding  to the cost coefficient for x3?FACT: Adding  to the cost coefficient in an initial tableau also adds  to the same coefficient in subsequent tableaus -1/3-1/3-1/21MIT and James Orlin © 200317000 021 030 12-3 01-3 0-4 100==26x1x4-z=0100x1x2-zWhat is the effect of adding  to the cost coefficient for x2?010x3x220RHS-1/2-1/2-1/2==31x4=-3-1/31/32/3x3RHSSarah’s ProblemMIT and James Orlin © 200318000 021 030 12-3 01-3 0-4 100==26x1x4-z=0100x1x2-zSubtract  times row 3 from row 1 to get it back in canonical form.010x3x220RHS-1/2-1/2-1/2==31x4=-3-1/31/32/3x3RHS-1/2 +/2-3- -1/3-2/30How large can  be?0 1 for the tableau to remain optimal. Bound on changes in cost coefficients.Sarah’s ProblemMIT and James Orlin © 200319Implications of Reduced CostsImplication 2: We can compute the reduced cost of any variable if we know the original column and if we know the “prices” for each constraint.MIT and James Orlin © 200320x5x50 0 -1/31 0 1/30 1 2/3 31-3-3 2 01-3 3 1-4 2 03/22100==26x1x2x5x3-z=0100==x1x2x3-z=Suppose that we add another variable, say x5. Should we produce x5? What is c5?-1/2-1/2-1/2001x4x4RHS1/21/3PricesMIT and James Orlin © 200321x5x50 0 1/3-1/31 0 1/30 1 2/3 31-3-3 2 01-3 3 1-4 2 03/22100==26x1x2x5x3-z=0100==x1x2x3-z=FACT: We can compute the reduced cost of a new variable. If the reduced cost is positive, it should be entered into the basis. -1/2-1/2-1/2001x4x4c5 = 3/2 - 2*1/3 – 1*1/2 = 1/3 RHS1/21/3PricesMIT and James Orlin © 200322More on Pricing OutEvery tableau