8

レベル A から 23 名、レベル B から 24 名、レベル C から 30 名の生徒を 3 つのクラスに割り当てる必要があります。クラスはほぼ同じサイズである必要があります。異なるレベルを 1 つのクラスに混在させることもできますが、できれば避けたほうがよいでしょう。どのような場合でも、クラスの 1 つのレベルから生徒が 0 人になるか、6 人以上になる必要があります。

この組み合わせ最適化問題を解くのを手伝ってくれませんか? 以下は、入力と出力のサンプルです。一般的な問題の解き方を教えていただければボーナスポイント！

入力：

pupils = { "A" : 23, "B" : 24, "C": 30 }

出力例 (あまり良くありません!)

Class #1 : {'A': 9,  'B': 6, 'C': 10},
Class #2 : {'A': 10, 'B': 9, 'C': 7},
Class #3 : {'A': 11, 'B': 9, 'C': 6}

編集：これは私の非常にハックな、完全に文書化されていない、半ブルートフォースコードです。それは醜いですが、うまくいきます！よりエレガントなソリューションを作成する方法を学びたいです。

4

1 に答える 1

18

ここでの根本的な問題は、多目的最適化問題を抱えていることです。目的または「ソフトな制約」のいずれかを検討できるという点で、あなたが興味を持っていると私が思う3つのことがあります。

  1. 同程度のクラスサイズを取得する
  2. クラスごとのレベル数を最小限に抑える
  3. クラスに生徒がいる場合、クラスのレベルから十分な生徒がいる。

このための最適化モデルを AMPL で作成したことに注意してください。Python を使用しているため、PuLP や pyomo など、Python 用の同様の最適化モデリング言語を使用できます。モデルは、翻訳するのが難しすぎてはいけません。

問題 (整数) を線形に保ちながら、目的番号 1 を強調する整数計画モデルとデータ ファイルを次に示します。この目的により、最適化問題は、例で示したのと同じ解を見つけます。うまくいけば、これに基づいて他の制約や客観的な用語を追加し、より良い解決策を得ることができます。

目的は、最大のクラス サイズを最小限に抑えることです。対象の変数は y[i,j] です。y[i,j] for i for LEVEL, j in CLASS は、クラス j に割り当てられたレベル i の生徒数です。各クラスの各レベルの最小人数の生徒がそのレベルに割り当てられている場合は、入力があると想定しています。

目的関数はあなたが望むものではないかもしれませんが、それはクラスのサイズを線形に等しくしようとする方法です。また、これが問題を解決する最も効率的な方法であるとは約束しません。この問題には、より優れたカスタム アルゴリズムがあるかもしれませんが、私がしなければならなかったのは、制約と目的を表現することだけで、アルゴリズムを作成する必要はありませんでした。あなたの使用にはおそらくそれで十分です。

neos-server.orgのソルバーGurobiを使用して（lpsolveまたは別のオープンソース最適化ソルバーを使用できます）、解決策を得ました

y :=
1 1   14
1 2    9
1 3    0
2 1    6
2 2    0
2 3   18
3 1    6
3 2   16
3 3    8
;

モデル：

set LEVEL ordered;
set CLASS;

param maxClassSize {CLASS};
param minLevelNumberInClass {LEVEL, CLASS};
param numInLevel {LEVEL};

var z >= 0;
var y{LEVEL, CLASS} integer, >= 0;
var x{LEVEL, CLASS} binary;

#minimize maximum class size
minimize obj: 
  z;

subject to allStudentsAssigned {i in LEVEL}:
  sum {j in CLASS} y[i,j] = numInLevel[i];

#z is the largest of all classes sizes
subject to minMaxZ {j in CLASS}:
  z >= sum {i in LEVEL} y[i,j];

subject to maxClassSizeCon {j in CLASS}:
  sum {i in LEVEL} y[i,j] <= maxClassSize[j];

#xij = 1 if any students from level i are in class j
subject to defineX {i in LEVEL, j in CLASS}:
  y[i,j] <= min(numInLevel[i], maxClassSize[j]) * x[i,j];

#if any students from level i are assigned to class j, then there is a minimum
#if x[i,j] = 1,  y[i,j] >= minLevelNumberInClass[i,j]
subject to minLevel {i in LEVEL, j in CLASS}:
  minLevelNumberInClass[i,j] * x[i,j] <= y[i,j];

あなたの例のデータファイル：

set LEVEL := 1 2 3;
set CLASS := 1 2 3;

param minLevelNumberInClass:  
  1 2 3 :=
1 6 6 6
2 6 6 6
3 6 6 6
;

param maxClassSize :=
1 77
2 77
3 77
;

param numInLevel :=
1 23
2 24
3 30
;
于 2013-06-09T22:04:05.147 に答える