作業研究中的指派問題可由匈牙利演算法在 O(n³) 時間內精確求解,該演算法會從一個方型成本矩陣的每一列中選出一個儲存格,並且從每一行中選出一個儲存格,使得加總後的成本可證明為最小值。

指派問題是作業研究課程中進入組合最佳化最乾淨的切入點之一。它用來模擬任何你必須指派每位工作者恰好一項任務、每項任務恰好一位工作者,同時最小化總成本、時間或距離的情境。經典的課堂範例包括將承包商指派到專案、將維修小組派遣到故障現場,或將機器指派到生產線。由於成本矩陣是方型且完整的——每位工作者可以承接每項任務,且具有已知的有限成本——因此這個問題是運輸問題的一個特例,其中供給、需求以及供給者的數量都等於任務的數量。匈牙利演算法由 Harold Kuhn 於 1955 年提出,也稱為 Kuhn–Munkres 法,可在多項式時間內回傳該精確最小值。像 Assignment Problem Solver 這樣的瀏覽器實作可以立即從矩陣產生配對與總和,這對於驗證手算結果以及調整小型草稿排程都很有用。

how to solve assignment problem in operational research
作業研究:如何求解指派問題

指派問題作為一個作業研究模型

作業研究將指派問題視為一個二元線性規劃。令 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 矩陣而言,該演算法可在三次方的時間內終止。三層巢狀的迴圈就足夠:一層處理列、一層處理行、再加一層在當前的等價子圖中尋找擴充路徑。由於這個方法是精確且確定性的——自然的列與行順序會在多個指派共享相同總成本時處理平手——同一個矩陣總是會回傳相同的配對與相同的最小總和。關於列與行縮減的逐步操作視圖,請參考指南 以匈牙利法求解指派問題;下方的示範矩陣則聚焦於輸入格式與已驗證的數值結果。

如何輸入成本矩陣並讀取結果

  1. 寫一個以逗號開頭、後接唯一任務名稱的標頭。一個三任務的範例以左上角的空白欄位開始,後接 ",Task A,Task B,Task C",使每個任務佔據一個欄位。
  2. 每列加入一位工作者,並對每項任務提供恰好一個有限成本,保持工作者與任務數量相等。每個資料列的第一欄存放工作者的名稱;後續每一欄存放該工作者-任務配對的單一有限成本。名稱在其所屬那一側必須唯一,且數量必須與任務欄數相符。
  3. 執行匈牙利求解器,檢查每個配對與成本慣例,然後複製精確的最小成本指派。結果會列出每位工作者對應的一項任務、該配對的成本,以及最小總和。將輸出複製為文字,以便貼到報告、比較欄或驗證過的答案卷中。

一個 3×3 的演算範例

考慮三位工作者(W1、W2、W3)與三項任務(A、B、C),其逗號分隔的成本矩陣如下。左上角的空白儲存格是刻意的,用以表示第一列是標頭而非資料列。

工作者任務 A任務 B任務 C
W1314
W2241
W3432

在匈牙利演算法下,最佳配對為 W1 指派到任務 B、W2 指派到任務 A、W3 指派到任務 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 項目,或無限大的成本。更正這些輸入通常就足以重新求得精確最小值,並確認你的手算結果。

延伸閱讀:如何以動態規劃求解背包問題。