第4章 运输问题与指派问题：Vogel 法、位势法与匈牙利法

1. 运输模型

有 $m$ 个产地（供应 $s_i$）、$n$ 个销地（需求 $d_j$），单位运价 $c_{ij}$。设 $x_{ij}$ 为从产地 $i$ 运到销地 $j$ 的量：

它当然可以用单纯形法解，但 $m=n=100$ 时就有 10000 个变量、200 条约束。运输问题的系数矩阵结构特殊，有一套直接在表格上操作的算法，快得多。四条性质先记住：

虚拟产地分到某个销地的量，含义是该销地缺货的数量；虚拟销地收到某个产地的量，含义是该产地没运出去的库存。

2. 主线例子

三个工厂供应 30、40、50 箱，四个仓库需求 20、35、25、40 箱，单位运价：

总供应 120 = 总需求 120，已平衡。基变量个数 $3+4-1=6$。

3. Vogel 近似法求初始解

Vogel 法的想法是：先照顾“选错代价最大”的行或列。 每一行（列）的罚数 = 该行（列）中次小运价 − 最小运价，表示如果不用最便宜的格，至少要多付多少。

步骤：

1. 计算每个未划去的行和列的罚数（只有一个格剩下时，罚数取该格运价）。
2. 选罚数最大的行或列（并列任选），在其中运价最小的格里分配尽可能多的量，即 $\min(\text{剩余供应},\text{剩余需求})$。
3. 更新供需，划去已满足的行或列（同时满足时只划去一个，另一个留下供应或需求为 0 的“退化”分配）。
4. 重复，直到全部分配完。

主线例子的六步：

初始解（6 个基变量，个数正确）：

$z=8\cdot20+7\cdot10+8\cdot25+2\cdot15+3\cdot35+10\cdot15=715$。

4. 位势法检验最优性

给每行一个位势 $u_i$、每列一个位势 $v_j$，要求每个基格满足

6 个方程、7 个未知数，任取一个设为 0（选基格最多的那一行，计算最省事）。然后对每个非基格计算检验数

全部 $\ge0$ 则最优；有负数则不是最优，最负的那个格进基。这里的 $\bar c_{ij}$ 和单纯形表里的检验数是同一个东西，$u_i,v_j$ 正是对偶变量。

取 $u_1=0$：

• 格(1,1)：$v_1=8$；格(1,4)：$v_4=7$；
• 格(2,4)：$u_2=2-7=-5$；格(2,3)：$v_3=8-(-5)=13$；
• 格(3,4)：$u_3=10-7=3$；格(3,2)：$v_2=3-3=0$。

非基格检验数：

格(3,3) 为 −2：每往这里运 1 箱，总成本降 2。不是最优。

5. 闭回路调整

闭回路是从进基格出发、只在基格上转弯、最后回到出发格的折线：相邻两格同行或同列，每次转弯 90°。可以证明对每个非基格这样的回路唯一存在。

格(3,3) 的回路：$(3,3)\to(3,4)\to(2,4)\to(2,3)\to(3,3)$。从进基格开始交替标 $+$、$-$：

调整量 $\theta$ = 标“−”的格中的最小运量 $=\min(15,25)=15$。“+”格加 15、“−”格减 15，格(3,4) 降为 0 出基。这样每行每列的增减相抵，供需仍满足。

新解：

$z=715+(-2)\times15=685$。重新求位势（$u_1=0$）：$v_1=8,\ v_4=7,\ u_2=-5,\ v_3=13,\ u_3=1,\ v_2=2$。非基格检验数为

全部为正，最优总运费 685，且最优解唯一（没有为 0 的检验数）。

6. 运价的灵敏度

问： 工厂 3 到仓库 3 的运价从 14 变成 $14+\Delta$，$\Delta$ 在什么范围内当前最优方案不变？

格(3,3) 是基格，运价变化会改变位势。保持 $u_1=0$ 重新求：$v_1=8,\ v_4=7,\ u_2=-5,\ v_3=13$，由格(3,3) 得 $u_3=14+\Delta-13=1+\Delta$，由格(3,2) 得 $v_2=3-u_3=2-\Delta$。非基格检验数：

取交集：$-2\le\Delta\le2$，即运价在 $[12,\ 16]$ 内最优方案不变（总运费随之变为 $685+15\Delta$）。

如果改的是非基格的运价，位势不变，只需要求该格自己的检验数非负：例如格(3,1) 的检验数是 3，运价降幅不超过 3（$\Delta\ge-3$）时方案不变。

7. 生产—库存问题写成运输模型

运输模型不只用于运货。“第 $i$ 期生产、第 $j$ 期交货”也可以看成从产地 $i$ 运到销地 $j$：

例： 三个月产能 50、60、40，需求 40、50、60，单位生产成本 30；提前生产每件每月保管费 1；延期交货每件每月罚金 3。

运价矩阵：$c_{ij}=30+1\cdot(j-i)$（$j\ge i$），$c_{ij}=30+3\cdot(i-j)$（$j<i$）：

用 Vogel 法得到 $x_{11}=40,\ x_{12}=10,\ x_{22}=40,\ x_{23}=20,\ x_{33}=40$，位势检验所有检验数 $\ge0$，最优总成本 4530。读法：1 月生产 50 件，其中 10 件存到 2 月；2 月生产 60 件，其中 20 件存到 3 月；3 月生产 40 件。格(1,3) 的检验数为 0，说明还有另一个同样便宜的方案（将 1 月原定存到 2 月的 10 件改为存到 3 月，2 月的 10 件相应提前交给 2 月需求）。

如果总产能大于总需求，就加一个“不生产”的虚拟需求期，运价取 0。

8. 指派问题

$n$ 个人做 $n$ 项任务，每人恰好一项、每项恰好一人，$c_{ij}$ 是第 $i$ 人做第 $j$ 项的成本：

它是所有供需都等于 1 的平衡运输问题。人数和任务数不等时，补虚拟人或虚拟任务（成本 0）；某人不能做某项任务时，成本设为很大的 $M$。

匈牙利法的依据是：某一行（列）同时减去一个常数，最优指派不变。于是不断化简成本矩阵，直到能在 0 上直接选出指派。

1. 行化简： 每行减去该行最小值。列化简： 每列再减去该列最小值。此时每行每列都至少有一个 0。
2. 试指派： 能否找到 $n$ 个位于不同行、不同列的 0？能，就是最优指派。
3. 画线调整： 不能时，用最少的横线和竖线盖住所有 0（线数等于最多能选出的独立 0 的个数，小于 $n$）。找出没被盖住的最小元素 $k$：未盖住的元素都减 $k$，两线交叉处的元素加 $k$，只被盖一次的不变。
4. 回到第 2 步。

例1：四人四项任务，丁不能做任务 4。

行化简（减 9、6、6、9）后再列化简（第 4 列减 2）：

已能选出 4 个独立的 0：乙→1、丁→2、丙→3、甲→4。总成本 $11+6+6+9=32$。

例2：四人五项任务（每人最多一项，有人不能做某些任务）。

“—”记为 $M$。人比任务少一个，补一个虚拟人（第 5 行，成本全为 0）凑成 $5\times5$。行化简后（虚拟行本来就全是 0，列最小值都是 0，列化简不变）：

甲和丁都只在任务 3 有 0，最多选出 4 个独立的 0，不够 5 个。用 4 条线覆盖所有 0（乙、丙、虚拟三行加第 3 列），未覆盖的元素只剩甲、丁两行中第 3 列以外的格，其中最小的是 1（甲→4、丁→4）。未覆盖元素减 1、交叉处加 1：

现在可以选出 5 个独立的 0：甲→4、乙→5、丙→1、丁→3、虚拟→2。最小总成本 $8+8+8+8=32$，任务 2 无人承担（被分给了虚拟人）。

9. 小结

• 运输问题：平衡后有 $m+n-1$ 个基变量，供需为整数则解为整数。
• Vogel 法：罚数 = 次小 − 最小运价，先照顾罚数最大的行列，在其最便宜的格分配。
• 位势法：基格 $u_i+v_j=c_{ij}$，非基格检验数 $c_{ij}-u_i-v_j$，全部非负即最优。
• 闭回路：从进基格交替 $+/-$，调整量取“−”格最小运量。
• 基格运价变化要重算位势；非基格只看自己的检验数。
• 指派问题：行列化简 → 试指派 → 最少线覆盖 → 未盖住减 $k$、交叉加 $k$。

自测