割当問題（ハンガリアン法）

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：最小費用流・輸送問題・代表的な組合せ問題　|　関連：線形計画の双対性

要点（BLUF）

割当問題： $n$ 人と $n$ 仕事を 1対1対応させ、総コストを最小にする。輸送問題（最小費用流・輸送問題）で供給・需要がすべて1の特殊例。
ハンガリアン法が $O(n^3)$ で厳密に解く。双対（行・列のポテンシャル）を使う組合せ的アルゴリズム。
制約行列が 全ユニモジュラなので、LP 緩和でも整数（0/1）解が出る ── 整数計画なのに易しい。

概念 ── 1対1で割り当てる

$n$ 人の作業者を $n$ 個の仕事に、各人1仕事・各仕事1人で割り当てる。作業者 $i$ が仕事 $j$ をやるコスト $c_{ij}$ を与え、総コスト最小の割当を探す。0/1 変数 $x_{ij}$ （ $i$ が $j$ を担当なら1）で：

\min \sum_{i,j} c_{ij}\, x_{ij} \quad \text{s.t.}\quad \sum_j x_{ij}=1\ (\forall i),\ \sum_i x_{ij}=1\ (\forall j),\ x_{ij}\in\{0,1\}

これは 二部グラフ（作業者側・仕事側）の 最小コスト完全マッチング。 $n!$ 通りの割当から最良を探す組合せ問題だが、構造の良さで多項式時間で解ける。

ハンガリアン法

双対変数（各行 $u_i$ ・各列 $v_j$ の ポテンシャル）を使う：

各行から行最小を引き、各列から列最小を引く（被約コスト $c_{ij}-u_i-v_j \ge 0$ を作る）。
被約コストが0の辺だけで完全マッチングが作れるか試す。
作れなければ、最少本数の線で0を覆い、ポテンシャルを更新して0を増やす。
完全マッチングが作れたら、それが最適。

被約コスト0の辺は「コストとポテンシャルが釣り合った辺」で、相補性条件（線形計画の双対性）を満たす。ポテンシャル更新は双対問題を改善する操作にあたる。

graph LR
  W1["作業者0"] -->|"2"| J2["仕事1"]
  W2["作業者1"] -->|"6"| J1["仕事0"]
  W3["作業者2"] -->|"1"| J3["仕事2"]

Pythonで解く

scipy の linear_sum_assignment がハンガリアン法（厳密 $O(n^3)$ ）。第3章（代表的な組合せ問題）で整数計画として解いたのと同じ問題を、専用アルゴリズムで解く。

import numpy as np
from scipy.optimize import linear_sum_assignment

cost = np.array([[9, 2, 7],     # 作業者0が仕事0,1,2をやるコスト
                 [6, 4, 3],     # 作業者1
                 [5, 8, 1]])    # 作業者2

row_ind, col_ind = linear_sum_assignment(cost)   # ハンガリアン法
total = cost[row_ind, col_ind].sum()
print(f"最小総コスト = {total}")
print(f"割当 (作業者->仕事) = {list(zip(row_ind.tolist(), col_ind.tolist()))}")

実行結果：

最小総コスト = 9
割当 (作業者->仕事) = [(0, 1), (1, 0), (2, 2)]

作業者0→仕事1（コスト2）、作業者1→仕事0（6）、作業者2→仕事2（1）で総コスト 9。第3章で PuLP の整数計画として解いた結果（代表的な組合せ問題）と完全に一致 ── だが整数計画ソルバーを使わず、専用の多項式アルゴリズムで直接解けた。これが構造（全ユニモジュラ）を知る価値。

数式の直観的意味

割当問題が「整数計画なのに $O(n^3)$ で解ける」のは、二部マッチングの制約行列が 全ユニモジュラだから（最小費用流・輸送問題）。だから LP 緩和（ $x_{ij}\in[0,1]$ ）の頂点がすべて 0/1 になり、整数性を課す必要がない（整数計画とは・LP緩和のギャップ0）。ハンガリアン法は、この LP の 主・双対を同時に解く組合せ的手続き：行・列ポテンシャル（双対変数）を調整しながら、相補性（線形計画の双対性）を満たす被約コスト0の辺でマッチングを構成する。完全マッチングができた瞬間、主実行可能（割当）と双対実行可能（ポテンシャル）が相補性で結ばれ、最適性が証明される。割当問題は、施設配置・スケジューリング・追跡（センサーと物標の対応付け）・経済学のマッチング理論まで広く現れる基礎部品で、輸送問題（最小費用流・輸送問題）→最小費用流という一般化の階段の最下段に位置する。

⚠️ よくある誤解・落とし穴

最大化なら符号反転：利益最大の割当は $-c_{ij}$ で最小化（最適化問題とは）。
人数と仕事数が違うときはダミー行／列（コスト0や大きな値）で正方行列にする。
「貪欲に各行の最小を選ぶ」は最適でない：行ごとに最安を取ると列が衝突する。全体最適には双対調整が要る。
大規模・疎なら最小費用流（最小費用流・輸送問題）の汎用解法や専用実装が速いことも。