指派問題將 n 位工作者與 n 項任務配對,以使所選成本的總和最小化,而匈牙利演算法可以在 O(n³) 時間內精確求解任何有限值的方陣。在 Excel 中,通常使用 Solver 增益集來處理這個問題,並為每個儲存格使用一個二元決策變數以及一個乘積和目標函式,而行列限制則強制執行一對一規則。一個名為指派問題求解器的專用網路工具可以在你的瀏覽器中執行相同的匈牙利法,因此你貼上標記好的方陣,即可獲得最小成本配對並複製結果——無需啟用增益集,無需編寫公式,也無需反覆試錯。當矩陣為 10 乘 10 時,可能的配對超過 360 萬個,而對每個配對進行暴力檢查是確保得到最小值的唯一明顯方法——這就是為什麼能在不到一秒內完成同樣工作的演算法會成為標準工具。其結果是精確的而非近似的,會針對你輸入的任何成本回傳經過驗證的最小值。

how to solve assignment problem in excel
如何在 Excel 中求解指派問題

指派問題究竟是什麼

指派問題是最低成本二元匹配問題最乾淨的特殊情況。你有兩個大小相等的集合——可以稱為工作者與任務、機器與工作,或代理人與位置——以及每種可能配對的已知數值成本。目標是從每列中恰好選擇一個儲存格、從每行中也恰好選擇一個儲存格,使所選儲存格的總和盡可能小。

由於每個儲存格可以選擇或不選,所有有效指派的搜尋空間對於 n 乘 n 矩陣為 n!,成長極快。10 乘 10 的問題有超過 360 萬種排列;20 乘 20 的問題約有 2.4 × 10¹⁸ 種。匈牙利演算法(又稱 Kuhn–Munkres 方法)由 Harold Kuhn 於 1955 年設計,能在多項式時間內精確求解,而生產環境求解器中使用的原始對偶版本可在 O(n³) 時間內回傳最佳解。根據 Google OR-Tools 關於指派的文件,相同的數學模型構成了大多數現代指派與最低成本流程式碼的基礎,且對於你所輸入的數字,最佳值可證明為最小。

該模型完全由一個方型成本矩陣描述:列代表工作者,行代表任務,每個儲存格一個成本。標準形式中沒有「禁止」或「缺失」的配對——假設每位工作者都能執行每項任務,成本代表配對之間唯一的差異。這就是 Excel Solver 和瀏覽器工具所實作的模型。

如何在 Excel 中求解指派問題

標準的 Excel 工作流程使用 Solver 增益集,透過檔案 → 選項 → 增益集 → 管理:Excel 增益集 → Solver 增益集 來啟用。載入 Solver 後,你在工作表上設定一個小型線性規劃,讓 Solver 為你找出二元決策。對於任何大小的指派問題,方法都相同;只有儲存格數量會隨之變動。

先佈局成本矩陣。在某個範圍的最上方一列放置不重複的任務名稱,最左側一欄放置不重複的工作者名稱,並在每個儲存格中填入一個有限的數值成本。矩陣必須為方陣:三個工作者對應三個任務,或四個對應四個,絕不能三個對應四個。在相鄰的範圍中,建立一個相同形狀的決策矩陣,並將每個儲存格填入 0。這些儲存格就是你的變數,Solver 會將工作者被指派到該任務的位置翻為 1。

新增一個總成本儲存格,使用 SUMPRODUCT 對成本矩陣與決策矩陣進行計算。這就是 Solver 要最小化的儲存格。然後新增兩個限制條件系列。對於每個工作者列,該列決策儲存格的總和必須恰好等於 1——每個工作者執行一項任務。對於每個任務行,該行決策儲存格的總和必須恰好等於 1——每項任務由一個工作者執行。決策儲存格本身必須為二元,即 0 或 1。選擇 Simplex LP 作為求解方法,然後按一下求解。

如果成本矩陣格式正確,Solver 會回傳一個 0/1 模式,其中每列每行恰好有一個 1,且總成本儲存格顯示最小值。工作者 i 的配對是第 i 列中為 1 的那一行。對於一個具有以下成本矩陣的 3 乘 3 範例:

,T1,T2,T3W1,9,2,7W2,6,4,3W3,5,8,1

Solver 選擇 W1→T2(成本 2)、W2→T1(成本 6)、W3→T3(成本 1),最低總成本為 2 + 6 + 1 = 9。那一個計算 2 + 6 + 1 = 9 就是模型的完整輸出,也是你複製到報告中的答案。

更快的瀏覽器替代方案

為了一次性的指派問題而設定 Solver,需要在公式、二元限制以及行列等式上小心處理。對於一個單純的作業問題或快速的草稿排程,花在設定 Solver 上的時間通常比匈牙利法本身執行的時間更長。指派問題求解器 跳過了所有這些步驟:將標記好的方陣貼到單一文字方塊中,確定性的匈牙利求解器在你的瀏覽器中本地執行,然後你會收到配對、各別成本以及最低總成本,皆以可複製的文字形式回傳。

該網路工具底層使用相同的 Kuhn–Munkres 方法,因此其回傳的最佳解對於你輸入的矩陣而言是精確的最小值,而非近似值。八個獨立的測試矩陣透過列舉所有排列進行驗證,包括 1 乘 1 和 2 乘 2 的邊界情況、一個總成本為 5 的標準 3 乘 3 案例、完全平手的情況,以及一個循環式的 4 乘 4 零成本組態。如果結果與暴力法得到的最小值不符,則測試失敗。

逐步使用指派問題求解器

  1. 撰寫以逗號開頭的標題列。第一個欄位為空,然後列出每個不重複的任務名稱。對於三個任務的範例,第一行是 ,Task A,Task B,Task C。
  2. 每行新增一個工作者。每個後續行以一個不重複的工作者名稱開頭,後面接著每個任務恰好一個有限的數值成本。工作者數量與任務數量必須相符,且每個儲存格都必須填寫。
  3. 執行匈牙利求解器。提交矩陣。求解器會驗證其為方陣、所有名稱不重複,且每個成本都是有限數;格式錯誤的輸入會以可見方式被拒絕。
  4. 檢查每個配對及其成本慣例。結果會列出每個工作者的對應任務、每個配對的個別成本,以及最低總成本。成本可為正、零或負,但求解器永遠最小化數值總和——如果你的資料代表利潤或分數,請有意識地進行轉換,不要假設「最佳」代表最大。
  5. 複製精確的最低成本指派。完整結果以純文字形式提供,因此你可以將其貼到 Excel、報告或排程表中,無需手動重新輸入配對。

匈牙利演算法的白話解釋

該演算法為每列和每行設定兩個數值,稱為勢能,並透過選擇最便宜的可用擴充路徑反覆擴展匹配。在每個步驟中,演算法檢查縮減成本(每個儲存格成本減去列勢能再減去行勢能),並調整勢能,使新的縮減成本為零的邊變為可用。當每列都被匹配時,演算法停止,而列與行的勢能證明了結果是最佳的——沒有其他配對能產生更小的總和。

精確的機制並不是使用該工具所需要的,但這種保證正是該方法有用的原因:三次方的時間界限意味著即使是 20 乘 20 的問題也能在極短的時間內求解,且自然的列與行順序能確定性地解決平手,因此相同的矩陣總是產生相同的配對。如需該方法的詳細逐步說明,請參考指南 以匈牙利法求解指派問題,其中以逐行縮減的方式涵蓋了相同的模型。

成本矩陣模型的限制

矩陣模型涵蓋一個完整的加權二元圖,這只是真實世界排程的其中一個切片。指派問題求解器無法處理禁止配對(空白儲存格)、超過一項任務的工作者容量限制、技能門檻、團隊依賴、公平性、交通時間變動、優先順序、部分可用性或不確定性,除非這些影響已經正確地反映在數字中。允許使用負成本,但在最小化慣例下應真正代表某種益處——直接貼上原始分數並假設「最佳」代表最大將會得到錯誤的答案。

如果你的問題包含上述任何真實世界的複雜因素,正確的做法是使用經過驗證的混合整數、限制規劃或最低成本流求解器,明確地表示所有規則,並在做出任何人事指派決定前進行獨立的人工審查。請將矩陣結果視為透明的數學基準,而非自動產生的人事決定——真實的人事安排還涉及法律、倫理與人文考量,而這些是任何成本矩陣都無法涵蓋的。

Excel Solver 與專用網路工具的比較

面向Excel Solver 工作流程指派問題求解器(網路)
設定時間手動:建立成本矩陣、決策矩陣、SUMPRODUCT、兩個限制系列、二元限制貼上標記好的方陣;無需編寫公式
是否需要增益集需要——必須在 Excel 選項中啟用 Solver不需要——在瀏覽器中本地執行
演算法二元 0/1 模型上的 Simplex LP確定性匈牙利法(Kuhn–Munkres)
最大規模受你的 Solver 版本中的變數與限制數量限制目前瀏覽器版本中為 20 乘 20
輸出留在工作表上的 0/1 決策矩陣配對清單、每對成本、最低總成本,可作為文字複製
驗證由你自己檢查輸入形狀與限制以可見方式拒絕格式錯誤或非方陣的矩陣、重複名稱、空白、NaN、無限成本

對於作業、想要驗證的手動匈牙利計算,或小型機器對工作的分配,網路工具是最短路徑。對於更大或受限制的排程,正確的做法是使用經過驗證的混合整數或限制規劃求解器,明確表示你的所有規則,而非依賴單一成本矩陣。

如果你正在權衡各種選項,如何在 Excel 中計算以年為單位的日期差異 對此有詳細說明。