Chapter3.9-Degeneracy and the Convergence of the Simplex Algorithm

《Chapter3.9-Degeneracy and the Convergence of the Simplex Algorithm》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DegeneracyandtheConvergenceoftheSimplexAlgorithmLIXiao-leiPreview•Therelationship(foramaxproblem)betweenthez-valuesforthecurrentbfsandthenewbfs:z-valuefornewbfs=z-valueofcurrentbfs–(valueofenteringvariableinnewbfs)(coefficientofenteringvariableinrow0ofcurrentbfs)(15)Pr

2、eview•(coefficientofenteringvariableinrow0)<0and(valueofenteringvariableinnewbfs)≥0•Wecandeducethefollowingfacts:if(valueofenteringvariableinnewbfs)>0,then(z-valuefornewbfs)>(z-valueforcurrentbfs)If(valueofenteringvariableinnewbfs)=0,then(z-valuefornewbfs)=(z-valueforc

3、urrentbfs)Preview•IneachoftheLP’sbasicfeasiblesolutions,allthebasicvariablesarepositive(>0).AnLPwiththispropertyisanondegenerateLP.•WhenthesimplexisusedtosolveanondegenerateLP,itisimpossibletoencounterthesamebfstwice.Weareguaranteedtofindtheoptimalsolutioninafinitenumb

4、erofiterations.PreviewThesimplexmayfailforadegenerateLP.•DEFINITIONAnLPisdegenerateifithasatleastonebfsinwhichabasicvariableisequaltozero.Example•ThefollowingLPisdegenerate:maxz=5x+2x12s.t.x+x≤612x1-x2≤0(16)x,x≥012Addingslackvariablessandstothetwo12constraints.Example•

5、AdegenerateLPBasiczxxssrhsvariableratio12121-5-2000Z=0011106S=6610①-1010S=00*2Thebasicvariables2=0,thus,(16)isadegenerateLP.Note:anybfsthathasatleastonebasicvariableequaltozero(orequivalently,atleastoneconstraintwithazeroright-handside)isadegeneratebfs.Example•Since-5<

6、-2,weenterx1intothebasis.Thewinningratiois0inrow2.Basiczxxssrhsvariableratio121210-7050Z=000②1-16S=66/2=3*101-1010x=0none1Ournewbfshasthesamez-valueastheoldbfs.Inthenewbfs,allvariableshaveexactlythesamevaluesastheyhadbeforethepivot!Thus,ournewbfsisalsodegenerate.Exampl

7、e•Continuingwiththesimplex,weenterx2inrow1.Basiczxxssrhsvariable12121003.51.521Z=210010.5-0.53x=320100.50.53x=31Thisisanoptimaltableau,sotheoptimalsolutionto(16)isz=21,x=3,x=3,s=s=0.2112•InsolvingadegenerateLP,itispossibleforapivottoleavethevalueofzunchanged.•Asequence

8、ofpivotslikethefollowingmayoccur:initialbfs(bfs1):z=20afterfirstpivot(bfs2):z=20aftersecondpivot(bfs3):z=20afterthird