algorithm - 网络流量 : Can I change edge capacity while solving for max flow?

Question

我想知道在解决网络流问题时是否可以更改边容量。

我对商品 A、B 和 AB 存在供需问题。一个单位的 A 需求将占用一个单位的 A，B 将占用一个单位的 B，AB 将占用一个单位的 AB 或一个单位的 A 和一个单位的 B。给定每种商品的供需 list ，我想要以确定手头是否有足够的商品来满足需求。

所以我的网络看起来像这样:

令 sX 为 X 的供应。
令 dX 为 X 的需求。
所有流从左到右。

你可以看到，如果我压入 x 个单位的 A，我就会从 (A+B) 的容量中减去 x。同样，如果我“撤消”推送，我会将容量添加回 (A+B)。所以我在算法中这样做了。这会搞乱算法吗？

Answer 1

这不是网络流量问题。假设 sA = 10，sB = 10，dA = 10，dB = 10，dAB = 10。从图中可以提供 10 个 As、Bs 和 A+Bs，因此可以满足需求。但事实上，您需要 20 个 A 和 20 个 B 才能满足这种需求。

我不知道有什么方法可以让简单的流网络表示您需要一个地方的流来匹配另一个地方的流的条件。

你描述的是一个有趣的问题，我确信已经有人研究过，但我不知道你怎么调用它。

这可以通过将其转化为线性规划问题来解决。参见 http://en.wikipedia.org/wiki/Linear_programming如果您不熟悉线性规划问题。考虑你的简单情况。您可以从 6 个变量开始:

1. x 是从输入 A 到输出 A 的流。
2. y 是从输入 B 到输出 B 的流。
3. z 是从输入 AB 到输出 AB 的流。
4. w 是从A 到A + B 的流。
5. w' 是从 B 到 A + B 的流。
6. w'' 是从A + B 到AB 的流。

当然最后3个都是相等的。所以我们有 4 个变量。 (如果我们没有注意到这一点，我们会有更多的方程式。)现在添加以下不等式:

1. 0 ≤ x
2. 0 ≤ y
3. 0 ≤ z
4. 0 ≤ w
5. x + w ≤ sA
6. y + w ≤ sB
7. z ≤ sAB
8. x ≤ dA
9. y ≤ dB
10. z + w ≤ dAB

这是一组不等式，表明我们正在生产东西，我们使用的不超过我们的供应量，我们创造的不超过对任何特定事物的最终需求。这定义了我们的“可行区域”。

接下来我们需要一个目标函数，即我们要最大化的目标函数。显而易见的选择是我们想要最大化我们生产的数量。所以我们想要最大化 x + y + z + w。

您原来问题的答案如下所示。给定一组可用输入和可用输出，解决上述线性规划问题以优化生产。当且仅当最佳生产水平为 dA + dB + dAB 时，您才能满足生产目标。更好的是，您将获得的解决方案将准确告诉您如何满足生产需求。