单纯形法：从思想到实施

课程目标

学完这 90 分钟，你应该能——

1. 理解单纯形法的几何（顶点↔bfs）与代数（基变换）双重原理
2. 执行单纯形表的手算：初始化→选入基→选主元→行变换→判别最优
3. 编程用 numpy 实现完整单纯形法（拓展任务）
4. 诊断退化、无界、循环等病态情形（错误诊断卡片）
5. 衔接从单纯形法的「离散」到梯度下降的「连续」（末页过渡）

前测 · 5 题（先修链）

确保你的基础能跟上 90 分钟。错题点开看提示。

① 思想（25 分钟）

对应原课件 2.5「单纯形方法的思想」。从几何直观到代数机制。

A.1 · 顶点 ↔ 基可行解（bfs）

1. 关键事实

• LP 的最优解一定在顶点（polytope 的顶点）取得。
• 顶点 ↔ 基可行解（bfs） 一一对应。
• 算法思路：从一个 bfs 移动到另一个 bfs，直到找到最优。

2. 一个三维例子（PPT slide 5-9）

考虑 LP：

$$\min \; c^T x, \quad x \in \mathbb{R}^3, \quad \text{subject to } Ax \le b, \ x \ge 0$$

约束定义的多面体有顶点：

(0,0,0), (0,0,3), (1,0,3), (2,0,2), (2,0,0), (2,2,0), (0,2,0), (0,1,3)

3. 为什么是 bfs？

每个 bfs 对应一个基（m 个基变量），换基 = 移动到相邻 bfs。这给了我们"从代数角度"枚举所有 bfs 的方法。

A.2 · 从 bfs 到 bfs 的移动机制

1. 移动公式（PPT slide 11-12）

从 x0 出发，沿 Aj 方向走 θ 步：

$$x^1 = x^0 + \theta A_j$$

新基变量值 = 原基变量值 - θ × 入基列在基中的展开（Aj = B·y，y 是 B⁻¹A_j）：

$$x^1_{B(i)} = x^0_{B(i)} - \theta \cdot \bar{a}_{ij}, \quad i = 1,\dots,m$$

这里 aij = B−1Aj 的第 i 个分量。

2. 最小比值规则（Min-Ratio Rule）

为保持 x¹B(i) ≥ 0，对所有 aij > 0 的行取最小比值：

3. 退化（Degenerate）

当某个 x0B(i) = 0 时，最小比值 = 0，θ = 0。换基不改变 bfs 位置（但换基），可能导致循环。这在课件里只是提醒，后续大 M/两阶段法会重新遇到。

A.3 · 初等行变换 = 基变换的代数实现

思想：在 bfs 之间移动 = 换基 = 对 A 做行变换（保持 Ax=b 等价）。

一个具体例子（PPT 2.5 slide 18 / 2.6 slide 17-22）

考虑 LP（5 变量，3 约束）：

min x₁+x₂+x₃+x₄+x₅
s.t. 3x₁+2x₂+x₃ = 1
    5x₁+x₂+x₃+x₄ = 3
    2x₁+5x₂+x₃+x₅ = 4
    x₁,x₂,x₃,x₄,x₅ ≥ 0

初始化：行变换 R₂ → R₂ − R₁，R₃ → R₃ − R₁

x₃ 在三行中的系数都是 1，不是单位列。做两次行变换，让 x₃ 只在 R₁ 出现：

A.4 · 检验数 z_j 与最优性准则

1. 成本变化（PPT slide 22-24）

把 Aj 引入基，bfs 位置从 x0 变到 x¹ = x0 + θAj，成本变化为：

$$\Delta z = c_j - c_B^T \bar{A}_j = c_j - z_j$$

其中 zj = cBT B−1 Aj 称为 Aj 的检验数。

2. 最优性判别

② 实施（35 分钟）

对应原课件 2.6「单纯形法的实施」。把思想变成可执行的算法步骤。

B.1 · 单纯形表（Simplex Tableau）的结构

1. 完整结构（PPT slide 3-4）

单纯形表 = 一张 m+1 行 × n+2 列的矩阵：

2. 关键元素

• B⁻¹A 的非基列：aij = B−1Aj，i 行 j 列
• B⁻¹b：当前 bfs，x_B = B−1b
• 检验数行：zj = cBTB−1Aj，等价于相对成本 cj − zj
• RHS：本课件用 −z = −cBTB−1b 写入 RHS 列

B.2 · 初始化：从 LP 到初始 bfs

1. 目标：找到一个 bfs 作为起点

关键：A 中要有 m 个线性无关的单位列向量，这些列对应的变量就是初始基。

2. 两种情形

• 情形 1：A 中已经有 m 个单位列 → 直接取这 m 个变量为基，x_B = b（要求 b ≥ 0）。
• 情形 2：A 中没有 m 个单位列 → 需要引入人工变量（大 M 法 / 两阶段法），本课件不展开。

3. 本课件例子的初始化

LP：

min x₁+x₂+x₃+x₄+x₅
s.t. 3x₁+2x₂+x₃ = 1 (R₁)
    5x₁+x₂+x₃+x₄ = 3 (R₂)
    2x₁+5x₂+x₃+x₅ = 4 (R₃)

观察：x₄ 在 R₂ 系数 1、x₅ 在 R₃ 系数 1 → x₄, x₅ 是天然基变量。但 x₃ 在 R₁、R₂、R₃ 三行都出现（系数都是 1），不是单位列。

B.3 · 选入基列：最负检验数（min 问题）

原理

沿 A_j 走一步 θ = 1，成本变化 = θ(cj − zj) = cj − zj。最负 = 下降最多。

本例（基 [x₃,x₄,x₅]）

检验数 = [−3, −3, 0, 0, 0]。x₁ 与 x₂ 并列最负（都是 −3），任选其一都能降成本： PPT 2.5 slide 20-21 以 x₁ 入基做演示，PPT 2.6 slide 20-21 选 x₂。两条路径殊途同归（最优表相同）。本课件主路径选 x₂（与 2.6 一致，一次迭代到最优）。

为什么「最负」不是「最大」？

对于最小化问题，成本要降。负的 cj − zj 意味着沿 A_j 走能降成本。最负 = 降最多。

对于最大化问题，cj − zj 改写为 zj − cj，选最大正的列（成本增加方向）。这是单纯形法最常被搞混的符号约定。

B.4 · 选主元：最小比值规则

本例（x₂ 入基，主路径）

最小比值 = 1/2，位于 R₁ → x₃ 出基，主元 = 2。

（对照：PPT 2.5 演示的 x₁ 路径，比值 1/3、2/2、R₃ 跳过（x₁ 系数 −1），主元 3，同样 x₃ 出基。）

B.5 · Clear Pivot Column：行变换

1. 目标：让主元列变成单位向量

2. 本例（主元 2 在 R₁，x₂ 入基）

3. 迭代 1 末表（基 [x₂,x₄,x₅]）

x_B = (1/2, 5/2, 3/2)，z = 9/2 = 4.5。检验数全部 ≥ 0 → 已是最优（本例走 x₂ 路径一次迭代到最优）。

B.6 · 成本变化：从 bfs⁰ 到 bfs¹

1. 几何与代数双视角

• 几何：多面体上从一个顶点走到相邻顶点。本例走 x₂ 路径（2.6 主路径），z 从 6 一步降到 9/2 = 4.5（最优）；走 x₁ 路径（2.5 演示），z 依次 6 → 5 → 9/2。
• 代数：每次迭代 Δz = θ × (cj − zj) = (1/2) × (−3) = −3/2（x₂ 入基），z: 6 → 9/2。

2. 终止判别

③ 实例 + 练习（30 分钟）

把前面学的思想 + 实施步骤完整走一遍，然后你自己动手做两道。

C.1 · 完整实例：从初始表到最优解

回顾本节课贯穿始终的 LP（5 个变量、3 个约束）：

min  x₁+x₂+x₃+x₄+x₅
s.t.  3x₁+2x₂+x₃     = 1 (R₁)
     5x₁+x₂+x₃+x₄ = 3 (R₂)
     2x₁+5x₂+x₃+x₅ = 4 (R₃)
     x₁,x₂,x₃,x₄,x₅ ≥ 0

迭代 0 · 初始表（基 [x₃, x₄, x₅]）

初始化：R₂ ← R₂ − R₁，R₃ ← R₃ − R₁，让 x₃ 只在 R₁ 出现，凑出单位基 I。

x_B = (1, 2, 3)，z = 6。检验数 = [−3, −3, 0, 0, 0]，有负数 → 未最优。x₁ 与 x₂ 并列最负。

迭代 1 · x₂ 入基，x₃ 出基（主元 = 2）

x₁、x₂ 并列最负（−3），按 PPT 2.6 选 x₂ 入基。x₂ 列 = (2, −1, 3)，正元素在 R₁、R₃。比值：1/2 = 0.5，3/3 = 1（R₂ 系数 −1 < 0 跳过）。最小 = 1/2 → 主元在 R₁。

检验数 = [3/2, 0, 3/2, 0, 0] 全部 ≥ 0 → 最优。x_B = (1/2, 5/2, 3/2)，z = 9/2 = 4.5。z 从 6 一步降到 9/2（Δz = (1/2)×(−3) = −3/2）。

最优解与验证

把 x* 代回三个约束检验：

• R₁：3·0 + 2·(1/2) + 0 = 1 ✓
• R₂：5·0 + 1·(1/2) + 0 + 5/2 = 3 ✓
• R₃：2·0 + 5·(1/2) + 0 + 0 + 3/2 = 4 ✓

三行全部成立，且非基变量 x₁=x₃=0，基变量非负 → 确实是一个可行基解，且检验数全非负，故为最优解。

C.2 · 自练 1：从建模到最优（生产计划）

某厂用三台设备加工两种产品 A、B。生产 1 件 A 需设备 I 1 小时、设备 II 4 小时；生产 1 件 B 需设备 I 2 小时、设备 III 4 小时。设备 I、II、III 每天可用工时分别为 8、16、12 小时。A、B 每件利润分别为 2、3 千元。求最优生产计划。

第 1 步 · 建模

设 x₁、x₂ 为 A、B 的产量：

max  z = 2x₁ + 3x₂
s.t.  x₁ + 2x₂ ≤ 8  (设备 I)
     4x₁     ≤ 16 (设备 II)
         4x₂ ≤ 12 (设备 III)
     x₁, x₂ ≥ 0

转成 min 标准型（加松弛变量 x₃、x₄、x₅，与例题一致）：

min  z = −2x₁ − 3x₂
s.t.  x₁ + 2x₂ + x₃     = 8
     4x₁     + x₄     = 16
         4x₂     + x₅ = 12
     x₁,…,x₅ ≥ 0

松弛变量 x₃、x₄、x₅ 天然构成单位基。

第 2 步 · 初始表

第 3 步 · 选主元（x₂ 入基后）

x₂ 列 = (2, 0, 4)，正元素在 R₁、R₃。比值：R₁ 8/2 = 4，R₃ 12/4 = 3。最小 = 3 → 主元在 R₃（x₅ 出基）。

C.3 · 自练 2：完整做一次主元消去

用单纯形表求解（min 问题，可直接标准化）：

min  z = x₁ − 2x₂ + x₃
s.t.  x₁ + 2x₂ + x₃     = 4
     2x₁ − x₂     + x₄ = 2
     x₁, x₂, x₃, x₄ ≥ 0

初始表（基 [x₃, x₄]）

C.4 · 错误诊断：这些坑你踩过吗？

下面每组各有 1 个常见错误，找出它并说明正确做法（先自己想，再点开看解析）。

C.5 · 小结与衔接

下一步去哪

• 没有天然单位基怎么办？→ 大 M 法 / 两阶段法（引入人工变量），下节课讲。
• 怎么知道最优解对参数多敏感？→ 对偶理论与灵敏度分析（影子价格）。
• 退化、循环怎么办？→ Bland 规则（按最小下标选入基/出基）可保证不循环。

这些内容对应《最优化方法》第 2 章的后续小节，也是期末考试与数模竞赛的常考点。

后测 · 5 分钟快检

对照课前 5 题，检验这一节课你真正掌握了多少。

拓展 · 从手算到代码，从经典到前沿

1. 用 Python 一行求解（scipy）

主例题对应的代码（对照手算结果 x*=(0, 0.5, 0, 2.5, 1.5), z*=4.5）：

手算是为了懂原理；真到工程和数模竞赛，用求解器（scipy、Gurobi、COPT、MindOpt）更稳、更快、更不易错。

2. 复杂度：为什么单纯形法「理论慢、实际快」

• 最坏情况：指数级。Klee–Minty 立方体（1972）可让某些选主元规则走遍所有顶点。
• 实际表现：平均迭代次数 ≈ O(m) 量级，商业求解器能解百万变量规模。
• 多项式替代：内点法（Karmarkar 1984）、椭球法（Khachiyan 1979）是多项式时间，但常数大，工程上仍常与单纯形法并用。

3. 三个后续专题的伏笔

本节知识图谱

13 个知识点，按「思想 → 工具 → 判别」三层组织。核心链路是绿色的主路径。