Help us understand the problem. What is going on with this article?

組合せ最適化でグループ分け

More than 3 years have passed since last update.

問題

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を参考にしました。
【日常に潜む最適化問題】受験者をなるべく均等に試験会場に割り振るアルゴリズム

以上

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away