2.1. 例題の紹介#
次の例題（割当問題）を解いていくことにします。
例題（割当問題）
ある飲食店の従業員「安藤」「佐藤」「鈴木」「山本」「渡辺」の5人に仕事を割り当てます。 仕事は「接客」「厨房」「レジ打ち」「仕入」「掃除」「仕込み」の6つです。 各人を仕事に割り当てるにはコストがかかり、それは個人・仕事によって決まります。 また、各人はそれぞれの仕事に対して熟練度があり、熟練度が高いほどコストがかかる傾向があります。 以下は熟練度とコストをまとめたものです。
熟練度 |
安藤 |
佐藤 |
鈴木 |
山本 |
渡辺 |
|---|---|---|---|---|---|
接客 |
-1 |
3 |
-2 |
3 |
-4 |
厨房 |
5 |
-2 |
3 |
-4 |
5 |
レジ打ち |
0 |
3 |
-2 |
3 |
-1 |
仕入 |
-3 |
-1 |
1 |
1 |
2 |
掃除 |
2 |
-2 |
2 |
-3 |
4 |
仕込み |
5 |
-2 |
0 |
1 |
5 |
コスト |
安藤 |
佐藤 |
鈴木 |
山本 |
渡辺 |
|---|---|---|---|---|---|
接客 |
570 |
1400 |
520 |
1410 |
450 |
厨房 |
1800 |
1000 |
1700 |
1050 |
2300 |
レジ打ち |
800 |
1500 |
500 |
1500 |
600 |
仕入 |
500 |
600 |
1000 |
1000 |
1200 |
掃除 |
1200 |
500 |
1200 |
500 |
1300 |
仕込み |
1500 |
1000 |
1200 |
1200 |
1500 |
また、割り当てる仕事を決定する際には以下の点を守らなくてはいけません。
各人に割り振る仕事は最大で 3 つまでとする。
「接客」「厨房」「レジ打ち」「掃除」「仕込み」は 2 人を割り当てる。
「仕入」は 1 人を割り当てる。
「接客」と「厨房」は別の人が担当する。
各仕事について、担当する人の熟練度の和を、その仕事のクオリティとする。
「接客」「厨房」のクオリティは 2 以上にする。
「レジ打ち」「仕入」「掃除」「仕込み」のクオリティは 0 以上にする。
このとき、コストの合計を最小にするような割り当て方を求めてください。