問題
26個のグループがあり、それぞれ下記のような人数で構成されています。
python3
import numpy as np
n = 26 # グループ数
np.random.seed(11)
a = np.random.randint(10, 20, n) # グループごとの人数
for i in range(n):
print('グループ%2d %d人'%(i, a[i]))
>>>
グループ 0 19人
グループ 1 10人
グループ 2 11人
グループ 3 17人
グループ 4 11人
グループ 5 17人
グループ 6 12人
グループ 7 18人
グループ 8 10人
グループ 9 10人
グループ10 14人
グループ11 12人
グループ12 11人
グループ13 15人
グループ14 15人
グループ15 17人
グループ16 14人
グループ17 11人
グループ18 18人
グループ19 18人
グループ20 11人
グループ21 13人
グループ22 16人
グループ23 12人
グループ24 12人
グループ25 10人
- 26グループを6部屋(0, 1, 2, 3, 4, 5)に分けます。(1部屋に複数グループ)
- 同じグループは、同じ部屋とします。
- グループ番号の若い順から、部屋番号の若い順に割当てます。
- グループ a, b (a<b) を、それぞれ部屋番号 c, d に入れる場合、c <= d でないといけない。
- 1部屋は、63人まで。
グループをどこで分けたらいいでしょうか？
Python で解いてみる
組合せ最適化問題に定式化して解きます。
python3
from pulp import *
limit = 63 # 部屋の容量
m = LpProblem() # 数理モデル
# そのグループまでの部屋の人数
x = [LpVariable('x%d'%i, lowBound=a[i], upBound=limit) for i in range(n)]
# 前後のグループで部屋を分けるかどうか
y = [LpVariable('y%d'%i, cat=LpBinary) for i in range(n-1)]
m += lpSum(x) # 目的関数
m += lpSum(y) <= 6-1 # 部屋数=6以下(区切りは6-1)
for i in range(n-1):
m += x[i+1] >= x[i] + a[i+1] - limit * y[i] # 同じ部屋なら人数を加算
m.solve() # 求解
print(LpStatus[m.status])
print([int(value(x[i])) for i in range(n) if i==n-1 or value(y[i])])
>>>
Optimal
[57, 58, 57, 61, 58, 63]
- 分散最小だと、非線形になり解きづらい。
- 最大値の最小化だと、ソルバーは解きづらいので、制約としている。
CodeIQを参考にしました。
【日常に潜む最適化問題】受験者をなるべく均等に試験会場に割り振るアルゴリズム
以上