跳至主要內容
Lizely

指派問題求解器

使用可重現的匈牙利演算法,在相同數量的工作者與任務間找出精確的最低成本一對一配對。

隱私權:你的檔案不會離開裝置,所有處理均在瀏覽器本機完成。

使用方式

  1. 1.建立以逗號開頭、後接唯一任務名稱的標題列。
  2. 2.每位工作者各占一列,並為每項任務填入一個有限成本;兩方數量必須相同。
  3. 3.執行匈牙利求解器,檢查每個配對和成本含義,再複製精確最低成本指派。

關於指派問題求解器

指派問題求解器會在工作者與任務之間找出最低成本的一對一配對。請貼上方形逗號分隔矩陣:第一列是任務名稱,接下來各列是工作者名稱及其成本。結果會列出每位工作者的任務、每個配對成本與最低總成本;所有運算都在瀏覽器本機完成,指派可複製為文字。

指派問題可視為完整加權二部圖:一側是工作者、機器、代理人或資源,另一側是任務、工作、地點或選擇;每個矩陣格都是一個可能配對的成本。有效解必須從每列與每欄各選一格,因此每位工作者與每項任務都只會出現一次。

本實作使用匈牙利演算法,也稱 Kuhn–Munkres 方法。它維護列與欄的勢能,重複擴增最小約化成本匹配;對 n × n 矩陣以三次時間求得精確最佳解,並以自然列欄順序確定相同成本時的結果。瀏覽器限制為 1×1 至 20×20,能涵蓋課堂題目與小型排程草案。

矩陣左上角必須留空,例如「,任務 A,任務 B,任務 C」,其後每列以唯一工作者名稱開始,並為每項任務提供一個有限數值成本。工作者和任務數量必須相同。成本可為正、零或負,但負成本只有在你的模型確實把它代表為效益時才有意義;本求解器永遠最小化數字總和。

輸出只反映你輸入的成本,未自動納入技能門檻、工作量、團隊關係、公平性、可用性、法律、倫理或不確定性。請將它視為透明的數學基準,而非自動的人員決策;較大或受限制的排程應使用能明確表達全部規則的驗證求解器,並獨立審查最終結果。

方法與來源

剖析具有 1 至 20 個唯一工作者和任務的完整方形矩陣,驗證每個成本有限後,執行原始-對偶匈牙利演算法,並以固定列欄順序處理同分。回傳每位工作者唯一任務、每項任務唯一工作者,以及輸入矩陣的精確最低總成本。

常見問題

這一定會找到最低總成本嗎?
會,前提是矩陣完整、方形、成本有限,並且每位工作者和每項任務皆剛好配對一次。
工作者可以比任務多嗎?
目前版本不行。只有在未配對工作者或任務的成本確實有意義時,才應自行加入虛擬列或欄。
可以改為最大化利潤嗎?
本求解器最小化數值。請以有根據的方式轉換利潤,或使用專為最大化設計的模型。
可以把某個格子設為禁止嗎?
目前不支援空白的禁止格;每個矩陣格都必須包含有限成本。

計算工具 使用指南

查看全部