1
第六章运输问题
2
运输问题的模型
3
运输问题的描述运输问题的一般提法是这样的：某种物资有若干个产地和销地,若已知各个产地的产量,各个销地的销量以及各产地到各销地的单位运价 （ 或运输距离 ） 。 问应如何组织调运,才能使总运费 （ 或总的运输量 ） 最省？
将此问题更具体化，假定有 m个产地,n
个销地，
4
ai— 第 i产地的供应量,i=1,2,…,m。
bj— 第 j销地的需求量,j=1,2,…,n。
cij— 从 i产地到 j销地的单位运费,i=1，
2,…,m,j=1,2,…,n。
xij— i产地到 j销地的调运数量 。
则该问题为求解最佳调运方案,即求解所有 xij的值,使总的运输费用 达到最少 。 决策变量为 xij 。
11
mn
ij ij
ij
cx
5
一般模型形式
11
m i n
mn
ij ij
ij
Z c x
1
1
,1,2,,
.,,1,2,,
0,
m
ij j
i
n
ij i
j
ij
x b j n
s t x a i m
x
所有的i,j
6
类型
（ 1）当 时，为平衡型运输问题。
（ 2）当 时，为不平衡型运输问题。
11
mn
ijijab
11
mn
ij
ij
ab
7
平衡型运输问题的模型
11
m i n
mn
ij ij
ij
Z c x
1
1
,1,2,,
.,,1,2,,
0,
m
ij j
i
n
ij i
j
ij
x b j n
s t x a i m
x
所有的i,j
8
平衡型运输问题的矩阵表示该模型包含有 m*n个变量,m+n个约束方程，
其系数矩阵 A如下：
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
A
11 12 1nx x x 2 1 2 2 2 nx x x 12m m m nx x x
m行
n行
9
闭回路
10
闭回路的意义
x11
x21
x12 x13 x14
x23
x42 x44
11
运输问题的基变量基变量个数为 m+n-1
m+n-1个变量构成基变量的充要条件是不含闭回路，并且从一个非基变量出发存在且惟一存在一条闭回路。
12
例
A1,A2两煤矿产的煤运往 B1,B2,B3三个城市销售，各煤矿的供应量、各城市的需求量以及煤矿与城市之间的单位运费如下表所示，试列出其数学规划模型。
13
200
230
95
75
180
70
65
150
90
80
100
A1
A2
需求量（ t）
供应量
（ t）
B3B2B1
城市单位运费煤矿
14
解设 xij为第 i煤矿向第 j城市的煤的供应量，
cij表示第 i煤矿向第 j城市供应煤的单位运费。 i=1,2，； j=1,2,3。
此题供应总量与需求总量相等，为平衡型的运输问题。列出模型如下：
15
1 1 1 2 1 3 2 1 2 2 2 3
1 1 1 2 1 3
2 1 2 2 2 3
1 1 2 1
1 2 2 2
1 3 2 3
m in 9 0 7 0 9 5 8 0 6 5 7 5
200
230
100
..
150
180
0,1,2 ; 1,2,3
ij
Z x x x x x x
x x x
x x x
xx
st
xx
xx
x i j
16
运输问题的基本求解方法：表上作业法基本可行解 结束换基最优否步骤：
1.确定初始基可行解（西北角法、最小元素法）
2.最优性检验（闭回路法、位势法）
3.解的改进（闭回路调整法）
17
初始基可行解的确定求解运输问题的初始基可行解的基本步骤：
（ 1）在产销平衡表中选一个单元 xij,令 xij =min{ai,bj}，
即 Ai尽量满足 Bj的需求，使一个约束方程得到满足，
将 xij的值填入表中相应位置。
（ 2）从 ai和 bj中分别减去 xij的值，即 Ai在尽可能满足 Bj
的需求后，调整 Ai供给量和 Bj需求量。
（ 3）若 ai =0，则划去对应行（ Ai产品全部供给完），
若 bj =0，则划去对应列（ Bj需求全部满足），注意每次只能划去一行或一列（即只去掉一个约束）。
（ 4）若产销平衡表中所有的行或列均被划去，则结束。
否则，在剩下的产销平衡表中选下一个变量，转步骤
（ 2）继续进行。
18
最终产生的一组变量将满足下面的条件：
（ 1）所有的变量 xij非负，且变量总数为
m+n-1。
（ 2） 所有的约束均得到满足。
（ 3）所有的变量 xij不构成闭回路。
19
西北角法也称为左上角法，每次选取的 xij,都是左上角第一个元素，也就是说，优先安排运价表上编号最小的产地和销地之间的运输业务。该方法的特点是 xij选取方便，
因而算法简单易实现。
20
例用西北角法求解上例的初始调运方案 。
解 第一步,从表中选取西北角的元素 x11,取 x11 =min{a1，
b1}=100,意即 A1煤矿尽可能满足城市 B1的需求量 100，
此时 B1达到全部需求后,需求量修改为 b1’=100-100=0，
A1的供给量第一次修改为 a1’=200-100=100 。 划去第 1
列；
第二步，重复第一步，选取剩下的表中西北角的元素
x12,取 x12 =min{a1’,b2}=100,意即 A1煤矿尽可能满足 B2城市的需求量，此时 A1已供给完所有的煤，供给量第二次修改为 a1’=100-100=0,B2未满足全部需求，
需求量修改为 b2’=150-100=50 。划去第 1行；
21
第三步，重复前面的步骤，选取剩下表中西北角的元素 x22,取 x22 =min{a2,b2’}=50,意即 A2煤矿尽可能满足 B2城市的需求量，此时 B2获得全部需求，需求量第二次修改为 b2’=50-50=0,A2供给量第一次修改为 a2’=230-50=180 。划去第 2列；
第四步，重复前面的步骤，选取剩下表中西北角的元素 x23,取 x23 =min{a2’,b3}=180,该问题是平衡型运输问题，所以最后 A2煤矿的供给量刚好达到 B3城市的需求量,a2’和 b3’均修改为 0。
此时划去第 2行或划去第 3列均可。
22
供应量修改值 ai’
0
0
100
180
200
230180
180
0
100
50
150
50
0
100
100
0
A1
A2
需求量（ t）
需求量修改值 bj’
第二次修改第一次修改供应量（ t）
B3B2B1
第一步 第三步第二步第四步城市调运量煤矿
23
至此产销平衡表中所有的行或列均被划去。由上表可得，初始基可行解为：
x11=100,x12 =100,x22=50,x23 =180，
x13 = x21 =0
24
最小元素法西北角法唯一的优点就是简单易实现，
但是从上例可看出，在用西北角法求解初始基可行解时，完全没有考虑运费的因素，也许优先满足需求的西北角上的元素运费是最大的。最小元素法正是从运费上考虑，希望能优先安排单位运价最小的产地与销地之间的运输业务，从而实现“就近供应”。
25
例用最小元素法求解上例的初始调运方案。
解：见下列两表
95
75
70
65
90
80
A1
A2
B3B2B1
城市单位运费煤矿表一第三步 第一步第四步第二步
26
供应量修改值 ai’
0
0
100
80
200
230
100
80
180
100
0
150
150
0
100
100
0
A1
A2
需求量（ t）
需求量修改值 bj’
第二次修改第一次修改供应量（ t）
B3B2B1
第三步 第一步第四步第二步城市调运量煤矿表二
27
第一步,从表一中选取单位运价最小的 c22=65，
对应的变量为 x22 。 在表二中,取 x22 =min{a2，
b2}=150,此时 B2需求量修改为 b2’=150-150=0。
A2的供给量第二次修改为 a2’=230-150=80 。 划去表一和表二中第 2列；
第二步，从表一中选取剩下的单位运价最小的
c23=75,对应的变量为 x23。在表二中,取 x23
=min{a2’,b3}=80,此时 B3的需求量修改为
b3’=180-80=100,A2的供给量第二次修改为
a2’=0。 划去表一和表二中第 2行；
28
第三步,从表一中选取剩下的单位运价最小的
c11=90,对应的变量为 x11 。 在表二中,取 x11
=min{a1,b1}=100,此时 B1需求量修改为 b1’=0。
A1的供给量第一次修改为 a1’=200-100=100 。
划去表一和表二中第 1列；
第四步，在表一中此时只剩 c13=95,对应变量为 x13,在表二中，取 x13 = min{a1’,b3’ }=100。
29
最终 A1的供给量第二次修改值 a1’和 B3的需求量第二次修改值 b1’均为 0。划去第 1行或第 3列均可。
由 表二 可得，初始基可行解为：
x11=100,x13 =100,x22=150,x23 =80，
x12 = x21 =0
30
练习某公司经销甲产品，它下设三个加工厂。
每日的产量分别为,A1— 7吨,A2— 4吨，
A3— 9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为,B1— 3
吨,B2— 6吨,B3— 5吨,B4— 6吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，
使总运费为最少。
31
单位运价表和产销平衡表
6563销量
7
4
9
10
8
5
3
2
10
11
9
4
3
1
7
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
32
模型设 xij为 Ai厂销往 Bj地的产品数量
11 12 13 14
21 22 23 24
31 32 33 34
11 12 13 14
21 22 23 24
31 32 33 34
11 21 31
12 22 32
13 23 33
14 24 34
m i n 3 11 3 10
9 2 8
7 4 10 5
7
4
9
3
..
6
5
6
0,1,2,3 ; 1,2,3,4
ij
Z x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x
st
x x x
x x x
x x x
x i j
33
确定初始基可行解（最小元素法）
6563销量
7
4
9
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
34
6560销量
7
1
9
13
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
35
6460销量
7
0
9
4
13
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
36
6060销量
3
0
9
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
37
6000销量
3
0
33
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
38
3000销量
3
0
03
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
39
0000销量
0
0
0
3
3
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
40
初始基可行解为：
x13 =4,x14=3,x21=3,x23 =1,x32=6，
x34=3,其它均为 0。
41
最优性检验所求得的基可行解均要经过最优性检验，
以判定该解是否为最优解（也就是最终选择的方案）。表上作业法的最优性检验是对检验数进行判别。运输问题的目标函数要求实现最小化，因而，当所有的时，所得的解为最优解，否则还要进行解的改进。下面介绍两种常用的最优性判别方法。
1,1,,; 1,,i j B i jC C B P i m j n
1 0ij B ijc C B P
42
闭回路法一般称基变量在产销平衡表中所对应的格为 数字格,非基变量值均为 0，对应格为 空格 。
闭回路法是通过在调运方案的计算表上，
从每一空格出发，以水平的或是垂直的直线向前划，每碰到数字格就转 90度后，
继续前进，直到回到起点为止。
43
以 此表 为例,x11,x12,x22,x23,为基变量,x21和
x13为非基变量。从空格 x21 （非基变量）出发，
经数字格 x11,x12,x22回到起点，形成回路，如下图
18050x21
x13100100
44
考察这个初始方案,x21=0表示 A2煤矿的煤没有运往 B1城市，现若想改变初始方案，把 A2的煤运送一单位给 B1,那么，为了保持平衡，就必须使 x11减少一单位,x12增加一单位以及 x22减少一单位。上述调整是为了使总的运输数量达到平衡，但是会造成总的运输费用上的改变。
总运输费用改变量 =80*1+90*（ -1） +70*1+65*
（ -1） =-5。
也就是说，当改变运输方案，使 A2运一单位的煤到 B1时，会使总的运输费用减少 5元。此总运输费用改变量 -5即为检验数。
45
同法可求得另一非基变量 x13的检验数为 15，增加 x13的值总运输费用改变量增加 15元。
因而可通过增加非基变量 x21的值寻求更优方案。
实际上,x21就是在单纯形表里进行迭代时的入基变量。
闭回路法的原理就是通过寻找闭回路来计算非基变量的检验数，再对检验数判断是否找到最优解。而 从每一空格出发一定存在唯一的闭回路。
46
位势法当产销点过多时，采用闭回路法就很繁琐，这时一般采用位势法。位势法又称 v— V法，它是由解运输问题的对偶问题而来的。平衡运输问题的对偶问题为
11
m a x
.,
1,,; 1,,
mn
i i j j
ij
i j ij
g a u b v
s t u v c
i m j n
47
这里对偶模型里的变量 与 个供应约束相对应，变量 与 个需求约束相对应。 和 称为变量的位势。
由于原问题是等式约束，因而对偶变量和 的符号无限制。
( 1,,)iu i m m
( 1,,)jv j n n
iu
iu
jv
jv
48
1 1 2 1 2,,,,,,,B m nC B u u u v v v
而决策变量 的系数向量
ijx
ij i m jP e e
所以，
1B ij i jC B P u v
，从而
1ij B ij ij i jc C B P c u v。
这是一种通过位势求检验数的方法。
根据对偶理论，有
49
单纯形法所有基变量的检验数为 0，所以对于基变量 有
ijx
0ij i jc u v
即
i j iju v c
50
平衡型运输问题基变量的个数有 m+n-1个，
因而像 这样的方程有 m+n-1个。
这组方程中包含有 m+n个未知的对偶变量和，所以其中必存在一个自由未知量，假定为,并取 （这样做并不影响结果），从而可以计算出所有其他的对偶变量的值。再根据对偶变量的值计算非基变量的检验数，并进行判断。
i j iju v c
1u 1 0u?
51
综上所述，位势法的判定步骤如下：
（ 1）根据初始基可行解列出关于对偶变量的方程组（共有 m+n-1个方程）
1 1 1 1
2 2 2 2
1 1 1 1
m n m n m n m n
i j i j
i j i j
i j i j
u v c
u v c
u v c
52
（ 2）令,求得所有对偶变量 和的值。
（ 3）将 和 的值代入,求得所有非基变量的检验数，若存在非基变量的检验数为负，则该非基变量的增大可以使解更优。
1 0u? iu jv
iu jvij i jc u v
53
下面以西北角法求得的初始基可行解
x11=100,x12=100,x22=50,x23=180,x13=x21=0
为例，根据基变量 x11,x12,x11,x11给出对偶变量方程组为
11
12
22
23
90
70
65
75
uv
uv
uv
uv
95
75
70
65
90
80
A1
A2
B3B2B1
城市单位运费煤矿
54
令,求得 。
代入 求得非基变量 x13和 x21的检验数分别为 和,意即非基变量 x21的增加能使方案更优，在进行解的改进的时候，选取它为入基变量。
可以看到，此法求得的结果与闭回路法一致 。
1 0u? 1 2 1 2 30,5,9 0,7 0,8 0u u v v v
ij i jc u v
1 3 1 3 15c u v2 1 2 1 5c u v
55
解的改进运输问题最常用的解的改进方法为闭回路调整法。
其基本思想是，选取检验数为负的所有非基变量中的最小者作为入基变量，以对应空格为出发点画出闭回路，在经过的数字格中选择（ -1）的最小者，对应的基变量为出基变量，然后对数据进行调整。
56
我们依然在前面几小节中计算的数据上进行说明。根据西北角法计算的初始基可行解为 x11=100,x12=100,x22=50，
x23=180,x13=x21=0，求得非基变量 x13和
x21的检验数分别为 15和 -5，此时只有 x21
的检验数不满足非负，取其为入基变量，
以对应的空格引出闭回路如下表
57
200
230（ +1）
（ -1） 180
100（ -1）
50（ +1）
150
100
100
A1
A2
需求量（ t）
供应量（ t）
B3B2B1
城市调运量煤矿
58
选取闭回路上具有（ -1）的数字格中最小者,（其原理与单纯形法中由 θ确定出基变量相同）。然后在闭回路上按照 +,-号分别加上和减去 θ值，即
，得下表
m i n 1 0 0,1 8 0 1 0 0
1 3 2 2 2 31 0 0,1 0 0,1 0 0x x x
59
200
230
100
80
180
150
150
100
100
A1
A2
需求量（ t）
供应量（ t）B3B2B1
城市煤矿调运量
60
得到新一轮基可行解为
x11=100,x13=100,x22=150,x23=80，
x12=x21=0
采用闭回路法或位势法计算该基可行解的非基变量 x12和 x21的检验数分别为 -15和
10，从而确定 x12为换入变量。
重复上述步骤，直至求得最终数据，如下表
61
200
230180
180
150
150
50
50
100
A1
A2
需求量（ t）
供应量（ t）B3B2B1
城市煤矿调运量
62
在计算过程中需要注意的是，可能会出现非基变量（空格）的检验数为 0的情况，
这时，该产销平衡的运输问题存在无穷多最优解。在已求得一个最优解的表格中，以这样的空格出发做闭回路重新调整，可以得到另一个最优解。
63
其他运输问题的处理
1.不平衡型运输问题
2.转运问题
64
不平衡型运输问题在给出的运输问题的一般模型中，
当 时，
该问题为不平衡型运输问题。不平衡型运输问题有产大于销和销大于产两种情况，下面讨论其中一种情况，另一种情况类似推出。
11
mn
ij
ij
ab
65
对于产量大于销量的运输问题，
有模型形式为
11
mn
ij
ij
ab
11
1
1
m in
,1,2,,
.,,1,2,,
0,
mn
ij ij
ij
m
ij j
i
n
ij i
j
ij
Z c x
x b j n
s t x a i m
x i j
所有的，
66
虚拟一个销地 Bn+1,Bn+1的需求量 bn+1为总产量与总销量之差，
即,
单位运费,这样原问题转化为有 m个产地和 n+1个销地的平衡型运输问题，
剩下的工作就是求解一个平衡型运输问题了。
销量大于产量的情况可以类似的虚拟一个产地。
1
11
mn
n i j
ij
b a b?
1 0 ( 1,,)inc i m
67
转运问题前述运输问题产地与销地的界线非常分明，产地只供给（输出）货物，销地只需求（输入）货物，而实际上，绝对的输出与输入几乎是不存在的，最多存在的是产地又是销地的情形，甚至有时一地仅作为其他两地之间输入输出的中转站，象这些类型的运输问题，我们称为转运问题。
68
转运问题的解题思路是先将其转化为平衡型运输问题，再按表上作业法求解，
这一点和不平衡型运输问题是一样的。
69
我们来看一下转运问题在这个转化中一些假定：
1,求最大可能中转量 Q（ Q为大于总产量 的一个数 ） ；
2,纯中转站视为输入量和输出量均为 Q的一个产地和销地；
3,兼中转站的产地 Ai视为输入量为 Q的销地和输出量为 Q+ai的产地；
4,兼中转站的销地 Bj视为输出量为 Q的产地和输入量为 Q+bj的销地 。
1
m
i
i
a
70
转化按照上述假设来完成，重新画出单位运价表和产销平衡表，再按表上作业法进行求解。
第六章运输问题
2
运输问题的模型
3
运输问题的描述运输问题的一般提法是这样的：某种物资有若干个产地和销地,若已知各个产地的产量,各个销地的销量以及各产地到各销地的单位运价 （ 或运输距离 ） 。 问应如何组织调运,才能使总运费 （ 或总的运输量 ） 最省？
将此问题更具体化，假定有 m个产地,n
个销地，
4
ai— 第 i产地的供应量,i=1,2,…,m。
bj— 第 j销地的需求量,j=1,2,…,n。
cij— 从 i产地到 j销地的单位运费,i=1，
2,…,m,j=1,2,…,n。
xij— i产地到 j销地的调运数量 。
则该问题为求解最佳调运方案,即求解所有 xij的值,使总的运输费用 达到最少 。 决策变量为 xij 。
11
mn
ij ij
ij
cx
5
一般模型形式
11
m i n
mn
ij ij
ij
Z c x
1
1
,1,2,,
.,,1,2,,
0,
m
ij j
i
n
ij i
j
ij
x b j n
s t x a i m
x
所有的i,j
6
类型
（ 1）当 时，为平衡型运输问题。
（ 2）当 时，为不平衡型运输问题。
11
mn
ijijab
11
mn
ij
ij
ab
7
平衡型运输问题的模型
11
m i n
mn
ij ij
ij
Z c x
1
1
,1,2,,
.,,1,2,,
0,
m
ij j
i
n
ij i
j
ij
x b j n
s t x a i m
x
所有的i,j
8
平衡型运输问题的矩阵表示该模型包含有 m*n个变量,m+n个约束方程，
其系数矩阵 A如下：
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
A
11 12 1nx x x 2 1 2 2 2 nx x x 12m m m nx x x
m行
n行
9
闭回路
10
闭回路的意义
x11
x21
x12 x13 x14
x23
x42 x44
11
运输问题的基变量基变量个数为 m+n-1
m+n-1个变量构成基变量的充要条件是不含闭回路，并且从一个非基变量出发存在且惟一存在一条闭回路。
12
例
A1,A2两煤矿产的煤运往 B1,B2,B3三个城市销售，各煤矿的供应量、各城市的需求量以及煤矿与城市之间的单位运费如下表所示，试列出其数学规划模型。
13
200
230
95
75
180
70
65
150
90
80
100
A1
A2
需求量（ t）
供应量
（ t）
B3B2B1
城市单位运费煤矿
14
解设 xij为第 i煤矿向第 j城市的煤的供应量，
cij表示第 i煤矿向第 j城市供应煤的单位运费。 i=1,2，； j=1,2,3。
此题供应总量与需求总量相等，为平衡型的运输问题。列出模型如下：
15
1 1 1 2 1 3 2 1 2 2 2 3
1 1 1 2 1 3
2 1 2 2 2 3
1 1 2 1
1 2 2 2
1 3 2 3
m in 9 0 7 0 9 5 8 0 6 5 7 5
200
230
100
..
150
180
0,1,2 ; 1,2,3
ij
Z x x x x x x
x x x
x x x
xx
st
xx
xx
x i j
16
运输问题的基本求解方法：表上作业法基本可行解 结束换基最优否步骤：
1.确定初始基可行解（西北角法、最小元素法）
2.最优性检验（闭回路法、位势法）
3.解的改进（闭回路调整法）
17
初始基可行解的确定求解运输问题的初始基可行解的基本步骤：
（ 1）在产销平衡表中选一个单元 xij,令 xij =min{ai,bj}，
即 Ai尽量满足 Bj的需求，使一个约束方程得到满足，
将 xij的值填入表中相应位置。
（ 2）从 ai和 bj中分别减去 xij的值，即 Ai在尽可能满足 Bj
的需求后，调整 Ai供给量和 Bj需求量。
（ 3）若 ai =0，则划去对应行（ Ai产品全部供给完），
若 bj =0，则划去对应列（ Bj需求全部满足），注意每次只能划去一行或一列（即只去掉一个约束）。
（ 4）若产销平衡表中所有的行或列均被划去，则结束。
否则，在剩下的产销平衡表中选下一个变量，转步骤
（ 2）继续进行。
18
最终产生的一组变量将满足下面的条件：
（ 1）所有的变量 xij非负，且变量总数为
m+n-1。
（ 2） 所有的约束均得到满足。
（ 3）所有的变量 xij不构成闭回路。
19
西北角法也称为左上角法，每次选取的 xij,都是左上角第一个元素，也就是说，优先安排运价表上编号最小的产地和销地之间的运输业务。该方法的特点是 xij选取方便，
因而算法简单易实现。
20
例用西北角法求解上例的初始调运方案 。
解 第一步,从表中选取西北角的元素 x11,取 x11 =min{a1，
b1}=100,意即 A1煤矿尽可能满足城市 B1的需求量 100，
此时 B1达到全部需求后,需求量修改为 b1’=100-100=0，
A1的供给量第一次修改为 a1’=200-100=100 。 划去第 1
列；
第二步，重复第一步，选取剩下的表中西北角的元素
x12,取 x12 =min{a1’,b2}=100,意即 A1煤矿尽可能满足 B2城市的需求量，此时 A1已供给完所有的煤，供给量第二次修改为 a1’=100-100=0,B2未满足全部需求，
需求量修改为 b2’=150-100=50 。划去第 1行；
21
第三步，重复前面的步骤，选取剩下表中西北角的元素 x22,取 x22 =min{a2,b2’}=50,意即 A2煤矿尽可能满足 B2城市的需求量，此时 B2获得全部需求，需求量第二次修改为 b2’=50-50=0,A2供给量第一次修改为 a2’=230-50=180 。划去第 2列；
第四步，重复前面的步骤，选取剩下表中西北角的元素 x23,取 x23 =min{a2’,b3}=180,该问题是平衡型运输问题，所以最后 A2煤矿的供给量刚好达到 B3城市的需求量,a2’和 b3’均修改为 0。
此时划去第 2行或划去第 3列均可。
22
供应量修改值 ai’
0
0
100
180
200
230180
180
0
100
50
150
50
0
100
100
0
A1
A2
需求量（ t）
需求量修改值 bj’
第二次修改第一次修改供应量（ t）
B3B2B1
第一步 第三步第二步第四步城市调运量煤矿
23
至此产销平衡表中所有的行或列均被划去。由上表可得，初始基可行解为：
x11=100,x12 =100,x22=50,x23 =180，
x13 = x21 =0
24
最小元素法西北角法唯一的优点就是简单易实现，
但是从上例可看出，在用西北角法求解初始基可行解时，完全没有考虑运费的因素，也许优先满足需求的西北角上的元素运费是最大的。最小元素法正是从运费上考虑，希望能优先安排单位运价最小的产地与销地之间的运输业务，从而实现“就近供应”。
25
例用最小元素法求解上例的初始调运方案。
解：见下列两表
95
75
70
65
90
80
A1
A2
B3B2B1
城市单位运费煤矿表一第三步 第一步第四步第二步
26
供应量修改值 ai’
0
0
100
80
200
230
100
80
180
100
0
150
150
0
100
100
0
A1
A2
需求量（ t）
需求量修改值 bj’
第二次修改第一次修改供应量（ t）
B3B2B1
第三步 第一步第四步第二步城市调运量煤矿表二
27
第一步,从表一中选取单位运价最小的 c22=65，
对应的变量为 x22 。 在表二中,取 x22 =min{a2，
b2}=150,此时 B2需求量修改为 b2’=150-150=0。
A2的供给量第二次修改为 a2’=230-150=80 。 划去表一和表二中第 2列；
第二步，从表一中选取剩下的单位运价最小的
c23=75,对应的变量为 x23。在表二中,取 x23
=min{a2’,b3}=80,此时 B3的需求量修改为
b3’=180-80=100,A2的供给量第二次修改为
a2’=0。 划去表一和表二中第 2行；
28
第三步,从表一中选取剩下的单位运价最小的
c11=90,对应的变量为 x11 。 在表二中,取 x11
=min{a1,b1}=100,此时 B1需求量修改为 b1’=0。
A1的供给量第一次修改为 a1’=200-100=100 。
划去表一和表二中第 1列；
第四步，在表一中此时只剩 c13=95,对应变量为 x13,在表二中，取 x13 = min{a1’,b3’ }=100。
29
最终 A1的供给量第二次修改值 a1’和 B3的需求量第二次修改值 b1’均为 0。划去第 1行或第 3列均可。
由 表二 可得，初始基可行解为：
x11=100,x13 =100,x22=150,x23 =80，
x12 = x21 =0
30
练习某公司经销甲产品，它下设三个加工厂。
每日的产量分别为,A1— 7吨,A2— 4吨，
A3— 9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为,B1— 3
吨,B2— 6吨,B3— 5吨,B4— 6吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，
使总运费为最少。
31
单位运价表和产销平衡表
6563销量
7
4
9
10
8
5
3
2
10
11
9
4
3
1
7
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
32
模型设 xij为 Ai厂销往 Bj地的产品数量
11 12 13 14
21 22 23 24
31 32 33 34
11 12 13 14
21 22 23 24
31 32 33 34
11 21 31
12 22 32
13 23 33
14 24 34
m i n 3 11 3 10
9 2 8
7 4 10 5
7
4
9
3
..
6
5
6
0,1,2,3 ; 1,2,3,4
ij
Z x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x
st
x x x
x x x
x x x
x i j
33
确定初始基可行解（最小元素法）
6563销量
7
4
9
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
34
6560销量
7
1
9
13
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
35
6460销量
7
0
9
4
13
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
36
6060销量
3
0
9
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
37
6000销量
3
0
33
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
38
3000销量
3
0
03
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
39
0000销量
0
0
0
3
3
4
1
6
3
A1
A2
A3
产量B4B3B2B1
销地加工厂单位运价
40
初始基可行解为：
x13 =4,x14=3,x21=3,x23 =1,x32=6，
x34=3,其它均为 0。
41
最优性检验所求得的基可行解均要经过最优性检验，
以判定该解是否为最优解（也就是最终选择的方案）。表上作业法的最优性检验是对检验数进行判别。运输问题的目标函数要求实现最小化，因而，当所有的时，所得的解为最优解，否则还要进行解的改进。下面介绍两种常用的最优性判别方法。
1,1,,; 1,,i j B i jC C B P i m j n
1 0ij B ijc C B P
42
闭回路法一般称基变量在产销平衡表中所对应的格为 数字格,非基变量值均为 0，对应格为 空格 。
闭回路法是通过在调运方案的计算表上，
从每一空格出发，以水平的或是垂直的直线向前划，每碰到数字格就转 90度后，
继续前进，直到回到起点为止。
43
以 此表 为例,x11,x12,x22,x23,为基变量,x21和
x13为非基变量。从空格 x21 （非基变量）出发，
经数字格 x11,x12,x22回到起点，形成回路，如下图
18050x21
x13100100
44
考察这个初始方案,x21=0表示 A2煤矿的煤没有运往 B1城市，现若想改变初始方案，把 A2的煤运送一单位给 B1,那么，为了保持平衡，就必须使 x11减少一单位,x12增加一单位以及 x22减少一单位。上述调整是为了使总的运输数量达到平衡，但是会造成总的运输费用上的改变。
总运输费用改变量 =80*1+90*（ -1） +70*1+65*
（ -1） =-5。
也就是说，当改变运输方案，使 A2运一单位的煤到 B1时，会使总的运输费用减少 5元。此总运输费用改变量 -5即为检验数。
45
同法可求得另一非基变量 x13的检验数为 15，增加 x13的值总运输费用改变量增加 15元。
因而可通过增加非基变量 x21的值寻求更优方案。
实际上,x21就是在单纯形表里进行迭代时的入基变量。
闭回路法的原理就是通过寻找闭回路来计算非基变量的检验数，再对检验数判断是否找到最优解。而 从每一空格出发一定存在唯一的闭回路。
46
位势法当产销点过多时，采用闭回路法就很繁琐，这时一般采用位势法。位势法又称 v— V法，它是由解运输问题的对偶问题而来的。平衡运输问题的对偶问题为
11
m a x
.,
1,,; 1,,
mn
i i j j
ij
i j ij
g a u b v
s t u v c
i m j n
47
这里对偶模型里的变量 与 个供应约束相对应，变量 与 个需求约束相对应。 和 称为变量的位势。
由于原问题是等式约束，因而对偶变量和 的符号无限制。
( 1,,)iu i m m
( 1,,)jv j n n
iu
iu
jv
jv
48
1 1 2 1 2,,,,,,,B m nC B u u u v v v
而决策变量 的系数向量
ijx
ij i m jP e e
所以，
1B ij i jC B P u v
，从而
1ij B ij ij i jc C B P c u v。
这是一种通过位势求检验数的方法。
根据对偶理论，有
49
单纯形法所有基变量的检验数为 0，所以对于基变量 有
ijx
0ij i jc u v
即
i j iju v c
50
平衡型运输问题基变量的个数有 m+n-1个，
因而像 这样的方程有 m+n-1个。
这组方程中包含有 m+n个未知的对偶变量和，所以其中必存在一个自由未知量，假定为,并取 （这样做并不影响结果），从而可以计算出所有其他的对偶变量的值。再根据对偶变量的值计算非基变量的检验数，并进行判断。
i j iju v c
1u 1 0u?
51
综上所述，位势法的判定步骤如下：
（ 1）根据初始基可行解列出关于对偶变量的方程组（共有 m+n-1个方程）
1 1 1 1
2 2 2 2
1 1 1 1
m n m n m n m n
i j i j
i j i j
i j i j
u v c
u v c
u v c
52
（ 2）令,求得所有对偶变量 和的值。
（ 3）将 和 的值代入,求得所有非基变量的检验数，若存在非基变量的检验数为负，则该非基变量的增大可以使解更优。
1 0u? iu jv
iu jvij i jc u v
53
下面以西北角法求得的初始基可行解
x11=100,x12=100,x22=50,x23=180,x13=x21=0
为例，根据基变量 x11,x12,x11,x11给出对偶变量方程组为
11
12
22
23
90
70
65
75
uv
uv
uv
uv
95
75
70
65
90
80
A1
A2
B3B2B1
城市单位运费煤矿
54
令,求得 。
代入 求得非基变量 x13和 x21的检验数分别为 和,意即非基变量 x21的增加能使方案更优，在进行解的改进的时候，选取它为入基变量。
可以看到，此法求得的结果与闭回路法一致 。
1 0u? 1 2 1 2 30,5,9 0,7 0,8 0u u v v v
ij i jc u v
1 3 1 3 15c u v2 1 2 1 5c u v
55
解的改进运输问题最常用的解的改进方法为闭回路调整法。
其基本思想是，选取检验数为负的所有非基变量中的最小者作为入基变量，以对应空格为出发点画出闭回路，在经过的数字格中选择（ -1）的最小者，对应的基变量为出基变量，然后对数据进行调整。
56
我们依然在前面几小节中计算的数据上进行说明。根据西北角法计算的初始基可行解为 x11=100,x12=100,x22=50，
x23=180,x13=x21=0，求得非基变量 x13和
x21的检验数分别为 15和 -5，此时只有 x21
的检验数不满足非负，取其为入基变量，
以对应的空格引出闭回路如下表
57
200
230（ +1）
（ -1） 180
100（ -1）
50（ +1）
150
100
100
A1
A2
需求量（ t）
供应量（ t）
B3B2B1
城市调运量煤矿
58
选取闭回路上具有（ -1）的数字格中最小者,（其原理与单纯形法中由 θ确定出基变量相同）。然后在闭回路上按照 +,-号分别加上和减去 θ值，即
，得下表
m i n 1 0 0,1 8 0 1 0 0
1 3 2 2 2 31 0 0,1 0 0,1 0 0x x x
59
200
230
100
80
180
150
150
100
100
A1
A2
需求量（ t）
供应量（ t）B3B2B1
城市煤矿调运量
60
得到新一轮基可行解为
x11=100,x13=100,x22=150,x23=80，
x12=x21=0
采用闭回路法或位势法计算该基可行解的非基变量 x12和 x21的检验数分别为 -15和
10，从而确定 x12为换入变量。
重复上述步骤，直至求得最终数据，如下表
61
200
230180
180
150
150
50
50
100
A1
A2
需求量（ t）
供应量（ t）B3B2B1
城市煤矿调运量
62
在计算过程中需要注意的是，可能会出现非基变量（空格）的检验数为 0的情况，
这时，该产销平衡的运输问题存在无穷多最优解。在已求得一个最优解的表格中，以这样的空格出发做闭回路重新调整，可以得到另一个最优解。
63
其他运输问题的处理
1.不平衡型运输问题
2.转运问题
64
不平衡型运输问题在给出的运输问题的一般模型中，
当 时，
该问题为不平衡型运输问题。不平衡型运输问题有产大于销和销大于产两种情况，下面讨论其中一种情况，另一种情况类似推出。
11
mn
ij
ij
ab
65
对于产量大于销量的运输问题，
有模型形式为
11
mn
ij
ij
ab
11
1
1
m in
,1,2,,
.,,1,2,,
0,
mn
ij ij
ij
m
ij j
i
n
ij i
j
ij
Z c x
x b j n
s t x a i m
x i j
所有的，
66
虚拟一个销地 Bn+1,Bn+1的需求量 bn+1为总产量与总销量之差，
即,
单位运费,这样原问题转化为有 m个产地和 n+1个销地的平衡型运输问题，
剩下的工作就是求解一个平衡型运输问题了。
销量大于产量的情况可以类似的虚拟一个产地。
1
11
mn
n i j
ij
b a b?
1 0 ( 1,,)inc i m
67
转运问题前述运输问题产地与销地的界线非常分明，产地只供给（输出）货物，销地只需求（输入）货物，而实际上，绝对的输出与输入几乎是不存在的，最多存在的是产地又是销地的情形，甚至有时一地仅作为其他两地之间输入输出的中转站，象这些类型的运输问题，我们称为转运问题。
68
转运问题的解题思路是先将其转化为平衡型运输问题，再按表上作业法求解，
这一点和不平衡型运输问题是一样的。
69
我们来看一下转运问题在这个转化中一些假定：
1,求最大可能中转量 Q（ Q为大于总产量 的一个数 ） ；
2,纯中转站视为输入量和输出量均为 Q的一个产地和销地；
3,兼中转站的产地 Ai视为输入量为 Q的销地和输出量为 Q+ai的产地；
4,兼中转站的销地 Bj视为输出量为 Q的产地和输入量为 Q+bj的销地 。
1
m
i
i
a
70
转化按照上述假设来完成，重新画出单位运价表和产销平衡表，再按表上作业法进行求解。
