Excel 解算器具有非相邻单元格约束？

Question

我是 Excel 求解器的新手，只是在拿起一本数据科学书籍后才了解它。我想更熟悉这个工具，所以我一直在尝试解决不同的问题。但我被困在一个问题上，我什至不确定是否可以使用求解器？基本上，我需要检查的约束是两个单元格是否相邻。

我的问题:我有一堆袋子，里面装有不同数量的弹珠。我想最大化通过拾取袋子获得的弹珠数量，但它们不能彼此相邻。

这是我在电子表格中的内容:

• 值(value) = 袋中弹珠的数量
• Choose = 是否选择包(二进制)
• 违规 = 行李 1 的(选择*行李编号)- 行李 2 的(选择*行李编号)

如果我拿起两个相邻的袋子，违规将= -1。

+------------+----+----+----+---+---+-------------+
| Bag Number | 1  | 2  | 3  | 4 | 5 | Total Value |
+------------+----+----+----+---+---+-------------+
| Value      | 10 | 20 | 30 | 40| 50|          150|
| Choose     |  0 |  0 |  0 | 0 | 0 |            0|
| Violation  |  0 |  0 |  0 | 0 |   |             |
+------------+----+----+----+---+---+-------------+

最优解:

+------------+----+----+----+---+---+-------------+
| Bag Number | 1  | 2  | 3  | 4 | 5 | Total Value |
+------------+----+----+----+---+---+-------------+
| Value      | 10 | 20 | 30 | 40| 50|          150|
| Choose     |  1 |  0 |  1 | 0 | 1 |           90|
| Violation  |  1 | -3 |  3 |-5 |   |             |
+------------+----+----+----+---+---+-------------+

我尝试了一些限制的组合:

• 对选择行设置二元约束
• 违规次数 >=0 且违规次数 <=-2
• 总目标值 <= 总可能值 (150)

这个问题是我自己编出来的。这可行吗？

Answer 1

是的，问题是适定的。

我建议采用不同的方式来制定邻接约束。特别是，我会使用以下内容:

choose_1 + choose_2 <= 1
choose_2 + choose_3 <= 1
choose_3 + choose_4 <= 1
choose_4 + choose_5 <= 1

这些表明每对 (1,2), (2,3), (3,4) 中最多有一个和(4,5)可以选择。它的优点是不使用袋子编号，袋子编号通常可以是袋子名称(即字符串而不是数字)。它还有另一个好处:我们不需要将变量定义为二进制，而只需将变量定义为连续且介于 0 和 1 之间: 0 <= choose_i <= 1 ，对于所有人i = 1,...,5 。这是因为生成的约束矩阵是 Totally Unimodular ，这意味着求解 linear programming relaxation二元问题的最优解为 choose_i都是 0或1 .

这是我的电子表格布局:

请注意，最好使用不同的颜色来区分变量(绿色)、约束(红色)和数据(蓝色)。我还用绿色字体标记了目标单元格。

以下是公式:

这是求解器模型:

解决方案:

请注意，矩阵完全幺模的事实是 guarantee最佳解决方案将具有二进制值。一般来说，这是不正确的，我们需要将变量定义为二进制并诉诸 branch and bound .

我希望这有帮助。快乐建模!