欢迎来到运输问题！
你有没有想过像 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\)）。
重点总结：线性规划只是我们一直在使用的表格的“数学语言”版。行是供应约束，列是需求约束，而格子内的成本则构成了目标函数。
最后的鼓励：运输问题可能会让你觉得算术量很大，但步骤永远是一样的。只要练习一个完整的周期——从西北角法到最终的最优解——你就会发现这一切是如何串联起来的！