Skip to main content
 首页 » 编程设计

python之二维装箱

2025年04月02日16Renyi-Fan

我正在使用以下整数规划模型来解决二维装箱问题。以下模型说明了一维版本。我编写的代码包含附加维度的约束。


我正在使用 Python PuLP 来解决优化问题。代码如下:

from pulp import * 
 
#knapsack problem 
 
def knapsolve(item): 
 
    prob = LpProblem('BinPacking', LpMinimize) 
 
    ys = [LpVariable("y{0}".format(i+1), cat="Binary") for i in range(item.bins)] 
 
    xs = [LpVariable("x{0}{1}".format(i+1, j+1), cat="Binary") 
          for i in range(item.items) for j in range(item.bins)] 
 
    #minimize objective 
    nbins = sum(ys) 
    prob += nbins 
 
    print(nbins) 
 
    #constraints 
 
    t = nbins >= 1 
    print(t) 
    prob += t 
 
    for i in range(item.items): 
        con1 = sum(xs[(i + j*item.bins)] for j in range(item.bins)) 
        t = con1 == 1 
        prob += t 
        print(t) 
 
    for k in range(item.bins): 
        x = xs[k*item.bins : (k+1)*item.bins] 
        con1 = sum([x1*w for x1, w in zip(x, item.itemweight)]) 
        t = con1 <= item.binweight[k] * ys[k] 
        #t = con1 <= item.binweight[k] 
        prob += t 
        print(t) 
 
    for k in range(item.bins): 
        x = xs[k*item.bins : (k+1)*item.bins] 
        con1 = sum([x1*w for x1, w in zip(x, item.itemheight)]) 
        t = con1 <= item.binheight[k] * ys[k] 
        #t = con1 <= item.binheight[k] 
        prob += t 
        print(t) 
 
    status = prob.solve() 
 
    print(LpStatus[status]) 
    print("Objective value:", value(prob.objective)) 
    print ('\nThe values of the variables : \n') 
 
    for v in prob.variables(): 
        print(v.name, "=", v.varValue) 
 
    return 
 
class Item: 
    #bins, binweight, items, weight, itemheight, binheight 
 
    bins = 5 
    items = 5 
 
    binweight = [2,3,2,5,3] 
    itemweight = [1,2,2,1,3] 
 
    itemheight = [2,1,4,5,3] 
    binheight = [4,9,10,8,10] 
 
 
item = Item() 
 
knapsolve(item) 

它产生以下输出:

y1 + y2 + y3 + y4 + y5 
y1 + y2 + y3 + y4 + y5 >= 1 
x11 + x21 + x31 + x41 + x51 = 1 
x12 + x22 + x32 + x42 + x52 = 1 
x13 + x23 + x33 + x43 + x53 = 1 
x14 + x24 + x34 + x44 + x54 = 1 
x15 + x25 + x35 + x45 + x55 = 1 
x11 + 2*x12 + 2*x13 + x14 + 3*x15 - 2*y1 <= 0 
x21 + 2*x22 + 2*x23 + x24 + 3*x25 - 3*y2 <= 0 
x31 + 2*x32 + 2*x33 + x34 + 3*x35 - 2*y3 <= 0 
x41 + 2*x42 + 2*x43 + x44 + 3*x45 - 5*y4 <= 0 
x51 + 2*x52 + 2*x53 + x54 + 3*x55 - 3*y5 <= 0 
2*x11 + x12 + 4*x13 + 5*x14 + 3*x15 - 4*y1 <= 0 
2*x21 + x22 + 4*x23 + 5*x24 + 3*x25 - 9*y2 <= 0 
2*x31 + x32 + 4*x33 + 5*x34 + 3*x35 - 10*y3 <= 0 
2*x41 + x42 + 4*x43 + 5*x44 + 3*x45 - 8*y4 <= 0 
2*x51 + x52 + 4*x53 + 5*x54 + 3*x55 - 10*y5 <= 0 
Optimal 
Objective value: 3.0 
 
The values of the variables :  
 
x11 = 0.0 
x12 = 0.0 
x13 = 0.0 
x14 = 0.0 
x15 = 0.0 
x21 = 0.0 
x22 = 0.0 
x23 = 1.0 
x24 = 0.0 
x25 = 0.0 
x31 = 0.0 
x32 = 0.0 
x33 = 0.0 
x34 = 0.0 
x35 = 0.0 
x41 = 0.0 
x42 = 1.0 
x43 = 0.0 
x44 = 0.0 
x45 = 1.0 
x51 = 1.0 
x52 = 0.0 
x53 = 0.0 
x54 = 1.0 
x55 = 0.0 
y1 = 0.0 
y2 = 1.0 
y3 = 0.0 
y4 = 1.0 
y5 = 1.0 

已硬编码的示例输入数据应产生 1 个 bin 作为输出,即一个 y 变量的值应为 1。但事实并非如此。方程式是否正确建模?是否有另一种方法来指定约束?

请您参考如下方法:

标准装箱问题的数学模型使用 x(bins,items) 而在 Python 模型中您似乎混合使用了 x(bins,items) 和 x(items,bins)。对 xs 的赋值使用 x(items,bins) 但构造 xs[(i + j*item.bins)] 暗示 x(箱子,元素)。通过检查输出很容易看出这一点:x11 + x21 + x31 + x41 + x51 = 1,表示 x(bins,items)。这种具有显式指数计算的建模在实践中是相当不可靠的。这是一个玩具模型,但对于真实模型来说,缺少类型检查可能非常危险。

不同的垃圾箱重量和高度应该没问题。

还给出了你的数据

binweight = [2,3,2,5,3] 
itemweight = [1,2,2,1,3]    
itemheight = [2,1,4,5,3] 
binheight = [4,9,10,8,10] 

我不相信这可以像您声称的那样仅用 1 个垃圾箱就可以处理。为此,您需要 3 个箱子(箱子 2,4 和 5)。 (你在这里很幸运,因为尽管 Python 代码中实际上存在错误,但你得到了很好的解决方案)。