python - 使用 Python 进行线性编程(Pulp)- 调度

Question

我正在尝试通过将其制定为(整数)线性问题来优化时间表。我在编码部分遇到了一些问题(主要是由于 Pulp)，这与公式完全不同。

问题:

在 5 年的时间段内安排 n 艘船(以月为单位的时间步长)，受以下限制:

• 每月只有一艘船必须进行“本地巡逻”(状态 = 'C')
• 每年只有一艘船必须进行“延长巡逻”(状态 = 'A')，从 7 月到 10 月(含)为期四个月
• 每艘船必须在 5 年期间进行一次为期 4 个月的检查(state = '4')
• 每艘船在 5 年期间必须有一次长达 8 个月的休息时间(state = '8')
• 每艘船必须大约每 5 个月进行一次定期维护(state = 'M')
• 一艘船在给定月份内只能处于一种状态，但也可以没有状态(开放/空置，'_')

目标函数公式:

定义松弛变量，计算计划偏离 5 个月 ('M') 维护计划的次数(和数量)。

如果需要，我可以解释更多设置，但现在我有一些基本问题可能是我问题的根源。

这是我的限制之一(blockList 存储每艘船的第 4 个月和第 8 个月区 block 的开始):

# Each ship must have one 8block and one m4block in a 5 year schedule, which must be between 2 and 3 years apart
for n in ship_list:
    prob += blockList[n][0] - blockList[n][1] >= 24
    prob += blockList[n][0] - blockList[n][1] <= 36

我想取上述表达式的 LHS 的绝对值，但我不能，因为对象被初始化为 pulp.LpVariable。有任何解决方法的建议吗？

无论如何，这可能会或可能不会解决我的问题。如果没有，我的下一个问题是针对任何熟悉 PuLP 的人。我怎么知道解决方案是否正确，或者求解器是否在后台添加了某种弹性？ (使用该约束按原样运行代码会给出不正确的结果，而使用不同的求解器(如 GLPK)会给出错误)。

Answer 1

这里有一些建议:

1. 取绝对值

   在 PuLP 中，您可以依靠底层 Python 命令来做到这一点。

   类似的东西:

   if blockList[n][0] > blockList[n][1]:
       prob += blockList[n][0] - blockList[n][1] >= 24
   else:
       prob += blockList[n][1] - blockList[n][0] >= 24
   

2. 要查看求解器是否要“增加弹性”，您需要检查 pulp.constants.LpStatusOptimal 的值。 如果此值为 1，则问题已最优解. 注意典型的做法是添加一个虚拟松弛变量或一个剩余变量，在目标函数中给它一个小的惩罚。如果在解决方案中虚拟变量不为零，则意味着该问题需要额外的“弹性”。

3. 最后，我的主要建议是从小处着手，使用 PuLP 中可用的最小示例。您甚至可以从 case studies here 之一开始.在每个步骤中，将您的 LP 记录到一个文件中并进行检查。这会立即告诉您关闭了哪些约束或变量，您可以更改它。

   class pulp.LpProblem(name='outfile.lp', sense=1)
   

希望这能让你继续前进。