输油管道布置的优化设计模型.doc

1、2010年全国大学生数学建模竞赛四川赛区三等奖论文 摘要管道运输是输送石油的一个重要途径，设计合理的管线铺设方案，不仅可以节省铺设的费用，还可以减少后期运输的成本，提高经济效益。本文针对题目中给出的不同情况，运用平面解析几何的轴对称原理、多元函数极值理论和计算机搜索算法等方法，设计了不同情况输油管线的详细方案。问题一中，根据有无共用管线，以及各段管线的单位费用相同或不同，将模型分为四种情况进行讨论，并用matlab软件进行符号运算。针对问题二，首先对三家工程咨询公司的估价结果按资质权重进行计算，得到较准确的附加费用估计值。接着就郊区部分是否铺设共用管线，分别建立数学模型并求得相应的最小费用。然

2、后用搜索算法在可行域内搜索最优解，验证设计方案的正确性。比较所得结果，有共用管线的设计方案费用最低，为283.2789万元。具体设计方案是：厂管线与城郊分界线的交点距铁路沿线7.37km；、两厂管线的会合点距城郊分界线9.55km，距铁路沿线1.85km；车站距城郊分界线9.55km。问题三与问题二类似，但各段管线的单位费用不相同。在前面结论的基础上，按郊区部分有无共用管线，分别建立模型并进行计算，再用搜索算法搜索最优点对方案进行验证。经比较，无共用管线方案费用最低，为252.5608万元。具体设计方案是：厂管线与城郊分界线的交点距铁路沿线7.3km；车站距城郊分界线8.3km。 本文综合考虑

3、了输油管线布置的各种情况，从费用最少的角度出发，为设计院提供了较为详细的设计方案。通过对比各种设计方案所需的费用，得出费用最少的方案，并用搜索算法进行了检验，确保了设计方案所需费用的准确性。关键词：轴对称 多元函数极值 搜索算法 优化设计一、问题重述某油田计划在铁路线一侧建造两家炼油厂，同时在铁路线上增建一个车站，用来运送成品油。针对两炼油厂到铁路线距离和两炼油厂间距离的各种不同情形，提出不同的设计方案。在方案设计时，若有共用管线，应考虑共用管线费用与非共用管线费用相同或不同的情形。对问题二进行具体设计时，所有管线的铺设费用均为每千米7.2万元。有一部分管线铺设在城区，还需增加拆迁和工程补偿等

4、附加费用。为对此项附加费用进行估计，聘请三家工程咨询公司进行了估算。三家工程咨询公司的资质分别为甲级、乙级、乙级，附加费用的估价分别为每千米21万元、24万元、20万元。在上述实际问题中，为进一步节省费用，可以根据炼油厂的生产能力，选用相适应的油管。这时的管线铺设费用将分别降为输送A厂成品油的每千米5.6万元，输送B厂成品油的每千米6.0万元，共用管线费用为每千米7.2万元，拆迁等附加费用同上。根据上述实际问题的情况，给出管线最佳布置方案及相应的费用。二、问题的分析问题一中，两个炼油厂均在铁路的一侧，要求针对两个炼油厂到铁路线距离和两炼油厂之间距离的各种情况提出设计方案，还要考虑各段管线单位长

5、度费用相同或不同的情况。因此，可将设计方案分为四类：不含共用管线、管线单位长度费用相同，不含共用管线、管线单位长度费用不同，含共用管线、管线单位长度费用相同，含共用管线、管线单位长度不同等四类。针对问题二，在给定数据的情况下铺设管线时，由于所有管线均为每千米7.2万元，故需分为不含共用管线和含有共用管线两种设计方案，进而比较求得最优。在城区的管线需增加拆迁和工程补偿等附加费用，设计院聘请了三家不同资质的咨询公司，得到3个估价。需要对这3个数据进行合理处理，得到较准确的附加费用的估计值。为了进一步节省费用，铺设路线时运输A厂的成品油每千米5.6万元，B厂的成品油每千米6.0万元，共用管线费用每千

6、米7.2万元，拆迁等附加费用不变。结合问题一的分析，该问题属于管线单位长度费用不同的情况，应该分为不含共用管线和含有共用管线两种方案进行讨论，以求最优。通过上述分析，容易看出，有以下两个问题需要解决：(1)当不清楚是否含有共用管线，管线单位长度费用是否相等时，分四种情况进行讨论；(2)根据问题二和问题三的具体数据，按是否含有共用管线分别建模并求解，比较两者的结果，得到最优的设计方案。三、模型的假设1、假设铺设管线地段的地质情况是一样的；2、假设输油管道的铺设范围内，铁路可以近似看成是直线，并且可以忽略铁路及两边安全区域的宽度；3、假设施工对有足够高的水平能按照计划进行施工，能够精确的利用管线；

7、4、假设在施工的这段时间里所有需要的管线的价格不会发生改变。四、符号说明输送厂成品油的管道的单位长度费用；输送厂成品油的管道的单位长度费用；共用管道的单位长度费用；城区铺设管道时，单位长度的附加费用；五、模型建立、求解及检验5.1 问题1的模型 由题目条件知，两个炼油厂在铁路的同侧。针对两个炼油厂到铁路线距离和两炼油厂之间距离的各种情况，考虑是否采用共用管线以及各段管线单位长度费用相同或不同的情况，分为以下四种情况进行讨论。(1)不采用共用管线，两炼油厂和车站之间成“V”形分布。设厂到车站的管道单位长度费用为万元/千米，厂到车站的管道单位长度费用为万元/千米。当时，即两段管线的价格相同。原问题

8、要求铺设管道所需的最小费用，可以转化为求管道的最小长度，也就是两家炼油厂到车站距离之和的最小值，可用初等数学“轴对称求最短距离”的方法进行求解，如图1所示。图1 轴对称求最短距离示意图因为铁路相对较直，不妨令铁路沿线方向为轴，过点作方向的垂线为轴，建立直角坐标系。如何在铁路线上建造一个车站，使得炼油厂、到车站的距离之和最小的问题，可以转化为一个纯几何问题，即在轴上找一点，使得该点到、距离之和最小。由平面解析几何轴对称的相关知识可知，作点关于轴的对称点，连接，交轴于点，则为所求。当时，即两段管道的价格不相同。这时不能将原问题简单的看成求距离最短。令各点坐标为、，则可建立如下的模型。即： 要使费用

9、最少，即求函数的最小值。matlab符号运算的结果较复杂，在此省略。当进行具体数据的运算时，可以令取适当的步长，在可行区间搜索函数的最小值点。图2 两段管道价格不相等时示意图(2)采用共用管线，两炼油厂和车站之间成“Y”字形分布。运用多元函数极值理论，确定点。图3 有共用管线时管道分布示意图同理，建立如图3所示的直角坐标系，为两家炼油厂的管道的会合处。为会合点到车站的距离。由于垂直距离最短，显然应垂直于轴。则记各点的坐标分别为，。当共用管道与非共用管道单位长度的费用相同时，即时，费用最少即线段、距离之和最小。建立费用与上述坐标之间的关系，得：化简，其中表示三条直线段、长度之和。要求线段距离之和

10、的最小值，即求二元函数的最小值。运用matlab的符号运算功能进行计算， 求关于的一阶偏导数，并令其为0，解得函数的驻点。=1/2/(x1-x)2+(y1-y)2)(1/2)*(-2*x1+2*x)+1/2/(x2-x)2+(y2-y)2)(1/2)*(-2*x2+2*x)=1/2/(x1-x)2+(y1-y)2)(1/2)*(-2*y1+2*y)+1/2/(x2-x)2+(y2-y)2)(1/2)*(-2*y2+2*y)+1令，解得：（增根已舍去）整理，得进一步求二阶偏导数，得到黑赛矩阵（由于符号运算的结果较为复杂，故未写进正文）。该矩阵的各阶顺序主子式均为正值，即该黑赛矩阵正定，上述驻点为

11、二元函数的局部极小点。又因为函数为定义在凸集上的凸函数，该区域中的极小值即为最小值。求得=1/2*y1+1/2*y2+1/2*3(1/2)*x2，即。由此可知，最小费用，其中为单位长度管道铺设费用。当共用管道与非共用管道单位长度的费用不同时，设厂到会合点的管道单位长度费用为万元/千米，厂到会合点的管道单位长度费用为万元/千米，共用管道单位长度的价格。同样建立如图2所示的坐标系，容易建立总费用与、坐标之间的关系。即：同理，用上述方法求解该函数的最小值。用matlab进行符号运算，求得函数取得最小值的点坐标。可表示为：由于符号运算的结果太长，故文中未给出。可以看出，这里求管道会合点坐标的结论具有普

12、遍性，后面类似的问题可以直接运用该结论。结合上面的分析，我们提出以下设计方案。(1) 不含共用管道，即两炼油厂与车站之间的管道分布成“V”字型。当，即炼油厂到车站的管道单价与厂到车站的管道单价相等时，运用轴对称求最短距离的原理，即由、两点坐标确定铁路上车站的位置；当时，建立模型：，最少费用即函数的最小值；(2) 含有共用管道，两炼油厂与车站之间的管道分布成“Y”字型。当共用管道与非共用管道单价相同时，即时，费用最少即线段、距离之和最小。建立费用与点的坐标之间的关系，得：运用求多元函数极值的办法，得到最少费用的会合点的坐标为：当各段管道的单位长度费用不相等时，建立如下模型：5.2 对三家公司估价

13、数据的处理根据题意，设计院要设计一条更为复杂的路线。路线一部分要穿过城区，该段管线的铺设涉及到拆迁和工程补偿问题。聘请的三家工程咨询公司的估算情况如表1所示。表1 工程咨询公司估算结果工程咨询公司公司一公司二公司三 附加费用（万元/千米）212420经查阅资料，通过对甲级资质和乙级资质咨询公司技术水平及技术装备的总体评估，甲乙两种资质的工程咨询公司对工程估价的精度比大致为。由此可知三家工程咨询公司估价结果的权重分别为、，即0.3846、0.3077、0.3077。按权重计算，得到附加费用。5.2.1 郊区部分不铺设共用管线，成“V”字型分布已知管道铺设费用为万元/千米。由于管道经过城区需要附加

14、费用，用于拆迁和赔偿，因此需要将炼油厂到车站之间看作两段，直线段和可能在一条直线上，也可能不在一条直线上。令管线与城郊分界线（即虚线）的交点为，则段的铺设费用为万元/千米，其余各段均为万元/千米。图4 郊区部分管道成“V”型分布的示意图根据题设条件，城区的管道路线应在直角三角形内部滑动，即点被限定在直线段上，也即，如图5所示。为了找到最佳的点，不妨在直线段上按步长0.01进行搜索。图5 点取值范围示意图对于随机取定的点，因为铺设管道的单价相等，郊区费用最少即直线段、之和最小。可以通过初等数学对称轴求最短距离的方法，求得管道与铁路的交点及相应的总费用。通过比较不同点导致的总费用大小，得到最小费用

15、的铺设路线方案。根据上述思路编写matlab程序，流程图如下所示。图6 程序problem2_1.m流程图代码见附录problem2_1.m。运行程序，求得、点的坐标分别为、，最小费用为285.1211万元。管道分布示意图如图7所示。图7 郊区管道分布成“V”字分布，最小费用的铺设示意图5.2.2 郊区部分铺设共用管线，成“Y”型分布，如图8所示。图8 郊区部分管道成“Y”型分布的示意图采用同样的方法沿城郊分界线搜索点。当取定一个点后，结合前面所述的多元函数极值理论求会合点的结论：，得到点坐标，进而确定整个管道的铺设路线。设点的坐标为，则由、两点的坐标可求得点的坐标：于是可以求得线段、的长度，

16、进而可以建立费用与坐标点之间的数学模型：代入点的坐标，可得： 可见，函数是点坐标的函数，即不同的坐标点会导致不同的管道铺设费用。考虑到，函数实际上只是自变量的一元函数。根据前面所述的流程图，修改通过两点坐标求会合点的算法，得到程序problem2_2.m。运行该程序，得到、两点的坐标分别为、，最小费用为283.2789万元，管道铺设示意图如图9。图9 随机确定点、运用多元函数极值方法确定会合点5.2.3 运用搜索算法对模型结果进行检验搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。为了验证上述方法的正确性，我们先在直线段上随机确定点，

17、再对每个确定，搜索梯形区域，找到铺设、费用最少的点。 图10 梯形区域示意图 图11 计算机搜索算法搜索梯形区域示意图编写程序problem2_3.m，见附录。运行，得到、两点的坐标分别为、，最小费用为283.2814万元。由于所用的PC计算机的运算能力有限，未能将步长取得足够小以搜索更优的点坐标。但即使这样，搜索得到的结果与上述两种方法取得的结果已经非常接近，说明上述方法取得的结果是正确的。综合上面的分析，得出三种方法的结果如表2所示。表2 三种方法取得结果的对照表使用方法“V”型“Y”型随机搜索最小费用(万元)285.1211283.2789283.2814可以看出，在题目给出的各种管道单

18、价的条件下，不含共用管线的设计方案费用最大，含共用管线的设计方案费用最小，但相差并不大。随机搜索可以说是一种比较“笨”的方法，按程序中给定的步长，遍历了整个区域。在数据量不是很大的前提下，它也是可行的，因为必然能够找到较准确的数值解。通过比较所需费用，选择郊区部分含有共用管线的设计方案，管线成“Y”型分布，、两点的坐标分别为、。即厂管线与城郊分界线的交点距铁路7.37km，、两厂管线的会合点距城郊分界线9.55km，距铁路1.85km。管道分布示意图如图12所示。图12 第二小题最优方案5.3 问题三的模型为进一步节省费用，现在根据炼油厂的生产能力选用相适应的油管。此时厂到会合点的管线单价为=

19、5.6万元/千米,厂到会合点的管线单价为=6.0万元/千米，共用管线单价为7.2万元/千米。(1)不铺设共用管道，即郊区的管道分布成“V”字型。由于，故该问题与5.1节中(1)的模型类似：不同之处在于需要增加段的费用。编写程序problem3_1.m，先让计算机在城郊分界线上随机确定点，再将、点坐标代入上述模型，求函数在当前点坐标下的最小值。求在当前点坐标下的最小值的过程，就是将点、看作定点，在线段上搜索最优点的过程，如图13。图13 计算机随机搜索、示意图根据上述思路编写计算机程序problem3_1.m，程序代码见附录。运行程序，得到、，最小费用为252.5608万元。(2)铺设共用管道，

20、即郊区的管道分布成“Y”字型。由于，故该问题与5.1节中(2)的情况类似，于是运用模型：不同的是，上述模型不包含城区拆迁补偿的问题，需要增加城区的管道费用及拆迁补偿费用。编写程序如problem3_2.m，见附录。运行程序，得到、，最小费用为253.9056万元。(3)对上述两种方案的检验。用计算机搜索整个区域的“笨”方法，对上面两种方法进行检验。先在线段上搜索点，再在梯形区域内搜索点。编写程序如problem3_3.m，见附录。运行，得到、，最小费用为253.8419万元。综合上面三种情况，得对照表，如表3所示。表3 三种方法取得结果的对照表使用方法“V”型“Y”型随机搜索最小费用(万元)2

21、52.5608253.9056253.8419由表3可以看出，随机搜索得到的结果与前面两种方法非常接近，误差可能是由于计算机运行时的舍入误差导致的。由于“V”型布置的费用最少，故应该采用这种方法，即不铺设共用管线。最优方案中，、，最小费用为252.5608万元。即厂管线与城郊分界线的交点距铁路7.3km，车站距城郊分界线8.3km，管道布置的示意图如图14所示。图14 第三题的最终方案图六、模型的评价本文运用了平面解析几何的轴对称原理、多元函数极值理论和计算机搜索算法等方法，对题目中给出的各种情况逐一建模求解，给设计院提供了铺设共用管线和不铺设共用管线两种方案，并通过比较，以费用最少的设计方案

22、为最优设计方案。文中运用了必要的表格和图片，使得论文的结果形象直观，一目了然。由于符号运算过于复杂，未能建立更一般、通用性更强的模型。由于PC机配置并不高，在进行搜索算法计算时，未能将搜索的步长取到足够小。七、参考文献1张志勇 杨祖樱等，Matlab教程，北京：北京航空航天大学出版社，2006.82张威，Matlab基础与编程入门，西安电子科技大学出版社，2004.23徐全智 杨晋浩，数学建模，北京：高等教育出版社，2003.74 赵静 但琦，数学建模与数学实验(第3版)，北京：高等教育出版社，2000八、附录主要程序源代码：1、distc.m%计算点（x1,y1）和（x2,y2）之间的距离f

23、unction f=distc(x1,y1,x2,y2)f=sqrt(x1-x2)2+(y1-y2)2);2、my_search.mfunction cost_min,X,Y=my_search(x1,y1,x2,y2,pA,pB,p)%在坐标点与X轴构成的梯形中，去寻找距离的最小值,第一个点在Y轴上。%函数的返回值是最少费用，和N点坐标%注意输入的参数中，x1,y1是A点坐标，x2,y2是E点坐标cost_min=100000;x=0:0.1:x2;for ki= 1 : length(x) y=interp1(x1,x2,y1,y2,x(ki); yki=0:0.1:y; for kj=1

24、:length(yki) %用x_1,y_1表示N点坐标 x_1=x(ki); y_1=yki(kj); %注意：当各段管道的单价不等时，费用最少不能等价于距离最小 cost_cur=pA*distc(x1,y1,x_1,y_1)+pB*distc(x2,y2,x_1,y_1)+p*y_1; if cost_curcost_min cost_min=cost_cur; X=x_1; Y=y_1; end endend3、problem2_1.m%在如图所示的虚线上，运用搜索算法生成点E，通过A、E两点，用轴对称的办法求M的坐标clear,clcp=7.2;p3=21.6154;xE=15;y1

25、=5;yE=0:0.1:8;n=length(yE);cost_city=p+p3;%城区管道费用,含拆迁费cost_min=100000;cost_sub=p;%郊区管道费用for k=1 : n %E点坐标相当于第一题中的B点坐标。 x2=xE; y2=yE(k); %通过A和E关于X轴的对称点E,求与X轴的交点M的横坐标 xM=interp1(5 -y2,0 x2,0); %当前这一次循环的费用 cost_cur=cost_city*distc(20,8,xE,yE(k)+cost_sub*distc(0,5,x2,-y2); if cost_curcost_min cost_min=c

26、ost_cur; YE=yE(k);XM=xM; endend4、problem2_2.m%在如图所示的虚线上，运用搜索算法生成点E，通过A、E两点，用第一题的结论得到会合点C的坐标clear,clcp=7.2;%管道费用p3=21.6154;%拆迁附加费xE=15;y1=5;%坐标yE=0:0.01:8;n=length(yE);cost_city=p+p3;%城区管道费用,含拆迁费cost_min=100000;cost_sub=p;%郊区管道费用for k=1 : n %E点坐标相当于第一题中的B点坐标。 x2=xE;y2=yE(k); %下面二式均为第一题用多元函数极值理论求得的结论

27、x=1/2*x2+1/6*3(1/2)*(3*y1-3*y2);y=1/2*y1+1/2*y2-1/6*3(1/2)*x2; %当前这一次循环的费用 cost_cur=cost_city*distc(20,8,xE,yE(k)+cost_sub*(distc(0,5,x,y)+distc(xE,yE(k),x,y)+y); if cost_curcost_min cost_min=cost_cur; YE=yE(k);XN=x;YN=y; endend5、problem2_3.m%在如图所示的虚线上，运用搜索算法生成点E，通过A、E两点，进一步搜索会合点Nclear,clcp=7.2;%管道费

28、用p3=21.6154;%拆迁附加费xE=15;y1=5;%坐标yE=0:0.05:8;n=length(yE);cost_city=p+p3;%城区管道费用,含拆迁费cost_min=100000;cost_sub=p;%郊区管道费用for k=1 : n %E点坐标相当于第一题中的B点坐标。 x2=xE;y2=yE(k); %调用搜索算法 d,x,y=my_search(0,5,x2,y2,p,p,p); %当前这一次循环的费用 cost_cur=cost_city*distc(20,8,xE,yE(k)+cost_sub*(distc(0,5,x,y)+distc(xE,yE(k),x,

29、y)+y); if cost_curcost_min cost_min=cost_cur; YE=yE(k);XN=x;YN=y; endend6、problem3_1.m%V在如图所示的虚线上，运用蒙特卡罗的方法随机生成点E，再滑动M，求最佳的坐标clear,clcp=7.2;%公用管道费用pA=5.6;pB=6.0;p3=21.6154;%拆迁附加费cost_city=pB+p3;%城区管道费用,含拆迁费xE=15;y1=5;%坐标yE=0:0.1:8;n_yE=length(yE);cost_min=100000;for ki=1 : n_yE %用x2,y2表示E点坐标，相当于第一题中

30、的B点坐标。 x2=xE; y2=yE(ki); %在0x15上滑动M xM=0:0.1:15; n_xM=length(xM); for kj=1:n_xM %用x3,y3表示M点的坐标 x3=xM(kj); y3=0; %当前这一次循环的费用 cost_cur=cost_city*distc(20,8,x2,y2)+pA*distc(0,5,x3,y3)+pB*distc(x2,y2,x3,y3); if cost_cur7.1 y222=y2; end %下面二式均为第一题用多元函数极值理论求得的结论，x,y即为N点坐标 x= y=（引用前面符号计算的结果，太长，省略）%当前这一次循环的

31、费用 cost_cur=cost_city*distc(20,8,x2,y2)+pA*distc(0,5,x,y)+pB*distc(x2,y2,x,y)+p*y; if cost_curcost_min cost_min=cost_cur; YE=y2; XN=x; YN=y; endend8、problem3_3.m%在如图所示的虚线上，运用蒙特卡罗的方法随机生成点E，通过A、E两点，用第一题的结论得到会合点C的坐标clear,clcp=7.2;%管道费用pA=5.6;pB=6.0;p3=21;%拆迁附加费cost_city=pB+p3;%城区管道费用,含拆迁费xE=15;y1=5;%坐标

32、yE=0:0.01:8;n=length(yE);cost_min=100000;for k=1 : n %用x2,y2表示E点坐标，相当于第一题中的B点坐标。 x2=xE;y2=yE(k); %调用problem3_monte_carlo, x,y即为N点坐标 cost_tixing,x,y=tixing_monte_carlo(0,5,x2,y2,pA,pB,p); %当前这一次循环的费用 cost_cur=cost_city*distc(20,8,x2,y2)+cost_tixing; if cost_curcost_min cost_min=cost_cur; YE=y2;XN=x;YN=y; endend18