运筹学-单纯形法的计算步骤.pptx

本节重点：本节重点：单纯形表（特别是检验数行）单纯形表（特别是检验数行）单纯形法的计算步骤单纯形法的计算步骤大大M法法两阶段法两阶段法解的存在情况判别解的存在情况判别41 单纯形表单纯形表 用表格法求解LP，规范的表格单纯形表如下：计算步骤计算步骤(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 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 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 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 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/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=145 单纯形法的进一步讨论51 人工变量法人工变量法 解决初始基可行解的问题。当某个约束方程中没有明 显的基变量时，在该方程中加上人工变量。其中第其中第2、3个约束方程中无明显基变量，分别加上人工变个约束方程中无明显基变量，分别加上人工变x6,x7这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例3的单纯形表格为：只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。3.大大M法法在目标函数中加上惩罚项max=3 3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。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 -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=22.两阶段法两阶段法第一阶段第一阶段：以人工变量之和最小化为目标函数：以人工变量之和最小化为目标函数 min min =x6+x7 第二阶段第二阶段：以第一阶段的最优解：以第一阶段的最优解(不含人工变量不含人工变量)为初为初始解，以原目标函数为目标函数。始解，以原目标函数为目标函数。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 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20例例:max z=3x1+4x2 x1+x2 40 2x1+x2 60 x1-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 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 例例 max z=3x1+5x2 3x1+5x2 15 2x1+x2 5 2x1+2x2 11 x1,x2 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-zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x2四、无（有）界解四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1-x2 2 -3x1+x2 3 x1,x2 0若检验数有大于若检验数有大于若检验数有大于若检验数有大于0 0，而对应系数列，而对应系数列，而对应系数列，而对应系数列中元素全部小于，中元素全部小于，中元素全部小于，中元素全部小于，等于零（无换出等于零（无换出等于零（无换出等于零（无换出变量）则原问题变量）则原问题变量）则原问题变量）则原问题有无界解。有无界解。有无界解。有无界解。练习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。线性规划解除有线性规划解除有唯一最优解唯一最优解的情况外，还有的情况外，还有如下几种情况如下几种情况 无可行解无可行解无可行解无可行解 退化退化退化退化 无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量 对目标函数求标准型线性规划问题，用单纯形法计算步骤的框图如下：唯一最优解唯一最优解 否 否否 是是是添添加加松松弛弛变变量量、人人工工变变量量 列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量各列的检验数各列的检验数j所有所有j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基变某非基变量检验数量检验数为零为零无可行解无可行解无穷多最优解无穷多最优解对任一对任一j0有有aik0无界解无界解令令k=maxjx xk k为换入变量为换入变量对对 所所 有有 aik 0计计 算算i i=bi/aik令令l l=min=mini i 第第l l个个基基变变量量为为换换出出变变量，量，alk为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk替换换出变量替换换出变量 .对主元素行对主元素行(第第l行行)令令 bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1aalklk;0;0其它元其它元素表中其它行列元素素表中其它行列元素令令 aij-ali/alkaikaaijij b bi i-b-bl l/a/alklka aikikbbi i j-alj/alk k j否