我正在尝试设计一种算法,该算法将模拟具有多个源和特定容量的多个汇的管道网络。
到目前为止,我已经尝试使用经典的 Ford-Fulkerson 算法,但我遇到的问题是这样的,给出下图:
S
|
a
/ \
B C
给定S的源容量为 1,B 和 C的汇容量为 1 - a 流将导致 S - a - B,使 B 饱和为 1,而 C 流为 0。
我正在尝试在网络上均匀分配流量,以便B 和 C 都收到 0.5。有任何想法吗?
谢谢!
我正在尝试设计一种算法,该算法将模拟具有多个源和特定容量的多个汇的管道网络。
到目前为止,我已经尝试使用经典的 Ford-Fulkerson 算法,但我遇到的问题是这样的,给出下图:
S
|
a
/ \
B C
给定S的源容量为 1,B 和 C的汇容量为 1 - a 流将导致 S - a - B,使 B 饱和为 1,而 C 流为 0。
我正在尝试在网络上均匀分配流量,以便B 和 C 都收到 0.5。有任何想法吗?
谢谢!
假设您有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单位的流量精确推送到每个接收器,则不清楚您要优化什么,但您可能会发现以下两种方法很有用:
我是一名水网工程师。当我对供水网络进行建模时,我通常将源作为压力节点,将汇作为需求节点,因为水模拟软件可以求解水头或节点处的流量。而且我知道源头泵的能力和客户的消耗量。管道中的流量通过 Hazen-Williams 或 Darcy-Weisbach 等水头损失流量方程求解。
在您的示例中,接收器的需求比源所能提供的更多,所有这些都是在流量方面。B 和 C 的顾客都会尽量打开他们的水龙头,以满足他们 1 单位的需求;但是假设从 a 到 B 的管道路径与从 a 到 C 的管道路径相同,那么在 B 和 C 都尽力使流向各自末端的流量最大化之后,1 个单位的流量将平均分配。
但由于不满足 2 台总需求的约束,仿真软件无法解决。要么将源更改为压力节点,这将给出发送 2 个单位的水所需的压力,或者应降低客户需求以匹配源能力。在后一种情况下,目的是模拟从源到汇的水力坡度线。