使用Python进行线性编程（Pulp）-计划

Question

我正在尝试通过将时间表公式化为（整数）线性问题来优化时间表。我在编码部分遇到了一些问题（主要是由于Pulp造成的），该部分与公式完全分开。

问题：

附表n的船期为5年（时间步长为月），但受以下限制：

• [每月只有一艘，只有一艘船必须在“本地巡逻”（状态='C'）
• [每年只有一艘，只有一艘船必须进行“扩展巡逻”（状态='A'，这是从7月到10月的四个月的时间段）
• 每艘船在5年内必须进行一次为期4个月的检查（状态='4'）
• 每艘船在5年内必须有8个月长的休息时间（状态='8'）
• 每艘船必须每5个月进行一次定期维护（状态='M'）
• [船舶在给定的月份中只能处于一种状态，但也可以没有任何状态（开放/空缺，'_'）

目标函数公式：

定义对计划偏离5个月（'M'）维护计划的次数（和数量）进行计数的松弛变量。

如果需要，我可以进一步解释设置，但是目前我有一些基本问题可能是我的问题的根源。

这是我的限制条件之一（blockList为每个飞船存储4个月和8个月的时间段的开始）：

# 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。有任何解决方法的建议吗？

无论如何，这可能会或可能不会解决我的问题。如果没有，那么我的下一个问题是对任何熟悉纸浆的人。我怎么知道解决方案是否正确，或者求解器在后台添加了某种弹性？ （使用该约束按原样运行代码会产生错误的结果，而使用其他求解器（例如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)
   

希望这可以使您前进。