第三章 运输问题的解法
运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许多其它问题也归结到这一类问题中。正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。
§1 运输问题的数学模型及其特性
1.1 运输问题的数学模型
A 1, A 2, , A m 的某种物资调至n 个地点（称为销
B 1, B 2, , B n a 1, a 2, , a m
地或收地） ，各个发点需要调出的物资量分别为 个单位，各
B j b , b , , b A n 个单位。已知每个发点i 到每个收点个收点需要调进的物资量分别为 12的
c ij
物资每单位运价为 ，现问如何调运，才能使总的运费最小。我们把它列在一张表上（称
x B A
为运价表）。设ij 表示从产地i 运往j 销地的运价（i =1，2，…，m ；j
=1，
设有 m 个地点（称为产地或发地）
2，…，
表3-1
n ）。
如果（总发量）
（总收量），我们有如下线性规划问题：
min z =∑∑c ij x ij
i =1j =1
n
m n
⎧
⎪∑x ij =a i (I =1, 2, , m ) ⎪j =1⎪⎪m
⎨∑x ij =b j (j =1, 2, , n ) ⎪i =1
⎪x ij ≥0(i =1, 2, m ; j =1, 2, , n ) ⎪⎪⎩
（3.1）
（3.1）式称为产销平衡运输问题的数学模型。当（总发量）
∑a ≠∑b
i i =1
j =1
m n
j
（总收量）时。即当产大于销（
∑a >∑b
i i =1
j =1
m n
j
）时，其数学模型为
n
min z =∑∑c ij x ij
i =1j =1
m
⎧n
⎪∑x ij ≤a i (I =1, 2, , m ) ⎪j =1⎪⎪m
⎨∑x ij =b j (j =1, 2, , n ) ⎪i =1
⎪x ij ≥0(i =1, 2, m ; j =1, 2, , n ) ⎪⎪⎩
（3.2）
当销大于产（
∑a
i i =1
j =1
m n
j
）时，其数学模型为
min z =∑∑c ij x ij
i =1j =1
m n
⎧
⎪∑x ij =a i (I =1, 2, , m ) ⎪j =1⎪⎪m
⎨∑x ij ≤b j (j =1, 2, , n ) ⎪i =1
⎪x ij ≥0(i =1, 2, m ; j =1, 2, , n ) ⎪⎪⎩
n
（3.3）
因为产销不平衡的运输问题可以转化为产销平衡的运输问题。所以我们先讨论产销平衡的运输问题的求解。
运输问题有mn 个未知量, m +n 个约束方程。例如当m ≈40,
n =70时（3.1）式就
有2800个未知量，110个方程, 若用前面的单纯形法求解，计算工作量是相当大的。我们必须寻找特殊解法。
1.2 运输问题的特性
由于运输问题也是线性规划问题，根据线性规划的一般原理，如果它的最优解存在，一定可以在基可行解中找到。因此，我们先求运输问题（3.1）的约束方程组的系数矩阵的秩r (A ) 等于多少。
（3.1）式有m +n 个约束，将前m 个约束相加得
∑∑x
i =1j =1
m n
ij
=∑a i
i =1n
m
将后n 个约束相加，得
, （3.4）
∑∑x
j =1i =1
n m
ij
=∑b j
i =1m
, （3.5）
n
因为，
,
所以，（3.4）式与（3.5）式是相同得。由此可见，这m +n 个约束不是独立的。我们可以证明：当所有的
∑a =∑b
i i =1
j =1
j
a i ，b j 都大于零时，任何m +n -1个约束都是相互独立的。即，系数矩
x 11 x 12…
阵A 的秩r (A ) =m +n -1，事实上，
x 1n x 21x 22 … x 2n … x m 1x m 2 … x mn
⎡11 1⎤⎢⎥11 1⎢⎥⎢⎥ ⎢⎥
11 1⎥A =⎢
⎢1⎥1 1⎢⎥
111⎢⎥⎢ ⎥⎢⎥
111⎢⎥⎣⎦
注意到在
中去掉第1行而取出第2，第3，…，第m +n 行，又取出与
x 11, x 12, , x 1n , x 21, x 31, , x m 1所对对应的列，则由这些取出的行和列的交叉处的元素构
成A 的一个m +n -1级子式D
1
1
1
D =⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯=1≠0
111 1
1
1
所以 r (A ) =m +n -1，由此可知，运输问题的任何一组基都由 m +n -1个变量组成。
§2 运输问题的表上作业法
2.1 初始解的求法
同单纯形法一样，首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常 见的是左上角法（或西北角法）、最小元素法和Vogl 近似法(VAM)。后两法的效果较好，在此我们仅对最小元素法加以介绍。
最小元素法的所谓元素就是指单位运价。此法的基本思想是：运价最便宜的优先调运，现通过例子来说明。
例1 设有某种物质要从
A 1, A 2, A 3三个仓库运往四个销售点B 1, B 2, B 3, B 4. 。各发
点（仓库）的发货量、各收点（销售点）的收货量以及
A i 到B j 的单位运费C ij 如表
3-2（ i =1,2,3； j =1,2,3,4）. 组织运输才能使总运费最少？
表3-2
由表3-2知，总的发量=总的收量，供销平衡。现从
有几个
c ij
取最小值的格子开始（若
c ij
同时取最小值，则可取其中之一）。在本例中
c 13=1最小。这说明，将A 1
B 3是最便宜的，故应给c 13所对应的变量x 13以尽可能大的数值。显然应
x =min(9, 7) =7。在x 13处填上7。由于B 3的 B 取 13需求已经得到满足（或者说 3列
x , x x , x B 已被满足），故2333应为零，在2333处打×将3列划去，并将A 1的发量相应
的物质调给
地改为2（见表3-3）。
在表3-3未划线的格子中，最小的
c ij
10, 9) 即令为 c 22=6。有 x 22=min(
x 22=9，并在第二列的其它空格（即在x 12, x 32）处打×，于是第二列又被划去，且
A 2的发量只有1了。
表
3-3
接下去的做法是：
在 x 11处填上2，此时， A 1的发量已分配完毕（一般说成： A 1行被满足），故应在第一行的其它空格处（实际上只有 x 14）打上×，划去第一行。
在 x 21处填上1，在第二行的其它空格处（实际上只有 x 24了）打上×，划去第二行。在
在
至此，所有方格都已填上数或打上×，总共填了3＋4－1=6个数（等于基变量的个数）其余方格均已打×。每填一数就划去了一行或一列，总共划去的行数与列数之和也是6。可以证明，用最小元素法所得到的一组解 量，打×处是非基变量。它对应的目标函数为
x 31处填上1，在第一列的其它空格处（实际上已无空格）打上×，划去第一列。 x 34处填上5，在第四列（或第3行）的其它空格处（实际上已无空格）打上×，
划去第四列（或第三行），见表3-4。
x ij
是基可行解，而且填数处是基变
z =9⨯2+1⨯7+11⨯1+6⨯9+14⨯1+16⨯5=184
在用最小元素法确定初始调运方案的
基本步骤：
值得注意的是，如
需要（或不可能）
x ij
是空格，但
B j
的需求已满足，（或
A i 的物质已调完）不
A i 再调运物质到B j ，此时必须禽x ij =0，以保证最后填数的个数
m +n -1个。这一点对于以下的计算是重要的。
2.2
验数的求法
表上作业法同单纯形法一样，也是利用检验数判别已取得的解是否为最优解。
表上作业法求检验数一般有两种方法：位势法和闭回路法。这里我们先介绍位势法。
1 位势法
首先构造位势表
我们将运价表中对应于表3-4有运量处划方格，然后在表的右边添加一列，下面添加一行。并且在添加的行、列里填上一些数，使得表中任何划了方格的对应运价正好等于它所在行及所在列中新填入数字之和。（见表3-5）具体作法如下：
将 A 1行右边空格填入零，则 B 1列、
B 3列下面的空格中必须分别填入9、1。由
于11=9＋2，所以， A 2行的右边空格必须填入2。类似地， B 2列的下面应该填入4（因6=4＋2），
A 3行的右边只能填5（因14=9＋5），最后，由C 34=16，所以,
B 4列必须填入11。这样就得到了表3-5. 这个表称为位势表，新填入的数字分别称为行
位势和列位势。并分别记为
再求检验数
αi 和βj （i =1,2,3；j =1,2,3,4）。
设
x ij
所在的格子的检验数为
σij
，则我们可以证明
σij
=
c ij
－(
αi ＋βj )(i =1，2，…，m ；j =1，2，…，n ),(3.6)并且
当所有的
σij
≥
0时，对应的调运方案是最优方案。
表3-5
显然，对亍那些在方中已确定了调运量的格子的检验数
σij
应该为零，即有
c ij
=
αi ＋βj ，上面我们在求行位势与列位势时就利用了这一关系。下面我们来求其
余格子所对应的检验数。
σ12=c 12-(α1+β2) =18-(0+4) =14； σ14=c 14-(α1+β2) =10-(0+11) =-1； σ23=c 23-(α2+β3) =8-(2+1) =5；
σ24=c 24-(α2+β4) =18-(2+11) =5； σ32=c 32-(α3+β2) =12-(5+4) =3； σ33=c 33-(α3+β3) =2-(5+1) =-4；
2 闭回路法
首先介绍闭回路的概念：如果已确定了某一调运方案，我们从某一空格出发（无调运量的格子），沿水平方向或垂直方向前进，遇到某一个适当有调运量的格子就转向 90︒继续前进。如此继续下去，经过若干次，就一定回到原来出发的空格。这样形成的一条由水平和垂直线段组成的封闭折线称为闭回路。
在表上作业法中，闭回路中重要的概念之一，它既可以计算检验数又可以调整调运方案。由于数字格对应着基变量，其检验数均为零，而我们考虑的是非基变量的检验数，所以只研究从空格出发所形成的闭回路。
由闭回路的构成可见，除起点是空格外，其余所有的拐角点都是填有调运量的。我们可以证明一个重要的事实：从每一个空格出发都存在唯一的闭回路。
例如在表3-5所示的初始调运方案中作出从（3.2）对应的空格为起点的闭回路为
（3,2） →(2,2) →(2,1) →
(3,1) → (3,2)
这条闭合回路，除出发格（3,2）为空格外，其余都是数字格，如表3-6所示。
为确定空格（ k , t ）的检验数，便可以从空格（ k , t ）出发作闭回路，并对该回路的顶点进行编号，即以（ k , t ）格为第一个顶点，所经过的顶点依次为第二个、第三个……。则闭回路上奇数顶点的单位运价之和减去偶数顶点的单位运价之和所得到的差，就是空格（ k , t ）的检验数。其经济意义是非基变量 单位所引起的总运费的变化量。
现以计算（3,2）格的检验数为例加以说明。若让（3,2）格的调运量增加一个单位，为保证产销平衡，则其奇数顶点的调运量也都要增加一个单位此同时，所有
x kt 取值增加一个
偶数顶点的调运量也都要减少一个单位。如表3-7所示。经过这样调整后，就会得到一个新的调运方案如表3-8。
现在考虑按上述方法调整方案后，总运费将如何变化。因为闭回路上所有奇数顶点的调运量都增加了1个单位，单考虑这一因素，总运费的增加量等于闭回路奇数顶点单位运价之和；另一方面，闭回路上所有偶数顶点的调运量都减少了1个单位，单考虑这一因素，总运费的减少量等于闭回路偶数顶点单位运价之和。如
果同时考虑这两方面的因素，总运费的增加量就等于该闭回路上奇数顶点的单位
运价之和减去偶数顶点单位运价之和所得的差，其差值 就是空格的检验数。所以，（2,3）格的检验数为
σ32=(c 32+c 11) -(c 22+c 31) =(12+11) -(14+6) =23-20=3
这表明，如果让（3,2）格的调运量（ A 3运往B 2
的货物量）增加一个单位，总运
费将增加3元（这与前面用位势法求检数的结果是一致的。）同样可以求得表3-7所示的基本可行方案每个空格检验数列于表3-9每个相应方格的括号内。
表3-9
在讨论闭回路法求检验数时，我们看到如果某人空格的检验数为正，那么若
使该空格的调运量增加（即由非基变量变为基变量），总运费就会增加之，如果某个空格的检验数为负，若使该空格的调运量增加，总运费就会减少。我们自然2.3最优方案的判别准则
会想到：如果没有负的检验，总运费就不能再减少了。一般我们有如下结论，即判别最优方案准则：
对于运输问题的一个基本可行方案，如果所有的检验数非负，即
是极小化线性规划问题。所以，最优判别准则乃是所有检验数非负。 σij ≥0, 那么该方案就是一具最优方案。这里的结论和前面线性规划的结论是一致的。因为运输问题
用上述最优判别准则检查表3-9，由于表中还有负的检验，所以，现在得到的方案还不是最优方案。
2.4调运方案的改进
如果所得的基本可行方案不是最优的，就要对其进行改进，这一步工作想当
于普通单纯形法的换基迭代，其运算法则和步骤是：
第一步 确定进基格。选取绝对值最大的负检验数格为进基格，标以“*”，进基格所对应的变量就是单纯形法所对应的变量；
第二步 作从进基格出发作闭回路，并沿任一方向对该闭回路的顶点进行编号，但进基格必须为第一个顶点；
第三步 确定调整量，求出闭回路上所有偶数顶点调运量的极小值 θ, θ叫做调整量；
第四步 调整方案，令此闭回路上所有奇数顶点的调运量加 θ，所有偶数顶点的调运量减 θ，其余调运量不变。调整后进基格由空格变为数字格，在闭回路的偶数顶点中选取一个调运量为零的顶点改为空格，如果有几个偶数顶点的调运量同时变为零，只能选取其中一个顶点改为空格，如果有几个偶数顶点的调运量同时变为零，只能选取其中一个顶点改为空格，这个变为空格的偶数顶点所对应的变量，就是单纯形法是所说的出基变量。
如表3-9， σ33是绝对值最大的负检验数，以（3,3）格为空格出发的闭合回路（3,3）→(1,3)→(1,1)→(3,1)用 θ1表示该闭合回路上的调整量，则
θ1=min(x 13, x 31) =min(7，1) =1。沿着该闭合回路奇数顶点的调运量加θ1，偶数顶点
的调运量减 θ1
，得表3-10。
对表3-10所示的基本可行方案，用闭合回路法重新计算检验数，见表3-11。
其中以（2,4）格为空格的闭回路是(2,4)→(2,1)→(1,1)→(1,3)→(3,3)→(3,4)→(2,4),因此，
σ24=(c 24+c 11+c 33) -(c 21+c 13+c 34) =1
现在， σ14=-5是唯一的负检验数，以(1,4)格为空格对偶调运量进行调整， θ2=min(6, 5) =5，调整后的结果见表3-12的第一表。
对调整后的调运方案继续求检验数，见表3-12的第二表。 由表3-12的第二表可见，所有的检验数 σij ≥0，当前的方案为最优调运方案。此时，总的调运费为：
z =
9⨯3+1⨯1+10⨯5+11⨯1+6⨯9+2⨯6=155,
表3-12
即当
x 11=3, x 13=1, x 14=5, x 21=1, x 22=9, x 33=6
时为最优，最小费用为155个单位。