1

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


DPV 7.20


我的解决方案:

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

受约束

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

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

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

4

1 回答 1

1

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

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

目标:最大化总吞吐量。(离开源 1..k 的所有边上的流量总和)

约束:

边缘容量限制:

你已经做对了。

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

*流量保护(流入 == 流出):*

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

需求满足:

  • 对于每个汇 t_i,流入 t_i 的总和(所有以 t_i 结尾的边)>= demand_i

您已经拥有的非零流量。

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

于 2013-08-01T19:14:24.377 回答