[来自知乎@运筹说]

问题的提出

运输问题 (transportation problem) 已知有 `m` 个产地, 货物的产量为 `(a_1, cdots, a_m)`; 又有 `n` 个销地, 销量为 `(b_1, cdots, b_n)`. 第 `i` 个产地运往第 `j` 个销地的运费为 `c_(i j)` 元/件, 求运输方案使得运费最小 `(a_i, b_j, c_(i j) ge 0)`.

假设我们的方案将 `x_(i j)` 件货物从第 `i` 个产地运往第 `j` 个销地. 显然运输问题是线性规划问题的特例, 可以写成: 最小化 `sum_(i,j) c_(i j) x_(i j)`, 满足 `AA i, j`:
`sum_j c_(i j) = a_i`, `quad sum_i c_(i j) = b_j`, `quad x_(i j) ge 0`. 但由于运输问题的特殊性, 我们有比单纯形法更为简便的求解方法.

根据 `sum a_i = sum b_j`, `sum a_i gt sum b_j` 和 `sum a_i lt sum b_j`, 我们将运输问题分为产销平衡、供大于求、供不应求三种类型.

观察可知运输问题共有 `m n` 个变量, `m n` 个非负约束和 `m+n` 个线性约束. 对于产销平衡问题, 由于总产量等于总销量, 故虽有 `m+n` 个线性约束, 其中线性无关的只有 `m+n-1` 个, 即运输问题系数矩阵的秩为 `m+n-1`.

产销平衡运输问题存在有限最优解.

记 `Q = sum a_i = sum b_j`, 则 `x_(i j) = a_i b_j // Q` 满足所有的约束条件, 为一个可行解. 又目标函数有下界 0, 目标函数不会趋于 `-oo`, 所以产销平衡运输问题存在有限最优解.

运输问题的求解

如上所述, 运输问题是特殊的线性规划问题, 可以用单纯形法求解. 其更简便的算法亦是从单纯形法化出, 思路是一致的:
1. 找出一个基可行解 (非基变量全部取 0, 且满足约束条件的解). 在非退化的情形下, 这个解含有 `m+n-1` 个非零元 (基变量);
2. 对该解进行最优性检验;
3. 若不是最优解, 就进行迭代调整, 最终得到最优解.

确定初始可行解

西北角法

优先安排运价表西北角 (左上角) 的运输业务, 从左上角开始, 尽可能多地安排货物的运输, 即:
1. 令 `x_11 = min(a_1, b_1)`, 同时该行的产量更新为 `a_1 - x_11`, 该列的销量更新为 `b_1 - x_11`.
2. 若 `x_11 = a_1`, 则该行的产量已得到满足, 将该行划去.
3. 若 `x_11 = b_1`, 则该列的销量已得到满足, 将该列划去.
4. 继续从表格剩余部分的左上角处安排运输业务, 直到所有货物运输完毕.

最小元素法

最小元素法是一种贪心策略, 它和西北角法的唯一区别是, 西北角法选择当前剩余表格的左上角安排运输, 而最小元素法选择当前剩余表格运价最低处安排运输, 即 `(i, j) = underset(i,j) "argmin"\ c_(i j)`. 这种贪心策略未必能取到全局最优方案. 有时为了节省一处的花费, 往往在别处增加了花费, 使总体运费增加.

Vogel 法

Vogel 法又称差值法, 首先计算每行/列最低运价和次低运价之差, 称为行罚数/列罚数. 罚数表示在该行/列不选最低运费时所付出的代价. 因此罚数越大, 越应该选择该行/列的最低运费. Vogel 法的思想就是按照最小运价对罚数最大处安排运输:
1. 找出当前剩余表格中罚数最大的行或列.
2. 找出该行/列中运价最低者进行运输.
3. 更新产/销量与罚数.

例题

求下面运输问题的初始可行解. `[ 4, 12, 4, 11, {:|:}, 16; 2, 10, 3, 9, {:|:}, 10; 8, 5, 11, 6, {:|:}, 22; -, -, -, -, +, -; 8, 14, 12, 14, {:|:}, 48; ]`

产量 = 销量 = 48, 该问题是产销平衡的.
1. 最小元素法. 优先安排运价最低处的运输, 将货物数量 `x_(i j)` 用小字写在价格的脚下, 灰色表示该行/列已划去, 不再考虑: `[ grey 4, 12, 4, 11, {:|:}, 16; grey 2_(red 8), 10, 3, 9, {:|:}, red 2; grey 8, 5, 11, 6, {:|:}, 22; -, -, -, -, +, -; red 0, 14, 12, 14, {:|:}, 48; ]` `to [ grey 4, 12, 4, 11, {:|:}, 16; grey(2_8), grey 10, grey 3_(red 2), grey 9, {:|:}, red 0; grey 8, 5, 11, 6, {:|:}, 22; -, -, -, -, +, -; grey 0, 14, red 10, 14, {:|:}, 48; ]` `to [ grey 4, 12, grey 4_(red 10), 11, {:|:}, red 6; grey(2_8), grey 10, grey(3_2), grey 9, {:|:}, grey 0; grey 8, 5, grey 11, 6, {:|:}, 22; -, -, -, -, +, -; grey 0, 14, red 0, 14, {:|:}, 48; ]` `to [ grey 4, grey 12, grey(4_10), 11, {:|:}, 6; grey(2_8), grey 10, grey(3_2), grey 9, {:|:}, grey 0; grey 8, grey 5_(red 14), grey 11, 6, {:|:}, red 8; -, -, -, -, +, -; grey 0, red 0, grey 0, 14, {:|:}, 48; ]` `to [ grey 4, grey 12, grey(4_10), 11, {:|:}, 6; grey(2_8), grey 10, grey(3_2), grey 9, {:|:}, grey 0; grey 8, grey (5_14), grey 11, grey 6_(red 8), {:|:}, red 0; -, -, -, -, +, -; grey 0, grey 0, grey 0, red 6, {:|:}, 48; ]` `to [ grey 4, grey 12, grey(4_10), grey 11_(red 6), {:|:}, red 0; grey(2_8), grey 10, grey(3_2), grey 9, {:|:}, grey 0; grey 8, grey (5_14), grey 11, grey(6_8), {:|:}, grey 0; -, -, -, -, +, -; grey 0, grey 0, grey 0, red 0, {:|:}, 48; ]` 从而求得一个初始可行解: 运输方案表 `[, , 10, 6; 8, , 2, ; , 14, , 8]`.
2. Vogel 法. 首先求得行/列罚数, 写在产量/销量的脚下. `[ 4, 12, 4, 11, {:|:}, 16_0; 2, 10, 3, 9, {:|:}, 10_1; 8, 5, 11, 6, {:|:}, 22_1; -, -, -, -, +, -; 8_2, 14_5, 12_1, 14_3, {:|:}, 48; ]` 选取最大罚数 (用括号标出) 所在的行或列, 按最小运价运输, 然后重新计算罚数: `[ 4, grey 12, 4, 11, {:|:}, 16_0; 2, grey 10, 3, 9, {:|:}, 10_1; 8, grey 5_(red 14), 11, 6, {:|:}, red(8_2); -, -, -, -, +, -; 8_2, red 0_5, 12_1, 14_3, {:|:}, 48; ]` `to [ 4, grey 12, 4, 11, {:|:}, 16_0; 2, grey 10, 3, 9, {:|:}, 10_1; grey 8, grey (5_14), grey 11, grey 6_(red 8), {:|:}, red 0_(grey 1); -, -, -, -, +, -; 8_2, grey (0_5), 12_1, red 6_(red 2), {:|:}, 48; ]` `to [ grey 4, grey 12, 4, 11, {:|:}, 16_(red 7); grey 2_(red 8), grey 10, 3, 9, {:|:}, red(2_6); grey 8, grey (5_14), grey 11, grey (6_8), {:|:}, grey(0_2); -, -, -, -, +, -; red 0_(grey 2), grey (0_5), 12_1, 6_2, {:|:}, 48; ]` `to [ grey 4, grey 12, grey 4_(red 12), 11, {:|:}, red 4_7; grey(2_8), grey 10, grey 3, 9, {:|:}, 2_6; grey 8, grey (5_14), grey 11, grey (6_8), {:|:}, grey(0_2); -, -, -, -, +, -; grey(0_2), grey (0_5), red 0_(grey 1), 6_2, {:|:}, 48; ]` `to [ grey 4, grey 12, grey(4_12), 11, {:|:}, 4_7; grey(2_8), grey 10, grey 3, grey 9_(red 2), {:|:}, red 0_6; grey 8, grey (5_14), grey 11, grey (6_8), {:|:}, grey(0_2); -, -, -, -, +, -; grey(0_2), grey (0_5), grey(0_1), red 4_(grey 2), {:|:}, 48; ]` `to [ grey 4, grey 12, grey(4_12), grey 11_(red 4), {:|:}, red 0_(grey 7); grey(2_8), grey 10, grey 3, grey(9_2), {:|:}, grey(0_6); grey 8, grey (5_14), grey 11, grey (6_8), {:|:}, grey(0_2); -, -, -, -, +, -; grey(0_2), grey (0_5), grey(0_1), red 0_(grey 2), {:|:}, 48; ]` 求得的初始可行解为: 运输方案表 `[ , , 12, 4; 8, , , 2; , 14, , 8]`

最优性检验

求出初始可行解后, 下一步是判断这个解是否最优.

闭回路法

仿照单纯形法的思路,
1. 计算各非基变量 (对应于运输方案表中的空格) 的检验数.
2. 若某空格的检验数为负, 说明将该空格变为基变量将使运费减少, 故当前解尚未达到最优;
3. 反之若所有空格的检验数均非负, 则当前解已经最优.

从上节例题中最小元素法所得的初始可行解 `[, , 10, 6; 8, , 2, ; , 14, , 8]` 出发, 通过具体实例介绍闭回路法.

1. 考虑运输方案表中的空格 `x_11`, 若 `x_11` 增加 1, 为保证货物总量的平衡, `x_21` 需减去 1, 继而引起连锁反应, `x_23` 需加上 1, `x_13` 需减去 1. 整个调整过程在表中体现为一个加减交替、纵横交替的闭合回路 (如下). 除起始点是空格外, 该回路上的任一顶点都填有数字. `[{::}^(red +), , 10^(red -), 6; 8^(red -), , 2^(red +), ; , 14, , 8]`. 按检验数的定义, 非基变量 `x_11` 的检验数就等于该调整方案造成的运费变化量: `sigma_11 = c_11 - c_21 + c_23 - c_13 = 1`. 又如空格 `x_31` 的调整路线为 `[, , 10^(red -), 6^(red +); 8^(red -), , 2^(red +), ; {::}^(red +), 14, , 8^(red -)]`. 检验数为 `sigma_31 = c_31 - c_21 + c_23 - c_13 + c_14 - c_34 = 10`. 将所有检验数用红色填入运输方案表: `[red 1, red 2, 10, 6; 8, red 1, 2, red(-1); red 10, 14, red 12, 8]`. 由于 `sigma_24 = -1 lt 0`, 当前解不是最优解.
2. 考虑按 `x_24` 的调整路线进行调整: `[, , 10^(red +), 6^(red -); 8, , 2^(red -), {::}^(red +); , 14, , 8]`. 路线中标记为 "-" 号的最小数字是 `x_23 = 2`, 这也是允许调整的货物数量上限. 因此我们沿该路线移动 2 件货物, 运输方案表变为: `[, , 12, 4; 8, , , 2; , 14, , 8]`. 重新计算各检验数: `[red 0, red 2, 12, 4; 8, red 2, red 1, 2; red 9, 14, red 12, 8]`. 此时所有检验数非负, 方案已达到最优.

1. 上例最后的检验数 `sigma_11 = 0`, 说明沿该路线进行调整, 运费不变, 这样又可得到不同的最优解. 假如货物的量是无限可分的, 则该问题有无穷多组最优解.
2. 若同时有多个检验数为负, 一般选取其中最小者作为换入变量.

位势法

1. 运用对偶线性规划的知识, 在产销平衡运输问题中, 设 `u_1, cdots, u_m` 是 `m` 个行约束等式的对偶变量 (称为行位势), `v_1, cdots, v_n` 是 `n` 个列约束等式的对偶变量 (称为列位势). 记对偶向量为 `bm Y = (u_1, cdots, u_m, v_1, cdots, v_n)`, 列出原问题的对偶规划: 最大化 `z' = sum_i a_i u_i + sum_j b_j v_j`, 满足 `AA i, j`:
   `u_i + v_j le c_(i j)`, `quad u_i, v_j` 符号不限.
2. 由对偶规划的理论, `x_(i j)` 对应的检验数为 `sigma_(i j) = c_(i j) - z_(i j) = c_(i j) - (u_i + v_j)`. 现假设已得到运输问题的一个基可行解 `x_(i_1 j_1), cdots, x_(i_s j_s)`, `quad s = m+n-1`, 利用基变量的检验数等于零, 写出方程组 `{ u_(i_1) + v_(j_1) = c_(i_1 j_1); cdots; u_(i_s) + v_(j_s) = c_(i_s j_s) :}` 由于运输表的每行每列至少含有一个基变量 (??), 可知该方程组含有全部 `m+n` 个对偶变量. 可以证明该方程组有解 (??). 注意到对偶变量有 `m+n` 个, 而方程有 `m+n-1` 个, 故解不唯一.
3. 若该方程组的某个解满足对偶规划 中的约束不等式 `sigma_(i j) = c_(i j) - (u_i + v_j) ge 0`, `quad AA i, j`. 这时, 我们同时得到原问题与对偶问题的最优解: `x_(i_1 j_1), cdots, x_(i_s j_s)` 和 `u_1, cdots, u_m, v_1, cdots, v_n`. (这时所有解都满足约束吗?) 反之, 若方程组的某个解不满足对偶规划的约束, 即非基变量的检验数有负值存在, 则运输问题尚未达到最优解. (这时所有解都不满足约束吗?)

沿用上例, 用位势法求解运输问题 `[ 4, 12, 4_(red 10), 11_(red 6), {:|:}, 16; 2_(red 8), 10, 3_(red 2), 9, {:|:}, 10; 8, 5_(red 14), 11, 6_(red 8), {:|:}, 22; -, -, -, -, +, -; 8, 14, 12, 14, {:|:}, 48; ]`, 红色小字是初始基可行解.

1. 列出位势方程 `{ u_1 + v_3 = 4; u_1 + v_4 = 11; u_2 + v_1 = 2; u_2 + v_3 = 3; u_3 + v_2 = 5; u_3 + v_4 = 6; :}` 位势方程组有无穷多组解, 我们任取一个即可. 如取 `u_2 = 0`, 解得 `u_2 = 0`, `v_1 = 2`, `v_3 = 3`, `u_1 = 1`, `v_4 = 10`, `u_3 = -4`, `v_2 = 9`. 实际操作时, 上述解方程的过程不必写出, 直接把位势填入表中: `[ 4, 12, 4_(grey 10), 11_(grey 6), {:|:}, 16_(red 1); 2_(grey 8), 10, 3_(grey 2), 9, {:|:}, 10_(red 0); 8, 5_(grey 14), 11, 6_(grey 8), {:|:}, 22_(red(-4)); -, -, -, -, +, -; 8_(red 2), 14_(red 9), 12_(red 3), 14_(red(10)), {:|:}, 48; ]`,
2. 再用公式 `sigma_(i j) = c_(i j) - (u_i + v_j)` 计算空格的检验数: `[ 4_(red 1), 12_(red 2), 4_(grey 10), 11_(grey 6), {:|:}, 16_(grey 1); 2_(grey 8), 10_(red 1), 3_(grey 2), 9_(red(-1)), {:|:}, 10_(grey 0); 8_(red 10), 5_(grey 14), 11_(red 12), 6_(grey 8), {:|:}, 22_(grey(-4)); -, -, -, -, +, -; 8_(grey 2), 14_(grey 9), 12_(grey 3), 14_(grey(10)), {:|:}, 48; ]`, 求出的检验数和闭回路法的一致.

闭回路法直观便于理解, 而位势法计算量小.

运输问题求解器