1-3-单纯形法完成课件

3.5人工变量及其处理方法

引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。人工变量法的基本思路是若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。

由于单位矩阵可以作为基阵，因此可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终的单纯形表中还存在非零的人工变量，这表示无可行解。3.5人工变量及其处理方法引用人工变量是用单纯1对于如下线性规划问题对于如下线性规划问题2首先分别对每个约束方程中加入一个人工变量

这样我们就可选……为基变量，令非基变……

=0便可以得到一个初始基可行解

X(0)=(0，0，0…b1，b2…bm)TX(0)=(0，0，0…b1，b2…bm)T33.5.1约束方程为“>=”或“=”的情形（加人工变量）

人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。3.5.1约束方程为“>=”或“=”的情形（加人工变量）4其中第2、3个约束方程中无明显基变量，分别加上人工变x6,x7,其中第2、3个约束方程中无明显基变量，分别加上人工变x6,5这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0的基可行解，从而求得问题的最优解，有两种方法：这时，初始基和初始基可行解很明显。X(0)=(0，0，0，163.5.2大M法（又称惩罚法）

由于人工变量对目标函数有很大的负影响，只要人工变量取值大于0，目标函数值就不可能是最优。单纯形法的寻优机制会自动将人工变量赶到基外，从而可以找到原问题的一个可行基。这种方法我们通常称其为大M法，又称惩罚法。

原理：当目标函数为maxz，对应的人工变量目标系数为—M;当目标函数为minz，对应的人工变量目标系数为+M,其中

M为充分大的正数。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底，再寻求原问题的最优解。3.5.2大M法（又称惩罚法）

由于人工变量对目标7

解先化标准型例3.12用单纯形法求解线性规划问题例3.12用单纯形法求解线性规划问题8然后，再添加人工变量

，将原线性规划问题变为例2.12用单纯形法求解的过程见下表1-3-单纯形法完成课件91-3-单纯形法完成课件103.5.3

两阶段法原理：当目标函数为maxZ，对应的人工变量目标系数为-1;当目标函数为minZ，对应的人工变量目标系数为+1。

第一阶段将原目标系数暂时取零值。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底。

第二阶段再去掉人工变量对应的列，恢复原线性规划问题的目标系数，寻原问题的最优解。3.5.3两阶段法原理：当目标函数为maxZ111-3-单纯形法完成课件121-3-单纯形法完成课件131-3-单纯形法完成课件143.5.4线性规划问题解的讨论一、无可行解

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两阶段法3.5.4线性规划问题解的讨论一、无可行解人工变量不能151-3-单纯形法完成课件16

例:maxz=3x1+4x2

x1+x240

2x1+x260

x1-x2=0

x1,x20

此题初始解是退化的。最优解也是退化解。退化解迭代中，当换入变量取零值时目标函数值没有改进，x1x20x340111000x4602101-1-Mx50[1]-10010x3400[2]100x46003013x101-1003+M4-M000zj-cj

000-7/3

zj-cj

0x30001-1/3

4x2200101/33x1201001/3cj→3400-M

CB

XBbx5

θx1x2x3

x4

0700zj-cj00-3.50zj-cj4x220011/200x4000-3/213x120101/20

例:maxz=3x1+4x2

171-3-单纯形法完成课件18

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

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

x4x5

00035000

x1x2x3x4x5521010153[5]1003511/2x2

x4x5

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

cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2例maxz=3x1+5x2

19四、无（有）界解

maxz=x1+x2

-2x1+x24

x1-x22

-3x1+x23

x1,x20

若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。练习：写出单纯形表,分析检验数与系数关系并画图验证。四、无（有）界解

maxz=x1+x2

20

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

无可行解

退化

无穷多解

无界解人工变量不能从基底中换出基可行解中非零元素个数小于基变量数检验数中零的个数多于基变量的个数检验数大于零，但对应列元素小于等于零，无换出变量线性规划解除有唯一最优解的情况外，还有如下几211-3-单纯形法完成课件22唯一最优解

否

否否

是是是添加松弛变量、人工变量列出初始单纯形表计算非基变量各列的检验数бj所有бj0基变量中有非零的人工变量某非基变量检验数为零无可行解无穷多最优解对任一бj>0有aik≤0无界解令бk=max{бj}xk为换入变量对所有aik>0计算θi=bi/aik令θl=min{θi}第l个基变量为换出变量，alk为主元素

迭代运算.用非基变量xk替换换出变量

.对主元素行(第l行)

令bl/alk→bl;alj/alk→ajl对主元素列(第k列)令1→alk;0→其它元素表中其它行列元素令aij-ali/alk·aik→aij

bi-bl/alk·aik→bi

бj-alj/alk·бk→бj否对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：唯一最优解否否否是是是添加松弛变量、人工变量23练习

下表中给出某线性规划问题计算过程中的一个单纯形表，目标函数为MaxZ=28x4+x5+2x6,约束条件为≤，表中x1,x2,x3为松弛变量，表中解的目标函数值为Z=14（1）求a~g的值；（2）判断给出的解是否为最优解；

x1x2x3x4x5x6x6ax25x403600de-14/32f00115/20100cj-zjbc00-1g练习下表中给出某线性规划问题计算过程中的一个单纯24练习

下表是某求极大值线性规划问题的初始表及迭代后的表，x4,x5为松弛变量，求表中的a~l的值及各下表m~t的值x1x2x3x4x5xm6xn1b-1c3de1001cj-zja1-200xsfxt4gh2i-11½½01cj-zj07jkl练习下表是某求极大值线性规划问题的初始表及迭代后的表25课后作业P451.5（1）（2）大M法（3）（4）两阶段法作业要求上交课后作业P451.5（1）（2）大M法26

3.5人工变量及其处理方法

引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。人工变量法的基本思路是若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。

由于单位矩阵可以作为基阵，因此可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终的单纯形表中还存在非零的人工变量，这表示无可行解。3.5人工变量及其处理方法引用人工变量是用单纯27对于如下线性规划问题对于如下线性规划问题28首先分别对每个约束方程中加入一个人工变量

这样我们就可选……为基变量，令非基变……

=0便可以得到一个初始基可行解

X(0)=(0，0，0…b1，b2…bm)TX(0)=(0，0，0…b1，b2…bm)T293.5.1约束方程为“>=”或“=”的情形（加人工变量）

人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。3.5.1约束方程为“>=”或“=”的情形（加人工变量）30其中第2、3个约束方程中无明显基变量，分别加上人工变x6,x7,其中第2、3个约束方程中无明显基变量，分别加上人工变x6,31这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0的基可行解，从而求得问题的最优解，有两种方法：这时，初始基和初始基可行解很明显。X(0)=(0，0，0，1323.5.2大M法（又称惩罚法）

由于人工变量对目标函数有很大的负影响，只要人工变量取值大于0，目标函数值就不可能是最优。单纯形法的寻优机制会自动将人工变量赶到基外，从而可以找到原问题的一个可行基。这种方法我们通常称其为大M法，又称惩罚法。

原理：当目标函数为maxz，对应的人工变量目标系数为—M;当目标函数为minz，对应的人工变量目标系数为+M,其中

M为充分大的正数。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底，再寻求原问题的最优解。3.5.2大M法（又称惩罚法）

由于人工变量对目标33

解先化标准型例3.12用单纯形法求解线性规划问题例3.12用单纯形法求解线性规划问题34然后，再添加人工变量

，将原线性规划问题变为例2.12用单纯形法求解的过程见下表1-3-单纯形法完成课件351-3-单纯形法完成课件363.5.3

两阶段法原理：当目标函数为maxZ，对应的人工变量目标系数为-1;当目标函数为minZ，对应的人工变量目标系数为+1。

第一阶段将原目标系数暂时取零值。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底。

第二阶段再去掉人工变量对应的列，恢复原线性规划问题的目标系数，寻原问题的最优解。3.5.3两阶段法原理：当目标函数为maxZ371-3-单纯形法完成课件381-3-单纯形法完成课件391-3-单纯形法完成课件403.5.4线性规划问题解的讨论一、无可行解

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两阶段法3.5.4线性规划问题解的讨论一、无可行解人工变量不能411-3-单纯形法完成课件42

例:maxz=3x1+4x2

x1+x240

2x1+x260

x1-x2=0

x1,x20

此题初始解是退化的。最优解也是退化解。退化解迭代中，当换入变量取零值时目标函数值没有改进，x1x20x340111000x4602101-1-Mx50[1]-10010x3400[2]100x46003013x101-1003+M4-M000zj-cj

000-7/3

zj-cj

0x30001-1/3

4x2200101/33x1201001/3cj→3400-M

CB

XBbx5

θx1x2x3

x4

0700zj-cj00-3.50zj-cj4x220011/200x4000-3/213x120101/20

例:maxz=3x1+4x2

431-3-单纯形法完成课件44

例maxz=3x1+5x2

3x1+5x215

2x1+x25

2x1+2x211

x1,x20

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

x4x5

00035000

x1x2x3x4x5521010153[5]1003511/2x2

x4x5

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

cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2例maxz=3x1+5x2

45四、无（有）界解

maxz=x1+x2

-2x1+x24

x1-x22

-3x1+x23

x1,x20

若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。练习：写出单纯形表,分析检验数与系数关系并画图验证。四、无（有）界解

maxz=x1+x2

46

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

无可行解

退化

无穷多解

无界解人工变量不能从基底中换出基可行解中非零元素个数小于基变量数检验数中零的个数多于基变量的个数检验数大于零，但对应列元素小于等于零，无换出变量线性规划解除有唯一最优解的情况外，还有如下几471-3-单纯形法完成课件48唯一最优