已知库存的最优装箱算法

Question

医院正在改变他们消毒设备的方式。以前，当地的外科医生会保留自己的所有设备并制作自己的手术托盘。现在他们必须遵守全国标准。他们想知道他们可以从现有库存中制作多少个新的托盘，以及需要购买多少新设备。

医疗设备清单如下：

http://pastebin.com/rstWSurU

每家医院都有各种医疗设备的代码，然后是相应物品的数量。这个字典展示了三个手术托盘及其对应物品。

http://pastebin.com/bUAZhanK

总共有144种不同的手术托盘。

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

他们希望最大化使用现有库存完成的托盘数量。他们还想知道需要购买哪些设备才能完成剩余的托盘。

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

如果有人知道如何聪明地解决这个问题，请让我知道！

- NicolaiF

---

我没有看到任何OR条件。你只需要把所有需要的东西都放进去，然后看看缺少什么多余的。为什么它不起作用？ - amit

这样做确实可以最小化所需的物品，但不能最大化创建的托盘数量。 - NicolaiF

如果您在购买所需物品之前最大化托盘数量，从实际道德的角度来看，您可能还希望按紧急程度优先考虑手术。 - גלעד ברקן

目前他们没有对任何手术托盘进行权重或优先级排序。 - NicolaiF

我还没有实现解决方案，我仍在努力找出解决问题的最聪明方法。我已经从相应的数据库中获取了必要的数据，并将它们放入字典中，并更新了原始问题。 - NicolaiF

Answer 1

如果我理解正确，我们可以分别针对每个医院进行优化。我的猜测是以下内容将是MIP（混合整数规划）模型的一个良好起点：

我使用以下指标：i代表物品，t代表托盘。 x（t，i）表示我们分配给每种托盘类型的物品数量。 y（t）计算可以使用可用物品组成的每种类型托盘的数量。从解决方案中，我们可以计算需要订购的短缺量。

当然，我们只是在最大化我们可以制作的托盘数量。没有考虑平衡（一种类型的托盘很多，而另一种类型很少或没有）。我通过不允许创建超过所需托盘的数量来稍微减轻一下（如果我们有更多的物品，它们需要放到其他类型的托盘中）。这个要求被规定为对y（t）的上限。

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

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

将运输过剩物品添加到其他医院会使模型更加复杂。在这种情况下，我们可能需要一个需要同时考虑所有医院的模型。这可能是某些分解方法的有趣案例。

- Erwin Kalvelagen

---

不得不深入研究 ILP 问题和 MILP 变量，这绝对是一个可行的解决方案。您有实现的任何技巧吗？现在我正在考虑使用 R 或 Python。 - NicolaiF

我最擅长使用高级建模语言，例如GAMS和AMPL。但是在实现优化模型时，R和Python也经常被使用。由于单一医院模型并不是非常复杂，因此使用R和Python应该可以很好地完成。如果使用Python，您可能需要考虑使用像Pulp或Pyomo这样的工具（或者您也可以直接针对求解器API在Python中编写模型代码）。 - Erwin Kalvelagen