数学建模竞赛

井冈山大学数学建模竞赛“井冈杯”题目：B题最优路线设计问题本科组:刘佳敏10数学本（2）10051201015679613675陈殷章10数学本（2）10051206113687969785张奇10电信本（1）100916010156796668271摘要本论文根据题意，要求最优管线铺设路线，只要求出管线与各地质层的交点即可，运用数学规划的思想，在已知管线与各地质层的交点的情况下，每个地质层间的直线铺设无疑是最短的，因此对于问题一建立了规划模型，运用lingo软件求出了满足条件的最优管线铺设路线。问题二在问题一的基础上进行推广，加入了管线转弯时角度至少为160°的限制，在通过一系列的几何计算后，将转弯时角度的限制转化为地质层交界面与管线交点的横坐标X1的取值范围的约束在问题一的模型的基础上建立新的模型。对于问题三，要求管线经过已知点P，通过将原来P点所在地质层用平行于横轴的直线重新划分为两个新的地质层，将约束条件要求管线经过已知点P，转化为管线与两个新地质层交面的交点为P点，按照对之前对交点处理方法容易将约束条写成表达式，加入新的约束条件后，对模型用lingo求解就可以得到最优管线铺设路线。最后本文还将模型推广能到处理一般的地质分布情况。【关键词】线性规划；条件转化；lingo求解。12最优路线设计问题一问题的重述准备在A地与B地之间修建一条地下管线，B地位于A地正南面26km和正东40km交汇处，它们之间有东西走向岩石带。地下管线的造价与地质特点有关，下图给出了整个地区的大致地质情况，显示可分为四条沿东西方向的地质带，其宽度分别为：沙土地质带宽C1,C5；沙石地质带宽C2；岩石地质带宽𝐶3；沙石土地质带宽C4。在给定三种地质条件上每千米的修建费用的情况如下：地质条件沙土沙石土沙石岩石费用(万元/千米)12161828试解决以下几个问题：(1)图中直线AB显然是路径最短的，但不一定最便宜；而路径ARSB过岩石和沙石的路径最短，但是否是最好的路径呢？试建立一个数学模型，确定最便宜的管线铺设路线。（若C1=6，C2=4，C3=5，C4=6，C5=5，确定最便宜的管线铺设路线。）(2)铺设管线时，如果要求管线转弯时，角度至少为1600，确定最便宜的管线铺设路线。(3)铺设管线时，如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P（位于A地正南面18km和正东30km交汇处）时，确定最便宜的铺设路线。二问题的分析在修建地下或管线或者进行公路建设时，由于地质结构复杂性，不同的地质结构将会有不同的造价，为了更好的节约资源，我们不得不对铺设路线进行规划。现准备在A地与B地之间修建一条地下管线，B地位于A地正南面26km和正东40km交汇处，给出整个地区的大致地质情况及各种地质条件上每千米的修建费用等，要求建立数学模型，求出满足条件下的最便宜的铺设路线。21三模型的假设与符号约定3.1模型的将基本假设（1）假设各地质带的交界呈直线走向。（2）假设各地质带内部分布及特点呈理想化状态，无空洞。（3）不考虑天气状况对施工的影响（所需费用提升…）。3.2符号的约定51,:iiifi由图示由上到下分别为其中个地质带第；的交点个地质带交界面与管线与1:iiiff；的距离与点11:xAAx；的距离与点11:iiiixxxx；的距离与点点BxBx44:；Z:管线总造价；取值的下界1:iiA；取值的上界1:iiB。四模型的建立与求解4.1.1问题一模型的建立如图1所示,对AB区域进直角坐标化:从图中可知直线AB是所有线路中最短的，但不一定最便宜；可是如果已知点i与1i，显然直线1ii是最短的路线，而i到1i段的总造价也是最低的。图126kmY40kmX（0,0）32由图1可知：AX1=√1212X1X2=√2221X2X3=√3232X3X4=√4243X4B=√524(其中C1=6,C2=4,C3=5,C4=6,C5=5)由于每段都是最低造价，所以总造价也是最低的，我们可以得出以下的规划模型。minZ=12（AX1+X4B）+18X1X2+28X2X3+16X3X4Xi+1Xis.t.X10X4404.1.2问题一模型的求解问题一模型是一个线性规划,利用lingo软件可以容易求得结果。此时可得：X1=15.67886X2=18.86159X3=21.04549X4=26.93428Z=748.62444.2.1问题二模型的建立问题二是对问题一的一个扩展，增加了要求转弯时要求转角大于160°的限制，可通过如图2所示方法，将转角的限制转化为坐标上长度的限制，对于1i有iiiBA1.图241对于点1通过计算可求得与1A相交于1处夹角为20°两条直线的方程，通过直线方程又可求得1A与1B的横坐标，具体做法如下：直线1A的倾斜角为µ，tanµ=--C11⁄，µ=-arctan(C11⁄)，与直线1A相交于1处夹角为20°的两条直线的斜率为：k=tan（µ20°），通过公式)(00kyy可求得两条直线的方程。分别将两直线方程与y=C3+C4+C5联立解方程组就可求出1A与1B的横坐标。同理可求得iA与iB的横坐标，将转角的限制转化为坐标上长度的限制,iiiBA1,可得如下模型：minZ=12(AX1+X4B)+18X1X2+28X2X3+16X3X4Xi+1XiX10s.t.X440C1+C2+C3+C4+C5=26AiXi+1Bi4.2.2问题二模型的求解对问题二模型求解同问题（1）进行求解。4.3.1问题三模型的建立问题三又是对问题的进一步推广，要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P（30,8）。如图3所示，过P点作一个与轴平行的新的地质层交界面，不过这个新的地质层交界面两边都是沙石。新的地质交界面图352假设新地质层交界面将之前宽为C2的f2沙石地质层划分为宽分别为C6和C7的两个地质层，在对新地质层交界面处理时，只需让管线与新地质层交界面交点为P点就可以了，与其它地质层交界面不同的是新地质层交界面与管线的交点是确定的。在经过转换后我们可以得出以下模型。minZ=12(AX1+X4B)+18（X1P+PX2）+28X2X3+16X3X4Xi+1Xi30X10X230X440s.t.C1+C2+C3+C4+C5=26X1P=√21PX2=√224.3.2问题三模型的求解对于问题三模型，可利用lingo求解,不妨取C1=12，C2=8，C3=1，C4=2，C5=3，C6=6，C7=2进行计算，可以求得：X1=25.46401X2=31.50348X3=31.92227X4=33.75698Z=675.1242五模型的进一步讨论及分析5.1模型的评价本论文运用数学规划的思想，从问题出发，运用代数语言抽象出规划模型，不仅很好的解决了本题中的问题，而且具有很好的移植性,能很好的解决同类的问题，数学推导严谨，理论性强。但是由于是基于本题中的问题，本题中还有许多因素没有考虑，在用这个模型处理其它问题时难免要加入不少的限制条件，才能满足要求。5.2模型的推广本论文的模型是基于本题中的条件而建立模型的，本题中的地质层是呈带状直线走向，对于地质层不是呈带状直线走向而是弯曲的曲线（而这更合乎实际），只需将本模型稍加推广即可解决。如图4所示，首先将铺设区域划分为一个个小的矩形区域，地质层交界的曲线将被这些小矩形分许多小段，每小段曲线可以通过求均值或其它方式求得一条平行于横轴的直线，用直线段代替原曲线段，如有多个地质层做同样的处理，在用原有模型求解时只需用每一小段线段所在的直线代替原模型的地质层交界直线，运用编程搜索求解，只要求出的解都在小线段横轴范内并且相对最优就是要求的解，但这不是最优的解，要得到更优的解可对所求出解所在的小线段细分再求解。虽然不一定能求出最优解，但对于生产61实际来说已达到优化可行的要求。取两小段计算,并把ix的取值限制在两段线段之内再求解.图4六参考文献[1]刘桂真等，运筹学，山东，山东大学出版社，1999年[2]刁在筠等，数学规划，济南，山东教育出版社，1997年[3]施光艳等，最优化方法（第二版），北京，高等教育出版社，2007年[4]钱颂迪等，运筹学，北京：清华大学出版社，2005年9月七附录7.1模型一的lingo求解Lingo编程model:min=12*(@sqrt(36+x1^2)+@sqrt(25+(40-x4)^2))+18*(@sqrt(16+(x2-x1)^2))+16*@sqrt(36+(x4-x3)^2)+28*@sqrt(25+(x3-x2)^2);x2=x1;x3=x2;x4=x3;x1=0;x4=40;end结果输出Localoptimalsolutionfound.Objectivevalue:748.6244Extendedsolversteps:5Totalsolveriterations:19272VariableValueReducedCostX115.678860.000000X426.934280.000000X218.861590.000000X321.045490.000000RowSlackorSurplusDualPrice1748.6244-1.00000023.1827320.00000032.1838950.00000045.8887980.000000515.678860.000000613.065720.0000007.2模型二的lingo求解如，模型一7.3模型三的lingo求解Lingo编程model:min=12*(@sqrt(144+x1^2)+@sqrt(9+(40-x4)^2))+18*(@sqrt(36+(30-x1)^2)+@sqrt(4+(x2-30)^2))+16*@sqrt(4+(x4-x3)^2)+28*@sqrt(1+(x3-x2)^2);x2=x1;x3=x2;x4=x3;x1=30;x2=30;x1=0;x4=40;end结果输出Localoptimalsolutionfound.Objectivevalue:675.1242Extendedsolversteps:5Totalsolveriterations:160VariableValueReducedCostX125.464010.000000X433.756980.000000X231.503480.000000X331.922270.000000RowSlackorSurplusDualPrice811675.1242-1.00000026.0394680.00000030.41879320.00000041.8347120.00000054.5359890.00000061.5034790.000000725.464010.00000086.2430160.0000009