1
第五章第五章 运输问题运输问题
2
主要内容
第一节 运输问题
第二节 转运问题
第三节 生产库存问题
3
例例1. 1. 某公司从两个产地A1、A2将物品运往三个销地
B1、B2、B3，各产地的产量、各销地的销量和各产地
运往各销地每件物品的运费如下表所示，问：应如何
调运可使总运输费用最小？
200150150销量
300556A2
200646A1
产量B3B2B1
一、运输问题
4
56
6
1
2
2
1
3
起始节点
终点节点单位运输成本
200
300
供给
4
6 150
150
200
需求
5
网
络
模
型
5
解：设 xij 为从产地Ai运往销地Bj的运输量，得到
下列运输量表：
200150150销量
300x23x22x21A2
200x13x12x11A1
产量B3B2B1
6 4 6
6 5 5
6
Min 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
. x11+ x12 + x13 ≤ 200
x21 + x22 + x23 ≤ 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij ≥ 0 (i=1, 2；j=1, 2, 3)
7
计算机软件求解
8
运输问题的基本特征
• 从 m 个起点(如工厂) A1, A2 , … , Am 向 n 个终点(如
分销中心) B1 , B2 , … , Bn发送某种货物；
• 起点Ai的供应量为 si，终点Bj的需求量为dj；
• 由Ai 运往 Bj 单位货物的运输成本为Cij；
• 总供应 Σ si与总需求 Σ dj相等，称此运输问题
为平衡运输问题，否则称非平衡运输问题。
9
dn…d2d1需求量
smcmn…cm2cm1Am
…………
s2c2n…c22c21A2
s1c1n…c12c11A1
供应量Bn…B2B1终点
起点
运输问题的图表形式运输问题的图表形式（产销平衡与运价表）
10
1
m
2
n
2
1
3
起始节点
终点节点单位运输成本
S１
S2
Sm
供给 分销路线(弧)
Cmn
Cm1
C1n
C11
d1
d2
d3
dn
需求
运运
输输
问问
题题
的的
网网
络络
模模
型型
11
dn…d2d1需求量
smxmn…xm2xm1Am
…………
s2x2n…x22x21A2
s1x1n…x12x11A1
供应量Bn…B2B1终点
起点
运输问题的决策变量运输问题的决策变量
c11 c12 c1n
c21 c22 c2n
cm1 cm2 cmn
12
Min S = ΣΣ cijxij
xi1 + xi2 + … + xin ≤ si
x1j + x2j + … + xmj = dj
xij ≥ 0(i=1,2, …, m; j=1,2,…,n)
起点供应量约束
终点需求量约束.
运输问题的线性规划模型运输问题的线性规划模型
13
在运输问题的线性规划模型中每个变量只在一
个供给约束条件和一个需求约束条件中出现，且约
束条件中的所有系数不是0就是1。因此，只要所有
的供给和需求都是整数，则最优解一定是整数。
运输问题解的结构运输问题解的结构
14
运输问题的求解方法运输问题的求解方法
z 表上作业法
z 计算机软件求解
15
例例2. 2. 石家庄北方研究院有一、二、三三个小区。
每年分别需要用煤3000、1000、2000吨，由河北
临城、山西盂县两处煤矿负责供应，价格、质量相
同。供应能力分别为1500、4000吨，运价为：
200010003000需要量
1500170165160河北临城
4000175170165山西盂县
产量三区二区一区
（1）试求总运输费用最小的调运方案。
16
解题思路：
显然供给总量小于需求总量，如何解决？
17
解：根据题意，作出产销平衡与运价表：
200010003000需求量
500000虚拟起点
河北临城
4000175170165山西盂县
产量三区二区一区
18
计算机求解结果（1）：
1
2
1
2
3
1500
1500
1000
1500
4000
1500
3000
1000
2000
Min C = 920000
19
解题思路：
显然供给总量小于需求总量，如何解决？
解决方法：
增加一个虚拟起点，以及从虚拟起点到每个终点
的弧，并规定每条从虚拟起点出发的弧表示的单位
成本为零（表示并没有货物从虚拟起点运出）。执
行最优解时，表示正在接收虚拟起点货物的终点就
会发生亏空或产生末满足的需求。
20
（2） 由于需大于供，经研究发现一区需求量可减
少0--200吨，二区必须满足需求量，三区需求量不
少于1700吨，试求总运输费用最小的调运方案。
解题思路：
考虑上述附加条件，如何解决？
21
解：根据题意，作出产销平衡与运价表：
这里 M 代表一个很大的正数，其作用是强迫相应
的 x31、 x33、 x34取值为0。
300170010002002800需求量
5000MM0M虚拟
生产点
1500170170165160160河北临城
4000175175170165165山西盂县
产量新三区三区二区新一区一区
22
1
2
1
2
3
1700
1500
1000
1300
4000
1500
2800
1000
1700
Min C = 922000
计算机求解结果（2）：
23
解题思路：
考虑上述附加条件，如何解决？
解决方法：
给所有不可接受的路线加上一个非常大的目标
函数成本系数。
直接在模型中增加一个约束条件，将希望去除
的变量设为0。
24
（3） 由于需大于供，经研究发现一区需求量可减
少0--300吨，二区必须满足需求量，三区需求量不
少于1600吨，试求总运输费用最小的调运方案。
解题思路：
考虑上述附加条件，如何解决？
25
解：根据题意，作出产销平衡与运价表：
这里 M 代表一个很大的正数，其作用是强迫相应
的 x31、 x33、 x34取值为0。
400160010003002700需求量
5000MM0M虚拟
生产点
1500170170165160160河北临城
4000175175170165165山西盂县
产量新三区三区二区新一区一区
26
1
2
1
2
3
1600
1500
1000
1400
4000
1500
2900
1000
1600
Min C = 921000
计算机求解结果（3）：
27
例例3. 3. 设有A、B、C三个化肥厂供应1、2、3、4四
个地区的农用化肥。假设效果相同，有关成本数据
如下：
试求总费用为最低的化肥调拨方案。
不限307060最高需要量
1007030最低需要量
50---232019C
6015191314B
5017221316A
产量4321
28
解：根据题意，作出产销平衡与运价表：
501030703030销量
6 00M0M0M虚拟点D
5 0MM23201919C
6 0151519131414B
5 0171722131616A
产量4”4’321”1’
29
最低要求必须满足，因此把相应的虚设产地运
费取为 M ，而最高要求与最低要求的差允许按需
要安排，因此把相应的虚设产地运费取为 0 。对应
4”的销量 50 是考虑问题本身适当取的数据（生产
量160-最低需求110），根据产销平衡要求确定 D的
产量为 60。
30
二、转运问题二、转运问题
在许多实际问题中，把商品从
产地直接运到销地可能并不是最合
理的，许多运输问题往往具有更为
复杂的运输途径。
31
如在产地和销地之间可以设置若干中转站
(现有的产地和销地也可以作为中转站)。商
品在到达最终销地之前可以经由不同的中转
站转运：产地→转运站、转运站→销地、
产地→产地、产地→销地、销地→转运
站、销地→销地等。
32
也就是说，在每对产地和销地
之间还存在若干不同的转运路线。
这类问题就称为转运问题。
33
转运问题的网络模型转运问题的网络模型
分发路线
（弧）
S1
S2
供给 需求
C13
C24
C14
C23
C28
C35
C48
工厂
（开始节
点）
仓库
（转载节
点）
1
2
8
7
6
5
3
4
零售商
（终点节点）
d5
d6
d7
d8
34
转运问题是运输问题的扩充，包括：
起始节点、转运节点、终点节点。
将各中转站分别视为产地和销地。
目标：确定在网络中每一个弧应该运
送多少单位货物，而使所有终点节点
的需求都得到满足并使运输成本最
小。
35
例例4. 4. 腾飞电子仪器公司在广州(1)和大连(2)有
两个分厂生产同一种仪器，大连分厂每月生产
400台，广州分厂每月生产600台。该公司在上
海(3)和天津(4)有两个销售公司负责对南京(5)、
济南(6)、南昌(7)、青岛(8)四个城市的仪器供
应。另外因为大连距离青岛较近，公司同意大
连分厂向青岛直接供货，运输费用如下图。问
应该如何调运仪器，可使总运输费用最低？
36
37
决策变量：
xij 为从 i 到 j 的运输量
目标函数：
Min f = 所有可能的运输费用
= 运输单价与运输量乘积之和
= 2x13+ 3x14+ 3x23+ x24+ 4x28+ 2x35
+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+
6x47+ 5x48
38
约束条件：
x13+ x14 ≤ 600 (广州分厂供应量限制）
x23+ x24+ x28 ≤ 400 (大连分厂供应量限制）
-x13- x23 + x35 + x36+ x37 + x38 = 0
（上海销售公司，转运站）
-x14- x24 + x45 + x46+ x47 + x48 = 0
（天津销售公司，转运站）
x35+ x45 = 200 （南京的销量）
x36+ x46 = 150 （济南的销量）
x37+ x47 = 350 （南昌的销量）
x38+ x48 + x28 = 300 （青岛的销量）
xij ≥ 0 , i,j = 1,2,3,4,5,6,7,8
39
约束条件：
对起始节点：
输出量 - 输入量 = 产量
对转运节点：
输入量 - 输出量 = 0
对终点节点：
输入量 - 输出量 = 销量
40
转运问题的线性规划模型转运问题的线性规划模型
Min S = ΣΣ cijxij
.
起点节点
转运节点
终点节点
Xij ≥ 0 对所有的i和j
iXij Xij s−∑ ∑
运出弧 运入弧
＝
0Xij Xij−∑ ∑
运出弧 运入弧
＝
jXij Xij d−∑ ∑
运入弧 运弧
＝
所有可能的运输费用之和
41
例例5. 5. 某厂按合同规定须于当年每个季度末分
别提供10、15、25、20台同一规格的柴油
机。已知该厂各季度的生产能力及生产每台柴
油机的成本如下表。如果生产出来的柴油机当
季不交货，每台每积压一个季度需储存、维护
等费用万元。试求在完成合同的情况下，
使该厂全年生产总费用为最小的决策方案。
三、生产库存问题三、生产库存问题
42
10
30
35
25
生产能力
（台）
四季度
三季度
二季度
一季度
需求量
（台）
单位成本
（万元）
43
分析：把第 i 季度生产的柴油机数目看
作第 i 个工厂的产量；把第 j 季度交货
的柴油机数目看作第 j 个销售点的销
量；成本加储存、维护等费用看作运
费，则可构造如下的产销平衡问题。
44
网络模型网络模型
45
20251510销量
第四
季度
第三
季度
第二
季度
第一
季度
产量第四季度第三季度第二季度第一季度
产销平衡与运价表产销平衡与运价表
00？？ M?M?
46
20251510销量
第四
季度
第三
季度
第二
季度
第一
季度
产量第四季度第三季度第二季度第一季度
产销平衡与运价表产销平衡与运价表
47
解：设 xij为第 i 季度生产的第 j 季度
交货的柴油机数目，则目标函数为：
Min f = x11 + x12 + x13
+ x14 + x22 + x23
+ x24 + x33 + x34 + x44
48
约束条件应满足：
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 = 20
交
货：
生
产：
49
例例6. 6. 光明仪器厂生产电脑绣花机是以产定销
的。已知1至6月份各月的生产能力、合同销
量和单台电脑绣花机平均生产费用见下表：
50
月份
13103401005月份
13160401004月份
月份
147510502月份
1510410601月份
单台费用
（万元）
销量
（台）
加班生产能
力（台）
正常生产能
力（台）
51
已知上年末库存103台绣花机，如果当月
生产出来的机器当月不交货，则需要运到分
厂库房，每台增加运输成本万元，每台机
器每月的平均仓储费、维护费为万元。在
7--8月份销售淡季，全厂停产1个月，因此在6
月份完成销售合同后还要留出库存80台。加
班生产机器每台增加成本1万元。问应如何安
排1--6月份的生产，可使总的生产费用（包括
运输、仓储、维护）最少？
52
解： 这个生产存储问题可化为运输问题来做。
1）1--6月份合计生产能力为 640+103=743
台，销量为 627+80=707台；
2）上年末库存103台，只有仓储费和运输
费，把它列为0行；
3）6月份的需求除70台销量外，还要80台
库存，其需求应为70+80=150台；
4）1--6表示1--6月份正常生产情况，1’—
—6’表示1--6月份加班生产情况。
53
产销平衡与运价表：
15010316011575104销量
’
’
’
’
’
’
加班产量正常产量6月5月4月3月2月1月
