3

我有一些纸浆代码，它解决了我的背包问题。

prob = LpProblem("Knapsack problem", LpMaximize)

x1 = LpVariable("x1", 0, 12, 'Integer')
x2 = LpVariable("x2", 0, 12, 'Integer')
x3 = LpVariable("x3", 0, 12, 'Integer')
x4 = LpVariable("x4", 0, 12, 'Integer')
x5 = LpVariable("x5", 0, 12, 'Integer')
x6 = LpVariable("x6", 0, 12, 'Integer')
x7 = LpVariable("x7", 0, 12, 'Integer')
x8 = LpVariable("x8", 0, 12, 'Integer')
x9 = LpVariable("x9", 0, 12, 'Integer')
x10 = LpVariable("x10", 0, 12, 'Integer')
x11 = LpVariable("x11", 0, 12, 'Integer')
x12 = LpVariable("x12", 0, 12, 'Integer')
x13 = LpVariable("x13", 0, 12, 'Integer')
x14 = LpVariable("x14", 0, 12, 'Integer')
x15 = LpVariable("x15", 0, 12, 'Integer')
x16 = LpVariable("x16", 0, 12, 'Integer')
x17 = LpVariable("x17", 0, 12, 'Integer')
x18 = LpVariable("x18", 0, 12, 'Integer')
x19 = LpVariable("x19", 0, 12, 'Integer')
x20 = LpVariable("x20", 0, 12, 'Integer')
x21 = LpVariable("x21", 0, 12, 'Integer')
x22 = LpVariable("x22", 0, 12, 'Integer')
x23 = LpVariable("x23", 0, 12, 'Integer')
x24 = LpVariable("x24", 0, 12, 'Integer')
x25 = LpVariable("x25", 0, 12, 'Integer')

prob += 15 * x1 + 18 * x2 + 18 * x3 + 23 * x4 + 18 * x5 + 20 * x6 + 15 * x7 + 16 * x8 + 12 * x9 + 12 * x10 + 25 * x11 + 25 * x12 + 28 * x13 + 35 * x14 + 28 * x15 + 28 * x16 + 25 * x17 + 25 * x18 + 25 * x19 + 28 * x20 + 25 * x21 + 32 * x22 + 32 * x23 + 28 * x24 + 25 * x25, "obj"

prob += 150 * x1 + 180 * x2 + 180 * x3 + 230 * x4 + 180 * x5 + 200 * x6 + 150 * x7 + 160 * x8 + 120 * x9 + 120 * x10 + 250 * x11 + 250 * x12 + 280 * x13 + 350 * x14 + 280 * x15 + 280 * x16 + 250 * x17 + 250 * x18 + 250 * x19 + 280 * x20 + 250 * x21 + 320 * x22 + 320 * x23 + 280 * x24 + 250 * x25 == 6600, "c1"

prob.solve()

print "Status:", LpStatus[prob.status]

for v in prob.variables():
    print v.name, "=", v.varValue

print ("objective = %s" % value(prob.objective))

但是对于这段代码，我需要附加另一个限制：例如，非零的数量prob.variables必须等于（例如）10 的限制。

有人可以帮忙吗？

更新：

对于这段代码，我有输出：

Status: Optimal
X1 = 1.0
x10 = 0.0
x11 = 0.0
x12 = 0.0
x13 = 0.0
x14 = 0.0
x15 = 0.0
x16 = 0.0
x17 = 0.0
x18 = 0.0
x19 = 0.0
x2 = 0.0
x20 = 0.0
x21 = 0.0
x22 = 0.0
x23 = 0.0
x24 = 0.0
x25 = 0.0
x3 = 0.0
x4 = 11.0
x5 = 0.0
x6 = 10.0
x7 = 0.0
x8 = 12.0
x9 = 0.0
objective = 660.0

prob.variables具有非零值的数量仅等于 4。但是说我需要 10，我将如何确保呢？

4

2 回答 2

2

如果您想要一定数量的非零值，您可以通过引入新的 0/1 变量来实现。

公式

引入 25 个新Y变量 [y1..y25]，它们都是二进制 {0,1}

如果 X[i] > 0，我们希望 Y[i] 取值 1。您可以通过添加以下约束来实现。

x[i] < y[i] x M (where M is some big number, say 10,000) for 1 in 1..25

现在，为了确保至少 10 个 Y 值不为零，我们希望其中至少有 10 个为 1。

Y[1]...y[25] >= 10 的总和将确保这一点。

在 PuLP 中 puLP 代码未经测试，但会给你正确的思路来继续。

x=[]
y=[]

for index in range(25):
    y[index] = LpVariable("y"+str(index), 0, 1) #binary variables
    prob += x[index] <= 10000 * y[index], "If x%s is non-zero, then y%s is forced to be 1",%index, %index

prob += lpSum([y[i] for i in range(25)]) >= 10,"Ensuring at least 10 items are non-zero"

希望有帮助。

于 2013-07-22T17:48:16.800 回答
0

我支持提供的答案，但也会评论更好地利用 PuLP（和 Python）的列表理解来获得更短的代码：

from pulp import *
prob = LpProblem("Knapsack problem", LpMaximize)
cost = [15,18,18,23,18,20,15,16,12,12,25,25,28,35,28,28,25,25,25,28,25,32,32,28,25]
x = LpVariable.dicts('x',range(1,26),lowBound=0,upBound=12,cat=pulp.LpInteger)
cap = [150,180,180,230,180,200,150,160,120,120,250,250,280,350,280,280,250,250,250,280,250,320,320,280,250] 
prob += pulp.lpSum([cost[ix]*x[ix] for ix in range(1,25)]), "obj"
prob += pulp.lpSum([cap[ix]*x[ix] for ix in range(1,25)]) == 6600, "c1"
prob.solve()

print "Status:", LpStatus[prob.status]

for v in prob.variables():
    if v.varValue>0.0001:
        print v.name, "=", v.varValue

print ("objective = %s" % value(prob.objective))

我可能在那里打错了一些系数，但我相信你明白我的意思。

于 2017-06-26T20:36:23.180 回答