作業研究中的指派問題可由匈牙利演算法在 O(n³) 時間內精確求解，該演算法從一個方形的成本矩陣中，從每一列恰好選取一個儲存格、從每一行也恰好選取一個儲存格，使加總成本可證明為最小。
指派問題是作業研究課程中進入組合最佳化最乾淨的入門點之一。它可為任何必須讓每位工作者恰好分配一項工作、每項工作恰好分配一位工作者的情況建模，同時最小化總成本、時間或距離。經典的課堂範例包括將承包商指派給專案、將維修小組指派給故障、或將機器指派給生產線。由於成本矩陣為方形且完整——每位工作者都能承擔每項工作且具有已知的有限成本——此問題是運輸問題的一個特例，其中供給、需求與供給者數量皆等於工作數。匈牙利演算法由 Harold Kuhn 於 1955 年提出，亦稱為 Kuhn–Munkres 法，可在三次方時間內回傳該精確最小值。像 Assignment Problem Solver 這樣的瀏覽器實作能直接從矩陣產生配對與總和，這對於驗算手動計算以及估算小型草擬排程都很實用。
指派問題作為作業研究模型
作業研究將指派問題視為一個二元線性規劃。令 xᵢⱼ 為一個二元變數，當工作者 i 與工作 j 配對時為 1，否則為 0。目標是在所有 (i, j) 上最小化總成本 Σᵢ Σⱼ cᵢⱼ xᵢⱼ，其中 cᵢⱼ 為該特定配對的成本。兩組限制式強制執行一對一規則：每位工作者恰好出現在一個配對中（對每個 i 而言 Σⱼ xᵢⱼ = 1），每項工作恰好由一位工作者承接（對每個 j 而言 Σᵢ xᵢⱼ = 1）。為了使這兩組限制式能與方形矩陣一致，工作者數量必須等於工作數量；否則系統不是過度指派就是留下未被配對的列。
同一個模型也能自然地以圖論問題來閱讀。在一個雙部圖的一側繪出工作者，另一側繪出工作，然後在每位工作者與每項工作之間繪出一條帶權重的邊，其權重即為配對的成本。該矩陣是完全雙部圖 K_{n,n} 的加權鄰接矩陣，而一個可行的指派即是一個完美配對——每個頂點恰好有一條邊與其相連。因此，最小成本的指派即為完全雙部圖中權重最小的完美配對。Google OR-Tools 將這種雙重詮釋描述為在防止兩位工作者承接同一項工作的同時最小化總指派成本，這只是用白話文寫出的同一條件。
為何匈牙利演算法能在多項式時間內求解
暴力法並非指派問題的可行方法。列舉 n 位工作者的所有排列就需要 n! 次比較，這在 n 大於約 10 之後就不可行了。匈牙利演算法以一系列擴充步驟取代列舉，並在多項式時間內收斂。它維持兩個電位陣列，一個用於列、一個用於行，並反覆擴充一個最小化簡成本的配對，直到每個列都被納入。每次迭代不是為一個新的列指派一個空閒的行，就是調整電位使原本不可行的指派變為可行，同時不會提高成本。
Kuhn 於 1955 年的論文證明了此演算法在 n×n 矩陣上可在三次方時間內結束。三層巢狀的迴圈就已足夠：一層掃描列、一層掃描行、一層在當前等價子圖中尋找擴充路徑。由於此方法是精確且確定性的——當多個指派具有相同總成本時，天然的列與行順序會解決平手——同一個矩陣永遠會回傳同一個配對與同一個最小總和。在 Solve Assignment Problem by Hungarian Method 這份指南中，有逐步展示列與行化簡的過程；下方展示的工作矩陣則著重於輸入格式與驗證過的數值結果。
如何輸入成本矩陣並讀取結果
- 撰寫一個以逗號開頭、後接唯一工作名稱的標頭列。一個三項工作的範例從左上角的空欄位開始，接著為 ",Task A,Task B,Task C"，使每項工作佔據一欄。
- 為每位工作者新增一列，並對每項工作提供恰好一個有限成本，確保工作者與工作的數量相等。每筆資料列的第一欄為該工作者的名稱；其後每一欄則為該工作者—工作配對的單一有限成本。名稱在其所屬側必須唯一，且數量必須符合工作欄數。
- 執行匈牙利求解器，檢視每個配對與成本慣例，然後複製精確的最小成本指派。結果會列出每位工作者對應的一項工作、該配對的成本，以及最小總和。將輸出以純文字複製，以便貼入報告、比較欄位或驗算答案表中。
3×3 範例演練
考慮三位工作者（W1、W2、W3）與三項工作（A、B、C），其以逗號分隔的成本矩陣如下。左上角的空格是刻意的，用以表示第一列是標頭而非資料列。
| 工作者 | Task A | Task B | Task C |
|---|---|---|---|
| W1 | 3 | 1 | 4 |
| W2 | 2 | 4 | 1 |
| W3 | 4 | 3 | 2 |
匈牙利演算法下的最佳配對為：W1 指派給 Task B、W2 指派給 Task A、W3 指派給 Task C。公式即為所選儲存格的總和：
總成本 = c(W1, B) + c(W2, A) + c(W3, C) = 1 + 2 + 2 = 5。
為了確認 5 是最小值而不僅是個低值，可與一個替代配對（例如 W1→A、W2→B、W3→C，其結果為 3 + 4 + 2 = 9）相比。三位工作者的其他所有排列所產生的總和皆至少為 5，因此 5 即為此矩陣的精確最小值。瀏覽器工具會回傳相同的配對與總和，因為該演算法是確定性的。
不同求解器方法的比較
匈牙利演算法是此精確模型的經典多項式時間方法，但作業研究依據您實際需要的限制條件，提供了其他框架來描述同一個問題。
| 方法 | 模型範圍 | 主要優點 | 主要限制 |
|---|---|---|---|
| 匈牙利演算法 | 完整方形成本矩陣 | 多項式時間精確解，確定性輸出 | 不允許禁制儲存格、無個別工作者容量 |
| 運輸問題形式 | 同一方形矩陣，視為平衡運輸問題 | 可沿用古典運輸單純形法 | 與匈牙利法具相同的結構性限制 |
| 混合整數線性規劃（MILP） | 任意大小、任意線性限制 | 支援禁制儲存格、容量、每位工作者承接多項工作以及附帶限制 | 需仰賴外部求解器；執行時間依問題實例而定 |
瀏覽器工具實作了此表中的第一列。至於第二列與第三列，通常需將矩陣交給專屬的求解器函式庫，或交由約束規劃、最小成本流等建模套件來處理。
數學模型的邊界
精確最小值僅涵蓋您所輸入的成本。它本身並不會編入技能門檻、工作負荷容量、團隊相依性、公平性、交通時間變化、工作之間的先後順序、每位工作者承接多項工作、工作者可用性或不確定性，除非這些效果已在成本矩陣中正確呈現。負成本可代表利益，但前提是該正負號慣例確實符合您的模型——求解器永遠在最小化數值總和，因此若要最大化利潤，必須刻意轉換問題，或使用最大化模型來求解，而非直接以分數形式貼入。
實際的人力配置決策還涉及法律、倫理與人為因素，這些都無法化約為一個成本矩陣。請將結果視為一個透明的數學基準，而非自動產生的人事決策。對於規模較大或帶有諸多限制的排程——例如超過二十位工作者、有限定配對或有容量限制——請使用經驗證的混合整數、約束規劃或最小成本流求解器，明確地呈現每一條規則，然後在採取行動前獨立檢視最終的指派結果。
以工具驗算手動計算
由於此演算法是確定性的，同一個矩陣永遠會產生同一個配對。這使得 Assignment Problem Solver 在三種常見情境中可作為透明的基準：驗算手動的匈牙利演算過程以核對作業答案、比較兩個略有不同的成本矩陣以觀察哪個假設實際上會改變指派結果，以及在每項成本皆已知的小型草擬排程中將一組機器分配給工作。所有運算皆在瀏覽器本地端執行，因此您可以貼上帶有標籤的矩陣、讀取結果，並以純文字複製出來，無需將資料上傳至遠端服務。
當工具明顯拒絕矩陣時，最常見的原因包括形狀非方形、列或行名稱重複、在應有數字處出現空白、含有 NaN 項目或無窮大成本。修正這些輸入通常足以恢復精確最小值並確認您的手動計算。