逢山开路模型 清华大学陈连飞林涛兰蒿 指导教师高策理 编者按本答案对于地貌、路线、裕量和环境等因素所作的假设基本合理,在确定了几个 控制点(桥头,隧道口)后,对一般路线提出了两个模型:利用等高线决定最大坡度路线和在小方 格内进行局部优化,本答案特别在居民点东面设一分又点,分别通往桥西头和隧道南口,这在工 程设计上有所创新对一般路线虽然是局部寻优,但总成本是370万元,较合理 摘要本文讨论的是在山区修建公路的路线选择问题 针对问题,本文阐述了局部优化的原理,并根据这个原理提出了对山区的具体情形 设置控制点的方法这种设置控制点局部优化的方法对一般修路问题都适用 2结合具体实例,详细说明具体的设置控制点局部优化方法 3.利用计算机进行计算并配以图形≤a处理显示,说明这种方法 4.对其他方法进行一些比较和讨论,考虑各种方法对本类问题的适用性 问题的提出 在某山区修建公路已知该山区的地形高度分布该山区里有一东西走向的山峰,以及 一山口湖.雨季时山口湖溢出在山谷形成溪流,最大水面宽度与溪流最深处的x坐标近似满 足 w(x) x-2400 +5(2400≤x≤4000) 现在设计一条线路,从(0,800)出发,经居民点(4000200到矿区(20004000段 工程的单位成本和路段坡度的限制已知 (1)提出一个较经济的方案,包括原理、方法、线路位置和工程成本 (2)居民点改为3600≤x≤4000,2000≤y≤2400居民区,而公路只需经过居民点即 可,那么设计方案做何变动? 工程种类 般路段桥梁 隧道 300 20001500(长度≤300m) 工程成本(元/m) 3000长度>300m) 对坡度a的限制a<0.125a=0 符号系统 A→B:表示从A到B的公路 R(A→B):所有从A到B的可行路线的集合 cost(A→B):建造公路A→B的成本
30 全国大学生数学建模竞赛优秀论文汇编 length(A→B):公路A→B的长度 J=|T1=1:T;为公路类型 T1=一般公路,T2=桥梁,T3=长度小于等于300m的隧道 T4=长度大于300m的隧道 a(T):对T的倾斜度限制 P(T):对T的单位距离工程成本 问题分析 设{A1Na是公路A0→AN上N+1个点的集合,定义T(A→A4+1)为公路Ak→A+1 的类型 上式成立的条件是A→A41和A→A+1没有重叠部分,其中:k≠k,在此条件 下 cost(A0→AN) A。→A∈R(Aa→A) cost(A4→Ak+1) A∈R(A→Ax)=0 i cost((A→Ak+1) length(A4→Ak+)上 由上式,我们可以进行分段讨论,我们可在整条路上取几个控制点{A1N0.设定T(k) =T(Ak→A4+1),与A4→A4+1的具体线路无关控制点A1的选择是根据具体情况分析得 到的 对本题,考虑到桥染和隧道成本远高于一般公路,因此在线路设计时往往为节省成本而 让一般公路多绕几个弯 利用 MATLAB软件,我们将数据画成等势图和三维视图,可以看出 1.从起点到居民点须经过一条小谷,雨季形成溪流 2.从居民点到矿区,有一山峰阻挡,且高度很高,坡度很陡 因此,我们设置控制点: A0:起始点(0,800) A1:狭谷西岸(待定) A2:狭谷东岸(待定) A3:居民点(4000,2000 A4:山峰南侧某处(待定) A5:山峰北侧某处(待定) A6:矿区(2000,4000) A1→A2:T(1)=桥梁 A4→As:T(4)=隧道
逢山开路模型 31 其余道路为一般公路 对第二个问题A3改成待定,在范围3600≤x≤4000内.且2000≤y≤2400 模型假设 1.地貌假设:假设题目提供的数据是精确和充分的在四个相邻数据点间的单位矩形 内没有太大起伏如果两条对角线两端数据的均值的差远小于矩形边长,侧可以近似认为该 矩形为平面 2.路线假设;三 a.只考虑公路为一几何线而不计其宽度,忽略横向坡度对宽度的限制 b.设计路线时,暂不考虑路线急转弯角度、缓急的限制 c.不考虑地质情况及气候条件等的影响 3.裕量假设 a.不妨假设溪流宽度已经留有桥梁高于水面的余地 b.坡度的上限也包含裕量 4.环境假设 a,假设该地区内无原公路可利用 b新修公路应限于所给区域内 20D0 3000 5000 10002000300040005000 图1模型一 图2地貌图 模型设计与结果 模型一 这一模型比较简单.只用于确定两个控制点间的最短路径 从等势图上可以看出,两点间的坡度为高度差除以两点间的水平距离设起始点高h, 等高线间高度差为△h若以起始点为中心,为半径作圆弧,交h0+△Mh和h0-M对应的 等高线于A,B两点,则这两点间圆弧上各点的高度h满足h+Mh≥h≥h0-Mh,则从 起始点到这些点的坡度小于a0,可从这些点中选取某点为第一步的终点例如想尽量爬高 时选ho+Mh的点 如图1所示,为本问题的初步路线 这一方案直观、简便缺点首先是不精确,只能得到大概的路线其次在坡度变化大的地
32 全国大学生数学建模竞赛优秀论文汇编 方需要等势线足够密(即△h足够小)才能实现 二、模型二 1.道路的选择(一般公路) 两个控制点之间,如何选择合适道路使长度短而坡度满足要求,是决定成本的重要条 件,也就是怎样实现区域优化,我们选择了逐步定线的方法原理与模型一有相似之处 先将A→A分an→a1→a2→…成若干段,a,是位于某单元矩形的边上的点,a a.,同是直线段,坡度小于或等于a的最大值且方向尽可能地靠向a→A,的直线方向 如图3所示,设a;位于矩形1和矩形2的棱上,除a;所在棱外还有6条棱,记为l1 l6·不妨设a:与A,的连线交l1-l6中某棱于P0点,可由假设1认为P3,P4间是直线由 此求出P0点的高度,从而求出a,→P0的坡度,设为a0 图3 当1a01<0.125时,取a1,为Po 当|a01>0.125时.再在P附近棱上找P,使a1对P的坡度正好为0.125,且a P与 a→A的角度偏差最小设(x1,y1),(x2,y2)为靠近a1→A的一条棱,且这两点中 对应a,的坡度一个大于0.125,一个小于0.125,那么可以知道该棱上必可找到坡度等于 0.125的点设该点为(xo,yo) 不妨设x0=x1=x2, 1由方程:y-y2)2x1+(y [(x0-xn)2+(yv )2)=y×0.125决定, x1,x2是(x1,y1),(x2,y2)点的高度.x是点a,的高度 |1a>0.125 (主要考虑上下坡问题) 1a<-0.125 易知这样的解是存在的,利用这个解求出P'即是a,依次进行下去逐步接近A 般情况下,这样的路线是较优的 2.山谷溪流的处理和桥梁 从图中和表中可以看出,谷底是直线的,谷的两侧基本也是对称的可以由此算出雨量 最大的液面界限 谷底方程:x+y=48002400≤x≤4800
逢山开路模型 面 图4模型二之方案 西岸方程:4800-x-y= x=y+4800 (2400≤x≤4800) 东岸方程:x+y-480=号 y+4800 (2400≤x≤4800) 其中:w(x) 4800 由于桥的成本与一般公路相比较高,所以建桥最好使桥正好跨在两岸的界限上,同时要 顾及桥的两端高度相等 3.隧道位置的选择 由于隧道的成本很高.且长度超过300m后成本增长一倍.因此最好能选择长度小于 300米的隧道从等势图上可以看出.x=4400处的山峰特别尖,在这里修隧道可能实现这 点.因此以下计算中固定隧道位置的横坐标x=4400 想让隧道的长度小于300m,需将路修到一定高度如图5所示,对水平隧道 300×650 ZC=150 650 1266 Termin 图5模型三