钢管订购和运输论文.doc

承 诺 书
我们仔细阅读了全国大学生数学建模的竞赛规则（）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。
我们的参赛（报名）队号为：32
参赛组别（研究生或本科）：本科
参赛队员 ：兰潇根、柳达强、汪锡平

钢管订购和运输

摘要：本文拟建立一个最合理的钢管运输与铺设方案模型。利用离散数学和数据结构中图论相关知识，应用最短路径的floyd算法和灵敏度分析法建立一个以总费用为目标函数的非线性规划模型， 对于钢管订购和运输的总费用，分为三部分：购买钢管费用，由钢厂运送到站点的费用以及由站点开始铺设的费用，对于由钢厂运送到站点的费用，用Floyd算法，求出铁路网和公路网的最短路径，然后转化为最少运输费用，之后利用Lingo软件编程，求解分析，解决问题。

关键词：Floyd算法，非线性规划，Lingo

精品资料
一 问题重述
要铺设一条的输送天然气的主管道, 如题图一所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位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）的要求给出模型和结果。

二 问题分析
1.问题一
所有的钢管必须通过铁路运送到铺设线路上的站点，之后再通过公路运输向左或右铺设。因此，总的费用由三部分组成：
一部分为购买所有主管道钢管的总费用，一部分为由钢管厂运送到各个站点时的铁路运费和公路运费的总和，最后一部分为由站点向左右两边铺设时的运输费用。
对于从钢管厂到各个站点的最小运费，由于在铁路和公路上的运费计算方法不同，所以，可以先用Floyd算法，求出钢管厂到铁路上任意结点的最小距离和路线，得到相应的单位钢管运费，同理再求出各个站点到公路上任意结点的最小距离和路线，得到相应的单位钢管运费，再将两运费求和求出最小值，于是就得到从某钢厂到某铺设地点运输单位钢管的最少运输费用。

2.问题二
题目中“哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大”可以理解为，当该模型达到最优解时，钢管销价或者产量上限变化一个单位时，对购运计划和总费用的影响的大小问题。可以利用Lingo编程运行得到结果。

3.问题三
要铺设的管道是一个树形图，是题图一的一种延拓，通过观察可知，只有9、11、17站点的铺设方向有三个，其它站点的铺设方向只有左右，因此，可以沿用问题一里的思路，在问题一的基础上再增加一个变量middle（j），用于表示向第三方向铺设的钢管数量。

三 模型的假设与符号说明
1、模型的假设

⑴.沿管道或者原来有公路或者建有施工公路。
⑵ 钢管全部由这7个钢厂生产，一个钢厂如果承担制造这种钢管，至少需要生产500个单位。
⑶ 公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
⑷ 由于公路运输费中，不足整公里部分按整公里计算，因此，从站点向左右两边运送钢管时，不应该是边运送边卸下钢管，这样也不符合实际，应当是走一个单位的公路，卸下一个单位的钢管。

2、符号说明

符号
说明

钢厂在指定期限内能生产该钢管的最大数量

钢厂的钢管出厂单位销价（单位：万元）
cost(i,j)
单位钢管从钢厂运到的最小费用（单位：万元）
l(j)
从 到之间的距离（单位：千米）

n(i,j)
从钢厂运到的钢管数量
left(j)
运到站点向左铺设的钢管数量
right(j)
运到地的钢管向右铺设的钢管数量

middle（j）
运到站点的钢管向第三方向铺设的钢管数量
c(i)=0
钢厂不提供钢管
c(i)=1
钢厂提供钢管

四 模型的建立与求解

（一）、问题一的模型：
采用Floyd算法，用matlab编程可以求出单位钢管从运输到的最小运输费用，数据如下表：

　A1
　A2
　A3
　A4
　A5
　A6
　A7
　A8
　A9
　A10
　A11
　A12
　A13
　A14
　A15
S1　
170.7
160.3
140.2
98.6
38
20.5
3.1
21.2
64.2
92
96
106
121.2
128
142
S2　
215.7
205.3
190.2
171.6
111
95.5
86
71.2
114.2
142
146
156
171.2
178
192
　S3
230.7
220.3
200.2
181.6
121
105.5
96
86.2
48.2
82
86
96
111.2
118
132
　S4
260.7
250.3
235.2
216.6
156
140.5
131
116.2
84.2
62
51
61
76.2
83
97
　S5
255.7
245.3
225.2
206.6
146
130.5
121
111.2
79.2
57
33
51
71.2
73
87
　S6
265.7
255.3
235.2
216.6
156
140.5
131
121.2
84.2
62
51
45
26.2
11
28
　S7
275.7
265.3
245.2
226.6
166
150.5
141
131.2
99.2
76
66
56
38.2
26
2

目标函数为总费用W，包括三个部分，购买所有主管道钢管的费用，将钢管从钢厂运到各个站点的费用，将钢管从站点运到铺设地点的费用
W=++
其中

则目标函数：
minW=++
约束条件：
1. 钢厂的钢管产量：
2. 运到各个站点的钢管刚好用完：
（j=1,2…15）
3. 与之间的钢管： ,
（j=1,2, …,14）
4. 钢管数量的非负性：n(i,j)≥0 , left(j) ≥0 , right(j) ≥0
(i=1,2,…,7 , j=1,2,…,15)
5° 钢管数量的整数性：n(i,j)∈N
运用数学软件Lingo编程求解
问题一的结果
最优最小费用(万元)

（二）、问题二的模型：
用Lingo对问题一求解后，即可根据Lingo的结果对问题二进行解答。
各钢厂销价的变化：

p(1)
p(2)
p(3)
p(4)
p(5)
p(6)
p(7)
对偶价格
-800
-800
-1000
0
-1320
-1250.99
0
对偶价格表示，在最优解的情况下，各钢厂钢管销价减少一个单位时，对总费用的影响。
根据表中的数据，S(5)钢厂钢管的销价对购运计划和总费用影响最大。
产量上限：

s(1)
s(2)
s(3)
s(4)
s5)
s(6)
s(7)
对偶价格
103
35
25
3.33
0
0
16
对偶价格表示，在最优解的情况下，各钢厂钢管生产上限每增加一个单位时，对总费用的影响。
根据表中的数据，得S(1)钢厂钢管的产量上限的变化对购运计划和总费用的影响最大。

（三）、问题三的模型：
采用Floyd算法，用matlab编程求出单位钢管从运输到的最小运输费用，数据如下表：

A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
S1
170.7
160.3
140.2
98.6
38
20.5
3.1
21.2
64.2

92
S2
215.7
205.3
190.2
171.6
111
95.5
86
71.2
114.2
142
S3
230.7
220.3
200.2
181.6
121
105.5
96
86.2
48.2
82
S4
260.7
250.3
235.2
216.6
156
140.5
131
116.2
84.2
62
S5
255.7
245.3
225.2
206.6
146
130.5
121
111.2
79.2
57
S6
260.7
250.3
235.2
216.6
156
140.5
128.1
116.2
84.2
61
S7
275.7
265.3
245.2
226.6
166
150.5
141
131.2
99.2
76
（续表）

A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
A21
S1
96
106
121.2
128
142
60
95
100
105
115
125
S2
146
156
171.2
178
192
110
145
150
155
165
175
S3
86
96
111.2
118
132
44
85
90
95
105
115
S4
51
61
76.2
83
97
80
50
55
60
70
80
S5
33
51
71.2
73
87
75
32
45
50
65
75
S6
47
37
16.2
11
28
80
46
33
36
10
0
S7
64
56
38.2
26
2
95
63
50
55
32
26

由于树形图的出现，发现在站点9、11、17处出现了3条支路的情况。则模型一中模型的变量left(j)，right(j)不再适用，此时可考虑增加一个支路变量middle（j），相应的增加约束条件，在目标函数中增加相应的从站点运到铺设地点的费用。

目标函数：

约束条件：
1. 钢厂的钢管产量：
2. 运到各个站点的钢管刚好用完：
(j=1, …,21且j≠9,11,17)
（j=9,11,17）
3. 与之间的钢管：
（j=1,2, …,14）
middle(9)+left(16)=42 middle(11)+middle(17)=10 left(17)+left(18)=130
right(17)+left(19)=190 right(19)+left(20)=260 right(20)+left(21)=100

4. 钢管数量的非负性：n(i,j)≥0 , left(j) ≥0 ,
right(j) ≥0 ,middle(j) ≥0,(i=1,2,…,7 , j=1,2,…,21)
5.钢管数量的整数性：n(i,j)∈N
运用数学软件Lingo编程求出
问题三的结果：
最优最小费用（万元）

五 模型优缺点
1.该模型通过简化运输网络，采用Floyd算法，具有技巧性和理论的保障。
2.模型的所有运算均由计算机程序完成，误差只由计算机产生，具有精度高的特点。
3.一般的图均可在该模型的基础上完善得出结果，故该模型具有较好的推广性。

六 参考文献

[1] 姜启源、谢金星 《数学模型》（第三版）高等教育出版社 2003
[2] 《Floyd最短路算法的MATLAB程序》

七 附录
问题一：
利用Floyd算法求解各钢管厂到各站点的最小费用路线的matlab程序：
钢厂到铁路网结点的最短距离:
n=24;a=zeros(n);
a(1,2)=450;a(2,3)=80;a(2,4)=1150;a(4,8)=1100;a(5,6)=360;a(6,7)=195;a(7,18)=20;a(8,9)=720;
a(8,18)=202;a(8,19)=1200;a(9,10)=520;a(9,20)=690;a(10,11)=170;a(11,12)=88;a(11,13)=160;
a(11,21)=690;a(12,22)=462;a(13,14)=70;a(13,15)=320;a(15,16)=160;a(16,17)=290;a(16,24)=70;
a(17,24)30;
a=a+a';M=max(max(a))*n^2;%M为充分大的正实数
a=a+((a==0)-eye(n))*M;
path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=k;
end
end
end
end
a, path
站点到公路网结点的最短距离:
n=32;b=zeros(n);
b(1,2)=104;b(2,3)=301;b(2,16)=3;b(3,4)=750;b(3,17)=2;b(4,5)=606;b(4,18)=600;b(5,6)=194;b(5,19)=10;b(6,7)=205;
b(6,20)=5;b(7,21)=10;b(7,22)=31;b(8,23)=12;b(8,9)=680;b(9,10)=480;b(9,24)=42;b(10,11)=300;b(10,25)=70;b(11,26)=10;
b(12,27)=10;b(13,28)=62;b(14,29)=110;b(14,30)=30;b(15,31)=20;b(15,24)=20;
b=b+b';M=mbx(mbx(b))*n^2;%M为充分大的正实数
b=b+((b==0)-eye(n))*M;
path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
if b(i,j)>b(i,k)+b(k,j)
b(i,j)=b(i,k)+b(k,j);
path(i,j)=k;
end
end
end
end
b,path
将最短路程换算成运输费用的程序：

b=b*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
a(i,j)=0;
case m1
a(i,j)=20;
case m2
a(i,j)=23;
case m3
a(i,j)=26;
case m4
a(i,j)=29;
case m5
a(i,j)=32;
case m6
a(i,j)=37;
case m7
a(i,j)=44;
case m8
a(i,j)=50;
case m9
a(i,j)=55;
case m0
a(i,j)=60;
otherwise
a(i,j)=ceil((a(i,j)-1000)/100)*5+60;
end
end
end
各个钢厂到各个站点的最少运输费用的程序

for i=1:7
for k=1:15
for j=8:24
if c(i,k)>a(i,j)+b(k,j+8)
c(i,k)=a(i,j)+b(k,j+8);
end
end
end
end
for i=1:7
for k=1:15
if c(i,k)>a(i,1)+b(k,33)
c(i,k)=a(i,1)+b(k,33);
end
if c(i,k)>a(i,6)+b(k,34)
c(i,k)=a(i,6)+b(k,34);
end
if c(i,k)>a(i,7)+b(k,35)
c(i,k)=a(i,7)+b(k,35);
end
end
end
Lingo程序：
model:
sets:
!七个生产厂c表示是否运输,p表示单位钢管的售价，s表示规定期限内的最大生产能力;
sch/1..7/:p,s,c;
!十五个站点,left表示某站点向左运输的量，right表示某站点向右运输的量,l表示相邻两个站点的距离;
zd/1..15/:left,right,l;
!cost表示最小单位运输费用,x表示某厂到某一处站点的运输量;
link(sch,zd):cost,n;
endsets
data:
s=@file('data.txt');
cost=@file('data.txt');
l=@file('data.txt');
enddata
!目标函数;
min=@sum(link(i,j):n(i,j)*p(i)+n(i,j)*cost(i,j))+0.05*@sumzd(j):left(j)^2+left(j)+right(j)^2+right(j));
!约束条件;
!在第一个和第十五个站点分别不能向左和右铺设;
left(1)=0;
right(15)=0;
!c为0-1约束条件;
@for(sch(i):@bin(c(i)));
!运输量为整数约束;
@gin(@sum(link(i,j):n(i,j)));
!总生产量为铺设管道的长度;
@sum(link(i,j):n(i,j))=5171;
!若生产最低产量为500单位或者不生产，c(i,j)为1，n(i,j)不小于500，c（i,j)为0，n(i,j)为0;
@for(sch(i):@sum(zd(j):n(i,j))>=500*c(i));
!各厂最大产量的约束;
@for(sch(i):@sum(zd(j):n(i,j))<=s(i)*c(i));
!相邻两站点间管道的铺设量为站点间距;
@for(zd(j)|j#le#14:right(j)+left(j+1)=l(j));
!在某站点的运输量为左右铺设量的总和;
@for(zd(j):@sum(sch(i):n(i,j))=left(j)+right(j));
p(1)=160;p(2)=155;p(3)=155;p(4)=160;p(5)=155;p(6)=150;p(7)=160
end

data.txt中的数据：
800,800,1000,2000,2000,2000,3000~
170.7 160.3 140.2 98.6 38.0 20.5 3.1 21.2 64.2 92.0 96.0 106.0 121.2 128.0 142.0
215.7 205.3 190.2 171.6 111.0 95.5 86.0 71.2 114.2 142.0 146.0 156.0 171.2 178.0 192.0
230.7 220.3 200.2 181.6 121.0 105.5 96.0 86.2 48.2 82.0 86.0 96.0 111.2 118.0 132.0
260.7 250.3 235.2 216.6 156.0 140.5 131.0 116.2 84.2 62.0 51.0 61.0 76.2 83.0 97.0
255.7 245.3 225.2 206.6 146.0 130.5 121.0 111.2 79.2 57.0 33.0 51.0 71.2 73.0 87.0
265.7 255.3 235.2 216.6 156.0 140.5 131.0 121.2 84.2 62.0 51.0 45.0 26.2 11.0 28.0
275.7 265.3 245.2 226.6 1660 150.5 141.0 131.2 99.2 77.0 66.0 56.0 38.2 26.0 2.0~
104,301,750,606,194,205,201,680,480,300,220,210,420,500,0~

问题三：
用Floyd算法求铁路最短距离和公路最短距离，matlab编程与问题一相同，再调用程序转化成费用，求出最小值。

Lingo程序：

model:
sets:
!七个生产厂c表示是否运输,p表示单位钢管的售价，s表示规定期限内的最大生产能力;
sch/1..7/:p,s,c;
!十五个站点,left表示某站点向左运输的量right表示某站点向右运输的量,middle表示第三个铺设方向，l表示相邻两个站点的距离;
zd/1..21/:left,right,middle,l;
!cost表示最小单位运输费用,x表示某厂到某一处站点的运输量;
link(sch,zd):cost,n;
endsets
data:
p=@file('data.txt');
s=@file('data.txt');
cost=@file('data.txt');
l=@file('data.txt');
enddata
!目标函数;
min=@sum(link(i,j):n(i,j)*p(i)+n(i,j)*cost(i,j))+0.05*(@sum(zd(j)|j#GE#2 #AND# j#LE#21 :left(j)^2+left(j))+@sum(zd(j)|j#LE#14 :right(j)^2+right(j))+@sum(zd(j)|j#EQ#9 #OR# j#EQ#11 #OR# j#EQ#17 :middle(j)^2+middle(j))+@sum(zd(j)|j#EQ#17 #OR# j#EQ#19 #OR# j#EQ#20 :right(j)^2+right(j)));
!约束条件;
!c为0-1约束条件;
@for(sch(i):@bin(c(i)));
!运输量为整数约束;
@gin(@sum(link(i,j):n(i,j)));
!若生产最低产量为500单位或者不生产，c(i,j)为1，n(i,j)不小于500，c（i,j)为0，n(i,j)为0;
@for(sch(i):@sum(zd(j):n(i,j))>=500*c(i));
!各厂最大产量的约束;
@for(sch(i):@sum(zd(j):n(i,j))<=s(i)*c(i));
!没有第三个铺设方向的站点;
@for(zd(j)|j#ne#9 #and# j#ne#11 #and# j#ne#17:middle(j)=0);
!相邻两站点间管道的铺设量为站点间距;
@for(zd(j)|j#lt#15:right(j)+left(j+1)=l(j));
!在某站点的运输量为左右铺设量的总和;
@for(zd(j):@sum(sch(i):n(i,j))=left(j)+right(j)+middle(j));
l(16)=middle(9)+left(16);l(17)=middle(11)+middle(17);
l(18)=left(17)+left(18);l(19)=right(17)+left(19);
l(20)=right(19)+left(20);l(21)=right(20)+left(21);

end

datatxt中的数据：
160,155,155,160,155,150,160~
800,800,1000,2000,2000,2000,3000~
170.7, 160.3, 140.2, 98.6, 38, 20.5, 3.1, 21.2, 64.2, 92, 96, 106, 121.2, 128, 142, 60, 95, 100, 105, 115, 125,
215.7, 205.3, 190.2, 171.6, 111, 95.5, 86, 71.2, 114.2, 142, 146, 156, 171.2, 178, 192, 110, 145, 150, 155, 165 175,
230.7, 220.3, 200.2, 181.6, 121, 105.5, 96, 86.2, 48.2, 82, 86, 96, 111.2, 118, 132, 44, 85, 90, 95, 105, 115,
260.7, 250.3, 235.2, 216.6, 156, 140.5, 131, 116.2, 84.2, 62, 51, 61, 76.2, 83, 97, 80, 50, 55, 60, 70, 80,
255.7, 245.3, 225.2, 206.6, 146, 130.5, 121, 111.2, 79.2, 57, 33, 51, 71.2, 73, 87, 75, 32, 45, 50, 65, 75,
265.7, 255.3, 235.2, 216.6, 156, 140.5, 131, 121.2, 84.2, 62, 51, 37, 16.2, 11, 28, 80, 50, 37, 36, 10, 0,
275.7, 265.3, 245.2, 226.6, 166, 150.5, 141, 131.2, 99.2, 77, 64, 56, 38.2, 26, 2, 95, 63, 50, 55, 32, 26~
104,301,750,606,194,205,201,680,480,300,220,210,420,500,,42,10,130,190,260,100~

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！

精品资料