逢山开路模型 清华大学陈连飞林涛兰蒿 指导教师高策理 编者按本答案对于地貌、路线、裕量和环境等因素所作的假设基本合理,在确定了几个 控制点(桥头,隧道口)后,对一般路线提出了两个模型:利用等高线决定最大坡度路线和在小方 格内进行局部优化,本答案特别在居民点东面设一分又点,分别通往桥西头和隧道南口,这在工 程设计上有所创新对一般路线虽然是局部寻优,但总成本是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 当1a010.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模型三
全国大学生数学建模竞赛优秀论文汇编 即使有坡度,隧道高度也不能低于1240m.对于矿区,高度1320m可以实现这一点.对于居 民区,高度950m,上升到这个高度相当困难.本模型采取了迂回绕道的方法达到爬高的目 的.显然这样做省下的遂道成本远大于多修公路的成本 4.模型的实现 对本模型我们使用了 FORTRAN语言编程实现通过上机算出两种方案 方案一:路径总长度10.685km,总费用3704.6千元 方案二:路径总长度10.802km,总费用4266.0千元 (除模型三中举出一例,其它模型结果具体路径见附录) 5.模型的不足 1.对地貌假设的范围.由地貌假设,每个单元矩形近似平面,这在山两侧不成立,会影 响桥的位置 2.采用迁回绕道的方法虽然最后隧道符合要求,但拐弯过于尖锐,实际需改进 ym)的形 图6 三、模型三 模型三是在模型二的基础上改进而成 1.模型三仍采用局部优化,逐步定线的方法 2.在河谷和山脊附近的地貌假设不合理,如x∈[2800,3200],y∈[1200,1600]这个 区域四个顶点高度分别为1300,700,1040,900,则(1300+900)2-(1040+700)2=230, 对这么大的差值仍将该矩形视为平面,显然不太合理 考虑到实际情况,可以将这类矩形近似成两个三角平面,其公共边是地表的一条凸出或 者下陷的线这要通过三维视图判断哪条对角线是公共边 根据这一假设,公路到了岸边的高度后,还要经过下降的坡才能到桥边,因此公路过桥 前还要沿河边走一段路才行这与模型二是不一样的我们在处理山脊附近的点的情况时, 也采用了这种假设这样得到的数据点更多,更精确 3.从居民点到隧道的爬高过程仍是一个难题考虑到按上一假设计算桥东头到居民 点的路上的有些点也很高,我们可以这样处理:假如公路允许分叉的话,我们可以在桥东侧 到居民点某处再取一个控制点A,将原来的A2→A3→A变成了A2→A 这样
逢山开路模型 方面减低公路总长,另一方面可以降低迂回绕道的次数和角度 4.为了得到精确的结果,我们采用 Mathematica软件逐点计算,应用该模型解决问题 结果如下: x=(0 12001600 3017,7 2925.4 2677.62677,6271 203003 360033253527.432003457.236003786.84000440044004000 360032003138.5280024002000) (800639.6474.6419,84198486.9666800120012121382 16001819.7200020892122.52109.12000195018751857.72000 18757187520002033.624002465.228002966.63080.83296,73345.4 3457.2.3561.236003930.43965.24000) 其中x向量是所得路径的横坐标,相应的y向量是所得路径的纵坐标 路径的总长度:10.72273km 总费用:357.4941千元 桥梁位置(2677.56,2089.033)—(2710.96,2122.45) 桥长:47.24m 桥费用:94489元 隧道位置:(4400,3080)—(4400,3296.74) 隧道长度:217.12m 隧道造价:325525元 模型三的结果分析: 由于三角平面的近似,使公路在桥边必须缓慢下坡这样使得桥的位置上移,长度减小 可以看出模型三的结果比模型二的更合理更实用 四、用模型三解决问题二 对问题二,相当于把控制点A3改为可变,其位置由(40002000改为3600≤x≤4000 2000≤y≤2400我们在区域里取了几个点进行计算.结果为 1000200030004000500 图7问题二之方案一 图8问题二之方案二
全国大学生数学建模竞赛优秀论文汇编 方案一总路径长10.1315km,总费用338.024万元 方案二总路径长10.0995km,总费用337.054万元, 从结果上看,这两个点的选取确实降低了造价而就这两点比较,造价很接近 模型的设计与分析 桥址的选择对总成本的影响 桥址的选择即A1,A2的选择.用模型二试计算: 第一种情况:A1=(3080.79,1651.40),A2=(3133.72,1782.60) ength(A1→A2) cost=3704.6千元 第二种情况:A1=(3092.09,1653.59),A2=(3138.58,144.09) length(A1-A2)=405. 4m cost=4266千元 可见桥址的选择与造价有很大关系应尽量使桥短些 二、居民点的变化对总成本的影响 对模型三,令居民点(4000,2000),cost=3557.49万元 居民点(3600,2000),cost=3380.24万元 居民点(3600,2400),cost=3370.54万元 对后面两种情况,△y=400,△y/y=20%,而2cs=0.3%,可知居民点的变化对总成 本的影响不大 讨论及优缺点 1.与连续模型的比较 对地面起伏不大,数据充足情况下,可以分区拟合地面的函数设为f(x,y,z)=0.那 么可用变分法求最佳路径 x(0)=A x(1)=B f(x,y,z)=0 不过,对地面起伏不大的地区,我们的方法也适用,且结果与变分法的相差不会大,而 对于地面不规则的地区,如本问题,则用变分法是求不到解的 2.三个模型的精确程度为:模型一较差,模型二较好,模型三最好.而模型二和三的计 算量大 3.本模型的优点在于灵活性好,得到的结果接近实际,通过灵敏度分析可以知道哪些 点的选择要求灵敏度高,需要进一步测量 4.我们无法证明我们得到的方案最佳,另外在选择路线时只考虑了成本,没有考虑使 用是否方便及长期经济效益 5.改进方向:可以加入其他条件的限制,使得到的方案更加实用
关于“逢山开路”赛题的分析和答卷评阅 中国科学院应用数学研究所 韩继业 本题的构思保留了工程实际背景的一些基本特征,涉及到地貌、路线、环境等自然条件 以及费用系数,这些在实际的工程设计上必须注意的重要因素我们在解决本题时也应考虑 到在用数学模型方法解题时,除了从数学角度上思考问题的求解之外,适当地考虑有关实 际因素,对于我们建立合理的数学模型提供了重要的依据条件,也会使我们设计的解题方法 比较可行和有效本题在这一方面表现得更加明显 本題的重要步骤是求两点间的最短路由于要在河流上架桥及开挖隧道,直接求从山脚 S到居民点R再到矿区M的最小费用的路线是困难的.一种简便方法是先根据对地形和不 同路段费用系数的分析,确定桥头和隧道口的若干候选地点,然后寻求从S到桥西头B 桥东头B2到R,从R到隧道南口D1和从隧道北口D2到M的最短路,也是最小费用路 径,其中B1,B2和D1,D2均有若干候选点最后再综合考虑修桥和隧道的费用,从候选路 径得到全局最小费用路线 下面介绍求两点(如S和B1)间最短路的一种方法 图1表示一个图G=(V,E),V是顶点V1,…,V的集合,E是连接顶点的弧的集合, 弧旁的数字不妨看作二顶点间的距离.求图中任意两点间最短路的一种有效算法是 Dijkstra 提出的所谓标号法,用它可以同时求出从图中某一点(如V1)到其他各点的最短路,因而适 合于本题中求S到有若干候选点的B1的最短路问题 这个方法的基本思想是从起点V1开始,逐步地 寻找到达各点的最短路,在每一步都对每一顶点记录 个数,称为该点的标号.它表示V1到该点的最短距 离的上界(称T标号),或者就是V1到该点的最短距 离(称P标号)实际上每一步都通过比较把至少一个 具有T标号的点变为P标号,这样最多经过9-1=8 步就可以找到V1到各点的最短路 将 Dijkstal方法用于求本题的最短路时,必须确 定图的顶点集V和弧集E.这可以在原来网格的基础 图1 上构造,现给出两种形式 对原网格加密.如将400m×400m加密为100m×100m,新格点构成图的顶点集 V,如图2所示(新格用虚线表示),其高度(x坐标)由原格点插值得到图的弧集E可以只 包括x方向和y方向的路径,这时相邻两顶点V1,V1间的距离,即弧长d定义为(且考虑 到坡度限制) [(△x)2+(△z)2] A(≤0.125
全国大学生数学建模竞赛优秀论文汇编 其中△是v与V的x坐标之差,△x=100m,且可视为△y=100m弧集E也可以包括 对角线方向的连线如图中左上角的格子所示,这时d应定义为 (△x)2+(△y)2+(△z)2], △z (△x)2+(△2)2)≤0.125 d (2) (△x)2+(4y)2)>0.125 2.对原网格只作200m×200m的加密,然后在新网格的边上细分.如分为50m一个 点,构成顶点集V.而弧集E由某顶点出发到它相邻的2个(或4个)新方格内任一点的连 线构成,如图3所示,这时d的定义同(2)式,图中折线表示一条从V1到V2的路径 图2 图3 顶点集V和弧集E一经确定,就可以直接用 Dijkstra方法求图上任一点到其他各点的 最短路了 这次数模竞赛中本题的绝大多数答案都利用了平面上格点的加密,以及地面高度的插 值插值的方法多为线性插值,少数答案为了使结果更精确,还利用了局部二次或 三次 大多数答案也都先根据地形和不同路段的费用系数的分析和计算,提出了桥和隧道的几个 可供选择的地点然后再对整个路线进行优化考虑,最后确定出各自的最优路线但大多数 答案中确定最优路线的数学方法不够先进,只有很少数答案提出了一般路线的优化模型,或 叙述了动态规划方法,但又缺乏动态规划方法计算过程的说明与分析多数答案对整个路线 的优化方法主要是通过对几种不同方案的比较来得到;部分答案在确定局部路线时基本上 是用图上作业方法,即在等高线图上沿着允许坡度的路线来确定,这样得到的路线的总费用 往往偏高但是多数答案的总费用仍属于可以接受的范围某些答案确定的路线的总费用过 于高,其原因多为隧道和桥的位置选择得不合理,致使过长,例如桥长超过了100m,隧道长 超过了500m,这使得整个路线的总费用超过了400万元,多数答案在建立数学模型时提出 的假设条件是比较合理的,分析问题也比较细致,但在确定出最优路线后,进一步对结果进 行稳定性分析的答案很少,这是一个不足之处 总起来看,通过各个参赛队的认真细致的分析和计算,大多数答案都取得了相当好的成 绩,彼此水平差距并不大,一、二等奖是从横向比较选择出来的
