运筹学01112单纯形法的进一步讨 论(2).ppt

文档介绍：2016-9-101运筹学Operations Research§ 单纯形法的进一步讨论(2)2016-9-102运筹学Operations Research???????????????????0)(1bBxxxBLPNB的基本可行解关于基回顾:非退化的基本可行解退化的基本可行解非退化的线性规划问题退化的线性规划问题2016-9-103Th1 对非退化的线性规划问题施行单纯形法,必可经过有限次迭代(转轴)得到其最优解或判明其无最优解. ▌Th2 对退化的线性规划问题施行单纯形法, Research证明:.}0{min,1,010为枢轴元转轴以,令不妨设rkjnjmkrbrrmrb????????2016-9-104运筹学Operations Research2016-9-105运筹学Operations Research转轴前后,基本可行解和相应的目标函数值都没有改????,单纯形法的施行有可能??一????可行基??,经过??次转轴,??回到?基的?????(c?c?in?),???得?到最优解或判明无最优解.▌2016-9-106运筹学Operations Research一???的??.1955?,?. ?. ?ea?e?????????????????????????????7,,1,010321122109841..6212043max6376542765417654?jxxxxxxxxxxxxxtsxxxxzj2016-9-10?运筹学Operations Research3321),,(IPPPB??解:取初始可行基2016-9-10?运筹学Operations Research2016-9-109运筹学Operations Research2016-9-1010运筹学Operations Research??,转轴过??回到?一?单纯形?,???????.???????轴?的??规???转轴,?转轴?一?进行?????终止.??,??得到最优解.▌