《最新单纯形法人工变量法ppt课件》由会员分享，可在线阅读，更多相关《最新单纯形法人工变量法ppt课件（21页珍藏版）》请在金锄头文库上搜索。
1、单纯形法单纯形法- -人工变量法人工变量法其中第其中第2、3个约束方程中无明显基变量，分别加上人工变量个约束方程中无明显基变量，分别加上人工变量x6, x7,约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量） 约束方程为约束方程为“=”或或“=”的情形的情形（加人工变量） 人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，xn+m人人工工变变量量是是虚虚拟拟变变量量，加加入入原原方方程程中中是是作作为为临临时时基基变变量量，经经过过基基的的旋旋转转变变换换，将将人人工工变变量量均均能能换换成成非非基基变变量量，所所得得解解是是最最优优解解；若若在在最最终终表
2、表中中检检验验数数小小于于零零，而而且且基基变变量量中中还有某个非零的人工变量，原问题无可行解。还有某个非零的人工变量，原问题无可行解。Max Z=2x1+ x 2+ x 3 s.t. 4x1+2x2+ 2x 34 2x1+4x2 20 4x1+8x2+ 2x 316 x1，x2，x 30 用两阶段法求下面线性规划问题的解用两阶段法求下面线性规划问题的解线性规划问题解的讨论线性规划问题解的讨论一、无可行解一、无可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0人工变量不能从基底人工变量不能从基底人工变量不能从基底人工变量不能从基底换出，此时原线性规换
3、出，此时原线性规换出，此时原线性规换出，此时原线性规划问题无可行解。划问题无可行解。划问题无可行解。划问题无可行解。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此题初始解是退化的。此题初始解是退
4、化的。此题初始解是退化的。此题初始解是退化的。最优解也是退化解。最优解也是退化解。最优解也是退化解。最优解也是退化解。退化解迭代中，当换入退化解迭代中，当换入退化解迭代中，当换入退化解迭代中，当换入变量取零值时目标函数变量取零值时目标函数变量取零值时目标函数变量取零值时目标函数值没有改进，值没有改进，值没有改进，值没有改进，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 -
5、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换入基底，得换入基底，得另一解，由可行域凸性另一解，由可行域凸性易知，有两个最优
6、解必易知，有两个最优解必有无穷多组最优解有无穷多组最优解当非基底变量的检验数当非基底变量的检验数中有取零值，或检验数中有取零值，或检验数中零的个数大于基变量中零的个数大于基变量个数时，有无穷多解个数时，有无穷多解。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/2x2 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四
7、、无（有）界解四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x2 3 x1 ,x2 0若检验数有大于若检验数有大于若检验数有大于若检验数有大于0 0，而对应系数列，而对应系数列，而对应系数列，而对应系数列中元素全部小于中元素全部小于中元素全部小于中元素全部小于或等于零（无换或等于零（无换或等于零（无换或等于零（无换出变量）则原问出变量）则原问出变量）则原问出变量）则原问题有无界解。题有无界解。题有无界解。题有无界解。练习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。 线性规划解除有线性规划解除有唯
8、一最优解唯一最优解的情况外，还有的情况外，还有如下几种情况如下几种情况 无可行解无可行解无可行解无可行解 退化退化退化退化 无穷多解无穷多解无穷多解无穷多解 无界解无界解无界解无界解人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量唯一最优解唯一最优解 否 否否 是是是添添加加松松弛弛变变量量、人人工工变变量量 列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量各列
9、的检验数各列的检验数j所有所有j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基某非基变量检变量检验数为验数为零零无可行解无可行解无穷多最优解无穷多最优解对任一对任一j0有有aik0无界解无界解令令k=maxjx xk k为换入变量为换入变量对对 所所 有有 aik 0计计 算算i i=bi/aik令令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/alklkaaikikbbi i j- alj/alk k j否对目标函数求极大值标准型线性规划对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：问题，单纯形法计算步骤的框图：
