线性规划中的大M法（Big-M Method in Linear Programming）
字数 2047 2025-12-13 22:39:29

线性规划中的大M法（Big-M Method in Linear Programming）

大M法是求解线性规划问题的一种人工变量技术，特别用于处理约束条件为“≥”或“=”类型，导致初始基本可行解不易直接获得的情况。我会从问题背景开始，逐步解释其原理、步骤和应用。

第一步：线性规划标准形式与初始基本可行解的困境
线性规划问题通常要求化为标准形式：目标函数最小化（或最大化），所有约束为等式，且右侧常数非负，所有变量非负。例如：
最小化 \(c^T x\)
满足 \(Ax = b, x \geq 0\)，其中 \(b \geq 0\)。

当约束矩阵 \(A\) 中不包含一个现成的单位矩阵（即没有明显的初始基本可行解）时，无法直接启动单纯形法。常见情况包括：

  1. 约束原是“≤”，通过加松弛变量可得单位矩阵。
  2. 但若约束是“≥”（需减剩余变量）或“=”，则加入的变量系数为-1或1，不构成单位矩阵。

第二步：引入人工变量与惩罚思想
为构造一个“人工的”单位矩阵，我们对每个没有松弛变量可用的约束（即“≥”或“=”）引入一个新变量，称为人工变量。例如：
原约束：\(a_{i1}x_1 + ... + a_{in}x_n = b_i\)（或 ≥ b_i）
引入人工变量 \(R_i \geq 0\)，变为：\(a_{i1}x_1 + ... + a_{in}x_n + R_i = b_i\)。
这样，所有人工变量系数构成一个单位矩阵，可令人工变量为基变量，其余非基变量为0，得到初始解 \(x=0, R=b\)。

但此解可能不可行于原问题，因为原问题要求人工变量为0。为此，大M法在目标函数中对人工变量施加一个巨大的惩罚系数 \(M\)（一个极大的正数），使得算法在优化过程中倾向于将人工变量驱赶出基（变为0）。对于最小化问题，目标函数变为：\(\min \; c^T x + M \sum R_i\)。

第三步：具体计算步骤与M的处理

  1. 建立修正问题：对每个需要人工变量的约束引入 \(R_i\)，并在目标函数中加上 \(M \cdot \sum R_i\)（最小化时）。
  2. 初始化单纯形表：以人工变量和可能的松弛变量为初始基变量，形成初始单纯形表。
  3. M的代数处理：在单纯形表计算中，M被视为一个极大的正数。检验数行（指示是否最优）会包含M的项。计算时，将检验数按M的幂次分开处理：先比较M的系数（极大惩罚主导），若M系数不为0，则更正的检验数更优；若M系数均为0，再比较常数部分。
  4. 迭代：进行单纯形法迭代，选择进基变量（通常检验数最负的列），出基变量按最小比值规则确定。
  5. 终止条件：
    • 最优解达到：所有检验数非负（最小化问题），且所有人工变量均为非基变量（值为0）。此时得到原问题最优解。
    • 若达到最优解但某人工变量仍在基中且值为正，则原问题无可行解（因为人工变量无法被驱离）。
    • 若检验数显示无界解，且涉及人工变量的部分满足一定条件，则原问题可能无界或无可行解（需具体分析）。

第四步：M的取值与实际计算注意
理论上M是一个任意大的正数，但实际计算中（如软件实现）通常不赋予具体数值，而是用符号M进行代数比较（如上述检验数比较规则），避免因取值不当引起的数值问题（太大导致病态，太小可能无法有效惩罚）。教学或手动计算时，有时会赋予一个具体大数（如10^6），但需谨慎。

第五步：举例说明
考虑问题：
最小化 \(z = 2x_1 + 3x_2\)
满足：
\(x_1 + x_2 \geq 3\)
\(x_1 - x_2 = 1\)
\(x_1, x_2 \geq 0\)

化为等式：
(1) \(x_1 + x_2 - s_1 + R_1 = 3\) （s_1为剩余变量，R_1为人工变量）
(2) \(x_1 - x_2 + R_2 = 1\)
目标：\(\min z = 2x_1 + 3x_2 + M R_1 + M R_2\)

以 \(R_1, R_2\) 为初始基，构建单纯形表。迭代中，由于M很大，检验数中x1、x2项会包含+M的系数，驱动算法优先将人工变量替换出基。最终若得到最优解且R1、R2为非基（值为0），则得到原问题解。

第六步：与大M法相关的讨论

  • 与两阶段法的比较：大M法将惩罚直接融入目标函数，一次求解；两阶段法则先以最小化人工变量和为第一阶段目标，找到可行解后再解原问题。大M法可能因M取值不当而数值不稳定，两阶段法更稳定常用。
  • 适用性：适用于任何线性规划问题初始基不可得的情况，是单纯形法的重要补充。
  • 无可行解的判断：若最优解中人工变量仍为正，则原问题无可行解。

通过以上步骤，大M法系统性地通过引入惩罚项，将寻找初始可行解的过程融入单纯形法优化中，是线性规划中处理人工变量的经典方法。

线性规划中的大M法（Big-M Method in Linear Programming） 大M法是求解线性规划问题的一种人工变量技术，特别用于处理约束条件为“≥”或“=”类型，导致初始基本可行解不易直接获得的情况。我会从问题背景开始，逐步解释其原理、步骤和应用。 第一步：线性规划标准形式与初始基本可行解的困境 线性规划问题通常要求化为标准形式：目标函数最小化（或最大化），所有约束为等式，且右侧常数非负，所有变量非负。例如： 最小化 \( c^T x \) 满足 \( Ax = b, x \geq 0 \)，其中 \( b \geq 0 \)。 当约束矩阵 \( A \) 中不包含一个现成的单位矩阵（即没有明显的初始基本可行解）时，无法直接启动单纯形法。常见情况包括： 约束原是“≤”，通过加松弛变量可得单位矩阵。 但若约束是“≥”（需减剩余变量）或“=”，则加入的变量系数为-1或1，不构成单位矩阵。 第二步：引入人工变量与惩罚思想 为构造一个“人工的”单位矩阵，我们对每个没有松弛变量可用的约束（即“≥”或“=”）引入一个新变量，称为人工变量。例如： 原约束：\( a_ {i1}x_ 1 + ... + a_ {in}x_ n = b_ i \)（或 ≥ b_ i） 引入人工变量 \( R_ i \geq 0 \)，变为：\( a_ {i1}x_ 1 + ... + a_ {in}x_ n + R_ i = b_ i \)。 这样，所有人工变量系数构成一个单位矩阵，可令人工变量为基变量，其余非基变量为0，得到初始解 \( x=0, R=b \)。 但此解可能不可行于原问题，因为原问题要求人工变量为0。为此，大M法在目标函数中对人工变量施加一个巨大的惩罚系数 \( M \)（一个极大的正数），使得算法在优化过程中倾向于将人工变量驱赶出基（变为0）。对于最小化问题，目标函数变为：\( \min \; c^T x + M \sum R_ i \)。 第三步：具体计算步骤与M的处理 建立修正问题 ：对每个需要人工变量的约束引入 \( R_ i \)，并在目标函数中加上 \( M \cdot \sum R_ i \)（最小化时）。 初始化单纯形表 ：以人工变量和可能的松弛变量为初始基变量，形成初始单纯形表。 M的代数处理 ：在单纯形表计算中，M被视为一个极大的正数。检验数行（指示是否最优）会包含M的项。计算时，将检验数按M的幂次分开处理：先比较M的系数（极大惩罚主导），若M系数不为0，则更正的检验数更优；若M系数均为0，再比较常数部分。 迭代 ：进行单纯形法迭代，选择进基变量（通常检验数最负的列），出基变量按最小比值规则确定。 终止条件 ： 最优解达到：所有检验数非负（最小化问题），且所有人工变量均为非基变量（值为0）。此时得到原问题最优解。 若达到最优解但某人工变量仍在基中且值为正，则原问题无可行解（因为人工变量无法被驱离）。 若检验数显示无界解，且涉及人工变量的部分满足一定条件，则原问题可能无界或无可行解（需具体分析）。 第四步：M的取值与实际计算注意 理论上M是一个任意大的正数，但实际计算中（如软件实现）通常不赋予具体数值，而是用符号M进行代数比较（如上述检验数比较规则），避免因取值不当引起的数值问题（太大导致病态，太小可能无法有效惩罚）。教学或手动计算时，有时会赋予一个具体大数（如10^6），但需谨慎。 第五步：举例说明 考虑问题： 最小化 \( z = 2x_ 1 + 3x_ 2 \) 满足： \( x_ 1 + x_ 2 \geq 3 \) \( x_ 1 - x_ 2 = 1 \) \( x_ 1, x_ 2 \geq 0 \) 化为等式： (1) \( x_ 1 + x_ 2 - s_ 1 + R_ 1 = 3 \) （s_ 1为剩余变量，R_ 1为人工变量） (2) \( x_ 1 - x_ 2 + R_ 2 = 1 \) 目标：\( \min z = 2x_ 1 + 3x_ 2 + M R_ 1 + M R_ 2 \) 以 \( R_ 1, R_ 2 \) 为初始基，构建单纯形表。迭代中，由于M很大，检验数中x1、x2项会包含+M的系数，驱动算法优先将人工变量替换出基。最终若得到最优解且R1、R2为非基（值为0），则得到原问题解。 第六步：与大M法相关的讨论 与两阶段法的比较 ：大M法将惩罚直接融入目标函数，一次求解；两阶段法则先以最小化人工变量和为第一阶段目标，找到可行解后再解原问题。大M法可能因M取值不当而数值不稳定，两阶段法更稳定常用。 适用性 ：适用于任何线性规划问题初始基不可得的情况，是单纯形法的重要补充。 无可行解的判断 ：若最优解中人工变量仍为正，则原问题无可行解。 通过以上步骤，大M法系统性地通过引入惩罚项，将寻找初始可行解的过程融入单纯形法优化中，是线性规划中处理人工变量的经典方法。