algorithm - 组合优化 - 制造家具时利润最大化

Question

一些公司提供大木板。这些面板被切割成所需的碎片。例如，为了制作书架，他们必须从大面板上切割碎片。大多数情况下， pig 板并没有100%使用，会有一些损失，一些剩余的碎片，无法使用。因此，为了最大限度地减少损失，他们必须在大面板上找到单独部件的最佳布局。我认为这就是所谓的“二维矩形装箱问题”。

现在变得越来越有趣了。

并非所有面板都相同，它们的色调可能略有不同。理想的书架是由一 block 或多 block 具有相同色调的面板切割而成的。但书架可以生产成不同的质量(理想的一个；一件不同色调的书架；两件……，使用三种不同颜色的板；等等……)。每种品质都有自己的价格。 (质量越好越贵)。

现在我们有一些木板库存，并且需要一些家具(例如 100 个书架)。目标是最大化利润(例如，创建一些质量理想的产品和一些质量较差的产品，以保持较低的 Material 损失)。

如何解决这个问题？如何将其与装箱问题结合起来？以及提示、论文/文章将不胜感激。我知道我可以通过整数线性规划最小化/最大化某些函数和不等式，但我真的不知道如何解决这个问题。

(请不要考虑真实的场景，例如，最好只创建理想的场景...想象一下，剩余 Material 的损失是每 cm^2 X 钱，Y 是特定产品的价格质量并且 X 和 Y 可以是“任意的”)

Answer 1

我可以说明这些问题是如何解决的，以及为什么你的问题特别困难。

在典型的优化问题中，您希望相对于一组变量(例如长度)最大化或最小化函数(例如能量)。例如， Spring 应该有多长才能最大限度地减少储存的能量。答案只是一个数字，即 Spring 的平衡长度。另一个例子是“我们应该将产品定价多少才能实现利润最大化？” (太贵了，没人会买任何东西；太便宜了，你就无法支付费用。)同样，答案只是一个数字，即最优价格。像这样的优化可以用普通的微积分来处理。

一个更困难的优化问题是答案不是数字，而是函数，例如形状。一个例子是:为了最小化其重力势能，悬链将形成什么形状。或者:我们应该将这些木板切成什么形状才能实现利润最大化？这类问题用变分微积分求解，难度很大。

无论如何，在用数值方法解决优化问题时，需要遵循一些基本步骤。首先，您必须定义一个函数，例如您希望相对于某些变量“cuts”最大化的利润(cuts，params)，同时其他参数“params”固定。 “params”存储诸如您拥有的木材数量和类型以及不同类型家具的值(value)等信息。

第二步是猜测最佳剪辑集，我们将其称为“cuts_guess”。为了做到这一点，你需要想出一个算法来建议一套你可以使用你拥有的 Material 实际制作的家具。例如，如果您可以用每 block 木板制作至少一个书架，那么这可能是您对使用木材的最佳方式的初步猜测。

第三阶段是优化。对于初始化，设置cuts_best=cuts_guess和profit_best=profit_guess=profit(cuts_guess, params)。然后，您需要(一种算法)对“削减”进行小的伪随机更改，并检查利润是否增加或减少。记录您找到的最佳切割组合以及相应的利润。通常最好是涉及一些随机性，以便探索最大数量的可能性，而不是“卡在”一个糟糕的选择上。如果您查找“蒙特卡洛算法”，您会找到这样的示例。

无论如何，这一切对于你的问题来说都是非常困难的。如何对变量(例如长度)进行猜测，然后如何更改该猜测(例如稍微增加或减少长度)很容易。如何“猜测”如何在板上放置切口，或者如何进行小改动，这一点都不明显。