《03.2运筹学大M法》由会员分享，可在线阅读，更多相关《03.2运筹学大M法（16页珍藏版）》请在金锄头文库上搜索。
1、第二节第二节 大大M法法 如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量，人工地构成一个单位向量组。人工变量只起过渡作用，不应影响决策变量的取值。 两种方法可控制人工变量取值。大M法两阶段法2021/3/101例2021/3/102解：引入松弛变量x4、剩余变量x5，将数学模型标准化2021/3/103观察约束条件系数矩阵AA矩阵不存在完全单位向量组。应人工地构建一个完全单位向量组。2021/3/104人为增加两列相当于又加入两个变量 x6、x72021/3/105调整后的A矩阵还原成约束条件为：由于加入的两个变量只起辅助计算的作用，不能影响目标函数和约束条件，因
2、此它的取值只能是0。2021/3/106大M法的原理 引入一个非常大的正数M，用来制约人工变量的取值，并使目标函数变为： 这样，如果计算结果xt0，那么由于M是一个非常大的正数，可以使得F0，也就是使F无法达到最大值。所以，M也被称为罚金系数，这种方法称为大M法。 2021/3/107例：加入人工变量x6，x7后，原模型变为： 2021/3/108用单纯形法求解此时，各系数矩阵、向量为：2021/3/109段段Cj03-1-100-M-MQi注注基基bP1P2P3P4P5P6P710x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011Cj-Zj4M-6
3、M+3M-13M-10-M0020x4103-20100-1-Mx610（1）00-11-21 -1x31-2010001Cj-ZjM+11M-100-M0-3M+130x412（3）001-2 2-5 -1x210100-11-2-1x31-2010001Cj-Zj21000-1-M+1-M-143x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Cj-Zj-2000-1/3-1/3-M+1/3-M+2/32021/3/1010结论 cj-zj均为非正数 得到最优解和最优值。 x1=4，x2=1，x3=9，x4=x5= x6=x7
4、=0， minF= -maxF=-2 2021/3/1011例2：用大M法求解2021/3/1012大M法引入人工变量x5，x6，x7，将原问题化为 2021/3/1013段段Cj0-2-111-M-M-MQi注注基基bP1P2P3P4P5P6P71-Mx52（1）-12-11002-Mx6621-310103-Mx7711110017Cj-Zj15M4M-2M-11M+10002-2x121-12-100-Mx6203-7（3）102/3-Mx7502-12015/2Cj-Zj7M+405M-3-8M+55M-1003-2x18/310-1/3001x42/301-7/310-Mx711/3
5、00(11/3)01Cj-Zj11/3M+14/30-211/3M+7/3004-2x1310001x43010(1)1x310010Cj-Zj20-2002021/3/1014特殊情况特殊情况1、无可行解无可行解无可行解无可行解：线性规划最优解中存在人工变量大于零，则此线性规划无可行解；2、无界解无界解无界解无界解：在求目标函数最大值的问题中，在某次迭代的单纯形表中，如果存在着一个不满足符号条件的检验数，并且该列的系数向量的每个元素都小于或等于零，则此线性规划问题无界。3、无穷多最优解无穷多最优解无穷多最优解无穷多最优解：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解；4、退化退化退化退化：在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。退化易产生循环迭代，为避免循环，遵守以下两条原则：在所有检验数小于零的非基变量中，选一个下标最小的作为调入变量；在存在两个以上最小比值时，选一个下标最小的作为调出变量。2021/3/1015练习题2021/3/1016
