运筹学 单纯形法的计算步骤精选课件.ppt

《运筹学 单纯形法的计算步骤精选课件.ppt》由会员分享，可在线阅读，更多相关《运筹学 单纯形法的计算步骤精选课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于运筹学 单纯形法的计算步骤第一页，本课件共有25页41单纯形表单纯形表 用表格法求解LP，规范的表格单纯形表如下：第二页，本课件共有25页计算步骤计算步骤(1).找出初始可行基，确定初始基可行解，建立初始单纯形表。(2).检验各非基变量xj的检验数，若j 0，j=m+1，n；则已得到最优解，可停止计算，否则转入下一步。(3).在j 0，j=m+1，n中，若有某个k对应xk的系数列向量Pk 0，则此问题是无界解，停止计算。否则，转入下一步。(4).根据max(max(j 0)=k，确定xk为换入变量，按 规则计算 =minb=minbi i/a/aikikaaikik00可确定第l行的基变量

2、为换出变量。转入下一步。第三页，本课件共有25页 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3 2 3 0 0 0 2 1 0 1 0 -1/2-9 2 0 0 0 -3/4003x3x4x224-()3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T，z z0 0=0=0第四页，本课件共有25页 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4

3、 8 0 0 -4 1 2 2 3 0 0 0 2 1 0 1 0 -1/2-9 2 0 0 0 -3/4003x3x4x224-3 0 1 0 0 1/4 16 4 0 0 1 0()X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T，z z1 1=9=9第五页，本课件共有25页 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2()2 3 0 0 0 4 1 0 0 1/4 0-14 0 0 -1.5 -1/8 0203x1x5x2 2 0 1 1/2 -1/

4、8 0 4 0 0 -2 1/2 1 X X(2)(2)=(2=(2，3 3，0 0，8 8，0)0)T T，z z2 2=13=13 X X(3)(3)=(4=(4，2 2，0 0，4 4，0)0)T T，z z3 3=14=14第六页，本课件共有25页5 单纯形法的进一步讨论51人工变量法人工变量法 解决初始基可行解的问题。当某个约束方程中没有明 显的基变量时，在该方程中加上人工变量。第七页，本课件共有25页其中第其中第2、3个约束方程中无明显基变量，分别加上人工变个约束方程中无明显基变量，分别加上人工变x6,x7第八页，本课件共有25页这时，初始基和初始基可行解很明显。X(0)=(0，0

5、，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：第九页，本课件共有25页反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例3的单纯形表格为：只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。3.大大M法法在目标函数中加上惩罚项max=3 3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。第十页，本课件共有25页3-6M M-13M-1 0-M 0 0 0 x4 10 3 -2 0

6、 1 0 0 -1 -M x6 1 0 1 0 0 -1 1 -2 1-1 x3 1 -2 0 1 0 0 0 1 1 1-1+M 0 0-M 0 -3M+1 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -1 4-1 x3 1 -2 0 1 0 0 1 0 0 0-1 3 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 0 0 0 -1/3 -1/3X X*=(4=(4，1 1，9 9，0 0，0),z0),z*=2=2第十一页，本课件共有25页2.两阶段法两阶段法第一阶段第一阶段：以人工变量

7、之和最小化为目标函数：以人工变量之和最小化为目标函数 min min =x6+x7 第二阶段第二阶段：以第一阶段的最优解：以第一阶段的最优解(不含人工变量不含人工变量)为初始解，为初始解，以原目标函数为目标函数。以原目标函数为目标函数。第十二页，本课件共有25页第十三页，本课件共有25页第十四页，本课件共有25页第十五页，本课件共有25页5.2 线性规划问题解的讨论线性规划问题解的讨论一、无可行解一、无可行解 max z=2x1+4x2 x1+x2 10 2x1+x2 40 x1,x2 0人工变量不能人工变量不能人工变量不能人工变量不能从基底换出，从基底换出，从基底换出，从基底换出，此时原线性

8、规此时原线性规此时原线性规此时原线性规划无可行解划无可行解划无可行解划无可行解x1x2CBXBbX3 x5x5 0-1 0 0 0 0 -1 x1 x2 x3 x4 x540 2 1 0 -1 110 1 1 1 0 0cj1040/2x1 x5 0-1 20 0 -1 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20第十六页，本课件共有25页第十七页，本课件共有25页例例:max z=3x1+4x2 x1+x2 40 2x1+x2 60 x1-x2 =0 x1,x2 0此题初始解是退化的。此题初始解是退化的。此

9、题初始解是退化的。此题初始解是退化的。最优解也是退化解。最优解也是退化解。最优解也是退化解。最优解也是退化解。退化解迭代中，当换入变量退化解迭代中，当换入变量退化解迭代中，当换入变量退化解迭代中，当换入变量取零值时目标函数值没有改取零值时目标函数值没有改取零值时目标函数值没有改取零值时目标函数值没有改进，进，进，进，x1x2 0 x3 40 1 1 1 0 0 0 x4 60 2 1 0 1 -1 -M x5 0 1 -1 0 0 1 0 x3 40 0 2 1 0 0 x4 60 0 3 0 1 3 x1 0 1 -1 0 0 3+M 4-M 0 0 0 zj-cj 0 0 0 -7/3 z

10、j-cj 0 x3 0 0 0 1 -1/3 4 x2 20 0 1 0 1/3 3 x1 20 1 0 0 1/3 cj 3 4 0 0 -M CB XB b x5 x1 x2 x3 x4 0 7 0 0 zj-cj 0 0 -3.5 0 zj-cj 4 x2 20 0 1 1/2 0 0 x4 0 0 0-3/2 1 3 x1 20 1 0 1/2 0 第十八页，本课件共有25页第十九页，本课件共有25页 例例 max z=3x1+5x2 3x1+5x2 15 2x1+x2 5 2x1+2x2 11 x1,x2 0如果将如果将x x1 1换入基底，得换入基底，得另一解，由可行域凸性另一解，

11、由可行域凸性易知，有两个最优解必易知，有两个最优解必有无穷多组最优解有无穷多组最优解当非基底变量的检验数中当非基底变量的检验数中有取零值，或检验数中零有取零值，或检验数中零的个数大于基变量个数时，的个数大于基变量个数时，有无穷多解有无穷多解。CBXBbx3 x4x4x5x5 000 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 015 3 5 1 0 035 11/5x2 x4x5 5003 3/5 1 1/5 0 02 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1 cj-zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0

12、 0 1Z1=15x1x2第二十页，本课件共有25页四、无（有）界解四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1-x2 2 -3x1+x2 3 x1,x2 0若检验数有大于若检验数有大于0 0，而对应系数列中，而对应系数列中，而对应系数列中，而对应系数列中元素全部小于，等元素全部小于，等元素全部小于，等元素全部小于，等于零（无换出变量）于零（无换出变量）于零（无换出变量）于零（无换出变量）则原问题有无界解。则原问题有无界解。则原问题有无界解。则原问题有无界解。练习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。第二十一页

13、，本课件共有25页 线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还有如的情况外，还有如下几种情况下几种情况 无可行解无可行解无可行解无可行解 退化退化退化退化 无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量第二十二页，本课件共有25页第二十三页，本课件共有25页 对目标函数求标准型线性规划问题，用单纯形法计算步骤的框图如下：第二十四页，本课件共有25页感谢大家观看第二十五页，本课件共有25页