歡迎來到分配問題！
你有沒有想過，快遞公司如何決定哪位司機應該走哪條路線以節省最多的燃油？或者運動教練如何分配球員位置以獲得最佳賽果？這正是分配問題（Allocation Problems / Assignment Problems）的核心！在決策數學 2（Decision Mathematics 2）的這一章中，我們將學習如何使用一種名為匈牙利演算法（Hungarian Algorithm）的巧妙方法，每次都能精準地做出這些決定。如果一開始覺得步驟很多，別擔心；只要掌握了節奏，它就像跟著食譜做菜一樣簡單！
1. 什麼是分配問題？
分配問題涉及將一組「工作者」分配給一組同樣數量的「任務」，目標是最小化總成本（或最大化總利潤）。
核心規則：每位工作者必須且只能分配到一個任務，且每個任務必須由一位工作者完成。這稱為一對一匹配（one-to-one matching）。
我們使用成本矩陣（cost matrix）來表示這些問題，其中矩陣內的數字代表特定工作者完成特定任務的成本。
小知識：分配問題實際上是你在上一章學到的運輸問題的一個特殊簡化版本。運輸問題處理的是「多對多」，而分配問題則嚴格要求「一對一」！
重點總結：
分配問題旨在找出兩組對象之間最高效的一對一配對，通常以方陣形式表示。
2. 匈牙利演算法（成本最小化）
匈牙利演算法是尋找成本最低分配的「黃金標準」。它的原理是透過簡化矩陣，直到最佳選擇以零的形式呈現出來。
步驟流程：
步驟 1：列簡化（Row Reduction）
查看每一列，找出該列中的最小數字，並從該列的所有數字中減去它。目標是確保每一列至少有一個零。
步驟 2：行簡化（Column Reduction）
現在查看新矩陣的每一行（欄）。找出該行中的最小數字，並從該行的所有數字中減去它。現在，每一列和每一行都應該至少有一個零。
步驟 3：覆蓋零點（Cover the Zeros）
嘗試使用最少數量的水平線和垂直線覆蓋矩陣中的所有零。
記憶小技巧：想像這就像玩踩地雷——你希望用最少的「膠帶」來遮住每一個零。
步驟 4：是否為最佳解？
計算你的線條數量。
- 如果線條數量 = 矩陣階數（例如 3x3 矩陣用了 3 條線），代表你已經找到最佳解！直接跳到步驟 6。
- 如果線條數量少於矩陣階數，你需要對矩陣進行「增廣」（步驟 5）。
步驟 5：增廣矩陣（Augmenting the Matrix）
這是學生最常覺得棘手的部分，我們慢慢來：
1. 找出最小的未被覆蓋數字（設為 \(e\)）。
2. 從所有未被覆蓋的數字中減去 \(e\)。
3. 在所有兩條線相交的位置（交點）加上 \(e\)。
4. 只被一條線覆蓋的數字保持不變。
5. 回到步驟 3，嘗試重新覆蓋零點。
步驟 6：分配（Assigning）
尋找在該列或該行中唯一的零，將該工作者分配給該任務。劃掉該行和該列，重複此過程直到所有人都完成匹配。
快速回顧：增廣矩陣的「3 條法則」
- 未被覆蓋？ 減去。
- 交點？ 加上。
- 被一條線覆蓋？ 保持不變。
3. 處理「不對稱」問題
有時候，現實生活中的問題並非完美的方陣。如果你有 4 個工人但只有 3 個工作，或者某個工人因故無法執行特定任務怎麼辦？
虛擬位置（Dummy Locations）
匈牙利演算法只能在方陣上運作。如果你有一個 3x4 的矩陣，你必須添加一個虛擬（dummy）行或列使其變成 4x4。
- 虛擬行/列中所有單元的成本均設為 0。
- 類比：想像在玩音樂椅遊戲時增加了一張隱形的「鬼椅」。如果有人被分配到鬼椅，這就代表他們在最終結果中沒有分到真實的椅子！
不完整數據（「大 M」法 / Big M Method）
如果某項任務不能分配給特定的工作者（例如他們缺乏相關證照），我們不希望演算法選取該單元。我們給該單元賦予一個無限大的成本（以 \(M\) 或 \(\infty\) 表示）。由於我們的目標是最小化成本，演算法會不惜一切代價避開「M」單元！
常見錯誤：
別忘了步驟 2（行簡化）！許多學生做完列簡化後，看到每一行似乎都有零，就以為可以跳過步驟 3。務必檢查每一行；如果某一行沒有零，你必須減去該行中的最小值。
4. 最大化利潤
如果矩陣中的數字不是「成本」（壞事），而是「利潤」（好事）怎麼辦？匈牙利演算法是為最小化而設計的，所以我們必須用點小技巧，讓它幫我們計算最大化。
如何修改演算法：
1. 找出原始矩陣中最大的數值。
2. 用這個最大值減去矩陣中的每一個數值。
3. 這會創造一個新的「機會成本」矩陣。
4. 對這個新矩陣執行標準的匈牙利演算法以求最小值。這個最小值對應的即是原始問題的最大利潤！
例子：如果你的最高利潤是 £50，而某個單元的利潤是 £10，那麼選取該單元的「損失」就是 £40。透過最小化「損失」，你就是在最大化利潤！
5. 線性規劃公式化（Linear Programming）
你可能會被要求展示如何將分配問題寫成線性規劃（Linear Program, LP）。這只是將我們「一對一」規則書寫下來的一種正式方式。
設 \(x_{ij}\) 為一個變量：
- 若工作者 \(i\) 被分配給任務 \(j\)，\(x_{ij} = 1\)。
- 若工作者 \(i\) 未被分配給任務 \(j\)，\(x_{ij} = 0\)。
目標函數：
最小化 \(C = \sum \sum (c_{ij} \times x_{ij})\)
（意思是：將每個成本乘以其 1 或 0 並加總）。
約束條件：
1. 每位工人只能做一個任務：對於每一列，\(x\) 值的總和必須等於 1。
\(\sum_{j=1}^{n} x_{ij} = 1\) (針對所有 \(i\))
2. 每個任務只能由一位工人完成：對於每一行，\(x\) 值的總和必須等於 1。
\(\sum_{i=1}^{n} x_{ij} = 1\) (針對所有 \(j\))
重點總結：
將問題表述為線性規劃使電腦能夠「讀懂」它。這些約束條件確保了最終分配矩陣中每一列和每一行都恰好有一個「1」，其餘皆為「0」。
最終總結檢查清單
- 矩陣是方陣嗎？ 如果不是，添加一個虛擬行/列（成本設為 0）。
- 這是最大化問題嗎？ 如果是，先用最大值減去所有數值。
- 是否有無法完成的任務？ 這些成本設為 \(M\)。
- 步驟 1：列減法。
- 步驟 2：行減法。
- 步驟 3：用最少線條覆蓋零點。
- 步驟 4：線條數量 < 矩陣階數？進行增廣（未覆蓋處減去，交點加上）。
- 步驟 5：利用零進行最終分配。
繼續練習！你「簡化」的矩陣越多，匈牙利演算法就會變得越自然。你一定沒問題的！