3

我正在尝试设计一种算法,该算法将模拟具有多个源和特定容量的多个汇的管道网络。

到目前为止,我已经尝试使用经典的 Ford-Fulkerson 算法,但我遇到的问题是这样的,给出下图:

    S
    |
    a
   / \
  B   C

给定S的源容量为 1,B 和 C的汇容量为 1 - a 流将导致 S - a - B,使 B 饱和为 1,而 C 流为 0。

我正在尝试在网络上均匀分配流量,以便B 和 C 都收到 0.5。有任何想法吗?

谢谢!

4

2 回答 2

1

假设您有n 个s 1 , ..., s n,源容量为c imt 1 , ..., t m。让f = sum i c i。我们想在网络中找到一个可行的流,其中每个源i的净流量为-c i,每个汇的净流量为f / m

我们可以通过引入一个超级源S和一个超级汇T并通过容量为c i的边 ( s i , S)将每个源i连接到S来解决这个问题。我们通过容量f / m的边缘将每个t i连接到 T 。然后我们只需使用源 S 和接收器 T 运行 max-flow。

如果无法将f / m单位的流量精确推送到每个接收器,则不清楚您要优化什么,但您可能会发现以下两种方法很有用:

  • 选择e并通过容量为f / m + e的边将汇连接到T。使用二分搜索找到最小的e使得总流量为f。这最小化了最大i流入量(t i
  • 选择e并通过具有下界 e的边将汇添加到T。使用二分搜索找到仍然允许可行流的最大e 。这使min i inflow(t i )最大化。下界的可行流问题可以简化为最大流:http ://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf在这种情况下,构造确实是简单:只需添加一个额外的超级源 S' 并通过容量为m * e的边缘将 S' 连接到S。通过容量为e的边将所有汇点连接到T。检查 S' 和 T 之间的最大流量是否为m * e
于 2014-03-21T21:47:16.943 回答
0

我是一名水网工程师。当我对供水网络进行建模时,我通常将源作为压力节点,将汇作为需求节点,因为水模拟软件可以求解水头或节点处的流量。而且我知道源头泵的能力和客户的消耗量。管道中的流量通过 Hazen-Williams 或 Darcy-Weisbach 等水头损失流量方程求解。

在您的示例中,接收器的需求比源所能提供的更多,所有这些都是在流量方面。B 和 C 的顾客都会尽量打开他们的水龙头,以满足他们 1 单位的需求;但是假设从 a 到 B 的管道路径与从 a 到 C 的管道路径相同,那么在 B 和 C 都尽力使流向各自末端的流量最大化之后,1 个单位的流量将平均分配。

但由于不满足 2 台总需求的约束,仿真软件无法解决。要么将源更改为压力节点,这将给出发送 2 个单位的水所需的压力,或者应降低客户需求以匹配源能力。在后一种情况下,目的是模拟从源到汇的水力坡度线。

于 2018-08-09T03:09:58.477 回答