如何计算多源单汇流网络获取指定总量的最大稳定流率？

问题说明 #

给定一个多源单汇的流网络：每条边有最大流率（容量），每个顶点拥有初始剩余量。我们需要为汇点获取指定总量的流量，如何高效确定能达成的最大稳定（固定）流率？

这是最大流问题的变体，和标准最大流的核心区别在于：每个顶点的有限剩余量会随流量输出而消耗，耗尽后无法再产生新流量；同时，来自前驱节点的流入流量可以补充该顶点的剩余量。

示例解析 #

示例1 #

流网络结构：

• u(1)->[2]->v(0)

顶点u初始剩余量为1，v为0；边(u,v)的容量为2。若要求汇点v获取总量10的流量，最大稳定流率为0（无解）——因为u的剩余量仅能支撑最多1单位的总流量，远达不到10的要求，无法形成持续稳定的流。

示例2 #

流网络结构：

• a(8)->[2]->b(0)
• c(5)->[1]->b(0)
• d(7)->[7]->b(0)

若要求汇点b获取总量20的流量，最大稳定流率为4（由a提供1.6、c提供1、d提供1.4，总和为4）。该流可持续5秒，总流量为4×5=20，刚好满足要求。

高效求解思路 #

模型转化 #

将问题转化为带约束的优化问题，核心变量为各边的稳定流率f_e和流的持续时间t：

• 目标：最大化汇点的总流入率F = sum(f_e 其中e指向汇点)
• 约束条件：
  1. 每条边的流率不超过容量：0 ≤ f_e ≤ C_e（C_e为边e的最大流率）
  2. 对每个顶点v，总流出流量不能超过初始剩余量加总流入流量：sum(f_{in}(v))×t + R(v) ≥ sum(f_{out}(v))×t（R(v)为顶点v的初始剩余量，sum(f_{in}(v))是流入v的总流率，sum(f_{out}(v))是流出v的总流率）
  3. 汇点的总流入量满足要求：F×t ≥ Q（Q为指定的总流量需求）
  4. 持续时间t > 0

求解方法 #

1. 二分查找法

   • 二分枚举可能的总流率F，对每个F验证是否存在t>0满足所有约束：
     • 先根据各边容量分配流率，确保汇点总流入为F；
     • 对每个顶点计算t_v：若sum(f_{out}(v)) > sum(f_{in}(v))，则t_v = R(v)/(sum(f_{out}(v)) - sum(f_{in}(v)))（该顶点剩余量耗尽的时间）；若流出≤流入，t_v为无穷大；
     • 取所有t_v的最小值t_min，如果F×t_min ≥ Q，则该F可行，尝试更大值；否则尝试更小值。

2. 线性规划求解

   • 将上述约束和目标转化为标准线性规划模型，使用成熟的线性规划求解器（如单纯形法工具）直接计算最优解，适合复杂网络场景。

3. 关键节点分析法

   • 对于结构简单的网络，可直接找出限制流持续时间的关键顶点（剩余量与流出/流入差比值最小的顶点），计算其能支撑的最长时间t，再根据Q反推最大流率F = Q/t，同时验证该流率是否满足所有边的容量约束。

内容的提问来源于stack exchange，提问作者felix