基于线性规划的图最小费用最大流问题求解示例
题目描述
在图论中，最小费用最大流问题（Min-Cost Max-Flow）旨在从源点（s）向汇点（t）输送尽可能多的流量，同时使总运输成本最小。给定一个有向图，每条边有容量限制（最大流量）和单位流量成本。目标是找到一种流量分配方案，在达到最大流量的前提下，总费用最小。例如，在物流网络中，需以最低成本实现从仓库到市场的最优货物运输。
解题过程
- 问题建模
- 设图 \(G = (V, E)\)，其中 \(V\) 为节点集合，\(E\) 为边集合。
- 每条边 \((i, j) \in E\) 有容量 \(u_{ij}\)（非负实数）和单位费用 \(c_{ij}\)（实数）。
- 变量 \(x_{ij}\) 表示边 \((i, j)\) 上的流量。
- 目标函数为最小化总费用：
\[ \min \sum_{(i,j) \in E} c_{ij} x_{ij} \]
- 约束包括：
- 流量守恒（除源点s和汇点t外，流入等于流出）：
\[ \sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = \begin{cases} v & (i = s) \\ -v & (i = t) \\ 0 & (\text{其他节点}) \end{cases} \]
其中 $ v $ 表示从s到t的总流量。
- **容量限制**：
\[ 0 \leq x_{ij} \leq u_{ij}, \quad \forall (i,j) \in E \]
- 注意：\(v\) 本身也是变量，需通过优化确定其最大值（最大流），同时最小化成本。
- 线性规划形式化
将问题转化为标准线性规划：- 变量：\(x_{ij}\)（每条边的流量）和 \(v\)（总流量）。
- 目标：
\[ \min \sum_{(i,j) \in E} c_{ij} x_{ij} \]
- 约束：
- 流量守恒约束（线性等式）。
- 容量约束（线性不等式）。
- 关键点：模型本身是线性的，可直接用单纯形法等求解。
-
求解步骤
步骤1：初始化可行解- 从零流量开始（\(x_{ij} = 0\)），此时 \(v = 0\)。
- 或使用辅助问题（如最大流问题）先找到一组可行流。
步骤2：构造残留网络
- 基于当前流量分配构造残留图 \(G_f\)：
- 对每条边 \((i, j)\)，在残留图中添加正向边（剩余容量 \(u_{ij} - x_{ij}\)，费用 \(c_{ij}\)）和反向边（容量 \(x_{ij}\)，费用 \(-c_{ij}\)）。
- 残留网络用于寻找增广路径（增加流量并调整费用）。
步骤3：寻找最小费用增广路径
- 在残留网络中，使用最短路径算法（如Bellman-Ford或Dijkstra，若费用非负）找到从s到t的最小费用路径。
- 若存在负费用边，需用Bellman-Ford算法处理负权。
步骤4：增广流量
- 沿找到的路径增加流量，增量为路径上的最小剩余容量。
- 更新当前流量分配和总流量 \(v\)。
步骤5：重复直至最优
- 重复步骤2-4，直到无法找到从s到t的增广路径（此时达到最大流）。
- 最终流量分配即是最小费用最大流。
-
示例验证
考虑简单图：节点 \(V = \{s, a, t\}\)，边 \(E = \{(s,a): u=5, c=2), (a,t): u=3, c=1), (s,t): u=2, c=4\}\)。- 初始流量为0。
- 第一次迭代：在残留网络中找到路径 \(s \to a \to t\)（费用3），增广流量3（受限于边 \(a \to t\) 的容量）。
- 第二次迭代：找到路径 \(s \to t\)（费用4），增广流量2。
- 总流量 \(v = 5\)，总费用 \(3 \times 3 + 2 \times 4 = 17\)。
- 验证无更优路径，解为最优。
-
算法特性
- 正确性：基于线性规划对偶理论（最小费用流问题的对偶是最短路问题）。
- 复杂度：若使用Dijkstra算法，复杂度为 \(O(F \cdot |E| \log |V|)\)，其中 \(F\) 为最大流值。
通过以上步骤，可系统解决最小费用最大流问题，兼顾流量最大化与成本最小化。