2

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

现在它变得越来越有趣了。

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

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

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

（请不要考虑真实的场景，例如，最好只创造理想的场景……想象一下，剩余材料的损失是 X 钱/cm^2，Y 是特定产品质量的价格，而X 和 Y 可以是“任意的”）

4

1 回答 1

2

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

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

一个更困难的优化问题是答案不是数字，而是一个函数，比如一个形状。一个例子是：为了最小化它的重力势能，一条吊链会做成什么样的形状。或者：为了最大化利润，我们应该从这些板上切出什么形状？这种类型的问题是使用变分微积分来解决的，这非常困难。

无论如何，在数值求解优化问题时，需要遵循几个基本步骤。首先，您必须定义一个函数，例如要针对某些变量 'cuts' 最大化的函数，例如 Profit(cuts,params)，而其他参数 'params' 是固定的。“参数”存储信息，例如您拥有的木材数量和类型，以及不同类型家具的价值。

第二步是猜测最佳剪切集，我们称之为cuts_guess。为了做到这一点，您需要提出一种算法，该算法会建议您可以使用您拥有的用品实际制作的一套家具。例如，如果您可以用每块木板制作至少一个书架，那么这可能是您对使用木材的最佳方式的初步猜测。

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

Anyway, all of this will be very difficult for your problem. It's easy how to come up with a guess for a variable (e.g. length), and then how to change that guess (e.g. increase or decrease the length a bit). It's not at all obvious how to make a 'guess' for how to place a cut-out on a board, or how to make a small change.

于 2013-03-24T03:23:19.773 回答