1

有人可以给我举一个小例子，说明延迟列生成如何解决切割库存问题。我找到了几个抽象地描述它的来源，但我仍然不明白它的作用或如何在程序中实现它。一个带有一小组数字的分步示例会很有帮助。

例如，假设我有不同长度的管道库存：

12、25

客户要求以下长度的管道：

5、10

现在说长度为 x 的管道的值为 x 1.2。我想在为客户进行削减后最大化库存中剩余的价值。究竟如何使用列生成来找到几乎最佳的答案？

4

1 回答 1

3

我们从一个看起来很悲伤的主 LP 开始，它只有阶段 I 松弛变量z5和z10.

minimize z5 + z10
subject to
z5 >= 1 (y5)
z10 >= 1 (y10)
z5, z10 >= 0

y5是我们切割足够多长度为 5 的管道y10的约束，是我们切割足够多长度为 10 的管道的约束。原始解是z5=1, z10=1，最优对偶解是y5=1, y10=1。换个角度看，5 管和 10 管的当前价格均为 1。由于这是第一阶段，我们的库存成本为零，并且解决了库存中每个管长的背包问题（如果您使用经典的 DP，因为它会为所有较小的长度生成一个表格），最大的利润空间是将 25 根管子切成五个 5 根管子。设变量x5,5,5,5,5为这种类型的切割数。

minimize z5 + z10
subject to
5 x5,5,5,5,5 + z5 >= 1 (y5)
z10 >= 1 (y10)
x5,5,5,5,5, z5, z10 >= 0

现在最优原始解是x5,5,5,5,5=0.2, z5=0, z10=1。5管的价格为0，10管的价格为1。我们还不是原始可行的，所以我们的库存仍然没有成本。当前价格下的最优模式是x10,10（浪费 5）和x10,10,5。我们不要浪费。

minimize z5 + z10
subject to
5 x5,5,5,5,5 + x10,10,5 + z5 >= 1 (y5)
2 x10,10,5 + z10 >= 1 (y10)
x5,5,5,5,5, x10,10,5, z5, z10 >= 0

最优原始解是x5,5,5,5,5=0.1, x10,10,5=0.5, z5=0, z10=0。所有的松弛变量都是 0，所以是时候进入第二阶段了。

minimize 25^1.2 x5,5,5,5,5 + 25^1.2 x10,10,5
subject to
5 x5,5,5,5,5 + x10,10,5 >= 1 (y5)
2 x10,10,5 >= 1 (y10)
x5,5,5,5,5, x10,10,5 >= 0

这是双重程序。

maximize y5 + y10
subject to
5 y5 <= 25^1.2
y5 + 2 y10 <= 25^1.2
y5, y10 >= 0

最优原始解仍然是x5,5,5,5,5=0.1, x10,10,5=0.5。最佳对偶解是y5=25^1.2 * 0.2（约 9.5）和y10=25^1.2 * 0.4（约 19.0）。由于我们处于第二阶段，现在 12 管的成本为 12^1.2（约 19.7），而 25 管的成本为 25^1.2（约 47.6）。如果我们切割 12 根管子并浪费 2 根，则成本为 12^1.2 - 2^1.2（约 17.4）。

目前，切割 25 管没有利润。然而，在切割 12 管时，我们花费大约 17.4 来获得两个 5 管或一个 10 管。无论哪种方式，当前总价约为 19.0，这意味着正利润。我将其中一列放入并再次求解，但我累了，只是会告诉你最终的最佳原始是x5,5=0.5, x10=1（12 管上的两个切口）。

请注意，虽然这个解决方案是部分最优的，但如果客户确实想要一个 5 管和一个 10 管，那么我们还有更多的想法要做。事实上，当且仅当客户想要每根管道的数​​量为奇数时，LP 解决方案之外会有浪费，但是，无论客户的总需求如何，浪费最多是一根 5 根管道，这就是我们说的原因这个答案“几乎是最佳的”。

于 2013-03-31T13:05:47.510 回答