《数学建模竞赛B题 最优路线设计问题.doc》由会员分享，可在线阅读，更多相关《数学建模竞赛B题 最优路线设计问题.doc（10页珍藏版）》请在三一文库上搜索。
1、“井冈杯”题目：B题 最优路线设计问题本科组 : 刘佳敏 10数学本（2） 100512010 15679613675 陈殷章 10数学本（2） 100512061 13687969785张奇 10电信本（1） 100916010 15679666827数学建模竞赛井冈山大学摘要 本论文根据题意，要求最优管线铺设路线，只要求出管线与各地质层的交点即可，运用数学规划的思想，在已知管线与各地质层的交点的情况下，每个地质层间的直线铺设无疑是最短的，因此对于问题一建立了规划模型，运用lingo软件求出了满足条件的最优管线铺设路线。问题二在问题一的基础上进行推广，加入了管线转弯时角度至少为160的限制，
2、在通过一系列的几何计算后，将转弯时角度的限制转化为地质层交界面与管线交点的横坐标X1的取值范围的约束在问题一的模型的基础上建立新的模型。对于问题三，要求管线经过已知点，通过将原来点所在地质层用平行于横轴的直线重新划分为两个新的地质层，将约束条件要求管线经过已知点，转化为管线与两个新地质层交面的交点为点，按照对之前对交点处理方法容易将约束条写成表达式，加入新的约束条件后，对模型用lingo求解就可以得到最优管线铺设路线。最后本文还将模型推广能到处理一般的地质分布情况。【关键词】线性规划；条件转化；lingo求解。1最优路线设计问题一 问题的重述准备在A地与B地之间修建一条地下管线，B地位于A地正
3、南面26km和正东40km交汇处，它们之间有东西走向岩石带。地下管线的造价与地质特点有关，下图给出了整个地区的大致地质情况，显示可分为四条沿东西方向的地质带，其宽度分别为：沙土地质带宽C1,C5；沙石地质带宽C2；岩石地质带宽C3；沙石土地质带宽C4。在给定三种地质条件上每千米的修建费用的情况如下：地质条件沙土沙石土沙石岩石费用(万元/千米)12161828试解决以下几个问题：(1) 图中直线AB显然是路径最短的，但不一定最便宜；而路径ARSB过岩石和沙石的路径最短，但是否是最好的路径呢？试建立一个数学模型，确定最便宜的管线铺设路线。（若C1=6，C2=4，C3=5，C4=6，C5=5，确定最
4、便宜的管线铺设路线。）(2) 铺设管线时，如果要求管线转弯时，角度至少为1600，确定最便宜的管线铺设路线。(3) 铺设管线时，如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P（位于A地正南面18km和正东30km交汇处）时，确定最便宜的铺设路线。二 问题的分析在修建地下或管线或者进行公路建设时，由于地质结构复杂性，不同的地质结构将会有不同的造价，为了更好的节约资源，我们不得不对铺设路线进行规划。2现准备在A地与B地之间修建一条地下管线，B地位于A地正南面26km和正东40km交汇处，给出整个地区的大致地质情况及各种地质条件上每千米的修建费用等，要求建立数学模型，求出满足条件下的
5、最便宜的铺设路线。 三 模型的假设与符号约定3.1模型的将基本假设（1）假设各地质带的交界呈直线走向。（2）假设各地质带内部分布及特点呈理想化状态，无空洞。（3）不考虑天气状况对施工的影响（所需费用提升）。3.2 符号的约定；Z:管线总造价；。四 模型的建立与求解4.1.1问题一模型的建立 如图1所示,对区域进直角坐标化:Y（0,0）X40km26km图140km（0,0） 3从图中可知直线AB是所有线路中最短的，但不一定最便宜；可是如果已知点与，显然直线是最短的路线，而到段的总造价也是最低的。由图1可知： AX1=c12+x12 X1X2=c22+(X2-X1)2 X2X3=c32+(X3-
6、X2)2 X3X4=c42+X4-X32 X4B=c52+(40-X4)2(其中C1=6,C2=4,C3=5,C4=6,C5=5) 由于每段都是最低造价，所以总造价也是最低的，我们可以得出以下的规划模型。 minZ=12（AX1+X4B）+18X1X2+28X2X3+16X3X4 Xi+1Xi s.t. X10 X4404.1.2 问题一模型的求解 问题一模型是一个线性规划,利用lingo软件可以容易求得结果。此时可得： X1=15.67886X2=18.86159X3=21.04549X4=26.93428Z=748.6244 4.2.1 问题二模型的建立 问题二是对问题一的一个扩展，增加了
7、要求转弯时要求转角大于160的限制，可通过如图2所示方法，将转角的限制转化为坐标上长度的限制，对于有 .4图2对于点通过计算可求得与相交于处夹角为20两条直线的方程，通过直线方程又可求得与的横坐标，具体做法如下： 直线的倾斜角为，tan = -C1X1，=-arctan (C1X1)，与直线相交于处夹角为20的两条直线的斜率为：k=tan（20），通过公式可求得两条直线的方程。分别将两直线方程与y=C3+C4+C5联立解方程组就可求出与的横坐标。同理可求得与的横坐标，将转角的限制转化为坐标上长度的限制, ,可得如下模型： min Z=12(AX1+X4B)+18X1X2+28X2X3+16X3
8、X4 Xi+1Xi X10 s.t. X440 C1+C2+C3+C4+C5=26 AiXi+1Bi 4.2.2 问题二模型的求解对问题二模型求解同问题（1）进行求解。4.3.1 问题三模型的建立问题三又是对问题的进一步推广，要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点（30,8）。如图3所示，过点作一个与轴平行的新的地质层交界面，不过这个新的地质层交界面两边都是沙石。新的地质交界面图3 5假设新地质层交界面将之前宽为C2的f2沙石地质层划分为宽分别为C6和C7的两个地质层，在对新地质层交界面处理时，只需让管线与新地质层交界面交点为点就可以了，与其它地质层交界面不同的是新地质层交界
9、面与管线的交点是确定的。在经过转换后我们可以得出以下模型。min Z=12(AX1+X4B)+18（X1P+PX2）+28X2X3+16X3X4 Xi+1Xi 30X10 X230 X440 s.t. C1+C2+C3+C4+C5=26 X1P= c62+(30-X1)2 PX2= c72+(X2-30)2 4.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五 模型的进一步
10、讨论及分析5.1 模型的评价本论文运用数学规划的思想，从问题出发，运用代数语言抽象出规划模型，不仅很好的解决了本题中的问题，而且具有很好的移植性,能很好的解决同类的问题，数学推导严谨，理论性强。但是由于是基于本题中的问题，本题中还有许多因素没有考虑，在用这个模型处理其它问题时难免要加入不少的限制条件，才能满足要求。5.2 模型的推广本论文的模型是基于本题中的条件而建立模型的，本题中的地质层是呈带状直线走向，对于地质层不是呈带状直线走向而是弯曲的曲线（而这更合乎实际），只需将本模型稍加推广即可解决。6如图4所示，首先将铺设区域划分为一个个小的矩形区域，地质层交界的曲线将被这些小矩形分许多小段，每
11、小段曲线可以通过求均值或其它方式求得一条平行于横轴的直线，用直线段代替原曲线段，如有多个地质层做同样的处理，在用原有模型求解时只需用每一小段线段所在的直线代替原模型的地质层交界直线，运用编程搜索求解，只要求出的解都在小线段横轴范内并且相对最优就是要求的解，但这不是最优的解，要得到更优的解可对所求出解所在的小线段细分再求解。虽然不一定能求出最优解，但对于生产实际来说已达到优化可行的要求。取两小段计算,并把的取值限制在两段线段之内再求解.图4六 参考文献1 刘桂真等，运筹学，山东，山东大学出版社，1999年2 刁在筠等，数学规划，济南，山东教育出版社，1997年3 施光艳等，最优化方法（第二版），
12、北京，高等教育出版社，2007年4 钱颂迪等，运筹学，北京：清华大学出版社，2005年9月七 附录7.1模型一的lingo求解 Lingo编程 model:min=12*(sqrt(36+x12)+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=x1;x3=x2;x4=x3;x1=30;x1=0;x4=40;end结果输出 Local optimal solution found. Objective value: 675.12
13、42 Extended solver steps: 5 Total solver iterations: 160 Variable Value Reduced Cost X1 25.46401 0.000000 X4 33.75698 0.000000 X2 31.50348 0.000000 X3 31.92227 0.0000008 Row Slack or Surplus Dual Price 1 675.1242 -1.000000 2 6.039468 0.000000 3 0.4187932 0.000000 4 1.834712 0.000000 5 4.535989 0.000000 6 1.503479 0.000000 7 25.46401 0.000000 8 6.243016 0.0000009