サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

【Python】順序付きビンパッキング問題

この記事の応用です。
商品とビンに順序をつけた場合のビンパッキング問題になります。

f:id:inarizuuuushi:20170918140838p:plain:w600

f:id:inarizuuuushi:20170918140846p:plain:w600

ソースコード

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()
view raw rabbit2.py hosted with ❤ by GitHub


実行結果

入力
うさぎ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