1

我想知道如何对以下优化问题进行分类。

木材厂出售各种库存长度的 2x4 木材。例如，8 英尺可能是 3 美元，10 英尺可能是 4 美元，而 14 英尺可能是 5.50 美元。重要的是，长度与价格不是线性相关的，并非所有离散长度都可以作为库存购买。可以假设在这些离散长度中可用的库存单位是取之不尽的。

length    cost
7.7ft     $2.75
  8ft     $3.00
 10ft     $4.00
 14ft     $5.50

我需要通过从上述库存中切割它们来创建一组具有给定长度的 2x4（说我需要 2 英尺、2.5 英尺、6 英尺的长度，一旦一切都说完了）。此外，每次“切割”都会产生 1/8" 的材料成本（即 0.0104 英尺）。问题的解决方案是将每个所需长度分配给一个库存，并使所有库存的总成本最小化。在这个例子中，最小化成本的最佳解决方案是以 5.50 美元购买 14 英尺的板。（亚军的解决方案是购买两块 8 英尺的板并分配为 {6ft} 和 {2ft, 0.0104ft, 2.5ft}，成本为 6 美元。）

这似乎不是一个背包级问题。这似乎不是一个裁减库存问题（因为我想尽量减少成本而不是尽量减少浪费）。这是什么类型的问题，我该如何有效地解决它？

（作为后记，这是一个非虚构的问题，我已经在 Haskell 中使用多集分区和迭代以明显、低效的方式解决了。运行时对于超过 23 个所需长度和 6 个可用库存大小的实际使用来说是禁止的。 )

4

1 回答 1

1

我相信这是一个库存问题，除了它是一个多目标或多标准的库存问题（您希望最大限度地减少货币成本和材料成本），请参阅本文的示例。不幸的是，我发现的几乎所有关于这种削减库存问题的在线资源都在付费墙后面。另外，我已经好几年没有做过整数线性规划了，但是如果我没记错的话，多目标问题比单目标问题要困难得多。

一种选择是实施两遍算法。第一遍完全忽略了切割板的材料成本，在单目标问题中只使用了货币成本（代替标准切割库存问题中的浪费成本）。这可能会给您留下一个无效的解决方案，此时您执行本地搜索，例如用一个 14 英尺的板和一个 8 英尺的吟游诗人替换两个 10 英尺的板，直到找到一个有效的解决方案。一旦找到有效的解决方案，您可以继续在本地搜索多次迭代，看看您是否可以改进解决方案。与一次性多目标解决方案相比，该算法可能不是最优的，但它应该更容易实现。

于 2013-04-23T14:32:44.677 回答