我正在尝试通过将其制定为(整数)线性问题来优化时间表。我在编码部分遇到了一些问题(主要是由于 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)会给出错误)。
最佳答案
这里有一些建议:
取绝对值
在 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
要查看求解器是否要“增加弹性”,您需要检查
pulp.constants.LpStatusOptimal 的值。
如果此值为 1,则问题已最优解. 注意典型的做法是添加一个虚拟松弛变量或一个剩余变量,在目标函数中给它一个小的惩罚。如果在解决方案中虚拟变量不为零,则意味着该问题需要额外的“弹性”。最后,我的主要建议是从小处着手,使用 PuLP 中可用的最小示例。您甚至可以从 case studies here 之一开始.在每个步骤中,将您的 LP 记录到一个文件中并进行检查。这会立即告诉您关闭了哪些约束或变量,您可以更改它。
class pulp.LpProblem(name='outfile.lp', sense=1)
希望这能让你继续前进。
关于python - 使用 Python 进行线性编程(Pulp)- 调度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18791754/