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

字数 2441 2025-11-27 14:12:41

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

问题描述
图最小费用流问题（Minimum Cost Flow Problem, MCF）是组合优化中的经典问题。给定一个有向图 \(G = (V, E)\)，每条边 \((i, j) \in E\) 有容量 \(u_{ij}\) 和单位流量的成本 \(c_{ij}\)。每个节点 \(i \in V\) 有净需求 \(b_i\)（若 \(b_i > 0\) 表示供应量，\(b_i < 0\) 表示需求量，且 \(\sum_{i} b_i = 0\)）。目标是找到一组边流量 \(x_{ij}\)，满足节点流量平衡和边容量约束，且总成本最小。数学模型为：

\[\begin{aligned} \min \quad & \sum_{(i,j) \in E} c_{ij} x_{ij} \\ \text{s.t.} \quad & \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 \end{aligned} \]

原始-对偶方法的核心思想
原始-对偶方法通过交替更新原始变量（流量 \(x\)）和对偶变量（节点势 \(\pi\)），逐步优化原始问题和对偶问题。其优势在于利用互补松弛条件将问题转化为在剩余图（Residual Graph）上寻找最短路径，避免直接求解大规模线性规划。

求解步骤详解

初始化
- 设初始流量 \(x_{ij} = 0\)（需满足容量约束，但可能不满足流量平衡）。
- 设初始节点势 \(\pi_i = 0\)（对偶变量对应节点的流量平衡约束）。
- 构建剩余图 \(G(x)\)：对于原图的每条边 \((i,j)\)，若 \(x_{ij} < u_{ij}\)，则添加前向边 \((i,j)\)，剩余容量为 \(u_{ij} - x_{ij}\)，成本为 \(c_{ij}\)；若 \(x_{ij} > 0\)，则添加反向边 \((j,i)\)，容量为 \(x_{ij}\)，成本为 \(-c_{ij}\)。
检查最优性条件
根据线性规划的对偶理论，最优解需满足互补松弛条件：
- 若 \(c_{ij} - \pi_i + \pi_j > 0\)，则 \(x_{ij} = 0\)（成本高时无流量）。
- 若 \(c_{ij} - \pi_i + \pi_j < 0\)，则 \(x_{ij} = u_{ij}\)（成本低时满容量）。
  定义简化成本 \(c_{ij}^{\pi} = c_{ij} - \pi_i + \pi_j\)。若对所有边有 \(c_{ij}^{\pi} \geq 0\)，则当前解最优。
迭代改进
- 步骤3.1：更新对偶变量
  若存在边不满足 \(c_{ij}^{\pi} \geq 0\)，则选择所有满足 \(c_{ij}^{\pi} < 0\) 的边构成子图，在这些边上尽可能增加流量（即沿负成本环增流），或调整节点势 \(\pi\) 使简化成本非负。具体操作：
  在剩余图 \(G(x)\) 上，以简化成本 \(c_{ij}^{\pi}\) 为边权，使用最短路径算法（如Dijkstra）计算从某源点 \(s\) 到所有节点的最短距离 \(d(i)\)。更新节点势：

\[ \pi_i \leftarrow \pi_i - d(i) \]

 此操作使所有边权 $ c_{ij}^{\pi} $ 变为非负（三角不等式保证 $ d(j) \leq d(i) + c_{ij}^{\pi} $）。

步骤3.2：增广流量
在更新后的剩余图中，找到从供应节点（\(b_i > 0\)）到需求节点（\(b_i < 0\)）的最短路径（基于新的 \(c_{ij}^{\pi}\)），沿该路径推送尽可能多的流量（受路径上最小剩余容量限制）。更新流量 \(x\) 和剩余图。

终止条件
重复步骤2-3，直到所有节点流量平衡（即净需求满足）且简化成本非负，此时得到最优解。

实例演示
考虑简单网络：节点 \(V = \{1,2,3\}\)，边 \(E = \{(1,2), (2,3), (1,3)\}\)，容量 \(u_{12} = 5, u_{23} = 3, u_{13} = 2\)，成本 \(c_{12} = 1, c_{23} = 2, c_{13} = 4\)，净需求 \(b_1 = 3, b_2 = 0, b_3 = -3\)。

初始化：设 \(x = 0, \pi = 0\)。
迭代1：简化成本均为正，但流量不平衡。从节点1到节点3的最短路径为1→2→3（成本1+2=3），推送流量3（受 \(u_{23} = 3\) 限制）。更新后 \(x_{12} = 3, x_{23} = 3\)，节点1余额0，节点3余额0。
验证：计算简化成本 \(c_{13}^{\pi} = 4 - 0 + 0 = 4 > 0\)，满足最优性条件。总成本为 \(3 \times 1 + 3 \times 2 = 9\)。

关键点总结
原始-对偶方法将最小费用流转化为一系列最短路径问题，高效利用网络结构。其核心是通过势函数调整边权，确保每次增广沿成本最低路径进行，避免单纯形法可能出现的退化问题。

基于线性规划的图最小费用流问题的原始-对偶方法求解示例问题描述图最小费用流问题（Minimum Cost Flow Problem, MCF）是组合优化中的经典问题。给定一个有向图 \( G = (V, E) \)，每条边 \( (i, j) \in E \) 有容量 \( u_ {ij} \) 和单位流量的成本 \( c_ {ij} \)。每个节点 \( i \in V \) 有净需求 \( b_ i \)（若 \( b_ i > 0 \) 表示供应量，\( b_ i < 0 \) 表示需求量，且 \( \sum_ {i} b_ i = 0 \)）。目标是找到一组边流量 \( x_ {ij} \)，满足节点流量平衡和边容量约束，且总成本最小。数学模型为： \[ \begin{aligned} \min \quad & \sum_ {(i,j) \in E} c_ {ij} x_ {ij} \\ \text{s.t.} \quad & \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 \end{aligned} \] 原始-对偶方法的核心思想原始-对偶方法通过交替更新原始变量（流量 \( x \)）和对偶变量（节点势 \( \pi \)），逐步优化原始问题和对偶问题。其优势在于利用互补松弛条件将问题转化为在剩余图（Residual Graph）上寻找最短路径，避免直接求解大规模线性规划。求解步骤详解初始化设初始流量 \( x_ {ij} = 0 \)（需满足容量约束，但可能不满足流量平衡）。设初始节点势 \( \pi_ i = 0 \)（对偶变量对应节点的流量平衡约束）。构建剩余图 \( G(x) \)：对于原图的每条边 \( (i,j) \)，若 \( x_ {ij} < u_ {ij} \)，则添加前向边 \( (i,j) \)，剩余容量为 \( u_ {ij} - x_ {ij} \)，成本为 \( c_ {ij} \)；若 \( x_ {ij} > 0 \)，则添加反向边 \( (j,i) \)，容量为 \( x_ {ij} \)，成本为 \( -c_ {ij} \)。检查最优性条件根据线性规划的对偶理论，最优解需满足互补松弛条件：若 \( c_ {ij} - \pi_ i + \pi_ j > 0 \)，则 \( x_ {ij} = 0 \)（成本高时无流量）。若 \( c_ {ij} - \pi_ i + \pi_ j < 0 \)，则 \( x_ {ij} = u_ {ij} \)（成本低时满容量）。定义简化成本 \( c_ {ij}^{\pi} = c_ {ij} - \pi_ i + \pi_ j \)。若对所有边有 \( c_ {ij}^{\pi} \geq 0 \)，则当前解最优。迭代改进步骤3.1：更新对偶变量若存在边不满足 \( c_ {ij}^{\pi} \geq 0 \)，则选择所有满足 \( c_ {ij}^{\pi} < 0 \) 的边构成子图，在这些边上尽可能增加流量（即沿负成本环增流），或调整节点势 \( \pi \) 使简化成本非负。具体操作：在剩余图 \( G(x) \) 上，以简化成本 \( c_ {ij}^{\pi} \) 为边权，使用最短路径算法（如Dijkstra）计算从某源点 \( s \) 到所有节点的最短距离 \( d(i) \)。更新节点势： \[ \pi_ i \leftarrow \pi_ i - d(i) \] 此操作使所有边权 \( c_ {ij}^{\pi} \) 变为非负（三角不等式保证 \( d(j) \leq d(i) + c_ {ij}^{\pi} \)）。步骤3.2：增广流量在更新后的剩余图中，找到从供应节点（\( b_ i > 0 \)）到需求节点（\( b_ i < 0 \)）的最短路径（基于新的 \( c_ {ij}^{\pi} \)），沿该路径推送尽可能多的流量（受路径上最小剩余容量限制）。更新流量 \( x \) 和剩余图。终止条件重复步骤2-3，直到所有节点流量平衡（即净需求满足）且简化成本非负，此时得到最优解。实例演示考虑简单网络：节点 \( V = \{1,2,3\} \)，边 \( E = \{(1,2), (2,3), (1,3)\} \)，容量 \( u_ {12} = 5, u_ {23} = 3, u_ {13} = 2 \)，成本 \( c_ {12} = 1, c_ {23} = 2, c_ {13} = 4 \)，净需求 \( b_ 1 = 3, b_ 2 = 0, b_ 3 = -3 \)。初始化：设 \( x = 0, \pi = 0 \)。迭代1 ：简化成本均为正，但流量不平衡。从节点1到节点3的最短路径为1→2→3（成本1+2=3），推送流量3（受 \( u_ {23} = 3 \) 限制）。更新后 \( x_ {12} = 3, x_ {23} = 3 \)，节点1余额0，节点3余额0。验证：计算简化成本 \( c_ {13}^{\pi} = 4 - 0 + 0 = 4 > 0 \)，满足最优性条件。总成本为 \( 3 \times 1 + 3 \times 2 = 9 \)。关键点总结原始-对偶方法将最小费用流转化为一系列最短路径问题，高效利用网络结构。其核心是通过势函数调整边权，确保每次增广沿成本最低路径进行，避免单纯形法可能出现的退化问题。