大M法和两阶段法.ppt

《大M法和两阶段法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LP当前解已是最优的四大特征：⑴存在一组(初始)可行基（其系数矩阵为单位阵）。⑵检验数行的基变量系数=0。⑶检验行的非基变量系数≤0。全部唯一解。存在无穷多个解。⑷常数列向量≥0。Q:所给LP的标准型中约束矩阵中没有现成的可行基怎么办？1.5.2单纯形的进一步讨论例解下列线性规划解:先化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，得说明：①不易接受。因为是强行引进，称为人工变量。它们与不一样。称为松弛变量和剩余变量，是为了将不等式改写为等式而引进的，而

2、改写前后两个约束是等价的。②人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为两个问题的最优解是相同的。处理办法：把人工变量从基变量中“赶”出去使其变为非基变量，以求出原问题的初始基本可行解。结论1.若新LP的最优解中，人工变量都处在非基变量位置（即取零值）时，原LP有最优解。2.若新LP的最优解中，包含有非零的人工变量，则原LP无可行解。3.若新LP的最优解的基变量中，包含有人工变量，但该人工变量取值为零。这时可将某个非基变量引入基变量中来替换该人工变量，从而得到原

3、LP的最优解。以X(0)作初始基本可行解进行迭代时，怎样才能较快地将所有的人工变量从基变量中全部“赶”出去（如果能全部“赶”出去的话）。这会影响到得到最优解的迭代次数。－－大M法与两阶段法例1-20用大M法解下列线性规划1.大M法解:先化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。目标函数修改为：其中M为任意大的实数，“-M”称为“罚因子”。Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2

4、M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3最优解X＝（31/3，13，19/3，0，0)T；最优值Z＝152/3例1-21求解线性规划解:化为标准型加入人工变量x5，得用单纯形法计算如下表所示。Cj5－800MbCBXBx1x2

5、x3x4x50Mx3x5[3]11－2100－1016→4λj5－M↑－8+2M0M05Mx1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0最优解X=（2，0，0，0，2），Z=10+2M。大M法小结：（1）求极大值时，目标函数变为（2）求极小值时，目标函数变为用计算机求解时，不容易确定M的取值，且M过大容易引起计算误差。不足：最优解中含有人工变量x5≠0说明这个解不是最优解，是不可行的，因此原问题无可行解。2.两阶段法约束条件是加入人工变量后的约束方程。用大M法处理人工变量，

6、在计算机求解时，对M只能在计算机内输入一个机器最大字长的数字。这有时可能使计算结果发生错误。为克服这个困难，可以对添加人工变量的线性规划问题分两阶段来求解——称为两阶段法。将LP的求解过程分成两个阶段：第一阶段：求解第一个LP：第一个LP的结果有三种可能情形：1.最优值,且人工变量皆为非基变量。从第一阶段的最优解中去掉人工变量后，即为原LP的一个基本可行解。作为原LP的一个初始基本可行解，再求原问题，从而进入第二阶段。2.最优值,说明至少有一个人工变量不为零。原LP无可行解。不再需要进入第二个阶段计算。3.最优值,且存在人工变量

7、为基变量，但取值为零，把某个非基变量与该人工变量进行调换。两阶段法的第一阶段求解的目的：1.判断原LP有无可行解。2.若有，则可得原LP的一个初始基本可行解，再对原LP进行第二阶段的计算。例1-22用两阶段单纯形法求解例20的线性规划。用单纯形法求解，得到第一阶段问题的计算表如下：目标函数为人工变量之和加入人工变量的约束条件第一阶段问题为解:标准型为Cj0000011bCBXBx1x2x3x4x5x6x7101x6x5x7－4123－1－212[1]－1000101000014101→λj2－1－2↑1000100x6x5x3－

8、6－32[5]3－2001－1000101003→81λj6－5↑0100000x2x5x3－6/53/5－2/5100001－1/53/5－2/50103/531/511/5λj00000最优解为，最优值w=0。原问题目标函数第二阶段问题为说明找到了原问题的一