大M法和两阶段法

1、2021/8/61LP当前解已是最优的四大特征：当前解已是最优的四大特征： 存在一组存在一组( (初始初始) )可行基（其系数矩阵为单位阵）。可行基（其系数矩阵为单位阵）。 检验数行的基变量系数检验数行的基变量系数=0。 检验行的非基变量系数检验行的非基变量系数0。全部全部 唯一解。唯一解。存在存在 无穷多个解。无穷多个解。 常数列向量常数列向量0。Q:Q:所给所给LPLP的标准型中约束矩阵中没有现成的可行基怎么办？的标准型中约束矩阵中没有现成的可行基怎么办？002021/8/621.5.2 单纯形的进一步讨论单纯形的进一步讨论2021/8/63例例 解下列线性规划解下列线性规划0122102

2、43423max321321321321321xxxxxxxxxxxxxxxZ、解解: 先化为标准形式先化为标准形式12312341235123max32434210. .2210,1,2,5jZxxxxxxxxxxxstxxxxj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。系数矩阵中不存在单位矩阵，无法建立初始单纯形表。2021/8/64x5可作为一个基变量，第一、三约束中分别加入可作为一个基变量，第一、三约束中分别加入人工人工变量变量x6、x7，得，得12346123512374342102210,1,2,7jxxxxxxxxxxxxxxj 12312341235123max32434

3、210. .2210,1,2,5jZxxxxxxxxxxxstxxxxj2021/8/65说明：说明：不易接受。不易接受。因为因为 是强行引进，称为是强行引进，称为人工变量人工变量。 76,xx它们与它们与 不一样。不一样。 称为松弛变量和剩余变量，是称为松弛变量和剩余变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。价的。54,xx54,xx人工变量的引入一般来说是前后不等价的。只有当最优解人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）中，人工变量都取值零时（此时

4、人工变量实质上就不存在了）才可认为两个问题的最优解是相同的。才可认为两个问题的最优解是相同的。 处理办法：处理办法：把人工变量从把人工变量从基变量基变量中中“赶赶”出去使其变为出去使其变为非基变量非基变量，以求出原问题的初始基本可行解。以求出原问题的初始基本可行解。12346123512374342102210,1,2,7jxxxxxxxxxxxxxxj 2021/8/661. 若新若新LP的最优解中，人工变量的最优解中，人工变量都处在非基变量位置都处在非基变量位置（即取（即取零值）时，原零值）时，原LP有最优解。有最优解。2.若新若新LP的最优解中，包含有的最优解中，包含有非零的人工变量非零

5、的人工变量，则原，则原LP无无可行解。可行解。3.若新若新LP的最优解的的最优解的基变量中，包含有人工变量，但该人工基变量中，包含有人工变量，但该人工变量取值为零变量取值为零。这时可将某个非基变量引入基变量中来。这时可将某个非基变量引入基变量中来替换替换该人工变量，从而得到原该人工变量，从而得到原LP的最优解。的最优解。2021/8/67 以以 X(0)作初始基本可行解进行迭代时，怎样才作初始基本可行解进行迭代时，怎样才能能较快较快地将所有的人工变量地将所有的人工变量从基变量中全部从基变量中全部“赶赶”出去出去（如果能全部（如果能全部“赶赶”出去的话）。这会影响到出去的话）。这会影响到得到最优

6、解的迭代次数。得到最优解的迭代次数。2021/8/68例例1-20 用大用大M法解下列线性规划法解下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、1. 大大M 法法解解: 先化为标准形式先化为标准形式12312341235123max32434210. .2210,1,2,5jZxxxxxxxxxxxstxxxxj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。系数矩阵中不存在单位矩阵，无法建立初始单纯形表。2021/8/69123671234612351237max324342102210,1,2,7jZxxxMxMxxxxxxxxx

7、xxxxxxj 目标函数修改为：目标函数修改为：其中其中M为任意大的实数，为任意大的实数，“-M”称为称为“罚因罚因子子”。2021/8/610Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/3最优解最优解X

8、（31/3，13，19/3，0，0)T；最优值；最优值Z152/32021/8/611例例1-21 求解线性规划求解线性规划 0,426385min21212121xxxxxxxxZ解解: 化为标准型化为标准型4 , 2 , 1, 0426385min42132121jxxxxxxxxxZj加入人工变量加入人工变量x5，得，得5 , 2 , 1, 0426385min5421321521jxxxxxxxxMxxxZj2021/8/6125 , 2 , 1, 0426385min5421321521jxxxxxxxxMxxxZj用单纯形法计算如下表所示。用单纯形法计算如下表所示。 Cj5800M

9、bCBXBx1x2x3x4x50Mx3x5311210010164j5M8+2M0M0 5Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM0 2021/8/613最优解最优解X=（2，0，0，0，2），）， Z=10+2M。大大M法小结：法小结：（1）求极大值时，目标函数变为）求极大值时，目标函数变为11maxnmjjijiZc xMR（2）求极小值时，目标函数变为）求极小值时，目标函数变为11minnmjjijiZc xMR用计算机求解时，不容易确定用计算机求解时，不容易确定M的取值，且的取值，且M过大容易过大容易引起计算误差。引起计算误差。不足：不

10、足：最优解中含有人工变量最优解中含有人工变量x50说明这个解不是最优解，是不说明这个解不是最优解，是不可行的，因此原问题无可行解。可行的，因此原问题无可行解。2021/8/6142. 两阶段法两阶段法miiRw1min约束条件是加入人工变量后的约束方程。约束条件是加入人工变量后的约束方程。用大用大M 法处理人工变量，在计算机求解时，对法处理人工变量，在计算机求解时，对M只能在计算只能在计算机内输入一个机器最大字长的数字。这有时可能使计算结果发机内输入一个机器最大字长的数字。这有时可能使计算结果发生错误。为克服这个困难，可以对添加人工变量的线性规划问生错误。为克服这个困难，可以对添加人工变量的线

11、性规划问题分两阶段来求解题分两阶段来求解称为称为两阶段法两阶段法。将将LPLP的求解过程分成两个阶段：的求解过程分成两个阶段：第一阶段：求解第一阶段：求解第一个第一个LPLP：2021/8/615第一个第一个LP的结果有的结果有三种三种可能情形：可能情形：1. 最优值最优值 ,且人工变量且人工变量皆为非基变量皆为非基变量。 0*w从第一阶段的最优解中从第一阶段的最优解中去掉去掉人工变量后，即为原人工变量后，即为原LP的的一个基本可行解。作为原一个基本可行解。作为原LP的一个初始基本可行解，的一个初始基本可行解，再求原问题，从而进入第二阶段。再求原问题，从而进入第二阶段。2. 最优值最优值 ,说

12、明至少有一个人工变量不为零。说明至少有一个人工变量不为零。 0*w原原LP无可行解。不再需要进入第二个阶段计算。无可行解。不再需要进入第二个阶段计算。 3. 最优值最优值 , 且存在人工变量且存在人工变量为基变量为基变量，但取值为零但取值为零 ， 0*w把某个非基变量与该人工变量进行调换。把某个非基变量与该人工变量进行调换。两阶段法的第一阶段求解的目的：两阶段法的第一阶段求解的目的： 1.判断判断原原LP有无可行解。有无可行解。 2.若有，则可得原若有，则可得原LP的一个的一个初始基本可行解初始基本可行解，再对原，再对原LP进进 行行第二阶段第二阶段的计算。的计算。2021/8/616例例1-

13、22 用两阶段单纯形法求解例用两阶段单纯形法求解例20的线性规划。的线性规划。5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj7 , 2 , 1, 0122102434min732153216432176jxxxxxxxxxxxxxxxxwj用单纯形法求解，得到第一阶段问题的计算表如下：用单纯形法求解，得到第一阶段问题的计算表如下：目标函数为人工变量之和目标函数为人工变量之和加入人工变量的约束条件加入人工变量的约束条件第一第一阶段阶段问题为问题为解解: 标准型为标准型为2021/8/617Cj0000011 bCBXBx1x2

14、x3x4x5x6x7101x6x5x74123121211000101000014101j2121000 100 x6x5x3632532001100010100 381j650100 000 x2x5x36/53/52/51000011/53/52/5010 3/531/511/5j00000 2021/8/618最优解为最优解为 ，最优值，最优值w=0。)5310 ,511,53, 0(X123124145134max32613555333155522115550,1,2,5jZxxxxxxxxxxxxxj原问题目标函数原问题目标函数第二阶段问题为第二阶段问题为说明找到了原问题的一组基本可

15、行解，将它作为初始基可行解，说明找到了原问题的一组基本可行解，将它作为初始基可行解，进行第二阶段的计算。进行第二阶段的计算。2021/8/619Cj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/5 11/5j5 0000 231x2x1x301010000111025/32/31331/319/3j000525/3 用单纯形法计算得到下表用单纯形法计算得到下表最优解最优解X（31/3，13，19/3，0，0)T；最优值；最优值Z152/32021/8/620例例1-23 用两阶段法求解用两阶段法求解5 , 2 , 1

16、, 04263min54213215jxxxxxxxxxwj用单纯形法计算如下表：用单纯形法计算如下表：0,426385min21212121xxxxxxxxZ解解: 第一阶段问题为第一阶段问题为2021/8/621Cj00001bCBXBx1x2x3x4x501x3x5311210010164j 12010 01x1x5101/37/31/31/3010122j 07/31/310 第一阶段的最优解第一阶段的最优解X=(2,0,0,0,2)T, 最优目标值最优目标值w=20,x5仍在基变量中仍在基变量中, 从而原问题无可行解。从而原问题无可行解。2021/8/622 解的判断解的判断唯一最优解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解规划具有唯一最优解 多重最优解的判断多重最优解的判断:最优表中存在非基