図1.1現在の配属方法の流れ
文教大学のゼミ配属問題
文教大学 97p21037 大内 徹
97p21037@shoan.bunkyo.ac.jp
文教大学経営情報学部では3年生になると「ゼミナール｣（以下ゼミ）という科目を履修しなくてはならない｡学生は10数個開設されたゼミの中の一つに所属する｡すべての学生が行きたいゼミに所属できればいいが、それぞれのゼミには14人という定員があるのでそうはいかない。もしそのゼミに所属したいと希望する学生が定員を越えた時は選考して学生が選ばれ、定員を守られる。現在行われている方法は、学生が一つゼミを選択してそこで一度締め切る。定員以下ならそのまま所属できるが定員を越えるとそのゼミの先生によって成績、面接などから選考される｡合格なら所属、不合格ならその学生は今度は定員に余裕のあるゼミから選ぶ、そしてまた締め切る、という段階をすべての学生が所属するまで繰り返すという方法である｡
この方法では第一希望で不合格となってしまった学生は、それ以降は残ったゼミからしか選べない。また、人気のあるゼミに希望を出す事は学生にとって大きな負担がかかる｡実際、第一希望はAゼミだったが、確実にBゼミに希望を出して所属したという話を聞く｡この学科で開設されるゼミは、経済、経営、OR、会計など多岐の分野にわたっているので、第一希望で所属できない学生は不本意な分野のゼミにしか希望を出せないという事が起こりうる｡
現在の配属方法は学生の第一希望だけを参照して配属をして、第二希望を参照して配属をする、というように何回かに配属を分けている｡もし最初にすべての学生のゼミに対する所属したい順番を知ることが出来たらもっと良い配属ができるのではないかと考えた。そこで、理想の配属方法を提案して現在の配属方法と比較をしようと考えた。現在の配属方法の特徴を考慮し、理想の配属方法として安定結婚問題を適用した｡
文教大学では3年生になると、必ずゼミに所属しなくてはならない。その為に学生のゼミ配属が行われる。ゼミは15個開かれていて、それぞれのゼミの定員が14名、学生は約180名である。
2年生の秋期から学生はゼミの見学や、先生方への訪問などを行い、所属したいゼミを1つだけ選択する。そして選択したゼミを用紙に記入し提出する。その希望先のゼミが定員以下ならそのまま所属できるのだが、もし定員を超しているとそのゼミの先生によって成績、面接などによって学生はふるいにかけられる。ここで不合格となってゼミに所属できなかった学生は、今度は残ったゼミから所属したいゼミを選択する、という配属方法をすべての学生が所属するまで行われている（図１参照）。
図1.1現在の配属方法の流れ
経営情報学科では経営、会計、経済、OR、法律、など幅広い分野のゼミが開設されている。その為、現在の配属方法では第1希望に所属できなかった学生は、自分の勉強したい分野のゼミに希望を出せないことが起こる。例えば、経営に関するすべてのゼミが第1希望で定員を満たした場合、経営に関する分野に第2希望を出せないということである。その時は不本意なゼミに所属するしかないのである。また、本当は人気のあるゼミが第1希望だけど、そのゼミに希望を出さず確実に所属できる第2希望のゼミを選択するということも考えられる。つまり、この配属方法は学生にとってとてもリスクが大きい。
秋期にいろいろなゼミを見学して、ほとんどの学生はある程度所属したいゼミの順位付けはできているはずである。しかしこの配属方法では第1希望しか参照されない。もし、学生のゼミに対する順位付けという情報を使うことができたら、より効率的な配属ができるのではないかと考える。
そこで、私の考える理想的な配属方法を提案して、現在の配属方法と比較しようと考える。ただ。理想の配属をするのではなく、同じ物差しで比較をするという点から、現在の配属方法の特徴をもつ上での理想の配属方法を提案するとする。
その特徴として、定員を超えたゼミに関してはそのゼミの先生方に学生を選択できる権利が与えられるということがあげられる。このことから先生方も学生に対して何らかの基準で順位付けをしている事がわかる。
以上のことから、
①理想の配属にあたって先生の意見も考慮されているという特徴を持たせる
②学生のゼミに対する順位付け
③先生の学生に対する順位付け、という特徴、
という情報を使って理想の配属方法を提案する。
配属問題に関する研究や成果は数多くあり[6]、そのほとんどは解決手段として線形計画を適用している。しかし、文教大学のゼミ配属問題の特徴を考慮すると線形計画法よりも安定結婚問題を適用したほうが良いと私は考える。なぜなら、文教大学では配属に当たって学生の意見だけではなく教員の意見も含まれていてる。学生、教員の2つのどちらのグループも満足できる配属を達成できる安定結婚問題の方が適していると考えたからである｡この章では、まず線形計画法と、安定結婚問題の最低限の説明をして、なぜ線形計画法ではなく、安定結婚問題で理想の配属方法を提案するのかを示す。
線形計画問題とは、何本かの線形不等式によって規定される空間の中で線形関数を最小化または最大化する問題である。
最小化または最大化する線形関数を目的関数と呼び、最大化の時にはmax、最小化の時にはminが書かれる。解の範囲を規定する線形不等式はs.t.(subject
to)の後に書く。すべての線形不等式を満たす変数の集まりを実行可能解と呼ぶ。実行可能解の存在する領域を実行可能領域と呼ぶ。実行可能領域の中で目的関数を最小化または最大化するものを最適解と呼ぶ（図3.1参照）[1]。
図.3.1．線形計画法の実行可能領域、最適解の例
この線形計画をゼミ割り当て問題へ応用する。
表3.1は学生iがゼミjに所属するなら(i,j)番目のセルを1、所属しないなら0とすることを表している。表3.2のセル(i,j)は学生iがゼミjに所属したときの満足度を表す。このように考えれば、セル（i,j）をXijとして、{0,1}変数として考えることができる。つまり定式化すると図3.2のようになる。
表.3.1．所属を表す表
| ゼミ1 | ゼミ2 | ゼミ3 | |
| 学生1 | 0 | 1 | 0 |
| 学生2 | 1 | 0 | 0 |
| 学生3 | 0 | 0 | 1 |
この例では学生1はゼミ2に、学生2はゼミ1に、学生3はゼミ3に所属
表.3.2．満足度を表す表
| ゼミ1 | ゼミ2 | ゼミ3 | |
| 学生1 | 10 | 5 | 2 |
| 学生2 | 10 | 4 | 8 |
| 学生3 | 7 | 6 | 10 |
学生1がゼミ1に所属すると10、ゼミ2に所属すると5、ゼミ3に所属すると2点の満足度が得られる
//点数が高い方が満足度が高い
max 10X11 + 5X12 + 2X13 +
10X21 + 4X22 + 8X23 +
7X31 + 6X32 + 10X33
s.t. //それぞれの学生はどれかのゼミに所属しなくてはならないという制約式
X11 + X12 + X13 >= 1
X21 + X22 + X23 >= 1
X31 + X32 + X33 >= 1
//それぞれのゼミは定員以下でなければならないという制約式
X11 + X21 + X31 <=
ゼミ1の定員
X12 + X22 + X23 <=
ゼミ2の定員
X13 + X23 + X33 <=
ゼミ3の定員
//表3.1を満たすようにする為、変数に制約を与える
変数X11,X12,・・・X32,X33は{0,1}変数
図.3.2 配属問題を定式化
この問題において導かれる解の変数は0か1である。このように求める解を整数に限定する線形計画を整数計画という。整数計画法は非常に難しい問題として知られている｡しかし、この問題の性質から最後の制約「変数X11,X12,・・・X32,X33は{0,1}変数でなければならない」を「変数X11,X12,・・・X32,X33は0から1の間をとれば良い」と緩和しても、最適解の中に整数値のみからなるものが存在する[2]。そこで最後の制約を図3.3のようにすれば線形計画として捉える事ができ、後は計算をすれば答えが得られる。
//変数に対して緩和をする
0 <= X11,X12,・・・X32,X33
<= 1
図.3.3 線形計画に緩和
以上のようなアプローチを行えば、ゼミの配属を行うことができる。その為の条件として学生には順位付けの以外に満足度を表してもらわなければならない。
n人の男性集合Mとnの女性集合Wが存在するとする。各人は異性を対象に好きな順番を持っている。ある男性hが女性d’よりdを好む時、d<hd'と表す。さらに、d=d'の時はd<=hd'と書く。女性においても同様に表現する。
1人の男性hと1人の女性dの組（h,d）をペアと呼ぶ。いくつかのペアから構成される集合Mにおいて、すべての人がいずれかのペアに属し、かつどの人もひとつより多くのペアに属さないとき、Mはマッチングと呼ばれる。マッチングMにペア(h,d)が属している時、hはd(dはh）の（マッチングMにおける）パートナーと呼び、h=pM(d)(d=dM(h)) と表す。
あるマッチングMにおいて、以下の3つの条件をすべて満たすペア(h',d')はマッチングMをブロックしていると表現し、そのペアをブロッキングペアと呼ぶ。
(h',d')はMにおけるブロッキングペア
ブロッキングペアが存在しないマッチングを安定マッチングと呼ぶ。
安定マッチングはGale-Shapleyのアルゴリズムによって求めることができる。
|
Gale-Shapleyのアルゴリズム 入力 男性集合M、女性集合W、および各人の異性全員に対する選好順序 出力 安定マッチング step0 （初期設定）全員の状況は独身であり、すべての男性はどの女性にもプロポーズを行ってない。 step1 独身の男性hが存在する限り以下の操作を繰り返す
|
このアルゴリズムでは男性が女性にプロポーズをする方法をとっているが逆に女性が男性にプロポーズをするという方法を行っても安定マッチングが得られる。
安定マッチングはいかなる安定結婚問題の例においても少なくとも1つは存在し、一般的には複数存在している。その中のひとつとして得られるGale-Shapleyのアルゴリズムの解の特徴を以下に示す。（証明は省略する）
|
安定結婚のある例に対しGale-Shapleyアルゴリズムで得られたマッチングをM1とする。 |
つまり、男性からプロポーズをする方法をとれば男性にもっとも好ましい（男性最良）、女性からプロポーズをする方法をとれば女性にもっとも好ましい（女性最良）のマッチングが得られる。
男性を学生、1人の女性を1つのゼミと考えれば安定結婚問題をゼミ配属問題に適用できるが、いくつかの問題点が挙げられる。そこでそれらを列挙し、それを配属用に拡張する。学生n人に対しゼミ数はm個であり1対1のマッチングにできない、ということが挙げられる。これについてはあるゼミの定員がk人ならそのゼミをk人の女性とみて適用すればよい（図3.4参照）。
図.3.4．安定結婚問題の配属問題への拡張
このようにすればゼミの集合の要素数は学生の集合の要素数を等しくなるか、上回る。一般的には上回るので、学生の集合にダミーの学生を入れて、ゼミと学生の集合数が等しくなるようにする。この時、ダミーのゼミに対する好きな順番は適当でよい。また、ゼミの選好順序において、ダミー学生の位置する順位はすべての学生の順位付けが終わった後におけばよい。ダミー学生同士の順位は適当でよい。（図3.5参照）
図3.5．安定結婚問題の配属問題への拡張2
このようにすれば安定結婚問題をゼミ配属問題に適用できる。
文教大学では、学生の意見だけではなく定員を超えた場合、先生方の意見が配属に関わってくる。線形計画法において、目的関数を「ゼミと学生の満足度を最大にする」とすれば確かに先生方の意見も含まれ、かつ、満足度が最大になる配属を導く。しかし、全体の満足度を最大にするために幾人かの学生（ゼミ）が不本意な結果になる可能性がある。そこで、配属されたあるマッチングにおいて、個人の不満のないようなマッチングを導く安定結婚問題で提案しようと考えた。まずはGale-Shapleyのアルゴリズムで学生、もしくはゼミに最も有利な安定マッチングを求めて分析をして、そこからより公平な配属を目標として拡張していきたい｡
ここでは実験を行ったときに使ったデータの作成方法と現在の配属方法のアルゴリズムの説明をする。ゼミの配属結果はゼミの人気の状況や、学生の人気の状況によって変化していくと考えられる。例えば、学生がバランスよくゼミに希望を出せばすべての人が第1希望に所属できるのに対し、ある１つのゼミに人気が集中するとほとんどの学生は第１希望に所属できない、という事だ｡そこで様々な人気のパターンを作り、データを作成しようと考えた｡データでは学生のゼミに対する順位付け、ゼミの学生に対する順位付けの2つを説明する。配属方法では現在の配属方法の説明をする｡安定結婚問題のGale-Shapleyのアルゴリズムは安定結婚問題の節を参照して欲しい｡
文教大学で開設されるゼミの数は15個ある。バランスよく学生が異なるゼミに希望を出せばほとんどの人が第1希望に所属できる。しかし実際は人気のあるゼミ、そうではないゼミがあり、希望者が定員の2倍以上のゼミや、反対に1名の希望者もいないゼミなどがある。前者のゼミは希望者の半数以上が第1希望に所属できない。このようにゼミの人気は第1希望で不合格となってしまう学生の数に関係している。そこで学生のゼミに対する順位付けのデータ作成に当たって、より現実的なデータにする為にゼミの人気を表そうと考えた｡
アルゴリズムを大まかに説明すると、各ゼミごとに乱数を発生させ割り当てる。その乱数の大きい順にゼミを並べ替える、それをすべての学生に対して行う｡その乱数の大きいゼミの順が学生のゼミに対する順位という方法だ｡
規模の小さな例で詳しくアルゴリズムを示す。ゼミa,b,cがあるとする。ゼミはb,c,aの順番で人気がある。ここで人気のあるゼミbの乱数の幅を[0,10]とし、次に人気のゼミcは乱数の幅を[0,5]とし、次のゼミaは[0,3]と指定する。そして各学生ごとに乱数を発生させ、降順に並べ替えるという方法である｡このようにすればゼミbの乱数が大きくなる可能性が大きく、ゼミaの乱数が小さくなる可能性が大きい｡（図4.1参照）
図4.1.人気のあるゼミb、ないゼミaの作成方法
|
学生順位付けアルゴリズム 入力 学生集合、ゼミ集合、各ゼミの乱数の範囲、 出力 学生のゼミへの順位付け step1 各学生に対して以下の作業を繰り返す。
step3 キーの大きな順番に並べ替えたゼミの順序が学生の選好順序 |
文教大学経営情報学科の1学年の学生数は約180名である。そのすべてをすべての先生が把握するのはほぼ不可能である。よって、実際にはゼミの学生に対する順位付けは不可能である。そこで、いくつかの事実を列挙して、アルゴリズム化を図る。
先生が学生に対し、判定の基準として考えられるのは成績、授業態度などが考えられる（感情も一因かれないがここでは考慮しない）。成績は総合の成績よりも分野に関する成績で参照されるだろう。例えば、ORゼミの選考の時に、ある学生の経営や会計の分野の成績が良くなくてもORの分野の成績がよければその学生はORゼミに合格しても不自然ではない。このように学生に対する順位付けのデータを作る際、一人の学生に人気が集中するのではなく、ゼミの分野ごとに好みの学生が散らばるように設定したいと考えた｡
ゼミの学生に対する順位付けのデータ作成の基本的なアルゴリズムは学生のゼミに対する順位付けと変わらない｡そのアルゴリズムを規模の小さな例で説明する｡学生1,2,...,10と分野a,bがあるとする｡分野aの成績の順を学生1,2,...,10とする｡分野bの成績の順を学生10,9,...,1とする。成績から選考するなら分野aのゼミは大体1,2,..,10の順番、分野bのゼミは大体10,9,...,1の順番で順位付けをするはずである。そこで乱数割り当てにあたって分野aの乱数の幅を学生1がいちばん大きく割り当てて、その次に大きいのが学生,2,..いちばん小さいのが学生10の順番とし、割り当てた値の大きい順をゼミの好きな順番とすれば大体1,2,...10の順番となる。同様に分野bのゼミは1がいちばん小さく、10がいちばん大きく乱数の幅を与えればよい。（表4.1参照）
表4.1 乱数の範囲を示す表
| 学生 1,2...10 |
学生11,12..,20 |
・・・ |
学生90,91,...100 | |
| 分野a | [0,10] | [0,9] | ・・・ | [0,1] |
| 分野b | [0,1] | [0,2] | ・・・ | [0,10] |
分野aのゼミi,jは分野aの行の乱数の割り当て方で学生に値を割り当てる
分野aのゼミm,nは分野bの行の乱数の割り当て方で学生に値を割り当てる
値を割り当てた後は学生のゼミに対する順位付けと同様に行う
安定結婚問題での標準形においては順位付けは全順序である事を仮定している[4]。しかし、ゼミの学生に対する順位付けはすべての学生を一列に並べるような全順序でつけるよりも、成績5のどの学生も同じくらいの気持ちで来て欲しい、という風に同順位を許す方が自然である(図4.2参照）。安定結婚問題を拡張した問題で順位付けに同順位を許す場合というのがあり、ここではそれを利用する｡その中でも弱安定マッチングの定義で拡張したい｡そこでまずは弱安定マッチングの定義を説明し、その後にゼミの学生に対する順位付けを導く｡
図4.2.同じ成績の学生はランダムに順位付け
それぞれの好きな順番において自分のパートナーと同順位の相手がどのようなパートナーを持つかは全く気にならないと仮定した場合、以下のようなブロッキングペアの定義ができる。
(h',d')はMにおけるブロッキングペア
このブロッキングペアの存在しないマッチングを弱安定マッチングと呼ぶ。
弱安定マッチングを見つける方法は同順位の要素たちを適当に順序を与え、安定結婚問題の標準形に直し、Gale-Shapleyのアルゴリズムを適用すればよい。この”適当”には任意性が含まれているので男性（女性）最良安定マッチングは複数存在する｡
これより強い安定の超安定マッチング、強安定マッチングというのがあるが、これを安定として定義すると安定マッチングが存在することが保証されない。そこでここでは弱安定マッチングを採用する事にする｡
|
ゼミの順位付けアルゴリズム ゼミの順位付けにおいて弱安定マッチングを満たす為にはまず、ゼミの分野を参照し、学生をその分野の成績を基に5,4,3,2,1の5つのグループに分ける、さらにその中で適当に学生に順位付けをしていけばよい｡（No11参照） 入力 学生集合、、ゼミ集合、ゼミの分野、各学生の乱数の範囲 出力 ゼミの学生に対する順位付け step0 各ゼミについて順位を持ってない（初期設定）。 step1 各ゼミについてゼミの分野を、そして乱数の範囲を学生に割り当てる。 step2 各ゼミについて以下の作業を繰り返す。
step3 各ゼミについて整列した順番が学生に対する好きな順番。 |
現在の配属方法をアルゴリズム化するに当たって実際と異なる点は、学生が一番最初にすべてのゼミに対して順位付けができているということである｡
現在の配属方法アルゴリズム入力 学生のゼミに対する選好順序、ゼミの学生に対する選好順序 出力 ゼミの配属 step0 どの学生もどのゼミにも配属されていない。 step1 すべての学生が所属するまで繰り返す。所属したならstep5に進む。 step2 学生は定員に余裕のあるゼミでもっとも最上位にあるゼミに申し込む。 step3 各ゼミにおいて以下の作業を行う。
step4 step1に戻る。 step5 選択されたゼミが、その学生が所属するゼミ。
|
安定結婚問題のGale-Shapleyのアルゴリズムと、前章でアルゴリズム化した現在の配属方法のプログラムを作成し、データをそのプログラムにかけて実験を行った。20通りの人気のパターンを作成し、1つにつき1000回の配属を行ったとするシミュレーションの結果を示し、考察に入る。なおここでは簡単のためゼミの数を15個、学生を150人、定員を10人、ゼミの分野を3つとしている。
人気のあるゼミが一つに集中すると第1希望に所属できない学生は増え、反対に人気のあるゼミ、そうでないゼミの差があまりないときは大体第1希望に所属できる。そこでデータ作成にあたり、ゼミの人気について人気の集中したパターンと人気の分散したパターンを作り、実験を行おうと考えた。人気の分散の方法は学生の集合を3つのグループに分け、（人気集中（強）はグループを作らなかった）それぞれ、3つのパターンにしたがって順位付けを行うようにした（表5.1参照）。
人気の集中したパターンと分散したパターンについてそれぞれ強い人気集中（分散）、弱い人気集中（分散）の2通りのデータを準備した。また、人気のあるゼミそうでないゼミを作成しない完全にランダムのデータの作成しプログラムにかけた｡
表5.1はその人気のパターンを示す｡例えば人気分散（強）の表のもとでのデータ作成方法について、グループ1でゼミを順位付けする学生はゼミ1,...,5に最も所属したく、ゼミ6,...,10には所属したくない、というような順位付けを行うようにする｡集中（強）の時はすべての学生がゼミ1,...,5に最も所属したく、ゼミ11,...,15には所属したくないという順位付けを行うようになる｡このように人気の集中度を変えてデータを作成した｡
表5.1.ゼミの人気の集中具合を4つに分けてデータ作成
人気分散（強）
| ゼミ1,..,.5 | ゼミ6,...,10 | ゼミ11,...,15 | |
| グループ1 | ◎ | × | ○ |
| グループ2 | ○ | ◎ | × |
| グループ3 | × | ○ | ◎ |
人気分散（弱）
| ゼミ1,..,.5 | ゼミ6,...,10 | ゼミ11,...,15 | |
| グループ1 | ◎ | ◎ | × |
| グループ2 | ○ | ◎ | ○ |
| グループ3 | ○ | ○ | ◎ |
人気集中（弱）
| ゼミ1,..,.5 | ゼミ6,...,10 | ゼミ11,...,15 | |
| グループ1 | ◎ | ○ | ○ |
| グループ2 | ◎ | ○ | ○ |
| グループ3 | ○ | ◎ | ○ |
人気集中（強）
| ゼミ1,..,.5 | ゼミ6,...,10 | ゼミ11,...,15 | |
| グループ1 | ◎ | ○ | × |
◎：人気があるゼミ
○：人気が普通のゼミ
×：人気がないゼミ
人気付けに当たってゼミの学生に対する人気付けも同様に行った｡例えば人気分散（強）の分野1において学生番号1,...,50番の学生は最も所属して欲しく、学生番号51,...,100番の学生は所属して欲しくないという事である｡表5.2のように分野を3つに分け、それぞれの分野の学生に対する人気付けのパターンを変えて人気の集中度を変化させた。
表5.2学生の人気の集中具合を4つに分けてデータ作成
人気分散（強）
| 学生1,..,.50 | 学生51,...,100 | 学生101,...,150 | |
| 分野1 | ◎ | × | ○ |
| 分野2 | ○ | ◎ | × |
| 分野3 | × | ○ | ◎ |
人気分散（弱）
| 学生1,..,.50 | 学生51,...,100 | 学生101,...,150 | |
| 分野1 | ◎ | ◎ | × |
| 分野2 | ○ | ◎ | ○ |
| 分野3 | ○ | ○ | ◎ |
人気集中（弱）
| 学生1,..,.50 | 学生51,...,100 | 学生101,...,150 | |
| 分野1 | ◎ | ○ | ○ |
| 分野2 | ◎ | ○ | ○ |
| 分野3 | ○ | ◎ | ○ |
人気集中（強）
| 学生1,..,.50 | 学生51,...,100 | 学生101,...,150 | |
| 分野1 | ◎ | ○ | × |
◎：人気がある学生
○：人気が普通の学生
×：人気がない学生
前章の5.2と5.3でそれぞれ作成したゼミの人気、学生の人気を使ってシミュレーションを行う。学生の人気が集中（強）の時、ゼミの人気との組合せの数は、ゼミの人気集中（強）、集中（弱）、分散（弱）、分散（強）、ランダムの5通りである｡同様に学生の人気が集中（弱）の時も5通りある。つまり、学生の人気付けのパターン4種類と、ゼミの人気付けのパターン5種類を乗じた数、20通りの人気のパターンがある。1つの組合せ（例えば学生の人気が集中（強）とゼミの人気が分散（弱）の組合せ）につき、1000回の配属を行ったとするシミュレーションを行い、学生は何番目に所属したいゼミに所属したのかの統計をとった。
図6.1は現在の配属方法のシミュレーションの結果で、20通りの組合せの結果の平均値をグラフで表したものである。また図6.2は安定結婚問題のGale-Shapleyの配属方法のシミュレーションの結果である。現在の配属方法、安定結婚問題の配属方法のどちらの配属方法のどの人気の集中パターンも、第１希望に所属できる学生の数が最も多く、第15希望に向かうにしたがってだんだんと人数が減少していく右下がりのグラフである｡またどちらの結果も、あるゼミに人気が集中していると第１希望に所属できる学生の人数は少なく、人気にばらつきがあると第１希望に所属できる学生が多くなっている｡特に現在の配属方法においてゼミの人気がランダムの時、第１希望に所属できる学生がほとんどである事がわかる｡反対に安定結婚問題においてゼミの人気が集中（強）の時、第１希望に所属できる学生は20%に満たない。（総計は150000人）
図6.1
現在の配属方法のゼミ配属シミュレーション
図6.2 安定結婚問題のGale-Shapleyのゼミ配属シミュレーション
図6.3は図6.1の現在の配属方法の結果の平均、図6.2の安定結婚問題の配属方法の結果の平均値をグラフにしたものである｡安定結婚問題よりも現在の配属方法の方が第１希望に所属できる人数が多い事が分かる｡図6.4と図6.5は図6.3の割合を円グラフで示したものだが、図6.5の現在の配属方法では第１希望に所属できる人数が60%を越す｡図6.4は安定結婚問題の配属方法で、第１希望に所属できる学生は30%代だった。
図6.3 図6.2の安定結婚問題の結果、図6.1の現在の配属方法の結果の平均の比較
図6.4 安定結婚問題での配属希望順位の割合 図6.5 現在の配属での配属希望順位の割合
前節と反対に、ゼミから見て所属した学生はどのくらい好ましいのかという統計をとった。ゼミが学生に対し、1番から150番まで順位付けを行っていたとして、1番から30番まで、 31番から60番まで、 61番から90番まで、91番から120番まで 121番から150番までの5つのランクに分けて統計をとった｡図6.6は現在の配属方法で行った場合、図6.7は安定結婚問題のGale-Shapleyの配属方法で行った場合の結果である。どちらの配属方法もゼミの人気に散らばりがある場合のほうが最も高いランクの学生の人数が最も多く、人気が集中した場合が最も少なくなっている｡図6.8は安定結婚問題の配属方法と現在の配属方法のすべてのシミュレーションの結果の平均値をグラフで表したものである。どちらの配属方法も右下がりで、数値もかなり似ている｡図6.9は図6.8の安定結婚問題の数値を割合で示したもの、図6.10は現在の配属方法の数値を割合で示したものである｡90%以上の学生はぞのゼミの60番以内に好ましい事がわかる｡
図6.6 現在の配属方法のゼミ配属シミュレーション
図6.7 安定結婚問題のGale-Shapleyアルゴリズムのゼミ配属シミュレーション
図6.8 図6.6の現在の配属方法の平均値と図6.7の安定結婚問題の平均値のグラフ
図6.9 安定結婚問題でのゼミの学生に対するランクの割合 図6.10 現在の配属方法でのゼミの学生に対するランクの割合
6.1では学生数がゼミ数とゼミの定員数を乗じた数に等しかった｡そのため、すべてのゼミがゼミの定員ピッタリに学生を持ち、最も所属したくないゼミに所属する学生が存在してしまったという事が考えられる｡そこでこの節では定員の数を増やし実験を行った（図6.11参照）｡これによりゼミによって学生の所属する人数が変化する。また、定員を増やす事により第1希望に所属できる学生の人数の割合が増加する事が予測できる｡この実験を行うに当たってゼミ数にゼミの定員を乗じた数を総容量と定義する。文教大学ではこの総容量が学生数の何倍くらいなのかを調べた｡文教大学では大体1学年が180名である。ゼミ数が15個、定員が14人であるので総容量は210である｡このことから、総容量は学生数の大体1から2割増しくらいである事がわかる｡この事実から総容量を学生の1割増しとした場合と、2割増しとした場合の実験を行った｡実験の方法は学生数と総容量が等しい時に行った時と同じように20通りの組合せ、1つの組合せにつき1000回の配属を行うというシミュレーションである｡
図6.10 ゼミの定員を増やした場合、学生a,b,...,k,lを配属した時、予想できる配属の変化
ここでは総容量を学生の1割増とした時、学生は何番目に好ましいゼミに所属できたのかという統計結果を示す｡図6.21は20通りのパターンの平均値をグラフにした｡図6.22は安定結婚問題の配属方法、図6.22は現在の配属方法における学生が所属したゼミの順位の割合である｡どちらの配属方法も総容量と学生数が等しい時よりも第1希望に所属できる学生が増加した｡特に安定結婚問題の配属方法は30%代から60%へと大幅に第1希望に所属できる学生が増加した｡なお、現在の配属方法での最悪順位は15位、安定結婚問題での最悪順位は13位だった｡
図6.21 総容量が学生の1割増しの時の平均値
図6.22 安定結婚問題の配属方法における学生の所属したゼミの順位の割合 図6.23 現在の配属方法における学生の所属したゼミの順位の割合
ここでは総容量を学生の2割増とした時、学生は何番目に好ましいゼミに所属できたのかという統計結果を示す｡図6.24は20通りのパターンの平均値をグラフにした｡図6.25は安定結婚問題の配属方法、図6.26は現在の配属方法における学生が所属したゼミの順位の割合である｡やはり総容量が1割増の時よりも第1希望に所属できる学生が増加した｡安定結婚問題は学生のゼミに対する希望がばらばらであれ第4希望が学生の最悪順位という結果を出した（付録参照）。現在の配属方法は第1希望に所属できる学生の割合が78%とかなり高い数値である｡また現在の配属方法での最悪順位は12位（1/120000の確率）安定結婚問題も12位（1/120000の確率）だった。
図6.24 総容量が学生の1割増しの時の平均値
図6.25 安定結婚問題の配属方法における学生の所属したゼミの順位の割合 図6.26 現在の配属方法における学生の所属したゼミの順位の割合
40000回のシミュレーションの結果から、現在の配属方法は学生が第1希望に所属できる割合が最も多い。その後は第2希望、第3希望と人数が減っていくのではなく、場合によっては第3希望が多かったり、第4希望が多かったりする。ゼミから見た学生の所属状況は学生が選んでその中から好ましい学生を選んでいるという配属方法の割には好ましい学生がほとんどという結果になった｡
安定結婚問題のGale-Shapleyのアルゴリズムでの配属方法も現在の配属方法と同様に第1希望に所属できる割合が最も多く、その後は大体第2希望、第3希望と少なくなっていく。ゼミから見た学生の状況も、現在の配属方法と同様に好ましい学生がほとんどという結果になった｡
また、総容量を増加させれば第1希望に所属できる学生が増加し、さらに低い順位に属する学生の割合が減少した。安定結婚問題において、学生の総容量を学生の1割増しとした時60%、2割増した時68%と学生数と総容量が等しい時と比べ、大幅に増加した｡しかしさらに、現在の配属方法においては、第1希望に所属できる学生の総数の割合は総容量が学生の1割増の時70%、2割増の時78%と非常に高くなっている。 第2希望は安定結婚問題の方が多い。大体安定結婚問題の第1希望と第2希望の割合の和が現在の配属方法の第1希望の割合に等しくなっている｡それ以降に関して観察してみると、図6.21、図6.24からも見てわかるようにどちらの配属方法も同じような割合で所属している。
また図6.9、6.10のグラフから、ゼミにとってはどちらの配属方法も似たような結果になり、どちらの配属方法でもゼミはかまわない、という事が言えそうだ｡どちらの配属方法も所属した学生は、ゼミが60番以内に順位付けした学生が90%を占める｡
以上の事から現在の配属方法の方は第1希望に所属できる学生が多く、それ以降の学生の所属した順位についても安定結婚問題に劣らないことが言え、文教大学のゼミの配属は安定結婚問題の配属方法よりも現在の配属方法で配属したほうが良いという事がわかった｡
安定結婚問題の配属方法は学生最良の配属方法で行った｡つまり、安定結婚問題では学生にとってこれ以上良い配属は出来ない反対にゼミの所属した学生に対するランクは他の安定な配属を行えばよくなっていくだろう。しかし、学生最良が最も好ましい配属の学生の所属する順位は悪くなっていく。
安定結婚問題は安定を制約とするとこにより、学生最良といえどゼミにも不満のないようなという配属を行ってしまい学生にとっては良くない結果に至ったということが考えられる｡本来学生の意見が最優先にすべきゼミ配属に、ゼミの意見も学生と対等に受け入れてしまう安定結婚問題はゼミ配属に向いていない事がわかった｡
今回は配属問題のアプローチとして安定結婚問題を採用した｡その結果、安定結婚問題を拡張した配属は文教大学のゼミ配属には適していない事がわかった。確かに現在の配属方法は安定結婚問題の配属方法よりも良い配属を導くという結果が得られたが、私は現在の配属方法が最も良い配属であるとは考えていない｡
そこで3章で紹介した線形計画でアプローチをしようと考えている｡線形計画でのゼミ配属は実際に採用している大学もあるという事もあり[6]、良い結果が期待できる。では文教大学ではどのようにはどのようにアプローチすればよいかを考える。まず文教大学では現在の配属方法において,、ゼミの教員もゼミ配属に関わっているという事実から学生だけでなくゼミも満足するような配属をしなくてはならない｡配属案を提案するに当たって学生のゼミに所属した時の満足度だけではなく、ゼミの学生に対する満足度を参照するということである。この時、順位を満足度として目的関数を最小化とすれば良い（図8.1参照）。
この時、表8.1、8.2のように満足度を設定すれば同順位も表現できる。ここでいう同順位とは学生（ゼミ）がどちらも同じくらいの気持ちで複数のゼミ（学生）に所属したい（して欲しい）ということである｡例えば表8.1はゼミaは学生1と2は同じくらいどちらにも来て欲しい事を示している｡図8.1は表8.1、8.2から定式化したものである。
表8.1 同順位を許したゼミa,b,cの学生1,2,...,4に対する順位付け
| 学生1 | 学生2 | 学生3 | 学生4 | |
| ゼミa | 1 | 1 | 3 | 3 |
| ゼミb | 2 | 1 | 4 | 2 |
| ゼミc | 3 | 1 | 2 | 4 |
表8.2 同順位を許した学生1,2,...,4のゼミa,b,cに対する順位付け
| ゼミa | ゼミb | ゼミc | |
| 学生1 | 1 | 2 | 3 |
| 学生2 | 1 | 3 | 1 |
| 学生3 | 2 | 1 | 3 |
| 学生4 | 3 | 1 | 1 |
min. //満足度を最小にする（希望順位を満足度とするため）
//ゼミの学生に対する順位付け
1X11+1X12+3X13+3X14
+2X21+1X22+4X23+2X24
+3X31+1X32+2X33+4X34
//学生のゼミに対する順位付け
+1X11+2X21+3X31
+1X12+3X22+1X32
+2X13+1X23+3X33
+3X14+1X24+1X34
s.t. //定員の制約
X11+X12+X13+X14<=ゼミの定員
X21+X22+X23+X24<=ゼミの定員
X31+X32+X33+X34<=ゼミの定員
//学生は必ずひとつのゼミに所属しなくてはならないという制約
X11+X21+X31=1
X12+X22+X32=1
X13+X23+X33=1
X14+X24+X34=1
図8.1 表8.1,8.2から定式化
しかし、このデータを作成する為には現在の配属方法や安定結婚問題で使ったデータとは違うデータを使わなくてはならない｡なぜなら、安定結婚問題は学生のゼミに対する順位付けにおいては同順位のゼミ同士ゼミの学生に対する順位付けは同順位の学生同士を適当に並べるだけで、安定な解が得られた（弱安定で定義している為）からである。つまり現在作成してある学生のゼミに対する（ゼミの学生に対する）データ作成プログラムはゼミaは学生1、2を第1希望としなくても、学生1と2は第1希望だが、学生2を仮に第2希望としようという風にしてデータを作成している。このようにしても安定な解を求めるのに問題はない｡このことから線形計画でのアプローチと現在の配属方法の比較の為にはデータ作成の改良が必要である｡さらに線形計画アプリケーションを使ったシミュレーションの方法を学ばなければならないだろう｡
このようにやるべき事はわかっている。これを実現し現在の配属方法と比較できたならおもしろいのではないか｡
本論文は私だけでは完成させる事はできませんでした。毎回のゼミナールでの4年生のゼミのメンバーから、そしてテーマ発表会、中間発表会では3年生のゼミのメンバーから多くの指摘、アドバイスをいただきました。また、堀田先生には不完全なプログラムを見ていただき、詳細にわたって教えていただきました｡たくさんのアドバイス、ヒントから資料の紹介まで指導教員の根本先生には本当にお世話になりました｡ここに謝意を表します｡ありがとうございました｡
[1] 山本芳嗣・久保幹雄；巡回セールスマン問題への招待；朝倉書店；1997
[2] 山本芳嗣；経営工学概論；http://www.sk.tsukuba.ac.jp/~yamamoto/ ；1999
[3] 根本 俊男；レジュメ；2000
[4] 茨木 俊秀；Cによるアルゴリズムとデータ構造；昭晃堂；1999
[5] 竹田 仁・若林 俊造・浜田 直進；C言語の基礎；日本理工出版会；1993
[6] 今野 浩；数理決定法入門 キャンパスのOR；朝倉書店；1992
以下2つのプログラムは学生のゼミに対する順位付け、ゼミの学生にタする順位付け、現在の配属アルゴリズム、安定結婚問題アルゴリズムの4つのプログラムの組合せからなっている。
現在の配属方法のプログラムは学生のゼミに対する順位付け、ゼミの学生にタする順位付け、現在の配属アルゴリズムのプログラムの組合せ、安定結婚問題の配属方法のプログラムは学生のゼミに対する順位付け、ゼミの学生に対する順位付け、安定結婚問題のアルゴリズムの組合せで作成した｡どちらのプログラムも、総容量が学生数より多いタイプで作成したものを示す｡学生のゼミに対する順位付けとゼミの学生に対する順位付けは表5.1、5.2の中のどれかのパターンにしたがっている。