人工变量法第二次迭代详解：从单纯形表到最优解判定

1. 项目概述：从“硬凑”到“真解”的人工变量法实战

在运筹学的线性规划求解里，单纯形法是个核心工具，但它的启动有个前提：你得先找到一个“初始基本可行解”。这就像开车，你得先打着火。可现实中的很多线性规划模型，特别是“≥”型约束或者等式约束，它们的标准形式里并不天然包含一个现成的单位矩阵作为初始基。这时候，直接点火是点不着的。怎么办？老司机们发明了一个巧妙的“助燃剂”——人工变量法。今天，我就以一个具体的案例，带大家走一遍人工变量法中第二次迭代的完整过程。这不仅仅是套公式，更是理解算法如何一步步剔除“水分”（人工变量），逼近真实最优解的关键。

我们这次聚焦的，正是从第一次迭代进入第二次迭代的那个转折点。第一次迭代后，我们可能还在和人工变量纠缠，目标函数值也掺着“惩罚项”的假象。第二次迭代，往往是决定人工变量能否被赶出基变量、求解能否回归正轨的关键一步。这个过程涉及到中心元变换、检验数重算、最优解再判定以及新一轮的入基/出基变量选择。很多教材讲得比较理论，我结合自己当年踩过的坑和教学中的反馈，把每一步的“为什么”和“怎么操作”掰开揉碎了讲，尤其是检验数计算这个容易迷糊的地方，我会用两种视角来解读，保证你不仅能跟着做对，更能理解背后的逻辑。

2. 案例回顾与第二次迭代起点设定

为了不让大家迷失在抽象的符号里，我们沿用一个人工变量法的经典教学案例，也是很多实际资源分配问题的简化模型。假设我们的线性规划问题标准化后是这样的：

目标函数（Min）:Z = 4x₁ + x₂ + 0x₃ + 0x₄ + M R₁ + M R₂约束条件:

1. 3x₁ + x₂ + x₃ = 3
2. 4x₁ + 3x₂ - x₄ + R₁ = 6
3. x₁ + 2x₂ + R₂ = 4
4. x₁, x₂, x₃, x₄, R₁, R₂ ≥ 0

其中，x₃是松弛变量，x₄是剩余变量（前面带了负号），R₁和R₂就是我们为了构造初始基而引入的人工变量。M是一个巨大的正数（惩罚系数），意味着在目标函数里，我们希望尽可能快地把人工变量的值降到0。

经过第一次迭代（初始单纯形表构建和第一次换基），我们通常会得到一张更新后的单纯形表。假设第一次迭代后，我们选择的入基变量是x₁，出基变量是R₁（具体计算过程略，这是第一次迭代的内容），那么迭代后的表格可能如下所示（这是本次第二次迭代的起点，请务必理解）：

注意：这个表格是假设的第一次迭代结果，用于演示第二次迭代。实际数字可能因第一次迭代时中心元选择不同而有差异，但结构相似。关键点在于：1. 人工变量R₁已出基（值为0），但R₂仍在基中且值为5/2。2. 目标函数值Z包含惩罚项M。3. 检验数中仍含有M。

我们的任务很明确：从这个状态出发，进行第二次迭代，目标是让另一个人工变量R₂也出基，并最终得到所有检验数非负（最小化问题）的最优解。

3. 第二次迭代详解：五步闭环操作

3.1 最优解判定与入基变量选择

首先，我们审视当前解是否最优。对于最小化问题，最优解的判定标准是：所有检验数σⱼ ≥ 0。

看上面表格最后一行检验数：

• σ(x₂) = 1 - 5M/4
• σ(x₄) = -1 + 3M/4
• σ(R₁) = M

由于M是很大的正数，1 - 5M/4和-1 + 3M/4的符号由M项主导。因为5M/4 > 1，所以1 - 5M/4 < 0。同理，3M/4 > 1，所以-1 + 3M/4 > 0。所以，检验数σ(x₂)为负数。

结论：当前解非最优。需要选择检验数为负的变量作为入基变量，以改善目标函数。这里只有σ(x₂)为负，因此入基变量确定为 x₂。

实操心得：在人工变量法阶段，判断检验数符号时，可以快速用“M主导”原则。只要M的系数是正的且足够大，该项就是很大的正数；M的系数是负的，该项就是绝对值很大的负数。这比具体计算数值更快。

3.2 出基变量选择（最小比值原则）

入基变量x₂确定后，我们要决定当前基变量（x₃, x₁, R₂）中哪一个要离开，给x₂腾位置。依据是最小非负比值原则：用右端项(b)的值除以入基变量x₂在对应约束行中的系数（主元列系数），取比值最小且非负的那一行对应的基变量出基。

计算比值θ：

1. 对于基变量x₃所在行：系数a₃₂ = -5/4 < 0。规则：系数为负或零时，不计算比值（或认为比值无穷大），因为增加x₂不会减少x₃，无法驱动x₃离基。
2. 对于基变量x₁所在行：系数a₁₂ = 3/4 > 0，比值 θ₁ = b₁ / a₁₂ = (3/2) / (3/4) = 2。
3. 对于基变量R₂所在行：系数aᵣ₂ = 5/4 > 0，比值 θ₂ = bᵣ / aᵣ₂ = (5/2) / (5/4) = 2。

这里出现了比值相等的情况（θ₁ = θ₂ = 2）。根据单纯形法的标准处理，可以任选其一。但这里有一个重要的策略考量：我们迫切希望人工变量R₂出基。因此，优先选择比值相同的人工变量行作为出基行。这能加速将人工变量剔出基外。

所以，选择出基变量为 R₂。对应的，中心元就是出基变量R₂行与入基变量x₂列交叉的那个元素：aᵣ₂ = 5/4。

避坑指南：最小比值原则计算时，一定要忽略系数为非正数的行。如果所有系数都非正，则问题无界（目标函数值可无限减小）。当比值相同时，选择人工变量出基是常用且有效的策略。如果都是结构变量，则可以任选或按行顺序选择，有时会影响迭代次数，但不影响最终结果。

3.3 中心元变换（高斯-约当消元）

这是迭代的核心计算步骤，目的是让入基变量x₂在其对应的列中变成一个单位向量（即中心元变为1，该列其他元素变为0），从而使其进入基变量组。

我们的中心元是5/4。变换步骤如下：

Step 1: 将中心元所在行（出基行）除以中心元值，使中心元变为1。出基行原为：[R₂ | 5/2 | 0 | 5/4 | 0 | 1/4 | -1/4 | 1] 除以 (5/4) 得到新行（此时基变量由R₂变为x₂）：[x₂ | 2 | 0 | 1 | 0 | 1/5 | -1/5 | 4/5]

Step 2: 用消元法将中心元所在列（x₂列）的其他行元素变为0。

• 针对x₃行：原行 [x₃ | 3/2 | 0 | -5/4 | 1 | 3/4 | -3/4 | 0] 要消去x₃行的x₂列系数(-5/4)。我们将新的x₂行乘以(5/4)，然后加到原x₃行上。 计算：新x₂行 × (5/4) = [0 | 5/2 | 0 | 1 | 1/4 | -1/4 | 1] 原x₃行 + 上式 = [x₃ | (3/2+5/2)=4 | 0 | (-5/4+5/4)=0 | 1 | (3/4+1/4)=1 | (-3/4-1/4)=-1 | (0+1)=1]新x₃行：[x₃ | 4 | 0 | 0 | 1 | 1 | -1 | 1]

• 针对x₁行：原行 [x₁ | 3/2 | 1 | 3/4 | 0 | -1/4 | 1/4 | 0] 要消去x₁行的x₂列系数(3/4)。我们将新的x₂行乘以(-3/4)，然后加到原x₁行上。 计算：新x₂行 × (-3/4) = [0 | -3/2 | 0 | -3/4 | 0 | -3/20 | 3/20 | -3/5] 原x₁行 + 上式 = [x₁ | (3/2-3/2)=0 | 1 | (3/4-3/4)=0 | 0 | (-1/4-3/20)=-8/20=-2/5 | (1/4+3/20)=8/20=2/5 | (0-3/5)=-3/5]新x₁行：[x₁ | 0 | 1 | 0 | 0 | -2/5 | 2/5 | -3/5]

Step 3: 更新基变量列。出基变量R₂被入基变量x₂替换。

变换后的新单纯形表如下：

计算技巧：中心元变换本质是初等行变换，保持耐心，一步一步来。建议在草稿纸上清晰地列出“原行”、“加减倍数×新中心行”、“结果新行”这三列，避免心算错误。分数运算时，通分要仔细。

3.4 检验数计算（两种方法）

检验数需要重新计算。有两种等效的方法，我建议都掌握，可以互相验证。

方法一：公式法 σⱼ = cⱼ - C_B * Pⱼ其中，cⱼ是变量xⱼ在目标函数中的原始系数，C_B是当前基变量在目标函数中系数构成的行向量，Pⱼ是当前表中变量xⱼ的系数列向量。 当前基变量为 [x₃, x₁, x₂]，对应的目标系数 C_B = [0, 4, 1]。

• 计算σ(x₁)：c₁=4, P₁=[0,1,0]^T。σ(x₁)=4 - [0,4,1][0,1,0]^T = 4 - (00+41+10)=4-4=0。
• 计算σ(x₄)：c₄=0, P₄=[1, -2/5, 1/5]^T。σ(x₄)=0 - [0,4,1][1, -2/5, 1/5]^T = 0 - (01 + 4*(-2/5) + 1*(1/5)) = 0 - (-8/5+1/5)=0 - (-7/5)=7/5。
• 计算σ(R₁)：c_{R₁}=M, P_{R₁}=[-1, 2/5, -1/5]^T。σ(R₁)=M - [0,4,1][-1, 2/5, -1/5]^T = M - (0(-1)+4*(2/5)+1*(-1/5)) = M - (8/5 - 1/5)= M - 7/5。
• 计算σ(R₂)：c_{R₂}=M, P_{R₂}=[1, -3/5, 4/5]^T。σ(R₂)=M - [0,4,1][1, -3/5, 4/5]^T = M - (01+4*(-3/5)+1*(4/5)) = M - (-12/5+4/5)= M - (-8/5)= M + 8/5。
• 对于基变量x₃, x₁, x₂，其检验数必为0，这是单纯形表的一个性质。

方法二：差额计算法（利用变换后的表）我们已知变换前的检验数行。中心元变换时，检验数行也应同步进行相同的行变换（以消去入基变量x₂对应的检验数，使其变为0）。 变换前检验数行（从起点表来）：[Z=6+5M/2 | 0, 1-5M/4, 0, -1+3M/4, M, 0] 我们需要消去检验数行中x₂列的系数(1-5M/4)。变换后新的x₂行（即中心行）为：[x₂ | 2 | 0, 1, 0, 1/5, -1/5, 4/5]。 将检验数行减去(1-5M/4)倍的新x₂行。 这个计算量较大，但原理清晰。通常在手算时，对于非基变量列，用方法一更直接；对于整个检验数行的更新，方法二在理解变换一致性上更有帮助。

我们采用方法一的结果，更新单纯形表：

目标函数值Z计算：Z = C_B * b = [0, 4, 1] * [4, 0, 2]^T = 04 + 40 + 1*2 = 2。 同时，由于人工变量R₁和R₂已全部出基（值均为0），惩罚项M不再影响目标函数值。所以当前Z=2是真实的目标函数值。

最终完整的第二次迭代后单纯形表为：

3.5 新一轮最优解判定

我们再次检查检验数行（最后一行）。对于最小化问题：

• σ(x₄) = 7/5 > 0
• σ(R₁) = M - 7/5。由于M是很大的正数，M - 7/5 > 0。
• σ(R₂) = M + 8/5 > 0。
• 其余非基变量检验数均为0或正数。

结论：所有检验数σⱼ ≥ 0。满足最小化问题的最优解判定条件。

同时，我们发现所有人工变量R₁和R₂都已不在基变量中，且当前解（x₁=0, x₂=2, x₃=4, x₄=0）满足所有原始约束（代入验证即可）。因此，我们得到了原问题的最优基本可行解。

最优解为：x₁* = 0, x₂* = 2。最优目标函数值为：Z* = 40 + 12 = 2。

4. 关键点解析与常见问题排查

4.1 为什么人工变量法需要大M？

引入大M是为了在目标函数中“惩罚”人工变量。对于最小化问题，加上+M*Rᵢ，意味着只要Rᵢ>0，目标函数值就会变得巨大，单纯形法为了最小化Z，就会优先驱动这些人工变量变为0（出基）。如果最终最优解中人工变量仍大于0，说明原问题无可行解（约束条件自相矛盾）。

注意事项：在计算机求解时，大M需要取一个足够大的数值，但又不是无穷大。如果M太小，可能无法起到惩罚作用；如果太大，在数值计算中可能引发舍入误差，误判检验数符号。实践中，软件常使用两阶段法来避免直接设定M值。

4.2 检验数计算错误的高发区

检验数计算错误是人工变量法手算中最常见的问题。

1. 混淆最大化与最小化的最优判定标准：最大化问题是σⱼ ≤ 0最优；最小化问题是σⱼ ≥ 0最优。务必先明确问题类型。
2. 忽略M的符号主导作用：在包含M的检验数表达式中（如1-5M/4），当M足够大时，符号完全由含M的项决定。快速判断时，不用精确计算具体数值，直接看M的系数正负即可。
3. 基变量检验数不为0：如果计算发现某个基变量的检验数不为0，几乎可以肯定是之前的中心元变换或检验数更新步骤出了错，需要回溯检查。

4.3 迭代停滞与退化现象

有时，你会遇到最小比值相同的情况（非人工变量），或者迭代后目标函数值没有改善。这可能是退化现象：一个或多个基变量取值为0。在比值相同时，不同的出基选择可能导致算法在几个基可行解之间循环（理论上可能，实际很少见）。应对策略是采用“勃兰特规则”等摄动法思想，比如总是选择下标最小的变量入基或出基。

在我们的案例中，比值相同发生在人工变量和结构变量之间，优先驱赶人工变量出基是一个明确且正确的策略，避免了可能的冗长迭代。

4.4 从第二次迭代看算法收敛

第二次迭代在这个案例中恰好找到了最优解。这展示了人工变量法的一个理想流程：通过引入人工变量启动，经过有限次迭代（通常1到n次），将所有人工变量逐出基，然后就在原始问题的可行域内进行单纯的优化，直至最优。第二次迭代的成功，关键在于正确选择了检验数为负且能使人工变量离基的入基变量，并通过中心元变换实现了基的替换和检验数的优化。

5. 手工计算与软件求解的桥梁理解

虽然现在有LINDO、Lingo、Excel规划求解等工具可以秒解线性规划，但手工演练人工变量法的每一步，尤其是第二次迭代这样的关键步骤，价值巨大。这能帮你：

1. 深刻理解单纯形法的“换基”本质：就像更换团队的骨干成员，每次迭代都是用一个有潜力改善目标的新变量（入基）替换一个贡献已达瓶颈的旧变量（出基）。
2. 调试模型：当软件报错“无可行解”或“无界解”时，你能通过理解人工变量的去向（是否无法驱离）或检验数的特征，快速定位是约束矛盾还是目标函数设置问题。
3. 理解两阶段法：人工变量法（大M法）在理论上是两阶段法的前身。第一阶段的目标就是最小化所有人工变量之和，这等价于给人工变量赋予一个极大的惩罚系数M。手工算过，你就能明白两阶段法为什么要分两步走。

我自己在最初学习时，曾机械地套用公式，直到在一次项目建模中，软件结果与预期不符。回头检查，发现是一个约束条件的方向设反了，导致人工变量无法离基。正是对手工算法步骤的熟悉，让我快速找到了这个建模错误。所以，别把这些迭代计算看成枯燥的数学练习，它是你构建和诊断优化模型的内功。