第三章 运输问题
—数学模型及其解法
顺风而呼，声非加疾也，而闻者彰。
假舆马者，非利足也，而致千里；假舟
楫者，非能水也，而绝江河。君子生非
异也，善假于物也。 荀子, 劝学,
?管理与人文学院 忻展红
1999,4
2
3.1 运输问题的一般数学模型
? 有 m个产地生产某种物资，有 n个地区需要该类物资
? 令 a1,a2,…,am表示各产地产量,b1,b2,…,bn表示各销
地的销量,?ai=?bj 称为产销平衡
? 设 xij表示产地 i 运往销地 j 的物资量,wij表示对应的单
位运费，则我们有运输问题的数学模型如下：
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
0
,,2,1
,,2,1
)(m i n
1
1
1 1
ij
j
m
i
ij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xwxf
销量约束
产地约束
?
?运输问题有 m?n个
决策变量,m+n个
约束条件。由于产
销平衡条件，只有
m+n–1个相互独立，
因此，运输问题的
基变量只有 m+n–1
个
3
3.2 运输问题的求解方法
? 约束条件非常有规律，技术系数非 0 即 1
? 基变量的个数远小于决策变量的个数
? 采用表上作业法，称为位势法和踏石法
? 运算中涉及两个表：运费表和产销平衡表 (分配表 )
销地
运费 1 2 ? n
产地
1 w
11
w
12 ?
w
1 n
2 w
21
w
22 ?
w
2 n
? ? ? ? ?
m w
m 1
w
m 2 ?
w
mn
4
3.2.1 寻找初始可行解的方法
1、西北角法
– 从 x11开始分配，从西北向东南方向逐个分配
– xij 的分配公式
?
?
?
??
??
? 列待分物资量列已分配的总量
行尚余物资量行已分配的总量
) (
) (
m i n jjb
iia
x
j
i
ij
例 3.2.1
销地 产量
运费 1 2 3 4 a
i
产地
1 20 11 3 6 5
2 5 9 10 2 10
3 18 7 4 1 15
销量 b
j 3 3 12 12
5
销地 产量
运量 1 2 3 4 a
i
产地
1 5
2 10
3 15
销量 b
j
3 3 12 12
例 3.2.1 西北角法
销地 产量
2 3 4 a
i
3 x
12
5
10
15
j
3 12 12
销地 产量
1 2 3 4 a
i
1 3 2 5
2 x
22
10
3 15
销量 b
j
3 3 12 12
销地 产量
2
1 x
23
产量
9
x
33
销量
销地 产量
1 2 3 4 a
i
3 2 5
1 9 10
3 x
33
15
销量 b
j
3 3 12 12
销地 产量
3 4 a
i
5
9 10
3 12 15
j
12
? ?
? ?
???? 3
1
4
1
205)(67
i j ijij
xwxfnm 个基变量有
6
2、最低费用法
? 采用最小费用优先分配的原则，看一步 编号 运费表 { w ij } 分配表 { x ij }
20 11 ( 3 ) 6 x 13 5
I 5 9 10 2 10
18 7 4 1 12 15
3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 5 5
II 5 9 10 2 10
18 7 ( 4 ) 1 x 3 3 12 15
3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 5 5
III 5 9 ( 1 0 ) 2 3 3 4 10
18 7 4 1 3 12 15
3 3 12 12
f(x)=121，比
西北角法低
84
7
3、运费差额法
? 采用最大差额费用 (即利用每行或列中最小费用与次最小之
间的差额中选最大 )优先分配的原则，看两步编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 3 5
I 5 9 10 2 3 3 10
18 7 4 1 3 15
13 2 1 1 3 3 12 12
f(x)=98，比
最低费用法
又低了 23
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 3 5
II 5 9 10 2 7 3 7 10
18 7 4 1 3 15
13 2 1 1 3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 3 5
III 5 9 10 2 7 3 7 10
18 7 4 1 3 5 15
13 4 1 5 3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 8 5 5
IV 5 9 10 2 7 3 7 10
18 7 4 1 3 3 7 5 15
13 - - 5 3 3 12 12
8
3.2.2 利用位势法检验分配方案是否最优
? 不采用单纯型法，如何获得 xij的检验数
? 找到原问题的基础可行解，保持互补松弛条件，求出
对应对偶问题的解，若该对偶问题的解非可行，则原
问题的解不是最优解；否则，达到最优解
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
0
,,2,1
,,2,1
)(m i n
1
1
1 1
ij
j
m
i
ij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xwxf
?
?
?
?
?
?
?
??
?
??
?? ??
??
njmi
vu
wvu
vbuavug
ji
ijji
n
j
jj
m
i
ii
,,2,1,,,2,1
,
),(m a x
11
??
不限
9
?
?
?
?
?
?
?
?
?
??
??
??
???
???
?????
332313
222212
112111
22232221
11131211
232322222121131312121111
vbxx
vb xx
vbxx
uaxxx
uaxxx
xwxwxwxwxwxwm i n
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
??
??
????
不限v,v,v,u,u
wv u
wvu
wvu
wv u
wvu
wvu
vbvbvbuauam a x
32121
2332
2222
2112
1331
1221
1111
3322112211
10
位势法的原理
? 为满足互补松弛条件，原问题中 xij被选为基变量，即 xij?0，
则要求对偶问题中 ui+vj=wij，即该行的松弛变量为 0
? 共有 m+n?1个基变量 xij,因此可得 m+n?1个等式 ui+vj=wij
? m+n?1个等式只能解出 m+n?1个 ui 和 vj,而一共有 m+n个
ui 和 vj,但可令任一个 ui 或 vj =0，从而解出其它 m+n?1个
的值；这就是 位势法
? 令 zij= ui + vj,其相当原问题 xij的 机会费用
? 若对所有非基变量有 zij ?wij ? 0，即 ui + vj ? wij，表明当前
ui 和 vj 是对偶问题的可行解，由互补松弛定理可知当前
m+n?1个基变量 xij 是最优解，否则
? 从 zij ? wij > 0 中找最大者，对应 xij 就是 入变量
11
3.2.3 踏石法
1、找入变量
– 从 zij ? wij > 0 中找最大者，对应 xij 就是入变量
2、以 xij 为起点，寻找由原基变量构成的 闭合回路
– 该回路只在每个拐角各有一个基变量，中间允许穿越某些基
变量；因此，闭合回路中必有偶数个变量 (包括 xij )，且回路
中每行每列只有两个变量
3、求入变量 xi*j* 的最大值及新基变量的解
– 从 xij出发，沿任一个方向对回路拐角上的基变量依此标,?”
和,+”，表示,?”和,+” xij, 从而迭代后仍满足分配的
平衡
– 标有,?”的变量中最小者就是 出变量 xi*j*, 对应 xi*j*的值就
是所 求入变量 xij 的最大值
– 标有,?”的变量减去 xi*j*,标有,+”的变量加上 xi*j*
4、用位势法求新基变量的检验数
– 若所有 zij ? wij ? 0，则达到最优，算法停止；否则返回 1
12
例 3.2.1 踏石法，以最低费用法所得初始解开始编号 运费表 { z ij / w ij } u i 分配表 { x ij }
- 2 / 20 2 / 11 3 0 / 6 3 5 5
I 5 9 10 7 / 2 10 3 3 4 ? x
24 10
- 1 / 18 3 / 7 4 1 4 3 + 12 ? 15
v j ? 5 ? 1 0 ? 3 3 3 12 12
编号 运费表 { z ij / w ij } u i 分配表 { x ij }
3 / 20 7 / 11 3 0 / 6 ? 2 5 5
II 5 9 5 / 1 0 2 0 3 3 ? 4 + 10
4 / 18 8 / 7 4 1 ? 1 x
32 7 8
? 15
v j 5 9 5 2 3 3 12 12
编号 运费表 { z ij / w ij } u i 分配表 { x ij }
3 / 20 6 / 11 3 0 / 6 ? 1 5 5
III 5 8 / 9 5 / 1 0 2 1 3 7 10
4 / 18 7 4 1 0 3 7 5 15
v j 4 7 4 1 3 3 12 12
答,最优解如上分配表,OBJ=98
OBJ=121
OBJ=101
13
3.3 运输问题迭代中的一些具体问题
3.3.1 闭合回路的画法
– 从入变量 xij出发，遇到某个基变量则选一个方向拐角，若不能再遇
到其它基变量，则返回上一拐角，换一个方向走，采用 深探法
– 闭合回路不一定是矩形
3.3.2 产销不平衡
– 供过于求，即 ?ai > ?bj, 增加一个虚收点 Dn+1,bn+1= ?ai - ?bj,令
wi,n+1=0,i=1,2,…,m
– 供小于求，即 ?ai < ?bj, 增加一个虚发点 Wm+1,am+1= ?bj - ?ai,
令 wm+1,j=0,j=1,2,…,n
3.3.3 关于退化问题
1、初始解退化。 即所求初始基变量的个数少于 m+n?1。必须
补足基变量的个数，否则不能正常解出 m+n个 ui 和 vj
– 所补基变量的值为 0,补充的原则,(1)尽量先选运费小的实变量 ；
(2)补充后不能有某个基变量独占一行一列
14
3.3.3 关于退化问题
2、迭代过程中出现退化
– 闭合回路中标有,?”的基变量同时有多个达到最小
– 变换后，有多个原基变量变为 0，选运费最大者为 出变量,其
余保留在新的基础解中
– 退化较严重时，可能会出现多次迭代只有值为 0 的基变量在
转移。此时，一要耐心，二要正确选择出变量
踏石法迭代中需注意的问题：
1、错误地将分配表中基变量的解代入到运费表中
2、不能正确画闭合回路
3、初始解退化，未能补足基变量的个数。因此在位势法中
多次令某个 ui 或 vj 为 0；
4、在位势法中只能令一个 ui 或 vj 为 0；若不能求出全部 ui
和 vj,说明基变量未选够数或未选对
—数学模型及其解法
顺风而呼，声非加疾也，而闻者彰。
假舆马者，非利足也，而致千里；假舟
楫者，非能水也，而绝江河。君子生非
异也，善假于物也。 荀子, 劝学,
?管理与人文学院 忻展红
1999,4
2
3.1 运输问题的一般数学模型
? 有 m个产地生产某种物资，有 n个地区需要该类物资
? 令 a1,a2,…,am表示各产地产量,b1,b2,…,bn表示各销
地的销量,?ai=?bj 称为产销平衡
? 设 xij表示产地 i 运往销地 j 的物资量,wij表示对应的单
位运费，则我们有运输问题的数学模型如下：
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
0
,,2,1
,,2,1
)(m i n
1
1
1 1
ij
j
m
i
ij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xwxf
销量约束
产地约束
?
?运输问题有 m?n个
决策变量,m+n个
约束条件。由于产
销平衡条件，只有
m+n–1个相互独立，
因此，运输问题的
基变量只有 m+n–1
个
3
3.2 运输问题的求解方法
? 约束条件非常有规律，技术系数非 0 即 1
? 基变量的个数远小于决策变量的个数
? 采用表上作业法，称为位势法和踏石法
? 运算中涉及两个表：运费表和产销平衡表 (分配表 )
销地
运费 1 2 ? n
产地
1 w
11
w
12 ?
w
1 n
2 w
21
w
22 ?
w
2 n
? ? ? ? ?
m w
m 1
w
m 2 ?
w
mn
4
3.2.1 寻找初始可行解的方法
1、西北角法
– 从 x11开始分配，从西北向东南方向逐个分配
– xij 的分配公式
?
?
?
??
??
? 列待分物资量列已分配的总量
行尚余物资量行已分配的总量
) (
) (
m i n jjb
iia
x
j
i
ij
例 3.2.1
销地 产量
运费 1 2 3 4 a
i
产地
1 20 11 3 6 5
2 5 9 10 2 10
3 18 7 4 1 15
销量 b
j 3 3 12 12
5
销地 产量
运量 1 2 3 4 a
i
产地
1 5
2 10
3 15
销量 b
j
3 3 12 12
例 3.2.1 西北角法
销地 产量
2 3 4 a
i
3 x
12
5
10
15
j
3 12 12
销地 产量
1 2 3 4 a
i
1 3 2 5
2 x
22
10
3 15
销量 b
j
3 3 12 12
销地 产量
2
1 x
23
产量
9
x
33
销量
销地 产量
1 2 3 4 a
i
3 2 5
1 9 10
3 x
33
15
销量 b
j
3 3 12 12
销地 产量
3 4 a
i
5
9 10
3 12 15
j
12
? ?
? ?
???? 3
1
4
1
205)(67
i j ijij
xwxfnm 个基变量有
6
2、最低费用法
? 采用最小费用优先分配的原则，看一步 编号 运费表 { w ij } 分配表 { x ij }
20 11 ( 3 ) 6 x 13 5
I 5 9 10 2 10
18 7 4 1 12 15
3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 5 5
II 5 9 10 2 10
18 7 ( 4 ) 1 x 3 3 12 15
3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 5 5
III 5 9 ( 1 0 ) 2 3 3 4 10
18 7 4 1 3 12 15
3 3 12 12
f(x)=121，比
西北角法低
84
7
3、运费差额法
? 采用最大差额费用 (即利用每行或列中最小费用与次最小之
间的差额中选最大 )优先分配的原则，看两步编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 3 5
I 5 9 10 2 3 3 10
18 7 4 1 3 15
13 2 1 1 3 3 12 12
f(x)=98，比
最低费用法
又低了 23
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 3 5
II 5 9 10 2 7 3 7 10
18 7 4 1 3 15
13 2 1 1 3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 3 5
III 5 9 10 2 7 3 7 10
18 7 4 1 3 5 15
13 4 1 5 3 3 12 12
编号 运费表 { w ij } 分配表 { x ij }
20 11 3 6 8 5 5
IV 5 9 10 2 7 3 7 10
18 7 4 1 3 3 7 5 15
13 - - 5 3 3 12 12
8
3.2.2 利用位势法检验分配方案是否最优
? 不采用单纯型法，如何获得 xij的检验数
? 找到原问题的基础可行解，保持互补松弛条件，求出
对应对偶问题的解，若该对偶问题的解非可行，则原
问题的解不是最优解；否则，达到最优解
?
?
?
?
?
?
?
?
??
??
?
?
?
? ?
?
?
? ?
0
,,2,1
,,2,1
)(m i n
1
1
1 1
ij
j
m
i
ij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xwxf
?
?
?
?
?
?
?
??
?
??
?? ??
??
njmi
vu
wvu
vbuavug
ji
ijji
n
j
jj
m
i
ii
,,2,1,,,2,1
,
),(m a x
11
??
不限
9
?
?
?
?
?
?
?
?
?
??
??
??
???
???
?????
332313
222212
112111
22232221
11131211
232322222121131312121111
vbxx
vb xx
vbxx
uaxxx
uaxxx
xwxwxwxwxwxwm i n
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
??
??
????
不限v,v,v,u,u
wv u
wvu
wvu
wv u
wvu
wvu
vbvbvbuauam a x
32121
2332
2222
2112
1331
1221
1111
3322112211
10
位势法的原理
? 为满足互补松弛条件，原问题中 xij被选为基变量，即 xij?0，
则要求对偶问题中 ui+vj=wij，即该行的松弛变量为 0
? 共有 m+n?1个基变量 xij,因此可得 m+n?1个等式 ui+vj=wij
? m+n?1个等式只能解出 m+n?1个 ui 和 vj,而一共有 m+n个
ui 和 vj,但可令任一个 ui 或 vj =0，从而解出其它 m+n?1个
的值；这就是 位势法
? 令 zij= ui + vj,其相当原问题 xij的 机会费用
? 若对所有非基变量有 zij ?wij ? 0，即 ui + vj ? wij，表明当前
ui 和 vj 是对偶问题的可行解，由互补松弛定理可知当前
m+n?1个基变量 xij 是最优解，否则
? 从 zij ? wij > 0 中找最大者，对应 xij 就是 入变量
11
3.2.3 踏石法
1、找入变量
– 从 zij ? wij > 0 中找最大者，对应 xij 就是入变量
2、以 xij 为起点，寻找由原基变量构成的 闭合回路
– 该回路只在每个拐角各有一个基变量，中间允许穿越某些基
变量；因此，闭合回路中必有偶数个变量 (包括 xij )，且回路
中每行每列只有两个变量
3、求入变量 xi*j* 的最大值及新基变量的解
– 从 xij出发，沿任一个方向对回路拐角上的基变量依此标,?”
和,+”，表示,?”和,+” xij, 从而迭代后仍满足分配的
平衡
– 标有,?”的变量中最小者就是 出变量 xi*j*, 对应 xi*j*的值就
是所 求入变量 xij 的最大值
– 标有,?”的变量减去 xi*j*,标有,+”的变量加上 xi*j*
4、用位势法求新基变量的检验数
– 若所有 zij ? wij ? 0，则达到最优，算法停止；否则返回 1
12
例 3.2.1 踏石法，以最低费用法所得初始解开始编号 运费表 { z ij / w ij } u i 分配表 { x ij }
- 2 / 20 2 / 11 3 0 / 6 3 5 5
I 5 9 10 7 / 2 10 3 3 4 ? x
24 10
- 1 / 18 3 / 7 4 1 4 3 + 12 ? 15
v j ? 5 ? 1 0 ? 3 3 3 12 12
编号 运费表 { z ij / w ij } u i 分配表 { x ij }
3 / 20 7 / 11 3 0 / 6 ? 2 5 5
II 5 9 5 / 1 0 2 0 3 3 ? 4 + 10
4 / 18 8 / 7 4 1 ? 1 x
32 7 8
? 15
v j 5 9 5 2 3 3 12 12
编号 运费表 { z ij / w ij } u i 分配表 { x ij }
3 / 20 6 / 11 3 0 / 6 ? 1 5 5
III 5 8 / 9 5 / 1 0 2 1 3 7 10
4 / 18 7 4 1 0 3 7 5 15
v j 4 7 4 1 3 3 12 12
答,最优解如上分配表,OBJ=98
OBJ=121
OBJ=101
13
3.3 运输问题迭代中的一些具体问题
3.3.1 闭合回路的画法
– 从入变量 xij出发，遇到某个基变量则选一个方向拐角，若不能再遇
到其它基变量，则返回上一拐角，换一个方向走，采用 深探法
– 闭合回路不一定是矩形
3.3.2 产销不平衡
– 供过于求，即 ?ai > ?bj, 增加一个虚收点 Dn+1,bn+1= ?ai - ?bj,令
wi,n+1=0,i=1,2,…,m
– 供小于求，即 ?ai < ?bj, 增加一个虚发点 Wm+1,am+1= ?bj - ?ai,
令 wm+1,j=0,j=1,2,…,n
3.3.3 关于退化问题
1、初始解退化。 即所求初始基变量的个数少于 m+n?1。必须
补足基变量的个数，否则不能正常解出 m+n个 ui 和 vj
– 所补基变量的值为 0,补充的原则,(1)尽量先选运费小的实变量 ；
(2)补充后不能有某个基变量独占一行一列
14
3.3.3 关于退化问题
2、迭代过程中出现退化
– 闭合回路中标有,?”的基变量同时有多个达到最小
– 变换后，有多个原基变量变为 0，选运费最大者为 出变量,其
余保留在新的基础解中
– 退化较严重时，可能会出现多次迭代只有值为 0 的基变量在
转移。此时，一要耐心，二要正确选择出变量
踏石法迭代中需注意的问题：
1、错误地将分配表中基变量的解代入到运费表中
2、不能正确画闭合回路
3、初始解退化，未能补足基变量的个数。因此在位势法中
多次令某个 ui 或 vj 为 0；
4、在位势法中只能令一个 ui 或 vj 为 0；若不能求出全部 ui
和 vj,说明基变量未选够数或未选对
