constraints - 多商品流通

Question

我一直在为我的考试准备 DPV 教科书的问题章节做准备。对于其中一个，我遇到了一些麻烦，但我取得了一些进展：

---

---

我的解决方案：

我将使用线性规划来最大化 x 其中所有 i 的 SUM {flow_i(s_i, v) 其中 v 是连接到源 s_i} >= x * d_i 的节点

受约束

• 对于每个边 e ， f1+..fk <= c_e
• 对于每个边 e，flow_e >= 0
• 还有一些我不确定的限制

我认为我走在正确的轨道上，但我需要一些帮助才能走得更远。我是否应该考虑尝试使用超级节点将其减少为常规的最大流量问题？

任何帮助都会很棒！谢谢你。

Answer 1

是的，解决多源、多汇商品流问题的一种典型方法是引入一个超级源和一个超级汇。然后将所有源s1...sk连接到超级源。将每个接收器t1,...tk连接到超级接收器。

重要提示：为离开或进入任何超级节点的所有边提供非常大的容量。

目标：最大化总吞吐量。（离开源 1..k 的所有边上的流量总和）

约束：

边缘容量限制：

你已经做对了。

• 对于每个边 e ， f1+..fk <= c_e

*流量保护（流入 == 流出）：*

• 对于每个顶点 v，流入 v 的流量总和 = 离开 v 的流量总和

需求满足：

• 对于每个汇 t_i，流入 t_i 的总和（所有以 t_i 结尾的边）>= demand_i

您已经拥有的非零流量。

这是一份可访问的讲义，它引用了您的具体问题。具体来说，请查看讲义中的示例 2。