已知库存的最佳包装算法

Question

医院正在改变他们对设备进行 sanitizer 的方式。以前，本地的外科医生保留所有自己的设备并制作自己的手术托盘。现在他们必须限制在全国范围内的标准。他们想知道他们可以用现有库存制造多少新托盘，以及他们需要购买多少新设备。

医疗设备的库存是这样的:

http://pastebin.com/rstWSurU

每家医院都有各种医疗设备的代码，然后是相应元素的编号

本词典中显示了 3 个手术托盘及其相应的项目。

http://pastebin.com/bUAZhanK

共有144个不同的操作托盘

医院会被告知他们需要 25 个托盘 x，30 个托盘 y，等等......

他们希望最大限度地增加可用当前库存完成的托盘数量。他们还想知道他们需要购买什么设备才能完成剩余的托盘。

我考虑过两种可能的解决方案，一种是将问题表示为线性规划问题。另一个解决问题的方法是对前 90% 的问题进行循环暴力求解，然后通过多次执行随机算法来解决剩余的 10%，然后选择这些尝试中的最佳解决方案。

我很想知道是否有人知道如何解决这个问题的聪明方法!

Answer 1

如果我理解正确，我们可以分别针对每家医院进行优化。我的猜测是，以下将是 MIP(混合整数规划)模型的良好开端:

我使用以下索引:i 是项目，t 是托盘。 x(t,i) 表示我们为每种托盘类型分配了多少项目。 y(t) 计算我们可以使用可用项目组成的每种类型的托盘数。从解决方案中我们可以计算出我们需要订购的短缺量。

当然，我们只是在尽可能多地制作托盘。没有考虑平衡(一种类型的托盘很多，另一种托盘很少或零)。我通过不允许创建比所需更多的托盘来缓解一点(如果我们有更多的项目，他们需要转到其他类型的托盘)。此要求被表述为 y(t) 的上限。

对于大型问题，我们可以将 (t,i) 组合限制为可能的组合。这将使模型更小。使用精确的数学符号时:

进一步的优化是替换变量 x(t,i)。

将剩余元素添加到其他医院会使模型更加困难。在那种情况下，我们最终可能会得到一个需要同时查看所有医院的模型。对于某些分解方法来说可能是一个有趣的案例。