基于线性规划的图最小费用流问题的容量缩放算法求解示例

我将为您讲解如何使用容量缩放算法求解图最小费用流问题。这是一个经典的网络流问题，在运输优化、通信网络等领域有广泛应用。

问题描述
考虑一个有向图G=(V,E)，其中：

• V是顶点集合，|V|=n
• E是边集合，|E|=m
• 每条边(i,j)∈E有容量u_ij和单位流量费用c_ij
• 每个顶点i有供需量b_i（b_i>0表示供应，b_i<0表示需求，且∑b_i=0）

目标：找到总费用最小的流分配方案，满足所有容量约束和流量平衡约束。

解题过程

步骤1：建立数学模型
最小费用流问题的线性规划模型为：

minimize ∑(c_ij × f_ij) 对所有边(i,j)
约束条件：
1. 流量平衡：对于每个顶点i，∑f_ji - ∑f_ij = b_i
3. 容量约束：0 ≤ f_ij ≤ u_ij

步骤2：理解容量缩放算法的核心思想
容量缩放算法是一种改进的最短路径增广算法，通过：

• 从较大的流量增量Δ开始，逐步缩小
• 在每個缩放阶段，只考虑剩余容量≥Δ的边
• 这样可以减少增广次数，提高效率

步骤3：算法初始化

1. 初始流f_ij = 0（零流）
2. 初始缩放参数Δ = 2^⌊log₂U⌋，其中U是最大容量
3. 计算初始剩余图G_f

步骤4：容量缩放阶段
对于每个缩放参数Δ：

1. 构建Δ剩余图：只包含剩余容量r_ij ≥ Δ的边
2. 在Δ剩余图中寻找从供应点到需求点的最短路径（按费用）
3. 沿找到的路径推送Δ单位的流量
4. 更新剩余容量和流值
5. 重复直到无法找到增广路径
6. Δ = Δ/2，进入下一阶段

步骤5：详细计算示例
考虑以下简单网络：

顶点：s(供应10)，t(需求-10)，中间顶点v
边：s→v(容量8,费用2)，s→t(容量5,费用1)，v→t(容量6,费用3)

初始化阶段：

• 初始流：f_sv=0, f_st=0, f_vt=0
• 最大容量U=8，Δ=2^⌊log₂8⌋=8

第一缩放阶段(Δ=8)：
构建Δ剩余图：只有s→v满足r_sv=8≥8
找不到从s到t的路径（s→v后无法到达t）
进入下一阶段

第二缩放阶段(Δ=4)：
Δ剩余图边：s→v(r=8≥4), s→t(r=5≥4), v→t(r=6≥4)
找到路径s→t，费用=1
推送4单位：f_st=4，剩余容量r_st=1
更新供需：s剩余6，t剩余-6

第三缩放阶段(Δ=2)：
Δ剩余图边：s→v(r=8≥2), s→t(r=1<2排除), v→t(r=6≥2)
找到路径s→v→t，总费用=2+3=5
推送2单位：f_sv=2, f_vt=2，剩余容量r_sv=6, r_vt=4
更新供需：s剩余4，t剩余-4

第四缩放阶段(Δ=1)：
Δ剩余图边：所有边都满足
找到路径s→t，费用=1
推送1单位：f_st=5，剩余容量r_st=0
更新供需：s剩余3，t剩余-3

找到路径s→v→t，总费用=5
推送3单位：f_sv=5, f_vt=5，剩余容量r_sv=3, r_vt=1
所有供需满足

步骤6：计算总费用
总费用 = 5×1 + 5×2 + 5×3 = 5 + 10 + 15 = 30

算法分析

• 时间复杂度：O(m²logU)
• 空间复杂度：O(m+n)
• 优势：相比基本的最短路径增广，减少了增广次数
• 适用：中等规模的网络流问题

容量缩放算法通过分阶段的流量推送策略，在保证最优性的同时提高了计算效率，是求解最小费用流问题的实用算法。