1

我有以下问题，我想用 excel 求解器或任何其他工具来解决（欢迎任何建议），但我不想编写代码。

我有几件物品（大约 40 个）要放在几个背包（大约 5 个）中。每件物品都有不同的重量，但每个背包都有相同的空间。

物品重量的总和远小于背包的容量。

我需要做的是分配背包中的物品，它们的重量或多或少相同。换句话说，减少方差。

有一个限制：有些项目不能放在一起。我有一个可以或不能一起使用的项目列表（或邻接矩阵）。

当然，一旦一件物品在背包中，就不能再放入第二件（每个物品之王只有一件物品）。

我正在尝试使用 excel 求解器来解决这个问题，但是所有 3 种算法都说他们找不到解决方案，但是手动我可以找到它们，所以我认为我没有正确配置。

无论如何，我只能在 excel 中配置有关权重的部分问题，但我无法设置有关项目之间不兼容的部分问题。

感谢您的帮助

4

1 回答 1

1

与背包相比，这更像是带有侧面约束的多处理器调度。

您可以尝试像这样的幼稚公式。对于每个项目，有 [背包数量] 0-1 个变量指示该项目在哪个背包中，以及这些变量总和为 1 的约束。目标是最小化背包中的最大总重量。对于每对不能一起走的物品，有[背包数]个约束，对应的指标变量之和小于等于1。

这是一个工作示例，其中包含两个背包（A 和 B）、三个项目（x，重量 3；y，重量 1；和 z，重量 4）和一个冲突（x 不能与 y）。

minimize C
over 0-1 variables Ax, Ay, Az, Bx, By, Bz and real variable C
subject to
C >= 3*Ax + 1*Ay + 4*Az  # load in A
C >= 3*Bx + 1*By + 4*Bz  # load in B
Ax + Bx = 1  # one placement of x
Ay + By = 1  # one placement of y
Az + Bz = 1  # one placement of z
Ax + Ay <= 1  # conflict between x and y in A
Bx + By <= 1  # conflict between x and y in B

这个公式不是最优的，因为没有对称性破坏——本质上，LP 求解器的搜索树被一个等于背包排列数量的因子复制。这只有5个！= 120 在你最坏的情况下，所以它可能没问题。要走的路可能是列生成，其中一个主问题相当于用正确数量的背包准确覆盖项目，一个子问题相当于包装一个受约束的背包，但这超出了 Excel 的范围。

于 2016-09-19T15:41:29.610 回答