清华大学工业工程系运筹学课件(ppt).ppt

13 09 1 Chapter4SensitivityAnalysisandDuality OperationsResearch 1 Dept ofIndustrialEngineering 2 Context 4 1AGraphicalIntroductiontoSensitivityAnalysis4 2SomeImportantFormulas4 3SensitivityAnalysis4 4SensitivityAnalysisWhenMoreThanOneParameterisChanged The100 Rule4 5FindingtheDualofanLP4 6EconomicInterpretationoftheDualProblem 3 4 1AGraphicalIntroductiontoSensitivityAnalysis Giapetto sWoodcarvingExample AvailableresourceSoldiers 40Objective Maximizeweeklyprofit 4 Solution x1 numberofsoldiersproducedeachweekx2 numberoftrainsproducedeachweek Solution OptimalSolution z 180 x1 20 x2 60 5 6 EffectofaChangeinanObjectiveFunctionCoefficient x2 C 2x1 constant 2 C thecurrentbasisremainoptimal 7 EffectofaChangeinaRHSontheLP sOptimalSolution thecurrentbasisremainoptimal b1 b1 100 D 2x1 x2 100 Dx1 x2 80 x1 20 Dx2 60 D 8 ShadowPrices ShadowPricesfortheithconstraintofanLPtobetheamountbywhichtheoptimalz valueisimproved increasedinamaxproblemanddecreasedinminproblem iftherhsoftheithconstraintisincreasedby1 9 MaxProblemNewoptimalz value oldoptimalz value Constrainti sshadownprice biMinProblemNewoptimalz value oldoptimalz value Constrainti sshadownprice bi 10 ImportanceofSensitivityAnalysis 11 4 2SomeImportantFormulas 12 Tableau 13 SimplifyingFormulaforSlack Excess andArtificialVariables NBV IftheyareBV itscoefficients 14 Example1 Computetheoptimaltableau 15 16 4 3SensitivityAnalysis Criteria Asimplextableau maxproblem forasetofbasicvariablesBVisoptimalifandonlyifeachconstrainthasanonnegativeright handsideandeachvariablehasanonnegativecoefficientinrow0 Methods Usingthematrixforms determinehowchangesintheLP sparameterschangetherhsandrow0oftheoptimaltableauIfeachvariableinrow0hasanonnegativecoefficientandeachconstrainthasanonnegativerhs BVisstilloptimal Otherwise BVisnolongeroptimal 17 Example Optimalbasis BV svaluesZ value 18 1 ChangingtheObjectiveFunctionCoefficientofaNonbasicVariable Thecurrentbasisremainoptimal Thecurrentbasisisnolongeroptimal Anewbasicvariableinoptimalsolution 19 20 c2ischangedandBVremainsoptimal butthevaluesofdecisionvariablesandz valueremainunchanged 21 22 2 ChangingtheObjectiveFunctionCoefficientofabasicVariable Thecurrentbasisremainoptimal Thecurrentbasisisnolongeroptimal 23 3 ChangingtheRight HandSideofaConstraint Thecurrentbasisremainoptimal Thecurrentbasisisnolongeroptimal Dualsimplexalgorithm 24 4 ChangingtheColumnofaVariable BasicVariable NonbasicVariable RemainoptimalNolongeroptimal 25 5 AddingaNewActivity Optimal Nooptimal 26 Summary MaxProblem Next 27 4 4SensitivityAnalysisWhenMoreThanOneParameterIsChanged The100 Rule 1 The100 RuleforChangingObjectiveFunctionCoefficients Case1 Allvariablewho sobjectivefunctioncoefficientsarechangedhavenonzeroreducedcostsintheoptimalrow0 Case2 Atleastonevariablewhoseobjectivefunctioncoefficientischangedhasareducedcostofzero 28 Ifandonlyiftheobjectivefunctioncoefficientforeachvariableremainswithintheallowablerange thecurrentbasisremainsoptimal boththevaluesofthedecisionvariablesandobjectivefunctionremainunchanged Iftheobjectivefunctioncoefficientforanyvariableisoutsideitsallowablerange thecurrentbasisisnolongeroptimal Case1 29 Case2 100 Rule Defineratiorj 30 2 The100 RuleforChangingRight HandSides Case1 Allconstraintswhoseright handsidesarebeingmodifiedarenonbindingconstraints Case2 Atleastoneoftheconstraintswhoseright handsideisbeingmodifiedisabindingconstraint 31 Ifandonlyifeachright handsideremainswithinitsallowablerange Thenboththevaluesofthedecisionvariablesandoptimalobjectivefunctionremainunchanged Iftheobjectivefunctioncoefficientforanyvariableisoutsideitsallowablerange thecurrentbasisisnolongeroptimal Case1 32 Case2 100 Rule Defineratiorj 33 4 5FindingtheDualofanLP Normalmaxproblem Normalminproblem DUAL 34 FindingtheDualofaNormalMaxorMinProblem 35 Example 36 FindingtheDualofaNonnormalLP Transformnonnormalformintonormalform For constraint Multiplyby 1 For constraint Forurs x x x 37 Example 38 FindingtheDualofaNonnormalMaxProblem For constraints dualvariablesmustsatisfy 0 For constraints dualvariablesisurs Forurs svariable thedualconstraintisanequalityconstraint 39 Example 40 FindingtheDualofaNonnormalMinProblem For constraints dualvariablesmustsatisfy 0 For constraints dualvariablesisurs Forurs svariable thedualconstraintisanequalityconstraint 41 Exercise 42 4 6EconomicInterpretationoftheDualProblem InterpretingtheDualofaMa