最小费用流问题
字数 2358 2025-11-02 10:10:41

最小费用流问题

最小费用流问题是网络流问题的一个重要分支，它研究的是在满足流量守恒和容量限制的前提下，如何以最小的总成本将流量从供应点（源点）输送到需求点（汇点）。

第一步：问题定义与基本概念

我们先来明确问题的构成要素。一个最小费用流问题通常由以下几个部分定义：

  1. 有向图：G = (N, A)，其中 N 是节点集合，A 是弧（有向边）集合。
  2. 容量：对于每条弧 (i, j) ∈ A，有一个非负的容量 u_ij，表示该弧上能通过的最大流量。
  3. 成本：对于每条弧 (i, j) ∈ A，有一个单位流量的成本 c_ij。当有 f_ij 个单位的流量通过此弧时，产生的成本为 c_ij * f_ij。
  4. 供应/需求：对于每个节点 i ∈ N，有一个值 b_i。
    • 如果 b_i > 0，则节点 i 是供应点（或源点），它提供 b_i 个单位的流量。
    • 如果 b_i < 0，则节点 i 是需求点（或汇点），它需要接收 |b_i| 个单位的流量。
    • 如果 b_i = 0，则节点 i 是转运点，流入的流量等于流出的流量。
  5. 关键假设：所有供应点的总供应量必须等于所有需求点的总需求量，即 Σ(i∈N) b_i = 0。这个假设保证了问题有可行解。

问题的目标是找到一组流 f_ij（定义在每条弧上），使得总成本最小。

第二步：数学模型

基于以上概念，我们可以建立最小费用流问题的线性规划模型：

目标函数：最小化总成本。
Minimize Σ((i,j)∈A) c_ij * f_ij

约束条件：

  1. 流量守恒约束（对于每个节点 i ∈ N）：
    Σ(j: (i,j)∈A) f_ij - Σ(j: (j,i)∈A) f_ji = b_i
    这个等式的含义是：从节点 i 流出的总流量减去流入节点 i 的总流量，必须等于该节点的净供应量 b_i。
  2. 容量约束（对于每条弧 (i, j) ∈ A）：
    0 ≤ f_ij ≤ u_ij
    流经每条弧的流量必须是非负的，且不能超过其容量。

第三步：一个简单实例

考虑一个简单的网络，有两个供应点（节点1和2，b1=4, b2=5），一个需求点（节点4，b4=-9），一个转运点（节点3，b3=0）。弧及其成本和容量如下：

  • 弧 (1,3): 成本=2, 容量=5
  • 弧 (1,4): 成本=9, 容量=4
  • 弧 (2,3): 成本=1, 容量=10
  • 弧 (3,4): 成本=3, 容量=9

我们的任务是找到从节点1和2到节点4的最小成本流方案。一个直观的（可能不是最优的）方案是：尽量使用成本低的路径。例如，让节点2的5个单位流量全部通过成本为1的弧(2,3)到达节点3，再通过成本为3的弧(3,4)到达节点4，这部分成本为 5*1 + 5*3 = 20。节点1的4个单位流量可以直接通过成本为9的弧(1,4)发送，成本为 4*9=36。总成本为56。优化算法会系统地寻找比这个方案更好的解。

第四步：最优性条件——负费用圈判定准则

如何判断我们找到的流方案是否是最优的呢？最小费用流问题有一个非常优美的最优性条件，它不直接依赖于线性规划的对偶理论，而是基于网络结构本身。

  • 剩余网络：给定一个可行的流 f，我们可以构建一个剩余网络 G(f)。在这个网络中，对于原图中的每条弧 (i, j)：

    • 如果 f_ij < u_ij，则在剩余网络中创建一条方向相同的弧 (i, j)，其剩余容量为 r_ij = u_ij - f_ij，成本为 c_ij。
    • 如果 f_ij > 0，则在剩余网络中创建一条方向相反的弧 (j, i)，其剩余容量为 f_ij（表示可以回退的流量），成本为 -c_ij。

  • 负费用圈：在剩余网络 G(f) 中找一个有向圈（即起点和终点相同的路径），如果这个圈上所有弧的成本之和为负数，则称其为负费用圈。

  • 最优性定理：一个可行流 f 是最小费用流，当且仅当其对应的剩余网络 G(f) 中不存在负费用圈。

这个定理的直观理解是：如果存在一个负费用圈，就意味着我们可以沿着这个圈推送一个正数的流量（流量值不能超过圈上任何弧的剩余容量）。这样做不会破坏任何节点的流量守恒（因为是在一个圈上循环），但会降低总成本（因为圈的总成本为负），所以当前的流 f 就不是最优的。反之，如果不存在负费用圈，则说明无法通过任何局部的流量调整来降低成本，因此流是最优的。

第五步：求解算法——网络单纯形法

基于负费用圈的最优性条件，最著名的求解最小费用流问题的算法是网络单纯形法。它是线性规划的单纯形法在网络流问题上的一个特化版本，因其极高的计算效率而闻名。

它的基本步骤是：

  1. 初始可行解：首先找到一个满足流量守恒和容量约束的初始可行流 f。这可以通过求解一个辅助的最大流问题来实现。
  2. 构建剩余网络：根据当前流 f 构建剩余网络 G(f)。
  3. 最优性检验：在剩余网络 G(f) 中寻找负费用圈。如果找不到任何负费用圈，则当前流 f 就是最优解，算法终止。
  4. 沿圈增广：如果找到了一个负费用圈，则计算能沿该圈推送的最大流量 Δ（受限于圈上弧的最小剩余容量）。然后，沿着这个圈推送 Δ 个单位的流量。对于圈上与原弧方向相同的弧，增加流量；对于方向相反的弧（回退弧），减少流量。
  5. 更新流量：根据增广操作更新当前流 f，然后返回步骤2。

网络单纯形法通过巧妙地利用树结构来表示基解，使得寻找负费用圈和更新流的操作非常高效，远胜于通用的线性规划算法。

最小费用流问题 最小费用流问题是网络流问题的一个重要分支，它研究的是在满足流量守恒和容量限制的前提下，如何以最小的总成本将流量从供应点（源点）输送到需求点（汇点）。 第一步：问题定义与基本概念 我们先来明确问题的构成要素。一个最小费用流问题通常由以下几个部分定义： 有向图 ： G = (N, A) ，其中 N 是节点集合， A 是弧（有向边）集合。 容量 ：对于每条弧 (i, j) ∈ A ，有一个非负的容量 u_ij ，表示该弧上能通过的最大流量。 成本 ：对于每条弧 (i, j) ∈ A ，有一个单位流量的成本 c_ij 。当有 f_ij 个单位的流量通过此弧时，产生的成本为 c_ij * f_ij 。 供应/需求 ：对于每个节点 i ∈ N ，有一个值 b_i 。 如果 b_i > 0 ，则节点 i 是 供应点 （或源点），它提供 b_i 个单位的流量。 如果 b_i < 0 ，则节点 i 是 需求点 （或汇点），它需要接收 |b_i| 个单位的流量。 如果 b_i = 0 ，则节点 i 是 转运点 ，流入的流量等于流出的流量。 关键假设 ：所有供应点的总供应量必须等于所有需求点的总需求量，即 Σ(i∈N) b_i = 0 。这个假设保证了问题有可行解。 问题的目标是找到一组流 f_ij （定义在每条弧上），使得总成本最小。 第二步：数学模型 基于以上概念，我们可以建立最小费用流问题的线性规划模型： 目标函数 ：最小化总成本。 Minimize Σ((i,j)∈A) c_ij * f_ij 约束条件 ： 流量守恒约束 （对于每个节点 i ∈ N ）： Σ(j: (i,j)∈A) f_ij - Σ(j: (j,i)∈A) f_ji = b_i 这个等式的含义是：从节点 i 流出的总流量减去流入节点 i 的总流量，必须等于该节点的净供应量 b_i 。 容量约束 （对于每条弧 (i, j) ∈ A ）： 0 ≤ f_ij ≤ u_ij 流经每条弧的流量必须是非负的，且不能超过其容量。 第三步：一个简单实例 考虑一个简单的网络，有两个供应点（节点1和2， b1=4 , b2=5 ），一个需求点（节点4， b4=-9 ），一个转运点（节点3， b3=0 ）。弧及其成本和容量如下： 弧 (1,3): 成本=2, 容量=5 弧 (1,4): 成本=9, 容量=4 弧 (2,3): 成本=1, 容量=10 弧 (3,4): 成本=3, 容量=9 我们的任务是找到从节点1和2到节点4的最小成本流方案。一个直观的（可能不是最优的）方案是：尽量使用成本低的路径。例如，让节点2的5个单位流量全部通过成本为1的弧(2,3)到达节点3，再通过成本为3的弧(3,4)到达节点4，这部分成本为 5*1 + 5*3 = 20 。节点1的4个单位流量可以直接通过成本为9的弧(1,4)发送，成本为 4*9=36 。总成本为56。优化算法会系统地寻找比这个方案更好的解。 第四步：最优性条件——负费用圈判定准则 如何判断我们找到的流方案是否是最优的呢？最小费用流问题有一个非常优美的最优性条件，它不直接依赖于线性规划的对偶理论，而是基于网络结构本身。 剩余网络 ：给定一个可行的流 f ，我们可以构建一个 剩余网络 G(f) 。在这个网络中，对于原图中的每条弧 (i, j) ： 如果 f_ij < u_ij ，则在剩余网络中创建一条方向相同的弧 (i, j) ，其 剩余容量 为 r_ij = u_ij - f_ij ，成本为 c_ij 。 如果 f_ij > 0 ，则在剩余网络中创建一条方向相反的弧 (j, i) ，其剩余容量为 f_ij （表示可以回退的流量），成本为 -c_ij 。 负费用圈 ：在剩余网络 G(f) 中找一个有向圈（即起点和终点相同的路径），如果这个圈上所有弧的成本之和为负数，则称其为 负费用圈 。 最优性定理 ：一个可行流 f 是最小费用流， 当且仅当 其对应的剩余网络 G(f) 中不存在负费用圈。 这个定理的直观理解是：如果存在一个负费用圈，就意味着我们可以沿着这个圈推送一个正数的流量（流量值不能超过圈上任何弧的剩余容量）。这样做不会破坏任何节点的流量守恒（因为是在一个圈上循环），但会降低总成本（因为圈的总成本为负），所以当前的流 f 就不是最优的。反之，如果不存在负费用圈，则说明无法通过任何局部的流量调整来降低成本，因此流是最优的。 第五步：求解算法——网络单纯形法 基于负费用圈的最优性条件，最著名的求解最小费用流问题的算法是 网络单纯形法 。它是线性规划的单纯形法在网络流问题上的一个特化版本，因其极高的计算效率而闻名。 它的基本步骤是： 初始可行解 ：首先找到一个满足流量守恒和容量约束的初始可行流 f 。这可以通过求解一个辅助的最大流问题来实现。 构建剩余网络 ：根据当前流 f 构建剩余网络 G(f) 。 最优性检验 ：在剩余网络 G(f) 中寻找负费用圈。如果找不到任何负费用圈，则当前流 f 就是最优解，算法终止。 沿圈增广 ：如果找到了一个负费用圈，则计算能沿该圈推送的最大流量 Δ （受限于圈上弧的最小剩余容量）。然后，沿着这个圈推送 Δ 个单位的流量。对于圈上与原弧方向相同的弧，增加流量；对于方向相反的弧（回退弧），减少流量。 更新流量 ：根据增广操作更新当前流 f ，然后返回步骤2。 网络单纯形法通过巧妙地利用树结构来表示基解，使得寻找负费用圈和更新流的操作非常高效，远胜于通用的线性规划算法。