基于线性规划的图最大流问题的最小费用流模型转换求解示例
1. 题目描述
我们考虑一个经典的网络流问题：最大流问题。给定一个有向图 G=(V, E)，其中V是顶点集合，E是边集合。图中有一个指定的源点 s ∈ V 和一个指定的汇点 t ∈ V。每条边 e ∈ E 有一个非负的容量 c(e) ≥ 0。最大流问题的目标是找到从源点 s 到汇点 t 的流量最大值，使得流满足容量约束（每条边上的流量不超过其容量）和流量守恒约束（除源点和汇点外，每个顶点的净流入等于净流出）。
本示例将介绍一种特殊的求解方法：将最大流问题转化为一个最小费用流问题，并通过求解后者来得到最大流。这种方法的核心思想是，在原始图的每条边上增加一个微小的、均匀的、与流量相关的“单位费用”（例如，对所有边设置单位费用为1），然后求解以“总费用最小”为目标、以“从s到t发送尽可能大的流量”为约束的最小费用流问题。当总流量达到最大时，求解的目标是使“总费用”最小，这等价于在实现最大流的前提下，使得“某种衡量指标”（这里是总流量路径长度，或简单理解为总流量）尽可能小，但这不影响最大流值本身的求解。通过精心设置这个费用，我们可以利用最小费用流算法（如网络单纯形法、连续最短路径增广算法等）来高效地找到最大流。
给定示例：
考虑下图：
- 顶点：V = {s, a, b, t}
- 有向边与容量：
s -> a, 容量 3
s -> b, 容量 2
a -> b, 容量 2
a -> t, 容量 2
b -> t, 容量 3 - 源点 s，汇点 t。
我们需要找出从s到t的最大流值，并通过将其转化为最小费用流问题来求解。
2. 解题过程
第一步：建立最大流问题的线性规划模型
首先，我们为每条边 e ∈ E 定义一个决策变量 f(e)，表示流过该边的流量。
- 目标：最大化从源点s发出的总流量（也等于流入汇点t的总流量）。
- 约束：
- 容量约束：对于每条边 e ∈ E，有 0 ≤ f(e) ≤ c(e)。
- 流量守恒约束：对于每个顶点 v ∈ V \ {s, t}，流入流量之和等于流出流量之和。
- 源点s的流出等于汇点t的流入，这个值即为总流量 F。
标准的线性规划模型如下：
决策变量：f(sa), f(sb), f(ab), f(at), f(bt)，以及总流量F。
目标函数：Maximize F
约束：
- 容量约束：
f(sa) ≤ 3
f(sb) ≤ 2
f(ab) ≤ 2
f(at) ≤ 2
f(bt) ≤ 3
所有 f(.) ≥ 0 - 流量守恒：
对于顶点 a: 流入 = f(sa) 流出 = f(ab) + f(at) => f(sa) = f(ab) + f(at)
对于顶点 b: 流入 = f(sb) + f(ab) 流出 = f(bt) => f(sb) + f(ab) = f(bt) - 源汇流量关联：
s 流出 = f(sa) + f(sb) = F
t 流入 = f(at) + f(bt) = F
第二步：将最大流问题转化为最小费用流问题
转换的关键在于引入一个“费用”系数。我们为每条边 e 赋予一个单位流量费用 w(e)。为了简单且不影响最大流值，我们可以为所有边设置相同的、微小的正费用，例如 w(e) = 1 对每条边 e。这可以理解为“每单位流量产生1个单位的成本”。
现在，我们定义一个新的问题：在满足与最大流问题完全相同的容量和流量守恒约束下，寻找一个从s到t的可行流，使得总流量 F 达到一个给定的目标值 D，并且总费用 ∑_{e∈E} w(e) * f(e) 最小化。 当我们逐步增加 D 时，能实现的最小费用会逐渐增加，直到 D 达到最大流值 F_max。超过 F_max 后，问题无可行解。
但在实际算法中，我们通常不直接指定 D，而是采用一种等价形式：在原有约束下，最大化一个目标：F - ε * ∑_{e∈E} f(e)，其中 ε 是一个非常小的正数（例如 0.001）。这个目标可以理解为“在最大化总流量 F 的前提下，其次最小化总流量 ∑f(e)”。由于 ε 很小，优化过程会优先最大化 F，只有在 F 值相同的方案中，才会选择 ∑f(e) 更小的那个（这通常意味着更“直接”的路径，但我们的核心是得到 F_max）。实际上，对于这个目标，最优解中的 F 必然是 F_max。
我们可以将上述目标重写为：Minimize ε * ∑{e∈E} f(e) - F，这看起来像一个最小费用流的目标函数，但有一个自由变量 F。一个更标准的转换是：引入一条虚拟的、从s到t的、容量为无穷大、单位费用为 -M 的边，其中 M 是一个非常大的正数。此时，最大化从s到t的净流量等价于最小化“总费用” = ∑{e∈E} 1f(e) - M f_虚拟，通过使虚拟边承担尽可能多的流量来最大化总流。这种方法在教学中常用，但对于手算，我们采用前一种“最大化 F - ε∑f(e)”的解释更直观。
为了本示例，我们设定目标为：Minimize ∑_{e∈E} f(e)，约束条件为：满足流量守恒，且从s到t的总流量 F 是一个需要最大化的量。这等价于一个两阶段过程：1) 先找到 F_max。2) 在 F = F_max 的所有可行流中，找一个使得 ∑f(e) 最小的流。而第一阶段可以通过求解一个“费用”均为0的最小费用流来得到（即普通最大流）。但我们的目的是用一个统一的模型。
一个更优雅的线性规划转换是：
决策变量：与原最大流相同，f(e) 表示边e上的流量，F 表示总流量。
目标函数：Minimize ∑_{e∈E} f(e) （注意，这里我们最小化总流量，似乎与最大流矛盾）
约束条件：包含原最大流的所有约束，再加上一个额外的约束：F ≥ F_max。但 F_max 未知。
这行不通，因为我们不知道 F_max。实际上，我们可以求解以下参数线性规划：
目标：Minimize ∑_{e∈E} f(e)
约束：原最大流的所有约束，以及 F = λ （λ 是一个参数）。
然后，我们找到最大的 λ 使得该问题有可行解。这个最大的 λ 就是 F_max，对应的解就是最大流。
但在标准的最小费用流框架中，我们通过设置两层的目标函数来规避这个问题。一种实现方式是：
- 在每条边上设置单位费用 w(e) = 1。
- 在源点s，我们固定一个供给量 B（即要从s发出的流量）。
- 在汇点t，我们固定一个需求量 -B（即要接收的流量）。
- 其他顶点需求为0。
- 目标是找到满足这些节点供需平衡和容量约束的流，使得总费用 ∑w(e)f(e) 最小。这是一个标准的最小费用流问题。
现在，关键点来了：如果我们逐步增加供给/需求量 B，从0开始递增，求解每一个 B 对应的最小费用流。当 B 较小时，问题总是可行的。当 B 增加到某个临界值 B* 时，问题变得不可行。那么，最大的可行 B 就是最大流值 F_max。而且，当 B = F_max 时，我们得到的最小费用流就是一个最大流。在递增 B 的过程中，我们可以利用最小费用流算法（如容量缩放算法、连续最短路径增广算法）的特性，这些算法通常从零流开始，逐步增加流量直到达到指定需求量，并在这个过程中保持费用最小。因此，我们可以运行一次从0开始，以最大可能增加流量为目标的最小费用流算法，实际上这就是最小费用流算法用于计算最大流的一种视角：当所有边费用相同时，算法会优先寻找最短的（跳数最少的）增广路径来增加流量，这有助于快速达到最大流，但最终的总流量 F 一定是最大的。
第三步：为示例图构建最小费用流问题模型
我们采用统一单位费用 w(e)=1 的模型。
- 节点净需求：
b(s) = B (供给)
b(t) = -B (需求)
b(a) = 0
b(b) = 0 - 目标：Minimize f(sa) + f(sb) + f(ab) + f(at) + f(bt)
- 约束（除目标外，与最大流模型完全相同）：
f(sa) ≤ 3
f(sb) ≤ 2
f(ab) ≤ 2
f(at) ≤ 2
f(bt) ≤ 3
f(sa) = f(ab) + f(at) （顶点a守恒）
f(sb) + f(ab) = f(bt) （顶点b守恒）
f(sa) + f(sb) = B （源点s流出等于供给B）
f(at) + f(bt) = B （汇点t流入等于需求B）
所有 f(e) ≥ 0
注意，B 不是一个变量，而是一个参数。我们需要找到最大的 B 使得上述问题有可行解。
第四步：手动求解与推理
我们先求解原始的最大流，以得知 F_max，然后验证当 B=F_max 时，最小费用流问题可行，且目标函数值（总流量）是某个数。
首先，用常规方法（如Ford-Fulkerson）找最大流：
- 找到路径 s -> a -> t，可增广流量 min(3,2)=2。更新后：f(sa)=2, f(at)=2，边a->t饱和。
- 找到路径 s -> a -> b -> t，注意f(sa)还剩1容量，a->b容量2，b->t容量3。可增广流量 min(1,2,3)=1。更新：f(sa)=3（饱和），f(ab)=1, f(bt)=1。
- 找到路径 s -> b -> t，f(sb)容量2，b->t还剩2容量。可增广流量 min(2,2)=2。更新：f(sb)=2（饱和），f(bt)=3（饱和）。
此时，从s出发的边 s->a 和 s->b 都已饱和，无法再找到从s到t的增广路径。总流量 F = f(sa)+f(sb) = 3+2 = 5。验证流量守恒：
顶点a: 流入=3，流出=f(ab)+f(at)=1+2=3。
顶点b: 流入=f(sb)+f(ab)=2+1=3，流出=f(bt)=3。
因此，最大流 F_max = 5。
一个具体的流分配方案是：
f(sa)=3, f(sb)=2, f(ab)=1, f(at)=2, f(bt)=3。
在这个方案下，总流量 ∑f(e) = 3+2+1+2+3 = 11。
第五步：将 B=5 代入最小费用流模型验证
代入 B=5，检查模型是否可行。显然，上述最大流方案满足所有约束，因此可行。目标函数值 ∑f(e)=11。是否存在另一个总流量（即目标值）更小的、流量也为5的可行流？我们需要最小化 ∑f(e) 在 F=5 的条件下。这等价于在满足最大流的前提下，寻找一个流，使得流经的边的总流量最小。由于总流出 F=5 是固定的，∑f(e) 衡量了“流在内部边上的冗余”。实际上，因为流量守恒，有：
∑{e∈E} f(e) = (从s流出的边流量和) + (其他边流量和) = B + ∑{e not incident to s} f(e)。在 B 固定时，最小化 ∑f(e) 等价于最小化非源点射出边的流量和。在我们的图中，非源点射出边是 a->b, a->t, b->t。由于流量守恒，内部流是必然存在的。但我们可以尝试调整。
我们尝试寻找另一个 F=5 的流，看 ∑f(e) 能否小于11。
- 设变量 f(sa), f(sb), f(ab), f(at), f(bt)。
- 约束：
f(sa) ≤ 3, f(sb) ≤ 2, f(ab) ≤ 2, f(at) ≤ 2, f(bt) ≤ 3.
f(sa) = f(ab) + f(at) --> (1)
f(sb) + f(ab) = f(bt) --> (2)
f(sa) + f(sb) = 5 --> (3)
f(at) + f(bt) = 5 --> (4) - 从(1)和(4)消去 f(at): f(at)=f(sa)-f(ab)，代入(4): (f(sa)-f(ab)) + f(bt) = 5 => f(bt) = 5 - f(sa) + f(ab)。结合(2): f(sb)+f(ab)=5-f(sa)+f(ab) => f(sb) = 5 - f(sa)。这与(3)一致。所以(3)是多余的。
- 我们使用(3) f(sb)=5-f(sa)。然后 f(bt) 由(2)得: f(bt)=f(sb)+f(ab)=5-f(sa)+f(ab)。还需要满足容量约束：
f(sa) ≤ 3
f(sb)=5-f(sa) ≤ 2 => f(sa) ≥ 3
=> 所以 f(sa) 必须等于 3，则 f(sb)=2。
由 f(sa)=3，且 f(sa)=f(ab)+f(at)，所以 f(ab)+f(at)=3。
f(bt)=5-f(sa)+f(ab)=5-3+f(ab)=2+f(ab) ≤ 3 => f(ab) ≤ 1。
f(at) ≤ 2, f(ab) ≤ 2。
另外，f(ab)+f(at)=3。 - 在 f(ab)+f(at)=3 的条件下，∑f(e) = f(sa)+f(sb)+f(ab)+f(at)+f(bt) = 3+2+f(ab)+f(at)+(2+f(ab)) = 7 + (f(ab)+f(at)) + f(ab) = 7+3+f(ab) = 10+f(ab)。
要最小化 ∑f(e)，就要最小化 f(ab)。同时满足 f(ab) ≤ 1, f(ab) ≤ 2, 且 f(at)=3-f(ab) ≤ 2 => f(ab) ≥ 1。
所以 f(ab) 最小值为1。此时 ∑f(e)=10+1=11。若 f(ab)=0，则 f(at)=3>2 违反容量。因此，我们找到的流（f(ab)=1）就是使 ∑f(e) 最小的最大流。最小费用流问题的目标函数最优值就是11。
第六步：解释算法的实际运作
在实际的算法实现中（如连续最短路径增广算法用于最小费用流），当所有边费用均为1时，算法会寻找最短的（即边数最少的）s-t路径进行增广，以最小化总费用。这类似于Edmonds-Karp算法（后者是每次找最短的增广路径，以边数计）。对于本例：
- 初始流为0。
- 找到最短路径 s->a->t（长度2）。可增广流量2。更新后流：f(sa)=2, f(at)=2。
- 剩余网络中，最短路径可能是 s->b->t（长度2）或 s->a->b->t（长度3）。算法会选择 s->b->t，增广流量2。更新：f(sb)=2, f(bt)=2。
- 此时，从s出发，还有s->a有剩余容量1，但a->t已满。从a可到b（容量2），b->t剩余容量1。路径 s->a->b->t 存在，长度3，增广流量 min(1,2,1)=1。更新：f(sa)=3, f(ab)=1, f(bt)=3。
算法停止，因为无法再找到s到t的路径。总流量=2+2+1=5，即为最大流。总费用（目标函数）=2+2+2+2+1+3? 让我们计算最终每条边流量：f(sa)=3, f(sb)=2, f(ab)=1, f(at)=2, f(bt)=3，总费用=3+2+1+2+3=11。这正是我们得到的最小总流量的最大流。
3. 总结
通过将最大流问题转化为一个所有边单位费用为1的最小费用流问题，我们可以利用最小费用流算法（如连续最短路径增广算法）来求解最大流。在这种设置下，算法倾向于优先通过最短路径发送流量，这有助于快速达到最大流，并且最终得到的总流量（目标函数）是所有最大流方案中“总流量”最小（或理解为内部流量最简洁）的一个。这种方法在概念上统一了最大流和最小费用流，并在某些情况下可以利用更高效的算法实现。在本例中，我们通过手动推导验证了当参数B（供需量）等于最大流值5时，问题可行，且最小总流量为11，并通过模拟算法步骤展示了求解过程。