2006/3
--第 3章 运输问题 --
--1--
2006/3
--第 3章 运输问题 --
--2--
第三章 运输问题
Transportation problem
2006/3
--第 3章 运输问题 --
--3--
3.1 运输问题的典例和数学模型
一、典例：
某食品公司经营糖果业务，公司下设三个工厂 A1,A2、
A3，四个销售门市部 B1,B2,B3,B4。已知每天各自的生产
量、销售量及调运时的单位运输费用情况。问：如何调运可
使总费用最小？
生产量,A1—— 7吨,A2 —— 4吨,A3 —— 9吨
销售量,B1 —— 3吨,B2 —— 6吨,B3 —— 5吨,B4 —— 6吨
产地
销地
B1 B2 B3 B4
A1
A2
A3
3 11 3 10
1 9 2 8
7 4 10 5
2006/3
--第 3章 运输问题 --
--4--
调运示意图
A1
A2
A3
B1
B2
B3
B4
7吨
4吨
9吨
3吨
6吨
5吨
6吨
x11
x34
产
地
销
地
2006/3
--第 3章 运输问题 --
--5--
二、建立模型
设 xij—— 第 i产地到第 j销地之间的调运量，则有
Min z = ? ? cij·xij3 4
i=1 j=1
x11+x12+x13+x14=7 x11+x21+x31=3
xij?0,(i=1,2,┄,3； j=1,2,┄,4)
产
量
限
制
销
量
限
制
x21+x22+x23+x24=4
x31+x32+x33+x34=9
x12+x22+x32=6
x13+x23+x33=5
x14+x24+x34=6
2006/3
--第 3章 运输问题 --
--6--
一般模型表示：
设有个 m产地,n个销地，其中第 i个产地的产量为 ai，第 j个
销地的销量为 bj，且 ??ai=?bj。若第 i个产地到第 j个销地每调运单
位物资的运费为 cij，则使总费用最少的调运模型为：
Min z = ? ? cij·xijn
i=1 j=1
m
m)1,2,.,,,(i
1
???
?
a in
j
ijx
n),.,,,1,2j ; m,,,,1,2,(i 0
n),.,,,1,2(j
1
???
???
?
x ij
j
m
i
ij bx
2006/3
--第 3章 运输问题 --
--7--
三、模型的特点
1.变量数,m?n个
2.约束方程数,m+n个
最大独立方程数,m+n-1
3.系数列向量结构：
Pij=
0···
·
1···
1···
0
—— 第 i个分量
—— 第 m+j个分量
2006/3
--第 3章 运输问题 --
--8--
x11 x12 ······ x1n x21 x22 ······ x2n,············,xm1 xm2 ······ xmn
1 1 ······ 1 0 0 ······ 0 ············ 0 0 ······ 0
0 0 ······ 0 1 1 ······ 1 ············ 0 0 ······ 0
0 0 ······ 0 0 0 ······ 0 ············ 1 1 ······ 1
1 0 ······ 0 1 0 ······ 0 ············ 1 0 ······ 0
0 1 ······ 0 0 1 ······ 0 ············ 0 1 ······ 0
0 0 ······ 1 0 0 ······ 1 ············ 0 0 ······ 1
i=1
i=2
i=m
j=1
j=2
j=n
············ ············ ············
············ ············ ············
······ ······ ······
······ ······ ······
2006/3
--第 3章 运输问题 --
--9--
3.2 运输问题的表上作业算法和程序求解
表上作业法步骤, 初始方案 ?最优性检验 ?改进方案
一、初始方案的确定
1.最小元素法
2.Vogel法
二、最优性检验
1.闭回路法
2.位势法
三、方案改进方法
在 闭回路 内改进。
2006/3
--第 3章 运输问题 --
--10--
A1
A2
A3
B1 B2 B3 B4
A1
A2
A3
B1 B2 B3 B4
A1
A2
A3
B1 B2 B3 B4
产量
销量
3 11 3 10
1 9 2 8
7 4 10 5 6
3
4 3
1
3
3 6 5 6
7
4
9
3 6 5 6
7
4
9
产量
销量
3
6 3
5 2
1
(1) (2)
(1) (-1)
(10) (12)
△ z=c11-c13+c23-c21=1=?11
△ z=c12-c14+c24-c22=2=?12 (0) (2)
(2)
(9)
(1)
(12)
单位运价表产销平衡表
2006/3
--第 3章 运输问题 --
--11--
A1
A2
A3
B1 B2 B3 B4
7
4
9
产量
销量 3 6 5 6
6 3
5 2
13
A1
A2
A3
B1 B2 B3 B4 行两最小元素之差
列两
最小
元素
之差
3 11 3 10
1 9 2 8
7 4 10 5
0
1
1
2 5 1 3
0
1
2
2 - 1 3
0
1
-
2 - 1 2
7
6
-
- - 1 2
Vogel法,
产销平衡表
2006/3
--第 3章 运输问题 --
--12--
A1
A2
A3
B1 B1 B3 B4
3 10
1 8
4 5
位势法,
(3) (9)
(7)
(-2)
(1)
(-2)
2.计算行位势和列位势；
令 u1=1，则依 cij=ui+vj 计算各
ui和 vj
3.计算空格处位势；
?ij=ui+vj
行位势
列位势
1
2
-1
-4
28 9
4.计算空格处检验数：
?ij=cij- ?ij
1.数字格处上添上对应的运价；
A1
A2
A3
B1 B1 B3 B4
3 11 3 10
1 9 2 8
7 4 10 5
单位运价表位势表,
2006/3
--第 3章 运输问题 --
--13--
A1
A2
A3
B1 B1 B3 B4
7
4
9
产量
销量 3 6 5 6
6 3
5 2
13
(0) (2)
(2)
(9)
(1)
(12)
检验数表
2006/3
--第 3章 运输问题 --
--14--
程序求解：
(1) 使用 LINDO程序求解, 同求解 LP模型。
(2) 使用 EXCEL求解：
2006/3
--第 3章 运输问题 --
--15--
3.3 产销不平衡运输问题及其应用
Min z= ? ? cij·xijn
i=1j=1
m
m)1,2,.,,,(i
1
???
?
a in
j
ijx
n) 1,.,,,j ; m,,,,1,(i 0
n),.,,,1,2(j
1
???
???
?
x ij
j
m
i
ij bx
一、产销不平衡问题
1?产 ?销
Min z= ? ? cij·xij+?0?xi,n+1
n
i=1 j=1
m
m)1,2,.,,,(i 1
1
????
?
a in
j
ijx
1)nn,1,.,,,j ; m,,,,1,(i 0
1)nn,,.,,,1,2(j
1
????
????
?
x ij
j
m
i
ij bx
i=1
m
2006/3
--第 3章 运输问题 --
--16--
产地 销地
A1
A2
┊
Am
B1 B2 ┈ Bn
C11 C12 ┈ C1n
C21 C22 ┈ C2n
┆ ┊ ┈ ┊
Cm1 Cm2 ┈ Cmn
Bn+1
０
０
┆
０
产＞销问题单位运价表
销量
产量
b1 b2 ┈ bn
a1
a2
┊
am
?ai??bj
2006/3
--第 3章 运输问题 --
--17--
Min z= ? ? cij·xijn
i=1j=1
m
m)1,2,.,,,(i
1
???
?
a in
j
ijx
n) 1,.,,,j ; m,,,,1,(i 0
n),.,,,1,2(j
1
???
???
?
x ij
j
m
i
ij bx
2?销 ?产
Min z= ? ?cij·xij +?0?xm+1,jn
i=1 j=1
m
1)mm,1,2,.,,,(i
1
????
?
a in
j
ijx
n) 1,.,,,j ; 1mm,.,,,1,(i 0
n),.,,,1,2(j
1
1
????
???
?
?
x ij
j
m
i
ij bx
j=1
n
2006/3
--第 3章 运输问题 --
--18--
产地 销地
A1
A2
┊
Am
B1 B2 ┈ Bn
C11 C12 ┈ C1n
C21 C22 ┈ C2n
┆ ┊ ┈ ┊
Cm1 Cm2 ┈ Cmn
Am+1
销＞产问题单位运价表
0 0 ┈ 0
销量
产量
b1 b2 ┈ bn
a1
a2
┊
am
?bj??ai
2006/3
--第 3章 运输问题 --
--19--
例一：某工厂按合同规定
必须于当年的每个季度末
分别提供 10,15,25,20
台同一规格的柴油机。已
知该厂的生产能力及生产
每台柴油机的成本如表示。
又如果生产出来的柴油机
当季不交货，每台每积压
一个季度需要存储维护费
用 0.15万元。要求在完成
合同的情况下，做出使全
年生产费用最小的决策。
季
度
生产能力
(台 )
单位成本
(万元 /台 )
Ⅰ
Ⅱ
Ⅲ
Ⅳ
25
35
30
10
10.8
11.1
11.0
11.3
二、应用模型
2006/3
--第 3章 运输问题 --
--20--
模型：
设 xij?? 第 i季度生产，用于第 j季度交货的数量。
obj,min z= ??cij xij
i=1j=1
4 4
x11+x12+x13+x14?25
x22+x23+x24?35
x33+x34?30
x44?10
x11 =10
x12+x22 =15
x13+x23+x33 =25
x14+x24+x34+x44=20x
ij? 0,(i=1,··,4;j=1,··,4)
供应,Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
需求：
2006/3
--第 3章 运输问题 --
--21--
单位费用表：
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅰ Ⅱ Ⅲ Ⅳ
10.8 10.95 11.10 11.25
M 11.10 11.25 11.40
M M 11.00 11.15
M M M 11.30
单位：万元
供应 需求
2006/3
--第 3章 运输问题 --
--22--
例二：
某餐馆承办宴会，每晚连续举行，共举行五次。
宴会上需用特殊的餐巾，根据参加的人数，预计每
晚的需要量为：第一天 1000条，第二天 700条，第三
天 800条，第四天 1200条，第五天 1500条，五天之后，
所有的餐巾作废。宴会中用过的餐巾经过洗涤处理
后可以重复使用，这样可以降低使用成本。已知每
条新餐巾需要 1元的费用，送洗时可选择两种方式：
快洗仅需要一天时间，每条洗涤费用为 0.2元，慢洗
需要两天时间，每条洗涤费用 0.1元。问：如何安排，
可使总费用最低？
2006/3
--第 3章 运输问题 --
--23--
建立模型：
设 xj— 第 j天使用新毛巾的数量； yij— 第 i天送第 j天使用快洗
餐巾的数量； zij— 第 i天送第 j天使用慢洗餐巾的数量；
第一天,x1=1000
第二天,x2+y12=700
第三天,x3+z13+y23=800
第四天,x4+z14+z24+y34=1200
第五天,x5+z15+z25+z35+y45=1500
需
求
约
束
供
应
约
束
新购餐巾,x1+x2+x3+x4+x5?5200
第一天送洗,y12+z13+z14+z15?1000
第二天送洗,y23+z24+z25?700
第三天送洗,y34+z35?800
第四天送洗,y45?1200
xj?0,yij?0,zij?0，（ i=1,┈,4 ； j=1,┈,5 ）
Min z=∑ xj+∑∑ 0.2yij+∑∑ 0.1zij
2006/3
--第 3章 运输问题 --
--24--
新 购
第一天
第二天
第三天
第四天
Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ
1 1 1 1 1 0
M 0.2 0.1 0.1 0.1 0
M M 0.2 0.1 0.1 0
M M M 0.2 0.1 0
供应 需求 产量
销 量
5200
1000
700
800
1200M M M 0.2 0.1 0
1000 700 800 1200 1500 3700
产销平衡表
2006/3
--第 3章 运输问题 --
--25--
例三：
有 A,B,C三个化肥厂供应四个地区 Ⅰ, Ⅱ, Ⅲ, Ⅳ 的农用化肥，
三个工厂每年各自的产量为 A--50万吨,B--60万吨,C--50万吨。四个
地区的需求量分别是 Ⅰ 地区最高 50万吨，最低 30万吨,Ⅱ 地区为 70万
吨,Ⅲ 地区为 30万吨以下,Ⅳ 地区不低于 10万吨。问：如何调运，可
使总的调运费用最小？单位调运费用如下表所示。
A1
A2
A3
B1 B2 B3 B4 产量
销量
16 13 22 17
14 13 19 15
19 20 23 ―
单位运价表
50
60
50
30-50 70 0-30 10-
单位：万元 /万吨
设 xij--第 i工厂
调至第 j需求地区
的化肥数量
2006/3
--第 3章 运输问题 --
--26--
A
B
C
D
Ⅰ ? Ⅰ ?? Ⅱ Ⅲ Ⅳ ? Ⅳ ??
16 16 13 22 17 17
14 14 13 19 15 15
19 19 20 23 M M
M 0 M 0 M 0
供应 需求 产量
销 量
50
60
50
50
30 20 70 30 10 50
产销平衡表
2006/3
--第 3章 运输问题 --
--27--
三、扩大的运输问题
例：在前面的例题中，若既可以从 Ai运到 Bj，也可以经过中间站
T1,T2,T3,T4或者 Ai,Bj转运，称扩大的运输问题。
几点说明：
1.所有的产地、销地、中间站均视作产地、销地；
2.转运量可定位总的产量之和；
3.不能出现循环倒运现象，允许自身往自身最多调运一次，
运价为 Cij=0；
4.实际产地产量为转运量与该产地实际产量之和，实际销地
销量为转运量与实际销量之和。
2006/3
--第 3章 运输问题 --
--28--
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4
A1
A2
A3
T1
T2
T3
T4
B1
B2
B3
B4
0 1 3
1 0 -
3 - 0
2 1 4 3
3 5 - 2
1 - 2 3
3 11 3 10
1 9 2 8
7 4 10 5
2 3 1
1 5 -
4 - 2
3 2 3
3 1 7
11 9 4
3 2 10
10 8 5
0 1 3 2
1 0 1 1
3 1 0 2
2 1 2 0
2 8 4 6
4 5 2 7
1 8 2 4
1 - 2 6
2 4 1 1
8 5 8 -
4 2 2 2
6 7 4 6
0 1 4 2
1 0 2 1
4 2 0 3
2 1 3 0
产 销 产量
销量
27
24
29
20
20
20
20
20
20
20
20
20 20 20 20 20 20 20 23 26 25 26
产销平衡表
--第 3章 运输问题 --
--1--
2006/3
--第 3章 运输问题 --
--2--
第三章 运输问题
Transportation problem
2006/3
--第 3章 运输问题 --
--3--
3.1 运输问题的典例和数学模型
一、典例：
某食品公司经营糖果业务，公司下设三个工厂 A1,A2、
A3，四个销售门市部 B1,B2,B3,B4。已知每天各自的生产
量、销售量及调运时的单位运输费用情况。问：如何调运可
使总费用最小？
生产量,A1—— 7吨,A2 —— 4吨,A3 —— 9吨
销售量,B1 —— 3吨,B2 —— 6吨,B3 —— 5吨,B4 —— 6吨
产地
销地
B1 B2 B3 B4
A1
A2
A3
3 11 3 10
1 9 2 8
7 4 10 5
2006/3
--第 3章 运输问题 --
--4--
调运示意图
A1
A2
A3
B1
B2
B3
B4
7吨
4吨
9吨
3吨
6吨
5吨
6吨
x11
x34
产
地
销
地
2006/3
--第 3章 运输问题 --
--5--
二、建立模型
设 xij—— 第 i产地到第 j销地之间的调运量，则有
Min z = ? ? cij·xij3 4
i=1 j=1
x11+x12+x13+x14=7 x11+x21+x31=3
xij?0,(i=1,2,┄,3； j=1,2,┄,4)
产
量
限
制
销
量
限
制
x21+x22+x23+x24=4
x31+x32+x33+x34=9
x12+x22+x32=6
x13+x23+x33=5
x14+x24+x34=6
2006/3
--第 3章 运输问题 --
--6--
一般模型表示：
设有个 m产地,n个销地，其中第 i个产地的产量为 ai，第 j个
销地的销量为 bj，且 ??ai=?bj。若第 i个产地到第 j个销地每调运单
位物资的运费为 cij，则使总费用最少的调运模型为：
Min z = ? ? cij·xijn
i=1 j=1
m
m)1,2,.,,,(i
1
???
?
a in
j
ijx
n),.,,,1,2j ; m,,,,1,2,(i 0
n),.,,,1,2(j
1
???
???
?
x ij
j
m
i
ij bx
2006/3
--第 3章 运输问题 --
--7--
三、模型的特点
1.变量数,m?n个
2.约束方程数,m+n个
最大独立方程数,m+n-1
3.系数列向量结构：
Pij=
0···
·
1···
1···
0
—— 第 i个分量
—— 第 m+j个分量
2006/3
--第 3章 运输问题 --
--8--
x11 x12 ······ x1n x21 x22 ······ x2n,············,xm1 xm2 ······ xmn
1 1 ······ 1 0 0 ······ 0 ············ 0 0 ······ 0
0 0 ······ 0 1 1 ······ 1 ············ 0 0 ······ 0
0 0 ······ 0 0 0 ······ 0 ············ 1 1 ······ 1
1 0 ······ 0 1 0 ······ 0 ············ 1 0 ······ 0
0 1 ······ 0 0 1 ······ 0 ············ 0 1 ······ 0
0 0 ······ 1 0 0 ······ 1 ············ 0 0 ······ 1
i=1
i=2
i=m
j=1
j=2
j=n
············ ············ ············
············ ············ ············
······ ······ ······
······ ······ ······
2006/3
--第 3章 运输问题 --
--9--
3.2 运输问题的表上作业算法和程序求解
表上作业法步骤, 初始方案 ?最优性检验 ?改进方案
一、初始方案的确定
1.最小元素法
2.Vogel法
二、最优性检验
1.闭回路法
2.位势法
三、方案改进方法
在 闭回路 内改进。
2006/3
--第 3章 运输问题 --
--10--
A1
A2
A3
B1 B2 B3 B4
A1
A2
A3
B1 B2 B3 B4
A1
A2
A3
B1 B2 B3 B4
产量
销量
3 11 3 10
1 9 2 8
7 4 10 5 6
3
4 3
1
3
3 6 5 6
7
4
9
3 6 5 6
7
4
9
产量
销量
3
6 3
5 2
1
(1) (2)
(1) (-1)
(10) (12)
△ z=c11-c13+c23-c21=1=?11
△ z=c12-c14+c24-c22=2=?12 (0) (2)
(2)
(9)
(1)
(12)
单位运价表产销平衡表
2006/3
--第 3章 运输问题 --
--11--
A1
A2
A3
B1 B2 B3 B4
7
4
9
产量
销量 3 6 5 6
6 3
5 2
13
A1
A2
A3
B1 B2 B3 B4 行两最小元素之差
列两
最小
元素
之差
3 11 3 10
1 9 2 8
7 4 10 5
0
1
1
2 5 1 3
0
1
2
2 - 1 3
0
1
-
2 - 1 2
7
6
-
- - 1 2
Vogel法,
产销平衡表
2006/3
--第 3章 运输问题 --
--12--
A1
A2
A3
B1 B1 B3 B4
3 10
1 8
4 5
位势法,
(3) (9)
(7)
(-2)
(1)
(-2)
2.计算行位势和列位势；
令 u1=1，则依 cij=ui+vj 计算各
ui和 vj
3.计算空格处位势；
?ij=ui+vj
行位势
列位势
1
2
-1
-4
28 9
4.计算空格处检验数：
?ij=cij- ?ij
1.数字格处上添上对应的运价；
A1
A2
A3
B1 B1 B3 B4
3 11 3 10
1 9 2 8
7 4 10 5
单位运价表位势表,
2006/3
--第 3章 运输问题 --
--13--
A1
A2
A3
B1 B1 B3 B4
7
4
9
产量
销量 3 6 5 6
6 3
5 2
13
(0) (2)
(2)
(9)
(1)
(12)
检验数表
2006/3
--第 3章 运输问题 --
--14--
程序求解：
(1) 使用 LINDO程序求解, 同求解 LP模型。
(2) 使用 EXCEL求解：
2006/3
--第 3章 运输问题 --
--15--
3.3 产销不平衡运输问题及其应用
Min z= ? ? cij·xijn
i=1j=1
m
m)1,2,.,,,(i
1
???
?
a in
j
ijx
n) 1,.,,,j ; m,,,,1,(i 0
n),.,,,1,2(j
1
???
???
?
x ij
j
m
i
ij bx
一、产销不平衡问题
1?产 ?销
Min z= ? ? cij·xij+?0?xi,n+1
n
i=1 j=1
m
m)1,2,.,,,(i 1
1
????
?
a in
j
ijx
1)nn,1,.,,,j ; m,,,,1,(i 0
1)nn,,.,,,1,2(j
1
????
????
?
x ij
j
m
i
ij bx
i=1
m
2006/3
--第 3章 运输问题 --
--16--
产地 销地
A1
A2
┊
Am
B1 B2 ┈ Bn
C11 C12 ┈ C1n
C21 C22 ┈ C2n
┆ ┊ ┈ ┊
Cm1 Cm2 ┈ Cmn
Bn+1
０
０
┆
０
产＞销问题单位运价表
销量
产量
b1 b2 ┈ bn
a1
a2
┊
am
?ai??bj
2006/3
--第 3章 运输问题 --
--17--
Min z= ? ? cij·xijn
i=1j=1
m
m)1,2,.,,,(i
1
???
?
a in
j
ijx
n) 1,.,,,j ; m,,,,1,(i 0
n),.,,,1,2(j
1
???
???
?
x ij
j
m
i
ij bx
2?销 ?产
Min z= ? ?cij·xij +?0?xm+1,jn
i=1 j=1
m
1)mm,1,2,.,,,(i
1
????
?
a in
j
ijx
n) 1,.,,,j ; 1mm,.,,,1,(i 0
n),.,,,1,2(j
1
1
????
???
?
?
x ij
j
m
i
ij bx
j=1
n
2006/3
--第 3章 运输问题 --
--18--
产地 销地
A1
A2
┊
Am
B1 B2 ┈ Bn
C11 C12 ┈ C1n
C21 C22 ┈ C2n
┆ ┊ ┈ ┊
Cm1 Cm2 ┈ Cmn
Am+1
销＞产问题单位运价表
0 0 ┈ 0
销量
产量
b1 b2 ┈ bn
a1
a2
┊
am
?bj??ai
2006/3
--第 3章 运输问题 --
--19--
例一：某工厂按合同规定
必须于当年的每个季度末
分别提供 10,15,25,20
台同一规格的柴油机。已
知该厂的生产能力及生产
每台柴油机的成本如表示。
又如果生产出来的柴油机
当季不交货，每台每积压
一个季度需要存储维护费
用 0.15万元。要求在完成
合同的情况下，做出使全
年生产费用最小的决策。
季
度
生产能力
(台 )
单位成本
(万元 /台 )
Ⅰ
Ⅱ
Ⅲ
Ⅳ
25
35
30
10
10.8
11.1
11.0
11.3
二、应用模型
2006/3
--第 3章 运输问题 --
--20--
模型：
设 xij?? 第 i季度生产，用于第 j季度交货的数量。
obj,min z= ??cij xij
i=1j=1
4 4
x11+x12+x13+x14?25
x22+x23+x24?35
x33+x34?30
x44?10
x11 =10
x12+x22 =15
x13+x23+x33 =25
x14+x24+x34+x44=20x
ij? 0,(i=1,··,4;j=1,··,4)
供应,Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
需求：
2006/3
--第 3章 运输问题 --
--21--
单位费用表：
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅰ Ⅱ Ⅲ Ⅳ
10.8 10.95 11.10 11.25
M 11.10 11.25 11.40
M M 11.00 11.15
M M M 11.30
单位：万元
供应 需求
2006/3
--第 3章 运输问题 --
--22--
例二：
某餐馆承办宴会，每晚连续举行，共举行五次。
宴会上需用特殊的餐巾，根据参加的人数，预计每
晚的需要量为：第一天 1000条，第二天 700条，第三
天 800条，第四天 1200条，第五天 1500条，五天之后，
所有的餐巾作废。宴会中用过的餐巾经过洗涤处理
后可以重复使用，这样可以降低使用成本。已知每
条新餐巾需要 1元的费用，送洗时可选择两种方式：
快洗仅需要一天时间，每条洗涤费用为 0.2元，慢洗
需要两天时间，每条洗涤费用 0.1元。问：如何安排，
可使总费用最低？
2006/3
--第 3章 运输问题 --
--23--
建立模型：
设 xj— 第 j天使用新毛巾的数量； yij— 第 i天送第 j天使用快洗
餐巾的数量； zij— 第 i天送第 j天使用慢洗餐巾的数量；
第一天,x1=1000
第二天,x2+y12=700
第三天,x3+z13+y23=800
第四天,x4+z14+z24+y34=1200
第五天,x5+z15+z25+z35+y45=1500
需
求
约
束
供
应
约
束
新购餐巾,x1+x2+x3+x4+x5?5200
第一天送洗,y12+z13+z14+z15?1000
第二天送洗,y23+z24+z25?700
第三天送洗,y34+z35?800
第四天送洗,y45?1200
xj?0,yij?0,zij?0，（ i=1,┈,4 ； j=1,┈,5 ）
Min z=∑ xj+∑∑ 0.2yij+∑∑ 0.1zij
2006/3
--第 3章 运输问题 --
--24--
新 购
第一天
第二天
第三天
第四天
Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ
1 1 1 1 1 0
M 0.2 0.1 0.1 0.1 0
M M 0.2 0.1 0.1 0
M M M 0.2 0.1 0
供应 需求 产量
销 量
5200
1000
700
800
1200M M M 0.2 0.1 0
1000 700 800 1200 1500 3700
产销平衡表
2006/3
--第 3章 运输问题 --
--25--
例三：
有 A,B,C三个化肥厂供应四个地区 Ⅰ, Ⅱ, Ⅲ, Ⅳ 的农用化肥，
三个工厂每年各自的产量为 A--50万吨,B--60万吨,C--50万吨。四个
地区的需求量分别是 Ⅰ 地区最高 50万吨，最低 30万吨,Ⅱ 地区为 70万
吨,Ⅲ 地区为 30万吨以下,Ⅳ 地区不低于 10万吨。问：如何调运，可
使总的调运费用最小？单位调运费用如下表所示。
A1
A2
A3
B1 B2 B3 B4 产量
销量
16 13 22 17
14 13 19 15
19 20 23 ―
单位运价表
50
60
50
30-50 70 0-30 10-
单位：万元 /万吨
设 xij--第 i工厂
调至第 j需求地区
的化肥数量
2006/3
--第 3章 运输问题 --
--26--
A
B
C
D
Ⅰ ? Ⅰ ?? Ⅱ Ⅲ Ⅳ ? Ⅳ ??
16 16 13 22 17 17
14 14 13 19 15 15
19 19 20 23 M M
M 0 M 0 M 0
供应 需求 产量
销 量
50
60
50
50
30 20 70 30 10 50
产销平衡表
2006/3
--第 3章 运输问题 --
--27--
三、扩大的运输问题
例：在前面的例题中，若既可以从 Ai运到 Bj，也可以经过中间站
T1,T2,T3,T4或者 Ai,Bj转运，称扩大的运输问题。
几点说明：
1.所有的产地、销地、中间站均视作产地、销地；
2.转运量可定位总的产量之和；
3.不能出现循环倒运现象，允许自身往自身最多调运一次，
运价为 Cij=0；
4.实际产地产量为转运量与该产地实际产量之和，实际销地
销量为转运量与实际销量之和。
2006/3
--第 3章 运输问题 --
--28--
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4
A1
A2
A3
T1
T2
T3
T4
B1
B2
B3
B4
0 1 3
1 0 -
3 - 0
2 1 4 3
3 5 - 2
1 - 2 3
3 11 3 10
1 9 2 8
7 4 10 5
2 3 1
1 5 -
4 - 2
3 2 3
3 1 7
11 9 4
3 2 10
10 8 5
0 1 3 2
1 0 1 1
3 1 0 2
2 1 2 0
2 8 4 6
4 5 2 7
1 8 2 4
1 - 2 6
2 4 1 1
8 5 8 -
4 2 2 2
6 7 4 6
0 1 4 2
1 0 2 1
4 2 0 3
2 1 3 0
产 销 产量
销量
27
24
29
20
20
20
20
20
20
20
20
20 20 20 20 20 20 20 23 26 25 26
产销平衡表
