单纯形法到底在干什么?
线性规划的可行域是一个凸多面体(二维时就是多边形)。一个基本事实是: 如果最优解存在,就一定能在可行域的某个顶点上取到。单纯形法的全部工作,就是 从一个顶点出发,沿着可行域的棱,一步步走到更好的相邻顶点,直到再也找不到更好的顶点为止。
它之所以能"只看表不看图",是因为一个顶点和一个基是一一对应的: 顶点处有 n 个变量取 0(非基变量),其余 m 个变量(基变量 X_B)由方程组唯一确定。 于是"换一个顶点"就变成了"换一组基",而换基在表上就是一次 Gauss-Jordan 消元,纯粹是机械的行运算。
1. 标准形:先把问题铺平成表格
- 目标:一律化成 max。若原题是 min,就令 z = −w 求 max,最后再把目标函数值取反。
- 约束:把 ≤ 加上松弛变量(系数 +1,代表没用完的资源); ≥ 减去剩余变量(系数 −1)再补一个人工变量(系数 +1); = 直接补人工变量。
- 右端项:把 b < 0 的约束两边同乘 −1,保证 b ≥ 0。
- 这样每个约束都变成等式 Ax = b,而且松弛变量和人工变量的系数列恰好是单位向量, 可以直接把它们取作初始基,立刻读出初始基可行解 X_B = b。
人工变量是"假变量",原问题里并不存在它。为了逼它在最优解中取 0,大 M 法把它的目标系数取成 −M (M 是一个任意大的正数),于是只要它取值大于 0,目标函数就会被罚得很惨。 这就是表中 C_B 列会出现 −M、σⱼ 会出现含 M 的项的原因。
2. σⱼ 检验数:判断"还能不能更好",并挑出谁进基
表中最后一行就是检验数:
σⱼ = cⱼ − Σᵢ C_B(i)·aᵢⱼ ,z = Σᵢ C_B(i)·bᵢ
它的含义是:非基变量 xⱼ 每增加 1 个单位,目标函数会改变多少。 因为把 xⱼ 增加 1 时,为了保持等式约束,基变量必须相应调整,调整的代价正好是 Σ C_B(i)aᵢⱼ, 所以净收益就是 cⱼ 减掉这个代价。
- max 问题:只要还有 σⱼ > 0,说明 xⱼ 进基能提高 z,就还没到最优; 通常取最大的 σⱼ 对应的变量进基(改善最快)。全部 σⱼ ≤ 0 时就是最优解。
- min 问题:σⱼ 的符号与此相反,判据变成 σⱼ ≥ 0 为最优,取最小的 σⱼ 进基。
- 基变量的 σⱼ 永远等于 0 —— 这是检验"表算对了没有"的一个快捷办法。
3. θ 最小比值规则:定出谁离基
选好进基变量 xₖ 之后,它从 0 开始变大。由 x_B(i) = bᵢ − aᵢₖ·xₖ 可知, 只有 aᵢₖ > 0 的基变量会随 xₖ 增大而减小。为了不破坏 X_B ≥ 0(可行性), 必须
xₖ ≤ θ = min{ bᵢ / aᵢₖ | aᵢₖ > 0 }
- 取到这最小比值的那一行,其基变量第一个被压到 0 —— 它就是离基变量,而主元就是这一行的 aᵢₖ。
- 若某列所有 aᵢₖ ≤ 0:xₖ 可以无限增大而所有基变量不减,同时 σₖ > 0 意味着 z 能无限增大 —— 这就是无界解。
- 若最小比值 θ = 0(某个基变量本来就是 0),则换基后 z 不变,这叫退化。退化时可能出现循环,可用 Bland 规则破解:从 σⱼ 违反最优性条件的变量中挑下标最小的进基。
4. Gauss-Jordan 消元:把新顶点"算"出来
- 主元行 ÷ 主元,使主元变成 1;
- 其余各行(含 σⱼ 行)减去"本行主元列数值 × 主元行",使主元列其余元素变成 0;
- 于是主元列又变成单位向量的一部分,新的 X_B 仍然是单位矩阵,可以直接读出新的基可行解。
几何上,这一步就是沿着一条棱滑到相邻顶点:进基变量从 0 变为 θ,离基变量从它的值变为 0,目标函数值由 z 变为 z + σₖ·θ。
5. 四种结局
| 情况 | 表上的特征 | 结论 |
|---|---|---|
| 唯一最优解 | 所有非基变量 σⱼ ≤ 0(max) | 当前顶点即唯一最优解 |
| 多重最优解 | 某个非基变量 σⱼ = 0 | 该变量可进基而 z 不变,最优解有无穷多个(最优解在一条边/一个面上) |
| 无界解 | σₖ > 0 但主元列所有 aᵢₖ ≤ 0 | 目标函数无上界,不存在有限最优解 |
| 无可行解 | 最优表中仍有人工变量在基内且取值 > 0 | 可行域为空,原问题无解 |
6. 手算流程(照着走就不会错)
- 化标准形:补松弛/剩余/人工变量,把 b 调成非负,目标一律化成 max。
- 填初始表:基变量取单位列对应的变量,写上 C_B、X_B、b。
- 算 σⱼ = cⱼ − Σ C_B(i)aᵢⱼ 与 z = Σ C_B(i)bᵢ。
- 检验:σⱼ 全部满足最优性条件 → 停,写出最优解;否则挑一个进基变量。
- 算 θ,取最小者定离基变量与主元;所有 aᵢₖ ≤ 0 则说明无界。
- Gauss-Jordan 消元,换基,回到第 3 步。