← 线性规划网络流 · 最大流、最小割与建模归约 / 线性规划视角：网络流是 LP，对偶即最小割 待审核 12 / 13
线性规划 · 对偶 · 全幺模

线性规划视角：网络流是 LP，对偶即最小割

前面各页都是算法视角：增广路、分层图、距离标号、预流推进、割、费用流——每一种都是「怎么把流推到最大」的具体过程。本页退后一步换个视角：最大流问题本身就是一个线性规划 (linear programming, LP)，而最小割是它的对偶 (dual)。最大流最小割定理那页的结论，在这个框架里只是 LP 强对偶定理 (strong duality) 在网络流上的一个特例。这把整个系列收进一个统一的框架，也解释了一个一直没明说的事实：为什么整数容量下最大流一定能取到整数。

1 · 最大流写成线性规划 (primal)

一个线性规划就是「在线性约束下最大化 / 最小化一个线性目标」。最大流与残量网络给出的流的定义——容量约束、流量守恒、最大化流值——逐字都是线性的，直接抄成 LP 即可。设每条边 e=(u→v)e = (u\to v) 的流量为变量 f_e，容量为常数 c_e，源 s 汇 t: 

maximize    |f| = Σ_{e 出 s} f_e − Σ_{e 入 s} f_e         # 从源净流出
subject to
   f_e ≤ c_e                           ∀ 边 e             # 容量约束 (每边一条)
   Σ_{e 入 w} f_e − Σ_{e 出 w} f_e = 0     ∀ 中间点 w       # 流量守恒 (每点一条)
   f_e ≥ 0                             ∀ 边 e             # 流量非负

这是一个标准 LP。 变量是每条边的流量 f_e（连续、非负）；约束有两类——一类不等式（容量，每条边一条），一类等式（守恒，每个中间点一条）；目标是最大化从源净流出的总量。没有任何非线性的东西。既然是 LP，它就有一个对应的对偶问题，而对偶有它自己的含义。

注意目标里只出现「源点关联的边」。 借助守恒约束可以证明「源净流出 = 汇净流入」，所以等价地也能写成最大化汇点净流入。两种写法对偶出来的结果一致；下面取「源净流出」这一版。

2 · 取对偶：每个约束配一个变量

取对偶的机械规则是：primal 的每条约束，对应 dual 的一个变量。primal 有两类约束，于是 dual 有两组变量：

  • 其一，给每条容量约束 fe≤cef_e \le c_e 配一个对偶变量 ye≥0y_e \ge 0（不等式约束 ⇒ 非负对偶变量）。
  • 其二，给每个守恒约束（中间点 w）配一个自由变量 p_w（等式约束 ⇒ 对偶变量无符号限制）。为统一记号，再令源点 p_s = 1、汇点 p_t = 0——这正是目标项「源净流出」在对偶里留下的痕迹。

dual 的每个变量，又对应 primal 的一个变量（每条边 f_e）生成一条约束。 对边 e=(u→v)e = (u\to v) 推导这条约束：在对偶里，f_e 的系数来自它出现的所有地方——容量约束里贡献 y_e,u 的守恒里以「流出」出现（系数 −pu-p_u）,v 的守恒里以「流入」出现（系数 +p_v）。整理得到对偶约束： 

minimize    Σ_e c_e · y_e             # 割的总容量
subject to
   y_e ≥ p_u − p_v       ∀ 边 e = (u→v)
   p_s = 1,   p_t = 0
   y_e ≥ 0               ∀ 边 e
   p_w 自由              ∀ 中间点 w

这正是最小割的 LP 松弛。 直观读法：给每个点一个标号 p（源 = 1、汇 = 0），给每条边一个 ye≥0y_e \ge 0；约束 ye≥pu−pvy_e \ge p_u - p_v 要求「若一条边从高标号点指向低标号点，就得为这个落差付出 y_e」；目标是用最小的总容量代价 Σce⋅yeΣ c_e\cdot y_e 把源汇隔开。把它限制到整数解上看得最清楚——见下表右列。

对应项 Primal · 最大流 (max-flow) Dual · 最小割 (min-cut)
变量 每边流量 $f_e \ge 0$ 每点势 p_w(s=1, t=0)+ 每边 $y_e \ge 0$
目标 max 源净流出 f min Σ c_e · y_e
约束 （一） 容量 $f_e \le c_e$（配 dual 变量 y_e） $y_e \ge p_u - p_v$（配 primal 变量 f_e）
约束 （二） 守恒 Σ入 = Σ出（配 dual 变量 p_w） 边界 p_s = 1, p_t = 0
整数最优解 整数流（见下文全幺模） p_w ∈ {0,1}:S = {p=1}, T = {p=0}
割的含义 流值受最窄咽喉所限 y_e = 1 的边（即 $u\in S, v\in T$）= 割边

为什么整数解里 y_e 自动落在 {0,1}、且恰好是割边？ 取定一组 0/1 的点势 p 后，minimize 会把每个 y_e 压到约束允许的最小值 max⁡(0,pu−pv)\max (0, p_u - p_v)。于是：边在割上(p_u = 1, p_v = 0)⇒ y_e = 1，计入代价 c_e；其余边(pu≤pvp_u \le p_v)⇒ y_e = 0，不计代价。目标 Σce⋅yeΣ c_e\cdot y_e 因此恰好等于「从 S = {p=1} 跨到 T = {p=0} 的边的总容量」——这就是最大流最小割定理那页定义的割容量。最小化它 = 求最小割。

3 · 弱对偶 ⇒ 流 ≤ 割，强对偶 ⇒ 相等

LP 对偶有两条普适定理，把它们落到上面这对 primal / dual 上，就直接得到最大流最小割定理的结论。

弱对偶 (weak duality): 对任意可行的 primal 解与任意可行的 dual 解，max 问题的目标值 ≤ min 问题的目标值。翻译到网络流就是：任意一个合法流的流值 ≤ 任意一个割的容量。这给了「流不可能超过割」一个一行的代数证明，无需再单独论证。直观上，源到汇的每一单位流都必须穿过割一次，而割上每条边能放行的量受其容量限制，故 |f| ≤ 割容量。

强对偶 (strong duality): 当 primal 与 dual 都有可行解时，二者的最优值相等。落到网络流：最大流 = 最小割。这就是 max-flow min-cut 定理——它不是网络流独有的奇迹，而是 LP 强对偶定理（对任何线性规划都成立）在这一族 LP 上的特例。最大流与残量网络结尾那个「末态残量网络里源点可达集 S 构成的割，容量恰等于最大流」的现象，在 LP 语言里就是：增广算法终止时，primal 与 dual 同时取到最优，二者目标值相撞——这正是互补松弛 (complementary slackness) 给出的最优性证书。

互补松弛串起了「饱和边」与「割」： 在最优解处，若某条边没被流占满（f_e < c_e，容量约束松），则其对偶变量 y_e = 0，即它不在割上；反过来，割边(y_e = 1)必然饱和(f_e = c_e)。这正是最大流最小割定理那页所见：最小割的每条边都是满流边。

4 · 全幺模：为什么整数容量必有整数流

一般的 LP 即便所有数据都是整数，其最优解也可能是分数。网络流却从不出现「半单位流」——整数容量下，最大流一定能取到整数值（integrality theorem / 整流定理）。这不是巧合，根源在约束矩阵的一个特殊性质：全幺模 (total unimodularity, TU)。

关联矩阵 (incidence matrix)。 把守恒约束写成矩阵形式 A⋅f=0A\cdot f = 0，其中 A 是有向图的点-边关联矩阵：每列对应一条边 e=(u→v)e=(u\to v)，在 u 行填 −1-1（流出）、v 行填 +1（流入）、其余为 0。每一列恰好一个 +1、一个 −1，其余全 0——这种结构的矩阵是全幺模的：它的每个方子矩阵的行列式都 ∈ {−1, 0, +1}。

TU ⇒ 整数最优，这条逻辑链：

  • 其一，LP 的最优一定能在可行域的顶点（vertex / 基本可行解） 处取到。
  • 其二，顶点是某个方子系统 B⋅x=bB\cdot x = b 的解，由 Cramer 法则 x=B−1bx = B^{-1}b，各分量 = det(B 换列) / det(B)。
  • 其三，当约束矩阵 TU 且右端 b（这里是容量 c_e）全为整数时，det⁡(B)=±1\det (B) = \pm 1，分子也是整数，故每个顶点坐标都是整数。

于是「整数容量 ⇒ 存在整数最优流」。同一性质作用在对偶上：dual 的约束矩阵也 TU，故 dual 的整数最优存在——这就是为什么前面那个 [0,1] 松弛能在 0/1 整点取到最优，松弛求出的就是真正的整数最小割，没有「整数间隙 (integrality gap)」。增广算法每步推的瓶颈是整数，正是这件事的构造性证明：它显式给出一个整数流。

这把「好解」量化了。 许多组合优化问题的自然 LP 都有整数间隙，只能近似；网络流的 LP 因 TU 而无间隙，连续松弛与整数原问题同解。所以网络流是「好解的 LP」的典范——一旦一个问题能建模成网络流 / 落进 TU 框架，就自动获得一个多项式时间的精确算法。这也是建模反复强调「把问题归约到流」的根本原因。

注 · 凸性也解释了增广算法为何不必回溯。

可行域是凸多面体，局部最优即全局最优，「顺着改进方向走」永远够用，所以任何一次糟糕的局部选择都能靠一条增广路补救。SAT、图着色这类问题的解集离散且不连通，局部修正不够，只能搜索加回溯。撤销与回溯 那页从这个角度重读了残量网络的反向边。

5 · 把三者数值对上

用最大流最小割定理那张「最小割网」实测一遍：跑到最大流，读出最小割 S / 割边，并把三个数——Primal LP 最优（最大流）、Dual LP 最优（最小割）、以及它们共同等于的那个值——摆在一起。强对偶预言它们必然相等。

收束。 整个系列，在这里合成一句话：网络流是带 TU 结构的线性规划，它的对偶就是最小割，而强对偶让二者数值精确相等、全幺模让连续优化自动吐出整数解。算法（增广 / 分层 / 阻塞流）是求这个 LP 的高效手段，而 LP / 对偶 / TU 是它们为何正确、为何高效的统一解释。当一个新问题摆在面前，最值得问的一句仍是：它能不能建模成网络流？