誰がどの地区を回るか
割り当て問題とは、人と仕事を1対1で組み合わせ、費用の合計をいちばん小さくする問題です。配達員と地区を結ぶ場合のように、組み合わせが少なければ、全部試して答えが出ます。
数が増えたときの速い解き方も、このレッスンで見ます。
このレッスンのゴール
メモ
小さな割り当て問題を、全部の組み合わせを試して解くことができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 割り当て問題 | 人と仕事を1対1で結び、費用の合計を最小にする問題 | |
| 費用の表 | 人と仕事の組ごとの費用を並べた表 | |
| 階乗 | 1からその数までを全部かけた数 | 3の階乗は6 |
| 貪欲法 | 目の前でいちばん安いものを順に選ぶ方法 | |
| 輸送問題 | 工場から店へ、運ぶ量と費用を決める問題 |
学生が入力するセルは、このプレビューでは空白です。
費用の表で、割り当てを考える
配達員のA、B、Cの3人が、3つの地区を1つずつ受け持ちます。表の数字は、その人がその地区を回る分数です。
合計の分数がいちばん小さくなる組み合わせを探します。1人が2つの地区を受け持つことはできません。
配達にかかる分数
| 配達員 | 地区0 | 地区1 | 地区2 |
|---|---|---|---|
| A | 9 | 2 | 7 |
| B | 6 | 4 | 3 |
| C | 5 | 8 | 1 |
学生が入力するセルは、このプレビューでは空白です。
全部試せば、必ず最小が見つかる
3人なら、組み合わせは6通りしかありません。全部の合計を出し、いちばん小さいものを選べば、それが最適です。
次の表は、6通りの合計です。最小は9分で、Aが地区1、Bが地区0、Cが地区2を回る組み合わせです。
6通りの合計
| A、B、Cの地区 | 費用の合計 |
|---|---|
| 0、1、2 | 9 + 4 + 1 = 14 |
| 0、2、1 | 9 + 3 + 8 = 20 |
| 1、0、2 | 2 + 6 + 1 = 9 |
| 1、2、0 | 2 + 3 + 5 = 10 |
| 2、0、1 | 7 + 6 + 8 = 21 |
| 2、1、0 | 7 + 4 + 5 = 16 |
学生が入力するセルは、このプレビューでは空白です。
6通りを全部試して最小を出す
docker exec jupyter python3 -c "from itertools import permutations; C = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]; print(min(sum(C[i][p[i]] for i in range(3)) for p in permutations(range(3))))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
組み合わせを全部書き出す
# 3人を3つの地区に割り当てる全部の組み合わせを、費用つきで表示します。
cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
for a in range(3):
for b in range(3):
for c in range(3):
if a != b and a != c and b != c:
total = cost[0][a] + cost[1][b] + cost[2][c]
print(a, b, c, "合計", total)
# cost の数字を変えて、いちばん小さい合計が変わるか確かめてください。
人数が増えると、全部試せなくなる
n人のときの組み合わせは、nの階乗です。3人は6通り、5人は120通り、10人は約363万通りに増えます。
20人になると、約243京通りです。全部試す方法は、人数が少ないときだけの方法です。
人数と組み合わせの数
| 人数 | 組み合わせの数 |
|---|---|
| 3人 | 6 |
| 5人 | 120 |
| 8人 | 40320 |
| 10人 | 3628800 |
| 15人 | 1307674368000 |
学生が入力するセルは、このプレビューでは空白です。
10人と15人の組み合わせの数
docker exec jupyter python3 -c "import math; print(math.factorial(10), math.factorial(15))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
多くの人は、各人が自分にいちばん安い地区を順に取れば、合計も最小になると考えます。この表では、Aが2、Bが3、Cが5で合計10になり、最小の9より大きくなります。目の前の安さだけでは、全体の最小になりません。
速い解き方と、輸送問題
SciPy の linear_sum_assignment は、割り当て問題を速く解きます。20人でも一瞬です。
輸送問題は、工場から店へ運ぶ量を決めます。各工場の供給と、各店の需要を守りながら、費用の合計を最小にします。linprog で解けます。
速い解き方で、同じ答えを出す
docker exec jupyter python3 -c "import numpy as np; from scipy.optimize import linear_sum_assignment as lsa; C = np.array([[9, 2, 7], [6, 4, 3], [5, 8, 1]]); r, c = lsa(C); print(c, C[r, c].sum())"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
輸送問題の例（100円単位）
| 工場と店 | 店P | 店Q | 供給 |
|---|---|---|---|
| 工場A | 4 | 6 | 30箱 |
| 工場B | 5 | 3 | 20箱 |
| 需要 | 25箱 | 25箱 |
学生が入力するセルは、このプレビューでは空白です。
輸送問題を解く
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([4, 6, 5, 3], A_eq=[[1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 0], [0, 1, 0, 1]], b_eq=[30, 20, 25, 25]); print(round(r.fun, 2), r.x)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦: 費用を変える
費用の表の数字を1つ変えて、最小の組み合わせがどう変わるかを調べてください。たとえば、Aの地区1を2から9に変えます。
すると、最小の合計と、組み合わせの両方が変わります。数字を変えるたびに、全部試す方法で確かめましょう。