产销不平衡的运输问题及其求解方法docx.docx
《产销不平衡的运输问题及其求解方法docx.docx》由会员分享，可在线阅读，更多相关《产销不平衡的运输问题及其求解方法docx.docx（14页珍藏版）》请在冰点文库上搜索。
产销不平衡的运输问题及其求解方法docx
运筹学
（第二版）
刁在筠等编
第3节
第3章运输问题
（继续）
产销不平衡的运输问题及其求解方法
第4节应用举例
高等教育出版社
第3节产销不平衡的运输问题及其求解方法
•前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。
就需要把产销不平衡的问题化成产销平衡的问题。
•当产大于销
mn
亍勺>乞bj
Al>1
运输问题的数学模型可写成
•目标函数:
mn
C・X…
Jj入IJklJ=1
Pn+1
由于总的产量大于销量，就要考虑多伞的物咨#哪-个产地就地储存的问题囂囂礬皓爲储存量，于是有：
1
m
工Xjj=bj（/=1,2,i=l
令:
当m，j=l，・・.，n日寸
当i二1，…，m,j二n+1时’
将其分别代入，得到
tmn+1,mnm
聞z=工Hcijxij=EHc\jxij+i=l>1Z=1>1Z=1
n+l
YXij=ai
满足:
j=\
m
汪Xjj=bj
i=i
n0
n+1
=工巧
J=1
由于这个模型中
mn
工坷=工巧+乞+1i=l丿T
所以这是一个产销平衡的运输问题。
若当产大于销时，
只要增加一个假想的销地j二n+1（实际上是储存），
该销地总需要量为
mn
=1j=l
而在单位运价表中从各产地到假想销地的单位运价为,
：
亠=0就转化成一个产销平衡的运输问题
当销大于产时,
可以在产销平衡表中增加一个假想的产地
i=m+l,该地产量为
nm
Dj-dj
j=l心1
在单位运价表上令从该假想产地到各销地的运价，“•=0同样可以转化为-个产销平衡的运输问题…例2设有三个化肥厂（A,B,C）供应四个地区（I,II,III,IV）的农用化肥。
假定等量的化肥在这些地区使用效果相同。
各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表3-25所示。
试求出总的运费最节省的化肥调拨方案。
表3—25
求地区
化工厂
I
II
III
IV
产量（万吨）
A
16
13
22
17
50
B
14
13
19
15
60
C
19
20
23
/
50
最低需求（万吨）最髙需求（力吨）
70
70
0
30
10不限
・解这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。
根据现有产量，第IV个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。
为了求得平衡，在产销平衡表中增加一个假想的化肥厂D,其年产量为50万吨。
由于各地区的需要量包含两部分，如地区I,其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M（任意大正数），而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。
对凡是需求分两种情况的地区，实际上可按照两个地区看待。
这样可以写岀这个问题的产销平衡表（表3-26）和单位运价表（表3-27）o
产销平衡表（表3-26）,单位运价表（表3-27）
求地区
化工广
I
I
II
III
IV
IV
产量（万吨）
A
B
C
D
5565OOOO
销量（万吨）
30
20
70
30
10
50
求地区
化工广
9
I
99
I
II
III
99
IV
A
16
16
13
22
17
17
B
14
14
13
19
15
15
C
19
19
20
23
M
M
D
M
0
M
0
M
0
根据表上作业法计算，可以求得这个问题的最优
方案如表3-28所示
求地区
化工
I
I
II
III
IV'
IV
产量（万吨）
A
B
C
D
30
20
50
20
0
30
10
30
20
5565
oooo
销量（万吨）
30
20
70
30
10
50
210
第4节应用举例
•由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。
所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。
下面介绍几个典型的例子。
•例3某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机。
已知该厂各季度的生产能力及生产每台柴油机的成本如表3-29所示。
又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。
要求在完成合同的情况下，作出使该厂全年生产（包括储存、维护）费用最小的决策
表3—29
季度
生产能力（台）
单位成本（万元）
I
25
10.8
II
35
11.1
III
30
11.0
IV
10
11.3
解由于每个季度生产出来的柴油机不一定当季交货，所以设Xi•为第i季度生产的用于第j季度交货的柴油机数。
根据合同要求，必须满足
兀[[=10
*12+x22=15
=25
<
x13+x23+x33
+兀24+兀34+兀44=20
又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力,故又有：
兀11+兀12+兀13+兀14'25
兀22+兀23+兀24<35
兀33+兀34-30习4-1°
第i季度生产的用于j季度交货的每台柴油机的实际成本5j应该是该季度单位成本加上储存、维护等费用。
Cij的具体数值见
表3-30
X
I
II
III
IV
I
10.8
10.95
11.10
11.25
11
11.10
11.25
11.40
III
11.00
11.15
IV
11.30
设用％表不该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成：
•目标函数：
Enz二He护^
/=1J=1
•满足
>1
4
1=1
护0显然，这是一个产大于销的运输问题模型。
注意到这个问题中当i>j时，Xj-O,所以应令对应的Cj~M,再加上一个假想的需求D,就可以把这个问题变成含销平衡的运输模型，并写出产销平衡表和单位运价表（合在一起，见表3-31）o
肖地
产土卜、
I
II
III
IV
D
产量
I
10.8
10.95
11.10
11.25
0
25
11
M
11.10
11.25
11.40
0
35
III
M
M
11.00
11.15
0
30
IV
M
M
M
11.30
0
10
销量
10
15
25
20
30
100
•经用表上作业法求解，可得多个最优方案，^3-32中列山最优方案之一。
即第i季应生产25台，10台占季交货，15台II季度交货；II季度生产5台，用于III季度交货;III季度生产30台，其中20台于当季交货，10台于IV季度交货。
IV季度生产10台，于当季交货。
按此方案生产,该厂总的生产（包括储存、维护）的费用为773万元。
表3-32
季度
生产辜
I
II
III
IV
D
产量
I
II
III
IV
10
15
0
5
20
10
10
10
1332OO55
销量
10
15
25
20
30
100
例4某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。
已知各条航线的起点、终点城市及每天航班数
见表3-33o
航线
起点城市
终点城市
每天航班数
1
E
D
3
2
B
C
2
3
A
F
1
4
D
B
1
假定各条航线使用相同型号的船只，又各城市间
的航程天数见表3-340
从、\
A
B
C
D
E
F
A
0
1
2
14
7
7
B
1
0
3
13
8
8
C
2
3
0
15
5
5
D
14
13
15
0
17
20
E
7
8
5
17
0
3
F
7
8
5
20
3
0
又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？
•解该公司所需配备船只分两部分。
•
（1）载货航程需要的周转船只数。
例如航线1,在港口E装货1无E-D航程17天，在D卸货1天，总计19天。
每天3航班，故该航线周转船只需57条。
各条航线周转所需船只数见表3-35o
表3—35
航线
装货天数
航程天数
卸货天数
小计
航班数
需周转船只数
1
1
17
1
19
3
57
2
1
3
1
5
2
10
3
1
7
1
9
1
9
4
1
13
1
15
1
15
•以上累计共需周转船只数91条.
（2）各港口间调度所需船只数。
有些港口每天到达船数多于需要船数，例如港口D,每天到达3条,需求1条；而有些港口到达数少于需求数，例如港口B。
各港口每天余缺船只数的计算见
表3-36o
港口城市
每天到达
每天需求
余缺数
A
0
1
-1
B
1
2
-1
C
2
0
2
D
3
1
2
E
0
3
-3
F
1
0
1
为使配备船只数最少，应做到周转的空船数为最
少。
因此建立以下运输问题，其产销平衡表见
表3-37o
港口
A
B
E
每天多余船只
C
D
F
2
2
1
每天缺少船只
1
1
3
单位运价表应为相应各港口之间的船只航程天数，见表3-38o
港口
A
B
E
C
2
3
5
D
14
13
17
F
7
8
3
用表上作业法求出空船的最优调度方案见
表3~39o
港口
A
B
E
每天多余船只
C
1
1
2
D
1
1
2
F
1
1
每天缺少船只
1
1
3
5
由表3-39知最少需周转的空船数为
2X1+13X1+5X1+17X1+3X1=40条。
这样在不考虑维修、储备等情况下，
该公司至少应配备40+91=131条船。
例5在本章的例1中，如果假定
・①每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；
・②运往各销地的产品可以先运给其中几个销地，再转运给其他销地；
・③除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间转运。
已知各产地、销地、中间转运站及相互之间每吨产品的运价如表3-40所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。
表3-40
项
目
r
匚地
中间转运站
销
地
A!
A2
A3
T1
T2
T3
T4
B1
B2
B3
B4
产
A1
1
3
2
1
4
3
3
11
3
10
地
A2
1
/
3
5
/
2
1
9
2
8
A3
3
/
1
/
2
3
7
4
10
5
中
T1
2
3
1
1
3
2
2
8
4
6
间
T2
1
5
/
1
1
1
4
5
2
7
转
T3
4
/
2
3
1
2
1
8
2
4
运
T4
3
2
3
2
1
2
1
/
2
6
站
B1
3
1
7
2
4
1
1
1
4
2
销
B2
11
9
4
8
5
8
/
1
2
1
地
B3
3
2
10
4
2
2
2
4
2
3
B1
10
8
5
6
7
4
6
2
1
3
•解从表3-40中看岀，从A］到企每吨产品的直接运费为11元，如从A］经A?
运往虽，每吨运价为3+4=7元，从A［经丁2运往企只需1+5二6元，而从A］到：
运费兹少的略径是从A］经A?
B1l!
jB2,令吨产品的运费只需1+1+1=3元。
可见这个问题中从每个产地到各销地之间的运输方案是很多的o为了把这个问题仍当作一般的运输问题处理，可以这样做：
•
（1）由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。
因此把整个问题当作有11个产地和11个销地的扩大的运输问题。
•
（2）对扩大的运输问题建立单位运价表。
方法将表3-40中不可能的运输方案的运价用任意大的正数M代替。
•（3）所有中间转运站的产量等于销量。
由于运费最少时不可能岀现一批物资来回倒运的现象，所以每个转运站的转运数不超过20吨。
可以规定Tl,T2,T3,T4的产量和销量均为20吨。
由于实际的转运量
nm
Dij"，工乂产耳j=i心1
可以在每个约束条件中增加一个松弛变量Xi：
乂订相当于一个虚构的转运站，意义就是自己运给自己。
（20-X"）就是每个转运站的实际转运量，咅］的对应运价Cii二0。
•（4）扩大的运输问题中原来的产地与销地因为也有转运站的作用，所以同样在原来产量与销量的数字上加20吨，即三个厂每天糖果产量改成27,24,29吨，销量均为20吨；四个销售点的每天销量改为23,26,25,26吨,产量均为20吨，同时引进©作为松弛变量。
下面写岀扩大运输问题的产销平衡表与单位运价表（见表3-41）,由于这是一个产销平衡的运输问题，所以可以用表上作业法求解（计算略）
肖地
产±4、
A!
A2
A3
T1
T2
T3
T4
B1
B2
B3
B4
产
丨L
里
A1
0
1
3
2
1
4
3
3
11
3
10
27
A2
1
0
M
3
5
M
2
1
9
2
8
24
A3
3
M
0
1
M
2
3
7
4
10
5
29
T1
2
3
1
0
1
3
2
2
8
4
6
20
T2
1
5
M
1
0
1
1
4
5
2
7
20
T3
4
M
2
3
1
0
2
1
8
2
4
20
T4
3
2
3
2
1
2
0
1
M
2
6
20
B1
3
1
7
2
4
1
1
0
1
4
2
20
B2
11
9
4
8
5
8
M
1
0
2
1
20
B3
3
2
10
4
2
2
2
4
2
0
3
20
B4
10
8
5
6
7
4
6
2
1
3
0
20
销量
20
20
20
20
20
20
20
23
26
25
26
第3章结束
升级会员 