基于线性规划的图最小费用循环流问题的多项式时间双尺度尺度算法求解示例 题目描述 考虑一个有向图 \( G = (V, E) \)，每条边 \( e \in E \) 有容量上界 \( u_ e \)、下界 \( l_ e \)（通常为 0）和单位流费用 \( c_ e \)。最小费用循环流问题要求找到一个循环流（即满足流量守恒的流），使得总费用最小，且每条边的流量在容量范围内。数学模型为： \[ \begin{aligned} \min \quad & \sum_ {e \in E} c_ e f_ e \\ \text{s.t.} \quad & \sum_ {e \in \delta^+(v)} f_ e - \sum_ {e \in \delta^-(v)} f_ e = 0 \quad \forall v \in V \quad \text{(流量守恒)} \\ & l_ e \leq f_ e \leq u_ e \quad \forall e \in E \quad \text{(容量约束)} \end{aligned} \] 多项式时间双尺度算法通过动态调整费用和容量尺度，将问题分解为多个子问题逐步求解，最终得到最优解。 解题过程 问题重构与尺度初始化 将容量和费用缩放为整数（若为小数，可乘大数取整）。定义尺度参数 \( \Delta \)，初始值设为大于最大费用的 2 的幂次（如 \( \Delta = 2^{\lceil \log_ 2 C \rceil} \)，其中 \( C = \max |c_ e| \)）。 目标：通过迭代缩小 \( \Delta \)，逐步逼近最优流。每轮迭代解决一个近似子问题，其最优解与原问题误差随 \( \Delta \) 减小而降低。 当前尺度的子问题求解 在当前尺度 \( \Delta \) 下，定义近似费用 \( \hat{c}_ e = \lfloor c_ e / \Delta \rfloor \)，将原问题转化为费用为 \( \hat{c}_ e \) 的最小费用循环流问题。 使用多项式时间算法（如成本缩放算法）求解该子问题，得到当前流 \( f \)。注意：子问题的容量约束保持不变，仅费用被缩放。 最优性检验与尺度更新 检查当前流 \( f \) 对于原费用 \( c_ e \) 是否满足 \( \epsilon \)-最优性条件（即对任意循环流 \( f' \)，有 \( c^\top f \leq c^\top f' + \epsilon \)，其中 \( \epsilon = |E| \Delta \)）。 若满足，则将尺度减半：\( \Delta \leftarrow \Delta / 2 \)，并进入下一轮迭代；否则，保持当前尺度重新求解子问题（通常需调整流以消除费用误差）。 终止与结果输出 当 \( \Delta < 1/|E| \) 时终止，此时流 \( f \) 为原问题的最优解（因误差小于 1，而费用和流量均为整数）。 算法总迭代次数为 \( O(\log C) \)，每次迭代需多项式时间，故整体为多项式时间复杂度。 关键点说明 双尺度指同时缩放费用和容量（本例仅缩放费用，但容量约束通过子问题保留）。 每轮迭代通过简化费用结构降低计算复杂度，而尺度缩减确保逼近最优解。 该算法避免了直接处理大数值，提升了数值稳定性和效率。