運籌學單純形法

上傳人：2*** IP屬地：湖北上傳時間：2023-02-01 格式：PPT 頁數(shù)：60 大?。?93KB 積分：28 舉報 版權申訴

已閱讀5頁，還剩55頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

TheSimplexMethodIntroductionTheSimplexMethodageneralprocedureforsolvinglinearprogrammingproblemsOriginsofthesimplexmethod1947Dantzigprovedtobearemarkablyefficientmethodthatisusedroutinelytosolvehugeproblemsontoday’scomputersWhydowestudythesimplexmethod?GraphicalmethodcanonlysolvetoyproblemsComputingprincipleofsoftwares.TheEssenceoftheSimplexMethodThesimplexmethodisanalgebraicprocedure.However,itsunderlyingconceptsaregeometric.Wefirstfindacorner-pointfeasiblesolution(CPFsolution).ExaminewhethertheCPFsolutionisoptimal.Ifthesolutionisnotoptimal,findabetterCPFsolution,whichisusuallyadjacenttothelastsolution.Iteratetheabovetwostepsuntilanoptimalsolutionisfoundoritisindicatedtheproblemhasnooptimalsolution.TheEssenceoftheSimplexMethod602424x1x2(6,0)(4,6)(4,3)(2,6)(0,9)(0,6)(0,0)(4,0)TheEssenceoftheSimplexMethodInitialization:Choose(0,0)astheinitialCPFsolutiontoexamine.(ThisisaconvenientchoicebecausenocalculationarerequiredtoidentifythisCPFsolution.)OptimalityTest:Concludethat(0,0)isnotanoptimalsolution.(AdjacentCPFsolutionsarebetter.)602424x1x2(6,0)(4,6)(4,3)(2,6)(0,9)(0,6)(0,0)(4,0)TheEssenceoftheSimplexMethodIteration1:MovetoabetteradjacentCPFsolution,(0,6),byperformingthefollowingthreesteps.602424x1x2(6,0)(4,6)(4,3)(2,6)(0,9)(0,6)(0,0)(4,0)Betweenthetwoedgesofthefeasibleregionthatemanatefrom(0,0),choosetomovealongtheedgethatleadsupthex2axis.Stopatthefirstnewconstraintboundary:2x2=12.Solvefortheintersectionofthenewsetofconstraintboundaries:(0,6).TheEssenceoftheSimplexMethodIteration1:MovetoabetteradjacentCPFsolution,(0,6),byperformingthefollowingthreesteps.602424x1x2(6,0)(4,6)(4,3)(2,6)(0,9)(0,6)(0,0)(4,0)OptimalityTest:Concludethat(0,6)isnotanoptimalsolution.(AnadjacentCPFsolutionisbetter.)TheEssenceoftheSimplexMethodIteration2:MovetoabetteradjacentCPFsolution,(2,6),byperformingthefollowingthreesteps.602424x1x2(6,0)(4,6)(4,3)(2,6)(0,9)(0,6)(0,0)(4,0)Betweenthetwoedgesofthefeasibleregionthatemanatefrom(0,6),choosetomovealongtheedgethatleadstotheright.Stopatthefirstnewconstraintboundaryencounteredwhenmovinginthatdirection:3x1+2x2=12.Solvefortheintersectionofthenewsetofconstraintboundaries:(2,6).TheEssenceoftheSimplexMethodIteration2:MovetoabetteradjacentCPFsolution,(2,6),byperformingthefollowingthreesteps.602424x1x2(6,0)(4,6)(4,3)(2,6)(0,9)(0,6)(0,0)(4,0)OptimalityTest:Concludethat(2,6)isanoptimalsolution,sostop.(NoneoftheadjacentCPFsolutionsarebetter.)TheEssenceoftheSimplexMethodThesimplexmethodfocusessolelyonCPFsolutions.Foranyproblemwithatleastoneoptimalsolution,findingonerequiresonlyfindingabestCPFsolution.Thesimplexmethodisaniterativealgorithm(asystematicsolutionprocedurethatkeepsrepeatingafixedseriesofsteps,calledaniteration,untiladesiredresulthasbeenobtained).TheEssenceoftheSimplexMethodWheneverpossible,theinitializationofthesimplexmethodchoosestheorigin(alldecisionvariablesequaltozero)tobetheinitialCPFsolution.GivenaCPFsolution,itismuchquickercomputationallytogatherinformationaboutitsadjacentCPFsolutionsthanaboutotherCPFsolutions.Therefore,eachtimethesimplexmethodperformsaniterationtomovefromthecurrentCPFsolutiontoabetterone,italwayschoosesaCPFsolutionthatisadjacenttothecurrentone.TheEssenceoftheSimplexMethodWecanidentifytherateoftheimprovementinZthatwouldbeobtainedbymovingalongeachedge.AmongtheedgeswithapositiverateofimprovementinZ,itthenchoosestomovealongtheonewiththelargestrateofimprovementinZ.TheEssenceoftheSimplexMethodApositiverateofimprovementinZimpliesthattheadjacentCPFsolutionisbetterthanthecurrentCPFsolution(sinceweareassumingmaximization),whereasanegativerateofimprovementinZimpliesthattheadjacentCPFsolutionisworse.Therefore,theoptimalitytestconsistssimplyofcheckingwhetheranyoftheedgesgiveapositiverateofimprovementinZ.Ifnonedo,thecurrentCPFsolutionisoptimal.AnExamplemaxz=50x1+100x2s.t.x1+x2≤300 2x1+x2≤400

x2≤250 x1,x2≥0maxz=50x1+100x2s.t.x1+x2+s1=300 2x1+x2+s2=400

x2+s3=250 x1,x2,s1,s2,s3≥0CoefficientMatrixThefeasibleregionisgivenasanumberoflinearequations:

x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250Coefficientmatrixpj

isthejthcolumnvectorofcoefficientmatrixA.TherankofAis3,whichissmallerthan5,thenumberofvariables.ConceptsBasis:letAbeanm×n

coefficientmatrix,whoserankism.IfBisanon-singularm×msub-matrix,thenBisabasisoftheLPmodel.BasicVector:eachcolumninBiscalledabasicvector,andtherearembasicvectorsinB.Non-basicVector:eachcolumnoutsideBisanon-basicvector.BasicVariable:thevariablexicorrespondingtothebasicvectorpiiscalledabasicvariable,andtherearem

basicvariables.Non-basicVariable:thevariablexicorrespondingtothenon-basicvectorpiiscalledanon-basicvariable,andtherearen－m

non-basicvariables.

BasicSolutionBasicSolution:

foragivenbasis,weletthevaluesofthenon-basicvariablesbe0,thenwecansolvethemequationstogetauniquesolution.Inthissolution,thevaluesofbasicvariablesaredeterminedbysolvingtheequations,whilethevaluesofnon-basicvariablesare0.Assumewesettherightsub-matrixtobethebasis

Weletthevaluesofthenon-basicvariablesx１ands2be0,thenwehavethefollowingequations:

x2+s1=300

x2=400

x2+s3=250

ThenwegetasolutiontotheLPproblem:

x1=0，x2=400，s1=－100，s2=0，s3=－150InitialBasicFeasibleSolutionBasicFeasibleSolution(BFS):abasicsolutionthatisafeasiblesolution.FeasibleBasis:thebasiscorrespondingtoaBFS.HowtofindaninitialBFS?Itiseasyifthefollowingconditionshold:Everybjisnon-negative.Thereisanidentitysub-matrixinA,andletitbetheinitialbasis.OptimalityTestTotestwhetheraBFSisoptimal.TestnumberσjRepresentbasicvariablesintermsofnon-basicvariablesRepresentobjectivefunctionintermsofnon-basicvariablesThenthecoefficientofeachvariableintheobjectivefunctionisnowthetestnumberofthevariable.Denoteσiasthetestnumberofvariablexi.Inourexample,ifwetaketheidentitymatrixasthebasis,wehaveσ1=50,σ2=100,σ3=0,σ4=0,σ5=0.OptimalityTestAssumethattheobjectiverepresentedintermsofnon-basicvariablesisasfollows:Ifforsomebasis,wehaveallσj≤0,thenTomaximizethevalueofz,thevalueofshouldbe0.Inaddition,themaximumvalueofzequalsz0.Ontheotherhand,theBFScorrespondingtothecurrentbasisistheoptimalsolution,asthevaluesofthenon-basicvariablesxjareall0,whichmakesthevalueof0.

Foramaximizingproblem,theoptimalityconditionisσj≤0.Foraminimizingproblem,theoptimalityconditionisσj≥0.BasisTransformationActually,ourtaskistofindabasiswhosecorrespondingtestnumbersarenon-positive(formaximizingproblems);ifso,theassociatedBFSistheoptimalsolution.WhenthecurrentBFSisnotoptimal(atleastonetestnumberispositive),weshouldfindanewfeasiblebasissuchthatthecorrespondingBFSimprovesthevalueofobjectivefunction.BasistransformationDeterminethe“enteringvariable”Determinethe“l(fā)eavingvariable”DeterminetheEnteringVariableAccordingtothedefinitionofthetestnumbers,weknowthatσi=0foreverybasicvariable.Ifthereexistsonetestnumberσj＞0,thensettingnon-basicvariablexj

asabasicvariablemayincreaseitsvalueandthusthevalueofobjectivefunction.Letthenon-basicvariablewiththelargestvalueofσj

astheenteringvariableandsetitasabasicvariable.Inourexample,σ2=100isthemaximumtestnumber,thuswesetx2

astheenteringvariable.DeterminetheLeavingVariableTheprincipleofdeterminingtheleavingvariableistomakethenewbasicsolutionfeasible(thatis,aBFS)Inourexample:Wehaveknownthattheenteringvariableisx2,thusforthethreeequationswecanfindthreeupperboundsforx2,whichareDeterminetheLeavingVariableTherefore,themaximumvalueofx2thatensuresthenewbasicsolutionisaBFSis250.Thismakesthevalueofs30.Thuswelets3betheleavingvariable.Now,wehaveanewBFS:x1=0,x2=250,s1=50,s2=150,s3=0.Andthevalueofobjectivefunctionis25000,whichisbetterthan0.DeterminetheLeavingVariableDeterminetheleavingvariable----theminimumratiotestForeachequationwherethecoefficientoftheenteringvariableisstrictlypositive

(>0),wecalculatetheratio

oftheright-handsidetothecoefficientoftheenteringvariable.Thebasicvariableintheequationwiththeminimumratioissetastheleavingvariable.TheSimplexMethodInitializationFindtheinitialbasisandBFSOptimalitytestWhetherthetestnumbersareallnon-positive(formaximizingproblems)IftheBFSisnotoptimal,do“basistransformation”andgetanewBFS,gobacktolaststep;otherwise,thealgorithmisterminated.ComputationofTestNumberσjIneachiterationofbasistransformation,byre-rankingdecisionvariablesandtransforminglinearequations,wecanhavethefollowingmodel,inwhichthefeasiblebasisisanidentitymatrixoforderm:DenotebasicvariablesasDenotenon-basicvariablesasComputationofTestNumberσjFirstwedenoteeachbasicvariableinxitermsofnon-basicvariables:Theobjectivefunctioncanbewrittenas:where

TheSimplexMethodinTabularFormThetabularformofthesimplexmethodrecordsonlytheessentialinformation,namely,thecoefficientsofthevariables,theconstantsontheright-handsidesoftheequations,andthebasicvariableappearingineachequation.Thissaveswritingthesymbolsforthevariablesineachoftheequations,butwhatisevenmoreimportantisthefactthatitpermitshighlightingthenumbersinvolvedinarithmeticcalculationsandrecordingthecomputationscompactly.TheSimplexMethodinTabularFormmaxz=50x1+100x2+0s1+0s2+0s3s.t. x1+x2+s1 =300 2x1+x2 +s2=400

x2 +s3=250 x1,x2,s1,s2,s3≥0TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s3bRatiobi/aij

501000000s1s2s3000