3

我试图通过将其公式化为（整数）线性问题来优化时间表。我在编码部分遇到了一些问题（主要是由于纸浆），这与配方完全不同。

问题：

附表 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。任何解决方法的建议？

Anyways, that may or may not fix my problem. If it doesn't, my next question is for anyone familiar with pulp. How can I know if the solution true, or if there was some sort of elasticity added by the solver in the background? (Running the code as is with that constraint gives incorrect results, and using a different solver like GLPK gives an error).

4

1 回答 1

0

这里有一些建议：

  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 的最小示例。您甚至可以从这里的一个案例研究开始。在每个步骤中，将您的 LP 写到一个文件中并检查它。这将立即告诉您哪些约束或变量已关闭，您可以对其进行更改。

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

希望这能让你继续前进。

于 2013-09-13T21:46:49.363 回答