割当問題（ハンガリアン法）とは？
割当問題（ハンガリアン法）とは、n人の作業者にn個の仕事を1対1で割り当て、総コスト（または総所要時間）を最小にする最適化問題。コスト行列の各行・各列から最小値を引き、0要素を最少本数の線で覆う操作を繰り返すハンガリアン法で厳密解が得られる。要員配置や機械への作業割当の題材で出る。
わりあてもんだい（はんがりあんほう）
割当問題（ハンガリアン法）の意味
n人の作業者にn個の仕事を1対1で割り当て、総コスト（または総所要時間）を最小にする最適化問題。コスト行列の各行・各列から最小値を引き、0要素を最少本数の線で覆う操作を繰り返すハンガリアン法で厳密解が得られる。要員配置や機械への作業割当の題材で出る。
割当問題（ハンガリアン法）の具体例
3人の技術者と3件の案件について、経験差による所要日数の行列を作る。各人の得意案件だけを見て貪欲に割り当てると、最後の1人に不得意案件が残って総日数が伸びる。全体最小を求めると、個々には最速でない割当が最適になることがある。
割当問題（ハンガリアン法）は試験でどう引っ掛けられる？
「各人が自分の最短時間の仕事を選べば全体最適」という局所最適の誤りが典型。行・列の数が異なる場合はダミー行・列（コスト0）を追加して正方行列にする。最大化問題は符号を反転するか最大値から引いて最小化に変換する。
割当問題（ハンガリアン法）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。