3

ナップザックの問題を解決する puLP コードがいくつかあります。

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 変数を導入することで実現できます。

処方

Yすべてバイナリ {0,1} である25 個の新しい変数 [y1..y25] を導入します

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 個の Y 値を 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 に答える