基于线性规划的“网络流中的最大流-最小割等价性证明与实例求解”

我们来探讨网络流理论中的一个核心定理——最大流-最小割定理，并展示如何通过构建线性规划模型，利用对偶理论来严谨地证明它，同时给出一个具体的计算实例。

第一步：问题描述与模型构建

问题定义：给定一个有向图 G=(V, E)，其中 V 是顶点集合（|V|=n），E 是边集合（|E|=m）。指定一个源点 s ∈ V 和一个汇点 t ∈ V。每条有向边 (i, j) ∈ E 都有一个容量 c_{ij} ≥ 0。网络中的一个流是一个函数 f: E → R⁺，满足：

1. 容量约束：对每条边 (i, j)，有 0 ≤ f_{ij} ≤ c_{ij}。
2. 流量守恒：对除 s 和 t 外的每个顶点 i，有 ∑{(j,i)∈E} f{ji} = ∑{(i,k)∈E} f{ik} （流入等于流出）。

目标：最大化从 s 流出（或流入 t）的总流量，即最大流问题。

线性规划模型：
设决策变量 f_{ij} 为边 (i, j) 上的流量。

• 目标函数：最大化从 s 流出的净流量，即 Maximize v = ∑_{(s,j)∈E} f_{sj} - ∑_{(j,s)∈E} f_{js}。（通常假设没有流入 s 的边，则简化为最大化 ∑ f_{sj}）。
• 约束条件：
  1. 容量约束：对于所有 (i, j) ∈ E， f_{ij} ≤ c_{ij}。
  2. 流量守恒：对于所有 i ∈ V \ {s, t}，∑_{(j,i)∈E} f_{ji} - ∑_{(i,k)∈E} f_{ik} = 0。
  3. 非负约束：f_{ij} ≥ 0。

最小割问题：一个 (s-t)割 是将顶点集 V 划分为两个子集 S 和 T = V \ S，满足 s ∈ S, t ∈ T。割的容量定义为从 S 指向 T 的所有边的容量之和，即 cap(S, T) = ∑_{i∈S, j∈T, (i,j)∈E} c_{ij}。
目标：找到一个容量最小的 (s-t) 割。

第二步：构造最大流线性规划的对偶问题

我们将通过求解最大流线性规划的对偶，自然地引出最小割问题，并证明两者的等价性。

1. 写出原问题的规范形式：
   为了便于求对偶，我们为每个顶点 i 引入一个“净流出”变量 b_i。令 b_s = 1, b_t = -1, 其他 b_i = 0。流量守恒约束可以重写为：对于所有 i ∈ V，∑_{(i,j)∈E} f_{ij} - ∑_{(j,i)∈E} f_{ji} = b_i。注意这里包含了 s 和 t 的约束（s 的净流出为 1 个单位流量，t 的净流入为 1 个单位）。
   将容量约束 f_{ij} ≤ c_{ij} 写为 f_{ij} + s_{ij} = c_{ij}，其中 s_{ij} ≥ 0 是松弛变量。
   目标函数变为：Maximize v，且满足 ∑_{(s,j)} f_{sj} - ∑_{(j,s)} f_{js} = v。我们可以将 v 视为一个变量，并增加约束 ∑_{(i,j)} f_{ij} - ∑_{(j,i)} f_{ji} = 0 对于 i ≠ s,t，以及 ∑_{(s,j)} f_{sj} - ∑_{(j,s)} f_{js} = v 和 ∑_{(t,j)} f_{tj} - ∑_{(j,t)} f_{jt} = -v。这等价于我们最初定义的 b_i 形式（b_s=v, b_t=-v, 其他=0）。为简化对偶推导，我们采用更直接的方法。

2. 直接应用对偶理论：
   考虑标准形式：Maximize c^T f， subject to A f ≤ b, f ≥ 0。
   我们将流量守恒和容量约束都写成不等式形式有点繁琐。一个更聪明的方式是为每个顶点 i 引入对偶变量 y_i（无符号限制），为每条边 (i,j) 引入对偶变量 w_{ij} ≥ 0（对应容量约束 f_{ij} ≤ c_{ij}）。
   原问题（最大流）的拉格朗日对偶可以推导出如下对偶线性规划：

   Minimize ∑_{(i,j)∈E} c_{ij} * w_{ij}
   Subject to:
   y_i - y_j + w_{ij} ≥ 0, 对于所有 (i,j) ∈ E
   y_s - y_t = 1
   w_{ij} ≥ 0, 对于所有 (i,j) ∈ E
   y_i 无约束。
   

   我们可以通过对偶变量的解释来理解这个模型。互补松弛条件将告诉我们很多信息。

第三步：最大流-最小割定理的证明（通过对偶理论）

1. 弱对偶性：对于任何可行流 f 和任何对偶可行解 (y, w)，有
   v = ∑_{(s,j)} f_{sj} - ∑_{(j,s)} f_{js} ≤ ∑_{E} c_{ij} w_{ij}。
   这表明任何流的流量 ≤ 任何割的容量。因为我们可以构造一个特殊的对偶解：对于某个 (s-t)割 (S, T)，令 y_i = 1 如果 i ∈ S，否则 y_i = 0。令 w_{ij} = max(0, y_j - y_i)。这个解是对偶可行的，并且此时对偶目标值 ∑ c_{ij} w_{ij} 恰好等于割 (S,T) 的容量（因为只有当 i∈S, j∈T 时，y_j - y_i = -1，所以 w_{ij}=1；否则为0）。代入弱对偶不等式，得到 v ≤ cap(S,T)。

2. 强对偶性与最优解结构：
   由于原问题（最大流）是可行的（零流是可行解）且有上界（总容量有限），根据线性规划强对偶定理，存在最优原解 f* 和最优对偶解 (y*, w*)，使得 v* = ∑ c_{ij} w*_{ij}。
   从互补松弛条件可得：

   • 如果 f*{ij} < c{ij}，则 w*_{ij} = 0。
   • 如果 w*{ij} > 0，则 f*{ij} = c_{ij}。
   • 如果 f*_{ij} > 0，则 y*_i - y*j + w*{ij} = 0。

3. 构造最小割：
   设最优对偶解中的 y*_i 是实数。由于 y*_s - y*_t = 1，我们可以找到一个实数 d ∈ [0, 1]，使得集合 S = { i ∈ V | y*_i > d } 包含 s 但不包含 t（因为 y*_s > y*_t，总能找到这样的 d，例如 d = (y*s + y*t)/2）。令 T = V \ S。
   考虑割 (S, T)。对于任何从 S 到 T 的边 (i,j)（即 i∈S, j∈T），有 y*i > d ≥ y*j。由对偶约束 y*_i - y*_j + w*_{ij} ≥ 0 和 w*{ij} ≥ 0，且由于 y*i > y*j，通常 w*{ij} 会为正以满足等式（在最优解中倾向于让 w*{ij} 尽可能小以最小化目标，但约束必须满足）。更关键的是，互补松弛条件告诉我们：**如果一条从 S 到 T 的边 (i,j) 满足 f*{ij} < c{ij}，那么 w*{ij}=0。但这会使得 y*i - y*j ≤ 0，与 y*i > y*j 矛盾。** 因此，**对于所有 (i,j) 从 S 到 T，必有 f*{ij} = c{ij}**。
   类似地，对于从 T 到 S 的边 (j,i)，如果 f*{ji} > 0，互补松弛条件要求 y*j - y*i + w*{ji} = 0。但由于 y*j ≤ d < y*i，这要求 w*{ji} > 0，进而由另一互补条件推出 f*{ji} = c{ji}。但我们可以证明，在最优流中，不会有流量从 T 流回 S，即所有从 T 到 S 的边上的流量 f*{ji} = 0。否则，净流入 S 的流量将不为零，违反 s 在 S 中且 t 不在 S 中的流量平衡。

4. 得出等价性：
   现在，计算通过割 (S,T) 的净流量，它等于从 S 到 T 的流量减去从 T 到 S 的流量。根据上面两点：

   • 从 S 到 T 的边：流量 = 容量。
   • 从 T 到 S 的边：流量 = 0。
     因此，净流量 = 割的容量。而这个净流量，根据流量守恒，恰好等于从 s 流出的总流量 v*。所以我们有：
     最大流值 v* = 割 (S,T) 的容量。
     结合弱对偶性（任何流 ≤ 任何割），我们证明了这个割 (S,T) 就是最小割，并且最大流值等于最小割容量。定理得证。

第四步：一个具体计算实例

考虑以下简单网络（s=1, t=4）：

边及容量： (1->2): 10, (1->3): 5, (2->3): 4, (2->4): 8, (3->4): 7

1. 建立最大流线性规划模型：
决策变量：f12, f13, f23, f24, f34。
目标：Maximize v = f12 + f13 （假设没有边流入1）。
约束：

• 容量：f12≤10, f13≤5, f23≤4, f24≤8, f34≤7。
• 流量守恒：
  顶点2：f12 = f23 + f24
  顶点3：f13 + f23 = f34
• 非负：所有 f ≥ 0。

2. 求解最大流（可使用单纯形法或观察）：
一个最优解：f12=9, f13=5, f23=4, f24=5, f34=9? 检查：顶点3流入=5+4=9，流出f34≤7，不可行。
正确求解：
尝试：f12=9, f13=5, f23=4, f24=5, f34=9? 不行，f34超容量。
我们需要满足容量。观察路径：
路径1: 1->2->4，可送 min(10,8)=8。
路径2: 1->3->4，可送 min(5,7)=5。
路径3: 1->2->3->4，但边2->3容量为4，3->4剩余容量(7-5)=2，所以此路可送 min(10-8, 4, 2)=2。
调整：先送路径1: 8单位，路径2: 5单位。此时 f12=8, f13=5, f24=8, f34=5。顶点2守恒：流入8=流出8+? 需要f23=0。顶点3守恒：流入5=流出5，成立。
再考虑路径3: 1(剩2)->2(但2已满? 24已8，容量8，已满。所以2无法接收更多)。实际上，从1出发的总容量是10+5=15，但瓶颈在中间。
用线性规划思想，写出约束：
顶点2: f12 - f23 - f24 = 0
顶点3: f13 + f23 - f34 = 0
代入容量约束，并最大化 v = f12+f13。
由顶点2约束：f24 = f12 - f23。
由顶点3约束：f34 = f13 + f23。
容量约束：
f12≤10, f13≤5, f23≤4, f24=f12-f23 ≤8, f34=f13+f23 ≤7, 且所有f≥0。
目标 v = f12+f13。
显然 f13 最大取5。f12最大受限于 f12 - f23 ≤8 和 f12≤10。为了最大化 f12+f13，我们令 f13=5。由 f34≤7 得 5+f23≤7 => f23≤2。由 f24≤8 得 f12 - f23 ≤8。我们希望 f12 大，令 f23=2（最大允许），则 f12 ≤ 8+f23=10。同时 f12≤10。所以可取 f12=10。检查：f24=10-2=8≤8，满足。f34=5+2=7≤7，满足。v=10+5=15。
得到最优流：f12=10, f13=5, f23=2, f24=8, f34=7。流量v=15。

3. 找出最小割：
根据我们的证明，可以从最优对偶变量或直接利用“饱和边”概念找割。饱和边（流量=容量）：f12=10（饱和），f13=5（饱和），f24=8（饱和），f34=7（饱和）。f23=2<4（不饱和）。
从源点 s=1 出发，寻找所有能通过非饱和边（f_{ij} < c_{ij}）或逆向有流量的边（f_{ji} > 0）到达的顶点。从1出发，边1->2饱和（不能走），1->3饱和（不能走）。所以只能走到1自己。因此集合 S = {1}。则割 (S, T) = ({1}, {2,3,4})。
割容量 = c12 + c13 = 10+5 = 15，等于最大流值。
验证：没有从2,3,4 回到1的边，所以反向流量为0。因此最小割容量为15，与最大流值相等。

第五步：总结

通过这个例子，我们完整地展示了：

1. 建模：将最大流问题形式化为线性规划。
2. 对偶：推导出其对偶问题，其最优值对应最小割容量。
3. 证明：利用线性规划强对偶定理和互补松弛条件，严格证明了最大流等于最小割。
4. 求解与验证：在一个具体实例上计算最大流，并利用定理找到对应的最小割，验证了等价性。

这个定理不仅是线性规划对偶理论的一个经典应用，也是网络流算法的基石（例如Ford-Fulkerson算法就是在不断寻找增广路直至找不到，此时由源点可达的顶点集合S就定义了一个最小割）。