最小费用最大流问题的网络单纯形算法（Network Simplex Algorithm for Min-Cost Max-Flow）
字数 3447 2025-12-16 18:43:14

最小费用最大流问题的网络单纯形算法（Network Simplex Algorithm for Min-Cost Max-Flow）

题目描述

我们考虑一个有向图 \(G = (V, E)\)，其中：

  • 每条边 \(e \in E\) 具有容量 \(u_e > 0\) 和单位流量成本 \(c_e\)（可为负数）。
  • 图中有源点 \(s\) 和汇点 \(t\)。
  • 目标：在满足流量守恒（除 \(s, t\) 外每个点的净流出为零）和容量约束的前提下，在获得最大流量的同时，使总运输成本最小化。

这个问题称为最小费用最大流（Minimum-Cost Maximum-Flow）。网络单纯形算法是求解此问题的一种经典方法，它结合了单纯形法的思想与图的结构特性，通常比一般的线性规划单纯形法更高效。

解题过程

第一步：将问题建模为线性规划

首先，将问题用线性规划表示。

变量：每条边 \(e\) 的流量 \(f_e\)。

目标：最小化总成本 \(\sum_{e \in E} c_e f_e\)。

约束：

  1. 容量约束：\(0 \le f_e \le u_e\)。
  2. 流量守恒：
    • 对源点 \(s\)：\(\sum_{e \in \text{out}(s)} f_e - \sum_{e \in \text{in}(s)} f_e = F\)（总流量）。
    • 对汇点 \(t\)：\(\sum_{e \in \text{in}(t)} f_e - \sum_{e \in \text{out}(t)} f_e = F\)。
    • 对其他顶点 \(v\)：\(\sum_{e \in \text{out}(v)} f_e = \sum_{e \in \text{in}(v)} f_e\)。
  3. 最大化 \(F\) 是首要目标，但可以分阶段：先求最大流，再调整到最小成本；或者同时处理。网络单纯形属于同时处理的方法，其线性规划形式包含一个额外的约束来确保流量是最大流。

为了方便，我们引入一条从 \(t\) 到 \(s\) 的“返回边”，其容量为无穷大（或最大流值），成本为 \(-\infty\)（实际可用足够小的负数 \(-M\)），这样目标变为寻找一个最小费用的循环流。但更常见的做法是直接基于基解的图结构来设计算法。

第二步：网络单纯形的核心思想

普通单纯形法在“基可行解”间迭代。在网络流中，一个基解对应一个生成树结构（实际上是一棵生成树加上一条额外的边，形成一棵“生成树加上一条回边”的结构，称为“生成树基”）。

关键观察：

  • 对于一个有 \(n\) 个顶点的图，其基解对应一个生成树（有 \(n-1\) 条边），这些树边的流量要么是 0 要么是容量上限（即“绑定”在边界上）。
  • 剩余的边（非树边）流量可以在其上下界之间自由变化，但当前解中它们绑定在边界（0 或上界）。

网络单纯形通过改变基（即替换一条树边）来改进解，每次迭代沿着一个负费用循环调整流量，从而降低总成本。

第三步：基本数据结构与初始解

我们需要：

  1. 一棵生成树 \(T\)，包含 \(n-1\) 条边，其余边为非树边。
  2. 每个节点关联一个势 \(\pi_v\)（对偶变量），满足互补松弛条件：
    • 对每条边 \((i, j)\)：
      • 如果流量 \(f_{ij} = 0\)，则必须有 \(c_{ij} - \pi_i + \pi_j \ge 0\)。
      • 如果流量 \(f_{ij} = u_{ij}\)，则必须有 \(c_{ij} - \pi_i + \pi_j \le 0\)。
      • 如果 \(0 < f_{ij} < u_{ij}\)，则必须有 \(c_{ij} - \pi_i + \pi_j = 0\)。
  3. 初始可行解：可以先用最大流算法（如 Edmonds-Karp）求一个最大流，然后通过“消负环”得到一个可行解；或者从一个所有流量为零的“可行树”开始，逐步增加流量并调整。

实际中，常用人工变量法构造初始可行基：添加一条从 \(s\) 到 \(t\) 的高成本边，保证初始基树存在。

第四步：算法步骤

网络单纯形的主要迭代包括以下几步：

步骤 1：定价（计算边的 reduced cost）
对每条边 \((i, j)\)，定义其简化成本：

\[\bar{c}_{ij} = c_{ij} - \pi_i + \pi_j \]

其中 \(\pi\) 通过对树边（那些 \(0 < f < u\) 的边）的互补松弛条件 \(\bar{c}_{ij} = 0\) 来唯一确定（令 \(\pi_1 = 0\)，通过树递推计算其他节点的势）。

步骤 2：检查最优性
如果对所有边：

  • 若 \(f_{ij} = 0\)，有 \(\bar{c}_{ij} \ge 0\)；
  • 若 \(f_{ij} = u_{ij}\)，有 \(\bar{c}_{ij} \le 0\)；
    则当前解为最优解，算法停止。

否则，存在一条边 \(e\) 违反条件，例如：

  • 一条非树边 \(e\) 满足 \(f_e = 0\) 但 \(\bar{c}_e < 0\)，或
  • 一条非树边 \(e\) 满足 \(f_e = u_e\) 但 \(\bar{c}_e > 0\)。

选择这样一条边作为入基边。

步骤 3：确定出基边
将入基边加入当前的生成树，会形成一个唯一的循环（cycle）。调整这个循环上的流量，可以使总成本降低。

  • 如果入基边当前流量为 0，我们试图增加它的流量（沿着循环的同一方向）。
  • 如果入基边当前流量为上界，我们试图减少它的流量（沿着循环的反方向）。

调整量 \(\delta\) 由循环上各边的剩余容量决定：

  • 对与增加方向同向的边，\(\delta\) 不能超过其剩余容量（上界减去当前流量）。
  • 对与增加方向反向的边，\(\delta\) 不能超过其当前流量（因为不能为负）。

取最小的 \(\delta\) 作为调整量，那条限制调整的边就是出基边。

步骤 4：更新流量和树结构
将循环上所有边的流量增加（或减少） \(\delta\)。从树中移除出基边，加入入基边，得到新的生成树。

更新节点的势 \(\pi\)，使得新树中所有边的简化成本为零（可以通过遍历新树重新计算）。

步骤 5：重复
返回步骤 1，继续迭代，直到满足最优性条件。

第五步：算法结束与结果

当算法停止时，我们得到了一个最小费用的最大流。总成本为 \(\sum_{e} c_e f_e\)，流量为从 \(s\) 流出的总量（或流入 \(t\) 的总量）。

关键细节与注意事项

  • 防止循环：与普通单纯形法类似，需防止基循环。常用Bland法则：选择下标最小的违反条件的边入基，下标最小的限制边出基。
  • 退化解：当调整量 \(\delta = 0\) 时发生退化，可能导致无限循环。实践中可通过扰动避免。
  • 初始解：可先忽略成本，用最大流算法得到一个可行最大流，然后将其转化为一个“可行树解”（通过添加人工边或调整）。
  • 效率：网络单纯形在稀疏图上通常比普通单纯形快得多，但最坏情况复杂度不是多项式时间的。实践中，对很多实际问题非常有效。

一个比喻帮助你理解

想象一个供水系统：

  • 管道有粗细（容量）和每吨水的运输费（成本）。
  • 水源（源点）要尽量多供水到目的地（汇点），同时希望总运费最低。
  • 当前的管道布局（生成树）代表一个“基本输送方案”。
  • 如果发现某条闲置管道运费很低（简化成本为负），就把它加入方案，调整相关管道的流量，并踢出一条“满载”或“空闲”的管道，形成新方案。
  • 反复优化，直到无法找到更省钱的调整，此时得到最优方案。

通过上述步骤，你就可以理解并实现网络单纯形算法来求解最小费用最大流问题。该算法巧妙地将线性规划的单纯形法与图论中的生成树结构结合，是组合优化中的一个重要算法。

最小费用最大流问题的网络单纯形算法（Network Simplex Algorithm for Min-Cost Max-Flow） 题目描述 我们考虑一个 有向图 \( G = (V, E) \)，其中： 每条边 \( e \in E \) 具有 容量 \( u_ e > 0 \) 和 单位流量成本 \( c_ e \)（可为负数）。 图中有 源点 \( s \) 和 汇点 \( t \)。 目标：在满足 流量守恒 （除 \( s, t \) 外每个点的净流出为零）和 容量约束 的前提下， 在获得最大流量的同时，使总运输成本最小化 。 这个问题称为 最小费用最大流 （Minimum-Cost Maximum-Flow）。网络单纯形算法是求解此问题的一种经典方法，它结合了 单纯形法 的思想与 图的结构特性 ，通常比一般的线性规划单纯形法更高效。 解题过程 第一步：将问题建模为线性规划 首先，将问题用线性规划表示。 变量 ：每条边 \( e \) 的流量 \( f_ e \)。 目标 ：最小化总成本 \( \sum_ {e \in E} c_ e f_ e \)。 约束 ： 容量约束：\( 0 \le f_ e \le u_ e \)。 流量守恒： 对源点 \( s \)：\( \sum_ {e \in \text{out}(s)} f_ e - \sum_ {e \in \text{in}(s)} f_ e = F \)（总流量）。 对汇点 \( t \)：\( \sum_ {e \in \text{in}(t)} f_ e - \sum_ {e \in \text{out}(t)} f_ e = F \)。 对其他顶点 \( v \)：\( \sum_ {e \in \text{out}(v)} f_ e = \sum_ {e \in \text{in}(v)} f_ e \)。 最大化 \( F \) 是首要目标，但可以 分阶段 ：先求最大流，再调整到最小成本；或者 同时处理 。网络单纯形属于同时处理的方法，其线性规划形式包含一个额外的约束来确保流量是最大流。 为了方便，我们引入一条 从 \( t \) 到 \( s \) 的“返回边”，其容量为无穷大（或最大流值），成本为 \( -\infty \)（实际可用足够小的负数 \( -M \)），这样目标变为寻找一个 最小费用的循环流 。但更常见的做法是直接基于 基解 的图结构来设计算法。 第二步：网络单纯形的核心思想 普通单纯形法在“基可行解”间迭代。在网络流中，一个 基解 对应一个 生成树结构 （实际上是一棵 生成树 加上一条额外的边，形成一棵“生成树加上一条回边”的结构，称为“生成树基”）。 关键观察 ： 对于一个有 \( n \) 个顶点的图，其基解对应一个 生成树 （有 \( n-1 \) 条边），这些树边的流量要么是 0 要么是容量上限（即“绑定”在边界上）。 剩余的边（非树边）流量可以在其上下界之间自由变化，但当前解中它们绑定在边界（0 或上界）。 网络单纯形通过 改变基 （即替换一条树边）来改进解，每次迭代沿着一个 负费用循环 调整流量，从而降低总成本。 第三步：基本数据结构与初始解 我们需要： 一棵 生成树 \( T \)，包含 \( n-1 \) 条边，其余边为非树边。 每个节点关联一个 势 \( \pi_ v \)（对偶变量），满足 互补松弛条件 ： 对每条边 \( (i, j) \)： 如果流量 \( f_ {ij} = 0 \)，则必须有 \( c_ {ij} - \pi_ i + \pi_ j \ge 0 \)。 如果流量 \( f_ {ij} = u_ {ij} \)，则必须有 \( c_ {ij} - \pi_ i + \pi_ j \le 0 \)。 如果 \( 0 < f_ {ij} < u_ {ij} \)，则必须有 \( c_ {ij} - \pi_ i + \pi_ j = 0 \)。 初始可行解：可以先用最大流算法（如 Edmonds-Karp）求一个最大流，然后通过“消负环”得到一个可行解；或者从一个 所有流量为零 的“可行树”开始，逐步增加流量并调整。 实际中，常用 人工变量法 构造初始可行基：添加一条从 \( s \) 到 \( t \) 的高成本边，保证初始基树存在。 第四步：算法步骤 网络单纯形的主要迭代包括以下几步： 步骤 1：定价（计算边的 reduced cost） 对每条边 \( (i, j) \)，定义其 简化成本 ： \[ \bar{c} {ij} = c {ij} - \pi_ i + \pi_ j \] 其中 \( \pi \) 通过对树边（那些 \( 0 < f < u \) 的边）的 互补松弛条件 \( \bar{c}_ {ij} = 0 \) 来唯一确定（令 \( \pi_ 1 = 0 \)，通过树递推计算其他节点的势）。 步骤 2：检查最优性 如果对所有边： 若 \( f_ {ij} = 0 \)，有 \( \bar{c}_ {ij} \ge 0 \)； 若 \( f_ {ij} = u_ {ij} \)，有 \( \bar{c}_ {ij} \le 0 \)； 则当前解为 最优解 ，算法停止。 否则，存在一条边 \( e \) 违反条件，例如： 一条非树边 \( e \) 满足 \( f_ e = 0 \) 但 \( \bar{c}_ e < 0 \)，或 一条非树边 \( e \) 满足 \( f_ e = u_ e \) 但 \( \bar{c}_ e > 0 \)。 选择这样一条边作为 入基边 。 步骤 3：确定出基边 将入基边加入当前的生成树，会形成一个唯一的 循环 （cycle）。调整这个循环上的流量，可以使总成本降低。 如果入基边当前流量为 0，我们试图增加它的流量（沿着循环的同一方向）。 如果入基边当前流量为上界，我们试图减少它的流量（沿着循环的反方向）。 调整量 \( \delta \) 由循环上各边的 剩余容量 决定： 对与增加方向同向的边，\( \delta \) 不能超过其剩余容量（上界减去当前流量）。 对与增加方向反向的边，\( \delta \) 不能超过其当前流量（因为不能为负）。 取最小的 \( \delta \) 作为调整量，那条限制调整的边就是 出基边 。 步骤 4：更新流量和树结构 将循环上所有边的流量增加（或减少） \( \delta \)。从树中移除出基边，加入入基边，得到新的生成树。 更新节点的势 \( \pi \)，使得新树中所有边的简化成本为零（可以通过遍历新树重新计算）。 步骤 5：重复 返回步骤 1，继续迭代，直到满足最优性条件。 第五步：算法结束与结果 当算法停止时，我们得到了一个 最小费用的最大流 。总成本为 \( \sum_ {e} c_ e f_ e \)，流量为从 \( s \) 流出的总量（或流入 \( t \) 的总量）。 关键细节与注意事项 防止循环 ：与普通单纯形法类似，需防止基循环。常用 Bland法则 ：选择下标最小的违反条件的边入基，下标最小的限制边出基。 退化解 ：当调整量 \( \delta = 0 \) 时发生退化，可能导致无限循环。实践中可通过扰动避免。 初始解 ：可先忽略成本，用最大流算法得到一个可行最大流，然后将其转化为一个“可行树解”（通过添加人工边或调整）。 效率 ：网络单纯形在稀疏图上通常比普通单纯形快得多，但最坏情况复杂度不是多项式时间的。实践中，对很多实际问题非常有效。 一个比喻帮助你理解 想象一个供水系统： 管道有粗细（容量）和每吨水的运输费（成本）。 水源（源点）要尽量多供水到目的地（汇点），同时希望总运费最低。 当前的管道布局（生成树）代表一个“基本输送方案”。 如果发现某条闲置管道运费很低（简化成本为负），就把它加入方案，调整相关管道的流量，并踢出一条“满载”或“空闲”的管道，形成新方案。 反复优化，直到无法找到更省钱的调整，此时得到最优方案。 通过上述步骤，你就可以理解并实现网络单纯形算法来求解最小费用最大流问题。该算法巧妙地将线性规划的单纯形法与图论中的生成树结构结合，是组合优化中的一个重要算法。