基于线性规划的图最大流问题最小费用流转换求解示例 一、问题描述 在图论和组合优化中， 最大流问题 （Maximum Flow Problem）的目标是在一个有向图中，从给定的源点 \( s \) 向汇点 \( t \) 输送尽可能多的流量，同时满足每条边上的容量限制。如果每条边还附有一个单位流量的输送成本，那么 最小费用最大流问题 （Minimum Cost Maximum Flow Problem）则要求在达到最大流量的同时，使得总输送成本最小。 本示例将展示 如何将最大流问题转化为一个特殊的最小费用流问题 ，并通过求解该最小费用流问题来得到最大流。这是一种巧妙的建模技巧，其核心思想是：在原图的所有边上 人为设定一个统一的单位费用（例如零） ，并增加一条从汇点 \( t \) 到源点 \( s \) 的 虚拟回流边 ，该边容量为无穷大，但赋予一个 负的单位费用 。通过求解这个新图上的最小费用流问题，可以迫使算法寻找最大流，因为只有尽可能多地利用负费用回流边（即输送更多流量从 \( s \) 到 \( t \)），才能降低总成本。 二、构建转化模型 我们给定一个有向图 \( G = (V, E) \)，其中： \( V \) 是顶点集合，包含源点 \( s \) 和汇点 \( t \)。 每条边 \( (u, v) \in E \) 有容量 \( c(u, v) \geq 0 \)。 目标 ：求从 \( s \) 到 \( t \) 的最大流量值 \( F_ {\max} \)。 转化步骤 ： 保持原图结构 ：保留所有原边 \( (u, v) \in E \)，容量仍为 \( c(u, v) \)。 设置边费用 ：为所有原边赋予 单位费用 \( \text{cost}(u, v) = 0 \) 。 添加虚拟回流边 ：增加一条从汇点 \( t \) 到源点 \( s \) 的边 \( (t, s) \)。 容量 \( c(t, s) = +\infty \)（理论上是足够大的数，实践中可用一个大于等于可能最大流的值代替）。 单位费用 \( \text{cost}(t, s) = -1 \)（或其他任意负数）。 定义新问题 ：在转化后的图上，寻找一个 循环流 （Circulation），使得总费用最小。由于存在负费用边 \( (t, s) \)，最小费用流会尝试尽可能多地让流量通过该边，而流量要经过 \( (t, s) \)，必须先从 \( s \) 经过原图到达 \( t \)，因此流过 \( (t, s) \) 的流量值就等于从 \( s \) 到 \( t \) 的流量。最小化总费用即最大化此流量（因为负费用边流量越大，总费用越低）。 三、线性规划建模 设决策变量 \( f(u, v) \) 表示边 \( (u, v) \) 上的流量。 转化后的最小费用流问题的线性规划模型 ： \[ \begin{aligned} \min \quad & \sum_ {(u, v) \in E} 0 \cdot f(u, v) + (-1) \cdot f(t, s) \\ \text{s.t.} \quad & \sum_ {v: (u, v) \in E'} f(u, v) - \sum_ {v: (v, u) \in E'} f(v, u) = 0, \quad \forall u \in V \quad (\text{流量守恒}) \\ & 0 \leq f(u, v) \leq c(u, v), \quad \forall (u, v) \in E \\ & 0 \leq f(t, s) \leq M \quad (M \text{是一个足够大的数}) \end{aligned} \] 其中 \( E' = E \cup \{(t, s)\} \)，流量守恒约束确保每个顶点的流入等于流出（包括虚拟边）。 关键观察 ： 目标函数简化为 \( \min \, (-f(t, s)) \)，等价于 \( \max \, f(t, s) \)。 由流量守恒，\( f(t, s) \) 的值正是从 \( s \) 到 \( t \) 的净流量。 因此，求解该线性规划即得到原图的最大流 \( F_ {\max} = f(t, s)^* \)，且最优解中原图边上的流量 \( f(u, v)^* \) 构成了一个最大流方案。 四、求解过程示例 考虑一个简单有向图： 顶点：\( V = \{s, a, b, t\} \) 边及容量：\( (s, a): 3, (s, b): 2, (a, b): 1, (a, t): 2, (b, t): 3 \) 目标：求 \( s \to t \) 的最大流。 步骤1：构建转化图 保留所有原边，单位费用设为0。 添加虚拟边 \( (t, s) \)，容量 \( M = 10 \)（足够大），单位费用 \( -1 \)。 步骤2：建立线性规划模型 变量：\( f_ {sa}, f_ {sb}, f_ {ab}, f_ {at}, f_ {bt}, f_ {ts} \) 分别对应各边流量。 目标函数： \[ \min \, (-f_ {ts}) \] 约束： 流量守恒 （每个顶点流入 = 流出）： \( s \)：\( f_ {ts} + f_ {sa} + f_ {sb} = 0 \) （注意：虚拟边 \( f_ {ts} \) 流入 \( s \)） \( a \)：\( f_ {sa} = f_ {ab} + f_ {at} \) \( b \)：\( f_ {sb} + f_ {ab} = f_ {bt} \) \( t \)：\( f_ {at} + f_ {bt} = f_ {ts} \) 容量限制 ： \( 0 \leq f_ {sa} \leq 3, \quad 0 \leq f_ {sb} \leq 2, \quad 0 \leq f_ {ab} \leq 1 \) \( 0 \leq f_ {at} \leq 2, \quad 0 \leq f_ {bt} \leq 3, \quad 0 \leq f_ {ts} \leq 10 \) 步骤3：求解线性规划 手动推导（也可用单纯形法）： 由目标函数知，应尽可能增大 \( f_ {ts} \)。 从 \( t \) 的守恒约束：\( f_ {ts} = f_ {at} + f_ {bt} \)，因此需最大化 \( f_ {at} + f_ {bt} \)。 考虑路径与瓶颈： 路径 \( s \to a \to t \)：最大贡献 \( \min(3, 2) = 2 \)。 路径 \( s \to b \to t \)：最大贡献 \( \min(2, 3) = 2 \)。 路径 \( s \to a \to b \to t \)：经 \( a \to b \) 容量为1，可额外从 \( s \to a \) 分1单位经 \( a \to b \) 到 \( b \to t \)。 一种最优分配： \( f_ {sa} = 3, f_ {at} = 2, f_ {ab} = 1, f_ {sb} = 1, f_ {bt} = 2, f_ {ts} = 4 \)。 检查守恒： \( s \)：流入 \( f_ {ts}=4 \)，流出 \( f_ {sa}+f_ {sb}=3+1=4 \)。 \( a \)：流入 \( f_ {sa}=3 \)，流出 \( f_ {at}+f_ {ab}=2+1=3 \)。 \( b \)：流入 \( f_ {sb}+f_ {ab}=1+1=2 \)，流出 \( f_ {bt}=2 \)。 \( t \)：流入 \( f_ {at}+f_ {bt}=2+2=4 \)，流出 \( f_ {ts}=4 \)。 所有容量约束满足。 此时 \( f_ {ts} = 4 \)，目标函数值 \( -4 \)。 步骤4：解释结果 最大流值 \( F_ {\max} = f_ {ts} = 4 \)。 原图中流量分配：\( s \to a \to t \) 流2，\( s \to a \to b \to t \) 流1，\( s \to b \to t \) 流1。 虚拟边 \( (t, s) \) 流量为4，将汇点 \( t \) 收到的流量“回流”至源点 \( s \)，形成一个循环，使得目标函数最小化。 五、算法意义与扩展 统一框架 ：该转化将最大流问题纳入最小费用流算法（如网络单纯形法、成本缩放算法）的框架中求解。 实际应用 ：在某些算法库中，可通过设置边费用为0并添加负费用回流边，复用最小费用流代码求解最大流。 理论价值 ：揭示了最大流与最小费用流之间的深刻联系，即最大流等价于在一个扩展图中寻找最小费用的循环流，其中负费用边驱动流量的最大化。 注意 ：若直接使用某些最小费用流算法（如基于负环消去的算法），需确保虚拟边容量 \( M \) 足够大，否则可能限制最大流值。 通过这种巧妙的转化，最大流问题可以借助成熟的最小费用流算法高效求解，体现了线性规划建模在组合优化中的灵活性与威力。