割当問題ソルバー

ハンガリアン法による割当問題の最適解. ハンガリアン法（Kuhn-Munkres）を実装し、作業者と仕事の最適な1対1割当を求め、O(n3)の計算量で総コストを最小化または最大化します。. 割当問題は基本的な組合せ最適化問題です：n人のエージェントとn個のタスクにコスト行列Cが与えられた場合、総コストを最小化する一対一…

ハンガリアン法（Kuhn-Munkres）を実装し、作業者と仕事の最適な1対1割当を求め、O(n3)の計算量で総コストを最小化または最大化します。

割当問題とは？

割当問題は基本的な組合せ最適化問題です：n人のエージェントとn個のタスクにコスト行列Cが与えられた場合、総コストを最小化する一対一の割当を見つけます。人員配置、ジョブショップ配分、車両ルーティングで発生します。

ハンガリアン法（Kuhn-Munkres法、1955年）はO(n³)時間で割当問題を解きます。行と列の減算によりコスト行列を繰り返し縮小し、二部グラフの増加パスで最適割当を見つけます。

矩形行列の場合、コスト0のダミー行または列を追加して正方行列にします。未割当のエージェントやタスクは別途報告されます。

Formula: 最小化 Σ C[i][σ(i)] (すべての i について) 制約条件: σ は置換(1対1対応)であることハンガリー法の手順: 1. 各行の最小値を減算 2. 各列の最小値を減算 3. 最少本数の線でゼロを被覆 4. 行列を調整し、最適になるまで繰り返す

計算例

コスト行列: [[9,2,7],[6,4,3],[5,8,1]]。行の縮約 → [[7,0,5],[3,1,0],[4,7,0]]。列の縮約 → [[4,0,5],[0,1,0],[1,7,0]]。0 のマスで各担当者に作業を 1 つずつ割り当て: 担当者 1→作業 2 (コスト 2)、担当者 2→作業 1 (コスト 6)、担当者 3→作業 3 (コスト 1)。総コスト = 9 — 目につく担当者 2→作業 3、担当者 3→作業 1 の組み合わせ (10) より低くなります。

この計算機を使うタイミング

総加工時間またはコストを最小化するように作業者を機械に割り当てる生産監督者
スキル適合度と工数見積もりに基づいてチームメンバーをタスクに配置するプロジェクトマネージャー
総走行距離を最小化するように配送車両をルートに割り当てる物流コーディネーター
競合や移動距離を最小化するように試験室を講座に割り当てる大学の管理担当者

よくある間違い

コストを一貫性なく入力する — コスト行列のすべての値は同じ単位(金額、時間、距離)で統一しなければなりません。単位が混在すると意味のない割り当てになります
最小化モードと最大化モードの切り替えを忘れる — 利益や選好度(高いほど良い)で割り当てる場合は最大化を、コストや時間(低いほど良い)の場合は最小化を選択してください
1人のエージェントに複数の割り当てがある問題に割当法を使う — ハンガリー法は各エージェントを正確に1つのタスクに割り当てます。エージェントが複数タスクを担当できる場合は別のモデルを使用してください
実行不可能な組み合わせを処理しない — 特定のエージェントとタスクの組み合わせが不可能な場合は、ゼロのまま放置せず、そのコストを非常に大きな数値に設定してください

結果の解釈方法

総コストは大域的最適解を表します — 他のいかなる1対1の割り当ても、これより低い(最大化の場合はこれより高い)合計を達成することはできません
一部の行や列が未割り当てと表示される場合、タスクよりエージェントが多い(またはその逆)状態です — それらのエージェント/タスクは空きのまま残ります
最適な合計値を素朴な割り当て(例: 行1を列1へ)と比較すると、アルゴリズムがどれだけの改善をもたらすかが分かります

よくある質問

割当問題で最大化は可能ですか？

はい。すべてのコストを否定するか、各要素を行列最大値から引いてから最小化問題を解きます。最適割当は同じで、目的関数の符号だけが変わります。

作業者とタスクの数が等しくない場合は？

アルゴリズムはコスト0のダミー行または列で小さい次元を埋めます。解後、ダミーエントリへの割当は未割当の作業者またはタスクを示します。

割当問題は作業者のスキルや稼働可否といった実務上の制約を扱えますか?

基本的な定式化では直接は扱えません。ただし、実行不可能な割り当てのコストを非常に大きな数値(例: 999999)に設定することで、アルゴリズムがそれらを選択しないように実質的に排除できます。複雑な制約には、整数線形計画法のソルバーの利用を検討してください。