基于线性规划的图最小费用流问题的原始-对偶近似算法求解示例
问题描述
考虑一个带权有向图 \(G = (V, E)\)，每条边 \(e \in E\) 有容量 \(u_e \geq 0\) 和单位流量费用 \(c_e \in \mathbb{R}\)。图中包含源点 \(s\) 和汇点 \(t\)，需从 \(s\) 到 \(t\) 输送 \(d\) 单位流量，目标是在满足容量约束的前提下最小化总费用。该问题可建模为线性规划：
\[\begin{aligned} \min \quad & \sum_{e \in E} c_e f_e \\ \text{s.t.} \quad & \sum_{e \in \delta^+(v)} f_e - \sum_{e \in \delta^-(v)} f_e = \begin{cases} d & \text{若 } v = s \\ -d & \text{若 } v = t \\ 0 & \text{否则} \end{cases} \\ & 0 \leq f_e \leq u_e \quad (\forall e \in E) \end{aligned} \]
其中 \(f_e\) 表示边 \(e\) 的流量，\(\delta^+(v)\) 和 \(\delta^-(v)\) 分别表示 \(v\) 的出边和入边集合。
原始-对偶方法的核心思想
- 构造对偶问题：通过引入势函数（对偶变量）\(p_v\)（\(v \in V\)）和边上的冗余变量 \(r_e\)，得到对偶线性规划：
\[ \begin{aligned} \max \quad & d \cdot (p_s - p_t) - \sum_{e \in E} u_e r_e \\ \text{s.t.} \quad & p_v - p_w - r_e \leq c_e \quad (\forall e = (v, w) \in E) \\ & r_e \geq 0 \quad (\forall e \in E) \end{aligned} \]
互补松弛条件为：
- 若 \(f_e > 0\)，则 \(p_v - p_w - r_e = c_e\)；
- 若 \(r_e > 0\)，则 \(f_e = u_e\)。
- 原始-对偶流程：
- 初始化零流量（\(f_e = 0\)）和零势函数（\(p_v = 0\)）。
- 逐步增加流量，同时调整对偶变量 \(p_v\) 和 \(r_e\)，始终保持对偶可行性和互补松弛条件。
逐步求解过程
假设图包含顶点 \(V = \{s, a, t\}\)，边集 \(E = \{(s,a), (a,t), (s,t)\}\)，参数如下：
| 边 \(e\) | 容量 \(u_e\) | 费用 \(c_e\) |
|---|---|---|
| \((s,a)\) | 3 | 2 |
| \((a,t)\) | 2 | 1 |
| \((s,t)\) | 2 | 5 |
| 需求流量 \(d = 3\)。 |
步骤1：初始化
- 原始变量：所有流量 \(f_e = 0\)。
- 对偶变量：所有 \(p_v = 0\)，\(r_e = 0\)。
- 检验对偶可行性：对任意边 \(e = (v,w)\)，条件 \(p_v - p_w - r_e \leq c_e\) 化为 \(0 \leq c_e\)，成立。
步骤2：构造剩余图与最短路径增广
-
剩余图构造：
- 若边 \(e = (v,w)\) 满足 \(f_e < u_e\)，则添加正向边 \((v,w)\)，容量 \(u_e - f_e\)，费用 \(c_e - (p_v - p_w)\)。
- 若 \(f_e > 0\)，则添加反向边 \((w,v)\)，容量 \(f_e\)，费用 \(-[c_e - (p_v - p_w)]\)。
初始时所有边流量为零，剩余图与原图一致，边费用为原费用 \(c_e\)。
-
寻找最短路径：
在剩余图中以费用为边权求 \(s \to t\) 的最短路径。路径 \(s \to a \to t\) 的费用为 \(2 + 1 = 3\)，路径 \(s \to t\) 的费用为 5。选择 \(s \to a \to t\)。 -
增广流量：
- 路径 \(s \to a \to t\) 上最小剩余容量为 \(\min(3, 2) = 2\)。
- 沿该路径推送 2 单位流量，更新：
- \(f_{(s,a)} = 2\)，\(f_{(a,t)} = 2\)。
步骤3：更新对偶变量
-
调整势函数：
在增广后的剩余图中，以费用为边权重新计算 \(s\) 到各顶点的最短路径距离（单位：费用）：- \(\text{dist}(s) = 0\)
- \(\text{dist}(a) = 2\)（通过边 \((s,a)\)，费用 2）
- \(\text{dist}(t) = 3\)（通过路径 \(s \to a \to t\)，费用 2+1=3）
更新势函数：\(p_v \leftarrow p_v + \text{dist}(v)\)，即： - \(p_s = 0\)，\(p_a = 2\)，\(p_t = 3\)。
-
更新冗余变量 \(r_e\)：
根据对偶约束 \(r_e = \max(0, p_v - p_w - c_e)\) 计算：- \(e = (s,a)\)：\(r_e = \max(0, 0 - 2 - 2) = 0\)
- \(e = (a,t)\)：\(r_e = \max(0, 2 - 3 - 1) = 0\)
- \(e = (s,t)\)：\(r_e = \max(0, 0 - 3 - 5) = 0\)
所有 \(r_e = 0\)，对偶目标值 \(d \cdot (p_s - p_t) - \sum u_e r_e = 3 \cdot (0 - 3) = -9\)。
步骤4：第二次增广
-
构造剩余图：
- 边 \((s,a)\) 剩余容量 \(3 - 2 = 1\)，费用 \(2 - (0 - 2) = 4\)。
- 边 \((a,t)\) 已满（剩余容量 0），不添加正向边；但因 \(f_{(a,t)} > 0\)，添加反向边 \((t,a)\)，容量 2，费用 \(-[1 - (2 - 3)] = -0 = 0\)。
- 边 \((s,t)\) 剩余容量 2，费用 \(5 - (0 - 3) = 8\)。
剩余图包含：\((s,a)\)（费用 4）、\((t,a)\)（费用 0）、\((s,t)\)（费用 8）。
-
寻找最短路径：
路径 \(s \to t\) 费用 8，路径 \(s \to a \to t\) 因 \((a,t)\) 无正向边不可行。但可通过 \(s \to a \to t\) 的反向边调整？实际需检查剩余图中从 \(s\) 到 \(t\) 的路径：- \(s \to a\)（费用 4）→ 仅能走反向边 \((a,t)\)？反向边是 \((t,a)\)，不可从 \(a\) 到 \(t\)。
唯一可行路径为 \(s \to t\)（费用 8）。
- \(s \to a\)（费用 4）→ 仅能走反向边 \((a,t)\)？反向边是 \((t,a)\)，不可从 \(a\) 到 \(t\)。
-
增广流量：
沿 \(s \to t\) 推送剩余需求流量 \(3 - 2 = 1\) 单位（容量允许 2），更新 \(f_{(s,t)} = 1\)。总流量现为 3，满足需求。
步骤5：验证最优性
最终流量：\(f_{(s,a)} = 2\)，\(f_{(a,t)} = 2\)，\(f_{(s,t)} = 1\)。
总费用：\(2 \times 2 + 2 \times 1 + 1 \times 5 = 11\)。
检查对偶可行性：
- 势函数 \(p = [0, 2, 3]\)，\(r_e = 0\) 仍成立。
- 对偶目标值 \(3 \cdot (0 - 3) = -9\)，与原始目标值 11 的差值由互补松弛条件解释，满足最优性。
算法总结
原始-对偶方法通过交替更新原始流与对偶势函数，逐步逼近最优解。其优势在于避免直接求解线性规划，而是利用最短路径等图算法高效迭代，适用于大规模最小费用流问题。