钢管订购和运输的规划模型.doc

编辑文本
钢管订购和运输的规划模型
陈丹妮
摘要：本文就天然气管道钢管的订购和运输问题，建立了使订购和运输总费用最小的优化模型.我们把计算分为订货和铁路，公路费用的计算及管道上运输费用的计算两个部分.对第一部分的计算，我们采用了增减约束条件的方法，避免了求解一组多分支规划的繁重的计算.对第二部分的计算，我们综合各种可能情况作出比较，从而使计算简化，并求出了最优的钢管订购和运输计划.对于第二问，我们把每个钢厂的销价及生产上限在一定范围内浮动，观察比较得出钢厂钢管的销价的变化对购运计划和总费用影响最大，钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大.在第三问中运用第一问的方法建立模型，同样求出了铁路，公路和管道构成网络时总费用最小的钢管订购和运输计划.

一 题的重述
要铺设一条的输送天然气的主管道.经筛选后可以生产这种主管道钢管的钢厂有.连接钢厂（i=1,…,15）和的有铁路和公路.沿管道或者原来有公路，或者建有施工公路.一个钢厂如果承担制造这种钢管，至少需要生产500个单位.已知钢厂在指定期限内能生产该钢管的最大数量，钢管出厂销价及1单位钢管的铁路运价和公路运输费.钢管不只是运到点 而是管道全线.问如何制定一个主管道钢管的订购和运输计划，使总费用最小；哪个钢厂的销价变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对可以计划和总费用的影响最大；如果要铺设的管道不是一条线，而是一个树形图，铁路，公路和管道构成网络，如何建立相应的模型和如何求解.
A1
3
2
5
80
10
10
31
20
12
42
70
10
88
10
70
62
70
30
20
20
30
450
104
301
750
606
194
205
201
680
480
300
220
210
420
500
600
3060
195
202
720
690
520
170
690
462
160
320
160
110
290
1150
1100
1200
A2
A3
A4
A5
A6A11
A711A11
A8A11
A911A11
A10
A11
A12
A13
A14
A15
S1
S2
S3
S4
S5
S6
S7
图一

.
编辑文本
A1
3
2
5
80
10
10
31
20
12
42
70
10
88
10
70
62
70
30
20
20
30
450
104
301
750
606
194
205
201
680
480
300
220
210
420
500
600
3060
195
202
720
690
520
170
690
462
160
320
160
110
290
1150
1100
1200
A19
130
190
260
100
A2
A3
A4
A5
A6
A7
A8A11
A9
A10
A11
A12
A13
A14
A15
S1
S2
S3
S4
S5
S6
S7
A16
A17
A18
A20
(A21)
图二
二 本假设与符号约定
1) 1km主管道钢管称为1单位钢管；
2) 假设在钢厂的订购货量为个单位；
3) 对于图一，铁路和公路相交的车站从左到右分别记为；
4) 对于图二，铁路和公路相交的车站或者铁路和管道相交的车站从左到右分别记为；
5) 假设钢厂流经站的钢管量为个单位；
6) 假设处的到货量为；
7) 假设1单位钢管从钢厂运到的运价为；
8) 钢厂在指定期限内能生产该钢管的最大数量是个单位；
9) 钢管出厂销价1单位钢管为万元；
10) 假设铁路运费是整段计算的（从货物上车到下车一次性收费），二不是分段计算；
11) 沿管道公路的运费计算与其他公路一致，且不考虑流量限制的问题.
三 问题的分析
从图上可以看出，各钢厂订购的钢管必先经铁路或公路运往主管道与公路的各节点上再沿主管道进行运输和铺设.因此，我们可以把运输的总费用分为在非管道（铁路或公路）上的运输费用和主管道上的运输费用两部分来计算.
.
编辑文本
对于非管道上的运输.由于钢厂承担制造钢管后至少生产500个单位，所以对于每一个钢厂来说，订购量要么为0，要么就大于或等于500个单位，这就构成一组个的多分支线性规划问题，计算将非常复杂.但我们可以采用如下办法简化计算：对所有钢厂的产量先不设下限进行求解，若解出来的订购量都符合不小于500个单位的情况则为可行解，若解出来的订购量中有不为0的，但小于500个单位，则在约束条件中加进这个订购量的下限进行求解，直至得出符合条件的最优解.
对于管道上的钢管运输铺设的费用则比较复杂，钢管从一个点出发，可以单纯沿管道公路进行运输，也可以一边运输一边铺设，要使运输费最优是类似一次规划的非线性规划问题，由于变量多，计算量大，因此要进行一定的简化.
我们现证明一重要结论：当管道上各节点的钢管量等于与节点相连接的两边管道总长度的一半时，管道上钢管的运输费最小.
设运价为y，运量为x,y是x的函数，并且有（其中路程单位为km）.假设一段长为S的路程，量为x的钢管从其中一端点出发，y-x的关系如图所示：
y y y
kx ks kx

k(x-s)
0 x s x 0 s x 0 s x

运费g即是图中阴影部分的面积.
当x<s时，，
当x=s时，，
当x>s时，，
容易看出，当x>s时，对g来求导有：，推出为稳定点.在[0,s]区间上，
所以当时，费用是最小的，由此方法我们计算出管线上的最小运输费t=61593.275万元.
四 模型的建立和求解
.
编辑文本
1,通过上面的分析，我们首先先令各钢厂订购的钢管运往各节点的铁（公）路运费和订购费最优，然后我们把各钢厂订购的钢管分成17份分别运往与公路相连的火车站.由于铁路轨道成树状分布，所以这样的最优路线是确定的.通过对图一的分析，我们发现， 这四段管道路有这样的情况：1单位钢管从这些管道路之一运过的运费，比从连结该管道路两端点的最短的公（铁）路线运过的运费要高.也就是说，与其将钢管经过这些管道路运输，不如发生“倒运”.因此，这些管道路左右两边的钢管存货应该要满足两边管道铺设的需要，而不应该经这四段管道路进行货物调送.根据前面的假设，我们列出如下以铁（公）路运费和订购费为目标函数的线性规划：

s.t

.
编辑文本

由于只对作非负限制时，计算出低于下界500，所以需另加约束条件
重新求解得：f=1015556, .这
样，我们得到各节点的钢管量，然后一边运输一边铺设这些钢管，求出所需运费为 q=366409.05万元，所以这样的运输方案得到的总费用为m=1381965.05万元.
对于这个方案我们还要进行调整.由上面的讨论我们知道，当管道上各节点的钢管量刚好等于与节点相连接的两边管道总长度的一半时，在管道上的运输费用最小.我们把
（）＝
( 0, 254.5, 525.5, 678, 400, 199.5, 203, 440.5, 580, 390, 260, 215, 315, 460, 250 ) 作为约束
条件加进上述规划中，解得m’=13066563万元，可见这样的运输方案更优.我们可以再考虑把各钢厂的钢管运到各节点后，再通过运输调整到运输最小时分钢量分布.调整的运输费用为
.
其中是1单位钢管从到沿管线运输的价格，是从到沿管线的钢管运输量.
因此我们又得到如下规划
其中，
s.t （加上一规划约束条件中的（1）至（16）及（25））

.
编辑文本

用Maple软件解得：
F=1203697.575,
经过比较，我们认为这个订购和运输的方案是最优的.由此可得详细的订运方案如下：
（1）7个钢厂的订购量分别为.
（2）钢厂的钢管分3批运输，第一批197个单位运往，第二批400个单位运到，第三批203个单位直接沿公路运到.钢厂的钢管分两批运输，第一批359.5个单位运往，另一批经运到.钢厂的钢管也分两批运输，第一批420个单位经 运到，另一批580个单位经运往.钢厂的钢管分六批运输，第一批45个单位运往,第二批166个单位运往，第三批61个单位运往，第四批199.5个单位经运到，第五批390单位运到，第六批260个单位运往.钢厂的钢管分三批运输，第一批115个单位往，第二批315个单位往，第三批420个单位直接沿公路运往.钢厂的钢管全部直接运到.
2，根据我们建立的模型，保持其它条件不变，令各个钢厂的钢管销价上浮或下降5％，可得到总费用的变化幅度和运购计划的变化情况，如下表：
项目
p1上调5%
最小值
1209827
变幅
6400（0.53%）
x1
800
x2
800
x3
1000
x4
0
x5
1181
x6
890
x7
500
下调5%
1197297
-6400（0.5%）
800
800
1000
0
1181
890
500
P2上调5%
1209897
6199（0.5%）
800
800
1000
0
791
1280
500
下调5%
1197497
6200（5.2%）
800
800
1000
0
1181
890
500

.
编辑文本
P3上调5%
1211447
7749（6.4%）
800
800
1000
0
1181
890
500
下调5%
1195947
-7750（6.4%）
800
800
1000
0
791
1280
500
P4上调5%
1203697
0
800
800
1000
0
790
1280
500
下调5%
1203697
0
800
800
1000
0
1181
890
500
P5上调5%
1208322
4625（3.8%）
800
800
1000
0
200
1871
500
下调5%
1208322
4625（3.8%）
800
800
1000
0
200
1871
500
P6上调5%
1210372
6675（5.5%）
800
800
1000
0
1181
890
500
下调5%
1210372
6675（5.5%）
800
800
1000
0
1181
890
500
P7上调5%
1207697
4000（3.3%）
800
800
1000
0
791
1280
500
下调5%
1199697
-4000（3.3%）
800
800
1000
0
1181
890
500
从上表比较可得，钢厂的钢管销价的变化对总费用及购运计划影响最大.
用同样的方法，保持其他条件不变，令各个钢厂钢管产量的上限上浮或下降10%，得出总费用和购运计划的变化情况：
项目
最小值
变幅
X1
X2
X3
X4
X5
X6
X7
S1上调10%
1195457
-8240(0.69%)
880
800
1000
0
1101
890
500
下调10%
1211937
8240(0.68%)
720
800
1000
0
1261
890
500
S2上调10%
1200497
-3200(0.27%)
800
880
1000
0
1101
890
500
下调10%
1206897
3200(0.27%)
800
720
1000
0
1261
890
500
S3上调10%
1201197
2500(0.21%)
800
800
1100
0
1081
890
500
下调10%
1206197
2500(0.21%)
800
800
900
0
1281
890
500
S5上调10%
1203697
0
800
800
1000
0
791
1280
500
下调10%
1203697
0
800
800
1000
0
1181
890
500

.
编辑文本
S6上调10%
1203697
0
800
800
1000
0
1181
890
500
下调10%
1203697
0
800
800
1000
0
791
1280
500
S7上调10%
1203697
0
800
800
1000
0
1181
890
500
下调10%
1203697
0
800
800
1000
0
1181
890
500
同样由上表可得出，钢厂的钢管产量的上限的变化对总费用及购运计划的影响最大.
3、如图二，要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络.管道运输最优时各个的存钢量为

对于这三个兼为火（汽）车中转站的点，我们把它们一分为二看待.以为例，一方面看成的货物由此经过，一方面看成，其钢管量为与之相连接的两段管道总长度的一半，并且钢管直接从它运到主管道.根据第一问的做法，先把的钢管量预置成L的数量值，这样沿主管道的运输费用就能降到最低，在此基础上对各钢厂的定货量及其分流方式进行调配.然后，使用第一问的方法列
出线性规划如下：

.
编辑文本

初次求解结果，，因此我们加入约束条件，再次求解：

最小费用 （万元），其中e是当节点上的钢管量取自中的数值时，仿照问题一中的计算方法所得出的管道上的运输费用，万元.
五 模型的优缺点分析及其推广
我们建立的模型具有较强的可行性和可操作性，并且具有相当的实际意义.虽然我们未能对多个分支规划组逐个进行求解从而得出最优解，但我们对模型进行了适当的近似简化处理，减少了计算量和计算难度，最后得出可行解.我们建立模型的方法和思想对其它类似题材也适用，在建筑运输方面适用性较强，并可以推广到社会生活中相关的多个领域中去.对于类似的问题，对模型的决策性因素加以具体对
照分析即可.

参考文献：
[1]程里文，吴江，张玉林，运筹学模型与方法教程，清华大学出版社，北京，2000
[2]L.库珀，U.N勃哈特，L.J勒布朗（美），运筹学模型概论，上海科学技术出版社，上海，1987
[3]刘宝碇，赵瑞清，随机规划与模糊规划，清华大学出版社，北京，1998
[4]李世奇，杜慧琴，Maple计算机代数系统应用及程序设计，重庆大学出版社，1999.

（文章编辑：黄绮玲\颜学友）

接83页
.
编辑文本

Dij
S1
S2
S3
S4
S5
S6
S7
A1
0
0
0
0
0
0
0
A2
160.3
205.3
220.3
250.3
245.3
255.3
265.3
A3
140.2
190.2
200.2
235.2
225.2
235.2
245.3
A4
98.6
171.6
181.6
216.6
206.6
216.6
226.6
A5
38
111
121
156
146
156
166
A6
20.5
95.5
105.5
140.5
130.5
140.5
150.5
A7
3.1
88.1
98.1
133.1
123.1
133.1
143.1
A8
21.2
71.2
86.2
116.2
111.2
121.2
131.2
A9
64.2
114.2
48.2
84.2
79.2
84.2
99.2
A10
92
142
82
62
57
57
77
A11
96
146
86
51
33
51
66
A12
106
156
96
61
51
61
71
A13
121.2
171.2
111.2
76.2
71.2
26.2
38.2
A14
128
178
118
83
73
11
26
A15
142
192
132
97
87
28
2
A16
60
110
44
80
75
80
95
A17
95
145
85
50
32
47
65
A18
100
150
90
55
50
33
50
A19
105
155
95
60
50
36
55
A20
115
165
105
70
65
10
32
A21
125
175
115
80
75
0
26
(表2：从厂家Si运1单位钢管往Aj的最小路费)（图2）
感谢您的支持与配合，我们会努力把内容做得更好！

.