基于线性规划的图最小费用循环流问题的多项式时间原始-对偶近似算法求解示例

我将为你讲解线性规划中的一个重要算法题目：如何用多项式时间的原始-对偶近似算法求解图最小费用循环流问题。这个算法基于线性规划和对偶理论，巧妙地将最小费用循环流问题转化为一系列最小费用流子问题求解。

题目描述

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

• 每个顶点v∈V有一个供需值b(v)，满足∑v∈V b(v)=0
• 每条边e∈E有一个容量上限u(e) ≥ 0
• 每条边e∈E有一个费用c(e) ∈ ℝ

最小费用循环流问题的目标是找到满足以下条件的流f: E→ℝ：

1. 流守恒：∀v∈V，∑(e进入v) f(e) - ∑(e离开v) f(e) = b(v)
2. 容量限制：∀e∈E，0 ≤ f(e) ≤ u(e)
3. 总费用最小化：∑e∈E c(e)·f(e) → min

这个问题是最小费用流问题的推广（最小费用流要求b(s)=-b(t)=F，其他顶点b(v)=0），而最小费用循环流允许任意顶点的供需分布。

解题过程

步骤1：建立原始线性规划模型

首先，我们将问题形式化为线性规划：

原始问题（Primal）：

minimize    ∑e∈E c(e)·f(e)
subject to:
    ∀v∈V: ∑e∈δ+(v) f(e) - ∑e∈δ-(v) f(e) = b(v)  (流守恒)
    ∀e∈E: 0 ≤ f(e) ≤ u(e)                      (容量约束)

其中δ+(v)表示离开v的边，δ-(v)表示进入v的边。

步骤2：构造对偶线性规划

为流守恒约束引入对偶变量π(v)（顶点势），为容量约束f(e) ≤ u(e)引入对偶变量α(e) ≥ 0，为下界约束f(e) ≥ 0引入对偶变量β(e) ≥ 0。

对偶问题（Dual）：

maximize    ∑v∈V b(v)·π(v) - ∑e∈E u(e)·α(e)
subject to:
    ∀e=(u,v)∈E: π(u) - π(v) - α(e) + β(e) = c(e)  (对偶约束)
    ∀e∈E: α(e) ≥ 0, β(e) ≥ 0

我们可以消去β(e)：由于β(e) = c(e) - π(u) + π(v) + α(e) ≥ 0，且β(e)不直接出现在目标函数中，我们可以选择最优解中β(e)尽可能小，即设β(e)=max{0, c(e)-π(u)+π(v)+α(e)}，但更常用的处理是重写约束。

简化对偶约束：
从对偶约束π(u)-π(v)-α(e)=c(e)-β(e)，且β(e)≥0，可得：
π(u)-π(v)-α(e) ≤ c(e)

于是等价的对偶问题为：

maximize    ∑v∈V b(v)·π(v) - ∑e∈E u(e)·α(e)
subject to:
    ∀e=(u,v)∈E: π(u) - π(v) - α(e) ≤ c(e)
    ∀e∈E: α(e) ≥ 0

步骤3：互补松弛条件

原始-对偶算法的核心是满足互补松弛条件：

1. 原始可行性：f满足流守恒和容量约束
2. 对偶可行性：(π,α)满足对偶约束
3. 互补松弛：
   (a) 如果f(e) < u(e)，则α(e) = 0
   (b) 如果f(e) > 0，则π(u)-π(v)-α(e) = c(e)

这意味着：

• 非饱和边（f(e)<u(e)）必须有α(e)=0，此时若f(e)>0则π(u)-π(v)=c(e)
• 饱和边（f(e)=u(e)）可能有α(e)>0，但需要满足π(u)-π(v)-α(e)=c(e)

步骤4：原始-对偶算法框架

算法思想：从零流f=0开始，不断调整流和对偶变量，使对偶目标值增加，同时保持互补松弛条件。

算法步骤：

1. 初始化：

   • 设f(e)=0，对所有e∈E
   • 设π(v)=0，对所有v∈V
   • 设α(e)=0，对所有e∈E
     （验证：此时对偶可行，因为π(u)-π(v)-α(e)=0 ≤ c(e)）

2. 定义边分类：
   根据当前对偶解(π,α)，将边分为三类：

   • 紧边：满足π(u)-π(v)-α(e)=c(e)
   • 非紧边：π(u)-π(v)-α(e)<c(e)

3. 构造辅助图：
   只考虑紧边，但根据当前流值进一步分类：

   • 如果f(e)<u(e)，则加入正向边(u,v)，费用为c(e)-π(u)+π(v)=0
   • 如果f(e)>0，则加入反向边(v,u)，费用为π(v)-π(u)-c(e)=-c(e)+π(u)-π(v)=0
     （注意：由于是紧边，c(e)-π(u)+π(v)=-α(e)≤0，但这里实际上在辅助图中我们设费用为0）

4. 计算最短距离：
   在辅助图中，从某个源点集S（供需不平衡的顶点）出发，计算到所有顶点的最短距离d(v)（因为边权非负，可用Dijkstra算法）

5. 更新对偶变量：
   设θ>0为步长，更新：

   • π(v) ← π(v) - θ·d(v) （对某些顶点）
   • α(e) ← α(e) + θ·(d(v)-d(u)) （需保持非负）

6. 沿增广路调整流：
   在更新的辅助图中找到从供给顶点到需求顶点的路径，沿路径增广流，保持互补松弛

7. 重复直到所有供需满足

步骤5：多项式时间实现细节

为了确保多项式时间，需要：

1. 缩放技术：从较大的θ开始，逐步缩小
2. 费用缩减：将边费用替换为c'(e)=c(e)-π(u)+π(v)，使得所有边费用非负
3. 增量调整：每次只调整少量流

简化版本算法流程：

输入：图G=(V,E), 供需b(v), 容量u(e), 费用c(e)
输出：最小费用循环流f

1. 初始化: f=0, π=0, 设置费用容限ε>0
2. while 存在未满足的供需 do
3.   构造残量网络G_f，边费用为c_π(e)=c(e)-π(u)+π(v)（约化费用）
4.   在G_f中，将所有满足c_π(e)<-ε的边设为不可用（暂时）
5.   在可用边构成的子图中，找到从供给顶点到需求顶点的最短路径P
6.   计算增广量δ=min{ min_{e∈P} u_f(e), |未满足供给|, |未满足需求| }
7.   沿P增广δ单位的流
8.   更新供需b(v)
9.   更新势π(v): 对可达顶点，π(v)=π(v)-d(v)（d(v)是最短距离）
10. end while

步骤6：算法正确性与复杂度

正确性：算法始终保持互补松弛条件，当所有供需满足时，原始可行。由互补松弛定理，此时原始解和对偶解都是最优的。

多项式时间复杂度：

• 每次迭代至少满足一个顶点的供需
• 每个顶点最多被处理|V|次
• 每次需要运行一次最短路径算法（如Dijkstra，O(|E|+|V|log|V|)）
• 总复杂度：O(|V|·(|E|+|V|log|V|))

这是伪多项式时间，可通过容量缩放改进为强多项式时间。

步骤7：实例演示

考虑简单例子：

顶点：s（供给2），t（需求2），中间顶点v
边：s→v（容量2，费用1），v→t（容量2，费用1），s→t（容量2，费用3）

初始：f=0, π=0

1. 构造残量网络，约化费用c_π=c
2. 最短路径：s→v→t，费用2
3. 增广2单位流
4. 更新供需：s剩余0，t剩余0
5. 总费用：2×1 + 2×1 = 4（最优解）

如果直接用s→t路径，费用为2×3=6，不是最优。

算法特点

1. 原始-对偶框架：同时维护原始流和对偶势
2. 保持互补松弛：确保解的最优性
3. 增量增广：每次沿最短路径增广
4. 多项式时间：通过巧妙设计避免指数级搜索

这个算法体现了线性规划对偶理论在图优化问题中的强大应用，是网络流算法设计的经典范例。