基于线性规划的图最小费用循环流问题的原始-对偶方法求解示例
字数 2567 2025-11-29 19:50:31

基于线性规划的图最小费用循环流问题的原始-对偶方法求解示例

题目描述
考虑一个带权有向图 \(G = (V, E)\)，每条边 \((i, j) \in E\) 有容量上界 \(u_{ij}\)、容量下界 \(l_{ij}\)（通常为0）和单位流量成本 \(c_{ij}\)。图中可能存在负权边，但要求存在可行流。最小费用循环流问题要求找到一个循环流（即满足流量守恒的流），使得总成本 \(\sum_{(i,j) \in E} c_{ij} f_{ij}\) 最小，且满足 \(l_{ij} \leq f_{ij} \leq u_{ij}\)。

解题过程

步骤1：问题建模

  1. 变量：\(f_{ij}\) 表示边 \((i,j)\) 的流量。
  2. 目标函数：最小化总成本 \(\sum_{(i,j) \in E} c_{ij} f_{ij}\)。
  3. 约束：
    • 容量约束：\(l_{ij} \leq f_{ij} \leq u_{ij}\)。
    • 流量守恒：对每个节点 \(i \in V\)，流入流量等于流出流量，即

\[ \sum_{j: (j,i) \in E} f_{ji} - \sum_{j: (i,j) \in E} f_{ij} = 0. \]

步骤2：原始-对偶方法框架
原始-对偶方法通过交替更新原始变量（流量 \(f\)）和对偶变量（节点势 \(\pi\)）来逐步逼近最优解。核心思想是利用互补松弛条件：

  • 若 \(c_{ij}^{\pi} = c_{ij} + \pi_i - \pi_j > 0\)，则最优解中 \(f_{ij} = l_{ij}\)（尽量取小值）。
  • 若 \(c_{ij}^{\pi} < 0\)，则 \(f_{ij} = u_{ij}\)（尽量取大值）。
  • 若 \(c_{ij}^{\pi} = 0\)，则 \(f_{ij}\) 可取任意可行值。
    其中 \(c_{ij}^{\pi}\) 称为简化成本（reduced cost）。

步骤3：初始化可行流

  1. 构造辅助图 \(G'\)：
    • 对每条边 \((i,j)\)，添加反向边 \((j,i)\)（若不存在），容量为0，成本为 \(-c_{ij}\)。
    • 初始流 \(f\) 可设为0（若满足容量约束）或通过最大流算法求可行流。
  2. 初始化对偶变量 \(\pi\) 为0。

步骤4：迭代过程

  1. 计算简化成本：对每条边 \((i,j)\)，计算 \(c_{ij}^{\pi} = c_{ij} + \pi_i - \pi_j\)。
  2. 构造残量网络：
    • 若 \(f_{ij} < u_{ij}\)，保留边 \((i,j)\)，残量容量为 \(u_{ij} - f_{ij}\)，成本为 \(c_{ij}^{\pi}\)。
    • 若 \(f_{ij} > l_{ij}\)，添加反向边 \((j,i)\)，残量容量为 \(f_{ij} - l_{ij}\)，成本为 \(-c_{ij}^{\pi}\)。
  3. 寻找负成本环：在残量网络中寻找总成本为负的环（Bellman-Ford算法检测负环）。
    • 若不存在负环，当前流是最优解，算法终止。
    • 若存在负环，沿该环增广流量（尽量增加流量以降低总成本）。
  4. 更新流量：沿负环增广流量 \(\delta\)，其中

\[ \delta = \min\{ u_{ij} - f_{ij} \mid (i,j) \text{为正向边} \} \cup \{ f_{ij} - l_{ij} \mid (j,i) \text{为反向边} \}. \]

更新 \(f_{ij} = f_{ij} + \delta\)（正向边）或 \(f_{ij} = f_{ij} - \delta\)（反向边）。
5. 更新对偶变量（可选）：若使用最短路更新，设 \(\pi_i = \pi_i + d(i)\)，其中 \(d(i)\) 是从虚设源点到节点 \(i\) 的最短路径长（通过Bellman-Ford计算）。

步骤5：示例演示
假设有图 \(G\) 包含节点 \(\{1,2,3\}\) 和边：

  • \((1,2): c=2, l=0, u=5\)
  • \((2,3): c=-1, l=0, u=4\)
  • \((3,1): c=3, l=0, u=6\)
  1. 初始流 \(f_{12}=0, f_{23}=0, f_{31}=0\)，对偶变量 \(\pi=[0,0,0]\)。
  2. 简化成本：\(c_{12}^{\pi}=2, c_{23}^{\pi}=-1, c_{31}^{\pi}=3\)。
  3. 残量网络中，边 \((2,3)\) 的简化成本为负，环 \(1 \to 2 \to 3 \to 1\) 的总成本为 \(2 + (-1) + 3 = 4 > 0\)，非负环。但边 \((2,3)\) 本身是负成本，可增广：沿路径 \(2 \to 3 \to 1 \to 2\)（实际为环）需检查可行性。更简单的方法是直接找负环：从节点2出发，经边 \((2,3)\)（成本-1）和虚拟反向边？实际上，需用Bellman-Ford检测：
    • 初始化距离 \(d=[0,\infty,\infty]\)。
    • 第一轮松弛：更新 \(d_2=2\)（经边1→2），\(d_3=1\)（经边2→3）。
    • 第二轮发现负环？此例中需仔细计算。实际执行时，若Bellman-Ford第 \(|V|\) 轮仍可松弛，则存在负环。
  4. 最终找到负环后增广，更新流直至无负环。

步骤6：终止条件
当残量网络中无负成本环时，当前流 \(f\) 即为最小费用循环流。总成本为 \(\sum c_{ij} f_{ij}\)。

该方法通过利用对偶变量调整成本，将问题转化为在残量网络中寻找负环，有效处理了负权边和容量约束。

基于线性规划的图最小费用循环流问题的原始-对偶方法求解示例 题目描述 考虑一个带权有向图 \( G = (V, E) \)，每条边 \( (i, j) \in E \) 有容量上界 \( u_ {ij} \)、容量下界 \( l_ {ij} \)（通常为0）和单位流量成本 \( c_ {ij} \)。图中可能存在负权边，但要求存在可行流。最小费用循环流问题要求找到一个循环流（即满足流量守恒的流），使得总成本 \( \sum_ {(i,j) \in E} c_ {ij} f_ {ij} \) 最小，且满足 \( l_ {ij} \leq f_ {ij} \leq u_ {ij} \)。 解题过程 步骤1：问题建模 变量：\( f_ {ij} \) 表示边 \( (i,j) \) 的流量。 目标函数：最小化总成本 \( \sum_ {(i,j) \in E} c_ {ij} f_ {ij} \)。 约束： 容量约束：\( l_ {ij} \leq f_ {ij} \leq u_ {ij} \)。 流量守恒：对每个节点 \( i \in V \)，流入流量等于流出流量，即 \[ \sum_ {j: (j,i) \in E} f_ {ji} - \sum_ {j: (i,j) \in E} f_ {ij} = 0. \] 步骤2：原始-对偶方法框架 原始-对偶方法通过交替更新原始变量（流量 \( f \)）和对偶变量（节点势 \( \pi \)）来逐步逼近最优解。核心思想是利用互补松弛条件： 若 \( c_ {ij}^{\pi} = c_ {ij} + \pi_ i - \pi_ j > 0 \)，则最优解中 \( f_ {ij} = l_ {ij} \)（尽量取小值）。 若 \( c_ {ij}^{\pi} < 0 \)，则 \( f_ {ij} = u_ {ij} \)（尽量取大值）。 若 \( c_ {ij}^{\pi} = 0 \)，则 \( f_ {ij} \) 可取任意可行值。 其中 \( c_ {ij}^{\pi} \) 称为简化成本（reduced cost）。 步骤3：初始化可行流 构造辅助图 \( G' \)： 对每条边 \( (i,j) \)，添加反向边 \( (j,i) \)（若不存在），容量为0，成本为 \( -c_ {ij} \)。 初始流 \( f \) 可设为0（若满足容量约束）或通过最大流算法求可行流。 初始化对偶变量 \( \pi \) 为0。 步骤4：迭代过程 计算简化成本 ：对每条边 \( (i,j) \)，计算 \( c_ {ij}^{\pi} = c_ {ij} + \pi_ i - \pi_ j \)。 构造残量网络 ： 若 \( f_ {ij} < u_ {ij} \)，保留边 \( (i,j) \)，残量容量为 \( u_ {ij} - f_ {ij} \)，成本为 \( c_ {ij}^{\pi} \)。 若 \( f_ {ij} > l_ {ij} \)，添加反向边 \( (j,i) \)，残量容量为 \( f_ {ij} - l_ {ij} \)，成本为 \( -c_ {ij}^{\pi} \)。 寻找负成本环 ：在残量网络中寻找总成本为负的环（Bellman-Ford算法检测负环）。 若不存在负环，当前流是最优解，算法终止。 若存在负环，沿该环增广流量（尽量增加流量以降低总成本）。 更新流量 ：沿负环增广流量 \( \delta \)，其中 \[ \delta = \min\{ u_ {ij} - f_ {ij} \mid (i,j) \text{为正向边} \} \cup \{ f_ {ij} - l_ {ij} \mid (j,i) \text{为反向边} \}. \] 更新 \( f_ {ij} = f_ {ij} + \delta \)（正向边）或 \( f_ {ij} = f_ {ij} - \delta \)（反向边）。 更新对偶变量 （可选）：若使用最短路更新，设 \( \pi_ i = \pi_ i + d(i) \)，其中 \( d(i) \) 是从虚设源点到节点 \( i \) 的最短路径长（通过Bellman-Ford计算）。 步骤5：示例演示 假设有图 \( G \) 包含节点 \( \{1,2,3\} \) 和边： \( (1,2): c=2, l=0, u=5 \) \( (2,3): c=-1, l=0, u=4 \) \( (3,1): c=3, l=0, u=6 \) 初始流 \( f_ {12}=0, f_ {23}=0, f_ {31}=0 \)，对偶变量 \( \pi=[ 0,0,0 ] \)。 简化成本：\( c_ {12}^{\pi}=2, c_ {23}^{\pi}=-1, c_ {31}^{\pi}=3 \)。 残量网络中，边 \( (2,3) \) 的简化成本为负，环 \( 1 \to 2 \to 3 \to 1 \) 的总成本为 \( 2 + (-1) + 3 = 4 > 0 \)，非负环。但边 \( (2,3) \) 本身是负成本，可增广：沿路径 \( 2 \to 3 \to 1 \to 2 \)（实际为环）需检查可行性。更简单的方法是直接找负环：从节点2出发，经边 \( (2,3) \)（成本-1）和虚拟反向边？实际上，需用Bellman-Ford检测： 初始化距离 \( d=[ 0,\infty,\infty ] \)。 第一轮松弛：更新 \( d_ 2=2 \)（经边1→2），\( d_ 3=1 \)（经边2→3）。 第二轮发现负环？此例中需仔细计算。实际执行时，若Bellman-Ford第 \( |V| \) 轮仍可松弛，则存在负环。 最终找到负环后增广，更新流直至无负环。 步骤6：终止条件 当残量网络中无负成本环时，当前流 \( f \) 即为最小费用循环流。总成本为 \( \sum c_ {ij} f_ {ij} \)。 该方法通过利用对偶变量调整成本，将问题转化为在残量网络中寻找负环，有效处理了负权边和容量约束。