歡迎來到分配問題 (Allocation Problems)！
你有沒有想過，快遞公司是如何決定哪個司機應該走哪條路線以節省最多的燃油？或者運動教練如何決定哪位球員應該擔任哪個位置以取得最佳成績？這正是分配問題 (Allocation/Assignment Problems) 的核心所在！
在決策數學 2 (Decision Mathematics 2) 的這一章中，你將學會如何以最高效率將「員工」與「工作」進行配對。雖然起初這些數字看起來很複雜，但這其實是一個非常有邏輯、一步步解開的謎題。如果覺得過程看起來有點機械化，請不用擔心；一旦你掌握了匈牙利演算法 (Hungarian Algorithm) 的節奏，你很快就會成為效率專家！
1. 理解目標
分配問題涉及一系列任務以及執行這些任務的等量人數（或機器）。每個人在執行每項任務時都有不同的「成本」（這可以是時間、金錢或距離）。
目標：我們希望指派剛好一個人負責一項任務，從而使總成本達到最小化。
我們將這些成本表示在一個成本矩陣 (cost matrix) 中。例如，如果我們有 3 名員工 (A, B, C) 和 3 項工作 (1, 2, 3)，矩陣會顯示員工 A 執行工作 1 的「成本」，以此類推。
你知道嗎？這個方法被稱為匈牙利演算法，是因為它是由兩位匈牙利數學家 Dénes Kőnig 和 Jenő Egerváry 所開發的！
重點總結：分配問題的核心在於找到「最佳配對」，以保持總成本盡可能低。
2. 成本矩陣簡化 (Cost Matrix Reduction)
在我們解題之前，需要先將矩陣「簡化」。這可以在不改變最佳指派結果的前提下簡化數字。注意：在 Edexcel 課程大綱中，你必須先進行列簡化 (reduce rows)。
步驟 A：列簡化 (Row Reduction)
1. 逐行查看。
2. 找出該行中最小的數字。
3. 將該行中的所有數字減去這個最小值。
結果：每一行現在至少會有一個零。
步驟 B：行簡化 (Column Reduction)
1. 查看你剛剛產生的新矩陣。
2. 逐列查看。
3. 找出該列中最小的數字。
4. 將該列中的所有數字減去這個最小值。
結果：現在每一行 AND 每一列應該都至少會有一個零。
小撇步：如果在列簡化後某一列已經有零，那麼行簡化不會改變它（因為你減去的是 0）！
重點總結：簡化過程創造了「機會成本」。這些零代表了每位員工或每項工作的最佳選項。
3. 匈牙利演算法
一旦簡化了矩陣，你需要檢查是否僅利用這些零就能做出完美的分配。如果不行，則需要調整矩陣。
「覆蓋線」測試 (Line Cover Test)
畫出最少數量的水平線和垂直線，以覆蓋矩陣中所有的零。
• 如果線的數量等於矩陣的大小 (\( n \))，則可以進行最佳分配。
• 如果線的數量小於 \( n \)，則必須改進矩陣。
改進矩陣（「最小未覆蓋」法則）
如果線的數量不足，請遵循以下步驟：
1. 找出沒有被任何線覆蓋的數值中最小的一個，我們稱之為 \( e \)。
2. 將所有沒有被任何線覆蓋的元素減去 \( e \)。
3. 將所有位於兩條線交叉點上的元素加上 \( e \)。
4. 被單一線覆蓋的元素保持不變。
5. 在這個新矩陣上重複「覆蓋線」測試。
類比：想像這些線是「已滿」的路徑。通過將未覆蓋位置減去 \( e \)，你創造了新的「空閒」路徑（即零）。通過在交叉點加上 \( e \)，你等於是為同時使用了兩條路徑「付出了代價」。
重點總結：我們不斷進行調整，直到覆蓋零所需的線數等於矩陣的行數/列數。
4. 做出最終分配
當線的數量等於 \( n \) 時，你就可以選取你的零了！
逐步配對：
1. 尋找只有一個零的行或列。圈選它，並劃掉該行或該列中的任何其他零。
2. 重複此步驟，直到每位員工都恰好分配到一項工作。
3. 使用原始成本矩陣，將所選配對的成本相加，以計算最終的最小總成本。
常見錯誤：學生經常使用簡化後的矩陣來計算總成本。務必回到題目開頭的原始數字進行計算！
5. 處理特殊情況
現實生活中的情況並不總是完美的正方形。以下是如何處理這些「棘手」數據的方法：
虛擬位置 (Dummy Locations)（行數與列數不等時）
匈牙利演算法僅適用於正方形矩陣（例如，4 名員工對 4 項工作）。
• 如果你有 4 名員工但只有 3 項工作，請增加一個「虛擬工作 (Dummy Job)」列。
• 為虛擬工作設置所有員工的成本為 0。
• 這代表了一名員工處於閒置狀態。
不完整數據（「不可能」的任務）
有時某位員工在生理上無法執行特定任務。在你的矩陣中，用一個非常大的成本替換這個「不可能」的連接，通常用字母 \( M \) 表示。
• 因為 \( M \) 非常大，演算法絕不會將其選為最小成本選項。
重點總結：使用虛擬項使矩陣變為正方形，並使用 \( M \) 來屏蔽特定的指派。
6. 最大化利潤
如果矩陣中的數字不是「成本」而是「利潤」怎麼辦？我們需要的是最高總額，而不是最低總額。
技巧：我們必須將一個最大化問題轉化為最小化問題。
1. 找出整個原始矩陣中最大的數值。
2. 用這個最大值減去矩陣中的每一個數值。
3. 現在，對這個新矩陣正常執行匈牙利演算法。
鼓勵一下：這感覺有點反直覺，對吧？但透過從最大值中減去所有數字，最好的利潤就變成了「0」成本！相信這個過程。
重點總結：要進行最大化，先將所有值從最大值中減去，從而「反轉」矩陣。
快速複習清單
1. 先進行列簡化：減去每行中的最小值。
2. 進行行簡化：減去每列中的最小值。
3. 覆蓋零：使用最少的線。
4. 線 < \( n \)？：將未覆蓋值減去最小的未覆蓋數值；在交叉點加上該數值。
5. 線 = \( n \)？：將員工指派到零的位置。
6. 最終成本：最終總和務必使用原始矩陣的數值。
如果起初覺得棘手也不用擔心——只要練習兩到三個完整的題目，這個模式很快就會變得像直覺一樣自然！