基于线性规划的图最小费用流问题的原始-对偶方法求解示例 我将为您讲解图最小费用流问题的原始-对偶方法。这是一种高效的组合优化算法，结合了线性规划的对偶理论和图论的最短路径算法。 问题描述 考虑一个有向图G=(V,E)，其中： V是顶点集合，|V|=n E是边集合，|E|=m 每条边(i,j)∈E有容量u_ ij≥0和单位流量成本c_ ij 每个顶点i∈V有净需求b_ i（b_ i>0表示供应，b_ i<0表示需求，且∑b_ i=0） 我们需要找到满足所有顶点净需求的最小总成本流量分配。 原始问题线性规划模型 最小化：∑_ {(i,j)∈E} c_ ij × f_ ij 约束： ∑ {j:(i,j)∈E} f_ ij - ∑ {j:(j,i)∈E} f_ ji = b_ i, ∀i∈V （流量平衡） 0 ≤ f_ ij ≤ u_ ij, ∀(i,j)∈E （容量约束） 对偶问题 引入对偶变量： π_ i：顶点i的势（对应流量平衡约束） α_ ij ≥ 0：边(i,j)的冗余对偶变量 对偶问题： 最大化：∑ {i∈V} b_ i × π_ i - ∑ {(i,j)∈E} u_ ij × α_ ij 约束：α_ ij ≥ max(0, c_ ij - (π_ i - π_ j)), ∀(i,j)∈E 互补松弛条件 最优解满足： 如果f_ ij > 0，则c_ ij - (π_ i - π_ j) + α_ ij = 0 如果f_ ij < u_ ij，则α_ ij = 0 原始-对偶算法步骤 步骤1：初始化 设置初始势π_ i=0, ∀i∈V 设置初始流量f_ ij=0, ∀(i,j)∈E 计算简化成本：c_ ij^π = c_ ij - (π_ i - π_ j) 步骤2：构建剩余图 创建剩余图G_ f=(V,E_ f)，其中： 对于每条边(i,j)∈E： 如果f_ ij < u_ ij，添加前向边(i,j)， 容量u_ ij - f_ ij，成本c_ ij^π 如果f_ ij > 0，添加反向边(j,i)， 容量f_ ij，成本-c_ ij^π 步骤3：检查最优性 如果所有边满足c_ ij^π ≥ 0，则当前解最优。 否则，转到步骤4。 步骤4：寻找改进路径 在剩余图中找到从供应顶点到需求顶点的负成本路径： 使用Bellman-Ford算法找到最短路径 路径的简化成本必须为负 步骤5：更新流量 沿找到的路径推送尽可能多的流量： 推送量δ = min(路径上的最小容量，未满足的需求) 更新路径上所有边的流量 步骤6：更新势 如果还有未满足的需求，更新势函数： 使用最短路径距离d_ i（从供应顶点出发） 新势：π_ i' = π_ i + d_ i × ε，其中ε是步长参数 转到步骤2 具体数值示例 考虑简单网络： 顶点：{s,a,t}，其中b_ s=2（供应），b_ a=0，b_ t=-2（需求） 边：(s,a)：容量2，成本1；(a,t)：容量2，成本1；(s,t)：容量2，成本3 迭代1： 初始势：π_ s=0, π_ a=0, π_ t=0 简化成本：c_ sa^π=1, c_ at^π=1, c_ st^π=3 剩余图：所有边前向，成本与原成本相同 最短路径：s→a→t，成本2 <直接路径成本3 推送流量：δ=2，更新f_ sa=2, f_ at=2 总成本=2×1+2×1=4 验证最优性： 剩余图中，只有s→t剩余，成本3>0，满足最优性条件。 算法特点 结合了原始可行性和对偶可行性 每次迭代保证对偶可行性 通过势函数调整简化成本 最终同时达到原始可行性和对偶可行性 这种方法比单纯形法更高效，特别适合大规模网络流问题。