基于线性规划的图最小费用流问题的成本缩放算法求解示例 我将为您讲解最小费用流问题中的成本缩放（Cost Scaling）算法。这个算法通过逐步调整成本精度，将问题分解为一系列更易求解的子问题。 问题描述 考虑一个有向图G=(V,E)，其中： V是顶点集合，|V|=n E是边集合，|E|=m 每条边e∈E有容量u(e)≥0和成本c(e)∈ℤ 每个顶点v∈V有需求b(v)∈ℤ，且∑b(v)=0 目标：找到满足所有顶点需求且总成本最小的流。 算法核心思想 成本缩放算法通过二进制表示的成本精度缩放，从粗精度到细精度逐步逼近最优解。算法维护ε-最优解，其中ε随迭代减半。 算法步骤详解 步骤1：初始化 1.1 计算最大成本：C = max{|c(e)| : e∈E} 1.2 设置初始精度：ε = C（最粗精度） 1.3 初始化流：从零流开始，f(e)=0 ∀e∈E 1.4 计算缩放因子：Δ = 2^⌊log₂C⌋（2的最大幂次≤C） 步骤2：成本缩放主循环 当ε ≥ 1/n时重复： 2.1 ε-细化：将当前ε-最优解改进为(ε/2)-最优解 2.2 价格函数维护：维护顶点势函数π:V→ℝ，使得约化成本非负 2.3 推流操作：沿约化成本为负的边推送流 2.4 重标价操作：当无法推流时调整顶点势函数 2.5 精度更新：ε ← ε/2 步骤3：推流操作细节 对于每个顶点v∈V： 3.1 检查超额流：超额e(v) = ∑f(wv) - ∑f(vw) - b(v) 3.2 如果e(v)>0（v有超额）： 3.3 寻找边(v,w)满足约化成本cπ(v,w)=c(v,w)+π(v)-π(w) <0 3.4 沿(v,w)推送流：推送量δ=min{e(v), u(v,w)-f(v,w)} 3.5 更新流：f(v,w)←f(v,w)+δ，e(v)←e(v)-δ 步骤4：重标价操作 当顶点v有超额但无可行的推流边时： 4.1 计算最小约化成本：min{cπ(v,w) | (v,w)∈E, f(v,w) <u(v,w)} 4.2 调整势函数：π(v)←π(v)-min{cπ(v,w)}-ε 4.3 这保证了至少有一条边变得可行 数学基础 ε-最优性条件：存在势函数π使得cπ(e)≥-ε ∀e∈E 约化成本：cπ(v,w)=c(v,w)+π(v)-π(w) 最优性检验：当ε <1/n时，流是最优的（因成本为整数） 算法复杂度分析 迭代次数：O(log(nC)) 每轮推流操作：O(n²m) 总复杂度：O(n²m log(nC)) 示例演示 考虑简单网络：顶点{1,2,3}，边(1,2):容量5成本2，(2,3):容量5成本1 需求：b(1)=5，b(3)=-5，b(2)=0 初始化：ε=2，π=(0,0,0)，零流 第一轮（ε=2）： 推流：顶点1→2推送5单位 更新后流：f(1,2)=5，f(2,3)=0 第二轮（ε=1）： 推流：顶点2→3推送5单位 最终流：f(1,2)=5，f(2,3)=5，总成本=5×2+5×1=15 算法优势 强多项式性：复杂度与成本值无关 数值稳定性：整数运算避免舍入误差 实现简单：主要操作是推流和重标价 这个算法通过成本精度的逐步细化，将复杂的最小费用流问题分解为多个可管理的子问题，是解决大规模网络流问题的有效方法。