我是 Excel 求解器的新手，只是在拿起一本数据科学书籍后才了解它。我想更熟悉这个工具，所以我一直在尝试解决不同的问题。但我被困在一个问题上，我什至不确定是否可以使用求解器？基本上，我需要检查的约束是两个单元格是否相邻。
我的问题：我有一堆袋子，里面装有不同数量的弹珠。我想最大限度地增加通过拾取袋子获得的弹珠数量，但它们不能彼此相邻。
这是我在电子表格中的内容：
- 价值 = 袋中弹珠的数量
- 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 且违规
- 总目标值
我自己解决了这个问题。这可行吗？
是的，问题是适定的。
我建议采用不同的方式来制定邻接约束。特别是，我会使用以下内容：
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) and (4,5)可以选择。它的优点是不使用袋子编号，袋子编号通常可以是袋子名称（即字符串而不是数字）。它还有另一个好处：我们不需要将变量定义为二进制，而只需将变量定义为连续且介于 0 和 1 之间：0 <= choose_i <= 1， 对全部i = 1,...,5。这是因为所得的约束矩阵是完全单模 http://en.wikipedia.org/wiki/Unimodular_matrix，这意味着求解线性规划松弛 http://en.wikipedia.org/wiki/Linear_programming_relaxation二元问题的最优解为choose_i都是0 or 1.
这是我的电子表格布局:
请注意，最好使用不同的颜色来区分变量（绿色）、约束（红色）和数据（蓝色）。我还用绿色字体标记了目标单元格。
这里有formulas:
这是求解器模型:
Solution:
请注意，矩阵完全幺模这一事实是保证 http://en.wikipedia.org/wiki/Linear_programming_relaxation#Solution_quality_of_relaxed_and_original_programs最佳解决方案将具有二进制值。一般来说，这是不正确的，我们需要将变量定义为二进制并诉诸分支定界 http://en.wikipedia.org/wiki/Branch_and_bound.
我希望这有帮助。快乐建模！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
