运筹学大M法.pptx

第二节第二节 大大M法法 如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量，人工地构成一个单位向量组。人工变量只起过渡作用，不应影响决策变量的取值。两种方法可控制人工变量取值。大M法两阶段法例解：引入松弛变量x4、剩余变量x5，将数学模型标准化观察约束条件系数矩阵AA矩阵不存在完全单位向量组。应人工地构建一个完全单位向量组。人为增加两列相当于又加入两个变量 x6、x7调整后的A矩阵还原成约束条件为：由于加入的两个变量只起辅助计算的作用，不能影响目标函数和约束条件，因此它的取值只能是0。大M法的原理 引入一个非常大的正数M，用来制约人工变量的取值，并使目标函数变为：这样，如果计算结果xt0，那么由于M是一个非常大的正数，可以使得F0，也就是使F无法达到最大值。所以，M也被称为罚金系数，这种方法称为大M法。例：加入人工变量x6，x7后，原模型变为：用单纯形法求解此时，各系数矩阵、向量为：段段Cj03-1-100-M-MQi注注基基bP1P2P3P4P5P6P710 x4111-21100011-Mx63-4120-1103/2-Mx71-20（1）00011Cj-Zj4M-6M+3M-13M-10-M0020 x4103-20100-1-Mx610（1）00-11-21-1x31-2010001Cj-ZjM+11M-100-M0-3M+130 x412（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/3结论 cj-zj均为非正数 得到最优解和最优值。x1=4，x2=1，x3=9，x4=x5=x6=x7=0，minF=-maxF=-2 例2：用大M法求解大M法引入人工变量x5，x6，x7，将原问题化为 段段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/300(11/3)01Cj-Zj11/3M+14/30-211/3M+7/3004-2x1310001x43010(1)1x310010Cj-Zj20-200特殊情况特殊情况1、无可行解无可行解无可行解无可行解：线性规划最优解中存在人工变量大于零，则此线性规划无可行解；2、无界解无界解无界解无界解：在求目标函数最大值的问题中，在某次迭代的单纯形表中，如果存在着一个不满足符号条件的检验数，并且该列的系数向量的每个元素都小于或等于零，则此线性规划问题无界。3、无穷多最优解无穷多最优解无穷多最优解无穷多最优解：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解；4、退化退化退化退化：在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。退化易产生循环迭代，为避免循环，遵守以下两条原则：在所有检验数小于零的非基变量中，选一个下标最小的作为调入变量；在存在两个以上最小比值时，选一个下标最小的作为调出变量。练习题