できるだけ希望順位が高くなるように講座編制をしたい

質問

１００人を対象に５講座開講します。１講座の最大は２５人，受講者にはあらかじめ１～５希望まで順位を付けてもらっています。

　これまで，エクセルに希望順位を入力し，並べ替えと人数のカウントを繰り返し，何となく編制してきました。これを数学的に合理的に編制する方法はないでしょうか。

　一人一人の決定講座の希望順位の合計が最小になり，１講座の人数＜＝２５　という制約の中で式を解けばよいのでしょうが，具体的なやり方が分かりません。エクセルのソルバーという機能をうまく使うことはできませんか。高校の教科書で「線形計画法」なるものを習った記憶があるのですが，その応用問題ととらえることはできますか。

　よいアイディアがあったら教えてくださると助かります。

回答No.2

nag0720

＃１です。

第１希望から順に埋めていくのはいいが、抽選では問題があるということでしょうか？

落選者を決める方法として簡単な方法として抽選と書きましたが、抽選でまずければ落選者の決め方を工夫すればいいでしょう。
例えば、第２希望の講座が定員未満だったら優先的に落選対象にするとか。

気になったのは、全員の決定講座の希望順位の和が最小になるように決めると、必ずしも第１希望が優先されるとは限らないことです。
例えば、３人いて、「２人が第１希望、もう一人が第４希望」の場合と「３人とも第２希望」の場合を較べると後者のほうになる可能性もでてきます。
また、「自分は第１希望の講座を落選したのに、その講座に第２希望で受けている人がいる」ということもありえます。これは受講者から見たらあまり気分のいいものではないでしょう。

そう考えると、やはり第１希望から順に埋めていくのがいいのではないでしょうか。

お礼

なかなか回答がつきませんので，締め切らせていただきます。お答えいただいた方ありがとうございました。

補足

再度のお返事ありがとうございます。
　全員の決定講座の希望順位の和の最小値を探すと御指摘のような問題が起こりますね。御指摘ありがとうございました。

　さて，私がやりたいことは第２希望の講座が定員未満だったら優先的に落選対象になるようにして第１希望から順に埋めていきたいのです。この優先的に落選対象とすることを含めて，並べ替えるなどの作業をしないで自動的に決定するような仕組みをエクセルで表現できないかと考えました。よいアイディアはあるでしょうか。

回答No.1

nag0720

これはソルバーや線形計画にはそぐわないような気がします。
単純に第１希望から順に埋めていけばいいのではないですか。

手順としては、

(1)　全員を第１希望の講座に振り分ける。定員をオーバーした講座は、抽選で落選者を決める。

(2)　落選者全員を第２希望の講座に振り分ける。定員をオーバーした講座は、第２希望者の中から抽選で落選者を決める。（すでに定員に達している講座は必然的に全員が落選となる）

(3)　落選者全員を第３希望の講座に振り分ける。定員をオーバーした講座は、第３希望者の中から抽選で落選者を決める。

というように決めていけば５回目までには全員がどれかの講座に決まるはずです。

補足

早速の御回答ありがとうございました。
　回答者様の方法はこれまでに行ってきた方法と同一ですし，有効な方法の一つだと思います。しかし，抽選という手段は次のような問題があります。

　例えば，ＡＢＣＤと４つの講座が次のような希望状況と仮定します。

Ａ（３０／２５），Ｂ（２５／２５），Ｃ（２０／２５），Ｄ（２０／２５）

　このときＢＣＤを第１希望にした人は決定できます。問題はＡを選んだ人ですが，希望順位が高いものから，ＡＢＣＤと選んだ人と，ＡＣＢＤと選んだ人がいたとします。
　ＡＢＣＤと選んだ人が抽選で落ちた場合，第３希望のＣに回ることになります。ＡＣＢＤを選んだ人が抽選で落ちた場合，第２希望までに収まります。
　つまり，抽選は公平で単純ではありますが，できる限り希望順位が高い講座に収まるように最適化することができません。今回は，できる限り全員の希望順位を高くするという要求を満たしたいのですが，それが可能かどうかを聞いているのです。

　言い換えれば，上記の例の場合は，ＡＢＣＤの人はＡ講座（第１希望）に決定し，ＡＣＢＤの人はＣ講座（第２希望）に決定となる処理です。

　ソルバーを使うと言ったのは，（使い方をよく知らないのですが）全員の決定講座の希望順位の和が最小　各講座の人数＜２５　全員の決定講座を順にＡ～Ｄまで順に入れていけば適する解が見つかるのではないかと考えました。ただし，（講座数×人数）回の計算をしてその中から最小値を探すというのは計算量が膨大になりそうで，よい方法を思い付きませんでした。これが質問の意図です。