使用 PuLP (python) 为多台薄膜制造机器分配薄膜生产作业

Question

我正在尝试解决一个有点类似于装箱问题的问题。在这个问题中，我必须将作业分配给具有不同薄膜宽度的薄膜制造机器。所有机器的使用量必须相同。每卷都有特定的宽度。只要所有作业宽度的总和小于机器薄膜宽度，机器就可以完成多个作业。

我将其建模为装箱问题。因为我需要确保所有机器都有相同数量的卷，所以我将垃圾箱作为二维数组，其中每种类型都有多个垃圾箱。在我的公式中 c 是机器的容量，x 是一个二进制变量，它指定是否正在使用一个 bin，y 是一个二进制变量，它指定一个 roll 是否被分配给一个 bin。总的来说objective就是尽量减少垃圾的产生。

$Minimize \sum_{j} \sum_{i} [c_{i} * x_{i,j} - \sum_{k}l_{k} * y_{k,ij}] \newline s.t. \sum_{k} y_{k, ij} = 1 , \quad \quad \forall i, j \newline \quad \sum_{k}l_{k} * y_{k,ij} <=x_{i,j} * c_{i}, \quad \forall i,j \newline \quad x_{i,j} = x_{i+1,j} \quad \forall i = 1.... n-1 ,j = 1... m \newline x_{i,j} = {{\left \{ 0,1 \right \}}} \newline y_{i,j,k} = {{\left \{ 0,1 \right \}}} \newline$

基于此，我用pulp写了python代码

from pulp import *
prob = LpProblem("Production Problem",LpMinimize)
capacity = [1350, 2100]
rolls = [970, 1050, 970, 1100, 1050, 500, 500, 500, 1050, 1350,1200, 370]
I = range(2) # machine film width
J = range(10) # bins for each machine film width 
K = range(len(rolls)) # number of rolls in total 

# variable to determine wether a particular bin is used
x = LpVariable.dicts(name = "Bin", indexs = ((i,j) for i in I for j in J), cat = 'Binary')
# variable to determine if roll is assigned to a particular bin 
y = LpVariable.dicts(name = "RollBin", indexs = ((i,j, k) for i in I for j in J for k in K), cat = 'Binary')
# variable to calculate wastage 
w = LpVariable(name = 'wastage', lowBound = 0, cat = LpInteger)

w = LpVariable(name = 'wastage')
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        for k in K:
            secondPart = rolls[k] * y[(i,j,k)]
        w += firstPart - secondPart
prob+=w

#each roll is assigned to exactly 1 bin
for k in K:
    prob += lpSum([y[(i,j,k)] for i in I for j in J]) == 1

#bin size is not exceeded
for i in I:
    for j in J:
        prob += lpSum(rolls[k] * y[(i,j,k)] for k in K) - capacity[i] * x[(i,j)] <= 0

# similar number of bins of each type are used 
# for i in range(0,len(capacity)-1):
#         prob+= lpSum(x[(i,j)] for j in J) - lpSum(x[(i + 1,j)] for j in J) <= 2
prob+= x[(i,j)] == x[i+1,j] for i in I for j in J 

status = prob.solve()
print(prob)
for v in prob.variables():
    if v.varValue > 0:
        print(v.name, "=", v.varValue)
print(value(prob.objective))
print(LpStatus[status])

我的第一个问题是我不确定如何指定最后一个约束。现在它抛出一个错误。其次，我尝试删除约束并得到 0 的 objective 值，这绝对是错误的。我认为第一个约束将确保所有卷都分配给一台机器但是当我打印出解决方案时，none 卷被分配并且 none 机器（箱）正在用过的。

有人可以帮我解决这个问题吗？我的公式有问题吗？

[更新]：现在只收录原题。

Answer 1

My first problem is that I am not sure how to specify the last constraint. Right now it throws an error.

约束格式正确：

for i in I[:-1]:
    for j in J:
        prob += x[i,j] == x[i+1,j]

Secondly, I tried removing the constraint and got an objective value of 0 which is definitely wrong. I thought that the first constraint would ensure that all the rolls would be assigned to a machine but when I printed out the solution, none of the rolls were assigned and none of the machines(bins) were being used.

还有其他一些小问题。

在此区块中：

w = LpVariable(name = 'wastage')
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        for k in K:
            secondPart = rolls[k] * y[(i,j,k)]
        w += firstPart - secondPart
prob+=w

secondPart 一直更新，最后只取最后一个 k 的值。你可能不想要这个。另外，我的理解是表达式 w+= 向 objective 函数添加了项。但是，prob+=w 在已添加的其他项之上添加了 w，并且由于 w 是连续无界变量，因此问题是无界的。我在 w 处添加了一个零下限并且它工作正常。

正确的方块：

w = LpVariable(name = 'wastage', lowBound=0)
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        secondPart = lpSum(rolls[k] * y[(i,j,k)] for k in K)
        w += firstPart - secondPart
prob+=w

修改了所有代码（我删除了求解器，因为我没有）：

from pulp import *
prob = LpProblem("Production Problem",LpMinimize)
capacity = [1350, 2100]
rolls = [970, 1050, 970, 1100, 1050, 500, 500, 500, 1050, 1350,1200, 370, 370]

I = range(2) # machine film width
J = range(10) # bins for each machine film width 
K = range(len(rolls)) # number of rolls in total 

# variable to determine wether a particular bin is used
x = LpVariable.dicts(name = "Bin", indexs = ((i,j) for i in I for j in J), lowBound = 0, upBound = 1, cat = 'Integer')
# variable to determine if roll is assigned to a particular bin 
y = LpVariable.dicts(name = "RollBin", indexs = ((i,j, k) for i in I for j in J for k in K), lowBound = 0, upBound = 1, cat = 'Integer')
w = LpVariable(name = 'wastage', lowBound=0)
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        secondPart = lpSum(rolls[k] * y[(i,j,k)] for k in K)
        w += firstPart - secondPart
prob+=w
#prob += lpSum(capacity[i] * x[(i,j)] - lpSum(rolls[k]*y[(i,j,k)] for k in K) for i in I for j in J)

for k in K:
    prob += lpSum([y[(i,j,k)] for i in I for j in J]) == 1

for k in K:
    prob += lpSum([rolls[k] * y[(i,j,k)] for i in I for j in J]) <= lpSum([capacity[i] * x[(i,j)] for i in I for j in J])

for i in I[:-1]:
    for j in J:
        prob += x[i,j] == x[i+1,j]

status = prob.solve()
print(prob)
for v in prob.variables():
    if v.varValue > 0:
        print(v.name, "=", v.varValue)
print(value(prob.objective))
print(LpStatus[status])

解输出：

('Bin_(0,_9)', '=', 1.0)
('Bin_(1,_9)', '=', 1.0)
('RollBin_(0,_3,_7)', '=', 1.0)
('RollBin_(0,_4,_12)', '=', 1.0)
('RollBin_(0,_6,_5)', '=', 1.0)
('RollBin_(0,_7,_10)', '=', 1.0)
('RollBin_(1,_0,_2)', '=', 1.0)
('RollBin_(1,_0,_6)', '=', 1.0)
('RollBin_(1,_2,_0)', '=', 1.0)
('RollBin_(1,_3,_11)', '=', 1.0)
('RollBin_(1,_4,_3)', '=', 1.0)
('RollBin_(1,_6,_1)', '=', 1.0)
('RollBin_(1,_8,_4)', '=', 1.0)
('RollBin_(1,_9,_8)', '=', 1.0)
('RollBin_(1,_9,_9)', '=', 1.0)
-7530.0
Optimal

另请注意，欧文的评论是正确的：x_{ij} 设计过度。我没有触及这个，但是给 x.

一个索引确实是个好主意

希望对您有所帮助！

使用 PuLP (python) 为多台薄膜制造机器分配薄膜生产作业

Allocating production jobs for films for multiple film manufacturing machines with PuLP (python)

python

linear-programming

bin-packing

pulp