全国大学生数学建模竞赛优秀论文汇编 即使有坡度,隧道高度也不能低于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万元,多数答案在建立数学模型时提出 的假设条件是比较合理的,分析问题也比较细致,但在确定出最优路线后,进一步对结果进 行稳定性分析的答案很少,这是一个不足之处 总起来看,通过各个参赛队的认真细致的分析和计算,大多数答案都取得了相当好的成 绩,彼此水平差距并不大,一、二等奖是从横向比较选择出来的