Chapter3.11-The Two-Phase Simplex Method(001).pdf

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

1、TheTwo-PhaseSimplexMethodLIXiao-leiPreviewWhenabasicfeasiblesolutionisnotreadilyavailable,thetwo-phasesimplexmethodmaybeusedasanalternativetothebigMmethod.Inthetwo-phasesimplexmethod,weaddartificialvariablestothesameconstraintsaswedidinbigMmethod.Thenwefindabfstotheorig

2、inalLPbysolvingthePhaseILP.InthePhaseILP,theobjectivefunctionistominimizethesumofallartificialvariables.AtthecompletionofPhaseI,wereintroducetheoriginalLP’sobjectivefunctionanddeterminetheoptimalsolutiontotheoriginalLP.Thetwo-phasesimplexmethodStep1Modifytheconstraints

3、sothattheright-handsideofeachconstraintisnonnegative.Thisrequiresthateachconstraintwithanegativeright-handsidebemultipliedthroughby-1.Step1’Identifyeachconstraintthatisnowan=or≥constraint.Instep3,wewilladdantheartificialvariabletoeachoftheseconstraints.Step2Converteachi

4、nequalityconstrainttostandardform.For≤constrainti,weaddaslackvariables;iFor≥constrainti,weaddanexcessvariablee;iThetwo-phasesimplexmethodStep4Fornow,ignoretheoriginalLP’sobjectivefunction.InsteadsolveanLPwhoseobjectivefunctionisminw’=(sumofalltheartificialvariables).This

5、iscalledthePhaseILP.TheactofsolvingthephaseILPwillforcetheartificialvariablestobezero.Thetwo-phasesimplexmethodSinceeacha≥0,solvingthePhaseILPwillresultinoneofithefollowingthreecases:Case1Theoptimalvalueofw’isgreaterthanzero.Inthiscase,theoriginalLPhasnofeasiblesolution.

6、Case2Theoptimalvalueofw’isequaltozero,andnoartificialvariablesareintheoptimalPhaseIbasis.Inthiscase,wedropallcolumnsintheoptimalPhaseItableauthatcorrespondtotheartificialvariables.WenowcombinetheoriginalobjectivefunctionwiththeconstraintsfromtheoptimalPhaseItableau.Thisy

7、ieldsthePhaseIILP.TheoptimalsolutiontothePhaseIILPistheoptimalsolutiontotheoriginalLP.Thetwo-phasesimplexmethodCase3Theoptimalvalueofw’isequaltozeroandatleastoneartificialvariableisintheoptimalPhaseIbasis.Inthiscase,wecanfindtheoptimalsolutiontotheoriginalLPifattheendofP

8、haseIwedropfromtheoptimalPhaseItableauallnonbasicartificialvariablesandanyvariablefromtheorigina