求解钢管订购和运输问题数学模型结业-本科论文.doc

《数学模型》课程结业论文

题 目
钢管订购与运输
院 系
理学院
专 业
信息与计算科学
学 号

学生姓名

任课教师
单锋

沈阳航空航天大学

2013年4月
任务及要求
任 务 书

[要求]
1、将所给的问题翻译成汉语；
2、给论文起个题目（名字或标题）
3、根据任务来完成数学模型论文；
4、论文书写格式要求按给定要求书写；
5、态度要认真，要独立思考，独立完成任务；
6、论文上交时间：5月30日前（要求交纸质论文和电子文档）。
7、严禁抄袭行为，若发现抄袭，则成绩记为“不及格”。

[任务]
钢管订购和运输
要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
为方便计，1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：

1
2
3
4
5
6
7

800
800
1000
2000
2000
2000
3000

160
155
155
160
155
150
160

1单位钢管的铁路运价如下表：

里程(km)
≤300
301～350
351～400
401～450
451～500
运价(万元)
20
23
26
29
32

里程(km)
501～600
601～700
701～800
801～900
901～1000
运价(万元)
37
44
50
55
60

1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。
（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。
（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。
（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（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)
图二

成 绩 评 定 单
评语：

成绩
任课教师签字 年 月 日

I

摘要
摘 要
本文讨论了在铺设天然气管道的过程中如何合理订购与运输钢管以使总费用最小的优化问题。
问题一是在一定约束条件下以钢管订购和运输的总费用为目标函数的非线性规划问题。总费用由订购钢管的总费用、从钢厂到站点运输钢管的总费用及从站点开始铺设钢管的总费用三部分组成。订购钢管的总费用和从钢厂到各站点运输钢管的总费用分别通过在各厂购买量与各厂出厂销价和各厂购买量与从各钢厂到各站点运输单位钢管的最小费用的线性规划运算得到。从站点开始铺设钢管的总费用通过等差数列求和得到。在求从钢厂到站点的运输钢管的总费用时，关键是采用弗洛伊德算法，用MATLAB软件编程求出单位钢管从各钢厂运往各站点最小运输费用。利用LINGO软件求解此模型，得到钢管订购与运输的最小费用。
问题二是对问题一模型的灵敏度分析，通过控制变量法的方法即每次只让一家钢厂的销价或生产线发生变化并且每次的变化是相同，分别得出各变量对购运计划的影响。
问题三是对问题一的推广，要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，在问题一的模型中又增加了一些约束条件和变量，同时在目标函数中增加相应的铺设费用。利用LINGO软件编程求解新的模型。

关键词：非线性规划；弗洛伊德算法；灵敏度分析；

目录
目 录
钢管订购与运输 1
1.1 问题提出 1
1.2 模型假设 3
1.3 符号说明 4
1.4 问题一的模型建立：求钢管订购和运输最小运费 4
1.5 问题一的求解 5
2.1问题二的模型建立：钢管销价变化对购运计划的影响。 6
2.2问题二的求解 6
3.1问题三的模型建立：直线管道向管道网变化时的购运计划 7
3.2题三的求解 9
4．优缺点改进 9
5．参考文献 10
6．附录 10

数学模型课程结业论文
钢管订购与运输
1.1 问题提出

要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
为方便计，1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：

1
2
3
4
5
6
7

800
800
1000
2000
2000
2000
3000

160
155
155
160
155
150
160

1单位钢管的铁路运价如下表：

里程(km)
≤300
301～350
351～400
401～450
451～500
运价(万元)
20
23
26
29
32

里程(km)
501～600
601～700
701～800
801～900
901～1000
运价(万元)
37
44
50
55
60

1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。
（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。
（2）请就（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
图一
（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（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
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.2 模型假设
1.模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，
如不计换车、转站的时间和费用，不计装卸费用等。
2.要铺设的管道侧有公路，可运输所需钢管。
2.钢管单价与订购量、订购次数、订购日期无关,即在钢管订购与运输过程中，钢管的单价保持不变。
3.将每一单位的管道所在地看成一个需求点，向以单位管道的所在地运输钢管即向一个点运输钢管。
4.钢管在运送和使用中没有损耗。
5.不计运输时由于运输工具出现故障等意外事故引起工期延误造成损失。

1.3 符号说明

第个工厂

第个钢厂的钢管最大生产数

由到的最小路运费用

由到的钢管的运量

由向段路线铺设的长度

由向段路线铺设的长度

运输总费用

第个钢厂每单位的钢管运价

表示0-1变量

的长度
1.4 问题一的模型建立：求钢管订购和运输最小运费
问题一的模型：
如上文分析所述，我们采用Floyd算法，用matlab编程求出单位钢管从运输到的最小费用，具体数据如表1：
表1 最优路径单位钢管运输费用

S1
S2
S3
S4
S5
S6
S7

170.7
215.7
230.7
260.7
255.7
265.7
275.7

160.3
205.3
220.3
250.3
245.3
255.3
265.3

140.2
190.2
200.2
235.2
225.2
235.2
245.2

98.6
171.6
181.6
216.6
206.6
216.6
226.6

38
111
121
156
146
156
166

20.5
95.5
105.5
140.5
130.5
140.5
150.5

3.1
86
96
131
121
131
141

21.2
71.2
86.2
116.2
111.2
121.2
131.2

64.2
114.2
48.2
84.2
79.2
84.2
99.2

92
142
82
62
57
62
76

96
146
86
51
33
51
66

106
156
96
61
51
45
56

121.2
171.2
111.2
76.2
71.2
26.2
38.2

128
178
118
83
73
11
26

142
192
132
97
87
28
2

目标函数为，表示钢管运输所需的费用，我们通过非线性规划求出问题的模型如下：

1.5 问题一的求解
所以根据上述的模型，得运输总费用最小为1278632（万元）. 具体的购运计划和铺设方案如表2，表3
表2 问题一的订购和调运方案

订购量
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
S1
800
0
0
40
295
200
265
0
0
0
0
0
0
0
0
S2
800
179
0
0
321
0
0
300
0
0
0
0
0
0
0
S3
1000
0
0
336
0
0
0
0
664
0
0
0
0
0
0
S4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
S5
1015
0
508
92
0
0
0
0
0
0
415
0
0
0
0
S6
1556
0
0
0
0
0
0
0
0
351
0
86
333
621
165
S7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

表3 问题一的铺设方案

0.000000
0.000000

104.0000
75.00000

226.0000
282.0000

468.0000
0.000000

606.0000
9.500000

184.5000
15.50000

189.5000
76.00000

125.0000
175.0000

505.0000
159.0000

321.0000
30.00000

270.0000
145.0000

75.00000
11.00000

199.0000
134.0000

286.0000
335.0000

165.0000
0.000000

2.1问题二的模型建立：钢管销价变化对购运计划的影响。
1．讨论钢厂钢管的销售价格变化对购运计划和总费用的影响
当钢厂钢管销售价格变化时，会对购运计划和总费用造成影响. 为了更好地观察每一个钢厂钢管销售价格所造成的影响，采用比较法，即每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化.
2.2问题二的求解
我们将各个钢厂单位钢管的销价分别增加1万元和减少1万元，借助LINGO软件得出相应的总费用、运输方案、订购方案变化情况如表4、表5所示
表4 各个钢厂单位钢管的销价分别增加1万元
钢厂
总费用
总费用变化量
运输方案变化量
订购方案变化量
S1
1279432
800
0
0
S2
1279432
800
0
0
S3
1279632
1000
0
0
S4
1278632
0
0
0
S5
1279639
1007
40
30
S6
1279834
1202
712
712
S7
1278632
0
0
0

表5 各个钢厂单位钢管的销价分别减少1万元
钢厂
总费用
总费用变化量
运输方案变化量
订购方案变化量
S1
1277832
800
0
0
S2
1277832
800
0
0
S3
1277632
1000
0
0
S4
1278632
0
0
0
S5
1277263
1369
712
712
S6
1277068
1564
40
30
S7
1278632
0
0
0
由上述表格观察分析可得： 钢厂销价变化对总费用影响最大，钢厂钢管的销价的变化对购运计划影响最大.
2．讨论钢厂钢管产量的上限的变化对购运计划和总费用的影响
同样采用比较法，即每次只让一个钢厂钢管产量的上限的发生相同的变化，其余钢厂钢管产量的上限不发生变化. 将各个钢厂的产量的上限分别增加100个单位和减少100个单位，分别计算，得到购运计划和总费用变化情况如表6、表9所示.

表6 各个钢厂钢管的产量的上限分别增加100个单位
钢厂
总费用
总费用变化量
运输方案变化量
订购方案变化量
S1
1268332
10300
218
200
S2
1275132
3500
404
200
S3
1276132
2500
1786
200
S4
1278632
0
0
0
S5
1278632
0
0
0
S6
1278632
0
844
0
S7
1278632
0
0
0

表9 各个钢厂钢管的产量的上限分别减少100个单位
钢厂
总费用
总费用变化量
运输方案变化量
订购方案变化量
S1
1288932
10300
260
200
S2
1282132
3500
1244
200
S3
1281132
2500
200
200
S4
1278632
0
0
0
S5
1278632
0
0
0
S6
1278632
0
0
0
S7
1278632
0
0
0
由上述表格观察分析可得：钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小。
3.1问题三的模型建立：直线管道向管道网变化时的购运计划
问题三与问题一非常类似，其主要区别在于问题三中将线性的管道铺设线变成了树形的铺设线路，多增加了几个节点。当主管道由直线变为树形图，铁路、公路和管道构成的网络时，求从钢厂运单位钢管到主管道结点的最小费用的算法仍旧适用，因此，我们仿照问题一中的思路，求出最小运费表，如表10：

表10 问题三的最小运费表

S1
S2
S3
S4
S5
S6
S7

170.7
215.7
230.7
260.7
255.7
265.7
275.7

160.3
205.3
220.3
250.3
245.3
255.3
265.3

140.2
190.2
200.2
235.2
225.2
235.2
245.2

98.6
171.6
181.6
216.6
206.6
216.6
226.6

38
111
121
156
146
156
166

20.5
95.5
105.5
140.5
130.5
140.5
150.5

3.1
86
96
131
121
131
141

21.2
71.2
86.2
116.2
111.2
121.2
131.2

64.2
114.2
48.2
84.2
79.2
84.2
99.2

92
142
82
62
57
62
76

96
146
86
51
33
51
66

106
156
96
61
51
45
56

121.2
171.2
111.2
76.2
71.2
26.2
38.2

128
178
118
83
73
11
26

142
192
132
97
87
28
2

(i=1,..,7)
3.2题三的求解

费用
800
800
1000
0
1303
2000
0
1406330

得到最优最小费用为万元。
4．优缺点改进
由于总费用由订购费用和运输费用部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成. 利用求网络中最短路径的弗洛伊德方法得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径），算出两点之间的最优路径，进而根据非线性规划，借助于Lingo软件求解即可求出相应的结果.
1．优点
1）本问题中运用了求网络中最短路径的弗洛伊德思想，改进和修改得到新的算法，可对含多种权重计算方式的网络进行搜索，算出两点之间的最优路径，计算结果准确，从而得出相应的购运单价的矩阵.
2）本问题构造出的模型算法较简单，也可以运用相应的其他编程软件来得到比较满意的结果.
3）本模型计算步骤清晰，借助于Lingo软件求解，可靠性较高.
2．缺点
1）由于题意中不考虑铁路公路间转运的中转费用，也不限制转运次数，因此在算法设计中存在着考虑不周全的缺限，如我们考虑是先通过铁路再通过公路到铺设点，但这不一定是最小费用路径，有可能先通过公路，然后经铁路再经公路运到铺设点，费用更少，这里没有理论证明.
2) 问题二要求根据问题一的分析,指出哪家钢厂销价的变化对购运计划和总费用影响最大，哪家钢厂钢管产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果. 这个问题属于规划问题的灵敏度分析，在此模型中，只是通过说明销价增加一万元，减少一万元来说明，并没有给出一般的理论说明。
3．模型改进
这个数学模型可以应用于西部开发中“西气东送”问题，当然，西部开发中“西气东送”问题远比我们的假设还要复杂的多，但无论如何，他们的本质一样，我们可将本问题运用于时间的变化等范围的推广。文还可以把问题1归结为网络最小费用流问题，建立了线性和非线性最小费用流模型，并运用相应的解法和分支定界法求解，简洁，层次分明。

5．参考文献
1．《数学模型》 单峰 朱丽梅 田贺民 国防工业出版社
2.《运筹学教程》 胡运权 清华大学出版社
3.《MATLAB程序设计与应用》 刘卫国 中国水利水电出版社
6．附录
附录一：
Floyd算法函数在matlab下的M函数文件如下：
function [D,path]=floyd(a)
n=size(a,1);
D=a;path=zeros(n,n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k);
end
end
end
end
附录二：
ab=[1 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 20 22 23];
bb=[ 14 15 15 16 19 18 23 24 10 10 11 15 13 14 16 17 19 19 20 21 22 23 24];
w=[20 202 1200 690 690 462 70 30 450 80 1150 1100 306 195 720 520 170 88 160 70 320 160 290];
ab1=[1 2 4 5 6 7 8 9 10 11 14 15 16 17 18 33 34 35];
bb1=[19 20 21 22 23 24 25 26 27 28 29 30 31 31 19 24 31 32];
w1=[3 2 600 10 5 10 12 42 70 10 10 62 30 20 104 31 110 20];
a=sparse(ab,bb,w);
a(24,24)=0;
a=a+a';
a=full(a);
for i=1:24
for j=1:24
if(a(i,j)==0&i~=j)
a(i,j)=inf;
end
end
end
[D,path]=floyd(a);
a1=sparse(ab1,bb1,w1);
a1(35,35)=0;
a1=a1+(a1)';
a1=full(a1);
for i=1:35
for j=1:35
if(a1(i,j)==0&i~=j)
a1(i,j)=inf;
end
end
end
[D1,path1]=floyd(a1);

%距离转换为费用的程序

D1=D1*0.1; %把公路最短距离换算成公路最少费用
for k=1:300
m1(k)={k};
end
for k=1:50
m2(k)={300+k};
m3(k)={350+k};
m4(k)={400+k};
m5(k)={450+k};
end
for k=1:100
m6(k)={500+k};
m7(k)={600+k};
m8(k)={700+k};
m9(k)={800+k};
m0(k)={900+k};
end
for i=1:24
for j=1:24 %把铁路最短距离换算成铁路最少费用
switch D(i,j)
case 0
D(i,j)=0;
case m1
D(i,j)=20;
case m2
D(i,j)=23;
case m3
D(i,j)=26;
case m4
D(i,j)=29;
case m5
D(i,j)=32;
case m6
D(i,j)=37;
case m7
D(i,j)=44;
case m8
D(i,j)=50;
case m9
D(i,j)=55;
case m0
D(i,j)=60;
otherwise
D(i,j)=ceil((D(i,j)-1000)/100)*5+60;
end
end
end

%c矩阵表示七个钢管生产厂到十五个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用 for 循环求出最小值
c=20000*ones(7,15);

for i=1:7 %7个钢管生产厂
for k=18:32 %15个铺设节点
for j=8:24 %7个钢管生产厂和17个中转点，i=1，表示第一个钢管生产厂，j=8，表示第一个中转点
if c(i,k-17)>D(i,j)+D1(j-7,k)
c(i,k-17)=D(i,j)+D1(j-7,k);
%对于所有中转点，在铁路网和公路网上的下标相差8
end
end
end
end
for i=1:7
for k=18:32
if c(i,k-17)>D(i,1)+D1(33,k)
c(i,k-17)=D(i,1)+D1(33,k);
%33代表第一个钢管生产厂S1点
end
if c(i,k-17)>D(i,6)+D1(34,k)
c(i,k-17)=D(i,6)+D1(34,k);
%34代表第六个钢管生产厂S6点
end
if c(i,k-17)>D(i,7)+D1(35,k)
c(i,k-17)=D(i,7)+D1(35,k);
%35代表第七个钢管生产厂S7点
end
end
%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理
end

13