单纯形法人工变量法

1、单纯形法人工变量法第1页，共20页，2022年，5月20日，3点17分，星期二其中第2、3个约束方程中无明显基变量，分别加上人工变量x6, x7,约束方程为“=”或“=”的情形（加人工变量）第2页，共20页，2022年，5月20日，3点17分，星期二这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：第3页，共20页，2022年，5月20日，3点17分，星期二 反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。

2、例的单纯形表格为： 只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。大M法在目标函数中加上惩罚项。max =3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。第4页，共20页，2022年，5月20日，3点17分，星期二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+M 0 0-M 0 -3M+1 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -

3、1 4 -1 x3 1 -2 0 1 0 0 1 0 0 0 -13 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 -2 0 0 0 -1/3 -1/3X* = (4，1，9，0，0)T, z* = 2113/2 1 第5页，共20页，2022年，5月20日，3点17分，星期二两阶段法第一阶段：以人工变量之和最小化为目标函数。 min = x6+x7 第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。第6页，共20页，2022年，5月20日，3点17分，星期二第7页，共20页，2022年，

4、5月20日，3点17分，星期二第8页，共20页，2022年，5月20日，3点17分，星期二第9页，共20页，2022年，5月20日，3点17分，星期二 约束方程为“=”或“=”的情形（加人工变量） 人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。第10页，共20页，2022年，5月20日，3点17分，星期二Max Z=2x1+ x 2+ x 3 s.t. 4x1+2x2+

5、2x 34 2x1+4x2 20 4x1+8x2+ 2x 316 x1，x2，x 30 用两阶段法求下面线性规划问题的解第11页，共20页，2022年，5月20日，3点17分，星期二线性规划问题解的讨论一、无可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0人工变量不能从基底换出，此时原线性规划问题无可行解。x1x2CBXBbX3 x5 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 -

6、1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20两阶段法第12页，共20页，2022年，5月20日，3点17分，星期二第13页，共20页，2022年，5月20日，3点17分，星期二例: max z=3x1+4x2 x1 +x2 40 2x1+x260 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

7、 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 第14页，共20页，2022年，5月20日，3点17分，星期二第15页，共20页，2022年，5月20日，3点17分，星期二 例 max z=3x

8、1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。CBXBbx3 x4x5 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

9、 0 0 1Z1=15x1x2第16页，共20页，2022年，5月20日，3点17分，星期二四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。练习：写出单纯形表,分析检验数 与系数关系并画图验证。第17页，共20页，2022年，5月20日，3点17分，星期二 线性规划解除有唯一最优解的情况外，还有如下几种情况 无可行解 退化 无穷多解 无界解人工变量不能从基底中换出基可行解中非零元素个数小于基变量数检验数中零的个数多于基变量的个数检验数大于零，但对应列元素小于等于零，无换出变量第18页，共20页，2022年，5月20日，3点17分，星期二第19页，共20页，2022年，5月20日，3点17分，星期二唯一最优解 否 否否 是是是添加松弛变量、人工变量 列出初始单纯形表计算非基变量各列的检验数j所有j0基变量中有非零的人工变量某非基变量检验数为零无可行解无穷多最优解对任一j0有aik0无界解令k=maxjxk为换入变量对所有aik0计算i=bi/aik令l=mini第l个基变量为换出变量，alk为主元素 迭代运算.用非基变量xk替换换出变量 .对主元素行(第l行) 令 bl/a