割り当て問題とは？

割り当て問題は、古典的な組み合わせ最適化問題です。ワーカーとタスクのセットが与えられ、それぞれに関連するコストがある場合、総コストを最小化する一対一のペアリングを見つけることです。スケジューリング、ロジスティクス、リソース割り当て、オペレーションズリサーチなど、2つのグループを最も効率的な方法でマッチングする必要があるあらゆる状況で自然に現れます。

この問題は、ハンガリアンアルゴリズム（Munkresアルゴリズムとも呼ばれます）で解決されます。これは1950年代に開発された効率的な方法です。すべての順列を評価する必要があるブルートフォースアプローチとは異なり、ハンガリアンアルゴリズムは多項式時間で最適解を見つけるため、中程度の大きさの行列でも実用的です。

ツール説明

各ワーカーを各タスクに割り当てるコストを表すコスト行列を入力し、解くをクリックして最適な割り当てを即座に見つけます。このツールは、総コストを最小化するワーカー・タスクペアをハイライトし、結果を明確なテーブルと最適な総コストとともに表示します。

例

入力行列（3ワーカー × 3タスク）:

タスク1 タスク2 タスク3
ワーカー1 400 150 400
ワーカー2 400 450 600
ワーカー3 300 225 300

最適な割り当て:

ワーカー タスク コスト
ワーカー1 タスク2 150
ワーカー2 タスク1 400
ワーカー3 タスク3 300

総コスト: 850

機能

  • 編集可能な行列 — セルまたは列ヘッダーをクリックして、ワーカー、タスク、コストをテーブル内で直接名前変更できます
  • 設定可能なサイズ — 2×2から8×8までの行列に対応
  • 即座の結果 — ハンガリアンアルゴリズムはブラウザ内で実行され、サーバーへのラウンドトリップはありません

仕組み

このツールは、Munkres（ハンガリアン）アルゴリズムを使用して割り当て問題を最適に解決します。入力からコスト行列を構築し、一連の行と列の削減ステップを適用し、完全な最適割り当てが特定されるまでゼロの最大マッチングを反復的に見つけます。時間計算量は$O(n^3)$です。ここで$n$は行列の次元です。

非正方行列（ワーカー数がタスク数より多い場合またはその逆）の場合、アルゴリズムはすべてのワーカーとすべてのタスクがマッチングされるようにゼロで行列をパディングします。

オプション説明

  • ワーカー数 / 行数 — コスト行列に表示される行数を制御します（2～8）
  • タスク数 / 列数 — コスト行列に表示される列数を制御します（2～8）
  • コスト行列セル — 特定のワーカーを特定のタスクに割り当てるコストを入力します。任意の数値が受け入れられます

制限事項

  • 行列サイズは8×8（64セル）に制限されています
  • アルゴリズムは総コストを最小化します。最大化する場合（例：利益行列の場合）は、値を入力する前に否定してください
  • 数値以外のセル値はゼロとして扱われます