基于线性规划的图最小费用循环流问题求解示例
题目描述
考虑一个带权有向图 \(G = (V, E)\)，其中每条边 \((i, j) \in E\) 有三个属性：
- 容量上界 \(u_{ij}\)（允许流量的最大值）
- 容量下界 \(l_{ij}\)（必须满足的最小流量，通常为非负）
- 单位流量成本 \(c_{ij}\)
同时，每个顶点 \(i \in V\) 有一个净需求 \(b_i\)（若 \(b_i > 0\) 表示供应量，\(b_i < 0\) 表示需求量，且需满足 \(\sum_{i \in V} b_i = 0\)）。最小费用循环流问题要求在所有顶点供需平衡与边容量约束下，找到总成本最小的可行流。
问题建模
设决策变量 \(x_{ij}\) 表示边 \((i, j)\) 上的流量，则线性规划模型为：
\[\text{最小化} \quad \sum_{(i,j) \in E} c_{ij} x_{ij} \]
\[ \text{约束条件} \quad \sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = b_i \quad \forall i \in V \quad \text{(流量平衡)} \]
\[ l_{ij} \leq x_{ij} \leq u_{ij} \quad \forall (i,j) \in E \quad \text{(容量约束)} \]
解题步骤
-
问题可行性检查
若存在 \(l_{ij} > u_{ij}\) 的边，问题无解。进一步，可通过构造辅助网络验证供需平衡与容量下界的兼容性（例如，若所有 \(l_{ij} = 0\)，则需满足 \(b_i\) 组成的供应-需求网络可行）。 -
消除容量下界
通过变量替换 \(x'_{ij} = x_{ij} - l_{ij}\)，将下界转化为非负约束：- 新流量变量范围： \(0 \leq x'_{ij} \leq u_{ij} - l_{ij}\)
- 目标函数变为： \(\sum c_{ij} x'_{ij} + \sum c_{ij} l_{ij}\)（常数项可忽略）
- 流量平衡约束调整为：
\[ \sum_{j} x'_{ij} - \sum_{j} x'_{ji} = b_i - \sum_{j} l_{ij} + \sum_{j} l_{ji} = b'_i \]
其中 $ b'_i $ 为调整后的净需求。
-
应用最小费用流算法
使用单纯形法或专用算法（如网络单纯形法）求解转化后的问题：- 初始基解构造：添加人工变量或利用图结构（如生成树）构造初始可行流。
- 迭代优化：在残差网络中寻找负费用增广环，沿环调整流量以降低总成本，直到无负费用环存在（最优性条件）。
-
恢复原问题解
将解 \(x'_{ij}\) 逆变换为 \(x_{ij} = x'_{ij} + l_{ij}\)，并验证是否满足原约束。
实例演示
考虑图 with \(V = \{1,2,3\}\)，边集与参数如下：
- 边 (1,2): \(l=2, u=5, c=3\)
- 边 (2,3): \(l=1, u=4, c=1\)
- 边 (3,1): \(l=0, u=3, c=2\)
顶点净需求： \(b_1 = 2, b_2 = -1, b_3 = -1\)
- 变量替换：令 \(x'_{12} = x_{12} - 2\)，\(x'_{23} = x_{23} - 1\)，\(x'_{31} = x_{31}\)
- 新约束：
- \(0 \leq x'_{12} \leq 3\)，\(0 \leq x'_{23} \leq 3\)，\(0 \leq x'_{31} \leq 3\)
- 新净需求：
\(b'_1 = 2 - 2 + 0 = 0\)
\(b'_2 = -1 + 2 - 1 = 0\)
\(b'_3 = -1 + 1 - 0 = 0\)
- 问题转化为无下界的最小费用循环流，目标函数为 \(3x'_{12} + x'_{23} + 2x'_{31}\)。
- 通过寻找负费用增广环（如环 1→2→3→1 的费用为 3+1+2=6>0，无负环），初始流 \(x'_{ij} = 0\) 即为最优。
- 还原得原问题解： \(x_{12} = 2\)，\(x_{23} = 1\)，\(x_{31} = 0\)，总成本为 \(3 \times 2 + 1 \times 1 + 2 \times 0 = 7\).
关键点
容量下界的处理是核心技巧，通过变量平移将问题转化为标准形式，再利用网络流理论的高效算法求解。