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