この記事の応用です。
商品とビンに順序をつけた場合のビンパッキング問題になります。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import pulp | |
from pulp import LpVariable as Var | |
from pulp import lpSum | |
from collections import defaultdict | |
def main(): | |
## 問題の宣言 | |
prob = pulp.LpProblem(sense=pulp.LpMinimize) | |
## 定数の宣言 | |
# うさぎの数 | |
N = 9 | |
# ゲージの個数 | |
M = 7 | |
# 各うさぎが食べるりんごの量 | |
w = [1.2, 2.2, 1.0, 0.7, 1.8, 2.3, 1.4, 1.8, 0.7] | |
# ゲージに入れられるうさぎの数 | |
g = [1, 1, 1, 1, 2, 2, 2] | |
## 変数の宣言 | |
x = defaultdict(dict) | |
for i in range(N): | |
for j in range(M): | |
x[i][j] = Var(name='x{}_{}'.format(i, j), cat='Binary') | |
p = [Var(name='p{}'.format(j), cat='Integer') for j in range(M)] | |
## 目的関数 | |
prob += lpSum([p[j] for j in range(M)]) | |
## 制約 | |
for i in range(N): | |
for j in range(M-1): | |
prob += x[i][j] <= x[i][j+1] | |
for i in range(N): | |
prob += x[i][M-1] == 1 | |
for i in range(N-1): | |
for j in range(M): | |
prob += x[i][j] >= x[i+1][j] | |
for j in range(M): | |
if j == 0: | |
prob += lpSum([x[i][j] for i in range(N)]) <= g[j] | |
else: | |
prob += lpSum([x[i][j] - x[i][j-1] for i in range(N)]) <= g[j] | |
for j in range(M): | |
if j == 0: | |
prob += lpSum([x[i][j]*w[i] for i in range(N)]) <= p[j] | |
else: | |
prob += lpSum([(x[i][j]-x[i][j-1])*w[i] for i in range(N)]) <= p[j] | |
## ソルバー実行 | |
prob.solve() | |
status = prob.status | |
print(status) | |
## 結果の表示 | |
print('\n入力') | |
for i in range(N): | |
print('うさぎ{}が食べるりんごの量は{}'.format(i, w[i])) | |
print('\n出力') | |
for j in range(M): | |
if j == 0: | |
rabs = [i for i in range(N) if x[i][j].value() == 1] | |
apps = '{0:.1f}'.format(sum([w[i] for i in rabs])) | |
else: | |
rabs = [i for i in range(N) if x[i][j].value() == 1 and x[i][j-1].value() == 0] | |
apps = '{0:.1f}'.format(sum([w[i] for i in rabs])) | |
print('ゲージ{}に入れるうさぎは {}'.format(j, ' '.join(map(str, rabs)))) | |
print('ゲージ{}に必要なりんごの個数は{} -> {}'.format(j, apps, p[j].value())) | |
if __name__ == '__main__': | |
main() |
実行結果
入力 うさぎ0が食べるりんごの量は1.2 うさぎ1が食べるりんごの量は2.2 うさぎ2が食べるりんごの量は1.0 うさぎ3が食べるりんごの量は0.7 うさぎ4が食べるりんごの量は1.8 うさぎ5が食べるりんごの量は2.3 うさぎ6が食べるりんごの量は1.4 うさぎ7が食べるりんごの量は1.8 うさぎ8が食べるりんごの量は0.7 出力 ゲージ0に入れるうさぎは ゲージ0に必要なりんごの個数は0.0 -> 0.0 ゲージ1に入れるうさぎは 0 ゲージ1に必要なりんごの個数は1.2 -> 2.0 ゲージ2に入れるうさぎは 1 ゲージ2に必要なりんごの個数は2.2 -> 3.0 ゲージ3に入れるうさぎは 2 ゲージ3に必要なりんごの個数は1.0 -> 1.0 ゲージ4に入れるうさぎは 3 4 ゲージ4に必要なりんごの個数は2.5 -> 3.0 ゲージ5に入れるうさぎは 5 6 ゲージ5に必要なりんごの個数は3.7 -> 4.0 ゲージ6に入れるうさぎは 7 8 ゲージ6に必要なりんごの個数は2.5 -> 3.0