Chapter3.10-The big M method(001).pdf

《Chapter3.10-The big M method(001).pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ThebigMmethodLIXiao-leiThebigMmethod•Thesimplexalgorithmrequiresastartingbfs.Wefoundastartingbfsbyusingtheslackvariablesasourbasicvariables.•IfanLPhasany≥orequalityconstraints,astartingbfsmaynotbereadilyapparent.•ThebigMmethod(orthetwo-phasesimplexmethod)maybeused.Example4•Bevcomanufacturesano

2、range-flavoredsoftdrinkcalledOranjbycombiningorangesodaandorangejuice.Eachounceoforangesodacontains0.5ozofsugarand1mgofvitaminC.eachounceoforangejuicecontains0.25ozofsugarand3mgofvitaminC.ItcostsBevco2¢toproduceanounceoforangesodaand3¢toproduceanounceoforangejuice.Example4•Bevco'smarketingdepa

3、rtmenthasdecidedthateach10-ozbottleofOranjmustcontainatleast20mgofvitaminCandatmost4ozofsugar.UseLPtodeterminehowBevcocanmeetthemarketingdepartment'srequirementsatminimumcost.Example4•SolutionLetx=numberofouncesoforangesodainabottleofOranj1x=numberofouncesoforangejuiceinabottleofOranj2Thenthea

4、ppropriateLPisminz=2x+3x12s.t.1/2x+1/4x≤4(sugarconstraint)12x+3x≥20(vitaminCconstraint)(17)12x+x=10(10ozinbottleofOranj)12x,x≥012Example4•Put(17)intostandardformz-2x-3x=0121/2x+1/4x+s=4121x+3x-e=20122x+x=1012AllvariablesnonnegativeExample4•SearchforabfsInrow1,s=4couldbeusedasabasicvariable1Inr

5、ow2,e=-20violatesthesignrestriction.2Inrow3,thereisnoreadilyapparentbasicvariable.•ArtificialvariablesToremedythisproblem,wesimply"invent"abasicfeasiblevariableforeachconstraintthatneedsone.Thesevariablesarecreatedbyusandarenotrealvariables,wecallthemartificialvariables.Ifanartificialvariablei

6、saddedtorowi,welabelita.iExample4•Inthecurrentproblem,weneedtoaddanartificialvariableatorow2andanartificialvariableatorow3.23z-2x-3x=0121/2x+1/4x+s=4121x+3x-e+a=20(18)1222x+x+a=10123Wenowhaveabfs:z=0,s=4,a=20,a=10123•Thereisnoguaranteethattheoptimalsolutionto(18)willbethesameastheoptimalsoluti

7、onto(17).•Inaminproblem,wecanensurethatalltheartificialvariableswillbezerobyaddingatermMatotheiobjectivefunctionforeachartificialvariableai.(inamaxproblem,addaterm–Matotheobjectivefunction.)iHereMrepresentsa"verylarge"positivenumber.Exa