匈牙利法（Hungarian method）是一種組合最佳化演算法，能在三次方的時間（即 $O(n^3)$ 複雜度）內求解指派問題，方法是透過化簡一個方形的成本矩陣，找出 $n$ 個工作者與 $n$ 個任務之間成本最低的一對一配對。此演算法也稱為 Kuhn–Munkres 演算法，其運作方式是操縱列與行的位能，以找出具有最小總權重的完整二部圖匹配。它需要一個完整的、方形的、有限成本的矩陣，其中每個儲存格代表將特定工作者指派給特定任務的數值成本。透過系統性地減去每行與每列中的最小值，演算法會暴露出可被最少數量的線條覆蓋的零成本機會。當覆蓋所有零所需的最少線條數等於矩陣的維度時，即已達到最佳指派。這個確定性的數學模型能確保恰好一位工作者與恰好一項任務配對，在使整體系統成本最小的同時避免資源衝突。
二部圖匹配的數學基礎
指派問題模擬的是一個完整的加權二部圖。在這個圖中，一邊包含工作者、機器、代理或其他資源，另一邊則包含任務、工作、地點或選擇。每個矩陣儲存格代表一種可能配對的成本。一個有效的解會從每一行中恰好選取一個儲存格，並從每一列中也恰好選取一個儲存格。根據 Google OR-Tools — Assignment 的說明，主要目標是在最小化總指派成本的同時，避免兩位工作者指派到同一項任務。
由於匈牙利演算法在處理一個 n 乘 n 的矩陣時採三次方時間執行，相較於以暴力列舉所有可能排列（其複雜度為階乘級成長）的方式，它極為高效。這個數學基準非常通用，但在結構上不同於其他網路最佳化問題。例如，指派問題是在二部圖上配對離散節點，而最小生成樹則是用最低的總邊權重連接一般圖中的所有節點。如果您正在處理更廣泛的網路設計，可以參考我們的指南 如何求解最小生成樹問題 來比較這些最佳化技術。
以 3 乘 3 範例進行手動矩陣化簡
要了解匈牙利法的運作機制，透過一個標準的 3 乘 3 矩陣進行手動計算會很有幫助。在此情境中，我們有三個工作者（W1、W2、W3）與三項任務（任務 A、任務 B、任務 C）。我們的目標是找出能產生絕對最小總成本的配對。
| 工作者 | 任務 A 成本 | 任務 B 成本 | 任務 C 成本 |
|---|---|---|---|
| W1 | 2 | 3 | 3 |
| W2 | 3 | 2 | 3 |
| W3 | 3 | 3 | 1 |
要以手動方式求解，請依照下列傳統的矩陣化簡步驟：
步驟 1：行化簡
找出每一行中的最小值，並將它從該行的每個元素中減去。此步驟會在每一行中至少產生一個零。
- 第 1 行的最小值是 2。將每個儲存格減去 2：$[2-2, 3-2, 3-2] = [0, 1, 1]$
- 第 2 行的最小值是 2。將每個儲存格減去 2：$[3-2, 2-2, 3-2] = [1, 0, 1]$
- 第 3 行的最小值是 1。將每個儲存格減去 1：$[3-1, 3-1, 1-1] = [2, 2, 0]$
步驟 2：列化簡
使用行化簡後的矩陣，找出每一列中的最小值，並將它從該列的每個元素中減去。這能確保每一列也至少包含一個零。
- 第 1 列的值為 $[0, 1, 2]$。最小值是 0。減去 0 後該列保持不變：$[0, 1, 2]$
- 第 2 列的值為 $[1, 0, 2]$。最小值是 0。減去 0 後該列保持不變：$[1, 0, 2]$
- 第 3 列的值為 $[1, 1, 0]$。最小值是 0。減去 0 後該列保持不變：$[1, 1, 0]$
步驟 3：以最少數量的線條覆蓋所有零
嘗試以最少數量的水平線或垂直線來覆蓋化簡後矩陣中的所有零。在我們化簡後的矩陣中，零位於 (W1, 任務 A)、(W2, 任務 B) 與 (W3, 任務 C)。為了覆蓋這三個獨立的零，我們必須恰好畫出三條線（三行或三列）。
由於覆蓋所有零所需的最少線條數 (3) 等於我們矩陣的維度（$n = 3$），我們已經達到最佳狀態。如果線條數小於 3，則必須透過找出最小的未覆蓋元素、將它從所有未覆蓋元素中減去，並將它加到線條交點上的元素，來執行額外的迭代。
步驟 4：決定最佳指派
我們將工作者指派給化簡後矩陣中零成本儲存格所對應的任務：
- W1 被指派到任務 A（原始成本 = 2）
- W2 被指派到任務 B（原始成本 = 2）
- W3 被指派到任務 C（原始成本 = 1）
要找出最小總成本，我們將這些最佳配對的原始值相加：$2 + 2 + 1 = 5$。這符合這個標準 3 乘 3 範例的確定性最小成本基準。
如何在線上求解指派問題
雖然手動化簡對於 3 乘 3 的矩陣很簡單，但較大的矩陣很快就會變得繁瑣且容易產生算術錯誤。在線的 指派問題求解器 能將整個過程自動化。它會解析一個最多 20 個唯一命名的工作者與任務的完整方形矩陣，驗證您的輸入，並套用原始對偶匈牙利演算法，立即回傳精確的最小成本匹配。
- 撰寫以逗號開頭的標頭，後面接著唯一的任務名稱。
- 每個工作者一行，為每項任務填入恰好一個有限成本，並保持工作者與任務數量相等。
- 執行匈牙利求解器，檢查每個配對與成本慣例，然後複製精確的最小成本指派。
舉例來說，要求解我們手動計算的 3 乘 3 問題，您可以在輸入欄位中貼上下列以逗號分隔的矩陣：
,Task A,Task B,Task C W1,2,3,3 W2,3,2,3 W3,3,3,1
此工具完全在您的瀏覽器中執行。它會立即顯示每位工作者被指派的任務、各別配對成本以及總最小成本。您可以將最終的指派表格以純文字形式複製，用於您的報告或作業中。
了解模型假設與限制
要成功地使用匈牙利法，您的資料必須符合此模型的數學假設。下表概述了手動方法與線上求解器功能的比較，突顯了重要的結構性限制。
| 功能或限制 | 手動匈牙利法 | 線上求解器工具 |
|---|---|---|
| 實際矩陣大小上限 | 通常最多 4x4 或 5x5，否後手動錯誤會急劇增加。 | 最多 20x20，輕鬆涵蓋課堂作業與一般排程任務。 |
| 處理位置 | 您的桌面或白板。 | 在本機瀏覽器中執行；不會將資料上傳到伺服器。 |
| 輸入驗證 | 受限於人為監督；容易漏掉重複名稱或缺失的儲存格。 | 會拒絕格式錯誤或非方形的矩陣、重複名稱、空格與 NaN。 |
| 平手解決方式 | 由畫線的人任意決定。 | 使用自然的行與列順序確定性地解決。 |
| 支援的成本類型 | 支援任何實數，但負數會讓手動運算變得複雜。 | 支援正值、零與負值，只要是有限的即可。 |
務必記住的是，此求解器永遠是將數值總和最小化。如果您的資料包含您想要最大化的利潤或分數，您必須在貼入工具之前刻意地進行轉換。例如，您可以從原始矩陣中的最大值減去每個值，將最大化問題轉換為最小化問題。不要貼上原始的利潤分數就假設「最佳」結果自動代表最大的數字。
此外，此實作假設每位工作者都能執行每項任務。空白或禁止的配對並不支援以缺失儲存格的方式處理。如果某個配對在您的真實情境中實際上不可能，您必須為它指派一個極高的虛擬成本（「懲罰成本」），以確保演算法不會選擇它。
最後，此模型所產生的精確最佳解僅涵蓋您輸入的精確成本。它並未考量現實世界的細微差異，例如技能門檻、工作負載容量、團隊相依性、公平性、旅行時間變動、先後順序、每位工作者的多項任務、工作者可用性或不確定性。真實的人事決策往往涉及法律、倫理與人際考量，這些無法簡化為一個成本矩陣。請將數學結果視為一個透明的基準，而非自動、無需審查的人事決策。對於大規模的工業排程或高度受限的作業，您應使用經過驗證的混合整數、限制規劃或最小成本流求解器，明確地表示所有政策規則。