Python PuLP 中的混合整数线性规划不可行解
Mixed Integer Linear Program Infeasible Solution in Python PuLP
我制定了一个 MILP 来模拟 PuLP 中的多周期多客户调度问题。目的是安排在一周内生产多批产品，以便通过最小化总劳动力成本来制造所有产品批次。每天有一个固定班次和一个加班班次（由于劳动力成本可变，使用起来更贵）。
我使用了两个创建为 'Integer' 变量的变量。但是，我的问题解决方案中仍然得到小数和负值。这怎么可能？请在下面查看我的代码。
'''
Multi-Period Scheduling Problem
'''
from pulp import *
import itertools
正在创建参数和数据：
'''SETS'''
#list of batch_id's waiting for production
batch_ids = ['b1', 'b2', 'b3', 'b4', 'b5', 'b6']
#list of the days available in a week
days = ['mon', 'tue', 'wed', 'thu', 'fri']
#list of shifts in a day
shifts= ['rt', 'ot']
'''PARAMETERS'''
#batch quantity needed
batch_size= {
'b1': 45,
'b2': 60,
'b3': 120,
'b4': 80,
'b5': 230,
'b6': 40
}
#regular time and over time values
time_dict= {'rt': 450, 'ot': 300}
#dict to store minutes available per day per shift
mins_per_day= {d: {s: time_dict[s] for s in shifts} for d in days}
#cycle time in minutes per unit per batch
cycle_time = {
'b1': 45,
'b2': 30,
'b3': 10,
'b4': 80,
'b5': 13,
'b6': 35
}
'''minimum needed units per batch per day; as of now this is a fixed qty= 10, but we can create a separate
dict to store different qty per batch if needed and then use it in the dict comprehension here'''
min_qty= {d:{b: 5 for b in batch_ids} for d in days}
pay_by_shift= {'ot': 0.8625, 'rt': 0.575}
#cost per minute per shift per day:
pay_dict= {d: {s: pay_by_shift[s] for s in shifts} for d in days}
#indexes for batch and day combinations
shifts_ind = [(d,s) for d in days for s in shifts]
#indexes for the make variable:
make_ind= [(d,b) for d in days for b in batch_ids]
定义变量：
'''VARIABLES'''
#number of units of a batch scheduled for production per day per shift
make= LpVariable.dicts("Make Per Day",(days, batch_ids, shifts),0, None, cat= 'Integer')
#binary variable to decide wether OT is scheduled on a given day or not
y= LpVariable.dicts("Use Shift",(days, shifts), 0, 1, cat= 'Integer')
'''model formulation'''
#create model object with a minimize objective
prob= LpProblem("FlexLine Problem",LpMinimize)
定义 Objective 函数
#objective function
prob += lpSum([y[d][s] for d in days for s in shifts]) + \
lpSum([make[d][b][s]* cycle_time[b]* pay_dict[d][s] for d in days for b in batch_ids for s in shifts]), "Total labor cost per week"
定义约束：
'''CONSTRAINTS'''
#demand constraint
for b in batch_ids:
prob += lpSum([make[d][b][s] for d in days for s in shifts]) == batch_size[b]
#time constraint
for (d,s) in shifts_ind:
prob += lpSum([make[d][b][s] * cycle_time[b] for b in batch_ids]) <= mins_per_day[d][s] * y[d][s]
#minimum per day constraint
for (d,b) in make_ind:
prob += lpSum([make[d][b][s] for s in shifts]) >= min_qty[d][b]
#linking constraint
for (d,s) in shifts_ind:
prob += lpSum([make[d][b][s] for b in batch_ids]) <= 100000 * y[d][s]
求解模型：
prob.solve()
Out: -1
print ("Status:", LpStatus[prob.status])
Out: Status: Infeasible
打印变量值：
for v in prob.variables():
print (v.name, "=", v.varValue)
Out:Make_Per_Day_fri_b1_ot = 0.0
Make_Per_Day_fri_b1_rt = 5.0
Make_Per_Day_fri_b2_ot = 0.0
Make_Per_Day_fri_b2_rt = -5.5
Make_Per_Day_fri_b3_ot = 0.0
Make_Per_Day_fri_b3_rt = 5.0
Make_Per_Day_fri_b4_ot = 1.5625
Make_Per_Day_fri_b4_rt = 3.4375
Make_Per_Day_fri_b5_ot = 0.0
Make_Per_Day_fri_b5_rt = 5.0
Make_Per_Day_fri_b6_ot = 5.0
Make_Per_Day_fri_b6_rt = 0.0
Make_Per_Day_mon_b1_ot = 0.0
Make_Per_Day_mon_b1_rt = 5.0
Make_Per_Day_mon_b2_ot = 0.0
Make_Per_Day_mon_b2_rt = -5.5
Make_Per_Day_mon_b3_ot = 0.0
Make_Per_Day_mon_b3_rt = 5.0
Make_Per_Day_mon_b4_ot = 2.9375
Make_Per_Day_mon_b4_rt = 2.0625
Make_Per_Day_mon_b5_ot = 5.0
Make_Per_Day_mon_b5_rt = 0.0
Make_Per_Day_mon_b6_ot = 0.0
Make_Per_Day_mon_b6_rt = 5.0
Make_Per_Day_thu_b1_ot = 25.0
Make_Per_Day_thu_b1_rt = 0.0
Make_Per_Day_thu_b2_ot = 61.0
Make_Per_Day_thu_b2_rt = 0.0
Make_Per_Day_thu_b3_ot = 131.5
Make_Per_Day_thu_b3_rt = 0.0
Make_Per_Day_thu_b4_ot = 60.0
Make_Per_Day_thu_b4_rt = 0.0
Make_Per_Day_thu_b5_ot = 210.0
Make_Per_Day_thu_b5_rt = 0.0
Make_Per_Day_thu_b6_ot = 16.142857
Make_Per_Day_thu_b6_rt = 12.857143
Make_Per_Day_tue_b1_ot = 5.0
Make_Per_Day_tue_b1_rt = 0.0
Make_Per_Day_tue_b2_ot = 0.83333333
Make_Per_Day_tue_b2_rt = 4.1666667
Make_Per_Day_tue_b3_ot = 5.0
Make_Per_Day_tue_b3_rt = 0.0
Make_Per_Day_tue_b4_ot = 0.0
Make_Per_Day_tue_b4_rt = 5.0
Make_Per_Day_tue_b5_ot = 0.0
Make_Per_Day_tue_b5_rt = 5.0
Make_Per_Day_tue_b6_ot = 0.0
Make_Per_Day_tue_b6_rt = -4.0
Make_Per_Day_wed_b1_ot = 5.0
Make_Per_Day_wed_b1_rt = 0.0
Make_Per_Day_wed_b2_ot = 5.0
Make_Per_Day_wed_b2_rt = 0.0
Make_Per_Day_wed_b3_ot = -26.5
Make_Per_Day_wed_b3_rt = 0.0
Make_Per_Day_wed_b4_ot = 1.5625
Make_Per_Day_wed_b4_rt = 3.4375
Make_Per_Day_wed_b5_ot = 5.0
Make_Per_Day_wed_b5_rt = 0.0
Make_Per_Day_wed_b6_ot = 0.0
Make_Per_Day_wed_b6_rt = 5.0
Use_Shift_fri_ot = 1.0
Use_Shift_fri_rt = 1.0
Use_Shift_mon_ot = 1.0
Use_Shift_mon_rt = 1.0
Use_Shift_thu_ot = 41.216667
Use_Shift_thu_rt = 1.0
Use_Shift_tue_ot = 1.0
Use_Shift_tue_rt = 1.0
Use_Shift_wed_ot = 1.0
Use_Shift_wed_rt = 1.0
重申一下，我看到负值、小数以及二进制变量显示为大于 1。这是怎么回事？
您的解决方案状态不可行或最优（似乎不可行）。因此变量值没有任何意义。您可以减小批量大小并尝试找到可行的解决方案和工作模型。同样使用 "writeLP" 你可以用数字检查你的模型。
我制定了一个 MILP 来模拟 PuLP 中的多周期多客户调度问题。目的是安排在一周内生产多批产品，以便通过最小化总劳动力成本来制造所有产品批次。每天有一个固定班次和一个加班班次（由于劳动力成本可变，使用起来更贵）。
我使用了两个创建为 'Integer' 变量的变量。但是，我的问题解决方案中仍然得到小数和负值。这怎么可能？请在下面查看我的代码。
'''
Multi-Period Scheduling Problem
'''
from pulp import *
import itertools
正在创建参数和数据：
'''SETS'''
#list of batch_id's waiting for production
batch_ids = ['b1', 'b2', 'b3', 'b4', 'b5', 'b6']
#list of the days available in a week
days = ['mon', 'tue', 'wed', 'thu', 'fri']
#list of shifts in a day
shifts= ['rt', 'ot']
'''PARAMETERS'''
#batch quantity needed
batch_size= {
'b1': 45,
'b2': 60,
'b3': 120,
'b4': 80,
'b5': 230,
'b6': 40
}
#regular time and over time values
time_dict= {'rt': 450, 'ot': 300}
#dict to store minutes available per day per shift
mins_per_day= {d: {s: time_dict[s] for s in shifts} for d in days}
#cycle time in minutes per unit per batch
cycle_time = {
'b1': 45,
'b2': 30,
'b3': 10,
'b4': 80,
'b5': 13,
'b6': 35
}
'''minimum needed units per batch per day; as of now this is a fixed qty= 10, but we can create a separate
dict to store different qty per batch if needed and then use it in the dict comprehension here'''
min_qty= {d:{b: 5 for b in batch_ids} for d in days}
pay_by_shift= {'ot': 0.8625, 'rt': 0.575}
#cost per minute per shift per day:
pay_dict= {d: {s: pay_by_shift[s] for s in shifts} for d in days}
#indexes for batch and day combinations
shifts_ind = [(d,s) for d in days for s in shifts]
#indexes for the make variable:
make_ind= [(d,b) for d in days for b in batch_ids]
定义变量：
'''VARIABLES'''
#number of units of a batch scheduled for production per day per shift
make= LpVariable.dicts("Make Per Day",(days, batch_ids, shifts),0, None, cat= 'Integer')
#binary variable to decide wether OT is scheduled on a given day or not
y= LpVariable.dicts("Use Shift",(days, shifts), 0, 1, cat= 'Integer')
'''model formulation'''
#create model object with a minimize objective
prob= LpProblem("FlexLine Problem",LpMinimize)
定义 Objective 函数
#objective function
prob += lpSum([y[d][s] for d in days for s in shifts]) + \
lpSum([make[d][b][s]* cycle_time[b]* pay_dict[d][s] for d in days for b in batch_ids for s in shifts]), "Total labor cost per week"
定义约束：
'''CONSTRAINTS'''
#demand constraint
for b in batch_ids:
prob += lpSum([make[d][b][s] for d in days for s in shifts]) == batch_size[b]
#time constraint
for (d,s) in shifts_ind:
prob += lpSum([make[d][b][s] * cycle_time[b] for b in batch_ids]) <= mins_per_day[d][s] * y[d][s]
#minimum per day constraint
for (d,b) in make_ind:
prob += lpSum([make[d][b][s] for s in shifts]) >= min_qty[d][b]
#linking constraint
for (d,s) in shifts_ind:
prob += lpSum([make[d][b][s] for b in batch_ids]) <= 100000 * y[d][s]
求解模型：
prob.solve()
Out: -1
print ("Status:", LpStatus[prob.status])
Out: Status: Infeasible
打印变量值：
for v in prob.variables():
print (v.name, "=", v.varValue)
Out:Make_Per_Day_fri_b1_ot = 0.0
Make_Per_Day_fri_b1_rt = 5.0
Make_Per_Day_fri_b2_ot = 0.0
Make_Per_Day_fri_b2_rt = -5.5
Make_Per_Day_fri_b3_ot = 0.0
Make_Per_Day_fri_b3_rt = 5.0
Make_Per_Day_fri_b4_ot = 1.5625
Make_Per_Day_fri_b4_rt = 3.4375
Make_Per_Day_fri_b5_ot = 0.0
Make_Per_Day_fri_b5_rt = 5.0
Make_Per_Day_fri_b6_ot = 5.0
Make_Per_Day_fri_b6_rt = 0.0
Make_Per_Day_mon_b1_ot = 0.0
Make_Per_Day_mon_b1_rt = 5.0
Make_Per_Day_mon_b2_ot = 0.0
Make_Per_Day_mon_b2_rt = -5.5
Make_Per_Day_mon_b3_ot = 0.0
Make_Per_Day_mon_b3_rt = 5.0
Make_Per_Day_mon_b4_ot = 2.9375
Make_Per_Day_mon_b4_rt = 2.0625
Make_Per_Day_mon_b5_ot = 5.0
Make_Per_Day_mon_b5_rt = 0.0
Make_Per_Day_mon_b6_ot = 0.0
Make_Per_Day_mon_b6_rt = 5.0
Make_Per_Day_thu_b1_ot = 25.0
Make_Per_Day_thu_b1_rt = 0.0
Make_Per_Day_thu_b2_ot = 61.0
Make_Per_Day_thu_b2_rt = 0.0
Make_Per_Day_thu_b3_ot = 131.5
Make_Per_Day_thu_b3_rt = 0.0
Make_Per_Day_thu_b4_ot = 60.0
Make_Per_Day_thu_b4_rt = 0.0
Make_Per_Day_thu_b5_ot = 210.0
Make_Per_Day_thu_b5_rt = 0.0
Make_Per_Day_thu_b6_ot = 16.142857
Make_Per_Day_thu_b6_rt = 12.857143
Make_Per_Day_tue_b1_ot = 5.0
Make_Per_Day_tue_b1_rt = 0.0
Make_Per_Day_tue_b2_ot = 0.83333333
Make_Per_Day_tue_b2_rt = 4.1666667
Make_Per_Day_tue_b3_ot = 5.0
Make_Per_Day_tue_b3_rt = 0.0
Make_Per_Day_tue_b4_ot = 0.0
Make_Per_Day_tue_b4_rt = 5.0
Make_Per_Day_tue_b5_ot = 0.0
Make_Per_Day_tue_b5_rt = 5.0
Make_Per_Day_tue_b6_ot = 0.0
Make_Per_Day_tue_b6_rt = -4.0
Make_Per_Day_wed_b1_ot = 5.0
Make_Per_Day_wed_b1_rt = 0.0
Make_Per_Day_wed_b2_ot = 5.0
Make_Per_Day_wed_b2_rt = 0.0
Make_Per_Day_wed_b3_ot = -26.5
Make_Per_Day_wed_b3_rt = 0.0
Make_Per_Day_wed_b4_ot = 1.5625
Make_Per_Day_wed_b4_rt = 3.4375
Make_Per_Day_wed_b5_ot = 5.0
Make_Per_Day_wed_b5_rt = 0.0
Make_Per_Day_wed_b6_ot = 0.0
Make_Per_Day_wed_b6_rt = 5.0
Use_Shift_fri_ot = 1.0
Use_Shift_fri_rt = 1.0
Use_Shift_mon_ot = 1.0
Use_Shift_mon_rt = 1.0
Use_Shift_thu_ot = 41.216667
Use_Shift_thu_rt = 1.0
Use_Shift_tue_ot = 1.0
Use_Shift_tue_rt = 1.0
Use_Shift_wed_ot = 1.0
Use_Shift_wed_rt = 1.0
重申一下，我看到负值、小数以及二进制变量显示为大于 1。这是怎么回事？
您的解决方案状态不可行或最优（似乎不可行）。因此变量值没有任何意义。您可以减小批量大小并尝试找到可行的解决方案和工作模型。同样使用 "writeLP" 你可以用数字检查你的模型。