先日どこかの学校のクラス分けに色々と考慮されていない点があり始業式を中断したというニュースを見て、すごい違和感が生まれたので、これをITで解決するならどうアプローチするかなということで考えてみました。
問題の定義
生徒たちを異なるクラスに分ける際には、様々な要因を考慮する必要があります。そこで今回は、クラス間での能力の平均をできるだけ均一に保ちつつ、人数も均等に分配したい、というような場合。加えて、特定の生徒同士を同じクラスにしない、というような特別な制約が存在する場合について考えていきます。
問題の定式化
この問題を解決するために、制約付き最適化問題として定式化し、線形プログラミングを用いて解を求める方法を紹介します。使用するツールはPythonのPuLPライブラリで、線形最適化問題を解くために広く使用されています。
変数の設定
まず、各生徒がどのクラスに割り当てられるかを表す二値変数を定義します。これにより、生徒が特定のクラスに割り当てられている場合は1、そうでない場合は0となります。
目的関数
目的関数は、クラスごとのスコア合計の偏差を最小化することで設定します。これは、各クラスの能力の平均が全体の平均からどれだけ離れているかを最小限に抑えることを意味します。非線形の要素（二乗項や絶対値）を含む目的関数を線形化するために、各クラスの偏差を表す補助変数を導入します。
制約条件
生徒割り当て制約: 各生徒はちょうど1つのクラスにのみ割り当てられます。
特定の制約: 特定の生徒同士が一緒にならないようにします。
人数の均等分配: できるだけ各クラスの人数が均等になるようにします。
コード
import pulp
# 生徒データと制約
students = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']
scores = {'A': 90, 'B': 85, 'C': 95, 'D': 70, 'E': 80, 'F': 75, 'G': 90, 'H': 85, 'I': 95, 'J': 70, 'K': 80, 'L': 75}
restrictions = [('A', 'B'), ('C', 'D')]
num_classes = 3
# 問題の設定
problem = pulp.LpProblem("ClassAssignment", pulp.LpMinimize)
# 変数の設定
x = pulp.LpVariable.dicts("x", (students, range(num_classes)), cat=pulp.LpBinary)
# 各クラスのスコア合計変数
class_scores = pulp.LpVariable.dicts("class_scores", range(num_classes), lowBound=0)
# 目的関数：クラスごとのスコア合計の平均からの偏差を最小化
total_score = sum(scores[s] for s in students)
average_score_per_class = total_score / num_classes
# 各クラスのスコア合計の偏差変数（線形最適化のための補助変数）
deviations = pulp.LpVariable.dicts("deviation", range(num_classes), lowBound=0)
# 目的関数：クラスごとのスコア合計の偏差の合計を最小化
problem += pulp.lpSum(deviations[j] for j in range(num_classes))
# 各クラスのスコア合計を計算
for j in range(num_classes):
problem += class_scores[j] == pulp.lpSum(x[s][j] * scores[s] for s in students), f"TotalScoreClass{j}"
# 制約の設定
# 各生徒は1つのクラスにのみ割り当てられる
for s in students:
problem += pulp.lpSum(x[s][j] for j in range(num_classes)) == 1
# 特定の生徒が一緒にならない制約
for s1, s2 in restrictions:
for j in range(num_classes):
problem += x[s1][j] + x[s2][j] <= 1
# 人数ができるだけ均等になるように
students_per_class = len(students) / num_classes
for j in range(num_classes):
problem += pulp.lpSum(x[s][j] for s in students) == students_per_class
# ソルバーの実行
problem.solve()
# 結果の表示
for s in students:
for j in range(num_classes):
if pulp.value(x[s][j]) == 1:
print(f"Student {s} is assigned to class {j}")
# 各クラスのスコア合計の表示
for j in range(num_classes):
print(f"Total score for class {j}: {pulp.value(class_scores[j])}")
実行結果とその解釈
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.02
Student A is assigned to class 0
Student B is assigned to class 2
Student C is assigned to class 1
Student D is assigned to class 2
Student E is assigned to class 2
Student F is assigned to class 0
Student G is assigned to class 2
Student H is assigned to class 1
Student I is assigned to class 1
Student J is assigned to class 1
Student K is assigned to class 0
Student L is assigned to class 0
Total score for class 0: 320.0
Total score for class 1: 345.0
Total score for class 2: 325.0
ソルバーの実行後、各生徒が割り当てられたクラスと、それによって達成されたクラスごとのスコア合計の偏差の最小化の結果を確認できます。この解は、制約条件を満たしつつ、できるだけ公平なクラス分けを提案します。
まとめ
このアプローチを用いることで、複雑な制約を持つクラス分け問題に対して、線形最適化を使って実行可能な解を見つけることができます。PuLPのようなライブラリを使えば、コードによる実装も直感的で、多くの実用的な問題に応用可能です。
ただ、個人的には数理モデルによる最適が生徒にとって最適とは思っていないので、生徒が自身で解決すべきなのか先生が解決すべきなのかなど、現実世界の問題は難しいなーと。