8
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Posted at

問題

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

以上

8
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?