3. 单纯形法原理：从几何到代数，单纯形法的核心思想（顶点迭代）与表格实现
单纯形法，说白了就是「沿着顶点爬山」。
我刚开始学运筹学的时候，觉得这名字挺唬人。什么单纯形？什么顶点迭代？后来做项目多了才发现，它的核心逻辑其实特别朴素——你想想看，一个线性规划问题的可行域是个多面体，最优解一定在某个顶点上。那我们就从一个顶点出发，沿着边走到相邻的、更优的顶点，直到走不动为止。
3.1 几何直觉：为什么是顶点？
先问一个问题：线性规划的最优解，为什么一定在顶点上？
我个人习惯用二维情况来理解。假设只有两个变量，约束条件画出来就是一堆直线围成的多边形。目标函数是一条等值线，你平移这条线，最后离开多边形的那个接触点，一定是个角点——也就是顶点。
高维情况同理。只不过我们没法画出来，但数学上可以严格证明：如果存在最优解，那么至少有一个最优解在顶点上。
核心结论：单纯形法本质上是在多面体的顶点之间跳来跳去，每次跳都让目标函数值变好（或至少不变差）。
3.2 从几何到代数：基变量与顶点
几何上我们看顶点，代数上我们怎么描述顶点？
嗯，这里要注意：顶点在代数上对应的是「基可行解」。
怎么理解？
- 一个线性规划问题有 n 个变量，m 个约束（等式形式）。
- 我们选 m 个变量作为「基变量」，剩下的 n-m 个变量设为 0。
- 解这个 m×m 的方程组，得到一组基变量的值。
- 如果这些值都非负，这就是一个基可行解——对应一个顶点。
我在项目中遇到过一个问题：明明模型写对了，但求解器跑出来结果不对。后来排查发现，是初始基变量选得不好，导致迭代次数暴增。所以选初始基这事，真不能马虎。
3.3 单纯形法的核心步骤
单纯形法的迭代过程，我习惯总结成四步：
- 找初始基可行解——通常通过引入松弛变量或人工变量来实现。
- 判断当前解是否最优——看检验数（Reduced Cost）。如果所有非基变量的检验数都 ≤ 0，那就最优了。
- 选择进基变量——选检验数最大的那个非基变量（或者按其他规则）。
- 确定离基变量——用最小比值原则，保证新解仍然可行。
然后重复第2步到第4步，直到最优。
避坑指南：我曾经在选进基变量时，单纯看检验数大小，结果遇到了循环（cycling）。后来改用 Bland 规则，就再也没出过问题。如果你也遇到迭代不收敛的情况，试试 Bland 规则——选下标最小的进基变量和离基变量。
3.4 表格实现：单纯形表
单纯形法的表格实现，说白了就是把上面的步骤用一张表来组织。我个人觉得，表格的好处是直观，每一步都能看到数据变化。
标准单纯形表的结构如下：
| 基变量 | 系数 | x₁ | x₂ | … | xₙ | RHS |
|---|---|---|---|---|---|---|
| x₃ | 0 | a₁₁ | a₁₂ | … | a₁ₙ | b₁ |
| x₄ | 0 | a₂₁ | a₂₂ | … | a₂ₙ | b₂ |
| … | … | … | … | … | … | … |
| z | 1 | c₁ | c₂ | … | cₙ | 0 |
最下面一行是检验数行。如果所有检验数 ≤ 0，当前解就是最优的。
举个例子：
最大化 z = 3x₁ + 2x₂
约束：
x₁ + x₂ ≤ 4
2x₁ + x₂ ≤ 6
x₁, x₂ ≥ 0
引入松弛变量 x₃, x₄，得到标准形：
x₁ + x₂ + x₃ = 4
2x₁ + x₂ + x₄ = 6
z - 3x₁ - 2x₂ = 0
初始单纯形表：
基变量 | x₁ x₂ x₃ x₄ RHS
x₃ | 1 1 1 0 4
x₄ | 2 1 0 1 6
z | -3 -2 0 0 0
检验数：x₁ = -3, x₂ = -2 → 选 x₁ 进基
最小比值：4/1=4, 6/2=3 → x₄ 离基
经过一次迭代后：
基变量 | x₁ x₂ x₃ x₄ RHS
x₃ | 0 0.5 1 -0.5 1
x₁ | 1 0.5 0 0.5 3
z | 0 -0.5 0 1.5 9
检验数：x₂ = -0.5 → 仍然有负检验数，继续迭代
选 x₂ 进基，最小比值：1/0.5=2, 3/0.5=6 → x₃ 离基
第二次迭代后：
基变量 | x₁ x₂ x₃ x₄ RHS
x₂ | 0 1 2 -1 2
x₁ | 1 0 -1 1 2
z | 0 0 1 1 10
所有检验数 ≥ 0，最优解：x₁=2, x₂=2, z=10
注意：单纯形表里的检验数，在最大化问题中，如果所有检验数 ≤ 0 则最优；在最小化问题中，如果所有检验数 ≥ 0 则最优。别搞反了，我曾经在这上面吃过亏。
3.5 单纯形法的知识体系
下面这张图，是我自己总结的单纯形法知识结构，方便你快速回顾：
3.6 一些实用建议
最后，分享几个我在实际项目中积累的经验：
- 初始解很重要：如果初始基可行解离最优解很远，迭代次数会很多。我习惯先用启发式方法找一个好点的初始解。
- 退化问题要小心：当基变量取值为0时，可能出现退化。这时候迭代可能不改进目标函数值，甚至循环。Bland规则是保底方案。
- 大规模问题别用手算：单纯形表手算只适合小规模教学案例。实际项目中，几十万变量的问题，用求解器（如CPLEX、Gurobi）才是正道。
- 理解原理比背步骤重要：我见过太多人只会填表，但不知道为什么这样填。一旦遇到非标准形式，就懵了。理解「顶点迭代」这个核心思想，比记住表格操作更有价值。
单纯形法虽然已经有七八十年历史了，但它背后的思想——从几何到代数，从顶点到基变量——至今仍然是优化算法的基石。搞懂了它，后面学内点法、列生成都会轻松很多。