单纯形法人工变量法

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

只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。大M法在目标函数中加上惩罚项。

max=3x1-x2-x3-Mx6-Mx7其中M为充分大的正数。第四页，共二十页，2022年，8月28日3-6M M-1 3M-1 0

-M 0 0

0x4

103-20100-1-Mx610[1]00-11-21-1x31-2010001

1 -1+M 0 0

-M 0-3M+1

0x4

12[3]001-2-1x210100-14-1x31-20100

1 0 0 0

-1

3x1

41001/3-2/3-1x210100-1-1x390012/3-4/3

-2000

-1/3-1/3

X*=(4，1，9，0，0)T,z*=2113/21〔〕第五页，共二十页，2022年，8月28日两阶段法第一阶段：以人工变量之和最小化为目标函数。 min=x6+x7

第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。第六页，共二十页，2022年，8月28日第七页，共二十页，2022年，8月28日第八页，共二十页，2022年，8月28日第九页，共二十页，2022年，8月28日约束方程为“>=”或“=”的情形（加人工变量）人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。第十页，共二十页，2022年，8月28日MaxZ=2x1+x2+x3s.t.4x1+2x2+2x3≥42x1+4x2≤204x1+8x2+2x3≤16x1，x2，x3≥0用两阶段法求下面线性规划问题的解第十一页，共二十页，2022年，8月28日线性规划问题解的讨论一、无可行解

maxz=2x1+4x2

x1+x210

2x1+x2

40

x1,x20人工变量不能从基底换出，此时原线性规划问题无可行解。x1x2CBXBbX3

x5

0-1

0000-1

x1x2x3x4x540210-1110[1]1100cj1040/2x1

x5

0-1

200-1-2-111011100

cj-zj0-1-2-10cj-zj210-10Z0=-40Z1=-20两阶段法第十二页，共二十页，2022年，8月28日第十三页，共二十页，2022年，8月28日

例:maxz=3x1+4x2

x1+x240

2x1+x260

x1-x2=0

x1,x20

此题初始解是退化的。最优解也是退化解。退化解迭代中，当换入变量取零值时目标函数值没有改进，x1x2

0x3

4011100

0

x4602101-1

-M

x5

0[1]-1001

0x3400[2]10

0x4

600301

3x1

01-100

3+M4-M000

zj-

cj

000-7/3

zj-

cj

0x3

0001-1/3

4x2

200101/3

3x1

201001/3

cj→

3400-M

CB

XB

bx5

θx1x2x3

x4

0700

zj-

cj

00-3.50

zj-

cj

4x2

20011/20

0x4

000-3/21

3x1

20101/20第十四页，共二十页，2022年，8月28日第十五页，共二十页，2022年，8月28日

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。CBXBbx3

x4x5

000

35000

x1x2x3x4x5

521010153[5]1003511/2x2

x4x5

50033/511/50027/50-1/51054/50-2/501

cj-zj

00-100cj-zj35000Z0=01122001Z1=15x1x2第十六页，共二十页，2022年，8月28日四、无（有）界解

maxz=x1+x2

-2x1+x24

x1-x22

-3x1+x23

x1,x20

若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。练习：写出单纯形表,分析检验数与系数关系并画图验证。第十七页，共二十页，2022年，8月28日

线性规划解除有唯一最优解的情况外，还有如下几种情况

无可行解

退化

无穷多解

无界解人工变量不能从基底中换出基可行解中非零元素个数小于基变量数检验数中零