人と仕事の最適な割り当てを計算する
何人かに1つずつ仕事を任せるとき、だれにどの仕事を割り当てると、全体の時間や費用がいちばん小さくなるか(点数ならいちばん大きくなるか)を計算します。表に数を入れるだけで、全部の組合せを調べたのと同じ答えが出ます。数学では「割り当て問題」と呼ばれ、ハンガリー法(ハンガリアン法)で解きます。
- 1人が1件ずつ受け持つときの、合計がいちばん良い組合せを出します(50人×50件まで)。
- 「それぞれが得意な仕事を選ぶ」と担当が重なることがあり、「小さいマスから順に決める」でも、いちばん良い組合せになるとは限りません(下の例では、順に決めると120分、最適は90分)。
- 1人に2つの仕事を任せるときは、その人を2行に分けて入れます(「使うときの注意」)。時間帯の重なりや、本人の希望を守る、といった条件は扱いません。
計算結果
いちばん小さいことの確かめ方
計算式と計算の内訳
割り当て問題とは
何人かの人と何件かの仕事があり、1人が1件ずつ受け持つとき、どの組合せにすると全体の合計(時間・費用など)がいちばん小さく、または点数の合計がいちばん大きくなるかを求める問題を「割り当て問題」といいます。作業の担当決め、配達員と配達先、機械と作業、クラスの係決めなど、「1対1で組にする」場面に出てきます。
組合せの数は、人数が増えると急に増えます。4人に4件なら 4×3×2×1 = 24通りですが、10人なら3,628,800通り、20人なら約2.4×1018通りです(人数の階乗)。割り当て問題の古典的な論文も、すべての割り当てを1つずつ調べるのは、ごく少ない人数のとき以外は現実にはできない、と書いています(Munkres, 1957)。
そこで使われるのがハンガリー法(ハンガリアン法)です。1955年に Kuhn が発表した方法で、2人のハンガリーの数学者の研究にあった考え方を使ったことから、この名前が付いています(Kuhn, 1955)。全部の組合せを調べなくても、全部を調べたのと同じ、いちばん良い割り当てが求まります。
計算の例:4人で4つの作業を分ける
次の表は、Aさん〜Dさんの4人が、レジ・品出し・清掃・発注の4つの作業を1つずつ受け持つときに、それぞれかかる時間(分)です。ページを開いたときの入力と同じです。
| 人\作業 | レジ | 品出し | 清掃 | 発注 |
|---|---|---|---|---|
| Aさん | 20 | 30 | 15 | 20 ✓ |
| Bさん | 55 | 45 | 20 ✓ | 50 |
| Cさん | 20 ✓ | 45 | 30 | 45 |
| Dさん | 15 | 30 ✓ | 30 | 50 |
- それぞれがいちばん速い作業を選ぶと、AさんとBさんは清掃、CさんとDさんはレジを選び、重なってしまいます。
- 小さいマスから順に決めると(まず15分のAさん→清掃、次に15分のDさん→レジ…)、残ったBさんとCさんに時間のかかる作業が回り、合計は120分です。
- このツールの答えは ✓ の4マスで、Aさん→発注(20分)、Bさん→清掃(20分)、Cさん→レジ(20分)、Dさん→品出し(30分)、合計90分です。24通りのうちいちばん小さく、ほかに90分になる組合せはありません。
Aさんは自分がいちばん速い清掃(15分)ではなく発注(20分)を受け持ちます。Aさん1人では5分遅くなりますが、そのぶんBさんが清掃に回れるので、全体では短くなります。合計がいちばん小さい割り当ては、一人ひとりにとっていちばん良い割り当てとは限りません。名前の順に「Aさん→レジ、Bさん→品出し…」と割り振った場合は145分で、55分の差があります(「今の割り当てと比べる」で確かめられます)。
いちばん小さな例は2人と2件です。Aさんが仕事1に9、仕事2に2、Bさんが仕事1に3、仕事2に8かかるとき、組み方は「A→仕事1・B→仕事2」(9+8=17)と「A→仕事2・B→仕事1」(2+3=5)の2通りで、交差させたほうが小さくなります。
結果の読み方
- 大きな数字……選んだ組合せの合計です。「割り当てなし」を「残してもよい」にして仕事が残ったときは、残った仕事の分も含みます。
- 表の ✓……入力した表の中で、選ばれたマスに印が付きます。結果の表には、人ごとの担当と数を並べます。
- いちばん大きい組(点数ならいちばん低い組)……合計だけでなく、だれか1人に負担が偏っていないかを見る目安です。
- 同じ合計の別の割り当て……「あり」のときは、表示しているのはそのうちの1つです。どれを選んでも合計は同じなので、本人の希望などほかの事情で選んでかまいません。「残してもよい」では、同じ合計のうち組の数がいちばん多いものを表示し、組を減らして仕事を残しても同じ合計になるときも「あり」と出します。
結果の「いちばん小さいことの確かめ方」を開くと、答えが本当にいちばん小さいことを、全部を調べずに確かめる数が出ます。上の例では、各行(人)から5・10・20・15を、各列(作業)から0・15・10・15を引くと、どのマスも0以上になり、✓ の4マスはちょうど0になります。どんな割り当てでも、合計はこの引いた数の合計の 5+10+20+15+0+15+10+15 = 90 より小さくなりません。✓ の組合せの合計はちょうど90なので、これより小さい割り当てはない、とわかります。
できない組合せ(×)と、人と仕事の数が違うとき
資格や経験の都合で受け持てない組合せは、マスに「×」を入れます。空欄とは区別していて、空欄のままだと入れ忘れとして計算しません。答えに × のマスが入ることはなく、計算のあとにも確かめています。
「できない組合せ(×)あり」の例(上の表で、Cさんはレジと発注ができず、Dさんは発注ができない)では、答えは Aさん→発注・Bさん→清掃・Cさん→品出し・Dさん→レジ の合計100分です。小さいマスから順に決めていくと、Cさんに残るのが × の作業だけになり、全員に割り当てられなくなります。
何人かが受け持てる仕事を合わせても、その人数より少ないときは、全員には割り当てられません。たとえばCさんとDさんがどちらもレジしかできないと、2人に対して仕事が1つしかないので、作れる組は最大3組です。逆に、どの何人を選んでも、その人たちが受け持てる仕事が人数以上あるなら、必ず全員に割り当てられることが知られています(ホールの定理、Hall, 1935)。このツールは、全員に割り当てられないとき、その理由になる人(または仕事)のグループを表示します。
人と仕事の数が違うときは、「割り当てなし」の決め方を選びます。
- 全員を組に……少ないほう(人が少なければ人の全員)を必ず組にします。多いほうの余りは割り当てなしで、合計には何も足しません。
- 残してもよい……仕事が残ったときに1件ごとにかかる費用(点数なら、その仕事を残したときの点数)を入れます。人が余るのは0として数えます。組にするより残したほうが合計がよくなる仕事は残し、同じ合計なら組の数が多いほうを選びます。たとえば上の「CさんとDさんがレジしかできない」場合に、残った仕事は1件60分の残業でこなすとすると、答えはAさん→発注・Bさん→清掃・Dさん→レジ、Cさんは割り当てなしで、品出しを残し、合計は55+60=115分です。
ハンガリー法のしくみと、このツールの計算
ハンガリー法の土台は、人と仕事が同じ数のとき、ある人の行のマス全部から同じ数を引いても、ある仕事の列のマス全部から同じ数を引いても、いちばん良い割り当ては変わらないということです(Munkres, 1957)。どの割り当てでも、どの人もどこかの1マスを使い、どの仕事もだれか1人が受け持つので、引いた数はどの割り当ての合計にも同じだけ効くからです。そこで、マスがマイナスにならないように行と列から数を引いて0のマスを作り、0のマスだけで全員を組にできるまで引く数を調整していきます。0のマスだけで組めたら、それがいちばん良い割り当てです。
人と仕事の数が違うときは、多いほうの側に使われない行や列が出るので、そのまま引くと答えが変わることがあります。たとえば人が1人・仕事が2件で、仕事1が5分・仕事2が6分なら答えは仕事1ですが、仕事2の列から2を引くと4分になり、答えが仕事2に変わります。そのためこのツールは、多い側の行や列から引く数を0以下(点数を大きくするときは0以上)にし、組にならなかった行や列からは引かない形で、同じ確かめをしています。
このツールは同じ考え方を、1人ずつ組を増やし、そのたびに今までの組を組み替える形で計算します。この形の解き方は、n人×n件の割り当て問題を、多くてもnの3乗回の足し算と比較で解けることが示されています(Tomizawa, 1971)。50人×50件では、全部の組合せは約3.0×1064通りありますが、それを数えずに答えが出ます。人と仕事の数が違う長方形の表にも、同じ方法を広げて使えます(Bourgeois と Lassalle, 1971)。
小数はすべて桁をそろえて整数に直してから計算するので、0.1+0.2 のような計算で丸めの誤差が出ません。答えが出たあと、上の「確かめ方」の条件(引いたあとのマスが全部0以上で、選んだマスがちょうど0)を整数で確かめています。
使うときの注意
- 単位をそろえる……「分」と「時間」、「円」と「万円」を1つの表に混ぜると、合計が意味を持ちません。
- 点数の付け方……点数を最大にするときは、点数の差に意味があるように付けてください。1点と2点の差と、4点と5点の差は、計算では同じ重さとして扱われます。「5人から3つの係(点数)」の例では、いちばん点の高い「Cさん→司会」(10点)から決めると合計24点ですが、答えはCさんを会計(9点)に回し、Bさん→司会・Eさん→記録で合計27点です。
- 合計がいちばん良くても、全員が満足するとは限らない……合計を最大にすると、1人の点数だけ低くなることがあります。また、組になる両方の側に希望の順位があり、「今の相手よりお互いを選びたい2人」が残らない組合せ(安定な組合せ)を求めるのは、別の問題です(Gale と Shapley, 1962)。
- 1人に2つ以上の仕事を任せたいとき……同じ人を2行に分け(「Aさん①」「Aさん②」)、同じ数を入れます。「全員を組に」では、分けたあとの行の数が仕事の数以下なら、どの行も必ず組になるので、その人はちょうど2件を受け持ちます(行のほうが多いときは0〜2件)。「2件目は任せなくてもよい(多くて2件)」ときは「残してもよい」にして、残った仕事の費用を入れてください。どちらでも、2つの仕事の時間が重なるかどうかは考えません。
- シフト表づくり……時間帯の重なり、連続勤務、時間帯ごとの必要人数といった条件は扱えません。1つの時間帯の中で、だれをどの持ち場にするかを決める、といった使い方になります。
- 見積もりの誤差……時間や費用の見積もりが少し変わると、答えが変わることがあります。合計の差が小さい組合せがありそうなときは、数を少し変えて確かめてください。
よくある質問
ハンガリアン法(ハンガリー法)とは何ですか?
割り当て問題は、全部の組合せを調べれば解けるのでは?
人と仕事の数が違うときはどうなりますか?
1人に2つ以上の仕事を割り当てたいときは?
シフト表の割り当てにも使えますか?
受け持てない組合せがあるときはどうすればいいですか?
同じ合計になる割り当てが複数あるときは、どれが出ますか?
点数を最大にするとき、どんな点数を入れればいいですか?
関連するツール
計算式と出典
- Kuhn HW. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 1955;2(1-2):83-97. doi:10.1002/nav.3800020109(ハンガリー法の原著)
- Munkres J. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics 1957;5(1):32-38. doi:10.1137/0105003(行・列から同じ数を引いても解は変わらないこと、全部の割り当てを調べる難しさ)
- Tomizawa N. On some techniques useful for solution of transportation network problems. Networks 1971;1(2):173-194. doi:10.1002/net.3230010206(n人×n件をおよそnの3乗の計算で解く方法)
- Bourgeois F, Lassalle JC. An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Communications of the ACM 1971;14(12):802-804. doi:10.1145/362919.362945(長方形の表への拡張)
- Hall P. On Representatives of Subsets. Journal of the London Mathematical Society 1935;s1-10(1):26-30. doi:10.1112/jlms/s1-10.37.26 / Cameron PJ. Hall's marriage theorem. arXiv:2503.23159(2025)(ホールの定理の述べ方と解説)
- Gale D, Shapley LS. College Admissions and the Stability of Marriage. The American Mathematical Monthly 1962;69(1):9-15. doi:10.1080/00029890.1962.11989827(安定な組合せ)
計算は、1人が1件ずつ受け持つ割り当て問題の厳密な解き方(ポテンシャル付きの最短増加路によるハンガリー法)です。入力した数は小数の桁をそろえて整数にし、丸めずに計算します。答えは、行と列の数による最適性の条件を整数で確かめたものだけを表示し、× のマスを使っていないことも確かめています。結果は入力した表の数にもとづく数学上の値で、実際の作業の結果や、人の配置の良し悪しを保証するものではありません。