基于线性规划的图最小费用流问题的对偶上升法求解示例 问题描述 考虑一个有向图G=(V,E)，其中V是顶点集，E是边集。每条边(i,j)∈E有容量u_ ij和单位流量费用c_ ij。某些顶点是供应点（提供流量），某些是需求点（消耗流量），且总供应量等于总需求量。最小费用流问题是在满足所有顶点流量平衡约束和边容量约束的前提下，找到总运输费用最小的流。 解题过程 第一步：建立原始线性规划模型 设决策变量x_ ij表示边(i,j)上的流量。原始问题为： min ∑ {(i,j)∈E} c_ ij x_ ij s.t. ∑ {j:(i,j)∈E} x_ ij - ∑_ {j:(j,i)∈E} x_ ji = b_ i, ∀i∈V (流量平衡约束) 0 ≤ x_ ij ≤ u_ ij, ∀(i,j)∈E (容量约束) 其中b_ i表示顶点i的净流出量（供应点b_ i>0，需求点b_ i<0，中转点b_ i=0） 第二步：构造对偶问题 引入对偶变量π_ i（对应流量平衡约束）和α_ ij（对应容量约束）。对偶问题为： max ∑ {i∈V} b_ i π_ i - ∑ {(i,j)∈E} u_ ij α_ ij s.t. π_ i - π_ j - α_ ij ≤ c_ ij, ∀(i,j)∈E α_ ij ≥ 0, ∀(i,j)∈E π_ i无符号限制 第三步：对偶上升法核心思想 对偶上升法通过迭代更新对偶变量π来提升对偶目标函数值，同时保持互补松弛条件。关键观察是：如果固定π，最优的α_ ij可由α_ ij = max(0, π_ i - π_ j - c_ ij)确定。 第四步：算法初始化 初始对偶变量：设置π_ i = 0, ∀i∈V 初始原始流：设置x_ ij = 0, ∀(i,j)∈E 定义残差图：初始时与原始图相同 第五步：迭代过程 在每次迭代中： 寻找增广路径 ：在残差图中寻找从供应点到需求点的路径，其中满足π_ i - π_ j = c_ ij（满足互补松弛条件） 更新流量 ：沿找到的路径推送尽可能多的流量（受路径上边容量限制） 更新对偶变量 ：如果没有找到满足条件的路径，则更新π_ i值 令S为从供应点可达且满足π_ i - π_ j ≤ c_ ij的顶点集合 计算δ = min{π_ i - π_ j - c_ ij | i∈S, j∉S, (i,j)∈E} 对∀i∈S，更新π_ i = π_ i - δ 第六步：终止条件 当所有顶点流量平衡约束得到满足时停止。由于对偶问题有上界（原始问题最优值），算法保证在有限步内收敛。 第七步：最优性验证 最终解满足： 原始可行性：流量平衡和容量约束 对偶可行性：π_ i - π_ j - α_ ij ≤ c_ ij 互补松弛条件： x_ ij > 0 ⇒ π_ i - π_ j = c_ ij + α_ ij α_ ij > 0 ⇒ x_ ij = u_ ij 0 < x_ ij < u_ ij ⇒ α_ ij = 0 算法特点 对偶上升法特别适合稀疏网络，每次只更新部分对偶变量，计算效率较高。通过利用对偶问题的结构特性，避免了直接求解大规模线性规划问题。