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 i和m汇t 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 回答