钢管铺设).doc

钢管铺设问题
摘要
本文以铺设一条输送天然气的主管道为背景。通过对问题的深入分析后，建立了关于钢管铺设的总费用最小的非线性规划优化模型。
针对问题一：我们首先利用图论思想来分析数据，并求到了每单位钢管从钢厂运到结点的最少总费用（即公路运费﹑铁路运费和钢管销价之和）。数据处理完后，我们根据模型在进行求解时，利用分枝定界的思想将模型转化成典型的二次规划问题。并利用Matlab数学软件求解出钢管铺设的最小费用为min1278632（万元）以及向钢管厂订购的计划表（详见模型求解）。
针对问题二：我们主要是利用问题一的模型对每个钢厂销价的变化以及产量的上限的变化进行单独讨论，然后作相对比较，最终得出：、钢厂销价的变化对总费用的影响最大；产量上限的变化对总费用影响最大。
针对问题三：我们从枢纽站点的各个方向出发，并在问题一的基础上建立了此问题更一般的优化模型。最后，和问题一的求解方式一样得出钢管铺设的最小费用min=14
06631（万元）以及向钢管厂订购的计划表（详见模型求解）。
通过对本文中的模型用计算机模拟检验结果得到,我们的模型是成功的,求解是正确的.对路线的安排是合理的。本论文所建立的数学模型有成熟的理论基础,可靠性高,操作简单,容易实施,在一些运输问题上都可以用此方法。本文最后指出的模型的缺陷给我们指明了今后继续研究的方向。

关键字：优化模型 二次规划 图论思想

问题重述

某地要从这7个预选钢管厂订购一批数量为5171km单位长度的主管道钢管，通过铁路、公路运送到十五个铺设点铺设一条的输送天然气的主管道，其中为便于计算我们把1km的主管道称为1单位钢管，并且要求满足一个钢管厂如果要承担制造这种钢管至少要生产500个单位，钢管厂在指定范围内能生产该钢管最大数量为个单位，其销价分别为万元/每单位。
请你根据题中所给出的铁路和公路运价以及图（1）（2）路程长度铺设图中制定一个主管道钢管的订购和运输计划，使得总费用最少（假设装卸费忽略不计入运费中），求出总费用具体值；并分析哪个钢管厂的销价变化对购运计划合总费用影响最大，给出相应的数字结果并思考如果铺设的管道是树形图，再另外给出解决该问题的模型，并计算出结果。

模型假设

1． 沿铺设的主渠道以有公路或者有施工公路.
2． 在主渠道上，每千米卸1单位的钢管.
3． 公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算）
4． 在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用.
5． 在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，即钢厂的产量不受限制.
6． 假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km，1单位钢管的运价增加5万元.

变量说明：
：表示第i个钢厂；（）
：表示第i个钢厂的最大产量；（）
:表示输送管道（主渠道）上的第个地点；（）
:表示第个钢厂钢管的单位销价；（）
:表示钢管厂向点运送的钢管数量；（）
:表示相邻点与之间的距离；（）
:表示1单位钢管从钢厂运到结点的最少总费用，即公路运费﹑铁路运费和钢管销价之和；（）
：表示与点相连的公路和铁路的相交点；（）

模型分析与建立

问题一：讨论如何调整主渠道钢管的订购和运输方案使总费用最小。
（一）数据分析与处理：
由题意可知，钢管从钢厂到运输结点的费用包括钢管的销价﹑钢管的铁路运输费用和钢管的公路运输费用.在费用最小时，对钢管的订购和运输进行分配，可得出本问题的最佳方案.
1. 求钢管从钢厂运到运输点的最小费用
1）先通过题中图表可得到钢管厂到运输结点的最短铁路路径权值为：
由于钢管从钢厂运到运输点要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关.又由于钢厂直接与铁路相连，所以可先求出钢厂到铁路与公路相交点的最短路径.如图1

图1钢厂到铁路与公路相交点的最短路径

依据钢管的铁路运价表，算出钢厂到铁路与公路相交点的最小铁路运输费用，并把费用作为边权赋给从钢厂到的边.再将与相连的公路、运输点及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边.以为例得图2

图2 钢管从钢厂运到各运输点的铁路运输与公路运输费用权值图

同理可知：由到可得到由2

b2
b3
b4
b5
b6
b7
b8
b9
b10
b11
b12
b13
b14
b15
S1
160
140
80
37
20
0
20
60
85
95
105
115
125
140

205
190
125
110
95
85
70
110
85
95
105
115
125
140

145
145
140
120
105
95
85
44
75
85
85
100
105
120

180
180
170
155
140
130
115
80
55
50
50
65
70
85

175
170
165
145
130
120
110
75
50
32
44
55
65
80

175
170
165
145
130
120
110
75
50
44
44
20
20
26

185
185
180
160
145
135
125
90
60
60
55
32
23
20

(表1）到最小铁路终点最小费用

b2
b3
b4
b5
b6
b7
b8
b9
b10
b11
b12
b13
b14
b15
S1
0.3
0.2
60
1
0.5
3.1
1.2
4.2
7
1
1
6.2
3
2

0.3
0.2
60
1
0.5
3.1
1.2
4.2
7
1
1
6.2
3
2

0.3
0.2
60
1
0.5
3.1
1.2
4.2
7
1
1
6.2
3
2

0.3
0.2
60
1
0.5
3.1
1.2
4.2
7
1
1
6.2
3
2

0.3
0.2
60
1
0.5
3.1
1.2
4.2
7
1
1
6.2
3
2

0.3
0.2
60
1
0.5
3.1
1.2
4.2
7
1
1
6.2
11
2

0.3
0.2
60
1
0.5
3.1
1.2
4.2
7
1
1
6.2
3
2

（表2）到最小公路终点最小费用

2).计算单位钢管从到的最少运输费用
根据以上数据，我们用上的最小铁路费用加上的最小公路费用求出单位钢管从到的最少运输费用依次为：70.7，160.3，140.2，98.6，38，20.5，3.1，21.2，64.2，92，96，106，121.2，128，142（单位：万元）.加上单位钢管的销售价，得出从钢厂购买单位钢管运输到点的最小费用依次为：330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302（单位：万元）.
同理，可用同样的方法求出钢厂﹑﹑﹑﹑﹑到点的最小费用，从而得出钢厂到点的最小总费用（单位：万元）为：

A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
S1
320.3
300.2
258.6
198
180.5
163
181.2
224.2
252
256
266
281.2
288
302

360.3
345.2
326.6
266
250.5
241
226.2
269.2
297
301
311
326.2
333
347

375.3
355.2
336.6
276
260.5
251
241.2
203.2
237
241
251
266.2
273
287

410.3
395.2
376.6
316
300.5
291
276.2
244.2
222
211
221
236.2
243
257

400.3
380.2
361.6
301
285.5
276
266.2
234.2
212
188
206
226.2
228
242

405.3
385.2
366.6
306
290.5
281
271.2
234.2
212
201
195
176.2
161
178

425.3
405.2
386.6
326
310.5
301
291.2
259.2
237
226
216
198.2
186
162
（表3）到点最小费用

（二）模型建立[1]：

根据题意可以分析出运输总费用可分为两部分：
运输总费用=钢厂到各点的运输费用+铺设费用.
运输费用：若运输点向钢厂订购单位钢管，则钢管从钢厂运到运输点所需的费用为，则：

=.

铺设费用：当钢管从钢厂运到点后，钢管就要向运输点的两边段和段运输铺设管道.设向段铺设的管道长度为，则设向和段铺设的长度分别为则向段的铺设费用为：.

（万元）
同理到段的铺设费用为：
（万元）
则铺设费用为：

= （万元）

运输加铺设总费用最小为：

约束条件:
1. 钢管厂向点运送的钢管数量要等于点需要铺设钢管的数量：

2. 针对钢管厂有两种情况 (选或者不选)：
ⅰ.若不选则订购量为0；
ⅱ.若选择钢管厂则一个钢管厂至少要大于500而且要小于钢厂的最大产量；

3.由于枢纽站运往两边的量受路段长度的制约，故：

4由于枢纽站的左边和的右边都没有路段了，故：
，
5.对于设的管道长度为以及单位钢管数量都应该为正整数。即：

综上所述：

s．t.

问题二：哪个钢厂钢管销价的变化对购运计划和总费用影响最大以及哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。

针对该问题主要是利用问题一的模型对每个钢厂销价的变化以及产量的上限的变化进行单独讨论，然后作相对比较，最终得出结论。

问题三：如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图2按（1）的要求给出模型和结果。

(一).模型的分析与建立[2]

针对问题三，由于铺设的管道不是一条线，而是一个树形图。因此，有些枢纽站点
不只是单独的向左边和右边运送。于是将运输到点的钢管总量不能简单地分为和两部分，而应该考虑从出发的各个方向。于是有：

其中E是树形图的边集，是连接点和的边，是到的钢管沿边和方向铺设的数量。
对于约束条件，其约束条件同问题一的类似，故为：

模型求解[3]

问题一的求解：
由以上分析，由于约束条件：

的存在，因此模型的求解不能简单地调用二次规划的软件。于是我们先考虑将该约束条件改为大范围0到进行求解

于是此模型便转化为了典型的二次规划优化模型，如果结果符合原有约束条件，则便是原问题的最优解，如果存在个别的，使，那么可以针对这些，用分枝定界法的思想强制的将它分为和两种情况考虑，然后找出其中最有的结果。
根据这种思想，我们用Matlab软件中的解决二次规划问题的命令求解得到的最优解中，。于是将从供应厂名单中删除，再将第7家工厂的供货量改为0以及不小于500两种情况重做。相比之下，取0的情况总费用较小，从而也应把删除。得到问题一的最优解为：
min1278632（万元）
具体的购运计划如表：

订购量
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
S1
800
0
201
133
200
266
0
0
0
0
0
0
0
0
0
S2
800
179
11
14
295
0
0
300
0
0
0
0
0
0
0
S3
1000
139
11
186
0
0
0
664
0
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
358
242
0
0
0
0
0
0
415
0
0
0
0
S6
1556
0
0
0
0
0
0
0
0
0
351
86
333
621
165
S7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

问题二的求解：

问题二相当于规划问题一的灵敏度分析，一般来说应该对销价变化和产量上限的变化求出总的费用的变化。但是针对本题的情况，要得到费用的变化关于销价变化和产量上限的变化的函数关系，几乎是不可能的，好在本题只要求对每个钢厂进行单独讨论，然后做相对比较。现在我们对各个钢厂单位钢管的销价分别增加1万元和减少一万元，然后利用Matlab计算得到总费用[4]。如下表(4)：

钢厂
销价增加1万元，总费用的增加量
销价减少1万元，总费用的减少量
S1
800
800

800
800

1000
800
S5
1008
1368

1202
1563

表(4)
其中： 、钢厂销价的变化对总费用没有影响，可以看出，、钢厂销价的变化对总费用的影响最大。
将各个钢厂的产量的上限分别增加100个单位和减少100个单位也就是将原模型中的分别增加100和减少100,。为此我们计算出总费用的变化情况如下表（5）：

钢厂
产量上限增加100个单位
总费用的减少量
产量上限减少100个单位
总费用的增加量
S1
10300
10300

3500
3500

2500
2500
表（5）
其中：S4 、 S5 、S6 、产量上限的变化对总费用没有影响。可以看出产量上限的变化对总费用影响最大。

综上分析所得：
销价的变化影响最大为：或；
产量上限的变化影响最大为：

问题三的求解[5]：

同问题一可得树形图最优运费为：

min=1406631（万元）

其具体的购运计划如表（6）：

订购量
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
A21
S1
800
0
201
133
200
266
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
S2
800
179
11
14
295
0
0
300
0
0
0
0
0
0
0
0
0
0
0
0
0
S3
1000
139
11
186
0
0
0
664
0
0
0
0
0
0
0
0
0
0
0
0
0
S4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
S5
1303
0
358
242
0
0
0
0
0
0
415
0
0
0
288
0
0
0
0
0
0
S6
2000
0
0
0
0
0
0
0
0
0
351
86
333
621
0
220
0
0
224
0
165
S7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

表（6）

模型评论与推广
我们建立的模型和构造算法思路简单，易懂，切对各种可能的情况都进行比较全面的考虑，故该模型的一般性很强,。不仅能求解由铁路、公路构成的交通网络的钢管订购和运输的最优化问题，给出订购计划，最佳运输路径和铺设管道方式，还可以推广到更为一般的运输、网络、节点和分配问题，所以该模型更能贴近生活，实用于生活，被广大群众所接受采用。但在作为图论问题的技术而言，求解过程比较难，不易求出最优解；并且在求解最短路时，若果网络更为复杂化我们用人工计算处理容易出错、工作量也比较大。

参考文献
[1]姜启源，数学模型，北京：北京高等教育出版社，1993年
[2]韩中庚主编，数学建模竞赛，北京：科学出版社，2007年
[3]许洪范，数学建模教程，北京：国防工业出版社，2007年
[4]费培之，数学与建模使用教程，成都：四川大学出版社，1998年
[5]李志林等，数学建模及典型案例分析，北京：化学工业出版社，2006年

附录

1.部分程序：
（1）当在解决二次规划问题中的约束条件为时

T=[104 301 750 606 194 205 201 680 480 300 220 210 420 500];
S=[800 800 1000 1000 2000 2000 2000];
C=[170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142;
215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192;
230.7 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132;
260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97;
255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87;
265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28;
275.7 265.3 245.2 226.6 166 150.5 141 131.2 99.2 76 66 56 38.2 26 2];
P=[160 155 155 160 155 150 160]
P=kron(P',ones(1,15));
D=[C+P;0.05*ones(2,15)]';
f=D(:);
H=[zeros(105,105) zeros(105,30);
zeros(30,105) 0.1*eye(30,30)];
A1=kron(eye(7,9),ones(1,15));
b1= S';
temp=eye(15);
e1=[zeros(1,15);temp(1,:)];
el5=[temp(15,:);zeros(1,15)];
A2=[zeros(2,105) el5 e1]
b2=zeros(2,1);
A=[A1;A2];
b=[b1;b2];
Aeq1=kron([ones(1,7) -ones(1,2)],eye(15));
beq1=zeros(15,1);
Aeq2=[zeros(14,105) temp(1:14,:) temp(2:15,:)];
beq2=T';
Aeq=[Aeq1;Aeq2];
beq=[beq1;beq2];
x0=x;
[x,fval,exitflag]=quadprog(H,f,A,b,Aeq,beq,zeros(135,1),[],x0);
exitflag
x=round(x); %取整
xm=reshape(x,15,9)' %调运方案矩阵
m=xm(1:7,:);
order=sum(m') %订购方案矩阵
format long;
fval=0.5*x'*H*x+f'*x %输出取整后的总费用;
format short;

（2）当在解决二次规划问题中令是的解：

T=[104 301 750 606 194 205 201 680 480 300 220 210 420 500];
S=[800 800 1000 0 2000 2000 0];
C=[170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142;
215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192;
230.7 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132;
260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97;
255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87;
265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28;
275.7 265.3 245.2 226.6 166 150.5 141 131.2 99.2 76 66 56 38.2 26 2];
P=[160 155 155 160 155 150 160]
P=kron(P',ones(1,15));
D=[C+P;0.05*ones(2,15)]';
f=D(:);
H=[zeros(105,105) zeros(105,30);
zeros(30,105) 0.1*eye(30,30)];
A1=kron(eye(7,9),ones(1,15));
b1= S';
temp=eye(15);
e1=[zeros(1,15);temp(1,:)];
el5=[temp(15,:);zeros(1,15)];
A2=[zeros(2,105) el5 e1]
b2=zeros(2,1);
A=[A1;A2];
b=[b1;b2];
Aeq1=kron([ones(1,7) -ones(1,2)],eye(15));
beq1=zeros(15,1);
Aeq2=[zeros(14,105) temp(1:14,:) temp(2:15,:)];
beq2=T';
Aeq=[Aeq1;Aeq2];
beq=[beq1;beq2];
x=x0;
[x,fval,exitflag]=quadprog(H,f,A,b,Aeq,beq,zeros(135,1),[],x0);
exitflag
x=round(x); %取整
xm=reshape(x,15,9)' %调运方案矩阵
m=xm(1:7,:);
order=sum(m') %订购方案矩阵
format long;
fval=0.5*x'*H*x+f'*x %输出取整后的总费用;
format short;
2.题目中的附图及附表

（1）图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
A6
A7A11
A8A11
A911A11
A10
A11
A12
A13
A14
A15
S1
S2
S3
S4
S5
S6
S7
图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)
图2

（2）图2

（1）钢厂生产钢管的最大数量及每单位的销价：

1
2
3
4
5
6
7

800
800
1000
2000
2000
2000
3000

160
155
155
160
155
150
160
（2）单位钢管的铁路运价表：

里程(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

15