逢山开路问题1

《逢山开路问题1》由会员分享，可在线阅读，更多相关《逢山开路问题1（20页珍藏版）》请在装配图网上搜索。

1、华北科技学院课程设计说明书班级：计算B101姓名:顾亚楠(201009014110)成绩:班级：计算B101姓名:孔维文(201009014119)成绩:班级：计算B102 姓名:陈 灏(201009014214)成绩:设计题目:逢山开路问题设计时间:十九周周四 至二十周周一指导教师:李慧评语:评阅教师:逢山开路问题摘要：本文是逢山开路问题的研究，主要研究特定两点之间的最短路，以及 使得总成本最小。主要采用的方法是Dijkstra算法求两点间的最短路径，从而得 到一条最优的路线，再对其进行细化获得更加精确的路线。最后再进行逐步定线， 以局部最优为准则，逐步逼近目标点，得到较优解。由于在开路期间

2、会遇到湖泊，山脉，山谷等问题，所以要进行桥梁，隧道， 一般路段的各种搭建与组合，在对这三种不同形式的选择是，仔细划分了三种形 式在不同情况下应该满足的坡度条件，从而确定路径的权值。本问题保留了工程实际背景的一些基本特征，涉及到地貌环境等自然条件以 及施工能力,费用系数等人为因素，这些在实际的工程设计上必须考虑的重要因素 我们在解决本题时则须注意取舍,在用数学模型解题时，除了从数学角度上思考之 外,适当的考虑有关实际因素，从总体上设计,这对于我们建立合理的数学模型提 供了重要的依据,也会使我们得到的方案行之有效,本题在这方面表现得很明显通过分析我们得出比较满意的结果，桥长：73米，位置为：(29

3、00, 1800) 全(3000, 1900)之间的一段，隧道长：300米，位置为(4000, 2800)至(4000, 3100)之间的一段，公路长：12083米，得出最优的解价格：375.8万。关键词：Dijkstra算法目标最优化模型逐步逼近动态规划一、问题重述公路的修建是近几年我们国家不断进行实施的工程，尤其在某些偏远地区， 由于地理条件的影响，实施起来难度可能会很大，并且花费大量的资金。就目前 的情况来看，我国路段形式主要有三种：一般公路，隧道，桥梁。当我们要为某 地区修路时，可能会遇到湖泊，山脉，山谷，在这种情况下，显然用一种形式是 不能解决的，要对其进行组合。这时实施人员不仅仅要

4、考虑资金问题，而且还要 联系实际。我们通常会有一种想法：遇到湖泊绕道而走，遇到山谷搭建桥梁，遇到山峰 就挖隧道。但实际情况不是这样的，根据实际情况要考虑坡度的问题，由于三种 形式所用到的资金差距较大，因此要进行计算得出最优路线，从而使所用到的资 金最小。也就是用最少的资金，达到实际的目标。本问题要求是：要在一山区修建公路，首先测得一些地点的高程，数据见附录B(平面区域0忍x5600,0忍y4800表中数据为坐标点的高程,单位:米).数据显 示:在y=3200处有一东西走向的山峰;从坐标(2400,2400)到(4800,0)有一西北 东南走向的山谷;在(2000，2800)附近有一山口湖，其最

5、高水位略高于1350米，雨季 在山谷中形成一溪流，经调查知，雨量最大时溪流最高水面宽度W与(溪流最深处 的)x坐标的关系可近似表示为W(x) = (X2400 )3/4 + 5(2400x4000)2公路从山脚(0,800)处开始，经居民点(4000,2000)至矿区(2000,4000),已知路段工程成本及对路段坡度(上升高程与水平距离之比)的限制见附录B本文将研究下列问题：(1) 给出特定两点之间的最短路线。(2) 进一步给出精确的路线，包括隧道，桥梁，一般路段，再进行总成本的 计算，找出最优解。(3) 当两点之间改变为点到面之间时，我们进一步给出解法，求取最短路和 总成本。(4) 对于给

6、出的模型，我们将进行评价与改进。二、问题分析首先我们看到题目中给出了好多的数据，面对这么多的数据，我们首先就要 做出地形的三维图形(matlab软件)。但是我们要精确的测量，这些数据只能粗 疏表现，因此可能要对这些数据进行插值，拟合。其次我们看到山脚到矿区要经过居民区，这样我们寻求最短路方可割裂成两 部分，从山脚到居民区建立一个动态规划，再从居民区到矿区建立一个动态规划， 这样就形成了一个双阶段的动态规划。当建立好动态模型时，我们需要细化两个 阶段，分别对两个阶段不同的地形进行三种道路形式的选择。最后我们要进行最短路的寻求，利用Dijkstra算法。进一步设计出第二种方 案：逐步逼近方法寻求最

7、优解。以上的分析我们可以看出Dijkstra算法，逐步逼近，绘制三维图等都需要对 其进行编程，因此编程在此问题中占得比重很大。三、基本假设（1）地貌假设：山区各处高度变化是连续的，不存在断崖，断层；（2）路段假设：忽略公路、桥梁、隧道的宽度，路段按几何线来处理；（3）设计假设：不考虑修建分岔路，不考虑急转弯，缓急的限制；（4） 几何假设：除溪流处外，四个相邻的测量点近似构成矩形，因为相邻两点 的高度差远小于它们的水平距离，实测点数据准确无误。（5）环境假设：该地区工程地质条件满足工程建设的要求,不存在对工程建设 有害因素，如地震带、溶岩地区等因素，并且该地区无原公路可用；四、基本符号说明A起始

8、点（0，800）B居民点（4000，2000）X矿区（2000，4000）标网格中g i点和g中点间的径向距离；气Gi点和g点连线的边的权值；dist两点间的最短路；坡度控制点线路必须经过的点A，B,X五、模型的建立与求解1、由题目中的数据绘制三维图形：为了对该山区有一个立体形象,我们做出它的三维图，读者可以轻易的辨别河 谷及山脉走势，在matlab软件中输入代码（见附录A地貌代码），进一步进行 插值拟合方可得到精确的三维图图1山区立体图我们对地貌进行等势线的描绘，在matlab软件中输入代码(见附录A等势线代 码)，进一步进行插值拟合得到精确的等势线。图2等势线2、动态模型建立：画出三维图形

9、后我们要建立双阶段动态规划，具体见下:min f (/ ,l ,l )g q s代表意义：f:整段路的总成本1 g:公路的长度lq：桥梁的长度ls :隧道的长度。进一步地，对各个阶段有：阶段1： minf 1（l板l1q）（从A到B，经过溪流）（2）f i（li 疽 J =300x I 廉 +2000X / m g q&q阶段2： min f 2g,l2）（从B到X,经过山脉）300 x 12g +1500 x 12s 隧道 0.125的情况下可以考虑 修建“2”形路。“Z”形路的每一段的斜率都为0.125,所以，“Z”形路的总 长度为L8Aho隧道在坡度较大的情况下，可以修建“2”形路或隧道

10、，而修建隧道的成本较高，只有在坡度满足一定条件（见下面说明）时，修隧道比修“2”形路节省资金。隧道长度300米修建隧道的条件为：1500X（& + &2）300X16h艮即当吉+六-32时，修建300米的隧道，因为此时在AB段和AX段修建 一般公路的费用高于在BX段修建隧道的费用，BX段越长费用越低。当间的距 离300米时，在最低处修建隧道；当距离为300时，选择BC段的长度为最大值 300米，即先将公路修建到一定高度，再修隧道，可使费用最低。当+ + + 32时，修建一般公路。J I】+ - 16时，修建隧道V +罕 16时，修建公路侦 a 1 a 2al a 2 隧道长度300.米 当隧道

11、垂直穿过山脉，即。=90（见图3）时，隧道长度最短，我们按这 种方式修建隧道。桥梁在两种情况下可以修建桥梁：线路经过溪流、湖泊，且满足坡度相等的条件时;两座相邻高地的坡度满足条件看+右-2.4时，修建桥梁比修建公路节省 资金。在本题中，不存在满足这样条件的相邻高地，因此，在以下的讨论中不考 虑此情况。4、最优路径的选取：由2、3式可知，1g，12, 12g，/ 2 s都较短时，能得到较优的f、f。此时， gqg s1 2 问题已转变为求两点间的最短路。对于从山脚全居民区的AB段规划，以溪谷为对称轴，对溪岸的可修桥点进 行搜索，便可以从多个可能的最短路中找出最优路径；对于从居民区全矿区的BX段规

12、划，则有多种可选性： 仅修建“2”形公路。 2修隧道。以山脊为对称轴，对可修隧道点进行搜索，就可以从多个可 能的最短路中找出最优路径；至于最短路径的搜索，给出以下两种方法：4.1最短路法采用Dijkstra算法(见算法说明)与边界搜索相结合的方法求两点间的最短路 径。分两段进行搜索。4.1.1从起始点A到居民点B。从A到B经过一条溪流，要在溪流两岸的等高点处修建桥梁。由于溪流各 处的宽度不同，因此桥所在的位置不同，将导致桥和公路的长度同时变化，在这 种情况下，无法直接确定桥的最佳位置。Dijkstra算法用于搜索两固定点间的最 短路，在桥梁位置不确定的情况下，先将桥设在溪流上的任一位置，搜索到

13、桥在 这一位置时对应的最短路，改变桥的位置，即在溪流岸边进行遍历，每一位置都 对应着一条最短路，再找出所有最短路中最短的一条，得到段最佳路径。由图，可以观察出：谷底成一条直线，且山谷两岸的等高线关于谷底对称。 因此，我们将溪流和溪流两岸都看作是关于谷底对称。所以，桥梁与谷底沿线是 垂直的。AB段的搜索步骤：a取P0是溪流西岸的一点；b找到P0关于谷底的对称点Q0；c用Dijkstra算法分别求出AP段、PQ0段和BQ0段的最短路distA,P, distB,Q0 , distP0,Q0;d dist0=distA,P0+distP0,Q0+distB,Q0;e对溪流西岸的另一点P1，用上述方法

14、的点的最短路dist1;f dist0=min(dist0,dist1)；g对溪流西岸的所有点，执行步骤e和f,最后得到的dist0为AB间的最短 路。4.1.2从居民点B到矿区X从等势图中可以看出，在居民点和矿区之间有一条东西走向的山脉，首先， 不考虑修隧道，在坡度0.125处修建“2”形路，用Djkstra算法可以在B点和 X点之间搜索到一条最短路；然后，考虑修建隧道，为保证隧道尽可能短，使隧 道方向与山脉走向垂直。用与1)中相同的方法遍历山脉两侧的点，找到一条最短 路。由4.1.1和4.1.2便可以得到从A经B到X的最佳路线。以上方法求最佳路 线可以先在400mX400m的网格中求得粗略

15、线路，然后进行优化，采用线形插值 法将网格细化为100mX 100m的细网格，得到精确线路。4.1.3 Dijkstra 算法说明：任意两顶点G中之间的径相距离为%= (Ax )2 + (Ay )2+ (&)21/2权值为w.ij300勺 /38 Ah/ d.ij;2000d., / 3500d.j1000d. j在匕匕间修建一般公路 修建，?”形路修建桥梁修建 300米的隧道修建 300米的隧道说明：P(i)表示start到i的最短距离，为0表示还没找出。V是边 的集合，W(i,j)是它的权start:起始点end:目标点图5算法流程图4.2 逐步逼近法这里给出另一种搜索公路线路的方法：首先

16、确定起点和终点，然后再以坡度 为约束条件，逐个确定线路经过的各点。若起点、终点连线上的点满足坡度条件， 则将此点定为新起点，否则，在邻边上寻找满足坡度条件的点。若所有邻边上都4.2.1算法说明:stepl: n=0,dist=0;step2:连接anA,与棱边交于点p；step3: a 为 anp 的坡度，若 a 0.125，dist=dist+distan,p , an=p , n=n+1;返回step2；否则，执行step4step4 :在邻近棱边以一定步长搜索与连线的坡度0.125的点，记为p ,p，P，。.为a p与a A的夹角，若p =min(p B p ) 01 n i n i n

17、i01 ndist=dist+distan,pi , an=pi, n=n+1;返回step2初始化（n=0）使得。1=0 123Noa AC邻近棱边P n* 1 寸1 a | v. u格lieYes-。项皂选择最接近 目标点的点走“之字形路 得P点YeS 1m|n=n+1a =P图7逐步逼近算法流程在400mX400m的网格中，用逐步逼近法得到最佳线路的各点数据如下:5、模型求解：5.1 方案一：Dijkstra 算法5.1.1当网格为400mX400m时，其最短路径如下（不开隧道）表1： Dijkstra算法执行结果X坐标y坐标X坐标y坐标X坐标y坐标0800240040040002000

18、400400280080036002400800032001200320028001200036001600280032001600040002000240036002000020004000公路长：13697米；桥长：95米；总价为:429.9万。如修隧道，结果为：公 路长：1406米；桥长：95米；隧道长：300米；总价：485.8万；（隧道位置为(4000, 2800)(4000, 3100)之间的一段)。结果比不开隧道大很多。因 此，以后均不考虑修隧道。5.1.2细化为200X200后，结果为：通过居民区的(3600, 2000)点，桥的 位置为：(2900, 1800)至(3000,

19、 1900)的一段。公路长：12083米；桥长： 73米；价格：375.8万。图8: Dijkstra路径可视化5.2方案二：逐步逼近算法表2：根据逐步逼近算法，可求得下表:&W&W&W&W0.00800.003200.001808.764400.002893.504600.003043.10400.00639.603600.001748.304580.002884.504400.003059.80800.00474.504000.002000.004400.002923.504573.003074.251200.00419.804154.002400.004532.002934.504400

20、.003080.001600.00419.804296.002800.004400.002945.504400.003296.742000.00486.904400.002838.714520.002955.504000.003381.202400.00668.204525.002823.934390.002963.503600.003496.002800.00999.004400.002860.044586.002981.603262.003600.003053.321201.814500.002857.834404.002997.902800.003747.603097.501642.30

21、4400.002876.854573.003012.002400.003866.003146.611720.464500.002880.264400.003026.402000.004000.00E吕rA1214x (*400 m)相关参数为：公路的总长度为1.08672万米，桥梁长93.86米，隧道长 217.94米,总成本377.479万元。注意居民点（4000，2000）到隧道南边（4400，3080）的公路。由于等高线 过于密集，坡度过于陡峭，故修了较多的“2”形路。考虑到实际公路不应过于曲折，改进如下：表3：逐步逼近路径节点表WWW0.00800.003053.321201.8144

22、00.003080.00400.00639.603097.501642.304400.003296.74800.00474.503146.611720.464000.003381.201200.00419.803200.001808.763600.003496.001600.00419.803600.001748.303262.003600.002000.00486.904000.002000.002800.003747.602400.00668.204053.132800.002400.003866.002800.00999.005296.332844.872000.004000.00相关参

23、数为：公路的总长度为1.0714万米，桥梁长93.86米，隧道长217.94 米，总成本372.889万元。024101268x (*400 m)6 SOOKH14图10逐步逼近隧道路径可视化六、模型的评价6.1模型的优点：（1）本文用动态规划思想，化整为零，使模型简化，便于更大程度的推广。（2）目标明确，有确定的目标函数和问题的分析方向。（3）寻找最优路段有两种方法，它们各具特色。方案一适用于精确定线，方 案二利用逐渐逼近思想，需求近似最优解，虽然没有方案一精确，但是 花费时间段，速度快。（4）三维立体图形与等势图使得模型更加直观，可视化，这也是本文的一大 特点。6.2模型的缺点：（1）没有

24、考虑分岔路，或许在适当的位置建分岔路还可以大大降低成本。（2）网络没有进一步细化，细化后可能会更加精确。6.3模型的改进：（1）进一步考虑分岔路，降低成本。（2）桥梁，隧道候选点的选定比较粗疏，进一步可以建立方程，求取最优点。（3）进一步进行网络优化，缩小范围，求取最优近似解。6.4模型的误差分析：（1）网络没有进一步细化，因此软件编程运行结果存在一定的误差。（2）模型本身建立的不是非常完善，存在一定的误差。6.5模型灵敏度分析：对于模型的灵敏度我们首先看到两种方法的误差在110万元以上，尤其是在 开隧道时，这是可以接受的。在网络的细分中我们看到最后细分为200X200， 这在很大程度上已经是

25、比较精确的了。七、参考文献1施光燕，董加礼编最优化方法高等教育出版社1999.9 周义仓，阮晓青编数学建模引论高等教育出版社 2005.73 李学文，王宏洲编数学建模优秀论文 清华大学出版社2011.94 马莉编MATLAB数学实验与建模清华大学出版社2010.15 周义仓，赫孝良数学建模实验 西安交通大学出版社2001.16 王素丽，高洁，孙新德MATLAB混合编程与工程应用清华大学出版社2008.5附录A:（源代码）插值拟合编程：Dodof400.j,400.i=Ai+1,j+1,i,1,12,j,o,14;Dof0.,400.i=Ai+1,1,i,o,12;Dof400.i,0.=A1,

26、i+1,i,0,14;funx_,y_:=Sumf1.x,400.j1j,y,j,o,12/;Modx,400=0;1j_,y_：=(y-400.(j-1)/(400.j-400.(j-1)/;400(j-1)=y=400j&j! =0;1j_,y_：=(y-400.(j+1)/(400.j-400.(j+1)/;400j=y=400(j+1)&j! =12; 1j_,y_：=0/；! (400(j-1)=y=400(j+1)&0=y=4800;funx_,y_:=Sumf400.i,1.y1i,x,i,0,14/;Mody,400=0;1I_,x_:=(x-400.(i-1)/(400.i-

27、400.(i-1)/;400(i-1)=x=400i&i! =0;1I_,x_:=(x-400.(i+1)/(400.i-400.(i+1)/;400 i=x=400(i+1)&i! =14;1I_,x_:=0/;! (400(i-1)=x=400(i+1)&0=x=5600;funx_,y_:=Sumfun400.i,1.y1I,x,i,0.14地貌代码：x=0:400:5600;y=0:400:4800;x,y=meshgrid(x,y);z=370 470 550 600 670 690 670 620 580 450 400 300 100 150 250;.510 620 730 8

28、00 850 870 850 780 720 650 500 200 300 350 320;.650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 350;.740 880 1080 1130 12501280 1230 1040 900 500 700 780 750 650550;.830 980 1180 1320 14501420 1400 1300 700 900 850 840 380 780750;.880 1060 1230 1390 15001500 1400 900 1100 1060 950 870 900

29、 930950;.910 1090 1270 1500 12001100 1350 1450 1200 1150 1010 880 100010501100;.950 1190 1370 1500 12001100 1550 1600 1550 1380 1070 900 105011501200;.1430 1450 1460 150015501600 1550 1600 1600 1600 1550 1500150015501500;.1420 1430 1450 1480 1500 1550 1510 1430 1300 1200 980 850 750 550500;.1380 141

30、0 1430 1450 1470 1320 1280 1200 1080 940 780 620 460 370350;.1370 1390 1410 1430 1440 1140 1110 1050 950 820 690 540 380 300 210;.1350 1370 1390 1400 1410 960 940 880 800 690 570 430 290 210 150; mesh(x,y,z)等势线代码：x=0:400:5600;y=0:400:4800;x,y=meshgrid(x,y);z=370 470 550 600 670 690 670 620 580 450 4

31、00 300 100 150 250;.510 620 730 800 850 870 850 780 720 650 500 200 300 350 320;.650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 350;.740 880 1080 1130 1250 1280 1230 1040 900 500 700 780 750 650550;.830 980 1180 1320 1450 1420 1400 1300 700 900 850 840 380 780750;.880 1060 1230 1390 1500

32、 1500 1400 900 1100 1060 950 870 900 930950;.910 1090 1270 1500 1200 1100 1350 1450 1200 1150 1010 880 100010501100;.950 1190 1370 1500 1200 1100 1550 1600 1550 1380 1070 900 105011501200;.1430 1450 1460 15001550 1600 1550 1600 1600 1600 15501500 150015501500;.1420 1430 1450 1480 1500 1550 1510 1430

33、 1300 1200 980 850 750 550500;.1380 1410 1430 1450 1470 1320 1280 1200 1080 940 780 620 460 370350;.1370 1390 1410 1430 1440 1140 1110 1050 950 820 690 540 380 300 210;.1350 1370 1390 1400 1410 960 940 880 800 690 570 430 290 210 150; contour(x,y,z,20);hold ongtext(terminal)gtext(mountain)gtext(brid

34、ge)gtext(residence)gtext(lake)gtext(start)gtext(river)x=linspace(2400,4800);y=4800-x;plot(x,y)附录B:（原始数据）（y轴正向为北）48001350137013901400141096094088080069057043029021015044001370139014101430144011401110105095082069054038030021040001380141014301450147013201280120010809407806204603703503600142014301450148

35、015001550151014301300120098085075055050032001430145014601500155016001550160016001600155015001500155015002800895011901370150012001100155016001550138010709001050115012002400910109012701500120011001350145012001150101088010001050110020008801060123013901500150014009001100106095087090093095016008309801180

36、1320145014201400130070090085084038078075012007408801080113012501280123010409005007007807506505508006507608809701020105010208308007003005005504803504005106207308008508708507807206505002003003503200370470550600670690670620580450400300100150250y/x0400800120016002000240028003200360040004400480052005600工

37、程种类一般路段桥梁隧道工程成本（元/米）30020001500（长度300 米）;3000（长度300 米）对坡度a的限制a 0.125a =0a 0.100200*200的路径xyxyxy0.000000800.0000002200.000000800.0000003800.0000002200.000000200.0000001000.0000002400.000000800.0000003600.0000002400.000000400.0000001200.0000002600.0000001000.0000003400.0000002600.000000600.0000001200.

38、0000002800.0000001200.0000003200.0000002800.000000800.0000001000.0000003000.0000001400.0000003000.0000003000.0000001000.000000800.0000003000.0000001600.0000002800.0000003200.0000001200.000000800.0000003200.0000001800.0000002600.0000003400.0000001400.000000800.0000003400.0000001800.0000002400.0000003600.0000001600.000000800.0000003600.0000001600.0000002200.0000003800.0000001800.000000800.0000003800.0000001800.0000002000.0000004000.0000002000.000000800.0000004000.0000002000.00000019