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

2020/6/9,1,Chapter4SensitivityAnalysisandDuality,OperationsResearch(1),Dept.ofIndustrialEngineering,2,Context,4.1AGraphicalIntroductiontoSensitivityAnalysis4.2SomeImportantFormulas4.3SensitivityAnalysis4.4SensitivityAnalysisWhenMoreThanOneParameterisChanged:The100%Rule4.5FindingtheDualofanLP4.6EconomicInterpretationoftheDualProblem,3,4.1AGraphicalIntroductiontoSensitivityAnalysis,GiapettosWoodcarvingExample:,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,EffectofaChangeinaRHSontheLPsOptimalSolution,thecurrentbasisremainoptimal,?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:Allvariablewhosobjectivefunctioncoefficientsarechangedhavenonzeroreducedcostsintheoptimalrow0,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,Forurssvariable,thedualconstraintisanequalityconstraint,39,Example:,40,FindingtheDualofaNonnormalMinProblem,For=constraints,dualvariablesmustsatisfy=0,For=constraints,dualvariablesisurs,Forurssvariable,thedualconstraintisanequalityconstraint,41,Exercise:,42,4.6EconomicInterpretationoftheDualProblem,InterpretingtheDualofaMaxProblem,43,Decisionvariables:y1=pricepaidfor1boardftoflumbery2=pricepaidfor1f