基于线性规划的图最小费用流问题的网络单纯形法求解示例

我将为您详细讲解网络单纯形法求解最小费用流问题的完整过程。

问题描述
考虑一个带权有向图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表示转运点）
• 总供给等于总需求：Σb_i=0

目标：找到满足所有顶点供需约束且总运输费用最小的流分布。

解题过程

步骤1：建立线性规划模型
最小费用流问题可表述为：

minimize Σc_ij·x_ij (对所有边(i,j))
subject to:
Σx_ij - Σx_ji = b_i, ∀i∈V (流量守恒)
0 ≤ x_ij ≤ u_ij, ∀(i,j)∈E (容量约束)

步骤2：构造初始基解
网络单纯形法需要构造一个生成树作为初始基：

1. 添加人工顶点和边：引入人工顶点w，对每个顶点i添加边(w,i)
2. 设置人工边费用：设人工边费用为足够大的正数M
3. 初始基：选择所有人工边构成初始生成树
4. 初始流：x_wi = max{b_i, 0}（满足供需约束）

步骤3：计算对偶变量（节点势）
对生成树中的每条边(i,j)，求解对偶变量π：

π_i - π_j = c_ij (对树边(i,j))

通常设某个顶点（如根节点）的势π_root=0，然后通过树遍历计算其他顶点势。

步骤4：计算简约费用
对于非基边(i,j)，计算简约费用：

c̄_ij = c_ij - (π_i - π_j)

如果所有c̄_ij ≥ 0，当前解已是最优，算法终止。

步骤5：确定进基边
选择简约费用最小的边进入基：

(i,j) = argmin{c̄_kl | c̄_kl < 0, (k,l)为非基边}

步骤6：确定离基边和流调整量

1. 在生成树中加入进基边(i,j)会形成唯一环
2. 确定环的方向：与进基边(i,j)同向为正方向
3. 计算调整量θ：
   • 正向边：θ ≤ u_kl - x_kl
   • 反向边：θ ≤ x_kl
4. 取最小θ值，对应的边为离基边

步骤7：基变换和流更新

1. 从生成树中移除离基边，加入进基边
2. 沿环更新流量：
   • 正向边：x_kl ← x_kl + θ
   • 反向边：x_kl ← x_kl - θ

步骤8：迭代优化
重复步骤3-7，直到所有简约费用非负，得到最优解。

实例演示
考虑简单网络：顶点{1,2,3}，边(1,2): 容量5、费用2，(2,3): 容量4、费用1，(1,3): 容量3、费用4
供需：b₁=3, b₂=0, b₃=-3

初始生成树：人工边(w,1),(w,2),(w,3)
经过网络单纯形法迭代：

• 第一次迭代：边(1,2)进基，人工边(w,2)离基
• 第二次迭代：边(2,3)进基，人工边(w,3)离基
  最优解：x₁₂=3, x₂₃=3, 总费用=3×2+3×1=9

网络单纯形法比普通单纯形法更高效，特别适合求解大规模最小费用流问题。