运输问题

运输问题决定从若干供给地向若干需求地各运多少货，使供需满足且总运输成本最小。它的重点不是寻找一条最短路线，而是同时安排所有流向：同一批货不能被两家客户各算一次。

两个仓库与两个门店

仓库甲有 3 箱、仓库乙有 2 箱；门店一要 2 箱、门店二要 3 箱。每箱的运费如下，数字是同一种货币单位。

发货地	门店一	门店二	供给
甲	2	5	3
乙	4	1	2
需求	2	3	5

记 $x_{i j}$ 为仓库 $i$ 运往门店 $j$ 的箱数。模型是 $min 2 x_{11} + 5 x_{12} + 4 x_{21} + x_{22}$ 并满足 $x_{11} + x_{12} = 3$ 、 $x_{21} + x_{22} = 2$ 、 $x_{11} + x_{21} = 2$ 、 $x_{12} + x_{22} = 3$ ，所有运量非负。总供给与总需求都为 5，所以这四条等式相容，其中有一条可由另外三条推出。

从一条交换链算出最优运量

令 $t = x_{11}$ 。供需等式依次给出 $x_{12} = 3 - t, x_{21} = 2 - t, x_{22} = t, 0 \leq t \leq 2.$ 总费用因而简化成 $2 t + 5 (3 - t) + 4 (2 - t) + t = 23 - 6 t$ 。在允许区间内， $t = 2$ 最便宜，费用为 11。实际运法是甲向门店一运 2 箱、向门店二运 1 箱，乙全部 2 箱运往门店二。

式子里的 $- 6 t$ 有操作上的含义。令 $t$ 增加一箱时，甲到门店一、乙到门店二各增加一箱；甲到门店二、乙到门店一各减少一箱。每个仓库的发货总量和每个门店的收货总量都保持不变，费用每次降低 $5 + 4 - 2 - 1 = 6$ 。直到 $x_{21} = 0$ ，这个交换方向才不能继续走。

一个不依赖枚举的最优性证据

给仓库、门店分别取数 $u_{1} = 0, u_{2} = - 4$ 和 $v_{1} = 2, v_{2} = 5$ 。四条线路都满足 $u_{i} + v_{j} \leq c_{i j}$ ，其中 $c_{i j}$ 是表中运费；例如乙到门店一有 $- 4 + 2 = - 2 \leq 4$ 。因此任何可行运输方案的费用都至少为 $\sum_{i} u_{i} s_{i} + \sum_{j} v_{j} d_{j} = 0 \cdot 3 - 4 \cdot 2 + 2 \cdot 2 + 5 \cdot 3 = 11.$ 理由是把每箱的 $u_{i} + v_{j} \leq c_{i j}$ 乘以 $x_{i j} \geq 0$ 后相加，左边利用供需等式恰好变成上式。前面的运输方案正好达到 11，故全局最优。这里的仓库权重可以为负；它们是证明下界的数学变量，不是“负运费”。

一般供需式与可行性

若仓库编号为 $i = 1, \dots, m$ 、门店编号为 $j = 1, \dots, n$ ，供给为 $s_{i}$ 、需求为 $d_{j}$ 、单位运费为 $c_{i j}$ ，平衡运输问题写成 $min_{x_{i j} \geq 0} \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{i j} x_{i j}, \sum_{j} x_{i j} = s_{i} (i = 1, \dots, m), \sum_{i} x_{i j} = d_{j} (j = 1, \dots, n) .$ 如果每条线路都允许使用、供需都非负且 $\sum_{i} s_{i} = \sum_{j} d_{j} = S > 0$ ，至少存在一个可行方案：令 $x_{i j} = s_{i} d_{j} / S$ 。它通常并不便宜，但逐行求和为 $s_{i}$ 、逐列求和为 $d_{j}$ ，可作为检查模型没有写错的起点。若某些线路禁止通行或有容量限制，总量相等就不再足以保证可行，必须检查各门店的需求能否通过实际可用的线路送达。

模型适用范围

若总供给多于总需求，可以把各仓库约束改为“发货不超过供给”，或加一个表示未运出数量的虚拟目的地；选择哪种写法取决于剩货是否有储存成本。若某线路容量有限，还要加 $x_{i j} \leq U_{i j}$ 。原式允许小数箱；当供给与需求均为整数、只有经典供需约束时，该线性规划总能找到整数最优运输量。对不同货物共用同一路段容量的情形，这个单一商品模型就不够了。人员一对一分配则是运输问题的特殊形式，见指派问题。

参考资料

MIT 18.310 线性规划讲义，含运输问题的模型。
MIT 1.224J Carrier Systems 讲义，讨论运输与线性规划。