基于线性规划的图最小费用循环流问题求解示例 问题描述 考虑一个有向图 \( G = (V, E) \)，每条边 \( (i, j) \in E \) 有容量上限 \( u_ {ij} \)、单位流量成本 \( c_ {ij} \)，且图中无外部供给或需求（即所有节点的净流量为零）。最小费用循环流问题要求找到一个流分配方案，满足容量约束和流量守恒条件，并使总成本最小。该问题可建模为线性规划： \[ \text{最小化} \quad \sum_ {(i,j) \in E} c_ {ij} f_ {ij} \] \[ \text{满足} \quad \sum_ {j: (i,j) \in E} f_ {ij} - \sum_ {j: (j,i) \in E} f_ {ji} = 0 \quad \forall i \in V \] \[ 0 \leq f_ {ij} \leq u_ {ij} \quad \forall (i,j) \in E \] 其中 \( f_ {ij} \) 为边 \( (i,j) \) 上的流量。 解题步骤 问题建模 变量：每条边的流量 \( f_ {ij} \)。 目标：最小化总成本 \( \sum c_ {ij} f_ {ij} \)。 约束： 流量守恒（每个节点流入等于流出）； 容量约束（流量非负且不超过上限）。 构造对偶问题 引入对偶变量 \( \pi_ i \)（对应每个节点的流量守恒约束）。对偶问题为： \[ \text{最大化} \quad \sum_ {(i,j) \in E} \mu_ {ij} u_ {ij} \] \[ \text{满足} \quad \pi_ i - \pi_ j + \mu_ {ij} \leq c_ {ij}, \quad \mu_ {ij} \geq 0 \quad \forall (i,j) \in E \] 其中 \( \mu_ {ij} \) 为容量约束的对偶变量。对偶问题揭示了成本与节点势能 \( \pi_ i \) 的关系。 最优性条件（互补松弛） 原始可行：流量满足守恒和容量约束。 对偶可行：存在 \( \pi_ i \) 和 \( \mu_ {ij} \geq 0 \) 使得 \( c_ {ij} - (\pi_ i - \pi_ j) - \mu_ {ij} = 0 \)。 互补条件： 若 \( f_ {ij} = 0 \)，则 \( \mu_ {ij} \geq 0 \)； 若 \( 0 < f_ {ij} < u_ {ij} \)，则 \( \mu_ {ij} = 0 \)； 若 \( f_ {ij} = u_ {ij} \)，则 \( \mu_ {ij} \leq 0 \)（实际中 \( \mu_ {ij} \) 非负，故此时 \( \mu_ {ij} = 0 \) 且 \( c_ {ij} - (\pi_ i - \pi_ j) \geq 0 \)）。 负循环消除算法 步骤1 ：从任意可行流（如零流）开始。 步骤2 ：构造残量图 \( G_ f \)。对每条边 \( (i,j) \)： 若 \( f_ {ij} < u_ {ij} \)，添加正向边 \( (i,j) \)，残量容量 \( r_ {ij} = u_ {ij} - f_ {ij} \)，成本 \( c_ {ij} \)； 若 \( f_ {ij} > 0 \)，添加反向边 \( (j,i) \)，残量容量 \( r_ {ji} = f_ {ij} \)，成本 \( -c_ {ij} \)。 步骤3 ：在残量图中寻找负成本循环（即总成本为负的环）。若存在，沿循环增加流量： 对正向边，流量增加 \( \delta = \min\{r_ {ij}\} \)； 对反向边，流量减少 \( \delta \)。 步骤4 ：重复步骤2-3，直到残量图中无负成本循环。此时流为最优。 示例验证 设图有节点 \( \{1,2,3\} \)，边 \( (1,2) \)：成本2、容量3；\( (2,3) \)：成本1、容量2；\( (3,1) \)：成本-4、容量4。 初始零流：残量图中边成本与原图相同。检测到循环 \( 1 \to 2 \to 3 \to 1 \) 总成本 \( 2+1-4=-1 <0 \)。 沿循环增流 \( \delta = \min\{3,2,4\} = 2 \)，更新流量后重新检查残量图，直至无负循环。 关键点 最小费用循环流是网络流问题的基础，可通过线性规划或组合算法（如负循环消除）求解。 最优时，残量图中无负循环等价于对偶可行性条件。