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

OperationsResearch(I)Dept.ofIndustrialEngineering18:581Chapter4SensitivityAnalysisandDualityOperationsResearch(1)Dept.ofIndustrialEngineeringAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China2Context4.1AGraphicalIntroductiontoSensitivityAnalysis4.2SomeImportantFormulas4.3SensitivityAnalysis4.4SensitivityAnalysisWhenMoreThanOneParameterisChanged:The100%Rule4.5FindingtheDualofanLP4.6EconomicInterpretationoftheDualProblemAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China34.1AGraphicalIntroductiontoSensitivityAnalysisGiapetto’sWoodcarvingExample:TypesoftoysSoldierTrainPrice$27$21Rawmaterial$10$9Variablelaborandoverheadcosts$14$10Labor:carpentry1hour1hourLabor:finishing2hours1hourAvailableresource&Demand:Rawmaterial:unlimitedFinishinghours:100;Carpentryhours:80hoursTrains:unlimited;Soldiers:=40Objective:MaximizeweeklyprofitAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China4Solution:2123maxxxz40801002.).(12121xxxxxtstosubject0021xxx1=numberofsoldiersproducedeachweekx2=numberoftrainsproducedeachweekSolution:OptimalSolution:z=180,x1=20,x2=60Author:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China50,,,,40801002..23max321213122112121sssxxsxsxxsxxtsxxzAs1,x2,s3Bx1,x2,s3Cx1,x2,s2DAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China6EffectofaChangeinanObjectiveFunctionCoefficientx2=-C/2x1+constant/2?=C=?thecurrentbasisremainoptimal0,,,,40801002..23max321213122112121sssxxsxsxxsxxtsxxzAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China7EffectofaChangeinaRHSontheLP’sOptimalSolutionthecurrentbasisremainoptimal?=b1=?b1=100+D2x1+x2=100+Dx1+x2=80x1=20+Dx2=60-D0,,,,40801002..23max321213122112121sssxxsxsxxsxxtsxxzAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China8ShadowPricesShadowPricesfortheithconstraintofanLPtobetheamountbywhichtheoptimalz-valueisimproved—increasedinamaxproblemanddecreasedinminproblem–iftherhsoftheithconstraintisincreasedby1Author:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China9MaxProblemNewoptimalz-value=(oldoptimalz-value)+(Constrainti’sshadownprice)△biMinProblemNewoptimalz-value=(oldoptimalz-value)-(Constrainti’sshadownprice)△biAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China10ImportanceofSensitivityAnalysis:Author:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China114.2SomeImportantFormulasnixbxaxaxabxaxaxabxaxaxatsxcxcxczimnmnnmnnnnnn,2,10..max(min)2211222221211121211122110,..NBVBVNBVBVNBVNBVBVBVXXbNXBXtsXCXCz0,..0111111NBVBVNBVBVNBVBVBVNBVNBVBVNBVNBVNBVBVXXbBNXBXbNXBXtsbBCXCNBCzXCNXBbBCzAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China12TableaubBNBIbBCCNBCRHSXXZmBVNBVBVNBVBV11110010,..0111111NBVBVNBVBVNBVBVBVNBVNBVBVNBVNBVNBVBVXXbBNXBXbNXBXtsbBCXCNBCzXCNXBbBCzAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China13SimplifyingFormulaforSlack,Excess,andArtificialVariables10BCofelementithrowoptimalinsvariableslackoftCoefficienBVi10BCofelementithrowoptimalinevariableexcessoftCoefficienBViproblemMaxMBCofelementithrowoptimalinaartificialoftCoefficienBVi10variablebBNBIbBCCNBCRHSXXZmBVNBVBVNBVBV1111001NBVIftheyareBV,itscoefficients=?Author:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China14Example1:Computetheoptimaltableau2221212121,0,8262..4maxsxBVxxxxxxtsxxz1102BbBNBIbBCCNBCRHSXXZmBVNBVBVNBVBV1111001Author:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China152221212121,0,8262..4maxsxBVxxxxxxtsxxzTNBVBVbCCNB8,60,1,0,40211,1102bBNBIbBCCNBCRHSXXZmBVNBVBVNBVBV1111001TBVNBVBVbBNBbBCCNBC5,35.05.15.05.0122,11111zx1x2s1s2rhsBV110201200.510.50301.50-0.515Author:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China164.3SensitivityAnalysisCriteria:Asimplextableau(maxproblem)forasetofbasicvariablesBVisoptimalifandonlyifeachconstrainthasanonnegativeright-handsideandeachvariablehasanonnegativecoefficientinrow0Methods:Usingthematrixforms,determinehowchangesintheLP’sparameterschangetherhsandrow0oftheoptimaltableauIfeachvariableinrow0hasanonnegativecoefficientandeachconstrainthasanonnegativerhs,BVisstilloptimal.Otherwise,BVisnolongeroptimal.Author:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Beijing,China17Example:32213132121332123211321321321,,,,,0,,,,85.05.12205.1244868..0203060203060maxssxNBVxxsBVsssxxsxxxsxxxsxxxtsxxxzxxxzOptimalbasis?BV’svaluesZ-valueAuthor:ZhangZhihai,Dept.ofIndustrialEngineering,TsinghuaUniversity,100084,Be