歡迎來到運輸問題！
你有沒有想過像 Amazon 或大型連鎖超市這樣的企業，是如何在不花費天價運費的情況下，將產品從倉庫運送到你身邊的店鋪呢？這正是我們這一章要解決的問題。我們的目標是在保持總成本最低的前提下，找出將「貨物」從來源地（sources）（生產貨物的地方）運送到目的地（destinations）（需要貨物的地方）的最有效率路徑。
如果剛開始覺得這看起來充滿了「數據」，別擔心。只要掌握了表格的運作規律，這就像在解一個巨大的邏輯拼圖一樣有趣！
快速回顧：黃金法則
在開始任何題目之前，總供應量（Supply）必須等於總需求量（Demand）。如果不相等，我們必須創建一個「虛擬」的來源地或目的地，稱為虛擬點（Dummy），來平衡帳目。
1. 尋找起點：西北角法 (North-West Corner Method)
在決策數學中，我們通常從一個「基本可行解」開始。這是一個很高級的說法，意思就是「一個可行的計劃，即使它還不是最便宜的」。找到這個方案最簡單的方法就是西北角法。
運作方式（步驟說明）：
想像你的數據表格是一張地圖，「西北」格就是指左上角的那一格。
1. 從左上角的格子開始。
2. 查看該行的供應量和該列的需求量。
3. 盡可能地分配最多的數量到該格（取兩者中的較小值）。
4. 從供應量和需求量的總數中扣除這個數值。
5. 如果該行的供應量變為零，則向下移動一格；如果該列的需求量變為零，則向右移動一格。
6. 重複上述步驟，直到到達右下角的格子為止。
記憶小撇步：把它想像成看書，你從左上角開始，一路向右讀，讀完一行就往下跳到下一行！
例子：如果倉庫 A 有 20 個單位，而商店 1 需要 15 個，你就將 15 放入左上角的格子。商店 1 的需求已滿足（需求 = 0），所以你向右移動到商店 2，把倉庫 A 剩下的 5 個單位分發出去。
重點總結：西北角法能給我們一個有效的起始計劃，但它完全忽略了運輸成本！雖然速度快，但通常不是最省錢的選項。
2. 可以變得更好嗎？階石法 (Stepping-Stone Method)
一旦有了起始計劃，我們就可以使用階石法來檢查透過將貨物轉移到其他格子，是否能節省開支。
檢查「影子成本」
為了檢查某個格子是否適合移動貨物，我們需要計算改善指標 (Improvement Indices)。首先，我們要為每一行 (\(u_i\)) 和每一列 (\(v_j\)) 找出數值。
對於每一個已佔用格（occupied cell）（即格子內有數字的），我們使用公式：
\(u_i + v_j = \text{該格的運輸成本}\)
提示：永遠從設 \(u_1 = 0\) 開始。這會為你提供一個計算所有其他 \(u\) 和 \(v\) 值的起點。
計算改善指標 (\(I_{ij}\))
對於每一個空置格（empty cell），我們計算潛在的節省額：
\(I_{ij} = \text{該格成本} - u_i - v_j\)
你知道嗎？如果改善指標是負數，代表將貨物移動到該格子將會降低總成本。我們應該挑選最負的指標來改善我們的方案！
重點總結：如果所有改善指標都大於或等於 0，你就已經找到了最優解（optimal solution）（即最便宜的方案）。如果還有負數，代表還有省錢空間！
3. 進行調整：入選格與退出格
當你找到一個改善指標為負的格子時，它就成了入選格（Entering Cell）。為了將貨物移動到那裡，我們必須完成一條封閉路徑（closed-loop path）。
路徑規則：
- 路徑必須從入選格開始，並回到入選格結束。
- 路徑上所有的其他「轉角」必須是已佔用格。
- 只能進行水平或垂直移動。
- 在路徑的轉角處交替標記 \(+\) 和 \(-\) 符號，從入選格的 \(+\) 開始。
確定退出格 (Exiting Cell)：
查看路徑中標有 \(-\) 符號的格子。找出這些格子中數量最少的一格。這就是你將要移動的數量。數量降為零的那個格子，就是你的退出格。
常見錯誤：學生經常會試圖在路徑中進行對角線移動。請記住：只能水平和垂直移動——就像國際象棋裡的城堡（Rook）一樣！
重點總結：沿著路徑移動貨物，可以在保持供需平衡的同時降低總成本。
4. 處理特殊情況：虛擬點與退化問題
虛擬點 (Dummies)
如果總供應量 \(>\) 總需求量，我們就創建一個虛擬目的地。如果總需求量 \(>\) 總供應量，我們就創建一個虛擬來源地。運送到虛擬點或從虛擬點運出的成本永遠為 0。
退化問題 (Degeneracy)
為了讓階石法有效運作，你必須擁有特定數量的已佔用格。這個數量是：
\(R + C - 1\)
（其中 \(R\) 是行數，\(C\) 是列數）。
如果你的格子數量少於此數，問題就是退化的 (degenerate)。為了修正這個問題，我們在其中一個空置格放入一個極小的虛擬數量（用希臘字母 \(\epsilon\) 表示），來「欺騙」算法，使其正常運作。
快速回顧欄：
- 供應 \(\neq\) 需求？ 使用虛擬點。
- 已佔用格太少？ 出現退化問題；使用 \(\epsilon\)。
- 最優解？ 所有改善指標均 \(\ge 0\)。
5. 表述為線性規劃問題
有時，考試會要求你將運輸問題寫成線性規劃 (LP) 模型。這只是將我們的目標和規則正式化的一種方式。
變量：
設 \(x_{ij}\) 為從來源地 \(i\) 運送到目的地 \(j\) 的貨物數量。
目標函數：
我們希望最小化總成本。公式如下：
\(\text{Minimize } Z = \sum (\text{成本}_{ij} \times x_{ij})\)
約束條件：
1. 供應約束：離開倉庫的總貨物量不能超過其供應量。
例子：\(x_{11} + x_{12} + x_{13} \le \text{供應量}_1\)
2. 需求約束：到達商店的總貨物量必須滿足其需求量。
例子：\(x_{11} + x_{21} + x_{31} = \text{需求量}_1\)
3. 非負約束：你不能運送負數量的貨物！（\(x_{ij} \ge 0\)）。
重點總結：線性規劃只是我們一直在使用的表格的「數學語言」版。行是供應約束，列是需求約束，而格子內的成本則構成了目標函數。
最後的鼓勵：運輸問題可能會讓你覺得算術量很大，但步驟永遠是一樣的。只要練習一個完整的週期——從西北角法到最終的最優解——你就會發現這一切是如何串聯起來的！