基于线性规划的图最小费用流问题的多项式时间双重尺度算法（Double Scaling Algorithm）求解示例
字数 3304 2025-12-19 23:55:06

基于线性规划的图最小费用流问题的多项式时间双重尺度算法（Double Scaling Algorithm）求解示例

题目描述

考虑一个有向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 具有：

  • 容量 \(u(e) \geq 0\)
  • 单位流量的费用 \(c(e) \in \mathbb{R}\)（可为负）
  • 以及每个顶点 \(v \in V\) 的供需量 \(b(v)\)，满足 \(\sum_{v \in V} b(v) = 0\)。

目标：找到满足所有顶点供需约束（即对每个顶点 \(v\)，净流出量等于 \(b(v)\)）且不违反边容量的流，使得总费用 \(\sum_{e \in E} c(e) f(e)\) 最小。

这是一个标准的最小费用流问题。我们将介绍一种多项式时间的双重尺度算法（Double Scaling Algorithm），它同时缩放容量和费用，以高效求解。

解题步骤

1. 问题建模

最小费用流可以写为线性规划：

\[\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) = b(v), \quad \forall v \in V, \\ & 0 \leq f(e) \leq u(e), \quad \forall e \in E, \end{aligned} \]

其中 \(\delta^+(v)\) 和 \(\delta^-(v)\) 分别表示从 \(v\) 出发和进入 \(v\) 的边集。

2. 双重尺度算法的核心思想

双重尺度算法结合了：

  • 容量缩放：从较大的容量尺度 \(\Delta\) 开始，每次将 \(\Delta\) 减半，逐步满足流量约束。
  • 费用缩放：在每轮容量缩放中，通过调整势函数（对偶变量）来确保费用非负，从而可以使用 Dijkstra 算法求最短路增广。

算法保持ε-最优性：即存在势函数 \(\pi\) 使得约化费用 \(c^\pi(e) = c(e) + \pi(u) - \pi(v)\) 满足：

\[c^\pi(e) \geq -\varepsilon, \quad \forall e \in E, \]

其中 \(\varepsilon\) 是费用尺度参数，初始时 \(\varepsilon = C\)（最大费用绝对值），每轮费用缩放将 \(\varepsilon\) 减半。

3. 算法步骤详解

步骤 0：初始化

  • 设 \(U = \max_{e \in E} u(e)\)，\(C = \max_{e \in E} |c(e)|\)。
  • 初始流 \(f = 0\)，初始势 \(\pi = 0\)。
  • 容量尺度 \(\Delta = 2^{\lfloor \log_2 U \rfloor}\)（即不小于 \(U\) 的最大2的幂）。
  • 费用尺度 \(\varepsilon = C\)。

步骤 1：费用缩放主循环
当 \(\varepsilon \geq 1/n\) 时（\(n = |V|\)）执行：

  • 调用 容量缩放子程序 在当前 \(\varepsilon\) 下寻找 \(\varepsilon\)-最优流。
  • 令 \(\varepsilon = \varepsilon / 2\)，并调整势函数以保持 \(\varepsilon\)-最优性。

步骤 2：容量缩放子程序（在给定 \(\varepsilon\) 下）

  • 初始化当前流 \(f\) 和势 \(\pi\) 满足 \(\varepsilon\)-最优性。
  • 当 \(\Delta \geq 1\) 时执行：
    1. 构建 Δ-剩余网络：定义剩余容量 \(r(e) = u(e) - f(e)\)（正向边）和 \(f(e)\)（反向边）。只考虑剩余容量 \(\geq \Delta\) 的边，且约化费用 \(c^\pi(e) \geq -\varepsilon\)。
    2. 寻找增广路：在 Δ-剩余网络中，用 Dijkstra 算法找从任意供应顶点（\(b(v) > 0\)）到需求顶点（\(b(v) < 0\)）的最短路（按约化费用）。
    3. 增广流量：沿最短路增广 \(\Delta\) 单位流量，更新流 \(f\) 和供需。
    4. 如果当前 Δ-剩余网络中无可增广路，则令 \(\Delta = \Delta / 2\)。

步骤 3：终止条件

  • 当 \(\Delta < 1\) 且所有顶点供需满足时，当前流即为最小费用流。

4. 举例演示

考虑简单图：
顶点 \(V = \{s, t\}\)，边 \(e_1 = (s, t)\)，容量 \(u = 4\)，费用 \(c = 3\)；\(e_2 = (t, s)\)，容量 \(u = 2\)，费用 \(c = -1\)。供需：\(b(s) = 2, b(t) = -2\)。（即从 \(s\) 到 \(t\) 净送2单位流量）

初始化：

  • \(U = 4, C = 3, n = 2\)。
  • \(\Delta = 4, \varepsilon = 3\)。
  • 初始流 \(f = 0\)，势 \(\pi = 0\)。

第一轮费用缩放（\(\varepsilon = 3\)）：

  • 构建 Δ-剩余网络（Δ=4）：
    • 边 \(e_1\) 剩余容量 4 ≥ Δ，约化费用 \(c^\pi = 3 ≥ -3\)。
    • 边 \(e_2\) 剩余容量 2 < Δ，忽略。
  • 最短路：\(s \to t\)（费用3），增广流量 min(Δ, 供需限制) = min(4, 2) = 2。
  • 更新流：\(f(e_1) = 2\)。
  • 更新供需：\(b(s) = 0, b(t) = 0\) → 供需已满足。
  • Δ 缩放：Δ=4 → 2 → 1 → 0.5 … 直到 Δ<1，结束容量缩放。

此时流已可行，但可能不是 ε-最优？检查反向边：

  • 剩余网络中加入反向边 \(e_1' = (t, s)\) 容量2（来自正向流2），约化费用 \(c^\pi(e_1') = -3\)（因为反向边费用 = -3）。
  • 但 ε=3，所以 \(c^\pi(e_1') = -3 ≥ -3\) 仍满足 ε-最优性。

费用缩放继续：ε = 3 → 1.5 → 0.75 → … 直到 ε < 1/n = 0.5 时停止。
最终流 \(f(e_1) = 2, f(e_2) = 0\)，总费用 = 6，是最优解（因为费用为负的 \(e_2\) 因容量不足无法使用）。

5. 算法复杂度与关键性质

  • 多项式时间：每轮费用缩放执行 \(O(\log C)\) 次。每轮容量缩放执行 \(O(\log U)\) 次。每次增广用 Dijkstra 需 \(O(m + n \log n)\)。总复杂度 \(O((m \log U)(m + n \log n) \log C)\)。
  • 正确性：通过维护 ε-最优性，当 ε < 1/n 时，流是最优的（因为约化费用均为非负，且整数费用下最优解为整数）。
  • 优势：同时缩放容量和费用，避免在剩余网络中处理负费用圈，适合大规模稀疏图。

总结

双重尺度算法通过容量缩放逐步满足流量约束，通过费用缩放保持约化费用非负，从而能用高效的最短路增广。它结合了容量缩放和费用缩放的优点，是多项式时间的最小费用流经典算法之一。

基于线性规划的图最小费用流问题的多项式时间双重尺度算法（Double Scaling Algorithm）求解示例 题目描述 考虑一个有向图 \( G = (V, E) \)，其中每条边 \( e \in E \) 具有： 容量 \( u(e) \geq 0 \) 单位流量的费用 \( c(e) \in \mathbb{R} \)（可为负） 以及每个顶点 \( v \in V \) 的供需量 \( b(v) \)，满足 \( \sum_ {v \in V} b(v) = 0 \)。 目标：找到满足所有顶点供需约束（即对每个顶点 \( v \)，净流出量等于 \( b(v) \)）且不违反边容量的流，使得总费用 \( \sum_ {e \in E} c(e) f(e) \) 最小。 这是一个标准的 最小费用流问题 。我们将介绍一种多项式时间的 双重尺度算法 （Double Scaling Algorithm），它同时缩放容量和费用，以高效求解。 解题步骤 1. 问题建模 最小费用流可以写为线性规划： \[ \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) = b(v), \quad \forall v \in V, \\ & 0 \leq f(e) \leq u(e), \quad \forall e \in E, \end{aligned} \] 其中 \( \delta^+(v) \) 和 \( \delta^-(v) \) 分别表示从 \( v \) 出发和进入 \( v \) 的边集。 2. 双重尺度算法的核心思想 双重尺度算法结合了： 容量缩放 ：从较大的容量尺度 \( \Delta \) 开始，每次将 \( \Delta \) 减半，逐步满足流量约束。 费用缩放 ：在每轮容量缩放中，通过调整势函数（对偶变量）来确保费用非负，从而可以使用 Dijkstra 算法求最短路增广。 算法保持 ε-最优性 ：即存在势函数 \( \pi \) 使得 约化费用 \( c^\pi(e) = c(e) + \pi(u) - \pi(v) \) 满足： \[ c^\pi(e) \geq -\varepsilon, \quad \forall e \in E, \] 其中 \( \varepsilon \) 是费用尺度参数，初始时 \( \varepsilon = C \)（最大费用绝对值），每轮费用缩放将 \( \varepsilon \) 减半。 3. 算法步骤详解 步骤 0：初始化 设 \( U = \max_ {e \in E} u(e) \)，\( C = \max_ {e \in E} |c(e)| \)。 初始流 \( f = 0 \)，初始势 \( \pi = 0 \)。 容量尺度 \( \Delta = 2^{\lfloor \log_ 2 U \rfloor} \)（即不小于 \( U \) 的最大2的幂）。 费用尺度 \( \varepsilon = C \)。 步骤 1：费用缩放主循环 当 \( \varepsilon \geq 1/n \) 时（\( n = |V| \)）执行： 调用 容量缩放子程序 在当前 \( \varepsilon \) 下寻找 \( \varepsilon \)-最优流。 令 \( \varepsilon = \varepsilon / 2 \)，并调整势函数以保持 \( \varepsilon \)-最优性。 步骤 2：容量缩放子程序（在给定 \( \varepsilon \) 下） 初始化当前流 \( f \) 和势 \( \pi \) 满足 \( \varepsilon \)-最优性。 当 \( \Delta \geq 1 \) 时执行： 构建 Δ-剩余网络 ：定义剩余容量 \( r(e) = u(e) - f(e) \)（正向边）和 \( f(e) \)（反向边）。只考虑剩余容量 \( \geq \Delta \) 的边，且约化费用 \( c^\pi(e) \geq -\varepsilon \)。 寻找增广路 ：在 Δ-剩余网络中，用 Dijkstra 算法找从任意供应顶点（\( b(v) > 0 \)）到需求顶点（\( b(v) < 0 \)）的最短路（按约化费用）。 增广流量 ：沿最短路增广 \( \Delta \) 单位流量，更新流 \( f \) 和供需。 如果当前 Δ-剩余网络中无可增广路，则令 \( \Delta = \Delta / 2 \)。 步骤 3：终止条件 当 \( \Delta < 1 \) 且所有顶点供需满足时，当前流即为最小费用流。 4. 举例演示 考虑简单图： 顶点 \( V = \{s, t\} \)，边 \( e_ 1 = (s, t) \)，容量 \( u = 4 \)，费用 \( c = 3 \)；\( e_ 2 = (t, s) \)，容量 \( u = 2 \)，费用 \( c = -1 \)。供需：\( b(s) = 2, b(t) = -2 \)。（即从 \( s \) 到 \( t \) 净送2单位流量） 初始化 ： \( U = 4, C = 3, n = 2 \)。 \( \Delta = 4, \varepsilon = 3 \)。 初始流 \( f = 0 \)，势 \( \pi = 0 \)。 第一轮费用缩放 （\( \varepsilon = 3 \)）： 构建 Δ-剩余网络（Δ=4）： 边 \( e_ 1 \) 剩余容量 4 ≥ Δ，约化费用 \( c^\pi = 3 ≥ -3 \)。 边 \( e_ 2 \) 剩余容量 2 < Δ，忽略。 最短路：\( s \to t \)（费用3），增广流量 min(Δ, 供需限制) = min(4, 2) = 2。 更新流：\( f(e_ 1) = 2 \)。 更新供需：\( b(s) = 0, b(t) = 0 \) → 供需已满足。 Δ 缩放：Δ=4 → 2 → 1 → 0.5 … 直到 Δ <1，结束容量缩放。 此时流已可行，但可能不是 ε-最优？检查反向边： 剩余网络中加入反向边 \( e_ 1' = (t, s) \) 容量2（来自正向流2），约化费用 \( c^\pi(e_ 1') = -3 \)（因为反向边费用 = -3）。 但 ε=3，所以 \( c^\pi(e_ 1') = -3 ≥ -3 \) 仍满足 ε-最优性。 费用缩放继续 ：ε = 3 → 1.5 → 0.75 → … 直到 ε < 1/n = 0.5 时停止。 最终流 \( f(e_ 1) = 2, f(e_ 2) = 0 \)，总费用 = 6，是最优解（因为费用为负的 \( e_ 2 \) 因容量不足无法使用）。 5. 算法复杂度与关键性质 多项式时间 ：每轮费用缩放执行 \( O(\log C) \) 次。每轮容量缩放执行 \( O(\log U) \) 次。每次增广用 Dijkstra 需 \( O(m + n \log n) \)。总复杂度 \( O((m \log U)(m + n \log n) \log C) \)。 正确性 ：通过维护 ε-最优性，当 ε < 1/n 时，流是最优的（因为约化费用均为非负，且整数费用下最优解为整数）。 优势 ：同时缩放容量和费用，避免在剩余网络中处理负费用圈，适合大规模稀疏图。 总结 双重尺度算法通过 容量缩放 逐步满足流量约束，通过 费用缩放 保持约化费用非负，从而能用高效的最短路增广。它结合了容量缩放和费用缩放的优点，是多项式时间的最小费用流经典算法之一。