数学实验论文

1、 数学实验论文 逢山开路 队员 姓 名 学 号 1 2 3 逢山开路摘 要本文针对逢山开路的问题，主要运用了局部优化的原理，并根据这个原理提出对山区的具体情形设置控制点的方法，并利用matlab、photoshop等软件进行计算并绘制图形，对一般路线运用两个模型对比，最后在综合考虑修桥和隧道的费用，从而得出全局最小费用路线。对于问题1，其本质是在山区修建公路的路线选择问题，题中给出了实际的基本特征，如地貌、路线、环境等自然条件以及费用系数，重点是求两点间的最短路，由于要在河流上架桥和开挖隧道，直接求从山脚到居民点再到矿区的最小费用的路线是困难的。在这里我们采用一种较为简便的方法，先根据对地形和

2、不同路段费用系数的分析，确定桥头和隧道口的若干候选地点，然后寻求山脚到桥，桥到隧道，隧道到矿区的最短路，也是最小费用路径。对一般路线提出了两个模型，利用等高线决定最大坡度路线和在小方格内进行局部优化。同时我们在模型中大胆创新，在居民点东面设置了一个分叉，分别通往桥西头和隧道南口，对一般路线虽然是局部优化，但总的成本只有370万元，最终结果较为合理。对于问题2，和问题1的唯一不同之处只是将原来的居民点改为了居民区，我们只需要在居民区上找到一个合适的点，然后我们可以改进问题1中的模型，便能找出一条较为理想的路线。关键词：局部优化 分叉道路 最短路径1、 问题重述要在一山区修建公路，已经知道一些地点

3、的高程。数据显示：在y=3200处有一东西走向的山峰；从坐标（2400,2400）到(4800,0)有一西北一东南走向的山谷，在（2000,2800）附近有一山口湖，其最高水位略高于1350米，雨季在山谷中形成一溪流。经调查知，雨最最大时溪流水面宽度w与（溪流最深处的）x坐标的关系可近似表示为（2400x4000）。公路从山脚（0,800）处开始，经居民点（4000,2000）至矿区（2000,4000）。已知路段工程成本及对路段坡度a（上升高程与水平距离之比）的限制如附表2.2。（1）试给出一种线路设计方案，包括原理、方法及比较精确的线路位置（含桥梁、隧道），并估算该方案的总成本。（2）如果

4、居民点改为3600x4000,2000y2400的居民区，公路只须经过居民区即可，那么你的方案有什么改变。附表2.2工程种类一般路段桥梁隧道工程成本（元/米）30020001500（长度300米）；3000（长度>300米）对坡度a的限制a<0.125a=0a<0.1002、 符号系统与模型假设2.1 符号系统:表示从A到B的公路R()：所有从A到B的可行路线的集合Cost（）：建造公路的成本Length（）：公路的长度=一般公路，=桥梁，=长度小于等于300m的隧道，=长度大于300m的隧道：对的倾斜度限制P（）：对的单位距离工程成本2.2模型假设1. 地貌假设：假设题目提

5、供的数据是精确和充分的。在四个相邻数据点之间的单位矩形内没有太大起伏，如果两条对角线两端数据的均值的差远小于矩形边长，则可以近视的认为该矩形面没有太大的起伏。2. 路线假设：a 只考虑公路为几何线而不计其宽度，忽略横向的坡度对宽度的影响，b 设计路线时，暂不考虑路线的急转弯角度的限制c 不考虑地质情况和气候条件的影响3环境假设：a假设该地区内无原公路可利用b新修公路应限于所给区域内3、 问题1的分析、建模与求解.1 问题的分析我们可以将整个路段进行分段讨论，首先可以在整条路上去几个控制点，设定，与的具体路线无关。控制点的选择是根据情况分析得到的。对本题中，考虑到桥梁的隧道的成本高于一般公路因此

6、在线路设计时为了节约成本而让一般公路多绕几个弯。 图表1图表2利用MATLAB软件，我们可以画成等势图和三维视图，可以看出：1.从起点到居民点必须经过一条小山谷，雨季会形成溪流2.从居民点到矿区，有一山峰阻挡，且高度很高，坡度很陡。因此我们选择控制点：起始点（0,800）:峡谷西岸（待定）峡谷东岸（待定）:居民点（4000,2000）:山峰南侧（待定）:山峰北侧（待定）其余道路都是一般公路对于第二个问题，改成待定，在范围内，且. 模型的建立模型一利用matlab软件可做出，山地等势图如下：从等势图上可以看出，两点间的坡度为高度差除以两点之间的水平距离。设起始点高，等高线的高度差是。若以起始点为

7、中心，为半径作圆弧，交对应的等高线A,B两点，从起始点到弧上任意点的坡度陡小于规定坡度。可从这些点中选取某点为第一步的终点，例如想尽量爬高时选的点。 图表3模型二道路的选择（一般公路）1 两个控制点之间，如何选择合适的道路使长度短而坡度又满足要求，是决定成本的重要条件看，也就是怎样实现区分优化，我选择了逐步定线的方法，原理和模型一有相似处。先将成若干段，是位于某个矩形边上的点，同是直线段，坡度小于或等于的最大值且尽可能的向的直线方向靠 图表4当时，取为当时，再在附近棱上找找一点，使对的坡度正好为0.125，且与的角度偏差最小。设（）,()为靠近的一条棱，且这两个点中对应的一个坡度大于0.125

8、，一个0.125，那么可以知道该棱上必可找到坡度等于0,。125的点，设该点（）不妨设=由方程：决定，是（）,()点的高度，z是点的高度主要考虑到上坡和下坡问题易知这样的解是存在的，利用这个解求出即使,依次进行下去逐步接近,一般情况下，这样的路线是最优的.山谷溪流的处理和桥梁从图中可以看出谷底是直线的，谷的两侧基本也是对称的，可以由此计算出雨量最大的液面界限谷底方程：西岸方程：东岸方程：其中：由于桥的成本与一般公路的成本相比较高，所以建桥最好使桥正好跨在两岸的界限上，同时要顾及桥两端的高度相等。3. 隧道位置的选择：由于隧道的成本很高，且长度超过300m后成本增长一倍，因此最好能选择长度小于3

9、00米的隧道，从等势图上可以看出线x=4400处的山峰特别尖，在这里修隧道可能实现这一点，因此以下计算中固定隧道位置的横坐标x=4400想让隧道的长度小于300m，需要将路修到一定的高度。对水平隧道即使有坡度，隧道高度也不能低于1240m。对于矿区，高度1320m可以实现这一点，对于居民区，高度950m上升到这个高度有点困难，本模型采用了迂回绕道的方法达到爬高的目的。显然这样做省下的隧道成本大于多修公路的成本。. 问题1的求解与结果分析算法说明step1: n=0,dist=0;step2: 连接anA,与棱边交于点p；step3: 为anp的坡度若0.125 dist=dist+distan

10、,p , an=p , n=n+1; 返回step2；否则，执行step4step4：在邻近棱边以一定步长搜索与连线的坡度0.125的点，记为p0,p1,pn， i为anpi与anA的夹角，若i=min(01n) dist=dist+distan,pi , an=pi , n=n+1; 返回step2图表5在400m×400m的网格中，用逐步逼近法得到最佳线路的各点数据如下：根据逐步逼近算法，可求得下表：xyxyxyxy0.00800.003200.001808.764400.002893.504600.003043.10400.00639.603600.001748.304580.

11、002884.504400.003059.80800.00474.504000.002000.004400.002923.504573.003074.251200.00419.804154.002400.004532.002934.504400.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.00280

12、0.00999.004400.002860.044586.002981.603262.003600.003053.321201.814500.002857.834404.002997.902800.003747.603097.501642.304400.002876.854573.003012.002400.003866.003146.611720.464500.002880.264400.003026.402000.004000.00图表6 路径节点表相关参数为： 公路的总长度为1.08672万米， 桥梁长93.86米, 隧道长217.94米,总成本377.479万元。路径可视化如下：图表7

13、 对于模型一Dijkstra算法说明：任意两顶点V i , V j 之间的径相距离为dij= 2 21/2权值为 我们可利用计算出：总路线长为10.802km，总费用为426.60万元 。四、问题2的分析、建模与求解.1 问题2的分析与建模问题二中居民点，由原来的一个点改为了一个区域，因此我们可以改进模型二后得到模型三，仍采用局部优化逐步定线的方法。在河谷和山脊附近的地貌假设不合理，如这个区域四个顶点高度分别为1300,700,1040,900,则（1300+900）/2-（1040+700）/2=230,对这么大的差值仍将该矩阵视为平面，显然不太合理。考虑到实际情况，可以将这类矩形近似两个三

14、角平面，其公共边是一条凸出或者下陷的线。这要通过三维视图判断哪条对角线是公共边。根据这一假设，公路到了彼岸的高度后，还要经过下降的破才能到桥边，因此公路过桥前还要沿河边走一段路才行。从居民点到隧道的爬高过程仍是一个难题，考虑按上一假设计算，桥东头到居民点的路上的有些点也很高，我们可以这样处理：假如公路允许分叉的话，我们可以在桥东侧到居民点某处再取一个控制点,将原来的一条道改成叉道，这样一方面减低公路总长，宁一方面可以降低迂回绕道的次数和角度。为了得到精确的结果，我们通过用Mathematica软件逐点计算得到的结果【1】画出可视化图形来解决问题。图表8.2 问题2的求解与结果分析路径的总长度：

15、10.72273km总费用：3557.4941km桥梁位置：（2677.56，2089.033）（2710.96，2122.45）桥长：47，24m桥费用：94489元隧道位置：（4400，3080）（4400，3296.74）隧道长度：217.12m隧道造价：325525元 对于问题2，相当于把控制点改为可变，其位置由（4000，2000）改为3600x4000,2000y2400.我们在区域里取了几个点进行计算。这里我们分别取（3600，2000）和（3600，2400）结果为：总路径长为10.1315km，修路总费用338.024万元，Cost=3380.24万元。：总路径长为10.09

16、95km，修路总费用337.054万元，Cost=3370.24万元。，而，可知居民点的变化对总成本的影响不大。五、参考文献【1】作者：陈连飞 林涛 兰嵩 资源标题：逢山开路模型，网址：，访问时间（2010年12月10日）。【2】施光燕，董加礼编 最优化方法 高等教育出版社 1999.9六、附录1、图表1、2的Matlab程序x=0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800 5200 5600y=0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800xx,y

17、y=meshgrid(x,y); zz=370 470 550 600 670 690 670 620 850 450 400 300 100 150 250510 620 730 800 850 870 850 780 720 650 500 200 300 350 320650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 350740 880 1080 1130 1250 1280 1230 1040 900 500 700 780 750 650 550830 980 1180 1320 1450 1420 1400 13

18、00 700 900 850 840 380 780 750880 1060 1230 1390 1500 1500 1400 900 1100 1060 950 870 900 930 950910 1090 1270 1500 1200 1100 1350 1450 1200 1150 1010 880 1000 1050 1100950 1190 1370 1500 1200 1100 1550 1600 1550 1380 1070 900 1050 1150 12001430 1450 1460 1500 1550 1600 1600 1550 1600 1600 1550 1500

19、 1500 1550 15501420 1430 1450 1480 1500 1550 1510 1430 1300 120 980 850 750 880 5001380 1410 1430 1450 1470 1320 1280 1200 1080 940 780 620 460 370 3501370 1390 1410 1430 1440 1140 1110 1050 950 820 690 540 380 300 2101350 1370 1390 1400 1410 960 940 880 800 690 570 430 290 210 150surf(xx,yy,zz);hol

20、d on;c,h=contour(xx,yy,zz,12);clabel(c,h)2、图表3的Matlab程序x=0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800 5200 5600 y=0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800 xx,yy=meshgrid(x,y); zz=370 470 550 600 670 690 670 620 850 450 400 300 100 150 250510 620 730 800 850 870 850

21、780 720 650 500 200 300 350 320650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 350740 880 1080 1130 1250 1280 1230 1040 900 500 700 780 750 650 550830 980 1180 1320 1450 1420 1400 1300 700 900 850 840 380 780 750880 1060 1230 1390 1500 1500 1400 900 1100 1060 950 870 900 930 950910 1090 1

22、270 1500 1200 1100 1350 1450 1200 1150 1010 880 1000 1050 1100950 1190 1370 1500 1200 1100 1550 1600 1550 1380 1070 900 1050 1150 12001430 1450 1460 1500 1550 1600 1600 1550 1600 1600 1550 1500 1500 1550 15501420 1430 1450 1480 1500 1550 1510 1430 1300 120 980 850 750 880 5001380 1410 1430 1450 1470

23、 1320 1280 1200 1080 940 780 620 460 370 3501370 1390 1410 1430 1440 1140 1110 1050 950 820 690 540 380 300 2101350 1370 1390 1400 1410 960 940 880 800 690 570 430 290 210 150 surf(xx,yy,zz); hold on; c,h=contour(xx,yy,zz,12); clabel(c,h)hold onx=0 400 800 1200 1600 2000 2400 2479 2788 2800 3017.7 2

24、925.4 2800 2677.6 2677.6 2711 2800 3100 3200 3325 3600 4000 3600 3325 3527.4 3200 3457.2 3600 3786.8 4000 4400 4400 4000 3600 3200 3138.5 2800 2400 2000y=800 639.6 474.6 419.8 419.8 486.9 666 800 1200 1212 1382 1600 1819.7 2000 2089 2122.5 2109.1 2000 1950 1875 1857.7 2000 1857.7 1875 2000 2033.6 24

25、00 2465.2 2806 2966.6 3080.8 3296.7 3345.4 3457.2 3561.2 3600 3930.4 3965.2 4000plot(x,y,'linewidth',5)3、 图表7的Matlab程序x=0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800 5200 5600 y=0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800 xx,yy=meshgrid(x,y); zz=370 470 550 600

26、670 690 670 620 850 450 400 300 100 150 250510 620 730 800 850 870 850 780 720 650 500 200 300 350 320650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 350740 880 1080 1130 1250 1280 1230 1040 900 500 700 780 750 650 550830 980 1180 1320 1450 1420 1400 1300 700 900 850 840 380 780 750880 10

27、60 1230 1390 1500 1500 1400 900 1100 1060 950 870 900 930 950910 1090 1270 1500 1200 1100 1350 1450 1200 1150 1010 880 1000 1050 1100950 1190 1370 1500 1200 1100 1550 1600 1550 1380 1070 900 1050 1150 12001430 1450 1460 1500 1550 1600 1600 1550 1600 1600 1550 1500 1500 1550 15501420 1430 1450 1480 1

28、500 1550 1510 1430 1300 120 980 850 750 880 5001380 1410 1430 1450 1470 1320 1280 1200 1080 940 780 620 460 370 3501370 1390 1410 1430 1440 1140 1110 1050 950 820 690 540 380 300 2101350 1370 1390 1400 1410 960 940 880 800 690 570 430 290 210 150 surf(xx,yy,zz); hold on; c,h=contour(xx,yy,zz,12); cl

29、abel(c,h)hold onx=0 400 800 1200 1600 2000 2400 2800 3053.32 3097.5 3146.61 3200 3600 4000 4154 4296 4400 4525 4400 4500 4400 4500 4400 4580 4400 4532 4400 4520 4390 4586 4404 4573 4400 4600 4400 4573 4400 4400 4000 3600 3262 2800 2400 2000y=800 639.6 474.6 419.8 419.8 486.9 668.2 999 1201.8 1642 17

30、20.5 1808.8 1748.3 2000 2400 2800 2838.7 2824 2860 2857.8 2876.8 2880 2893.5 2884.5 2923.5 2934.5 2945.5 2955.5 2963.5 2981.5 2997.9 3012 3026.4 3043 3059.8 3074.25 3080 3296.74 3381.2 3496 3600 3747.6 3866 4000plot(x,y,'linewidth',5)4、图表8的Matlab程序x=0 400 800 1200 1600 2000 2400 2800 3200 36

31、00 4000 4400 4800 5200 5600 y=0 400 800 1200 1600 2000 2400 2800 3200 3600 4000 4400 4800 xx,yy=meshgrid(x,y); zz=370 470 550 600 670 690 670 620 850 450 400 300 100 150 250510 620 730 800 850 870 850 780 720 650 500 200 300 350 320650 760 880 970 1020 1050 1020 830 800 700 300 500 550 480 350740 88

32、0 1080 1130 1250 1280 1230 1040 900 500 700 780 750 650 550830 980 1180 1320 1450 1420 1400 1300 700 900 850 840 380 780 750880 1060 1230 1390 1500 1500 1400 900 1100 1060 950 870 900 930 950910 1090 1270 1500 1200 1100 1350 1450 1200 1150 1010 880 1000 1050 1100950 1190 1370 1500 1200 1100 1550 1600 1550 1380 1070 900 1050 1150 1200