algorithm - 如何使用网络流解决线性规划？

Question

假设我们有 m 个考试 E={E1,E2,...,Em} 和一组 I={I1,I2,...,In} 的工具，并且每个考试 Ej 需要 I 的 Rj 的一个子集。每次检查都有 Pj $ 利润，每个仪器成本 Cj $。我们想选择一些检查来最大化（利润总和 - 成本总和）。

我认为我们可以使用 LP，这样我们每次检查都有 m 个变量 Xi 并且 Xi = 0 或 1，我们的目标函数是：对于所有 i 和 j Xi(Pi) - (A)Cj 其中 A 是 xor 所有需要的 Xi Ij

但我不能通过网络流来模拟这个问题。我的问题是如何表达这样一个事实，即当我们选择考试并为其仪器付费时，我们可以将这些仪器用于其他考试。

Answer 1

将问题建模为二分图：将检查作为顶点放在左侧，将仪器放在右侧。通过无限容量的边缘将检查连接到他们的仪器。现在引入源 S 和汇 T。通过代表利润的边将 S 连接到检查。通过代表其成本的边将仪器连接到 T。

最大利润是所有 Pi-min cut 的总和。

为什么？考虑在图中切割边以将 T 与 S 分开。对于每次检查，我们需要切割检查本身，“支付”我们错过的利润，或切割所有工具。

一组最佳检查由剩余流网络中从 S 可达的检查顶点集表示。