數(shù)學(xué)實(shí)驗(yàn)論文

1、 數(shù)學(xué)實(shí)驗(yàn)論文 逢山開路 隊(duì)員 姓 名 學(xué) 號 1 2 3 逢山開路摘 要本文針對逢山開路的問題，主要運(yùn)用了局部優(yōu)化的原理，并根據(jù)這個原理提出對山區(qū)的具體情形設(shè)置控制點(diǎn)的方法，并利用matlab、photoshop等軟件進(jìn)行計(jì)算并繪制圖形，對一般路線運(yùn)用兩個模型對比，最后在綜合考慮修橋和隧道的費(fèi)用，從而得出全局最小費(fèi)用路線。對于問題1，其本質(zhì)是在山區(qū)修建公路的路線選擇問題，題中給出了實(shí)際的基本特征，如地貌、路線、環(huán)境等自然條件以及費(fèi)用系數(shù)，重點(diǎn)是求兩點(diǎn)間的最短路，由于要在河流上架橋和開挖隧道，直接求從山腳到居民點(diǎn)再到礦區(qū)的最小費(fèi)用的路線是困難的。在這里我們采用一種較為簡便的方法，先根據(jù)對地形和

2、不同路段費(fèi)用系數(shù)的分析，確定橋頭和隧道口的若干候選地點(diǎn)，然后尋求山腳到橋，橋到隧道，隧道到礦區(qū)的最短路，也是最小費(fèi)用路徑。對一般路線提出了兩個模型，利用等高線決定最大坡度路線和在小方格內(nèi)進(jìn)行局部優(yōu)化。同時我們在模型中大膽創(chuàng)新，在居民點(diǎn)東面設(shè)置了一個分叉，分別通往橋西頭和隧道南口，對一般路線雖然是局部優(yōu)化，但總的成本只有370萬元，最終結(jié)果較為合理。對于問題2，和問題1的唯一不同之處只是將原來的居民點(diǎn)改為了居民區(qū)，我們只需要在居民區(qū)上找到一個合適的點(diǎn)，然后我們可以改進(jìn)問題1中的模型，便能找出一條較為理想的路線。關(guān)鍵詞：局部優(yōu)化 分叉道路 最短路徑1、 問題重述要在一山區(qū)修建公路，已經(jīng)知道一些地點(diǎn)

3、的高程。數(shù)據(jù)顯示：在y=3200處有一東西走向的山峰；從坐標(biāo)（2400,2400）到(4800,0)有一西北一東南走向的山谷，在（2000,2800）附近有一山口湖，其最高水位略高于1350米，雨季在山谷中形成一溪流。經(jīng)調(diào)查知，雨最最大時溪流水面寬度w與（溪流最深處的）x坐標(biāo)的關(guān)系可近似表示為（2400x4000）。公路從山腳（0,800）處開始，經(jīng)居民點(diǎn)（4000,2000）至礦區(qū)（2000,4000）。已知路段工程成本及對路段坡度a（上升高程與水平距離之比）的限制如附表2.2。（1）試給出一種線路設(shè)計(jì)方案，包括原理、方法及比較精確的線路位置（含橋梁、隧道），并估算該方案的總成本。（2）如果

4、居民點(diǎn)改為3600x4000,2000y2400的居民區(qū)，公路只須經(jīng)過居民區(qū)即可，那么你的方案有什么改變。附表2.2工程種類一般路段橋梁隧道工程成本（元/米）30020001500（長度300米）；3000（長度>300米）對坡度a的限制a<0.125a=0a<0.1002、 符號系統(tǒng)與模型假設(shè)2.1 符號系統(tǒng):表示從A到B的公路R()：所有從A到B的可行路線的集合Cost（）：建造公路的成本Length（）：公路的長度=一般公路，=橋梁，=長度小于等于300m的隧道，=長度大于300m的隧道：對的傾斜度限制P（）：對的單位距離工程成本2.2模型假設(shè)1. 地貌假設(shè)：假設(shè)題目提

5、供的數(shù)據(jù)是精確和充分的。在四個相鄰數(shù)據(jù)點(diǎn)之間的單位矩形內(nèi)沒有太大起伏，如果兩條對角線兩端數(shù)據(jù)的均值的差遠(yuǎn)小于矩形邊長，則可以近視的認(rèn)為該矩形面沒有太大的起伏。2. 路線假設(shè)：a 只考慮公路為幾何線而不計(jì)其寬度，忽略橫向的坡度對寬度的影響，b 設(shè)計(jì)路線時，暫不考慮路線的急轉(zhuǎn)彎角度的限制c 不考慮地質(zhì)情況和氣候條件的影響3環(huán)境假設(shè)：a假設(shè)該地區(qū)內(nèi)無原公路可利用b新修公路應(yīng)限于所給區(qū)域內(nèi)3、 問題1的分析、建模與求解.1 問題的分析我們可以將整個路段進(jìn)行分段討論，首先可以在整條路上去幾個控制點(diǎn)，設(shè)定，與的具體路線無關(guān)?？刂泣c(diǎn)的選擇是根據(jù)情況分析得到的。對本題中，考慮到橋梁的隧道的成本高于一般公路因此

6、在線路設(shè)計(jì)時為了節(jié)約成本而讓一般公路多繞幾個彎。 圖表1圖表2利用MATLAB軟件，我們可以畫成等勢圖和三維視圖，可以看出：1.從起點(diǎn)到居民點(diǎn)必須經(jīng)過一條小山谷，雨季會形成溪流2.從居民點(diǎn)到礦區(qū)，有一山峰阻擋，且高度很高，坡度很陡。因此我們選擇控制點(diǎn)：起始點(diǎn)（0,800）:峽谷西岸（待定）峽谷東岸（待定）:居民點(diǎn)（4000,2000）:山峰南側(cè)（待定）:山峰北側(cè)（待定）其余道路都是一般公路對于第二個問題，改成待定，在范圍內(nèi)，且. 模型的建立模型一利用matlab軟件可做出，山地等勢圖如下：從等勢圖上可以看出，兩點(diǎn)間的坡度為高度差除以兩點(diǎn)之間的水平距離。設(shè)起始點(diǎn)高，等高線的高度差是。若以起始點(diǎn)為

7、中心，為半徑作圓弧，交對應(yīng)的等高線A,B兩點(diǎn)，從起始點(diǎn)到弧上任意點(diǎn)的坡度陡小于規(guī)定坡度?？蓮倪@些點(diǎn)中選取某點(diǎn)為第一步的終點(diǎn)，例如想盡量爬高時選的點(diǎn)。 圖表3模型二道路的選擇（一般公路）1 兩個控制點(diǎn)之間，如何選擇合適的道路使長度短而坡度又滿足要求，是決定成本的重要條件看，也就是怎樣實(shí)現(xiàn)區(qū)分優(yōu)化，我選擇了逐步定線的方法，原理和模型一有相似處。先將成若干段，是位于某個矩形邊上的點(diǎn)，同是直線段，坡度小于或等于的最大值且盡可能的向的直線方向靠 圖表4當(dāng)時，取為當(dāng)時，再在附近棱上找找一點(diǎn)，使對的坡度正好為0.125，且與的角度偏差最小。設(shè)（）,()為靠近的一條棱，且這兩個點(diǎn)中對應(yīng)的一個坡度大于0.125

8、，一個0.125，那么可以知道該棱上必可找到坡度等于0,。125的點(diǎn)，設(shè)該點(diǎn)（）不妨設(shè)=由方程：決定，是（）,()點(diǎn)的高度，z是點(diǎn)的高度主要考慮到上坡和下坡問題易知這樣的解是存在的，利用這個解求出即使,依次進(jìn)行下去逐步接近,一般情況下，這樣的路線是最優(yōu)的.山谷溪流的處理和橋梁從圖中可以看出谷底是直線的，谷的兩側(cè)基本也是對稱的，可以由此計(jì)算出雨量最大的液面界限谷底方程：西岸方程：東岸方程：其中：由于橋的成本與一般公路的成本相比較高，所以建橋最好使橋正好跨在兩岸的界限上，同時要顧及橋兩端的高度相等。3. 隧道位置的選擇：由于隧道的成本很高，且長度超過300m后成本增長一倍，因此最好能選擇長度小于3

9、00米的隧道，從等勢圖上可以看出線x=4400處的山峰特別尖，在這里修隧道可能實(shí)現(xiàn)這一點(diǎn)，因此以下計(jì)算中固定隧道位置的橫坐標(biāo)x=4400想讓隧道的長度小于300m，需要將路修到一定的高度。對水平隧道即使有坡度，隧道高度也不能低于1240m。對于礦區(qū)，高度1320m可以實(shí)現(xiàn)這一點(diǎn)，對于居民區(qū)，高度950m上升到這個高度有點(diǎn)困難，本模型采用了迂回繞道的方法達(dá)到爬高的目的。顯然這樣做省下的隧道成本大于多修公路的成本。. 問題1的求解與結(jié)果分析算法說明step1: n=0,dist=0;step2: 連接anA,與棱邊交于點(diǎn)p；step3: 為anp的坡度若0.125 dist=dist+distan

10、,p , an=p , n=n+1; 返回step2；否則，執(zhí)行step4step4：在鄰近棱邊以一定步長搜索與連線的坡度0.125的點(diǎn)，記為p0,p1,pn， i為anpi與anA的夾角，若i=min(01n) dist=dist+distan,pi , an=pi , n=n+1; 返回step2圖表5在400m×400m的網(wǎng)格中，用逐步逼近法得到最佳線路的各點(diǎn)數(shù)據(jù)如下：根據(jù)逐步逼近算法，可求得下表：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 路徑節(jié)點(diǎn)表相關(guān)參數(shù)為： 公路的總長度為1.08672萬米， 橋梁長93.86米, 隧道長217.94米,總成本377.479萬元。路徑可視化如下：圖表7

13、 對于模型一Dijkstra算法說明：任意兩頂點(diǎn)V i , V j 之間的徑相距離為dij= 2 21/2權(quán)值為 我們可利用計(jì)算出：總路線長為10.802km，總費(fèi)用為426.60萬元 。四、問題2的分析、建模與求解.1 問題2的分析與建模問題二中居民點(diǎn)，由原來的一個點(diǎn)改為了一個區(qū)域，因此我們可以改進(jìn)模型二后得到模型三，仍采用局部優(yōu)化逐步定線的方法。在河谷和山脊附近的地貌假設(shè)不合理，如這個區(qū)域四個頂點(diǎn)高度分別為1300,700,1040,900,則（1300+900）/2-（1040+700）/2=230,對這么大的差值仍將該矩陣視為平面，顯然不太合理。考慮到實(shí)際情況，可以將這類矩形近似兩個三

14、角平面，其公共邊是一條凸出或者下陷的線。這要通過三維視圖判斷哪條對角線是公共邊。根據(jù)這一假設(shè)，公路到了彼岸的高度后，還要經(jīng)過下降的破才能到橋邊，因此公路過橋前還要沿河邊走一段路才行。從居民點(diǎn)到隧道的爬高過程仍是一個難題，考慮按上一假設(shè)計(jì)算，橋東頭到居民點(diǎn)的路上的有些點(diǎn)也很高，我們可以這樣處理：假如公路允許分叉的話，我們可以在橋東側(cè)到居民點(diǎn)某處再取一個控制點(diǎn),將原來的一條道改成叉道，這樣一方面減低公路總長，寧一方面可以降低迂回繞道的次數(shù)和角度。為了得到精確的結(jié)果，我們通過用Mathematica軟件逐點(diǎn)計(jì)算得到的結(jié)果【1】畫出可視化圖形來解決問題。圖表8.2 問題2的求解與結(jié)果分析路徑的總長度：

15、10.72273km總費(fèi)用：3557.4941km橋梁位置：（2677.56，2089.033）（2710.96，2122.45）橋長：47，24m橋費(fèi)用：94489元隧道位置：（4400，3080）（4400，3296.74）隧道長度：217.12m隧道造價：325525元 對于問題2，相當(dāng)于把控制點(diǎn)改為可變，其位置由（4000，2000）改為3600x4000,2000y2400.我們在區(qū)域里取了幾個點(diǎn)進(jìn)行計(jì)算。這里我們分別?。?600，2000）和（3600，2400）結(jié)果為：總路徑長為10.1315km，修路總費(fèi)用338.024萬元，Cost=3380.24萬元。：總路徑長為10.09

16、95km，修路總費(fèi)用337.054萬元，Cost=3370.24萬元。，而，可知居民點(diǎn)的變化對總成本的影響不大。五、參考文獻(xiàn)【1】作者：陳連飛 林濤 蘭嵩 資源標(biāo)題：逢山開路模型，網(wǎng)址：，訪問時間（2010年12月10日）?！?】施光燕，董加禮編 最優(yōu)化方法 高等教育出版社 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