网络流与线性规划

一条贯穿全局的主线：流、割与对偶

设想你是一位后勤指挥官，要把物资从大本营 $s$ 运到前线 $t$。道路网纵横交错，每条路都有自己的运力上限——有的是高速公路，有的是乡间小道。问题朴素得近乎天真：一次最多能运多少物资过去？

这就是最大流（Maximum Flow）问题。它看起来只是个调度问题，但藏着一个惊人的对偶现象：你能运过去的最大流量，恰好等于敌人用最小代价「切断」整张网络所需付出的代价——最小割（Minimum Cut）。运得越多和切得越省，本是风马牛不相及的两件事，却在数值上分毫不差。这种「一个最大化问题的最优值 = 另一个最小化问题的最优值」的现象，就是本讲的灵魂——对偶（Duality）。

为什么要从网络流讲起？因为它是理解对偶最好的具体例子，而对偶又是现代算法设计中最强大的思想之一。本讲会沿着这样一条线索层层展开：

• 先把网络流彻底讲清楚：怎么定义、怎么求解、求得多快；
• 看到「最大流 = 最小割」这个对偶现象，并理解它为什么成立；
• 把网络流抽象成线性规划（Linear Programming, LP）——一个能统一刻画海量优化问题的框架，而且能在多项式时间内求解；
• 用线性规划当「锤子」去砸 NP-难问题：通过松弛（Relaxation）与舍入（Rounding）得到近似解；
• 最后揭示线性规划自带的对偶结构，并把它锻造成一套通用的算法设计范式——原始对偶框架（Primal-Dual Schema）。

这是一条从具体到抽象、再回到具体的旅程。读完它，你会发现「最大流 = 最小割」不是孤立的巧合，而是一个普遍规律的冰山一角。

网络流模型

流网络

一切从一张带容量的有向图开始。

流网络

流网络（Flow Network）是一个有向图 $G = (V, E)$，其中：

• 每条边 $e \in E$ 有一个非负容量（Capacity）$c_e \in \R^+$，表示这条边能承载的流量上限；
• 指定两个特殊顶点：源点（Source）$s \in V$ 与汇点（Sink）$t \in V$。

我们要在这张图上「注入」流量。流量用一个函数 $f\colon E \to \R^+$ 描述，$f(e)$ 表示边 $e$ 上实际流过的量。但不是随便一个函数都算合法的流——它必须遵守两条物理上天经地义的规则。

合法流

函数 $f\colon E \to \R^+$ 是一个合法流（Valid Flow），若满足：

• 容量约束（Capacity Constraint）：$\forall e \in E,\ 0 \le f(e) \le c_e$。流量不能超过运力，也不能倒着流（非负）。
• 流量守恒（Flow Conservation）：除源点与汇点外，每个顶点流入等于流出：

  $$\forall v \in V \setminus \{s, t\},\quad \sum_{e \in \delta^{\text{in}}(v)} f(e) = \sum_{e \in \delta^{\text{out}}(v)} f(e)$$

这里 $\delta^{\text{in}}(v)$ 与 $\delta^{\text{out}}(v)$ 分别表示射入、射出 $v$ 的边集。守恒律的直觉很简单：中间节点既不是仓库也不是黑洞，进多少就得出多少——就像水管的接头处不会凭空蓄水或漏水。

如果去掉源汇点的特殊地位，要求所有顶点都满足守恒，那么流就「自给自足」地循环起来，称为循环流（Circulation）。源汇点的存在，正是为了让流量有「来处」和「去处」。

流量与最大流问题

源点 $s$ 净流出的总量，就是这个流的流量（Value），记作 $|f|$：

$$|f| = \sum_{e \in \delta^{\text{out}}(s)} f(e) - \sum_{e \in \delta^{\text{in}}(s)} f(e)$$

由守恒律可以证明，源点净流出 = 汇点净流入，所以 $|f|$ 也等于「最终到达 $t$ 的量」。这正是我们关心的「运过去多少」。

最大流问题

给定流网络 $G = (V, E)$、容量 $c$、源点 $s$ 与汇点 $t$，找一个合法流 $f$ 使流量 $|f|$ 最大。

接下来的几节就是要回答：这样的最大流长什么样？怎么求？为了求解，我们先要理解流的「结构」——任何一个流，本质上都是若干条路径和环的叠加。

流分解定理

直接面对「一个流函数」是抽象的：它给每条边分配一个数，看不出物资究竟是怎么从 $s$ 走到 $t$ 的。下面这个定理把这堆数字翻译回我们最朴素的直觉——流就是一条条路径。

流分解定理

任何 $s$-$t$ 流都可以被分解成若干条 $s$-$t$ 路径（Path）和若干个环（Cycle）。也就是说，存在一组 $s$-$t$ 路径和环，每条配一个正的流量值，叠加起来恰好等于原来的流 $f$。

这个定理之所以重要，是因为它把「流」还原成了「运输方案」：物资沿着哪几条路走、各走多少，一目了然。而环则是「空转」的部分——绕一圈回到原地，对净流量毫无贡献，往往可以直接删掉。

构造性证明

证明本身就是一个剥离算法，每一步抽出一条路径或一个环。

抽路径：只要源点还有流出（$\sum_{e \in \delta^{\text{out}}(s)} f(e) > 0$），由守恒律，流量像水一样必然能从 $s$ 一路「流到」$t$——因为每个中间点有入必有出，不会断在半路。于是存在一条 $s$-$t$ 路径 $P$ 上每条边都有正流量。令 $\delta(P) = \min_{e \in P} f_e$ 为这条路径的瓶颈，把路径上每条边的流量都减去 $\delta(P)$。这样至少有一条边被「清零」，路径数随之减少。

抽环：路径抽完后，若图中还有正流量，那么这些剩余流量在每个顶点（包括 $s, t$）都满足流入等于流出——因为路径已经把源汇的「不平衡」抽干了。一个处处守恒、又非零的流必然含环：从任一条有流量的边出发不断往前走，顶点有限，迟早重复，便找到一个环。同样取瓶颈、整体扣减、删掉清零的边。

每一步都至少清零一条边，边数有限，所以算法必然终止，且终止时流量恰好被这些路径和环表示完毕。

流分解定理会在后面反复用到——无论是证明「流量 $\le$ 割容量」，还是分析各种算法的迭代次数，核心都是「一个流最多拆成 $m$ 条路径/环」（$m = |E|$，因为每抽一次至少清零一条边）。记住这个 $m$；连同 $n = |V|$，它们是后面所有复杂度分析的主角。

增广路径与 Ford-Fulkerson 算法

一个朴素的贪心，和它的陷阱

既然流就是一条条路径的叠加，求最大流最自然的想法就是贪心：只要还能从 $s$ 找到一条「有余量」的路径，就尽量往上面灌流量。

形式化地，对一条 $s$-$t$ 路径 $P$，定义它的剩余容量（Residual Capacity）为 $\delta(P) = \min_{e \in P}(c_e - f_e)$——路径上最「紧」那条边还能再塞多少。贪心算法就是：

当存在剩余容量 $\delta(P) > 0$ 的 $s$-$t$ 路径 $P$ 时，把 $P$ 上的流量都增加 $\delta(P)$。

这个贪心有什么问题吗？有，而且很致命。看下面这个经典反例：

考虑四个点 $s, a, b, t$，边为 $s \to a$（容量 $1$）、$a \to t$（容量 $1$）、$s \to b$（容量 $1$）、$b \to t$（容量 $1$），以及中间一条 $a \to b$（容量 $1$）。最大流显然是 $2$（$s \to a \to t$ 和 $s \to b \to t$ 各走 $1$）。但如果贪心第一步选了 $s \to a \to b \to t$，灌入 $1$ 单位流量，三条边 $s\to a, a\to b, b\to t$ 全部占满。此时再也找不到剩余容量为正的 $s$-$t$ 路径了——贪心卡在流量 $1$，却误以为已经最优。

贪心的致命缺陷

一旦把流量「错误地」灌到某条边上，朴素贪心无法反悔。它没有「把已经送出的流量退回来、改道而行」的机制，于是会卡在次优解。

问题的根源是：我们需要一种方式来表达「撤销」。如果算法能意识到「$a \to b$ 这一单位流量其实该改走 $a \to t$」，就能挣脱困境。这正是残余图要解决的事。

残余图

残余图的核心想法是：在描述「还能怎么调整流量」时，不仅要记录每条边还能正向加多少，还要记录它已经流了多少、因而能反向退多少。

残余图

给定流网络 $G = (V, E)$、容量 $c$ 和当前流 $f$，其残余图（Residual Graph）$G_f = (V, E')$ 这样构造：

• 正向残余边：对每条 $e = (u, v) \in E$，若 $c_e > f_e$，在 $E'$ 中加入边 $(u, v)$，容量 $c'_e = c_e - f_e$（还能正向再加这么多）；
• 反向残余边：对每条 $e = (u, v) \in E$，若 $f_e > 0$，在 $E'$ 中加入反向边 $(v, u)$，容量 $c'_{e'} = f_e$（最多能把这么多流量退回去）。

反向边是整个构造的精髓。它代表「撤销」的能力：沿反向边「推送」流量，实际效果是抵消原边上已有的流量，等价于让那部分物资改道。有了反向边，前面的死局立刻解开——卡住后，残余图里出现了一条 $s \to b \to a \to t$ 的路径（其中 $b \to a$ 是 $a \to b$ 的反向残余边），沿它增广，就把误送到 $a \to b$ 的流量「掰」回了正轨。

Ford-Fulkerson 算法

把贪心搬到残余图上，就得到了求最大流的奠基性算法。残余图里的一条 $s$-$t$ 路径称为增广路径（Augmenting Path）——沿着它调整流量，总流量必然增加。

Ford-Fulkerson 算法

令 $\delta(P)$ 为残余图中路径 $P$ 的剩余容量。

当残余图 $G_f$ 中存在剩余容量 $\delta(P) > 0$ 的 $s$-$t$ 路径 $P$ 时：沿 $P$ 把流 $f$ 增广 $\delta(P)$。

「沿 $P$ 增广」的含义要对两类残余边区别对待：正向残余边对应的原边增加流量，反向残余边对应的原边减少流量。无论哪种，源点的净流出都恰好增加 $\delta(P)$。

算法的框架朴素到极致：不停找增广路径，找到就增广，直到残余图里再没有 $s$-$t$ 路径。剩下的问题有两个——它停下来时给出的真是最大流吗？它要花多久才停下来？第一个问题由下面的最大流最小割定理回答，第二个问题留到算法复杂度一节。

最大流最小割定理

割

要刻画「最大流何时达到上限」，需要引入它的对偶概念——割。

割

一个 $s$-$t$ 割（Cut）是顶点集的一个划分 $(S, \neg S)$，满足 $s \in S, t \in \neg S$。割的容量（Capacity）是所有从 $S$ 跨到 $\neg S$ 的边的容量之和：

$$\operatorname{cut}(S) = \sum_{\substack{a \in S,\, b \notin S \\ (a, b) \in E}} c_{a, b}$$

直观上，割就是把网络一刀切成「源点这边」和「汇点那边」，容量是切断所有「顺流」边所需的总代价。注意从 $\neg S$ 回到 $S$ 的「逆流」边不计入割容量——我们只关心切断顺流方向。

三个等价命题

下面这个定理是网络流理论的基石，它把「最大流」「无增广路径」「存在饱和割」三件事钉死在一起。

最大流最小割定理

对一个流网络中的流 $f$，以下三个命题等价：

1. $f$ 是最大流；
2. 残余图 $G_f$ 中不存在剩余容量 $> 0$ 的 $s$-$t$ 路径（即无增广路径）；
3. 存在一个割 $(S, \neg S)$ 使得 $\operatorname{cut}(S) = |f|$。

命题 (1) ⟺ (2) 保证了 Ford-Fulkerson 的正确性：当算法因「找不到增广路径」而停止时，得到的就是最大流。命题 (3) 则揭示了对偶——最大流的流量等于某个割的容量。再配上后面会证的「任意流 $\le$ 任意割」，立刻得到著名的结论：

最大流 = 最小割

$$\max_{f} |f| = \min_{S} \operatorname{cut}(S)$$

一张网络能通过的最大流量，等于切断它的最小割容量。

下面逐一证明三个蕴含，串成一个环 $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (1)$。

证明

$(1) \Rightarrow (2)$：用逆否命题 $\neg(2) \Rightarrow \neg(1)$。若残余图中存在剩余容量 $\delta(P) > 0$ 的增广路径，那么沿它增广能让流量增加 $\delta(P) > 0$，于是 $f$ 不是最大流。

$(2) \Rightarrow (3)$：设残余图中无增广路径。令 $S$ 为「在残余图 $G_f$ 中从 $s$ 出发可达的顶点集」。由于没有 $s$-$t$ 路径，$t \notin S$，所以 $(S, \neg S)$ 是一个合法的割。关键观察是这个割上的边都被「卡死」了：

• 对每条 $e = (a, b) \in E$ 且 $a \in S, b \notin S$（顺流边）：必有 $f_e = c_e$。否则 $c_e - f_e > 0$，残余图里就有正向边 $a \to b$，使 $b$ 也从 $s$ 可达，与 $b \notin S$ 矛盾。
• 对每条 $e = (b, a) \in E$ 且 $a \in S, b \notin S$（逆流边）：必有 $f_e = 0$。否则 $f_e > 0$，残余图里就有反向边 $a \to b$，同样使 $b$ 可达，矛盾。

也就是说，所有顺流边满载、所有逆流边空载。而 $|f|$（源点净流出）恰好等于穿过任何割的净流量——把 $S$ 中所有顶点的「流出 $-$ 流入」求和，$S$ 内部边的贡献一进一出相互抵消，除 $s$ 外其余顶点由守恒律贡献为零，剩下的恰是跨割的顺流减逆流。代入「满载/空载」：

$$|f| = \sum_{\substack{a \in S,\, b \notin S}} f_{a, b} - \sum_{\substack{a \in S,\, b \notin S}} f_{b, a} = \sum_{\substack{a \in S,\, b \notin S}} c_{a, b} - 0 = \operatorname{cut}(S)$$

$(3) \Rightarrow (1)$：先证一个更一般的事实——对任意流 $f$ 和任意割 $S$，都有 $|f| \le \operatorname{cut}(S)$（这就是「弱对偶」）。用流分解：把 $f$ 分解成若干 $s$-$t$ 路径（环对 $|f|$ 无贡献，丢掉）。每条携带 $p$ 单位流量的路径从 $s \in S$ 走到 $t \notin S$，至少要正向跨过割一次（即便来回穿越，正向次数也比逆向多一），每次正向跨越都占用 $\operatorname{cut}(S)$ 中 $p$ 的容量。所有路径占用的容量加起来不超过割容量，故

$$|f| = \sum_P p \le \operatorname{cut}(S)$$

有了这个上界，命题 (3) 的威力就显现了：若某个流 $f$ 与某个割 $S$ 满足 $|f| = \operatorname{cut}(S)$，那么任何流 $f'$ 都满足 $|f'| \le \operatorname{cut}(S) = |f|$，所以 $f$ 是最大流。$\blacksquare$

这个证明的副产品值得单独强调：任意流 $\le$ 任意割。最大流要往上顶，最小割要往下压，两者从两侧逼近同一个值并在最优处相遇。这种「最大化的下界由最小化提供、反之亦然」的夹逼结构，是对偶的本质，后面在线性规划里会以更一般的面貌再次登场。

让 Ford-Fulkerson 跑得更快

Ford-Fulkerson 保证了正确性，但「不停找增广路径」这句话留了个大坑：到底要找多少次？答案取决于怎么选增广路径——选得好与选得差，效率天差地别。这一节我们顺着「越选越聪明」的脉络，把求最大流的算法从「伪多项式」一路优化到「强多项式」。

朴素 Ford-Fulkerson：伪多项式的陷阱

最朴素的实现随便选一条增广路径。每次增广至少让整数容量下的流量增加 $1$，所以迭代次数不超过 $|f^*|$（最大流值），每次找路径 $O(m)$，总时间 $O(|f^*| \cdot m)$。

这看似多项式，实则暗藏杀机。考虑这样一张图：$s \to a$ 和 $s \to b$ 容量都是 $10^9$，$a \to t$ 和 $b \to t$ 容量也是 $10^9$，但中间有一条 $a \to b$ 容量为 $1$ 的细边。如果每次增广都「不幸」地经过那条细边——轮流走 $s \to a \to b \to t$ 与 $s \to b \to a \to t$（后者经过反向残余边 $b \to a$）——每次只能推 $1$ 单位流量，要 $2 \times 10^9$ 次才能灌满——尽管这张图只有 $4$ 个点、$5$ 条边。

伪多项式

$O(|f^*| \cdot m)$ 中的 $|f^*|$ 是流量的数值，而非输入规模。容量写成二进制只需 $O(\log |f^*|)$ 位，所以运行时间是输入规模的指数。这种「随数值大小线性、随输入位数指数」的复杂度称为伪多项式（Pseudo-polynomial）。当容量是无理数时，算法甚至可能永不停机。

病根在于「选路太随意」。下面三种策略，分别从「选粗路」「按位逼近」「选短路」三个角度根治这个问题。

策略一：总挑最粗的路（Fattest Path）

既然每次只推一点点太亏，那就每次都挑能推最多流量的路——剩余容量最大的增广路径，俗称「最肥的路」。

收敛速度

设当前流为 $f$、最大流为 $f^*$，记 $f' = f^* - f$（逐边相减，负值理解为反向流量）。可以验证 $f'$ 恰是残余图 $G_f$ 中一个流量为 $|f^*| - |f|$ 的合法流——它正是「还没补上的差额」。由流分解，$f'$ 至多拆成 $m$ 条路径，所以其中最肥的一条至少携带 $|f'| / m$ 的流量。沿它增广后，剩余差距至少缩小 $1/m$ 比例：

$$|f'| \le |f^*| \left(1 - \frac{1}{m}\right)^t \quad (\text{经过 } t \text{ 次迭代})$$

由 $(1 - 1/m)^t \le \e^{-t/m}$，要把差距从 $|f^*|$ 压到 $< 1$（整数容量下即等于补满），需要 $t = O(m \log |f^*|)$ 次迭代。直觉上，一条肥路被增广后会变「细」（瓶颈边饱和消失），后面的路只会越来越细——但每一步都啃掉剩余差距的至少 $1/m$，细得有节制。

怎么高效找到最肥的路？靠另一个简单观察：肥路径由肥边组成——瓶颈 $\ge W$ 的路径只会使用剩余容量 $\ge W$ 的边。于是可以二分阈值 $W$：删掉所有剩余容量 $< W$ 的边，用 BFS 判断 $s$ 能否到达 $t$，便知「肥度 $\ge W$ 的路」存不存在。单次查找 $O(m \log |f^*|)$。

最肥路策略把迭代次数降到了 $O(m \log |f^*|)$——对数级别，比朴素的 $|f^*|$ 大幅改善。但它仍依赖 $\log |f^*|$，属于弱多项式（Weakly-polynomial）：随输入位数多项式，但仍含容量数值的对数。而且面对无理容量，收敛性依旧没有保证。

策略二：按容量位数缩放（Scaling）

缩放法换了个思路：不追求一步到位，而是按二进制位从高到低逐步逼近。先只考虑「粗管道」，把大流量的骨架搭好，再逐步加入细管道修补。

容量缩放

对 $i = \lceil \log_2 C \rceil, \dots, 1, 0$（$C$ 为最大容量）逐轮进行。第 $i$ 轮只在「缩放残余图」$G_i$ 上增广，其中 $G_i$ 只保留剩余容量 $\ge 2^i$ 的边：

$$E'' \triangleq \{e \in E' : c'_e \ge 2^i\}$$

在这一轮里，每条增广路径都至少贡献 $2^i$ 的流量，而这一轮还差的流量有限，所以增广次数 $O(m)$。

为什么每轮增广次数 $\le m$？因为进入第 $i$ 轮时，上一轮（阈值 $2^{i+1}$）刚刚结束，$G_{i+1}$ 中已无 $s$-$t$ 路径。由最大流最小割定理的论证，此时残余图里存在一个割，其每条边的剩余容量都 $< 2^{i+1}$（否则那条边会留在 $G_{i+1}$ 里继续连通），于是残余的最大流 $< m \cdot 2^{i+1}$。本轮每次增广至少拿走 $2^i$，所以至多 $2m$ 次就把这一轮榨干。

总共 $O(\log C)$ 轮，每轮 $O(m)$ 次增广、每次 $O(m)$，总时间

$$O(\log_2 C \cdot m \cdot m) = O(m^2 \log C)$$

这同样是弱多项式（依赖容量的对数 $\log C$），但比最肥路更简洁稳健，是实践中常见的实现。

策略三：总挑最短的路（Edmonds-Karp / Dinitz）

最漂亮的思路来自一个反直觉的选择：不挑最肥的，挑最短的（边数最少的）增广路径。神奇之处在于——这样选，复杂度居然彻底摆脱了容量数值，变成强多项式（Strongly-polynomial，只依赖 $n, m$）。

把残余图按到 $s$ 的 BFS 距离分层，理解最短增广为什么有效：

• 前向边（Forth Edge）：连接相邻两层（距离差 $1$），最短路径只走这种边；
• 同层边（Side Edge）：连接同一层的两点；
• 回退边（Back Edge）：从远层指向近层；
• 跳跃边（Jumping Edge）：从近层跨到不相邻的远层。

最短路只增不减

沿最短增广路径增广时：

• 至少删掉一条前向边（瓶颈边饱和后从残余图消失）；
• 只可能新增回退边——增广只在前向边上推流量，新冒出来的残余边都是前向边的反向，恰好从第 $i+1$ 层指回第 $i$ 层；
• 绝不会新增跳跃边。

因此从 $s$ 到 $t$ 的最短距离单调不减：想变短就得靠跳跃边「抄近道」，而跳跃边永远不会被造出来。

有了这个单调性，复杂度就好数了：最短距离取值范围是 $1, \dots, n$；对每个固定的距离值，最多增广 $m$ 次（每次至少删一条前向边，前向边不超过 $m$ 条）就会迫使距离增大。所以总增广次数 $O(nm)$，每次 BFS 找路 $O(m)$：

$$O(nm) \times O(m) = O(m^2 n)$$

这就是 Edmonds-Karp 算法。

Dinitz 的改进：一次性榨干一层

Edmonds-Karp 每找到一条最短路就增广一次，太浪费了——同一个距离值下其实可以一口气把所有最短路径都增广掉。这就是 Dinitz 算法（也写作 Dinic）的核心。

阻塞流

在一个固定最短距离下，只保留前向边构成分层图，在其上用一次 DFS 找出一个阻塞流（Blocking Flow）——一组增广，使得每条 $s$-$t$ 最短路上至少有一条边被饱和。这相当于把当前距离下所有最短路径一次性增广完毕。

每个「阶段」（一个固定的最短距离）用一次 DFS 构造阻塞流，耗时 $O(nm)$^[1]；由最短距离单调不减且取值 $1, \dots, n$，共 $O(n)$ 个阶段：

$$O(n) \times O(nm) = O(n^2 m)$$

由于通常 $m \ge n$，Dinitz 的 $O(n^2 m)$ 优于 Edmonds-Karp 的 $O(m^2 n)$。

算法全景

把这一节的成果汇成一张表——同一个 Ford-Fulkerson 框架，仅仅因为「怎么选增广路径」的不同，复杂度就跨越了三个量级：

算法	策略	时间复杂度	类型
Ford-Fulkerson	任意增广路径	$O(\lvert f^* \rvert \cdot m)$	伪多项式
最肥路径	最大瓶颈增广	$O(m^2 \log^2 \lvert f^* \rvert)$	弱多项式
容量缩放	按位缩放	$O(m^2 \log C)$	弱多项式
Edmonds-Karp	最短增广路径	$O(m^2 n)$	强多项式
Dinitz	阻塞流	$O(n^2 m)$	强多项式

三种「多项式」

• 伪多项式：随数值大小多项式，随输入位数指数（如 $|f^*|$）。
• 弱多项式：随输入位数多项式，但仍含数值的对数（如 $\log C$）。
• 强多项式：只依赖输入中「数的个数」$n, m$，与数值大小完全无关。

这条优化之路的终点——强多项式——正是算法理论追求的理想形态：无论容量是 $1$ 还是 $10^{100}$，运行时间纹丝不动。

最大流的应用

最大流的真正威力，在于它是一台「归约机器」：许多看似与流毫无关系的问题，只要巧妙地构造一张网络，就能转化为求最大流。这一节看几个经典归约。

多源多汇

最直接的推广是允许多个源点和多个汇点。

多源多汇最大流

给定网络 $G = (V, E)$、容量 $c$，一组源点 $S = \{s_1, \dots, s_k\}$ 和一组汇点 $T = \{t_1, \dots, t_\ell\}$，求从 $S$ 整体到 $T$ 整体的最大流。

归约只需一个小技巧：添加一个超级源点 $s^*$，从它向每个 $s_i$ 连一条容量为 $\infty$ 的边；再添加一个超级汇点 $t^*$，从每个 $t_j$ 向它连一条容量为 $\infty$ 的边。在新图上求单源单汇的 $s^*$-$t^*$ 最大流，就是原问题的答案。无穷容量的连接边保证它们永不成为瓶颈。

二部图最大匹配

这是最优美的归约之一。回忆第一讲，我们曾用 Edmonds 矩阵和随机化来判定二部图是否存在完美匹配；现在用最大流，我们能直接求出最大匹配。

二部图最大匹配

二部图（Bipartite Graph）$G = (L \cup R, E)$ 的顶点可分成左右两部 $L, R$，每条边都连接一个左点和一个右点。匹配（Matching）$M \subseteq E$ 是一组边，使得每个顶点至多被一条边覆盖；若每个顶点都恰好被覆盖，则称完美匹配（Perfect Matching）。最大匹配就是边数最多的匹配。

把匹配问题「流化」的构造：

• 加源点 $s$，从 $s$ 向每个左点 $u \in L$ 连边，容量 $1$；
• 每条原边 $(u, v) \in E$（$u \in L, v \in R$）保留，方向 $u \to v$，容量 $1$；
• 加汇点 $t$，从每个右点 $v \in R$ 向 $t$ 连边，容量 $1$。

所有容量都是 $1$，这是关键——它逼着每个顶点至多「参与」一条边。

匹配 ⟺ 流

最大匹配的大小 = 这张网络的最大流值，且二者可以互相转换：

• 匹配 $\Rightarrow$ 流：给定匹配 $M$，对每条 $(u, v) \in M$ 令 $f_{su} = f_{uv} = f_{vt} = 1$，其余为 $0$。这是合法流，且 $|f| = |M|$。
• 流 $\Rightarrow$ 匹配：给定整数流 $f$，令 $M = \{(u, v) \in E : u \in L, v \in R, f_{uv} > 0\}$。由容量 $1$ 约束，每个 $u \in L$ 至多流出 $1$、每个 $v \in R$ 至多流入 $1$，所以 $M$ 是匹配，且 $|M| = |f|$。

这里有一个需要补的细节：流可能是分数的，但匹配要求整数。所幸最大流问题有整性定理——当所有容量为整数时，Ford-Fulkerson 全程只做整数加减，必然给出整数最大流。所以求出的流自动是 $0/1$ 的，可以干净地翻译回匹配。

边不相交路径与最小割

容量为 $1$ 的网络还能刻画「路径的独立性」。

最大边不相交路径

给定有向图 $G = (V, E)$ 和源汇 $s, t$，求从 $s$ 到 $t$ 的最多条边不相交（Edge-disjoint）路径。

把每条边容量设为 $1$，求 $s$-$t$ 最大流，流量就是最多的边不相交路径数——因为每条边容量 $1$ 意味着它至多被一条路径使用，而整数流又能按流分解定理拆成这么多条路径。

而最大流最小割定理在这里化身为图论里著名的 Menger 定理：$s$ 到 $t$ 的最大边不相交路径数，等于「要切断 $s, t$ 之间所有连接，最少需删除的边数」（每条边权 $1$ 时的最小割）。

最小割问题

• $s$-$t$ 最小割：给定带权有向图和源汇 $s, t$，求容量最小的、删除后能切断 $s, t$ 的割。由最大流最小割定理，它等于最大流，可直接求解。
• 全局最小割（Global Min-Cut）：不指定源汇，求删除后能让整张图断开的最小割。可以固定一个点为 $s$，枚举其余每个点 $t$，分别求 $s$-$t$ 与 $t$-$s$ 两个方向的最小割（全局割必把 $s$ 和某个 $t$ 分开，但谁在源侧未知），取所有结果的最小值——共 $2(n - 1)$ 次最大流计算。

最小费用流

现实中，运输不仅有容量限制，还有成本：同样把货送到，走高速要过路费，走小路则免费但慢。我们想在「送得最多」的前提下「花得最少」。

最小费用流问题

最小费用流问题（Minimum-Cost Flow Problem, MCFP）：每条边 $e$ 除容量 $c_e$ 外，还有单位流量费用 $a_e \in \R^+$。在所有最大流当中，找一个使总费用最小的：

$$\min \sum_{e \in E} a_e \cdot f(e) \quad \text{s.t. } \sum_{e \in \delta^{\text{out}}(s)} f(e) \text{ 达到最大}$$

它的一个著名特例是指派问题（Assignment Problem）：把 $n$ 个工人指派给 $n$ 项任务，每个「工人-任务」配对有一个成本，求总成本最小的完美匹配——正是「最小费用完美匹配」。

怎么求最小费用流？思路依然是「改进当前解」，但改进的目标从「流量」换成了「费用」。一个已经达到最大流量的解，若还想降低费用，唯一的办法是重新分配流量：在某条路径上少送一点、在另一条更便宜的路径上多送一点，保持总流量不变。这样一次「此消彼长」的重分配，在残余图里恰好对应一个环——一部分流量退回（沿反向边），一部分流量新增（沿正向边）。

消圈算法

一次重分配能降低费用，当且仅当它对应残余图中一个负费用环（费用之和为负的环，反向边的费用取相反数）。于是算法朴素得惊人：

当残余图中存在负费用环时，沿该环重分配流量，消去这个负环。

没有负费用环时，当前流就是最小费用流。这就是消圈算法（Cycle Canceling）。

负环的判定可用 Bellman-Ford 完成。消圈算法的正确性源于一个漂亮的事实：一个最大流是最小费用的，当且仅当它的残余图中不含负费用环——与「最大流 ⟺ 无增广路径」如出一辙，都是「局部最优 ⟺ 全局最优」的体现。

一个理论注脚：最大流是 P-完全的

最后一个值得知道的事实：在对数空间归约下，最大流问题是 P-完全的（P-complete）。

这意味着什么？P-完全问题是 P 类中「最难并行化」的代表——如果最大流能被高效并行（落入 NC 类），那么整个 P 类都能高效并行，而这被广泛认为不太可能。换句话说，最大流大概率是「本质串行」的：增广路径一条接一条，难以拆成大量独立的并行子任务。这与它「易于串行求解」（多项式时间）并不矛盾——多项式时间说的是串行效率，P-完全说的是并行困难。

至此，网络流的故事告一段落。我们见识了一个具体优化问题的完整生命周期：定义、求解、加速、应用，以及贯穿始终的「流-割对偶」。接下来，我们要把视野从网络流拉高到一个更宏大的框架——它能把网络流、匹配乃至无数优化问题都收纳其中。

从网络流到线性规划

一个似曾相识的问题

先看一个中学就见过的优化问题：

$$\begin{aligned} \text{minimize} \quad & 7x_1 + 4x_2 \\ \text{subject to} \quad & x_1 + x_2 \ge 5 \\ & x_1 + 2x_2 \ge 6 \\ & 4x_1 + x_2 \ge 8 \\ & x_1, x_2 \ge 0 \end{aligned}$$

目标函数是变量的线性组合，约束也都是线性不等式。这类问题——线性的目标 + 线性的约束——就是线性规划。上面这个例子的最优解是 $x_1 = 1, x_2 = 4$，最优值 $7 \times 1 + 4 \times 4 = 23$。

线性规划的几何图像很美：每个不等式约束划出一个半平面，所有约束的交集是一个多边形（高维下是多面体）的可行区域；目标函数 $7x_1 + 4x_2 = \text{常数}$ 是一族平行线，我们沿着它的下降方向推进，直到「触碰」可行区域的边界——最优解总在某个顶点上取得。这个「最优解在顶点」的现象，是后面所有算法的基石。

最大流其实是线性规划

为什么在讲完网络流后突然转向线性规划？因为最大流本身就是一个线性规划。把流的每条边流量 $f_{uv}$ 当作变量，最大流问题写出来是：

$$\begin{aligned} \text{maximize} \quad & \sum_{u : (s, u) \in E} f_{su} \\ \text{subject to} \quad & 0 \le f_{uv} \le c_{uv} & \forall (u, v) \in E \\ & \sum_{w : (w, u) \in E} f_{wu} - \sum_{v : (u, v) \in E} f_{uv} = 0 & \forall u \in V \setminus \{s, t\} \end{aligned}$$

目标（最大化源点流出）是线性的，容量约束和守恒约束也都是线性的——这就是一个不折不扣的线性规划。这个观察有深远意义：网络流的所有结构（包括最大流最小割对偶）都是线性规划一般理论的特例。当我们后面建立起线性规划的对偶理论，会发现「最大流 = 最小割」不过是「线性规划强对偶定理」的一个具体实例。

线性规划的统一能力远不止于此。匹配、最短路、覆盖、调度、运输、网络设计……数不清的优化问题都能写成线性规划。掌握它，就掌握了一把能撬动整个组合优化领域的杠杆。

线性规划的三种形式

要研究线性规划，先要把五花八门的写法统一起来。同一个线性规划可以有多种等价形式，互相之间可以机械地转换。

一般形式

最一般的线性规划允许等式约束、不等式约束、有界变量、自由变量混杂：

线性规划（一般形式）

给定矩阵 $\bm{A} = \{a_{ij}\}_{[m] \times [n]}$，下标子集 $M \subseteq [m], N \subseteq [n]$：

$$\begin{aligned} \text{minimize} \quad & \bm{c}^{\intercal} \bm{x} \\ \text{subject to} \quad & \bm{a}_i^{\intercal} \bm{x} = b_i & i \in M \\ & \bm{a}_i^{\intercal} \bm{x} \ge b_i & i \notin M \\ & x_j \ge 0 & j \in N \\ & x_j \text{ 无约束} & j \notin N \end{aligned}$$

这里 $\bm{a}_i^{\intercal}$ 是 $\bm{A}$ 的第 $i$ 行。一般形式表达力最强，但太杂乱不便分析。我们把它整理成两种更规整的标准写法。

规范形式与标准形式

规范形式与标准形式

规范形式（Canonical Form）：只有 $\ge$ 不等式约束，所有变量非负。

$$\min \bm{c}^{\intercal} \bm{x} \quad \text{s.t. } \bm{A}\bm{x} \ge \bm{b},\ \bm{x} \ge \bm{0}$$

标准形式（Standard Form）：只有 $=$ 等式约束，所有变量非负。

$$\min \bm{c}^{\intercal} \bm{x} \quad \text{s.t. } \bm{A}\bm{x} = \bm{b},\ \bm{x} \ge \bm{0}$$

两种形式各有用处：规范形式（不等式）便于讨论几何与对偶，标准形式（等式）便于代数操作与单纯形法。任意线性规划都能转成它们，靠的是几个小变换。

一般形式 $\to$ 规范形式：

• 等式 $\bm{a}_i^{\intercal} \bm{x} = b_i$ 拆成两个不等式 $\bm{a}_i^{\intercal} \bm{x} \ge b_i$ 与 $-\bm{a}_i^{\intercal} \bm{x} \ge -b_i$；
• 自由变量 $x_j$（无符号约束）写成两个非负变量之差 $x_j = x_j^+ - x_j^-$，其中 $x_j^+, x_j^- \ge 0$；
• 最大化 $\bm{c}^{\intercal}\bm{x}$ 等于最小化 $-\bm{c}^{\intercal}\bm{x}$，$\le$ 约束两边取负变 $\ge$。

规范形式 $\to$ 标准形式：每个不等式 $\bm{a}_i^{\intercal} \bm{x} \ge b_i$ 引入一个非负的松弛变量（Slack Variable）$s_i \ge 0$，把「超出 $b_i$ 的部分」装进 $s_i$，写成等式 $\bm{a}_i^{\intercal} \bm{x} - s_i = b_i$（若约束是 $\le$，则改为 $+ s_i$）。在矩阵层面，这相当于把约束矩阵 $\bm{A}$ 扩成 $\bm{A}' = [\bm{A} \mid -\bm{I}]$（追加的那一块对应松弛变量）。

形式之间可以自由穿梭

三种形式互相等价、可机械转换。证明定理时挑最顺手的那个用就行——讲几何用规范形式，讲单纯形用标准形式。下面默认线性规划都能在多项式时间内求解（具体算法稍后介绍），先来理解它的几何结构。

线性规划的几何

线性规划「最优解在顶点」的直觉需要严格的几何语言来支撑。这一节建立可行域的几何图像：它是一个由半空间相交而成的「多面体」，而最优解总能在它的「角」上找到。先看本讲开头那个例子的可行域长什么样：

三条 $\ge$ 约束各划出一个半平面，交集（蓝色区域）就是可行域；目标函数 $7x_1 + 4x_2 = \text{常数}$ 是一族平行虚线，沿下降方向推到底，恰好顶在可行域左下角的顶点 $(1, 4)$ 上——这正是「最优在顶点」的具象。下面把这套直觉精确化。

凸多面体

先从凸性这个基本概念说起。

凸集与凸包

集合 $S \subseteq \R^n$ 是凸集（Convex Set），若 $\forall \bm{x}, \bm{y} \in S$ 及 $\lambda \in [0, 1]$，都有 $\lambda \bm{x} + (1 - \lambda) \bm{y} \in S$——任意两点连线段整段都在集合内。紧致（有界闭）的凸集称为凸体（Convex Body）。集合 $S$ 的凸包（Convex Hull）是包含它的最小凸集。

线性规划的可行域是由一组线性不等式（每个划出一个「半空间」）交出来的，这种集合有专门的名字。

超平面、半空间与多面体

• 超平面（Hyperplane）：$n$ 维空间中维度为 $n - 1$ 的子空间 $\left\{\bm{x} : \sum_{j=1}^n a_j x_j = b\right\}$；
• （闭仿射）半空间（Halfspace）：超平面的一侧 $\left\{\bm{x} : \sum_{j=1}^n a_j x_j \ge b\right\}$；
• 凸多面体（Convex Polyhedron）：有限多个半空间的交集 $\{\bm{x} : \bm{A}\bm{x} \ge \bm{b}\}$；
• 凸多胞形（Convex Polytope）：有界的凸多面体（等价地，有限个点的凸包）。

规范形式线性规划的可行域 $\{\bm{x} : \bm{A}\bm{x} \ge \bm{b},\ \bm{x} \ge \bm{0}\}$ 正是一个凸多面体。多面体可能无界（伸向无穷远），多胞形则是有界的「有限块」。

顶点与极点

多面体的「角」有两种看似不同、实则等价的定义方式：一种从优化角度（顶点），一种从几何角度（极点）。

顶点与极点

设 $P = \{\bm{x} \in \R^n : \bm{A}\bm{x} \ge \bm{b}\}$ 是凸多面体。

• 顶点（Vertex）：点 $\bm{x} \in P$ 是顶点，若存在某个方向 $\bm{c} \in \R^n$，使 $\bm{x}$ 是 $P$ 上唯一最小化 $\bm{c}^{\intercal} \bm{y}$ 的点（即 $\bm{c}^{\intercal}\bm{x} < \bm{c}^{\intercal}\bm{y}$ 对所有 $\bm{y} \ne \bm{x}$ 成立）。直观说：存在某个线性目标，它在 $P$ 上的唯一最优点就是 $\bm{x}$。
• 极点（Extreme Point）：点 $\bm{x} \in P$ 是极点，若它不能表示成 $P$ 中其他两点 $\bm{y}, \bm{z}$ 的凸组合。直观说：$\bm{x}$ 不在任何线段的「内部」。

多胞形的五个角都既是顶点又是极点；而上边中点（红色方块）能写成相邻两顶点的凸组合，所以不是极点。这两种「角」的刻画殊途同归，再加上关于「最优解落在哪」的结论，构成三个奠基命题。

三个关键命题

1. 顶点存在性：凸多面体 $P$ 有顶点，当且仅当它不包含任何整条直线（不存在 $\bm{x}, \bm{y}$ 且 $\bm{y} \ne \bm{0}$，使 $\bm{x} + \lambda \bm{y} \in P$ 对所有 $\lambda \in \R$ 成立）。
2. 顶点 = 极点：对非空凸多面体 $P$ 与任意 $\bm{x} \in P$，$\bm{x}$ 是顶点 $\iff$ $\bm{x}$ 是极点。
3. 顶点是最优解：若可行域 $\{\bm{x} : \bm{A}\bm{x} \ge \bm{b}\}$ 有顶点，且线性规划 $\min\{\bm{c}^{\intercal}\bm{x} : \bm{A}\bm{x} \ge \bm{b}\}$ 有最优解，则存在一个最优解是顶点。

命题 3 是整个单纯形法的理论支柱：要找最优解，不必在整个连续的可行域里大海捞针，只需在有限多个顶点中搜索。直觉上，线性目标函数沿某方向单调，把它推到底，最优值必然顶在可行域的「角」上——除非目标方向恰好与某条边平行，但那种情况下那条边的端点（仍是顶点）也是最优的。

基本可行解

顶点是几何概念，但算法需要代数的抓手。在标准形式下，顶点有一个纯代数的等价描述——基本可行解。

把标准形式 $\min\{\bm{c}^{\intercal}\bm{x} : \bm{A}\bm{x} = \bm{b},\ \bm{x} \ge \bm{0}\}$ 不失一般性地假设 $\bm{A} \in \R^{m \times n}$ 行满秩，$m = \operatorname{rank}(\bm{A}) \le n$。

基本可行解

• 基（Basis）$B \subseteq [n]$：$\bm{A}$ 的 $m$ 个线性无关的列构成的下标集；
• 基本解（Basic Solution）：令非基变量 $x_{[n] \setminus B} = 0$，再解 $\bm{A}_{[m] \times B}\, \bm{x}_B = \bm{b}$ 得到的 $\bm{x}$（满足 $\bm{A}\bm{x} = \bm{b}$，但未必 $\ge 0$）；
• 基本可行解（Basic Feasible Solution, bfs）：满足 $\bm{x} \ge \bm{0}$ 的基本解。注意这个小写缩写 bfs 与图搜索的 BFS（宽度优先搜索）无关。

代数与几何在这里完美对接：

bfs = 顶点

$\bm{x}$ 是线性规划 $\min\{\bm{c}^{\intercal}\bm{x} : \bm{A}\bm{x} = \bm{b} \wedge \bm{x} \ge \bm{0}\}$ 的基本可行解，当且仅当 $\bm{x}$ 是多面体 $\{\bm{x} : \bm{A}\bm{x} = \bm{b} \wedge \bm{x} \ge \bm{0}\}$ 的顶点。

这座桥让算法得以「计算」顶点：每选定一组基 $B$（$m$ 个线性无关的列），就唯一确定一个基本解；若它非负，就是一个顶点。顶点的总数是有限的（至多 $\binom{n}{m}$ 种选基方式），于是「在顶点中搜索最优」成了一件可以编程实现的事。

单纯形法与求解器

单纯形法

有了「最优解在顶点」与「顶点 = bfs」，求解线性规划的第一个算法呼之欲出：从一个顶点出发，沿着多面体的棱不断走向更好的相邻顶点，直到无路可走。

单纯形法（Dantzig 1947）

称两个 bfs 为相邻（Neighbor），若它们的基共享 $m - 1$ 个列（即只差一个基变量——几何上对应多面体的一条棱相连的两个顶点）。单纯形法（Simplex Method）：

从某个 bfs $\bm{x}$ 出发；
当存在相邻 bfs $\bm{x}'$ 使 $\bm{c}^{\intercal}\bm{x}' < \bm{c}^{\intercal}\bm{x}$ 时，移动到这样的 $\bm{x}'$。

单纯形法本质是「沿棱下山」的局部搜索：从某个 bfs 出发，每次挪到目标值更小的相邻顶点，直到无路可走。

它为什么能找到全局最优？因为线性规划是凸优化：

局部最优即全局最优

可行域是凸集、目标函数是线性（从而是凸）函数，所以任何局部最优自动是全局最优。单纯形法停在一个「所有邻居都不更优」的顶点，这个顶点就是全局最优解。

凸性是这里的关键魔法。在非凸问题里，局部搜索会困在山谷中的次优解；但凸性抹平了所有「假谷底」，让简单的爬山法直达真正的最优。

单纯形法的复杂度与其他求解器

单纯形法在实践中极快，但它有一个理论上的尴尬：

单纯形法的最坏情况是指数的

Klee-Minty（1972）构造了一个「扭曲的立方体」，让单纯形法被迫访问几乎所有 $2^n$ 个顶点才到达最优——最坏情况指数时间。不过 Spielman-Teng（2001）证明它的平滑复杂度（Smoothed Complexity）是多项式的：对输入做微小随机扰动后，期望运行时间是多项式。这解释了「最坏情况指数、实践中飞快」的反差。

那么线性规划到底能不能保证多项式时间求解？能——但要靠另外两类算法。

椭球法（Khachiyan 1979）

椭球法（Ellipsoid Method）维护一个包含可行域的椭球，每步用一个超平面把椭球切成两半，找一个更小的椭球罩住「正确的那一半」，不断收缩，直到锁定可行点。它首次证明了线性规划属于 $\mathsf{P}$，运行时间 $O(n^6)$。理论意义重大，但常数大、实践中慢。

内点法（Karmarkar 1984）

内点法（Interior-Point Method）让解始终待在多面体内部，用一个「障碍惩罚函数」阻止它过早贴到边界上，沿内部的「中心路径」滑向最优，最终任意逼近最优解。Karmarkar 开创此路线后，Vaidya（1989）将运行时间改进到 $O(n^{2.5})$，且实践中可与单纯形法竞争；近年更做到了「当前矩阵乘法时间」的突破（Cohen-Lee-Song 2019；Jiang-Song-Weinstein-Zhang 2021）。

这两类算法的对比，连同单纯形法一起汇成下表——它们走的「路线」截然不同：单纯形法沿边界的顶点跳，椭球法和内点法则一个从外包夹、一个从内部逼近。

求解器	最坏复杂度	特点
单纯形法	指数（平滑多项式）	实践极快，沿顶点游走
椭球法	$O(n^6)$	首个多项式算法，理论价值大
内点法	$O(n^{2.5})$（Vaidya）	多项式且实践快，沿内部路径

线性规划的研究方向

围绕线性规划的算法研究不止「解得更快」一条线：除了多项式时间精确算法，还包括多项式时间近似算法、把线性规划作为整数规划分支定界（Branch-and-Bound）法的子程序，以及在线算法、分布式算法、动态算法、快速算法等其他计算模型下的线性规划求解。

把线性规划当黑箱

本讲后半部分只需记住一个事实：线性规划可以在多项式时间内求解。具体用哪种求解器无关紧要——我们要把它当成一个现成的「优化引擎」，去攻克那些本来很难的组合问题。

线性规划的应用横跨计算机科学、数学、运筹学、经济学，涵盖运输、调度、聚类、网络路由、资源分配、设施选址等问题。而它在算法设计中最迷人的用法，是作为攻克 NP-难问题的跳板——这正是下一节的主题。

线性规划松弛与舍入

顶点覆盖问题

我们用一个经典的 NP-难^[2]问题作主角：顶点覆盖。

顶点覆盖

给定无向图 $G = (V, E)$，找最小的顶点集 $C \subseteq V$，使每条边都至少有一个端点在 $C$ 中（即 $C$ 「覆盖」了所有边）。

顶点覆盖是经典的 NP-难问题。它其实是集合覆盖（Set Cover）的一个特例：把每个顶点看作一个「集合」，包含与它相邻的边——由于每条边恰有两个端点，每个元素（边）恰好出现在两个集合里，即「频率为 $2$」的集合覆盖。已知的结果勾勒出它的近似难度地图：

• 用贪心的集合覆盖算法可得 $\ln n$ 近似；
• 有一个漂亮的 $2$-近似算法：求一个极大匹配（Maximal Matching，即不能再添加任何边的匹配——注意它不同于边数最多的「最大」匹配，极大的不一定最大），输出所有被匹配的顶点；
• Khot-Regev（2008）证明：假设唯一博弈猜想（Unique Games Conjecture, UGC）成立，不存在多项式时间的 $(2 - \epsilon)$-近似算法。

近似比

一个最小化问题的算法是 $\alpha$-近似（$\alpha \ge 1$），若它的输出 $\text{SOL}$ 总满足 $\text{SOL} \le \alpha \cdot \text{OPT}$。$\alpha$ 越接近 $1$ 越好。$2$-近似就是「保证不超过最优解的两倍」。在 UGC 下，顶点覆盖的 $2$ 是一道无法逾越的墙——这让能达到 $2$ 的算法显得尤为珍贵。

下面我们用线性规划重新得到这个 $2$-近似，方法极具一般性，能推广到大量其他问题。

整数规划与它的松弛

第一步是把组合问题写成整数线性规划（Integer Linear Program, ILP）——和线性规划一样，但变量被限制为整数。

顶点覆盖的整数规划

为每个顶点 $v$ 设一个 $0/1$ 变量 $x_v$（$x_v = 1$ 表示选入 $C$）：

$$\begin{aligned} \text{minimize} \quad & \sum_{v \in V} x_v & \text{(线性目标)} \\ \text{subject to} \quad & \sum_{v \in e} x_v \ge 1 & \forall e \in E \quad \text{(线性约束)} \\ & x_v \in \{0, 1\} & \forall v \in V \quad \text{(整数域)} \end{aligned}$$

约束 $\sum_{v \in e} x_v \ge 1$ 是说每条边 $e = (u, w)$ 至少选一个端点（$x_u + x_w \ge 1$）。

这个整数规划精确刻画了顶点覆盖——但 $x_v \in \{0, 1\}$ 这个整数约束让它变得 NP-难。整数规划求解是 NP-难的，所以我们不能直接解它。

关键的一步叫松弛：把碍事的整数约束 $x_v \in \{0, 1\}$ 放宽成连续区间 $x_v \in [0, 1]$。

线性规划松弛

$$\begin{aligned} \text{minimize} \quad & \sum_{v \in V} x_v \\ \text{subject to} \quad & \sum_{v \in e} x_v \ge 1 && \forall e \in E \\ & x_v \in [0, 1] && \forall v \in V \quad \text{(分数域)} \end{aligned}$$

把整数域 $\{0, 1\}$ 换成连续域 $[0, 1]$ 后，问题从 NP-难的整数规划变成了多项式时间可解的线性规划。代价是：解出来的 $x_v^*$ 可能是分数（比如三角形的三个顶点各取 $1/2$），不再是一个真正的顶点覆盖。把分数解「变回」整数解，就是舍入。

松弛与舍入

线性规划松弛与舍入

1. 求线性规划松弛的最优解 $\bm{x}^* \in [0, 1]^V$；
2. 把 $\bm{x}^*$ 舍入成整数解 $\hat{\bm{x}} \in \{0, 1\}^V$：

   $$\hat{x}_v = \begin{cases} 1 & x_v^* \ge 0.5 \\ 0 & \text{否则} \end{cases}$$

阈值 $0.5$ 是精心选的，下面的分析会揭示它的来历。

舍入后要回答两个问题：得到的 $\hat{\bm{x}}$ 真的是顶点覆盖吗（可行性）？它离最优有多远（近似比）？

可行性：对任意边 $e = (u, w)$，松弛约束 $x_u^* + x_w^* \ge 1$ 保证两者中至少一个 $\ge 0.5$（否则和 $< 1$）。那个 $\ge 0.5$ 的变量被舍入为 $1$，于是 $\hat{x}_u + \hat{x}_w \ge 1$——边 $e$ 被覆盖。所以 $\hat{\bm{x}}$ 是合法的顶点覆盖。这正是阈值取 $0.5$ 的原因：它恰好能保证每条边的约束在舍入后不被破坏。

近似比：舍入规则有个关键性质——$\hat{x}_v \le 2 x_v^*$。因为 $\hat{x}_v = 1$ 时必有 $x_v^* \ge 0.5$，故 $2x_v^* \ge 1 = \hat{x}_v$；$\hat{x}_v = 0$ 时不等式平凡成立。于是

$$\text{SOL} = \sum_{v \in V} \hat{x}_v \le 2 \sum_{v \in V} x_v^* = 2 \cdot \text{OPT}_{\text{LP}}$$

再用一个核心不等式把松弛最优值与真实最优值联系起来：

松弛是真实问题的下界

$$\text{OPT} = \text{OPT}_{\text{Int}} \ge \text{OPT}_{\text{LP}}$$

线性规划松弛的可行域包含整数规划的可行域（$\{0, 1\} \subset [0, 1]$），在更大的范围上最小化，最优值只会更小或相等。所以松弛的最优值是原问题最优值的下界。

把两步串起来：

$$\text{SOL} \le 2 \cdot \text{OPT}_{\text{LP}} \le 2 \cdot \text{OPT}$$

这就证明了线性规划松弛舍入是顶点覆盖的 $2$-近似算法。

通用范式

刚才的过程不是顶点覆盖独有的，而是一套适用于海量 NP-难问题的通用范式：

flowchart LR
    A["原问题<br/>（NP-难组合优化）"] --> B["建模<br/>写成整数规划 ILP"]
    B --> C["松弛<br/>整数域 → 分数域"]
    C --> D["求解<br/>多项式时间解 LP"]
    D --> E["舍入<br/>分数解 → 整数解"]
    E --> F["分析<br/>证明 SOL ≤ α·OPT"]

    classDef problem fill:#ffebee,stroke:#c62828,stroke-width:2px
    classDef model fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef solve fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef analyze fill:#fff3e0,stroke:#ef6c00,stroke-width:2px

    class A problem
    class B,C model
    class D,E solve
    class F analyze

• 建模：把优化问题写成整数线性规划；
• 松弛：放宽整数约束，得到线性规划；
• 求解：用高效线性规划求解器找松弛最优解；
• 舍入：把分数最优解舍入成可行的整数解；
• 分析：证明舍入解与最优解相差不远（通常拿松弛最优值作下界来比较）。

这套范式的精髓是：用一个能在多项式时间解出的「松弛版本」当跳板，借它的最优值作标尺，再把它的解小心地「圆整」回合法的整数解。

整性间隙

松弛舍入法能做到多好，有一个内在的极限——它取决于「松弛」这一步丢失了多少信息。这个损失由整性间隙度量。

整性间隙

一个整数规划与其线性规划松弛之间的整性间隙（Integrality Gap）是二者最优值之比在所有实例上的最坏值：

$$\text{整性间隙} = \sup_{I} \frac{\text{OPT}(I)}{\text{OPT}_{\text{LP}}(I)}$$

（最小化问题中此比值 $\ge 1$；最大化问题习惯上取 $\text{OPT} / \text{OPT}_{\text{LP}} \le 1$，越接近 $1$ 松弛越「忠实」。）

整性间隙刻画了松弛的「先天质量」。它有两层含义：

• 我们的 $2$-近似分析证明了顶点覆盖的整性间隙 $\le 2$——因为我们构造出了一个不超过 $2 \cdot \text{OPT}_{\text{LP}}$ 的整数解。
• 反过来，存在实例使比值逼近 $2$：取 $n$ 个顶点的完全图 $K_n$，每个 $x_v = 1/2$ 是松弛可行解，$\text{OPT}_{\text{LP}} = n/2$；但任何顶点覆盖必须留下至多一个点不选（否则有边没覆盖），$\text{OPT} = n - 1$。比值 $\frac{n-1}{n/2} \to 2$。

最小的非平凡情形 $K_3$（三角形）就能看清这个「分数解占便宜」的机理：

所以顶点覆盖线性规划松弛的整性间隙恰好等于 $2$。

整性间隙是松弛方法的天花板

整性间隙是这个特定线性规划松弛能达到的近似比下限——只要算法的分析是「拿松弛最优值作下界」，就不可能做得比整性间隙更好。要突破它，必须换更强的松弛（如半定规划）或全新的方法。

Singh（2019）给出了更精细的刻画：在图 $G$ 上整性间隙为 $2 - \frac{2}{\chi^f(G)}$，其中 $\chi^f(G)$ 是 $G$ 的分数色数。图越「稠密复杂」（分数色数越大），间隙越逼近 $2$。

整性间隙提醒我们：松弛舍入虽强大，但有先天局限。接下来的 Max-SAT 会展示更精巧的舍入技巧，把整性间隙「榨」到极致。

Max-SAT：舍入技巧的博物馆

Max-SAT 是展示「随机化舍入」威力的绝佳舞台。我们会看到四种逐步进化的算法：从最朴素的随机赋值，到线性规划舍入，再到两者的巧妙组合，最后是一个把组合的优势浓缩进单一算法的非线性舍入。

Max-SAT

给定一个合取范式（Conjunctive Normal Form, CNF）公式 $\Phi = C_1 \wedge C_2 \wedge \dots \wedge C_m$，找一个布尔赋值 $\bm{x} \in \{\texttt{T}, \texttt{F}\}^n$，使被满足的子句数最多。

• CNF：若干子句（Clause）的合取（$\wedge$）；
• 子句：若干文字（Literal）的析取（$\vee$），如 $C = (x_1 \vee \neg x_2 \vee x_3)$；
• 文字：一个变量 $x_i$ 或其否定 $\neg x_i$。

Max-SAT 是 NP-难的。

记子句 $C_j$ 含 $k_j$ 个文字。下面所有算法的目标，都是让满足子句数的期望尽可能接近最优值 $\text{OPT}$。

算法一：纯随机赋值

最朴素的想法：抛硬币。每个变量 $x_i$ 独立均匀地取 $\texttt{T}$ 或 $\texttt{F}$。

子句 $C_j = (\ell_1 \vee \dots \vee \ell_{k_j})$ 不被满足，当且仅当它的 $k_j$ 个文字全部取假——每个文字独立地以 $1/2$ 概率为假，所以

$$\Pr[C_j \text{ 被满足}] = 1 - 2^{-k_j} \ge \frac{1}{2}$$

最后一步用了 $k_j \ge 1$。由期望的线性性（无需任何独立性假设）：

$$\mathbb{E}[\text{满足子句数}] = \sum_{j=1}^m \Pr[C_j \text{ 被满足}] \ge \frac{m}{2} \ge \frac{\text{OPT}}{2}$$

最后一步因为 $\text{OPT} \le m$（最多满足全部 $m$ 个子句）。所以纯随机赋值是 $\frac{1}{2}$-近似算法——什么都没算，靠抛硬币就赢了一半。这个朴素界会成为后面组合算法的一块基石。注意它对「子句长」的情形特别好：$k_j$ 越大，$1 - 2^{-k_j}$ 越接近 $1$。

算法二：线性规划舍入

随机赋值的弱点是对短子句（尤其 $k_j = 1$ 的单文字子句）只有 $1/2$ 的保障。线性规划能利用问题结构做得更好。先把 Max-SAT 写成整数规划。

为每个变量设 $x_i \in \{0, 1\}$（$1$ 表示取 $\texttt{T}$），为每个子句设指示变量 $y_j \in \{0, 1\}$（$1$ 表示 $C_j$ 被满足）。记 $S_j^+ = \{i : x_i \text{ 出现在 } C_j\}$，$S_j^- = \{i : \neg x_i \text{ 出现在 } C_j\}$。子句被满足当且仅当某个正文字取真或某个负文字取假：

Max-SAT 的整数规划与松弛

$$\begin{aligned} \text{maximize} \quad & \sum_{j=1}^m y_j \\ \text{subject to} \quad & \sum_{i \in S_j^+} x_i + \sum_{i \in S_j^-} (1 - x_i) \ge y_j & 1 \le j \le m \\ & x_i, y_j \in \{0, 1\} \quad (\text{松弛为 } [0, 1]) \end{aligned}$$

约束的含义：左边是「为 $C_j$ 出力的文字总数」，只有它 $\ge 1$（至少一个文字为真）时，$y_j$ 才被允许取 $1$。把整数域松弛成 $[0, 1]$ 即得线性规划。

设松弛最优解为 $\bm{x}^* \in [0, 1]^n, \bm{y}^* \in [0, 1]^m$。线性随机舍入：每个变量独立地以概率 $x_i^*$ 取 $1$：

$$\hat{x}_i = \begin{cases} 1 & \text{以概率 } x_i^* \\ 0 & \text{以概率 } 1 - x_i^* \end{cases} \quad (\text{相互独立})$$

把分数值直接当概率用——这是「随机化舍入」的核心思想。来分析单个子句被满足的概率：

$$\Pr[C_j \text{ 被满足}] = 1 - \prod_{i \in S_j^+} (1 - x_i^*) \prod_{i \in S_j^-} x_i^*$$

右边减去的是「所有文字都为假」的概率。要给它一个下界，用两个不等式：

用到的两个不等式

• AM-GM 不等式：$k$ 个非负数的几何平均 $\le$ 算术平均，即 $\prod a_i \le \left(\frac{\sum a_i}{k}\right)^k$。
• Jensen 不等式：对凹函数 $g$ 与 $t \in [0, 1]$，$g(t \cdot v) \ge t \cdot g(v) + (1-t)g(0)$；用在 $g(z) = 1 - (1 - z/k)^k$ 上（它在 $[0,1]$ 上凹且 $g(0)=0$），给出 $g(t) \ge t \cdot g(1)$。

由 AM-GM，把那 $k_j$ 个「为假概率」的乘积放大成它们平均值的 $k_j$ 次方。而这些为假概率之和等于 $k_j$ 减去「为 $C_j$ 出力的文字总量」，由约束后者 $\ge y_j^*$，所以平均值 $\le 1 - y_j^* / k_j$：

$$\Pr[C_j \text{ 被满足}] \ge 1 - \left(1 - \frac{y_j^*}{k_j}\right)^{k_j} \ge \left(1 - \left(1 - \frac{1}{k_j}\right)^{k_j}\right) y_j^* \ge \left(1 - \frac{1}{\e}\right) y_j^*$$

中间一步是 Jensen 不等式（凹函数的弦在函数下方），最后一步用了 $(1 - 1/k)^k$ 随 $k$ 递增趋于 $1/\e$，所以 $1 - (1 - 1/k)^k \ge 1 - 1/\e$。对所有子句求和：

$$\mathbb{E}[\text{SOL}] = \sum_{j=1}^m \Pr[C_j \text{ 被满足}] \ge \left(1 - \frac{1}{\e}\right) \sum_{j=1}^m y_j^* = \left(1 - \frac{1}{\e}\right) \text{OPT}_{\text{LP}} \ge \left(1 - \frac{1}{\e}\right) \text{OPT}$$

末尾用到 $\text{OPT}_{\text{LP}} \ge \text{OPT}$——注意这里是最大化问题，与顶点覆盖方向相反：松弛扩大可行域，最大化的最优值只会更大，所以松弛最优值是真实最优值的上界。

所以线性规划舍入是 $(1 - 1/\e) \approx 0.632$-近似。它和随机赋值的优劣恰好相反：对短子句更好（$k_j$ 越小 $1 - (1 - 1/k_j)^{k_j}$ 越大，$k_j=1$ 时达 $1$），对长子句反而略逊。

算法三：两个选择的力量

我们手上有两个互补的算法：随机赋值偏爱长子句，线性规划舍入偏爱短子句。能不能取长补短？

两个选择的力量

• 用随机赋值满足 $M_1$ 个子句；
• 用线性规划舍入满足 $M_2$ 个子句；
• 输出两者中满足子句更多的那个。

「取较大者」至少不小于「取平均」，这个朴素的观察是关键：

$$\mathbb{E}[\max\{M_1, M_2\}] \ge \mathbb{E}\left[\frac{M_1 + M_2}{2}\right]$$

分别代入两个算法对单个子句的贡献下界：

$$\mathbb{E}[M_1] \ge \sum_{j=1}^m (1 - 2^{-k_j}) y_j^*, \qquad \mathbb{E}[M_2] \ge \sum_{j=1}^m \left(1 - \left(1 - \frac{1}{k_j}\right)^{k_j}\right) y_j^*$$

（随机赋值的 $1 - 2^{-k_j} \ge (1 - 2^{-k_j}) y_j^*$ 因为 $y_j^* \le 1$。）于是每个子句的平均系数是

$$\frac{(1 - 2^{-k_j}) + \left(1 - (1 - 1/k_j)^{k_j}\right)}{2}$$

逐一验证这个量对所有 $k_j$ 都 $\ge 3/4$，恰好是两个算法的「短板」互补的结果：

$k_j$	随机赋值 $1 - 2^{-k}$	线性舍入 $1 - (1-1/k)^k$	平均
$1$	$1/2$	$1$	$3/4$
$2$	$3/4$	$3/4$	$3/4$
$\ge 3$	$\ge 7/8$	$\ge 1 - 1/\e \approx 0.63$	$> 3/4$

最小值恰好在 $k_j = 1, 2$ 处取得，都等于 $3/4$。把两个算法的逐子句系数与它们的平均画在一起，这种「此消彼长」看得更清楚：

所以

$$\mathbb{E}[\max\{M_1, M_2\}] \ge \frac{3}{4} \sum_{j=1}^m y_j^* \ge \frac{3}{4} \text{OPT}$$

两个选择的组合是 $\frac{3}{4}$-近似——比单独任一个都好。一个算法的短板（随机赋值在 $k=1$ 处只有 $1/2$）恰好是另一个的长板（线性舍入在 $k=1$ 处满分），平均下来填平了凹陷。

算法四：非线性舍入

组合算法虽好，却要跑两个算法再比较。能否用单个算法直接达到 $3/4$？答案是肯定的，靠的是更聪明的舍入函数。

线性舍入直接把 $x_i^*$ 当概率，非线性舍入则先用一个函数 $f$ 变换一下：以概率 $f(x_i^*)$ 取 $1$。重新分析子句不被满足的概率：

$$\Pr[C_j \text{ 不被满足}] = \prod_{i \in S_j^+} (1 - f(x_i^*)) \prod_{i \in S_j^-} f(x_i^*)$$

关键想法：若能找到 $f$ 和常数 $c > 1$，使

$$1 - c^{-x} \le f(x) \le c^{x - 1} \quad \forall x \in [0, 1]$$

那么正文字的「为假概率」由下界控制——$f(x) \ge 1 - c^{-x}$ 给出 $1 - f(x_i^*) \le c^{-x_i^*}$；负文字的「为假概率」由上界控制——$f(x) \le c^{x-1}$ 即 $f(x_i^*) \le c^{-(1 - x_i^*)}$。乘起来：

$$\Pr[C_j \text{ 不被满足}] \le c^{-\left(\sum_{i \in S_j^+} x_i^* + \sum_{i \in S_j^-}(1 - x_i^*)\right)} \le c^{-y_j^*}$$

于是 $\Pr[C_j \text{ 被满足}] \ge 1 - c^{-y_j^*} \ge (1 - 1/c) y_j^*$（最后用 Jensen，因 $1 - c^{-z}$ 在 $[0,1]$ 上凹），从而

$$\mathbb{E}[\text{SOL}] \ge (1 - 1/c)\, \text{OPT}$$

要让近似比 $1 - 1/c$ 尽量大，就要 $c$ 尽量大。但 $c$ 不能无限大——夹住 $f$ 的两条曲线 $1 - c^{-x}$（下）与 $c^{x-1}$（上）必须留出空间让 $f$ 存在，即对所有 $x \in [0,1]$ 需要 $1 - c^{-x} \le c^{x-1}$。

两条曲线的最窄处在哪？考察差 $c^{x-1} - (1 - c^{-x}) = c^{x-1} - 1 + c^{-x}$，对 $x$ 求导置零，驻点在 $x = 1/2$，此处差值为

$$\frac{2}{\sqrt{c}} - 1 = \min_{0 \le x \le 1}\left(c^{x-1} - 1 + c^{-x}\right)$$

要让这个最小差 $\ge 0$（曲线不交叉、$f$ 有容身之处），需 $\frac{2}{\sqrt c} - 1 \ge 0$，即 $c \le 4$。取最大的 $c = 4$，近似比达到 $1 - 1/4 = 3/4$。

一个显式的舍入函数

$c = 4$ 时夹逼条件成为 $1 - 4^{-x} \le f(x) \le 4^{x-1}$。满足它的函数必须穿过 $x = 1/2$ 处的「针眼」，写出来并不顺手。一个更好算的选择是线性函数

$$f(x) = \frac{x}{2} + \frac{1}{4}$$

它正是「两个选择」的逐变量翻版：对每个变量独立抛一枚公平硬币，正面用纯随机赋值（以 $1/2$ 取 $1$），反面用线性舍入（以 $x_i^*$ 取 $1$），合计取 $1$ 的概率恰为 $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} x_i^* = f(x_i^*)$。

有趣的是，这个 $f$ 并不处处满足夹逼条件——上图中可以看出，它只在 $x = 0, \frac{1}{2}, 1$ 三点触及边界曲线，其余位置都略微越界。所以它的近似比要单独验证。直接用 AM-GM：

$$\Pr[C_j \text{ 不被满足}] = \prod_{i \in S_j^+}\left(\frac{3}{4} - \frac{x_i^*}{2}\right) \prod_{i \in S_j^-}\left(\frac{1}{4} + \frac{x_i^*}{2}\right) \le \left(\frac{3}{4} - \frac{y_j^*}{2k_j}\right)^{k_j}$$

括号里的因子都能写成 $\frac{3}{4}$ 减去「该文字为真的出力」的一半，求和后用约束 $\ge y_j^*$。再由 Jensen 不等式（与线性舍入的分析同款），

$$\Pr[C_j \text{ 被满足}] \ge 1 - \left(\frac{3}{4} - \frac{y_j^*}{2k_j}\right)^{k_j} \ge \left[1 - \left(\frac{3}{4} - \frac{1}{2k_j}\right)^{k_j}\right] y_j^* \ge \frac{3}{4}\, y_j^*$$

最后一个不等式对一切 $k_j \ge 1$ 成立（最小值又是在 $k_j = 1, 2$ 处取得，恰为 $\frac{3}{4}$）。于是单次舍入就是 $\frac{3}{4}$-近似，无需跑两遍再比较。

Max-SAT 小结

我们用四种算法把 Max-SAT 的近似比从 $1/2$ 一路推到 $3/4$：

算法	近似比	关键思想
纯随机赋值	$1/2$	抛硬币，偏爱长子句
线性规划舍入	$1 - 1/\e \approx 0.63$	分数解当概率，偏爱短子句
两个选择	$3/4$	取两者较优，长短互补
非线性舍入	$3/4$	单算法，曲线夹逼定 $c = 4$

几个值得记住的收尾事实：

• 上述随机算法都可以用条件期望法（Method of Conditional Expectation）去随机化，得到确定性的 $3/4$-近似算法；
• Max-SAT 线性规划松弛的整性间隙恰好是 $3/4$——所以 $3/4$ 是这套松弛方法的极限；
• 对每个子句恰好 $3$ 个文字的 Max-3SAT，用半定规划（Semidefinite Programming, SDP）松弛舍入可达 $7/8$-近似，且除非 $\mathsf{P} = \mathsf{NP}$，否则无法超过 $7/8$。

线性规划松弛已被榨到 $3/4$ 的天花板，要再进一步就得换更强的工具（SDP）。但在转向那之前，我们还欠一笔账：本讲开头的「最大流 = 最小割」，到底为什么成立？答案藏在线性规划自身的对偶结构里。

线性规划对偶

一个朴素的问题：怎么知道自己已经最优？

考虑这个最小化线性规划：

$$\begin{aligned} \text{minimize} \quad & 7x_1 + x_2 + 5x_3 \\ \text{subject to} \quad & x_1 - x_2 + 3x_3 \ge 10 \\ & 5x_1 + 2x_2 - x_3 \ge 6 \\ & x_1, x_2, x_3 \ge 0 \end{aligned}$$

随手找一个可行解，比如 $\bm{x} = (2, 1, 3)$：代入两个约束，$2 - 1 + 9 = 10 \ge 10,\, 10 + 2 - 3 = 9 \ge 6$，都满足；目标值 $7 \cdot 2 + 1 + 5 \cdot 3 = 30$。所以 $\text{OPT} \le 30$——任何可行解都给出一个上界。

但我们怎么知道 $30$ 离最优有多远？需要一个下界。一个绝妙的技巧是：把约束非负线性组合起来。给两个约束分别配权重 $y_1, y_2 \ge 0$，相加：

$$y_1(x_1 - x_2 + 3x_3) + y_2(5x_1 + 2x_2 - x_3) \ge 10 y_1 + 6 y_2$$

左边整理成 $x$ 的系数：$(y_1 + 5y_2)x_1 + (-y_1 + 2y_2)x_2 + (3y_1 - y_2)x_3$。如果这些系数都不超过目标函数对应的系数（$7, 1, 5$），那么因为 $\bm{x} \ge 0$，目标函数 $\ge$ 左边 $\ge 10y_1 + 6y_2$。于是只要 $y$ 满足

$$y_1 + 5y_2 \le 7, \quad -y_1 + 2y_2 \le 1, \quad 3y_1 - y_2 \le 5, \quad y_1, y_2 \ge 0$$

那么 $10y_1 + 6y_2$ 就是 $\text{OPT}$ 的一个下界。例如 $\bm{y} = (1, 1)$ 满足这些约束（$6 \le 7,\, 1 \le 1,\, 2 \le 5$），给出下界 $10 + 6 = 16$。所以 $16 \le \text{OPT} \le 30$。

为了得到最好的下界，我们要最大化 $10y_1 + 6y_2$——这本身又是一个线性规划！它就是原问题的对偶。

对偶的一般构造

把上面的推导抽象出来，就得到了线性规划对偶的一般定义。

线性规划对偶

原始（Primal）与对偶（Dual）成对出现：

$$\text{Primal:} \quad \min \bm{c}^{\intercal}\bm{x} \ \text{ s.t. } \bm{A}\bm{x} \ge \bm{b},\ \bm{x} \ge \bm{0} \qquad\Longleftrightarrow\qquad \text{Dual:} \quad \max \bm{b}^{\intercal}\bm{y} \ \text{ s.t. } \bm{A}^{\intercal}\bm{y} \le \bm{c},\ \bm{y} \ge \bm{0}$$

对偶变量 $y_i$ 对应原始的第 $i$ 个约束；对偶约束 $\bm{A}^{\intercal}\bm{y} \le \bm{c}$（即 $\bm{y}^{\intercal}\bm{A} \le \bm{c}^{\intercal}$）对应原始的每个变量。原始最小化、对偶最大化；原始约束数 = 对偶变量数，反之亦然。

一个生动的解释是「维生素定价问题」（即经典的膳食问题，Diet Problem）：

维生素定价

原始问题（消费者视角）：$n$ 种天然食物，价格 $c_1, \dots, c_n$，每种含各类维生素 $a_{ij}$；要摄入足够的维生素（$\bm{A}\bm{x} \ge \bm{b}$）同时花钱最少（$\min \bm{c}^{\intercal}\bm{x}$）。

对偶问题（药商视角）：药商想卖 $m$ 种维生素药片，为每种维生素定价 $y_i$。他要让自己的定价「有竞争力」——任何一种天然食物的维生素，按药片定价算出来都不比食物本身贵（$\bm{A}^{\intercal}\bm{y} \le \bm{c}$）；在此前提下最大化卖给消费者一套维生素的总收入（$\max \bm{b}^{\intercal}\bm{y}$）。

强对偶定理（下面会讲）说：药商的最大收入 = 消费者的最小花费。无论你买食物还是买药片，达到健康标准的最低成本是同一个数。

对偶还有一个优雅的对称性：

对偶的对偶是原始

对对偶问题再取一次对偶，得到的就是原始问题：$\text{dual}(\text{dual}(\text{LP})) = \text{LP}$。原始与对偶是完全对等的一对，谁也不比谁更「根本」。

弱对偶与强对偶

前面「下界」的推导，本质上证明了对偶的第一个核心定理。

弱对偶定理

对任意原始可行解 $\bm{x}$ 与对偶可行解 $\bm{y}$：

$$\bm{y}^{\intercal}\bm{b} \le \bm{y}^{\intercal}\bm{A}\bm{x} \le \bm{c}^{\intercal}\bm{x}$$

即任意对偶可行值 $\le$ 任意原始可行值。

证明只是两次「夹」：由 $\bm{A}\bm{x} \ge \bm{b}$ 且 $\bm{y} \ge 0$，得 $\bm{y}^{\intercal}\bm{b} \le \bm{y}^{\intercal}(\bm{A}\bm{x})$；由 $\bm{y}^{\intercal}\bm{A} \le \bm{c}^{\intercal}$ 且 $\bm{x} \ge 0$，得 $(\bm{y}^{\intercal}\bm{A})\bm{x} \le \bm{c}^{\intercal}\bm{x}$。这正是我们在网络流里见过的「任意流 $\le$ 任意割」的一般版本！

弱对偶只说对偶值不超过原始值，但没说它们能否相等。令人惊叹的是，对线性规划而言，二者总能相遇。

强对偶定理

原始线性规划有有限最优解 $\bm{x}^*$，当且仅当对偶线性规划有有限最优解 $\bm{y}^*$，并且此时两者最优值相等：

$$\bm{y}^{*\intercal}\bm{b} = \bm{c}^{\intercal}\bm{x}^*$$

强对偶是线性规划理论的皇冠。它说最大化的对偶和最小化的原始不仅互为界限，最优处还严丝合缝地重合——没有任何「间隙」。这与网络流里「最大流 = 最小割」是同一回事，只是更普遍。

把前面那个「怎么知道已经最优」的例子画成一根目标值轴，弱对偶与强对偶就一目了然：原始可行解的目标值都落在 OPT 上方（如 $\bm{x} = (2,1,3)$ 给出 $30$），对偶可行解的值都落在 OPT 下方（如 $\bm{y} = (1,1)$ 给出 $16$），于是弱对偶夹出 $16 \le \text{OPT} \le 30$；而强对偶进一步保证两者在最优处严丝合缝地相遇于 $\text{OPT} = 26$，中间没有任何间隙。

线性规划属于 $\mathsf{NP} \cap \mathsf{coNP}$

强对偶有一个漂亮的复杂度推论：要证明「最优值 $\le k$」，出示一个目标值 $\le k$ 的原始可行解即可（NP 式证书）；要证明「最优值 $\ge k$」，出示一个目标值 $\ge k$ 的对偶可行解即可（coNP 式证书）。所以线性规划的判定版本同时属于 $\mathsf{NP}$ 和 $\mathsf{coNP}$——这强烈暗示它不是 NP-难的（后来椭球法证实它确在 $\mathsf{P}$ 中）。

最大流最小割就是线性规划对偶

现在可以兑现本讲开头的承诺了。把最大流写成线性规划，取它的对偶，会精确地得到最小割。

最大流的线性规划（用一条容量无穷的 $t \to s$ 回边，最大化 $f_{ts}$，使所有点都守恒）：

$$\begin{aligned} \max \quad & f_{ts} \\ \text{s.t.} \quad & f_{uv} \le c_{uv} & \forall (u, v) \in E \\ & \sum_{w} f_{wu} - \sum_{v} f_{uv} \le 0 & \forall u \in V \\ & f_{uv} \ge 0 & \forall (u, v) \in E \end{aligned}$$

守恒约束写成「流入 $\le$ 流出」而非等式，是个不影响答案的小技巧：把所有顶点的「流入 $-$ 流出」加起来恒等于零（每条边恰好给一个顶点贡献流入、给另一个贡献流出），一堆非正数之和为零，只能每个都是零——所以 $\le$ 实际上被逼成 $=$。

这样写的好处是：最大化问题中全部约束都是 $\le$，正好与「$\max$ 配 $\le$ 约束、对偶变量非负」的标准对偶规则（即原始对偶角色互换后的同一对规则）对上。

为容量约束配对偶变量 $d_{uv} \ge 0$、为守恒约束配对偶变量 $p_u \ge 0$，逐列取对偶——每个原始变量 $f_{uv}$ 生成一条对偶约束，把它在各约束中的系数乘上对偶变量加总，要求 $\ge$ 它的目标系数：

• 普通边 $f_{uv}$（目标系数 $0$）：出现在自己的容量约束（系数 $1$，配 $d_{uv}$）、$u$ 的守恒约束（流出，系数 $-1$，配 $p_u$）、$v$ 的守恒约束（流入，系数 $1$，配 $p_v$），得 $d_{uv} - p_u + p_v \ge 0$；
• 回边 $f_{ts}$（目标系数 $1$，无容量约束）：流出 $t$、流入 $s$，得 $p_s - p_t \ge 1$。

整理出来就是：

最小割的线性规划（最大流的对偶）

$$\begin{aligned} \min \quad & \sum_{(u, v) \in E} c_{uv}\, d_{uv} \\ \text{s.t.} \quad & d_{uv} - p_u + p_v \ge 0 & \forall (u, v) \in E \\ & p_s - p_t \ge 1 \\ & d_{uv} \ge 0,\ p_u \ge 0 \end{aligned}$$

这个对偶的整数版本（$d, p \in \{0, 1\}$）正是最小割！解读对偶变量的含义：

• $p_u \in \{0, 1\}$ 标记 $u$ 在割的哪一侧（$p_u = 1$ 表示 $u \in S$，即源点侧）；约束 $p_s - p_t \ge 1$ 强制 $p_s = 1, p_t = 0$，即 $s \in S, t \notin S$；
• $d_{uv} \in \{0, 1\}$ 标记边 $(u, v)$ 是否被切断；约束 $d_{uv} \ge p_u - p_v$ 是说：若 $u \in S$（$p_u=1$）而 $v \notin S$（$p_v=0$），则 $d_{uv} \ge 1$，这条顺流边必须被切断；
• 目标 $\min \sum c_{uv} d_{uv}$ 就是最小化被切断边的总容量——最小割。

这个线性规划松弛恰好有整数最优解（其约束矩阵的特殊结构——所谓全单位模（Totally Unimodular），即每个方子式都是 $0, \pm 1$——保证了多面体的顶点都落在整点上），所以「最小割线性规划」=「最小割」。强对偶定理立刻给出 $\max\text{-flow} = \min\text{-cut}$。网络流里那个看似神奇的对偶，原来只是线性规划强对偶定理的一个特例。

互补松弛

强对偶定理还有一个更精细的「局部」版本，它刻画了原始解与对偶解在最优时必须满足的配对关系。

互补松弛条件

对原始可行解 $\bm{x}$ 与对偶可行解 $\bm{y}$，二者都最优当且仅当：

$$\begin{aligned} &\forall i: \quad \bm{A}_{i \cdot}\bm{x} = b_i \ \text{ 或 } \ y_i = 0 \\ &\forall j: \quad \bm{y}^{\intercal}\bm{A}_{\cdot j} = c_j \ \text{ 或 } \ x_j = 0 \end{aligned}$$

直觉是「不浪费」：第一行说，要么原始第 $i$ 个约束取等（紧），要么对应的对偶变量 $y_i = 0$（不出力）——一个「松」的约束配的对偶价格必为零。第二行对称。换句话说，最优时弱对偶的两个 $\le$ 都必须取等，逼着每一对原始约束/对偶变量「一紧一松不能并存」。

互补松弛是从弱对偶推来的：弱对偶 $\bm{y}^{\intercal}\bm{b} \le \bm{y}^{\intercal}\bm{A}\bm{x} \le \bm{c}^{\intercal}\bm{x}$ 中，若首尾相等（强对偶最优），中间两个不等式必须都取等，逐项展开就是上面的条件。

松弛的互补松弛

为了把对偶用于近似算法，我们需要允许互补松弛「不那么严格」——这是原始对偶框架的技术核心。

松弛的互补松弛条件

对 $\alpha, \beta \ge 1$，若原始可行 $\bm{x}$ 与对偶可行 $\bm{y}$ 满足：

$$\begin{aligned} &\forall i: \quad \bm{A}_{i \cdot}\bm{x} \le \alpha\, b_i \ \text{ 或 } \ y_i = 0 \\ &\forall j: \quad \bm{y}^{\intercal}\bm{A}_{\cdot j} \ge c_j / \beta \ \text{ 或 } \ x_j = 0 \end{aligned}$$

则

$$\bm{c}^{\intercal}\bm{x} \le \alpha\beta\, \bm{b}^{\intercal}\bm{y} \le \alpha\beta\, \text{OPT}_{\text{LP}}$$

结论的证明就是把弱对偶的链条「放松」一遍：第二组条件保证每个 $x_j > 0$ 的项都有 $c_j \le \beta\, \bm{y}^{\intercal}\bm{A}_{\cdot j}$，第一组条件保证每个 $y_i > 0$ 的项都有 $\bm{A}_{i\cdot}\bm{x} \le \alpha\, b_i$，于是

$$\bm{c}^{\intercal}\bm{x} = \sum_j c_j x_j \le \beta \sum_j (\bm{y}^{\intercal}\bm{A}_{\cdot j})\, x_j = \beta\, \bm{y}^{\intercal}\bm{A}\bm{x} = \beta \sum_i (\bm{A}_{i\cdot}\bm{x})\, y_i \le \alpha\beta \sum_i b_i y_i = \alpha\beta\, \bm{b}^{\intercal}\bm{y}$$

把严格的「取等」放松成「相差不超过 $\alpha$ 倍 / $\beta$ 倍」，结论也相应地从「相等」松弛成「相差不超过 $\alpha\beta$ 倍」。这个 $\alpha\beta$ 因子，正是近似比的来源——下一节会看到它怎么直接转化为算法的近似保证。

原始对偶框架

前面我们用「松弛 + 求解 + 舍入」攻克 NP-难问题，但那条路要真的调用线性规划求解器去解松弛。原始对偶框架走一条更聪明的路：根本不解线性规划，只利用对偶的结构，同时「生长」出一个原始整数解和一个对偶解，让二者通过松弛的互补松弛绑在一起，近似比自动浮现。

先看一个对偶现象：顶点覆盖与匹配

回到顶点覆盖。它的线性规划松弛 $\min\{\sum_v x_v : \sum_{v \in e} x_v \ge 1,\ x_v \ge 0\}$ 的对偶是什么？机械地取对偶——每条边一个对偶变量 $y_e$，每个顶点一条对偶约束：

顶点覆盖与匹配互为对偶

$$\text{Primal (顶点覆盖):} \ \min \sum_{v} x_v,\ \sum_{v \in e} x_v \ge 1 \quad\Longleftrightarrow\quad \text{Dual (分数匹配):} \ \max \sum_{e} y_e,\ \sum_{e \ni v} y_e \le 1$$

对偶恰好是分数匹配（Fractional Matching）问题！顶点覆盖的约束（每条边）变成匹配的变量（每条边 $y_e$），顶点覆盖的变量（每个顶点）变成匹配的约束（每个顶点 $\sum_{e \ni v} y_e \le 1$）。

这解释了一个早已存在的经典算法：求一个极大匹配 $M$，输出所有被匹配的顶点 $C$。它为什么是 $2$-近似？

• $C$ 是顶点覆盖：若某条边 $e$ 两端都不在 $C$ 中，那 $e$ 没碰到任何匹配边，可以加入 $M$，与 $M$ 极大矛盾。
• $|M| \le \text{OPT}_{\text{VC}}$（弱对偶）：匹配的每条边都需要一个专属的覆盖顶点（匹配边两两不共享顶点），所以覆盖至少要 $|M|$ 个点。
• 合起来：$|C| = 2|M| \le 2\,\text{OPT}_{\text{VC}}$。

匹配（对偶）给出了顶点覆盖（原始）的下界——这正是弱对偶在组合问题里的化身。原始对偶框架把这个洞察系统化。

顶点覆盖的原始对偶算法

算法同时维护原始解 $\bm{x}$（初始全 $0$，不可行）和对偶解 $\bm{y}$（初始全 $0$，可行）。称顶点 $v$ 紧（Tight / Saturated），若它的对偶约束取等：$\sum_{e \ni v} y_e = 1$。

初始 x = 0, y = 0;
while E ≠ ∅:
    任取一条边 e ∈ E，增大 y_e 直到某个端点 v 变紧（∑_{e∋v} y_e = 1）;
    对所有变紧的 v 置 x_v = 1，并从 E 中删去所有与 v 相关的边;

算法不停地「抬高」某条边的对偶价格，直到压紧某个顶点，就把那个顶点选进覆盖，并删掉它覆盖的所有边。来验证它的正确性与近似比：

$\bm{x}$ 是合法顶点覆盖：每条被删的边都因为它的某个端点 $v$ 被置 $x_v = 1$ 才删去。循环结束时所有边都被删，所以每条边都有端点在覆盖里，$\forall e: \sum_{v \in e} x_v \ge 1$。

近似比由松弛互补松弛给出。检查两组条件：

• $\forall e$：要么 $\sum_{v \in e} x_v \le 2$，要么 $y_e = 0$。每条边只有两个端点，所以 $\sum_{v \in e} x_v \le 2$ 永远成立——取 $\alpha = 2$。
• $\forall v$：要么 $\sum_{e \ni v} y_e = 1$（$v$ 紧），要么 $x_v = 0$。算法只在 $v$ 变紧时才置 $x_v = 1$，所以 $x_v = 1 \Rightarrow v$ 紧——取 $\beta = 1$。

代入松弛互补松弛的结论：

$$\text{SOL} = \sum_v x_v \le \alpha\beta \sum_e y_e = 2 \sum_e y_e \le 2\,\text{OPT}_{\text{LP}} \le 2\,\text{OPT}$$

所以这个原始对偶算法是 $2$-近似。事实上，它生成的覆盖恰好对应一个极大匹配的匹配顶点——原始对偶算法与极大匹配算法殊途同归，但前者揭示了「为什么是 $2$」：$2$ 来自「每条边至多两个端点」这个 $\alpha = 2$。

原始对偶的妙处

整个过程没有调用任何线性规划求解器，只是从 $\bm{x} = \bm{0}, \bm{y} = \bm{0}$ 出发，机械地「抬对偶、紧约束、置原始」。对偶解 $\bm{y}$ 全程只用来记账——它给出的 $\sum_e y_e \le \text{OPT}_{\text{LP}}$ 是近似比分析的标尺，算法结束后甚至可以丢掉。这使原始对偶算法通常比「解线性规划再舍入」快得多。

通用框架

把顶点覆盖的做法抽象出来，就是适用于大量覆盖类问题的原始对偶框架。

flowchart TD
    A["写出 LP 松弛及其对偶<br/>min cᵀx, Ax≥b ⟷ max bᵀy, yᵀA≤c"] --> B["初始化<br/>原始 x 不可行、对偶 y 可行<br/>(通常 x=0, y=0)"]
    B --> C{"x 可行了吗？"}
    C -->|否| D["抬高对偶 y<br/>直到某条对偶约束变紧 yᵀA·ⱼ = cⱼ"]
    D --> E["按变紧的对偶约束<br/>整数地抬高对应的 xⱼ"]
    E --> C
    C -->|是| F["验证松弛互补松弛<br/>∀i: A·x≤αbᵢ 或 yᵢ=0<br/>∀j: yᵀA·ⱼ=cⱼ 或 xⱼ=0"]
    F --> G["得近似比<br/>cᵀx ≤ αβ·bᵀy ≤ αβ·OPT"]

    classDef setup fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef loop fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef decide fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef result fill:#f3e5f5,stroke:#4a148c,stroke-width:2px

    class A,B setup
    class D,E loop
    class C decide
    class F,G result

原始对偶框架

1. 写出松弛与对偶：把原始整数规划 $\min\{\bm{c}^{\intercal}\bm{x} : \bm{A}\bm{x} \ge \bm{b},\ \bm{x} \in \Z_{\ge 0}\}$ 松弛，并写出对偶 $\max\{\bm{b}^{\intercal}\bm{y} : \bm{y}^{\intercal}\bm{A} \le \bm{c}^{\intercal},\ \bm{y} \ge \bm{0}\}$。
2. 初始化：原始 $\bm{x}$ 不可行、对偶 $\bm{y}$ 可行（通常 $\bm{x} = \bm{0}, \bm{y} = \bm{0}$）。
3. 同步生长：在 $\bm{x}$ 变可行之前，反复地——抬高 $\bm{y}$ 直到某条对偶约束变紧（$\bm{y}^{\intercal}\bm{A}_{\cdot j} = c_j$）；按变紧的对偶约束整数地抬高对应的 $x_j$。
4. 验证松弛互补松弛：$\forall i$ 要么 $\bm{A}_{i\cdot}\bm{x} \le \alpha b_i$ 要么 $y_i = 0$；$\forall j$ 要么 $\bm{y}^{\intercal}\bm{A}_{\cdot j} = c_j$ 要么 $x_j = 0$（第二组条件因「只在对偶约束变紧时才抬 $x_j$」自动满足，即 $\beta = 1$）。
5. 由此得到 $\bm{c}^{\intercal}\bm{x} \le \alpha\beta\, \bm{b}^{\intercal}\bm{y} \le \alpha\beta\, \text{OPT}_{\text{LP}} \le \alpha\beta\, \text{OPT}_{\text{IP}}$，近似比 $\alpha\beta$。

最后一步的不等式链值得回味：$\bm{b}^{\intercal}\bm{y} \le \text{OPT}_{\text{LP}}$ 因为 $\bm{y}$ 对偶可行（弱对偶），$\text{OPT}_{\text{LP}} \le \text{OPT}_{\text{IP}}$ 因为松弛放大了可行域。对偶解 $\bm{y}$ 像一根「内置的标尺」，让算法在不知道 $\text{OPT}$ 的情况下，依然能证明自己离它不远。这套框架后来被用于 Steiner 树、设施选址、网络设计等一大批问题，是近似算法领域最具生产力的设计范式之一。

章节小结

本讲从一个朴素的运输问题出发，最终抵达了组合优化的核心思想——对偶。回顾这条主线：

flowchart TD
    Flow["网络流<br/>最大流问题"] --> FF["Ford-Fulkerson<br/>残余图 + 增广路径"]
    FF --> MFMC["最大流 = 最小割<br/>(对偶现象初现)"]
    FF --> Algo["算法加速<br/>缩放 / 最短增广 / Dinitz"]
    Flow --> App["应用<br/>二部匹配 / 最小割 / 最小费用流"]

    MFMC --> LP["线性规划<br/>(统一框架)"]
    LP --> Geo["几何<br/>多面体 / 顶点 / bfs"]
    LP --> Solve["求解器<br/>单纯形 / 椭球 / 内点"]

    LP --> Round["LP 松弛与舍入<br/>顶点覆盖 2-近似 / Max-SAT 3/4"]
    LP --> Dual["LP 对偶<br/>弱对偶 / 强对偶 / 互补松弛"]
    Dual --> MFMC2["最大流最小割<br/>= 强对偶特例"]
    Dual --> PD["原始对偶框架<br/>不解 LP 也能近似"]
    Round --> PD

    classDef flow fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef lp fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef apply fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef dual fill:#f3e5f5,stroke:#4a148c,stroke-width:2px

    class Flow,FF,Algo flow
    class LP,Geo,Solve lp
    class App,Round apply
    class MFMC,Dual,MFMC2,PD dual

几条贯穿全讲的核心思想：

• 对偶无处不在。「最大流 = 最小割」「匹配 = 顶点覆盖」「消费者最小花费 = 药商最大收入」，看似不相干的最大化与最小化问题成对出现、最优值相等。它们都是线性规划强对偶定理的具体面孔。
• 线性规划是统一的语言。网络流、匹配、覆盖、可满足性……都能写成线性规划或整数规划。线性规划可在多项式时间求解，于是成了攻克难题的通用引擎。
• 松弛—舍入是攻克 NP-难的标准套路。把整数约束放宽成连续、解出分数最优、再小心舍回整数，近似比由整性间隙这个内在量决定。
• 对偶可以「不解就用」。原始对偶框架同步生长原始整数解与对偶解，用对偶当标尺，不调用求解器就得到近似保证——往往更快、更有洞察力。

问题	最优结构	关键结果
最大流	增广路径耗尽	$\max\text{-flow} = \min\text{-cut}$，Dinitz $O(n^2 m)$
线性规划	最优在顶点	多项式时间可解（椭球 / 内点）
顶点覆盖	LP 松弛 + 舍入	$2$-近似，整性间隙 $= 2$
Max-SAT	随机化舍入	$3/4$-近似，整性间隙 $= 3/4$
LP 对偶	强对偶	原始最优 = 对偶最优
原始对偶	松弛互补松弛	近似比 $= \alpha\beta$

从一次物资运输，到一套攻克难题的通用哲学——这就是网络流与线性规划交给我们的礼物：当一个问题难以直接求解时，去寻找它的对偶；当一个问题难以精确求解时，去松弛它、再小心地舍回来。

---

1. 严格说是一串带回退的 DFS：每次沿前向边深入，走到死路就回退并删掉死边，抵达 $t$ 就增广。每次增广（至多 $m$ 次，每次饱和一条边）路径长 $\le n$，删边总开销 $\le m$，摊还下来 $O(nm)$。 ↩︎

2. NP-难（NP-hard）粗略地说，是指「至少和 NP 类中最难的问题一样难」的一类问题。直观理解：目前没有已知的多项式时间精确算法，且被广泛相信（在 $\mathsf{P} \ne \mathsf{NP}$ 的假设下）根本不存在这样的算法。面对 NP-难问题，实践中只能退而求其次——要么接受指数时间，要么寻找近似算法：放弃「精确最优」，换取「多项式时间内得到接近最优的解」。本讲后半部分正是用线性规划来设计这类近似算法。 ↩︎