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

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

问题描述
考虑一个带权有向图 \(G = (V, E)\)，每条边 \((i, j) \in E\) 有容量上界 \(u_{ij}\)、成本 \(c_{ij}\)，且每个顶点 \(i \in V\) 有净需求 \(b_i\)（满足 \(\sum_{i \in V} b_i = 0\)）。最小费用循环流问题要求找到一组流 \(x_{ij}\)，满足以下约束：

  1. 流量平衡：对每个顶点 \(i\)，\(\sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = b_i\)；
  2. 容量约束：对每条边 \((i,j)\)，\(0 \leq x_{ij} \leq u_{ij}\)；
  3. 目标：最小化总成本 \(\sum_{(i,j) \in E} c_{ij} x_{ij}\)。
    该问题是传统最小费用流的扩展，允许顶点存在净需求（即非可行流），但通过循环流（无源无汇）调整实现成本最小化。

解题步骤
1. 线性规划建模

  • 变量：\(x_{ij}\) 表示边 \((i,j)\) 上的流量。
  • 目标函数：

\[ \min \sum_{(i,j) \in E} c_{ij} x_{ij} \]

  • 约束条件：

\[ \sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = b_i \quad (\forall i \in V) \]

\[ 0 \leq x_{ij} \leq u_{ij} \quad (\forall (i,j) \in E) \]

2. 构造对偶问题

  • 为每个顶点约束引入对偶变量 \(\pi_i\)（无符号限制），为每个容量约束引入对偶变量 \(\alpha_{ij} \geq 0\)（对应上界 \(u_{ij}\)）。
  • 对偶目标函数：

\[ \max \sum_{i \in V} b_i \pi_i - \sum_{(i,j) \in E} u_{ij} \alpha_{ij} \]

  • 对偶约束（基于原始变量 \(x_{ij}\) 的系数关系）：

\[ \pi_i - \pi_j - \alpha_{ij} \leq c_{ij} \quad (\forall (i,j) \in E) \]

\[ \alpha_{ij} \geq 0 \quad (\forall (i,j) \in E) \]

3. 互补松弛条件
原始可行解 \(x^*\) 和对偶可行解 \((\pi^*, \alpha^*)\) 最优时满足：

  • 若 \(x_{ij}^* > 0\)，则 \(\pi_i^* - \pi_j^* - \alpha_{ij}^* = c_{ij}\)；
  • 若 \(x_{ij}^* < u_{ij}\)，则 \(\alpha_{ij}^* = 0\)。
    这意味着：
  • 当 \(0 < x_{ij}^* < u_{ij}\) 时，\(\pi_i^* - \pi_j^* = c_{ij}\)；
  • 当 \(x_{ij}^* = 0\) 时，\(\pi_i^* - \pi_j^* \leq c_{ij}\)；
  • 当 \(x_{ij}^* = u_{ij}\) 时，\(\pi_i^* - \pi_j^* \geq c_{ij}\)。

4. 原始-对偶算法流程

  • 步骤1：初始化
    设初始对偶变量 \(\pi_i = 0\)（满足对偶可行性），初始流 \(x_{ij} = 0\)（未必满足流量平衡）。
  • 步骤2：构造残量图
    基于当前流 \(x\) 和对偶变量 \(\pi\)，定义残量边：
    • 前向边：若 \(x_{ij} < u_{ij}\)，残量容量 \(r_{ij} = u_{ij} - x_{ij}\)，成本 \(c_{ij}^\pi = c_{ij} - (\pi_i - \pi_j)\)。
    • 反向边：若 \(x_{ij} > 0\)，残量容量 \(r_{ji} = x_{ij}\)，成本 \(c_{ji}^\pi = -c_{ij} - (\pi_j - \pi_i)\)。
      互补松弛要求：最优时所有边满足 \(c_{ij}^\pi \geq 0\)。
  • 步骤3：检查最优性
    计算每个顶点的不平衡量 \(\Delta_i = b_i - \left( \sum_{j} x_{ij} - \sum_{j} x_{ji} \right)\)。若所有 \(\Delta_i = 0\)，当前流可行且最优，算法终止。
  • 步骤4：更新流与对偶变量
    • 情况1：若存在负成本圈（即 \(c_{ij}^\pi < 0\) 的圈），沿该圈增广流（增加流量以降低总成本），更新 \(x\)。
    • 情况2：若无可增广负圈，但存在不平衡顶点（\(\Delta_i \neq 0\)），则通过最短路径算法（如Bellman-Ford）在残量图中找到从过剩顶点（\(\Delta_i > 0\)）到不足顶点（\(\Delta_i < 0\)）的最短路径，并沿路径增广流。
    • 增广后更新对偶变量 \(\pi_i\)（例如，通过设置 \(\pi_i \leftarrow \pi_i + d_i\)，其中 \(d_i\) 为从过剩顶点到 \(i\) 的最短距离）。
  • 步骤5：迭代
    重复步骤2-4直到所有顶点平衡且无负成本圈。

5. 示例演示
考虑简单图：顶点集 \(V = \{1,2,3\}\)，边 \((1,2)\)：\(c=2, u=3\)；\((2,3)\)：\(c=1, u=5\)；\((3,1)\)：\(c=1, u=4\)。净需求 \(b_1 = 2, b_2 = -1, b_3 = -1\)。

  • 初始流 \(x=0\)，对偶变量 \(\pi=0\)。
  • 残量图边成本：\(c_{12}^\pi=2, c_{23}^\pi=1, c_{31}^\pi=1\)。
  • 顶点1过剩（\(\Delta_1=2\)），顶点2、3不足。从顶点1到2的最短路径成本为2，增广流1单位，更新 \(x_{12}=1\)。
  • 重新计算不平衡量，继续增广直至满足所有需求，最终得到最小费用流。

总结
原始-对偶方法通过交替调整流和对偶变量，逐步逼近最优解。其优势在于利用对偶理论指导搜索方向，避免单纯形法的退化问题，适用于大规模网络流问题。

基于线性规划的图最小费用循环流问题的原始-对偶方法求解示例 问题描述 考虑一个带权有向图 \( G = (V, E) \)，每条边 \( (i, j) \in E \) 有容量上界 \( u_ {ij} \)、成本 \( c_ {ij} \)，且每个顶点 \( i \in V \) 有净需求 \( b_ i \)（满足 \( \sum_ {i \in V} b_ i = 0 \)）。最小费用循环流问题要求找到一组流 \( x_ {ij} \)，满足以下约束： 流量平衡 ：对每个顶点 \( i \)，\( \sum_ {j: (i,j) \in E} x_ {ij} - \sum_ {j: (j,i) \in E} x_ {ji} = b_ i \)； 容量约束 ：对每条边 \( (i,j) \)，\( 0 \leq x_ {ij} \leq u_ {ij} \)； 目标 ：最小化总成本 \( \sum_ {(i,j) \in E} c_ {ij} x_ {ij} \)。 该问题是传统最小费用流的扩展，允许顶点存在净需求（即非可行流），但通过循环流（无源无汇）调整实现成本最小化。 解题步骤 1. 线性规划建模 变量 ：\( x_ {ij} \) 表示边 \( (i,j) \) 上的流量。 目标函数 ： \[ \min \sum_ {(i,j) \in E} c_ {ij} x_ {ij} \] 约束条件 ： \[ \sum_ {j: (i,j) \in E} x_ {ij} - \sum_ {j: (j,i) \in E} x_ {ji} = b_ i \quad (\forall i \in V) \] \[ 0 \leq x_ {ij} \leq u_ {ij} \quad (\forall (i,j) \in E) \] 2. 构造对偶问题 为每个顶点约束引入对偶变量 \( \pi_ i \)（无符号限制），为每个容量约束引入对偶变量 \( \alpha_ {ij} \geq 0 \)（对应上界 \( u_ {ij} \)）。 对偶目标函数 ： \[ \max \sum_ {i \in V} b_ i \pi_ i - \sum_ {(i,j) \in E} u_ {ij} \alpha_ {ij} \] 对偶约束 （基于原始变量 \( x_ {ij} \) 的系数关系）： \[ \pi_ i - \pi_ j - \alpha_ {ij} \leq c_ {ij} \quad (\forall (i,j) \in E) \] \[ \alpha_ {ij} \geq 0 \quad (\forall (i,j) \in E) \] 3. 互补松弛条件 原始可行解 \( x^* \) 和对偶可行解 \( (\pi^ , \alpha^ ) \) 最优时满足： 若 \( x_ {ij}^* > 0 \)，则 \( \pi_ i^* - \pi_ j^* - \alpha_ {ij}^* = c_ {ij} \)； 若 \( x_ {ij}^* < u_ {ij} \)，则 \( \alpha_ {ij}^* = 0 \)。 这意味着： 当 \( 0 < x_ {ij}^* < u_ {ij} \) 时，\( \pi_ i^* - \pi_ j^* = c_ {ij} \)； 当 \( x_ {ij}^* = 0 \) 时，\( \pi_ i^* - \pi_ j^* \leq c_ {ij} \)； 当 \( x_ {ij}^* = u_ {ij} \) 时，\( \pi_ i^* - \pi_ j^* \geq c_ {ij} \)。 4. 原始-对偶算法流程 步骤1：初始化 设初始对偶变量 \( \pi_ i = 0 \)（满足对偶可行性），初始流 \( x_ {ij} = 0 \)（未必满足流量平衡）。 步骤2：构造残量图 基于当前流 \( x \) 和对偶变量 \( \pi \)，定义残量边： 前向边 ：若 \( x_ {ij} < u_ {ij} \)，残量容量 \( r_ {ij} = u_ {ij} - x_ {ij} \)，成本 \( c_ {ij}^\pi = c_ {ij} - (\pi_ i - \pi_ j) \)。 反向边 ：若 \( x_ {ij} > 0 \)，残量容量 \( r_ {ji} = x_ {ij} \)，成本 \( c_ {ji}^\pi = -c_ {ij} - (\pi_ j - \pi_ i) \)。 互补松弛要求：最优时所有边满足 \( c_ {ij}^\pi \geq 0 \)。 步骤3：检查最优性 计算每个顶点的不平衡量 \( \Delta_ i = b_ i - \left( \sum_ {j} x_ {ij} - \sum_ {j} x_ {ji} \right) \)。若所有 \( \Delta_ i = 0 \)，当前流可行且最优，算法终止。 步骤4：更新流与对偶变量 情况1 ：若存在负成本圈（即 \( c_ {ij}^\pi < 0 \) 的圈），沿该圈增广流（增加流量以降低总成本），更新 \( x \)。 情况2 ：若无可增广负圈，但存在不平衡顶点（\( \Delta_ i \neq 0 \)），则通过最短路径算法（如Bellman-Ford）在残量图中找到从过剩顶点（\( \Delta_ i > 0 \)）到不足顶点（\( \Delta_ i < 0 \)）的最短路径，并沿路径增广流。 增广后更新对偶变量 \( \pi_ i \)（例如，通过设置 \( \pi_ i \leftarrow \pi_ i + d_ i \)，其中 \( d_ i \) 为从过剩顶点到 \( i \) 的最短距离）。 步骤5：迭代 重复步骤2-4直到所有顶点平衡且无负成本圈。 5. 示例演示 考虑简单图：顶点集 \( V = \{1,2,3\} \)，边 \( (1,2) \)：\( c=2, u=3 \)；\( (2,3) \)：\( c=1, u=5 \)；\( (3,1) \)：\( c=1, u=4 \)。净需求 \( b_ 1 = 2, b_ 2 = -1, b_ 3 = -1 \)。 初始流 \( x=0 \)，对偶变量 \( \pi=0 \)。 残量图边成本：\( c_ {12}^\pi=2, c_ {23}^\pi=1, c_ {31}^\pi=1 \)。 顶点1过剩（\( \Delta_ 1=2 \)），顶点2、3不足。从顶点1到2的最短路径成本为2，增广流1单位，更新 \( x_ {12}=1 \)。 重新计算不平衡量，继续增广直至满足所有需求，最终得到最小费用流。 总结 原始-对偶方法通过交替调整流和对偶变量，逐步逼近最优解。其优势在于利用对偶理论指导搜索方向，避免单纯形法的退化问题，适用于大规模网络流问题。