我正在尝试设计一种算法，该算法将模拟具有多个源和具有特定容量的多个接收器的管道网络 .
到目前为止，我已尝试使用经典的Ford-Fulkerson算法，但我遇到的问题是这个，给出如下图：
S | a / \ B C
给定 S ，源容量为1，并且 B and C 的接收容量为1 - 流将产生S-a-B，将B饱和为1并使C流为0 .
我正试图在整个网络中统一分配流量，以便 B and C receive 0.5 . 有任何想法吗？
谢谢！
假设您有n个源s1，...，sn，源容量ci和m汇t1，...，tm . 设f = sumi ci . 我们希望在网络中找到一个可行的流，其中每个源i的净流量为-ci，每个接收器的净流量为f / m .
我们可以通过引入超级源S和超级宿T并通过容量ci的边（si，S）将每个源i连接到S来解决这个问题 . 我们通过容量f / m的边缘将每个ti连接到T.然后我们只用源S和接收器T运行max-flow .
如果无法将精确的f / m流量单位推送到每个接收器，则不清楚要优化的是什么，但您可能会发现以下两种方法非常有用：
选择e并通过容量为f / m e的边缘将接收器连接到T.使用二进制搜索找到最小e，使总流量为f . 这最大限度地减少了最大流入量（ti）
选择e并通过下边界e的边缘将水槽添加到T.使用二进制搜索来查找仍然允许可行流的最大e . 这最大化了迷你流入（ti） . 具有下限的可行流问题可以减少到最大流量：http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf在这种情况下，构造非常简单：只需通过容量m * e的边缘向S添加额外的超级源S ' and connect S' . 通过容量e的边缘将所有接收器连接到T.检查S'和T之间的最大流量是否为m * e
我是一名水网工程师 . 当我对供水网络进行建模时，我通常将源作为压力节点和下沉作为需求节点，因为水模拟软件可以解决节点的头部或流量问题 . 我知道泵在源头的能力和客户的消耗 . 管道中的流动通过诸如Hazen-Williams或Darcy-Weisbach的水流损失方程来解决 .
在您的示例中，接收器需要的数量超过源可以提供的数量，所有这些都在流量方面 . B和C的客户都会尝试尽可能大地打开他们的水龙头，以满足他们的1个单位的需求;但是假设从a到B的管道路径从a到C是相同的，在B和C都尽力使流到各自的末端之后，1个流量单位将均匀分配 .
但由于不满足2个单位总需求的约束，仿真软件无法解决 . 要么将源更改为压力节点，这将提供输出2单位水所需的压力，或者应减少客户需求以匹配源功能 . 在后一种情况下，目的是模拟从源到水槽的液压等级线 .
2 回答
假设您有n个源s1，...，sn，源容量ci和m汇t1，...，tm . 设f = sumi ci . 我们希望在网络中找到一个可行的流，其中每个源i的净流量为-ci，每个接收器的净流量为f / m .
我们可以通过引入超级源S和超级宿T并通过容量ci的边（si，S）将每个源i连接到S来解决这个问题 . 我们通过容量f / m的边缘将每个ti连接到T.然后我们只用源S和接收器T运行max-flow .
如果无法将精确的f / m流量单位推送到每个接收器，则不清楚要优化的是什么，但您可能会发现以下两种方法非常有用：
选择e并通过容量为f / m e的边缘将接收器连接到T.使用二进制搜索找到最小e，使总流量为f . 这最大限度地减少了最大流入量（ti）
选择e并通过下边界e的边缘将水槽添加到T.使用二进制搜索来查找仍然允许可行流的最大e . 这最大化了迷你流入（ti） . 具有下限的可行流问题可以减少到最大流量：http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf在这种情况下，构造非常简单：只需通过容量m * e的边缘向S添加额外的超级源S ' and connect S' . 通过容量e的边缘将所有接收器连接到T.检查S'和T之间的最大流量是否为m * e
我是一名水网工程师 . 当我对供水网络进行建模时，我通常将源作为压力节点和下沉作为需求节点，因为水模拟软件可以解决节点的头部或流量问题 . 我知道泵在源头的能力和客户的消耗 . 管道中的流动通过诸如Hazen-Williams或Darcy-Weisbach的水流损失方程来解决 .
在您的示例中，接收器需要的数量超过源可以提供的数量，所有这些都在流量方面 . B和C的客户都会尝试尽可能大地打开他们的水龙头，以满足他们的1个单位的需求;但是假设从a到B的管道路径从a到C是相同的，在B和C都尽力使流到各自的末端之后，1个流量单位将均匀分配 .
但由于不满足2个单位总需求的约束，仿真软件无法解决 . 要么将源更改为压力节点，这将提供输出2单位水所需的压力，或者应减少客户需求以匹配源功能 . 在后一种情况下，目的是模拟从源到水槽的液压等级线 .