5

我正在编写一个在木材场中使用的应用程序。给定许多板或梁长度，目标是计算所需的板数量，同时最大限度地减少浪费。例如，一个特定维度的购物清单可能如下：

3x 2.9 米
5x 1.6 米
21x 0.9 米

在木材场，人们会检查可用的木板长度并将其输入到应用程序中。假设这个尺寸有 4.8 米的长度。

一个简单的方法是尝试以递减的长度安装剩余的板：

2.9 + 2.9 = 5.8 所以不适合 4.8 米的板
2.9 + 1.6 = 4.5 所以没关系。

没有长度小于剩余的 0.3 米，所以这个板是“满的”。我们将再安装两个这种类型，然后我们有以下长度可供选择：

2x 1.6 米
21x 0.9 米

好的，所以这个算法工作得相当好。但是，如果我们不拟合 2.9 + 1.6，而是拟合 2.9 + 0.9 + 0.9 = 4.7 会怎样。然后，我们将每块板产生 0.1 米的废物，而不是 0.3 米。

枚举所有可能组合的一个问题是，每个长度可能在一块板上出现不止一次，并且一块板中适合的长度的数量也会有所不同。有没有一种我可以使用的已知算法来最大程度地减少所有电路板的总浪费？

此外，如果木材场有两个或更多长度可用怎么办？例如 5.4、4.8 和 3.6 米？这肯定会使事情复杂化。可以为每个可用长度运行选定的算法，并选择浪费最少的长度。但最优雅的解决方案是允许混合可用长度，因此最佳答案可能是 1x 5.4、3x 4.8、6x 3.6。但对于初学者来说，我很乐意将答案限制为一个长度。

4

2 回答 2

3

最小化浪费实际上是广义子集和问题的优化问题，即NP-Complete，因此该问题没有已知的多项式时间解，

虽然是 NP-Complete，但可以使用动态规划生成该问题的伪多项式解决方案，或者将其简化为背包（重量=值=长度，W=板尺寸），并使用其伪多项式解决方案，这非常相似。

但是，在这里更棘手的是，伪多项式解决方案假定整数，而您的示例表明情况并非如此。您可以通过使用定点算法来表示长度来解决它（即 4.8 将显示为 48，如果您在每个长度的点后仅使用一位数字，如果您在点后使用 2 位数字，则为 480， ...）。

注意：这个算法会为你最小化浪费，但它不保证最小化浪费的“最小日志数”。

无论如何，由于找到任何解决方案都是 NP-Hard，因此找到使用最少对数的解决方案也是 NP-Hard。

于 2012-05-03T13:20:06.940 回答
2

您的特定问题是所谓的“切割库存”类问题的变体。看看维基百科的“切割库存问题”（CSP）页面

我喜欢用简单的英语解释切割库存问题的简单版本。来自AIMMS：

“切料问题：如何将长卷材料（称为原料）切割成规定尺寸的较小卷（称为成品），给定每个成品的需求。”

AIMMS 的这个pdf很好。

请注意，研究人员提出的基本切割库存问题有很多变体。这些整数编程讲座记录了广义切削库存问题的良好表述（参见第 17 页）

这些 MILP 问题并不难表述，因为目标函数和约束遵循标准 CSP 的基本模式。关于有效解决这些问题的技术存在大量研究。

如果您可以使用 LP/IP 求解器，例如 CPLEX、R 或 Excel 求解器（针对较小的问题），那么绝对值得制定您的问题并在这些求解器上进行尝试。

希望有帮助。

于 2012-05-03T19:56:50.620 回答