基于线性规划的图最小成本最大流问题求解示例
字数 7464 2025-12-20 14:41:13

基于线性规划的图最小成本最大流问题求解示例

我将为您讲解一个在“线性规划”与“网络流”交叉领域的重要问题：图最小成本最大流问题。这个问题的核心是，在给定网络容量限制下，寻找一个流量总和最大的流（即最大流），并且在所有这样的最大流中，总运输成本最小的那一个。这是一个经典的组合优化问题，可以通过线性规划（LP）优雅地建模，并利用网络结构设计出比通用单纯形法更高效的专门算法。

1. 问题描述

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

  • \(V\) 是顶点集合， \(|V| = n\)。
  • \(E\) 是有向边集合， \(|E| = m\)。
  • 每条边 \((i, j) \in E\) 有两个关键参数：
    1. 容量 \(u_{ij} \geq 0\): 表示该边上允许流过的最大流量。
    2. 单位流成本 \(c_{ij} \in \mathbb{R}\): 表示每单位流量通过该边所产生的成本（可为负，表示“利润”）。
  • 图中指定两个特殊顶点：
    1. 源点 \(s \in V\)。
    2. 汇点 \(t \in V\) ( \(s \neq t\) )。
  • 目标：在所有从 \(s\) 到 \(t\) 的可行流中，找到一个最大流（即从 \(s\) 流出/流入 \(t\) 的流量总和最大），并且在所有最大流中，其总成本最小。换句话说，我们首先最大化流量 \(|f|\) (称为流值)，然后在这个最大流值下最小化成本。

2. 线性规划建模

设决策变量 \(f_{ij} \geq 0\) 表示边 \((i, j)\) 上的流量。

目标函数：最小化总运输成本。

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

约束条件：

  1. 容量约束：每条边上的流量不能超过其容量。

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

  1. 流量守恒约束：除源点 \(s\) 和汇点 \(t\) 外，每个顶点的净流量为零（流入等于流出）。对于 \(s\) 和 \(t\)，我们定义其净流出为流值 \(|f|\)。
    • 令 \(f^{\text{out}}(i) = \sum_{j: (i, j) \in E} f_{ij}\) 为从 \(i\) 流出的总流量。
    • 令 \(f^{\text{in}}(i) = \sum_{j: (j, i) \in E} f_{ji}\) 为流入 \(i\) 的总流量。
    • 流量守恒可写为：

\[ f^{\text{out}}(i) - f^{\text{in}}(i) = \begin{cases} |f|, & \text{if } i = s \\ -|f|, & \text{if } i = t \\ 0, & \text{otherwise} \end{cases} \]

  1. 流值最大化：为了将“最大流”和“最小成本”统一在一个模型中，我们引入一个变量 \(F\) 表示流值，并将其最大化间接转化为一个约束。但标准的最小成本最大流建模通常采用两阶段法或引入一个大M惩罚。更直接且符合线性规划形式的建模是：我们将流值 \(F\) 作为一个变量，在目标函数中先最大化 \(F\)（用负号转为最小化），再最小化成本。但为了得到一个纯最小化的线性规划，我们可以固定流值 \(F\) 为最大可能值，然后求最小成本。然而，最大流值我们事先并不知道。
    因此，一个优雅的方法是利用对偶理论，但更直观的教学模型是将其拆解为两步，或者构建一个能同时实现这两个目标的扩展模型。然而，一个更标准的线性规划表述是：我们将目标函数改为最小化 \(\sum c_{ij} f_{ij} - M \cdot F\)，其中 \(M\) 是一个非常大的正数，这样优化程序会优先最大化 \(F\)（因为 \(-M \cdot F\) 是负成本，最小化总成本时会先尽可能增大 \( F\)），然后再最小化实际成本 \(\sum c_{ij} f_{ij}\)。但为了使讲解更聚焦于核心思想，我们通常先求解最大流问题得到最大流值 \(F_{\max}\)，然后在流量守恒约束中固定 \(|f| = F_{\max}\)，再求解上述线性规划。这样，问题就变成了一个固定流值的最小成本流问题。

    最终使用的线性规划模型（假设我们已通过最大流算法，如Edmonds-Karp，求得最大流值 \(F_{\max}\)）：

\[ \begin{aligned} \min \quad & \sum_{(i, j) \in E} c_{ij} f_{ij} \\ \text{s.t.} \quad & f^{\text{out}}(i) - f^{\text{in}}(i) = \begin{cases} F_{\max}, & i = s \\ -F_{\max}, & i = t \\ 0, & \text{otherwise} \end{cases} \\ & 0 \leq f_{ij} \leq u_{ij} \quad \forall (i, j) \in E \end{aligned} \]

这是一个标准的线性规划，变量数为 $ m $，约束数为 $ n + m $（流量守恒 $ n $ 条，容量约束 $ m $ 条）。

3. 基于网络单纯形法的求解思路

虽然可以直接用通用单纯形法求解上述LP，但利用问题的网络流结构，有更高效的专门算法，例如最小费用流算法（如消圈算法、连续最短路径算法、最小平均回路消去算法等）。这些算法本质上是针对这个特定LP结构的原始-对偶或单纯形法的变体。

这里，我为您讲解最直观的连续最短路径算法（Successive Shortest Path Algorithm, SSPA），它非常适合理解如何将“最小成本”和“最大流”两个目标结合起来。

算法核心思想：

  1. 从零流开始（ \(f_{ij} = 0\) ）。
  2. 每次迭代，我们都尝试沿着从源点 \(s\) 到汇点 \(t\) 的当前残差网络中一条“最短”（即单位成本最小）的可增广路径，尽可能多地增加流量，直到无法再增加流量（即达到最大流）为止。
  3. 这里“最短路径”的成本是基于边在残差网络中的成本计算的。在残差网络中：
    • 对于原图中的边 \((i, j)\)，如果当前流量 \(f_{ij} < u_{ij}\)，则残差边 \((i, j)\) 存在，其残差容量为 \(r_{ij} = u_{ij} - f_{ij}\)，成本为 \(c_{ij}\)。
    • 对于原图中的边 \((i, j)\)，如果当前流量 \(f_{ij} > 0\)，则反向边 \((j, i)\) 存在，其残差容量为 \(f_{ij}\)，成本为 \(-c_{ij}\)（因为退回流量可以节省成本）。
  4. 在残差网络中寻找从 \(s\) 到 \(t\) 的、以单位流成本为边权的最短路径（即最小成本路径），可以使用能处理负边权但不含负回路的算法，如Bellman-Ford算法（如果初始成本有负值）或其改进版本。为了高效，常引入势函数（Reduced Cost） 将边权转为非负，然后使用Dijkstra算法。

逐步求解过程：
我们通过一个具体例子来演示。
考虑下图：

  • 顶点： \(V = \{s, a, b, t\}\)， \(s=1, t=4\)。
  • 有向边及其 \((容量, 单位成本)\)：
    \((s,a): (2, 2)\)
    \((s,b): (3, 1)\)
    \((a,b): (1, 1)\)
    \((a,t): (1, 3)\)
    \((b,t): (2, 2)\)

目标：求从 \(s\) 到 \(t\) 的最小成本最大流。

步骤1：初始化
初始流 \(f = 0\)。总流量 \(F = 0\)，总成本 \(Cost = 0\)。

步骤2：构建初始残差网络
残差网络包含所有原边（容量=原容量，成本=原成本），反向边暂时没有（因为初始流为0）。
我们需要找到从 \(s\) 到 \(t\) 的、以成本为边权的最短路径。由于没有负边权，可以直接用Dijkstra算法。

  • 从 \(s\) 出发的最短路径树： \(s \to a\) 成本2， \(s \to b\) 成本1。
  • 到 \(t\) 的最短路径： \(s \to b \to t\)，成本 = 1+2=3，路径容量瓶颈 = min(3, 2)=2。

步骤3：沿最短路径增广
沿着路径 \(s \to b \to t\) 推送2单位流量。
更新：

  • \(f_{sb} = 2\) (容量3，剩余1)
  • \(f_{bt} = 2\) (容量2，剩余0)
    总流量 \(F = 2\)，总成本增加 \(2 \times (1+2) = 6\)， \(Cost = 6\)。

步骤4：更新残差网络
正向边容量减少，并创建反向边。

  • 边 \((s,b)\)：剩余容量 = 3-2=1，成本1。新增反向边 \((b,s)\)：容量=2，成本=-1。
  • 边 \((b,t)\)：剩余容量 = 2-2=0，成本2（实际上已满，在残差网络中正向边消失）。新增反向边 \((t,b)\)：容量=2，成本=-2。

步骤5：继续寻找最短增广路
在更新后的残差网络中，计算从 \(s\) 到 \(t\) 的最短路径。
残差边及其成本：
\((s,a): cap=2, cost=2\)
\((s,b): cap=1, cost=1\)
\((a,b): cap=1, cost=1\) (原图)
\((a,t): cap=1, cost=3\)
\((b,s): cap=2, cost=-1\) (反向)
\((t,b): cap=2, cost=-2\) (反向)
使用Bellman-Ford计算最短路径（因为有负成本反向边）：
从 \(s\) 出发的距离（成本）：

  • 到 \(s\): 0
  • 到 \(a\): 2 (路径 s-a)
  • 到 \(b\)：有两种可能：
    • 直接 s-b: 成本1
    • 经过 a: s->a(2) + a->b(1)=3。所以最短是1。
  • 到 \(t\)：考虑所有可能：
    • s->a->t: 2+3=5
    • s->b->t: 但 (b,t) 已满，正向边不存在，不能走。
    • s->a->b->? 但 (b,t) 不可用。
    • s->b->s->a->t: 1 + (-1) + 2 + 3 = 5 (走负边绕路)
    • 发现一条路径：s->b->s->a->t? 不行，因为 b->s 是反向边，允许走，但 s 已访问过通常避免循环，但Bellman-Ford能处理。实际上，计算发现 s->b (cost1) -> t? 不通。s->a (cost2)->b (cost1) ->? 到t不通。看来从s到t的路径必须包含 (a,t) 或找到新的。检查 s->a->b->? 到t不通。似乎没有更短于5的路径？等一下，让我们仔细看：从s到t，必须有一条边进入t。可能的入边是 (a,t) 成本3，或者 (b,t) 已满。所以必须通过a。到a的最短路径是s-a成本2，然后a-t成本3，总5。所以当前最短路径是 s->a->t，成本5，瓶颈容量 = min(2,1)=1。

沿路径 \(s \to a \to t\) 推送1单位流量。
更新：

  • \(f_{sa} = 1\) (容量2，剩余1)
  • \(f_{at} = 1\) (容量1，剩余0)
    总流量 \(F = 2+1=3\)，总成本增加 \(1 \times (2+3)=5\)， \(Cost = 6+5=11\)。

步骤6：再次更新残差网络

  • 边 \((s,a)\)：剩余容量=1，成本2。新增反向边 \((a,s)\): 容量=1，成本=-2。
  • 边 \((a,t)\)：剩余容量=0（消失）。新增反向边 \((t,a)\): 容量=1，成本=-3。

步骤7：继续寻找增广路
当前残差网络（只列出容量>0的边）：
\((s,a): cap=1, cost=2\)
\((s,b): cap=1, cost=1\)
\((a,b): cap=1, cost=1\)
\((b,t):\) 正向消失
反向边：
\((b,s): cap=2, cost=-1\)
\((t,b): cap=2, cost=-2\)
\((a,s): cap=1, cost=-2\)
\((t,a): cap=1, cost=-3\)
计算从 \(s\) 到 \(t\) 的最短路径。注意，现在 (b,t) 已满，但我们可以通过“退流”来重新安排流。考虑路径 \(s \to b \to a \to t\) 是否存在？让我们检查：
s->b: 成本1，容量1。
b->a? 没有直接边。但有 a->b 容量1 成本1 是正向边，但方向是a到b，不能从b到a。不过，我们可以走 b->s->a? 但 s 是源点，通常算法避免走回源点，但Bellman-Ford允许。让我们用距离标号系统（势函数）来规范计算。为了简便，我们列出可能路径：

  1. s->a->t: 但 (a,t) 已满，正向边消失。所以不行。
  2. s->a->b->? 到t? (b,t) 已满。不行。
  3. s->b->? 到t? (b,t) 已满。不行。
  4. s->b->s->a->t: 1 + (-1) + 2 + ? 但 (a,t) 已满，不行。
    看来似乎没有从s到t的路径了？等等，我们还有边 (a,b) 可用。考虑路径 s->a->b->? 但 (b,t) 已满。不过我们可以利用反向边 (t,b) 退回流量，从而“腾出”空间给 (a,b) 来的流量。实际上，存在一条增广路径： \(s \to a \to b \to t\) 吗？不，因为 (b,t) 已满，所以不能直接从b到t。但我们可以考虑更复杂的路径： \(s \to b \to a \to t\) 是不通的，因为没有 b->a 的边。让我们用“最短增广路”算法的标准步骤，通过维护势函数来简化计算。

由于引入势函数细节较多，我们换一种更直观的方法：检查当前的流是否是最大流。我们可以从 \(s\) 出发，在残差网络中看是否能到达 \(t\)。
从 \(s\) 可达的节点：走 (s,a) 到 a，从 a 可以走 (a,b) 到 b。从 b 出发，正向边 (b,t) 已满消失，反向边 (t,b) 是回到 t 的，但 t 是汇点，从 b 无法直接到 t。所以从 s 无法到达 t。因此，当前流已经是最大流。

步骤8：验证流值最大化
原图最大流是多少？我们可以用最大流算法快速验证。从 s 出发，有两条出去边：到a容量2，到b容量3，总容量5。进入t的边：从a来容量1，从b来容量2，总容量3。所以最大流受限于进入t的容量，最大为3。我们目前流量F=3，已经达到最大。

步骤9：结果
我们得到了一个最大流，流值为3。其总成本为11。但这是最小成本的最大流吗？我们需要检查是否存在另一个总流量为3的流，其成本更低。例如，如果我们调整流：原来从 s-b-t 走了2单位，成本 2*(1+2)=6。从 s-a-t 走了1单位，成本 1*(2+3)=5。总11。
考虑另一种分配：让 s-b 只走1单位，s-a 走2单位？但 a-t 容量只有1，所以从a只能输出1单位到t，多出的1单位必须从 a-b 走到b，然后和 s-b 的流一起到 t。试试：

  • 路径1: s-a-t: 流量1，成本 2+3=5。
  • 路径2: s-a-b-t: 流量1，成本 2+1+2=5。
  • 路径3: s-b-t: 流量1，成本 1+2=3。
    总流量 = 1+1+1=3，总成本 = 5+5+3=13 > 11。所以我们的解成本11更优。再尝试其他组合，最终可验证11是最小的。

因此，最小成本最大流的流值为3，总成本为11。具体流分布：
\(f_{sa}=1, f_{sb}=2, f_{ab}=0, f_{at}=1, f_{bt}=2\)。

4. 算法总结与要点

  1. 建模：将最小成本最大流问题可以精确地建模为一个线性规划问题。
  2. 求解策略：通常采用两阶段法或集成法。上述连续最短路径算法是集成法的代表，它在每次迭代中沿残差网络的最短（最小单位成本）增广路径发送尽可能多的流量，直到无法增广。这保证了最终得到的流既是最大流，也是所有最大流中总成本最小的。
  3. 负成本边：如果原图中有负成本边，算法初始可能需要用Bellman-Ford检测并消除负成本圈，或引入势函数。
  4. 最优性条件：该算法基于一个重要的最优性条件：当且仅当残差网络中不存在从 \(s\) 到 \(t\) 的路径，并且不存在负成本圈（关于某个势函数）时，当前流是最小成本最大流。
  5. 效率：如果使用适当的势函数和Dijkstra算法求最短路径，该算法的时间复杂度为 \(O(F \cdot m \log n)\)，其中 \(F\) 是最大流值。对于整数容量，这是一个伪多项式时间算法。有更高效的多项式时间算法（如容量缩放、成本缩放等），但上述算法易于理解和实现。

这个示例展示了如何将一个具有双重目标（最大流、最小成本）的网络流问题，通过线性规划建模和专门的组合算法进行求解，体现了线性规划思想与图算法设计的巧妙结合。

基于线性规划的图最小成本最大流问题求解示例 我将为您讲解一个在“线性规划”与“网络流”交叉领域的重要问题： 图最小成本最大流问题 。这个问题的核心是，在给定网络容量限制下，寻找一个流量总和最大的流（即最大流），并且在所有这样的最大流中，总运输成本最小的那一个。这是一个经典的组合优化问题，可以通过线性规划（LP）优雅地建模，并利用网络结构设计出比通用单纯形法更高效的专门算法。 1. 问题描述 我们有一个 有向图 \( G = (V, E) \)，其中： \( V \) 是顶点集合， \( |V| = n \)。 \( E \) 是有向边集合， \( |E| = m \)。 每条边 \( (i, j) \in E \) 有两个关键参数： 容量 \( u_ {ij} \geq 0 \): 表示该边上允许流过的最大流量。 单位流成本 \( c_ {ij} \in \mathbb{R} \): 表示每单位流量通过该边所产生的成本（可为负，表示“利润”）。 图中指定两个特殊顶点： 源点 \( s \in V \)。 汇点 \( t \in V \) ( \( s \neq t \) )。 目标：在所有从 \( s \) 到 \( t \) 的可行流中，找到一个 最大流 （即从 \( s \) 流出/流入 \( t \) 的流量总和最大），并且 在所有最大流中，其总成本最小 。换句话说，我们首先最大化流量 \( |f| \) (称为流值)，然后在这个最大流值下最小化成本。 2. 线性规划建模 设决策变量 \( f_ {ij} \geq 0 \) 表示边 \( (i, j) \) 上的流量。 目标函数 ：最小化总运输成本。 \[ \min \sum_ {(i, j) \in E} c_ {ij} f_ {ij} \] 约束条件 ： 容量约束 ：每条边上的流量不能超过其容量。 \[ 0 \leq f_ {ij} \leq u_ {ij} \quad \forall (i, j) \in E \] 流量守恒约束 ：除源点 \( s \) 和汇点 \( t \) 外，每个顶点的净流量为零（流入等于流出）。对于 \( s \) 和 \( t \)，我们定义其净流出为流值 \( |f| \)。 令 \( f^{\text{out}}(i) = \sum_ {j: (i, j) \in E} f_ {ij} \) 为从 \( i \) 流出的总流量。 令 \( f^{\text{in}}(i) = \sum_ {j: (j, i) \in E} f_ {ji} \) 为流入 \( i \) 的总流量。 流量守恒可写为： \[ f^{\text{out}}(i) - f^{\text{in}}(i) = \begin{cases} |f|, & \text{if } i = s \\ -|f|, & \text{if } i = t \\ 0, & \text{otherwise} \end{cases} \] 流值最大化 ：为了将“最大流”和“最小成本”统一在一个模型中，我们引入一个 变量 \( F \) 表示流值，并 将其最大化间接转化为一个约束 。但标准的最小成本最大流建模通常采用 两阶段法 或 引入一个大M惩罚 。更直接且符合线性规划形式的建模是： 我们将流值 \( F \) 作为一个变量，在目标函数中先最大化 \( F \)（用负号转为最小化），再最小化成本 。但为了得到一个纯最小化的线性规划，我们可以 固定流值 \( F \) 为最大可能值 ，然后求最小成本。然而，最大流值我们事先并不知道。 因此，一个优雅的方法是 利用对偶理论 ，但更直观的教学模型是将其拆解为两步，或者构建一个能同时实现这两个目标的 扩展模型 。然而，一个更标准的线性规划表述是：我们将目标函数改为最小化 \( \sum c_ {ij} f_ {ij} - M \cdot F \)，其中 \( M \) 是一个非常大的正数，这样优化程序会优先最大化 \( F \)（因为 \(-M \cdot F\) 是负成本，最小化总成本时会先尽可能增大 \( F\)），然后再最小化实际成本 \( \sum c_ {ij} f_ {ij} \)。但为了使讲解更聚焦于核心思想，我们通常 先求解最大流问题得到最大流值 \( F_ {\max} \) ，然后 在流量守恒约束中固定 \( |f| = F_ {\max} \) ，再求解上述线性规划。这样，问题就变成了一个 固定流值的最小成本流问题 。 最终使用的线性规划模型 （假设我们已通过最大流算法，如Edmonds-Karp，求得最大流值 \( F_ {\max} \)）： \[ \begin{aligned} \min \quad & \sum_ {(i, j) \in E} c_ {ij} f_ {ij} \\ \text{s.t.} \quad & f^{\text{out}}(i) - f^{\text{in}}(i) = \begin{cases} F_ {\max}, & i = s \\ -F_ {\max}, & i = t \\ 0, & \text{otherwise} \end{cases} \\ & 0 \leq f_ {ij} \leq u_ {ij} \quad \forall (i, j) \in E \end{aligned} \] 这是一个标准的线性规划，变量数为 \( m \)，约束数为 \( n + m \)（流量守恒 \( n \) 条，容量约束 \( m \) 条）。 3. 基于网络单纯形法的求解思路 虽然可以直接用通用单纯形法求解上述LP，但利用问题的网络流结构，有更高效的专门算法，例如 最小费用流算法 （如 消圈算法 、 连续最短路径算法 、 最小平均回路消去算法 等）。这些算法本质上是针对这个特定LP结构的原始-对偶或单纯形法的变体。 这里，我为您讲解最直观的 连续最短路径算法 （Successive Shortest Path Algorithm, SSPA），它非常适合理解如何将“最小成本”和“最大流”两个目标结合起来。 算法核心思想 ： 从零流开始（ \( f_ {ij} = 0 \) ）。 每次迭代，我们都尝试 沿着从源点 \( s \) 到汇点 \( t \) 的当前残差网络中一条“最短”（即单位成本最小）的可增广路径 ，尽可能多地增加流量，直到无法再增加流量（即达到最大流）为止。 这里“最短路径”的成本是基于 边在残差网络中的成本 计算的。在残差网络中： 对于原图中的边 \( (i, j) \)，如果当前流量 \( f_ {ij} < u_ {ij} \)，则残差边 \( (i, j) \) 存在，其 残差容量 为 \( r_ {ij} = u_ {ij} - f_ {ij} \)， 成本 为 \( c_ {ij} \)。 对于原图中的边 \( (i, j) \)，如果当前流量 \( f_ {ij} > 0 \)，则反向边 \( (j, i) \) 存在，其 残差容量 为 \( f_ {ij} \)， 成本 为 \( -c_ {ij} \)（因为退回流量可以节省成本）。 在残差网络中寻找从 \( s \) 到 \( t \) 的、以单位流成本为边权的最短路径（即最小成本路径），可以使用能处理负边权但不含负回路的算法，如 Bellman-Ford算法 （如果初始成本有负值）或其改进版本。为了高效，常引入 势函数（Reduced Cost） 将边权转为非负，然后使用Dijkstra算法。 逐步求解过程 ： 我们通过一个具体例子来演示。 考虑下图： 顶点： \( V = \{s, a, b, t\} \)， \( s=1, t=4 \)。 有向边及其 \( (容量, 单位成本) \)： \( (s,a): (2, 2) \) \( (s,b): (3, 1) \) \( (a,b): (1, 1) \) \( (a,t): (1, 3) \) \( (b,t): (2, 2) \) 目标 ：求从 \( s \) 到 \( t \) 的最小成本最大流。 步骤1：初始化 初始流 \( f = 0 \)。总流量 \( F = 0 \)，总成本 \( Cost = 0 \)。 步骤2：构建初始残差网络 残差网络包含所有原边（容量=原容量，成本=原成本），反向边暂时没有（因为初始流为0）。 我们需要找到从 \( s \) 到 \( t \) 的、以成本为边权的最短路径。由于没有负边权，可以直接用Dijkstra算法。 从 \( s \) 出发的最短路径树： \( s \to a \) 成本2， \( s \to b \) 成本1。 到 \( t \) 的最短路径： \( s \to b \to t \)，成本 = 1+2=3，路径容量瓶颈 = min(3, 2)=2。 步骤3：沿最短路径增广 沿着路径 \( s \to b \to t \) 推送2单位流量。 更新： \( f_ {sb} = 2 \) (容量3，剩余1) \( f_ {bt} = 2 \) (容量2，剩余0) 总流量 \( F = 2 \)，总成本增加 \( 2 \times (1+2) = 6 \)， \( Cost = 6 \)。 步骤4：更新残差网络 正向边容量减少，并创建反向边。 边 \( (s,b) \)：剩余容量 = 3-2=1，成本1。新增反向边 \( (b,s) \)：容量=2，成本=-1。 边 \( (b,t) \)：剩余容量 = 2-2=0，成本2（实际上已满，在残差网络中正向边消失）。新增反向边 \( (t,b) \)：容量=2，成本=-2。 步骤5：继续寻找最短增广路 在更新后的残差网络中，计算从 \( s \) 到 \( t \) 的最短路径。 残差边及其成本： \( (s,a): cap=2, cost=2 \) \( (s,b): cap=1, cost=1 \) \( (a,b): cap=1, cost=1 \) (原图) \( (a,t): cap=1, cost=3 \) \( (b,s): cap=2, cost=-1 \) (反向) \( (t,b): cap=2, cost=-2 \) (反向) 使用Bellman-Ford计算最短路径（因为有负成本反向边）： 从 \( s \) 出发的距离（成本）： 到 \( s \): 0 到 \( a \): 2 (路径 s-a) 到 \( b \)：有两种可能： 直接 s-b: 成本1 经过 a: s->a(2) + a->b(1)=3。所以最短是1。 到 \( t \)：考虑所有可能： s->a->t: 2+3=5 s->b->t: 但 (b,t) 已满，正向边不存在，不能走。 s->a->b->? 但 (b,t) 不可用。 s->b->s->a->t: 1 + (-1) + 2 + 3 = 5 (走负边绕路) 发现一条路径：s->b->s->a->t? 不行，因为 b->s 是反向边，允许走，但 s 已访问过通常避免循环，但Bellman-Ford能处理。实际上，计算发现 s->b (cost1) -> t? 不通。s->a (cost2)->b (cost1) ->? 到t不通。看来从s到t的路径必须包含 (a,t) 或找到新的。检查 s->a->b->? 到t不通。似乎没有更短于5的路径？等一下，让我们仔细看：从s到t，必须有一条边进入t。可能的入边是 (a,t) 成本3，或者 (b,t) 已满。所以必须通过a。到a的最短路径是s-a成本2，然后a-t成本3，总5。所以当前最短路径是 s->a->t，成本5，瓶颈容量 = min(2,1)=1。 沿路径 \( s \to a \to t \) 推送1单位流量。 更新： \( f_ {sa} = 1 \) (容量2，剩余1) \( f_ {at} = 1 \) (容量1，剩余0) 总流量 \( F = 2+1=3 \)，总成本增加 \( 1 \times (2+3)=5 \)， \( Cost = 6+5=11 \)。 步骤6：再次更新残差网络 边 \( (s,a) \)：剩余容量=1，成本2。新增反向边 \( (a,s) \): 容量=1，成本=-2。 边 \( (a,t) \)：剩余容量=0（消失）。新增反向边 \( (t,a) \): 容量=1，成本=-3。 步骤7：继续寻找增广路 当前残差网络（只列出容量>0的边）： \( (s,a): cap=1, cost=2 \) \( (s,b): cap=1, cost=1 \) \( (a,b): cap=1, cost=1 \) \( (b,t): \) 正向消失 反向边： \( (b,s): cap=2, cost=-1 \) \( (t,b): cap=2, cost=-2 \) \( (a,s): cap=1, cost=-2 \) \( (t,a): cap=1, cost=-3 \) 计算从 \( s \) 到 \( t \) 的最短路径。注意，现在 (b,t) 已满，但我们可以通过“退流”来重新安排流。考虑路径 \( s \to b \to a \to t \) 是否存在？让我们检查： s->b: 成本1，容量1。 b->a? 没有直接边。但有 a->b 容量1 成本1 是正向边，但方向是a到b，不能从b到a。不过，我们可以走 b->s->a? 但 s 是源点，通常算法避免走回源点，但Bellman-Ford允许。让我们用距离标号系统（势函数）来规范计算。为了简便，我们列出可能路径： s->a->t: 但 (a,t) 已满，正向边消失。所以不行。 s->a->b->? 到t? (b,t) 已满。不行。 s->b->? 到t? (b,t) 已满。不行。 s->b->s->a->t: 1 + (-1) + 2 + ? 但 (a,t) 已满，不行。 看来似乎没有从s到t的路径了？等等，我们还有边 (a,b) 可用。考虑路径 s->a->b->? 但 (b,t) 已满。不过我们可以利用反向边 (t,b) 退回流量，从而“腾出”空间给 (a,b) 来的流量。实际上，存在一条增广路径： \( s \to a \to b \to t \) 吗？不，因为 (b,t) 已满，所以不能直接从b到t。但我们可以考虑更复杂的路径： \( s \to b \to a \to t \) 是不通的，因为没有 b->a 的边。让我们用“最短增广路”算法的标准步骤，通过维护势函数来简化计算。 由于引入势函数细节较多，我们换一种更直观的方法：检查当前的流是否是最大流。我们可以从 \( s \) 出发，在残差网络中看是否能到达 \( t \)。 从 \( s \) 可达的节点：走 (s,a) 到 a，从 a 可以走 (a,b) 到 b。从 b 出发，正向边 (b,t) 已满消失，反向边 (t,b) 是回到 t 的，但 t 是汇点，从 b 无法直接到 t。所以从 s 无法到达 t。 因此，当前流已经是最大流 。 步骤8：验证流值最大化 原图最大流是多少？我们可以用最大流算法快速验证。从 s 出发，有两条出去边：到a容量2，到b容量3，总容量5。进入t的边：从a来容量1，从b来容量2，总容量3。所以最大流受限于进入t的容量，最大为3。我们目前流量F=3，已经达到最大。 步骤9：结果 我们得到了一个最大流，流值为3。其总成本为11。但这是最小成本的最大流吗？我们需要检查是否存在另一个总流量为3的流，其成本更低。例如，如果我们调整流：原来从 s-b-t 走了2单位，成本 2* (1+2)=6。从 s-a-t 走了1单位，成本 1* (2+3)=5。总11。 考虑另一种分配：让 s-b 只走1单位，s-a 走2单位？但 a-t 容量只有1，所以从a只能输出1单位到t，多出的1单位必须从 a-b 走到b，然后和 s-b 的流一起到 t。试试： 路径1: s-a-t: 流量1，成本 2+3=5。 路径2: s-a-b-t: 流量1，成本 2+1+2=5。 路径3: s-b-t: 流量1，成本 1+2=3。 总流量 = 1+1+1=3，总成本 = 5+5+3=13 > 11。所以我们的解成本11更优。再尝试其他组合，最终可验证11是最小的。 因此， 最小成本最大流 的流值为3，总成本为11。具体流分布： \( f_ {sa}=1, f_ {sb}=2, f_ {ab}=0, f_ {at}=1, f_ {bt}=2 \)。 4. 算法总结与要点 建模 ：将最小成本最大流问题可以精确地建模为一个线性规划问题。 求解策略 ：通常采用 两阶段法 或 集成法 。上述连续最短路径算法是集成法的代表，它在每次迭代中沿残差网络的最短（最小单位成本）增广路径发送尽可能多的流量，直到无法增广。这保证了最终得到的流既是最大流，也是所有最大流中总成本最小的。 负成本边 ：如果原图中有负成本边，算法初始可能需要用Bellman-Ford检测并消除负成本圈，或引入势函数。 最优性条件 ：该算法基于一个重要的最优性条件： 当且仅当残差网络中不存在从 \( s \) 到 \( t \) 的路径，并且不存在负成本圈（关于某个势函数）时，当前流是最小成本最大流 。 效率 ：如果使用适当的势函数和Dijkstra算法求最短路径，该算法的时间复杂度为 \( O(F \cdot m \log n) \)，其中 \( F \) 是最大流值。对于整数容量，这是一个伪多项式时间算法。有更高效的多项式时间算法（如容量缩放、成本缩放等），但上述算法易于理解和实现。 这个示例展示了如何将一个具有双重目标（最大流、最小成本）的网络流问题，通过线性规划建模和专门的组合算法进行求解，体现了线性规划思想与图算法设计的巧妙结合。