基于线性规划的图最小费用流问题的对偶方法求解示例

我将为您讲解如何使用对偶方法求解图的最小费用流问题。这个问题在物流运输、通信网络等领域有广泛应用。

问题描述
考虑一个有向图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）

目标：在满足容量约束和流量平衡的条件下，找到总费用最小的流。

数学模型
原始问题：
min ∑(c_ij × x_ij) 对所有边(i,j)
约束：

1. ∑(x_ji) - ∑(x_ij) = b_i 对所有顶点i（流量平衡）
2. 0 ≤ x_ij ≤ u_ij 对所有边(i,j)（容量约束）

解题过程

第一步：构造对偶问题
对原始问题的每个约束引入对偶变量：

• 对流量平衡约束引入变量π_i（无符号限制）
• 对容量约束引入变量α_ij ≥ 0

对偶问题：
max ∑(b_i × π_i) - ∑(u_ij × α_ij)
约束：
π_i - π_j - α_ij ≤ c_ij 对所有边(i,j)
α_ij ≥ 0 对所有边(i,j)

第三步：简化对偶问题
通过变量替换，我们可以简化对偶问题。令w_ij = α_ij + c_ij - (π_i - π_j)，则：
max ∑(b_i × π_i) - ∑(u_ij × max{0, π_i - π_j - c_ij})
约束：无（π_i无限制）

第四步：对偶问题的经济学解释

• π_i可解释为顶点i的势或价格
• 对偶目标函数表示净收益：供应点收益减去需求点成本，再减去容量使用成本
• 条件π_i - π_j ≤ c_ij表示在最优解中，如果流量未达上限，则势的差不超过运输成本

第五步：互补松弛条件
最优解满足：

1. 如果x_ij > 0，则π_i - π_j = c_ij + α_ij
2. 如果x_ij < u_ij，则α_ij = 0
3. 如果0 < x_ij < u_ij，则π_i - π_j = c_ij

第六步：对偶方法求解步骤

1. 初始化：从任意可行流开始（如零流），设置初始势π_i=0
2. 计算约化费用：对于每条边(i,j)，计算c̃_ij = c_ij - (π_i - π_j)
3. 最优性检验：如果对所有边满足：
   • 如果c̃_ij > 0，则x_ij = 0
   • 如果c̃_ij < 0，则x_ij = u_ij
   • 如果c̃_ij = 0，则0 ≤ x_ij ≤ u_ij
     则当前解最优
4. 更新势和流：如果最优性条件不满足，选择违反的边，沿该边调整流量，并更新相应顶点的势
5. 迭代：重复步骤2-4直到满足最优性条件

第七步：具体算例
考虑简单网络：顶点{1,2,3}，边：

• (1,2)：容量5，费用2
• (2,3)：容量5，费用3
• (1,3)：容量10，费用6
  供需：b₁=5, b₂=0, b₃=-5

迭代过程：

1. 初始：零流，π=[0,0,0]
2. 约化费用：c̃₁₂=2, c̃₂₃=3, c̃₁₃=6
3. 选择c̃最小的负费用路径1→2→3，发送5单位流量
4. 更新流：x₁₂=5, x₂₃=5, x₁₃=0
5. 更新势：π₁=0, π₂=-2, π₃=-5
6. 重新计算约化费用：c̃₁₂=0, c̃₂₃=0, c̃₁₃=1
7. 满足最优性条件，找到最优解

第八步：结果分析
最优流：x₁₂=5, x₂₃=5, x₁₃=0
总费用：5×2 + 5×3 = 25
对偶变量：π=[0,-2,-5]提供了每个顶点的影子价格

这种方法通过利用对偶理论，将最小费用流问题转化为势函数的优化问题，在理论和计算上都具有重要意义。