运输问题¶

运输问题是一种特殊的线性规划问题，具有如下的数学形式：

物资的产地为$A_i,\; i=1, 2, \dots m$，产量为$a_i$
物资的销地为$B_j,\; j=1, 2, \dots n$，销量为$b_j$
从$i$到$j$的单位运价$c_{ij}$
优化运输安排使得总运价最小

其线性规划形式如下：

\[ \begin{aligned} & \min Z = \sum_{i=1}^m \sum_{i=1}^n c_{ij}x_{ij} \\ s.t. & \left\{ \begin{aligned} & \sum_{i = 1}^m x_{ij} = b_{j} \\ & \sum_{j = 1}^n x_{ij} = a_{i} \\ & x_{ij} \geq 0 \end{aligned} \right . \end{aligned} \]

对偶问题为：

\[ \begin{aligned} & \max W = \sum_{i=1}^m a_iu_i + \sum_{j=1}^n b_jv_j \\ s.t. & \left\{ \begin{aligned} & u_j + v_j \leq c_{ij} \\ & u_i \geq 0 \\ & v_j \geq 0 \\ & i = 1, 2, \dots m \\ & j = 1, 2, \dots n \end{aligned} \right . \end{aligned} \]

如果运输问题的产销平衡，即$\sum a_i = \sum b_j$，则运输问题必有有限最优解。基可行解中基变量的个数为$m + n - 1$

表上作业法¶

表格的通常格式如下：

$2$

计算初始基可行解，即在表格上填入$m + n - 1$个数字
计算表中各空格（非基变量）的检验数，判断当前解是否最优解
若当前解不是最优解，则迭代到下一个基

注意

基变量不能构成闭回路，构成一组闭回路的变量中必然包含至少一个非基变量。

闭回路示意图如下：

$1$

一个闭回路中含有偶数个单元格。

如下使用空格表示$x_{ij} = 0$的单元格，使用 数字格 表示$x_{ij} > 0$的单元格

确定初始基可行解¶

有三种方法用于确定初始基可行解：

最小元素法
西北角法
Vogol法

最小元素法¶

最小元素法优先寻找运价较低的变量作为基变量。如果选取出的$x_{ij}$正分量不包含闭回路，则$\{x_{ij}\}$为基可行解。

西北角法¶

西北角法从左上开始，优先最大化满足左上角的运输需求。如果供给方需求已经满足，则划去供给方所在的行，否则划去需求方所在的列。重复以上过程直到右下角。

Vogol法¶

Vogol法计算各行各列中最小$c_{ij}$与次小$c_{ij}$的差作为罚数，优先安排罚数比较大的产地-销地。选取罚数最大的行或列，并填入最小的$c_{ij}$，然后划去该行或列，重新计算罚数。

Vogol法通常能够得到更优的初始基可行解。

最优性检验¶

闭回路法¶

定理

对于每个空格，都存在一条闭回路：

空格位于该闭回路的拐点上
闭回路的其他拐点是数字格

将从空格出发，偶数单元格的运价和与奇数单元格的运价和之差记为$\lambda_{ij}$，若对于所有空格，都有$\lambda_{ij} \leq 0$，则当前的$\{x_{ij}\}$为最优解。

位势法¶

设$(u_{i}, v_{j})$为对偶问题的可行解，$\{x_{ij}\}$为原问题的可行解。根据互补松弛性，若$x_{ij}(c_{ij} - u_i - v_j) = 0$，则两组解分别为对应问题的最优解。

已知当前一组基可行解$\{x_{ij}\}$：

对于基变量$\{x_{ij}\}$，列出方程$u_i + v_j = c_{ij}$，组合成方程组
该方程组有$m+n$个变量但只有$m + n - 1$个方程，因此有无数解，任选一组解即可
对于非基变量$x_{ij}$，计算$\lambda_{ij} = c_{ij} - u_i - v_j$
若$\lambda _{ij}$全部$\geq 0$，则当前解为最优解
否则转出$(i, j) = \arg\max_{(i, j)} -\lambda_{ij}$，调整该空格所在的闭回路

运输问题的变种¶

两地无连接¶

如果模型中存在两个地点之间不能运输，则可以将两地间的运价设为足够高的正数。

产销不平衡¶

当问题中产量与销量不相等时：

如果产量大于销售量，则添加一个虚拟买方，增加$m$个松弛变量
如果销售量大于产量，则添加一个虚拟卖方，增加$n$个松弛变量

需求范围¶

如果买方的需求在一个范围中，则可以将存在范围需求的买方拆分为两个部分，即必须满足的需求部分与可选满足的需求部分，两部分到卖方的运价相同。同时加入一个虚拟卖方，虚拟卖方到必须满足的虚拟买家的运价为足够大的正数，虚拟卖方到可选满足的虚拟买家的运价为$0$。

供应问题¶

考虑按月生产的卖方与按月产生需求的买方，不允许延期交货。卖方生产的产品当月可以不销售。则该问题可以转化为运输问题。

多维运输问题¶

假设两地之间存在$k$个中间节点$c_k$，从$A$到$B$的所有路径都必须经过节点$C$，求最优运输方案。