《运筹学 单纯形法的计算步骤课件.ppt》由会员分享，可在线阅读，更多相关《运筹学 单纯形法的计算步骤课件.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于运筹学 单纯形法的计算步骤现在学习的是第1页，共25页41单纯形表单纯形表 用表格法求解LP，规范的表格单纯形表如下：现在学习的是第2页，共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、的基变量为换出变量。转入下一步。现在学习的是第3页，共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现在学习的是第4页，共25页 2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1
3、 0 0 1/4 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现在学习的是第5页，共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
4、 1 1/2 -1/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现在学习的是第6页，共25页5 单纯形法的进一步讨论51 人工变量法人工变量法 解决初始基可行解的问题。当某个约束方程中没有明 显的基变量时，在该方程中加上人工变量。现在学习的是第7页，共25页其中第其中第2、3个约束方程中无明显基变量，分别加上人工变个约束方程中无明显基变量，分别加上人工变x6,x7现在学习的是第8页，共25页这时，初始基和初始
5、基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：现在学习的是第9页，共25页反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例3的单纯形表格为：只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。3.大大M法法在目标函数中加上惩罚项max=3 3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。现在学习的是第10页，共25页3-6M M-13M-1
6、0-M 0 0 0 x4 10 3 -2 0 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现在学习的是第11页，共25页
7、2.两阶段法两阶段法第一阶段第一阶段：以人工变量之和最小化为目标函数：以人工变量之和最小化为目标函数 min min =x6+x7 第二阶段第二阶段：以第一阶段的最优解：以第一阶段的最优解(不含人工变量不含人工变量)为初始解，为初始解，以原目标函数为目标函数。以原目标函数为目标函数。现在学习的是第12页，共25页现在学习的是第13页，共25页现在学习的是第14页，共25页现在学习的是第15页，共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现在学习的是第16页，共25页现在学习的是第17页，共25页例例:max z=3x1+4x2 x1+x2 40 2x1+x2 60 x
9、1-x2 =0 x1,x2 0此题初始解是退化的。最优此题初始解是退化的。最优此题初始解是退化的。最优此题初始解是退化的。最优解也是退化解。解也是退化解。解也是退化解。解也是退化解。退化解迭代中，当换入变退化解迭代中，当换入变退化解迭代中，当换入变退化解迭代中，当换入变量取零值时目标函数值没量取零值时目标函数值没量取零值时目标函数值没量取零值时目标函数值没有改进，有改进，有改进，有改进，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
10、0 0 3+M 4-M 0 0 0 zj-cj 0 0 0 -7/3 zj-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 现在学习的是第18页，共25页现在学习的是第19页，共25页 例例 max z=3x1+5x2 3x1+5x2 15 2x1+x2 5 2x1+2x2 11 x1,x2
11、 0如果将如果将x x1 1换入基底，得另换入基底，得另一解，由可行域凸性易一解，由可行域凸性易知，有两个最优解必有知，有两个最优解必有无穷多组最优解无穷多组最优解当非基底变量的检验数中当非基底变量的检验数中有取零值，或检验数中零有取零值，或检验数中零的个数大于基变量个数时，的个数大于基变量个数时，有无穷多解有无穷多解。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-
12、zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x2现在学习的是第20页，共25页四、无（有）界解四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1-x2 2 -3x1+x2 3 x1,x2 0若检验数有大于若检验数有大于若检验数有大于若检验数有大于0 0，而对应系数列中，而对应系数列中，而对应系数列中，而对应系数列中元素全部小于，等元素全部小于，等元素全部小于，等元素全部小于，等于零（无换出变量）于零（无换出变量）于零（无换出变量）于零（无换出变量）则原问题有无界解。则原问题有无界解。则原问题有无界解。则原问题有无界解。练
13、习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。现在学习的是第21页，共25页 线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还有如下的情况外，还有如下几种情况几种情况 无可行解无可行解无可行解无可行解 退化退化退化退化 无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量现在学习的是第22页，共25页现在学习的是第23页，共25页 对目标函数求标准型线性规划问题，用单纯形法计算步骤的框图如下：现在学习的是第24页，共25页感感谢谢大大家家观观看看现在学习的是第25页，共25页