最小成本最大流问题的网络单纯形算法 题目描述 我们有一个有向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 有三个属性：容量 \(u(e) \ge 0\)，单位流量成本 \(c(e)\)（可为负数），以及当前流量 \(f(e)\)（初始通常为0）。 目标是找到一个 最大流 ，使得在满足容量限制和流量守恒的前提下， 总成本 \(\sum_ {e \in E} c(e) f(e)\) 最小。 这就是 最小成本最大流问题 。网络单纯形算法是求解该问题的一种高效算法，它借鉴了线性规划中的单纯形法，但利用图的结构进行优化，通常比一般的线性规划单纯形法快得多。 解题过程循序渐进讲解 1. 问题形式化为线性规划 首先，我们将问题写成线性规划形式： 变量：\(f(e)\) 表示边 \(e\) 上的流量。 目标：最小化 \(\sum_ {e} c(e) f(e)\)。 约束： 容量限制：\(0 \le f(e) \le u(e)\)。 流量守恒：对于每个顶点 \(v\)，进入 \(v\) 的流量总和等于离开 \(v\) 的流量总和，除非 \(v\) 是源点 \(s\)（净流出）或汇点 \(t\)（净流入）。 设源点 \(s\) 的净流出量为 \(F\)（即流量值），汇点 \(t\) 的净流入量为 \(F\)，其余顶点净流量为0。 在最大流问题中，\(F\) 应尽可能大，但这里我们先固定一个可行流，然后通过迭代增加流量并保持成本最小，直到无法增广。 2. 网络单纯形法的核心思想 单纯形法在线性规划中从一个“基可行解”迭代到另一个，每次沿着一个方向改进目标函数。 在图论中，一个 基解 对应一个 生成树结构 （实际上是“生成树”加上一个“根”的概念，但这里我们先简化理解）。 关键观察：对于一个有 \(n\) 个顶点的图，在流量守恒约束下，线性独立的约束个数是 \(n-1\)（因为所有顶点的流量守恒方程之和是冗余的）。 因此，一个基解对应选择 \(n-1\) 条边，这些边组成一棵 生成树 （实际上，如果考虑反向边等，它是“支撑树”结构，但先理解为生成树）。 基变量对应这 \(n-1\) 条树边上的流量，非基变量对应非树边上的流量。 非基变量要么取0（下界），要么取容量上限（上界）。 每次迭代，我们尝试将一条非基边加入基（即改变它的流量），同时踢出一条基边，以改进成本。 3. 准备工作：残量图与势 我们引入“势”函数 \(\pi: V \to \mathbb{R}\)。 对于每条边 \(e = (i, j)\)，定义其 缩减成本 为： \[ \bar{c}(e) = c(e) + \pi(i) - \pi(j) \] 如果存在势函数使得所有边的缩减成本非负，且满足某些互补松弛条件，则当前流是最小成本流。 网络单纯形法通过维护一棵生成树（基）和对应的势，使得 所有树边的缩减成本为0 ，非树边的缩减成本可能为正或负。 4. 算法步骤 假设我们已经有一个初始可行流（例如零流）和一个初始生成树基（如何得到初始基是一个技术点，常用“人工变量”法，但这里我们暂假设已有一个可行基解）。 迭代过程如下： (1) 计算势 在当前的生成树 \(T\) 上，我们固定根节点 \(r\) 的势 \(\pi(r) = 0\)，然后通过树边递推： 对树边 \(e = (i, j) \in T\)，如果它是正向边（在树中方向从父到子），则要求 \(\bar{c}(e) = 0\)，即： \[ c(e) + \pi(i) - \pi(j) = 0 \quad \Rightarrow \quad \pi(j) = \pi(i) + c(e) \] 如果它是反向边（在树中方向从子到父），则也要求 \(\bar{c}(e) = 0\)，但注意反向边的成本是原边成本的相反数（因为流量可反向），所以也能算出势。 这样我们可以唯一确定所有顶点的势。 (2) 检查最优性 计算所有非树边 \(e = (i, j)\) 的缩减成本 \(\bar{c}(e) = c(e) + \pi(i) - \pi(j)\)。 如果对于所有非树边： 如果当前流量 \(f(e) = 0\)（取下界），则检查 \(\bar{c}(e) \ge 0\)。 如果当前流量 \(f(e) = u(e)\)（取上界），则检查 \(\bar{c}(e) \le 0\)。 如果这些条件全部满足，则当前流是最小成本流（对应当前流量值）。 否则，存在一条非树边违反条件，它可以改进目标函数。 (3) 选择入基边 找到一条违反条件的非树边 \(e\)： 如果 \(f(e) = 0\) 且 \(\bar{c}(e) < 0\)，则增加这条边上的流量可降低成本。 如果 \(f(e) = u(e)\) 且 \(\bar{c}(e) > 0\)，则减少这条边上的流量（即增加反向流量）可降低成本。 我们选择这条边作为“入基边”。 (4) 在树中形成环并调整流量 将入基边加入生成树 \(T\)，会形成一个唯一的环（称为“基本环”）。 根据入基边的类型决定沿环增加还是减少流量： 如果入基边当前流量为0，我们想增加它的流量，则沿环的方向与入基边同向的边上增加流量，反向边上减少流量。 如果入基边当前流量为上限，我们想减少它的流量，则沿环的方向与入基边反向的边上增加流量。 调整的量 \(\delta\) 是有限的：要保证所有边上调整后流量仍在 \([ 0, u(e) ]\) 范围内。 \(\delta\) 由环上“瓶颈”容量决定。 (5) 选择出基边 环上某条边在调整 \(\delta\) 后会达到其上界或下界（即不能再调），我们选择这条边作为“出基边”，将它从生成树中移除。 这样生成树恢复为 \(n-1\) 条边，得到新的基。 (6) 更新势 因为树结构改变，我们需要重新计算势，使其满足树边缩减成本为0。 高效的做法是：出基边将树分成两个子树，我们只需要更新其中一个子树的势值（加上或减去一个常数）。 常数由入基边的缩减成本决定，这样能保持树边缩减成本为0的性质。 (7) 重复 回到步骤(2)，直到没有违反条件的非树边，则当前流是当前流量下的最小成本流。 如果此时流量尚未达到最大，我们需要增加流量：这可以通过添加一条从源到汇的路径，并保证增加流量后仍保持最优性（这涉及到“流量增广”与“势”的调整，实践中网络单纯形法常与“最短路增广”结合，但纯粹的网络单纯形也可通过引入“人工边”来增加流量）。 5. 初始可行基的构造 一个常用技巧是添加“人工边”：从每个顶点到汇点或从源点添加零成本、大容量的边，形成一个初始生成树。然后通过调整使这些人工边的流量归零，从而得到原问题的可行基。 6. 算法复杂度与注意事项 网络单纯形法在实践中非常快，尽管最坏情况是指数时间，但对于大多数实际问题效率很高。 关键优化包括： 使用“强可行基”规则避免循环。 高效的数据结构（动态树）维护生成树和势的更新。 聪明的入基边选择策略（如最负缩减成本边）。 总结 网络单纯形法将最小成本最大流问题转化为在生成树基上的迭代优化。通过维护势函数和缩减成本，利用图的结构快速判断最优性、选择改进边、调整流量和基。这个算法是线性规划单纯形法在图问题中的特化，兼具理论美感与实用高效性。