运筹学 单纯形法

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“leavingvariable”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

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0The0thIteration(findinitialBFS)TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0Alldecisionvariables(includingslackvariables)TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0CoefficientscorrespondingtothevariablesTheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0CoefficientMatrixoftheconstraintsTheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0Theconstantsontheright-handsidesoftheequationsTheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0Identitymatrix,whichistheinitialfeasiblebasisTheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0Basicvariables,eachappearinginoneequationTheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0CoefficientofeachbasicvariableTheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0zjisthevalueofforcolumnj.WefirstleteachelementincolumnjmultiplyitscorrespondingelementincolumncB,thenaddthemup.TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0Thetestnumberσj,whichiscj-zj.TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0z

isthevalueoftheobjectivefunctionforthecurrentBFS.Wefirstleteachelementincolumnb

multiplythecorrespondingelementincolumncB,andthenaddthemup.TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0Asσ1andσ2

arepositiveandσ1<σ2,theinitialBFSisnotoptimalandx2

istheenteringvariable.TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000000s1s2s3000

111002101001001300400250300/1400/1250/1zjσj=cj-zj

0000050100000z=0FindtheleavingvariableFindthepositivecoefficientsoftheenteringvariables.Findtheconstantsontheright-handsidesoftheequationsthatcorrespondtotheenteringvariables.Divideeachofthesecoefficientsintotherightsideconstantsforthesamerow.PivotElement:theintersectionofthecolumncorrespondingtotheenteringvariableandtherowcorrespondingtotheleavingvariable.TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000001s1s2x200100

1010-12001-1010015015025050/1150/2—zjσj=cj-zj

01000010050000-100z=25000ThefirstiterationThroughrowtransformation,wesetthepivotelementas1andtheothercoefficientsinthecolumncorrespondingtotheenteringvariableas0.Notethattheelementsincolumnbarealsotransformed.Inourexample,afteriteration0,thepivotelementa32

isalready1,thuswekeepthe3rdrowunchanged.Thenweletthe3rdrowmultiply-1andaddittothe1strowandthe2ndrow,respectively,tomakethecoefficientsofx2be0.

TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000001s1s2x200100

1010-12001-1010015015025050/1150/2—zjσj=cj-zj

01000010050000-100z=25000Afteriteration1,thevalueofzisimprovedobviously.Next,wecanfindthattheenteringvariableandtheleavingvariablearex1ands1,respectively.Thepivotelementisa11.TheSimplexMethodinTabularFormIterationBasicVariablescBx1x2

s1

s2

s3bRatiobi/aij

501000002x1s2x2500100

1010-100-211010015050250zjσj=cj-zj

501005005000-500-50z=27500Aftertheseconditeration,wefindthatalltestnumbersarenon-positive,thusthecurrentBFSisoptimal,andthemostfavorablevalueisz=27500.PracticeAnotherProblem

minf=2x1+3x2

s.t.x1+x2≥350

x1≥125 2x1+x2≤600

x1,x2≥0Letz=-f

maxz=–2x1–3x2

s.t.x1+x2–s1=350

x1–s2=125 2x1+x2+s3=600

x1,x2,s1,s2,s3≥0BigMMethodForsomeproblems,itisdifficulttofindaninitialBFS,becauseitisdifficulttofindaninitialfeasiblebasis.Anidentitymatrixofordermisanidealfeasiblebasis.Constructanartificialproblembyaddingartificialvariables maxz=-2x1-3x2-M

a1-M

a2 s.t.x1+x2–s1+a1=350

x1–s2+a2=125 2x1+x2+s3=600

x1,x2,s1,s2,s3,a1,a2≥0BigMMethodDifferencebetweenartificialvariablesandslackvariablesThevaluesofslackvariablescanbeeither0orpositive.Thevaluesofartificialvariablesintheoptimalsolutioncanonlybe0;otherwise,thesolutionisnotafeasibleonefortheoriginalmodel.BigMMethodInordertomakethevaluesofartificialvariablesbe0inthesolutionwefinallyget,weletthecoefficientsoftheartificialvariablesbe－M,whereM

ishugepositivenumber.Thisactuallyassignsanoverwhelmingpenaltytohavingpositiveartificialvariables.Iftheoriginalproblemhasfeasiblesolutions,thesimplexmethodwillfinallysetartificialvariablestobenon-basicvariables;otherwise,theoriginalproblemhasnofeasiblesolutions.BigMMethodIterationBasicvariablescB

x1

x2

s1

s2

s3

a1

a2bRatio

-2-3000-M-M0a1a2s3-M-M0

11-10010100-10012100100350125600350/1125/1600/2zj-2M-M

M

M0-M-M-2+2M-3+M-M-M000-475M1a1x1s3-M-20

01-1101-1100-1001010210-2225125350225-----350/2

zj

-2-M

M-M+20-M

M-20-3+M-M

M-2002-2M-225M-250BigMMethodIterationBasicvariablescB

x1

x2

s1

s2

s3

a1

a2bRatio

-2-3000-M-M2a1x1s2-M-20

01/2-10-1/21011/2001/20001/20110.5300/0.5175/0.5zj

-2-1/2M-1M01/2M-1-M001/2M-2-M0-1/2M+10-M-50M-6003

x2

x1

s2

-3-20

01-20-12010101-1000111-1-1

100250125

zj

-2-3401-4000-40-1-M+4-M

-800TheTwo-PhaseMethodWeaddartificialvariablesanddividetheprocessofsolvinganLPproblemintotwophases.Phase1:tofindaBFSfortherealproblem maxz=-a1

-a2

s.t.x1+x2–s1+a1

=350

x1–s2+a2

=125 2x1+x2+s3=600

x1,x2,s1,s2,s3,