Recurrence relations

分配（指派）問題簡介

歡迎來到決策數學 2 (Decision Mathematics 2)！我們將從一個在現實生活中非常實用的課題開始：分配問題 (Allocation Problems)。試想你是一間繁忙餐廳的經理。你有四位廚師和四項特定任務（例如：準備食材、燒烤、擺盤和清潔）。有些廚師燒烤速度較快，而另一些則擅長準備食材。你該如何分配，讓每個人正好負責一項任務，並使總耗時降至最低？

這正是分配問題的核心。我們的目標是找出將一群人（或機器）與同等數量的任務進行匹配的「最低成本」方案。如果一開始覺得有點棘手也不用擔心，我們有一套非常可靠的「食譜」，稱為匈牙利演算法 (Hungarian Algorithm)，它能助你每次都順利解決問題！

快速複習：在開始之前，請記住本章通常處理的是方陣 (square matrices)（例如 3x3 或 4x4），因為我們假設人數等於任務數量。

1. 成本矩陣 (Cost Matrix)

你首先會看到的是成本矩陣。這只是一張表格，行代表人員，列代表工作。矩陣內的每個數字都是該人員進行該項工作的「成本」（可以是時間、金錢或距離）。

例子：如果 A 行第 2 列的數值是 15，這意味著人員 A 進行工作 2 需要 15 分鐘。

2. 匈牙利演算法：逐步詳解

匈牙利演算法是一種找出最佳分配方案的系統化方法。你可以把它想像成不斷「減少」成本直到我們找到零值——這些零代表了最佳的匹配組合！

第 1 步：行減少 (Row Reduction)

在每一行中，找出最小的數字。從該行的每個元素中減去這個數字。重要提示：請務必先處理行！

第 2 步：列減少 (Column Reduction)

觀察你新得到的矩陣。在每一列中，找出最小的數字。從該列的每個元素中減去它。（如果某一列已經含有零，則該列保持不變）。

第 3 步：覆蓋零值 (Covering Zeros)

嘗試使用最少數量的橫線和直線來覆蓋矩陣中所有的零。
- 如果線的數量等於矩陣的階數（例如 3x3 矩陣用 3 條線），代表你已經找到最佳解！請跳到第 5 步。
- 如果你使用的線條數量少於矩陣的階數，請進行第 4 步。

第 4 步：擴充矩陣 (Augmenting the Matrix)

如果線條數量不足，我們需要「製造」更多的零：
1. 找出最小的未被覆蓋數字（我們稱之為 \(e\)）。
2. 從所有未被覆蓋的數字中減去 \(e\)。
3. 將 \(e\) 加到任何被兩條線交叉覆蓋的數字上。
4. 只被一條線覆蓋的數字保持不變。
5. 現在，回到第 3 步，再次嘗試覆蓋零值。

第 5 步：最終分配

觀察零的位置。將人員分配給對應零的工作，確保每個人只分配到一項工作，且每項工作只被執行一次。

記憶小撇步：使用口訣「Really Cool Llamas Act」來記住順序：Row (行減少)、Column (列減少)、Lines (線條覆蓋)、Augment (擴充)！

3. 特殊情況：虛擬任務與不可能的任務

有時候現實世界並非完美的方陣。以下是處理方法：

虛擬行或虛擬列 (Dummy Rows or Columns)

如果你有 3 名員工但有 4 項工作怎麼辦？你不能讓工作空著！我們會加入一個虛擬員工 (dummy worker)。
- 建立一個新行（D 行）。
- 為該行的每一項工作分配 0 的成本。
- 像平常一樣解決問題。被分配到「虛擬」工作的人，實際上就是那項沒有被真人負責的工作！

數據不完整（不可能的任務）

如果人員 B 對魚類過敏，不能做「處理魚類」的工作怎麼辦？
- 我們將該特定單元格設為極大成本（通常標記為 \(M\) 或像 999 這樣非常大的數字）。
- 由於演算法會尋找最低成本，它會竭盡所能避開這個「極大」成本！

關鍵總結

虛擬任務用於將矩陣變為方陣。極大成本用於防止不可能的分配。

4. 最大化而非最小化

通常我們想最小化成本或時間。但如果矩陣中的數字是利潤，而我們想要最大化它們呢？

訣竅：要將最大化問題轉化為最小化問題：
1. 找出原始矩陣中最大的數字。
2. 用這個最大數字減去矩陣中的每一個數值。
3. 現在，對這個新矩陣正常使用匈牙利演算法即可！

例子：如果最高利潤是 50，而某單元格是 40，則新值變為 \(50 - 40 = 10\)。求解後，新矩陣中的「最低成本」對應的就是舊矩陣中的「最高利潤」。

避開常見錯誤

- 忘記列減少：許多學生做完行減少後就直接開始畫線。一定要檢查那些列！
- 畫了太多線：永遠尋找覆蓋零值的絕對最少線條數。如果可以用 2 條線覆蓋，就不要用 3 條。
- 交叉點：進行擴充（第 4 步）時，記得將數值加到交叉點上。很容易不小心在那裡也做了減法。

快速複習箱

- 目標：以最低成本將 \(n\) 名員工與 \(n\) 項任務進行匹配。
- 演算法：匈牙利演算法 (行 -> 列 -> 線條 -> 擴充)。
- 非方陣：添加具有零成本的「虛擬」行/列。
- 最大化：先用最大值減去所有數值，再進行計算。

冷知識：匈牙利演算法以兩位匈牙利數學家 Dénes Kőnig 和 Jenő Egerváry 的名字命名，他們在 1931 年奠定了該演算法的基礎！直到今天，它仍然是解決這類問題最有效的方法之一。