线性规划条件约束

Question

有 22 个 driver。每个 driver 必须至少工作 7.6 小时，最多可以工作 10 小时。每个 driver 成本和生产力都不同。

如果有人driver加班（超过7.6小时），前2小时，我们需要支付1.5倍的费用。剩余的0.4小时，我们需要支付2次。

195 小时的工作必须在 22 driver 秒内完成。我们需要以成本最低的方式进行安排。

Driver,Cost,Productivity
A,70,0.8
B,22,0.8
C,24,0.8
D,26,0.8
E,28,0.8
F,30,0.8
G,32,0.8
H,34,0.8
I,36,0.8
J,38,0.8
K,40,0.8
L,42,0.9
M,44,0.9
N,46,0.9
O,48,0.9
P,50,0.9
Q,52,0.9
R,54,0.9
S,56,0.9
T,58,0.9
U,60,0.9
V,62,0.5

决策变量：

X1,X2 .......X22代表分配给每个driver

的总小时数

Objective函数：

最小Z = 20*X1 +22*X2......62*X22

约束条件：

X1>=7.6,X2>=7.6....X22>=7.6

X1<=10,X2<=10....X22<=10

X1+X2.......+X22 <= 195

到目前为止，我已经尝试遵循 python 程序。

import pulp
import pandas as pd


def main():
    model = pulp.LpProblem("Cost minimising scheduling problem", pulp.LpMinimize)

    totalHours = 192
    minHourEachDriver = 7.6
    maxHourEachDriver = 10

    # importing data from CSV

    drivers = pd.DataFrame.from_csv('csv/drivers.csv', index_col=['Driver', 'Cost', 'Productivity'])

    # Decision Variables
    drv = pulp.LpVariable.dicts("driverName", indexs=((i) for i, j, k in drivers.index), lowBound=0,
                                cat='Continuous')

    # Objective
    model += pulp.lpSum([j * (1 / k) * drv[i] for i, j, k in drivers.index]), "Cost"

    # Constraints

    # total no of hours work to be done
    model += pulp.lpSum([drv[i] for i, j, k in drivers.index]) == totalHours

    for i, j, k in drivers.index:
        # minimum hours driver has to work
        model += drv[i] >= minHourEachDriver
        # Maximum hour driver can work
        model += drv[i] <= maxHourEachDriver

    model.solve()

    # model status
    print(pulp.LpStatus[model.status])

    # Total Cost
    print(pulp.value(model.objective))

    # No of hrs allocated to each driver

    for i, j, k in drivers.index:
        var_value = drv[i].varValue
        # print(var_value)
        print("The number hours for driver {0} are {1}".format(i, var_value))


if __name__ == '__main__':
    main()

但是，我无法弄清楚，我们如何设置以下约束。

if some driver work overtime (more than 7.6 hrs), for first 2 hrs, we need to pay 1.5 times. For remaining 0.4 hrs, we need to pay 2 times.

Answer 1

如果for each driver是强制工作7.6h，就没有必要放在条件里了。它只是可以从总小时数（成本）中减去的静态时间（成本），因为它总是发生：

195 - (NumDrivers * 7.6) = 为达到195小时（总时数>NumDrivers*7,6）需要在drivers之间灵活分配的剩余时间作为加班。

我将用两个变量表示每个 driver（一个表示以 1.5 速率工作的时间，另一个表示以双倍速率工作的时间）并制作以下 LP：

Xij = 表示在 j-working 模式下分配给 i-driver 的小时数（假设 j=1 表示 1,5，j=2 表示 2）

基于提供的输入文件：

最小 Z = 70*1,5*X11 + 70*2*X12 + 22*1,5*X21 + 22*2*X22 + ... 62*1,5*X221 + 62*2 *X222

限制条件：

X11+X12+X21+X22+...X221+X222 = 27,8 (195 - (22*7,6))

X11+X12 <= 3,4 X21+X22 <= 3,4 ... X221+X222 <= 3,4

X11<=2 X21<=2 ... X221<=2

为了完整起见，还应该有一组条件表示每个 driver 只有在以 1.5* 完成 2 小时后才能以 j 模式 (2*) 开始，但在这种情况下 objective 函数应该会自动生成。

线性规划条件约束

Linear programming conditional constraint

python-3.x

linear-programming

pulp