用Python(Pulp)进行线性规划-调度

3
我正在尝试将排班优化为一个(整数)线性问题来进行公式化。我遇到了一些编码问题(主要是由于Pulp),这与公式化相当分离。
问题如下:
在五年期间内(每月时间步长),安排n艘船只,受以下限制约束:
- 每月必须有一条船只处于“本地巡逻”状态(state = 'C') - 每年必须有一条船只进行“扩展巡逻”(state = 'A'),持续四个月,从7月到10月结束 - 每艘船只在五年期间内必须进行4个月的检查(state = '4') - 每艘船只在五年期间内必须有8个月的休息(state = '8') - 每艘船只大约每5个月需要进行常规维护(state = '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

我希望对上述表达式的左侧取绝对值,但我无法这样做,因为对象被初始化为pulp.LpVariable。有没有解决方法?
无论如何,这可能会或可能不会解决我的问题。如果不能解决,下一个问题是针对熟悉pulp的任何人。如何知道解决方案是否正确,或者求解器在后台添加了某种弹性?(使用该约束条件运行代码会导致错误结果,并且使用不同的求解器(如GLPK)会导致错误)。
1个回答

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中的一个最小示例开始。您甚至可以从这里的案例研究之一开始。每一步都将您的LP写入文件并进行检查。这将立即告诉您哪些约束条件或变量有误,您可以进行修改。

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

希望这能让你向前迈进。


谢谢Ram,最终我使用了case语句使其正常工作。但是我无法使用通用的“>”操作符。 - user2777139
嗨@Ram。请回答这个问题https://datascience.stackexchange.com/questions/49792/adding-constraints-in-pulp-optimization-problems-in-python?noredirect=1#comment56928_49792 - KHAN irfan

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接