我是 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)
这个问题是我自己编出来的。这可行吗?
最佳答案
是的,问题是适定的。
我建议采用不同的方式来制定邻接约束。特别是,我会使用以下内容:
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 .
我希望这有帮助。快乐建模!
关于Excel 解算器具有非相邻单元格约束?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24945693/