03.2大M法和两阶段法.ppt

第二节 大M法和两阶段法 如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量，人工地构成一个单位向量组。 人工变量只起过渡作用，不应影响决策变量的取值。 两种方法可控制人工变量取值。 大M法 两阶段法 例 解：引入松弛变量x4、剩余变量x5，将数学模型标准化 观察约束条件系数矩阵A A矩阵不存在完全单位向量组。 应人工地构建一个完全单位向量组。 人为增加两列 相当于又加入两个变量 x6、x7 调整后的A矩阵还原成约束条件为： 由于加入的两个变量只起辅助计算的作用，不能影响目标函数和约束条件，因此它的取值只能是0。 两种方法可控制人工变量的取值 大M法 两阶段法 一、大M法 原理： 引入一个非常大的正数M，用来制约人工变量的取值，并使目标函数变为： 这样，如果计算结果xt≠0，那么由于M是一个非常大的正数，可以使得F0，也就是使F无法达到最大值。所以，M也被称为罚金系数，这种方法称为大M法。 例：加入人工变量x6，x7后，原模型变为： 用单纯形法求解 此时，各系数矩阵、向量为： 初始表 检验数判断 1、检验数Cj-Zj=aM+b：当a0时，认为检验数为负；当a0时，认为检验数为正。 2、若最终检验数Zj-Cj均为非正，而b列中对应的检验数Cb-Zb（即最优值）中仍有M存在，说明没有得到确定的最优值，可以解释为约束条件过于苛刻，该线性规划问题无可行解。 结论 ∵Zj-Cj均为负数， ∴得到最优解和最优值。 x1=4，x2=1，x3=9，x4=x5= x6=x7=0， minF= -maxF’=-2 二、两阶段法： 原理：分两阶段求解。 第一阶段，构筑一个只包括人工变量的目标函数：minF=∑xt，在原约束条件下求解，如果计算结果是人工变量均为0，则继续求解；进入第二阶段，如果人工变量不为0，说明原问题无解。 如上例：人工变量为x6，x7， 第一阶段 解题过程 结论 此时，目标函数已得最优值，人工变量均为0。转入第二阶段。 第二阶段 求原问题最优值。目标函数为原问题的目标函数，单纯形表初始表为第一阶段最后一段的元素值，但应去掉人工变量所在列。 maxF’=3x1-x2-x3+0x4+0x5 解题过程 结论 ∵Zj-Cj均为正数， ∴得到最优解和最优值。 x1=4，x2=1，x3=9，x4=x5=0， minF=-2 例2：用大M法和两阶段法求解 大M法 引入人工变量x5，x6，x7，将原问题化为 解题过程 两阶段法 第一阶段：引入辅助问题 解题过程 第二阶段 求原问题最优值：maxF=-2x1-x2+x3+x4 解题过程 特殊情况 1、无可行解：线性规划最优解中存在人工变量大于零，则此线性规划无可行解； 2、无界解：在求目标函数最大值的问题中，在某次迭代的单纯形表中，如果存在着一个不满足符号条件的检验数，并且该列的系数向量的每个元素都小于或等于零，则此线性规划问题无界。 3、无穷多最优解：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解； 4、退化：在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。 退化易产生循环迭代，为避免循环，遵守以下两条原则： 在所有检验数小于零的非基变量中，选一个下标最小的作为调入变量； 在存在两个以上最小比值时，选一个下标最小的作为调出变量。 练习题 P.98 第6、7题 　 　 -1/3 -1/3 0 0 0 -2 → Cj-Zj 2/3 -4/3 1 0 0 9 x3 -1 0 -1 0 1 0 1 x2 -1 　 　 1/3 -2/3 0 0 1 4 x1 3 2 　 　 0 -1 0 0 1 2 → Cj-Zj 0 0 1 0 -2 1 x3 -1 　 0 -1 0 1 0 1 x2 -1 → 　 1 -2 0 0 （3） 12 x5 0 1 P5 P4 P3 P2 P1 b 基 ↓ 注 Qi 0 0 -1 -1 3 0 → Cj 段 　 　 0 0 0 M+1 1 M-1 4M-2 15M → Cj-Zj 7 1 0 0 1 1 1 1 7 x7 -M 3 0 1 0 1 -3 1 2 6 x6 -M → 2 0 0 1 -1 2 -1 （1） 2 x5 -M 1 P7 P6 P5 P4 P3 P2 P1 b 基 ↓ 注 Qi -M -M -M 1 1 -1 -2 0 → Cj 段 　 　 0 0 -4M+2 5M-1 -8M+5 5M-3 0 7M+4 → Cj-Zj 　 5/2 1 0 -1 2 -1 2 0 5 x7 -