运筹学 05.pptx

Chapter5SensitivityAnalysis AnAppliedApproach toaccompanyOperationsResearch ApplicationsandAlgorithms4theditionbyWayneL Winston Copyright c 2004Brooks Cole adivisionofThomsonLearning Inc 5 1 AGraphicalIntroductiontoSensitivityAnalysis SensitivityanalysisisconcernedwithhowchangesinanLP sparametersaffecttheoptimalsolution ReconsidertheGiapettoproblemfromChapter3 Where x1 numberofsoldiersproducedeachweekx2 numberoftrainsproducedeachweek maxz 3x1 2x22x1 x2 100 finishingconstraint x1 x2 80 carpentryconstraint x1 40 demandconstraint x1 x2 0 signrestriction TheoptimalsolutionforthisLPwasz 180 x1 20 x2 60 pointB andithasx1 x2 ands3 theslackvariableforthedemandconstraint asbasicvariables Howwouldchangesintheproblem sobjectivefunctioncoefficientsorright handsidevalueschangethisoptimalsolution GraphicalanalysisoftheeffectofachangeinanobjectivefunctionvaluefortheGiapettoLPshows Byinspection wecanseethatmakingtheslopeoftheisoprofitlinemorenegativethanthefinishingconstraint slope 2 willcausetheoptimalpointtoswitchfrompointBtopointC Likewise makingtheslopeoftheisoprofitlinelessnegativethanthecarpentryconstraint slope 1 willcausetheoptimalpointtoswitchfrompointBtopointA Clearly theslopeoftheisoprofitlinemustbebetween 2and 1forthecurrentbasistoremainoptimal Agraphicalanalysiscanalsobeusedtodeterminewhetherachangeintherhsofaconstraintwillmakethecurrentbasisnolongeroptimal Forexample letb1 numberofavailablefinishinghours Thecurrentoptimalsolution pointB iswherethecarpentryandfinishingconstraintsarebinding Ifthevalueofb1ischanged thenaslongaswherethecarpentryandfinishingconstraintsarebinding theoptimalsolutionwillstilloccurwherethecarpentryandfinishingconstraintsintersect IntheGiapettoproblemtotheright weseethatifb1 120 x1willbegreaterthan40andwillviolatethedemandconstraint Also ifb1 80 x1willbelessthan0andthenonnegativityconstraintforx1willbeviolated Therefore 80 b1 120Thecurrentbasisremainsoptimalfor80 b1 120 butthedecisionvariablevaluesandz valuewillchange Itisoftenimportanttodeterminehowachangeinaconstraint srhschangestheLP soptimalz value TheshadowpricefortheithconstraintofanLPistheamountbywhichtheoptimalz valueisimprovediftherhsoftheithconstraintisincreasedbyone Thisdefinitionappliesonlyifthechangeintherhsofconstraintileavesthecurrentbasisoptimal Forthefinishingconstraint 100 finishinghoursareavailable TheLP soptimalsolutionisthenx1 20 andx2 60 withz 3x1 2x2 3 20 2 60 180 Thus aslongasthecurrentbasisremainsoptimal aone unitincreaseinthenumberoffinishinghourswillincreasetheoptimalz valueby 1 So theshadowpriceforthefirst finishinghours constraintis 1 Sensitivityanalysisisimportantforseveralreasons ValuesofLPparametersmightchange Ifaparameterchanges sensitivityanalysisshowsitisunnecessarytosolvetheproblemagain ForexampleintheGiapettoproblem iftheprofitcontributionofasoldierchangesto 3 50 sensitivityanalysisshowsthecurrentsolutionremainsoptimal UncertaintyaboutLPparameters IntheGiapettoproblemforexample iftheweeklydemandforsoldiersisatleast20 theoptimalsolutionremains20soldiersand60trains Thus evenifdemandforsoldiersisuncertain thecompanycanbefairlyconfidentthatitisstilloptimaltoproduce20soldiersand60trains 5 2TheComputerandSensitivityAnalysis IfanLPhasmorethantwodecisionvariables therangeofvaluesforarhs orobjectivefunctioncoefficient forwhichthebasisremainsoptimalcannotbedeterminedgraphically Theserangescanbecomputedbyhandbutthisisoftentedious sotheyareusuallydeterminedbyapackagedcomputerprogram LINDOwillbeusedandtheinterpretationofitssensitivityanalysisdiscussed Example1 WincoProducts1 Wincosellsfourtypesofproducts Theresourcesneededtoproduceoneunitofeachareknown Tomeetcustomerdemand exactly950totalunitsmustbeproduced Customersdemandthatatleast400unitsofproduct4beproduced FormulateanLPtomaximizeprofit Example1 Solution Letxi numberofunitsofproductiproducedbyWinco TheWincoLPformulation maxz 4x1 6x2 7x3 8x4s t x1 x2 x3 x4 950 x4 4002x1 3x2 4x3 7x4 46003x1 4x2 5x3 6x4 5000 x1 x2 x3 x4 0 Ex 1 Solutioncontinued TheLINDOoutput Reducedcostistheamounttheobjectivefunctioncoefficientforvariableiwouldhavetobeincreasedfortheretobeanalternativeoptimalsolution MAX4X1 6X2 7X3 8X4SUBJECTTO2 X1 X2 X3 X4 9503 X4 4004 2X1 3X2 4X3 7X4 46005 3X1 4X2 5X3 6X4 5000ENDLPOPTIMUMFOUNDATSTEP4OBJECTIVEFUNCTIONVALUE1 6650 000VARIABLEVALUEREDUCEDCOSTX10 0000001 000000X2400 0000000 000000X3150 0000000 000000X4400 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000003 0000003 0 000000 2 0000004 0 0000001 0000005 250 0000000 000000NO ITERATIONS 4 Ex 1 Solutioncontinued LINDOsensitivityanalysisoutputAllowablerange w ochangingbasis forthex2coefficient c2 is 5 50 c2 6 667Allowablerange w ochangingbasis fortherhs b1 ofthefirstconstraintis 850 b1 1000 RANGESINWHICHTHEBASISISUNCHANGED OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX14 0000001 000000INFINITYX26 0000000 6666670 500000X37 0000001 0000000 500000X48 0000002 000000INFINITYRIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2950 00000050 000000100 0000003400 00000037 500000125 00000044600 000000250 000000150 00000055000 000000INFINITY250 000000 Ex 1 Solutioncontinued ShadowpricesareshownintheDualPricessectionofLINDOoutput Shadowpricesaretheamounttheoptimalz valueimprovesiftherhsofaconstraintisincreasedbyoneunit assumingnochangeinbasis MAX4X1 6X2 7X3 8X4SUBJECTTO2 X1 X2 X3 X4 9503 X4 4004 2X1 3X2 4X3 7X4 46005 3X1 4X2 5X3 6X4 5000ENDLPOPTIMUMFOUNDATSTEP4OBJECTIVEFUNCTIONVALUE1 6650 000VARIABLEVALUEREDUCEDCOSTX10 0000001 000000X2400 0000000 000000X3150 0000000 000000X4400 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000003 0000003 0 000000 2 0000004 0 0000001 0000005 250 0000000 000000NO ITERATIONS 4 Shadowpricesigns Constraintswith symbolswillalwayshavenonpositiveshadowprices Constraintswith willalwayshavenonnegativeshadowprices Equalityconstraintsmayhaveapositive anegative orazeroshadowprice Foranyinequalityconstraint theproductofthevaluesoftheconstraint sslack excessvariableandtheconstraint sshadowpricemustequalzero Thisimpliesthatanyconstraintwhoseslackorexcessvariable 0willhaveazeroshadowprice Similarly anyconstraintwithanonzeroshadowpricemustbebinding haveslackorexcessequalingzero Forconstraintswithnonzeroslackorexcess relationshipsaredetailedinthetablebelow Whentheoptimalsolutionisdegenerate abfsisdegenerateifatleastonebasicvariableintheoptimalsolutionequals0 cautionmustbeusedwheninterpretingtheLINDOoutput ForanLPwithmconstraints iftheoptimalLINDOoutputindicateslessthanmvariablesarepositive thentheoptimalsolutionisdegeneratebfs MAX6X1 4X2 3X3 2X4SUBJECTTO2 2X1 3X2 X3 2X4 4003 X1 X2 2X3 X4 1504 2X1 X2 X3 0 5X4 2005 3X1 X2 X4 250 5 3ManagerialUseofShadowPrices Themanagerialsignificanceofshadowpricesisthattheycanoftenbeusedtodeterminethemaximumamountamangershouldbewillingtopayforanadditionalunitofaresource Example5 WincoProducts2 ReconsidertheWincototheright WhatisthemostWincoshouldbewillingtopayforadditionalunitsofrawmaterialorlabor 5 4WhathappenstotheOptimalz ValueiftheCurrentBasisIsNoLongerOptimal Shadowpriceswereusedtodeterminethenewoptimalz valueiftherhsofaconstraintwaschangedbutremainedwithintherangewherethecurrentbasisremainsoptimal ChangingtherhsofaconstrainttovalueswherethecurrentbasisisnolongeroptimalcanbeaddressedbytheLINDOPARAMETRICSfeature Thisfeaturecanbeusedtodeterminehowtheshadowpriceofaconstraintandoptimalz valuechange ForanyLP thegraphoftheoptima