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

《清华大学工业工程系运筹学课件().ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter4SensitivityAnalysisandDualityOperationsResearch(1)Dept.ofIndustrialEngineering2021/7/221Context4.1AGraphicalIntroductiontoSensitivityAnalysis4.2SomeImportantFormulas4.3SensitivityAnalysis4.4SensitivityAnalysisWhenMoreThanOneParameterisChanged:

2、The100%Rule4.5FindingtheDualofanLP4.6EconomicInterpretationoftheDualProblem24.1AGraphicalIntroductiontoSensitivityAnalysisGiapetto’sWoodcarvingExample:TypesoftoysSoldierTrainPrice$27$21Rawmaterial$10$9Variablelaborandoverheadcosts$14$10Labor:carpentry1

3、hour1hourLabor:finishing2hours1hourAvailableresource&Demand:Rawmaterial:unlimitedFinishinghours:100;Carpentryhours:80hoursTrains:unlimited;Soldiers:<=40Objective:Maximizeweeklyprofit3Solution:x1=numberofsoldiersproducedeachweekx2=numberoftrainsproduced

4、eachweekSolution:OptimalSolution:z=180,x1=20,x2=604As1,x2,s3Bx1,x2,s3Cx1,x2,s2D5EffectofaChangeinanObjectiveFunctionCoefficientx2=-C/2x1+constant/2?<=C<=?thecurrentbasisremainoptimal6EffectofaChangeinaRHSontheLP’sOptimalSolutionthecurrentbasisremainopt

5、imal?<=b1<=?b1=100+D2x1+x2=100+Dx1+x2=80x1=20+Dx2=60-D7ShadowPricesShadowPricesfortheithconstraintofanLPtobetheamountbywhichtheoptimalz-valueisimproved—increasedinamaxproblemanddecreasedinminproblem–iftherhsoftheithconstraintisincreasedby18MaxProblemNe

6、woptimalz-value=(oldoptimalz-value)+(Constrainti’sshadownprice)△biMinProblemNewoptimalz-value=(oldoptimalz-value)-(Constrainti’sshadownprice)△bi9ImportanceofSensitivityAnalysis:104.2SomeImportantFormulas11Tableau12SimplifyingFormulaforSlack,Excess,andA

7、rtificialVariablesNBVIftheyareBV,itscoefficients=?13Example1:Computetheoptimaltableau14zx1x2s1s2rhsBV110201200.510.50301.50-0.515154.3SensitivityAnalysisCriteria:Asimplextableau(maxproblem)forasetofbasicvariablesBVisoptimalifandonlyifeachconstrainthasa

8、nonnegativeright-handsideandeachvariablehasanonnegativecoefficientinrow0Methods:Usingthematrixforms,determinehowchangesintheLP’sparameterschangetherhsandrow0oftheoptimaltableauIfeachvariableinrow0hasanonnegativecoefficientandeachconstra