最佳流量分配
Optimal Flow Distribution
我搜索了 Whosebug 和 google，但我没有找到遇到相同类型问题的人。
Optimal distribution of power plants on a city 似乎是这个问题最接近的解决方案，但我相信我的问题比那里的问题更简单，因此会有比暴力破解更好的解决方案。
问题是这样的：
我有 9 个城市，每个城市都生产电力和使用电力。每个城市都与其他 8 个城市相连。如何确定以最少的能量传输量向需要的城市输送多余电力的最佳方式？
我尝试使用多个源和接收器解决网络流的这个问题，但它确实工作正常。
谢谢！
看看this article。这就是您可以将问题减少到最小成本最大流量的方法。
对于每个城市，将需求 d 计算为 usage - production。按 d=0、d<0 和 d>0 对城市进行分组。让所有的连接都有无限的能力。然后添加两个新节点，sink 和 source。在源节点和 d<0 节点之间添加边，容量为 |d|。在 d>0 和 sink 节点之间添加边，容量为 d。现在你有了单源单汇网络，你可以应用任何最小成本最大流算法来找到解决方案。
这是一个标准的配电网优化问题。定义 2 组决策变量
Xi ：第 i 个城市产生的电力，
Yij : 第 i 个城市消耗的电量，其中 j 是供电城市
定义将电力从一个城市传输到另一个城市的传输成本
Objective : min ∑ Cij * Yij 对于所有 i,j
约束：
需求约束：Xi + ∑Yij（对于所有 js）<= 城市 i 的总功率需求
同样供应限制
希望这有效
我搜索了 Whosebug 和 google，但我没有找到遇到相同类型问题的人。
Optimal distribution of power plants on a city 似乎是这个问题最接近的解决方案，但我相信我的问题比那里的问题更简单，因此会有比暴力破解更好的解决方案。
问题是这样的： 我有 9 个城市，每个城市都生产电力和使用电力。每个城市都与其他 8 个城市相连。如何确定以最少的能量传输量向需要的城市输送多余电力的最佳方式？
我尝试使用多个源和接收器解决网络流的这个问题，但它确实工作正常。
谢谢！
看看this article。这就是您可以将问题减少到最小成本最大流量的方法。
对于每个城市，将需求 d 计算为 usage - production。按 d=0、d<0 和 d>0 对城市进行分组。让所有的连接都有无限的能力。然后添加两个新节点，sink 和 source。在源节点和 d<0 节点之间添加边，容量为 |d|。在 d>0 和 sink 节点之间添加边，容量为 d。现在你有了单源单汇网络，你可以应用任何最小成本最大流算法来找到解决方案。
这是一个标准的配电网优化问题。定义 2 组决策变量 Xi ：第 i 个城市产生的电力， Yij : 第 i 个城市消耗的电量，其中 j 是供电城市
定义将电力从一个城市传输到另一个城市的传输成本
Objective : min ∑ Cij * Yij 对于所有 i,j
约束： 需求约束：Xi + ∑Yij（对于所有 js）<= 城市 i 的总功率需求 同样供应限制
希望这有效