1、華 北 科 技 學(xué) 院課程設(shè)計(jì)說明書班級(jí): 計(jì)算B101 姓名:顧亞楠（201009014110）成績(jī)：_班級(jí): 計(jì)算B101 姓名:孔維文（201009014119） 成績(jī)：_班級(jí): 計(jì)算B102 姓名:陳 灝（201009014214）成績(jī)：_設(shè)計(jì)題目: 逢山開路問題 設(shè)計(jì)時(shí)間: 十九周周四 至 二十周周一 指導(dǎo)教師: 李慧 評(píng) 語(yǔ):_ _評(píng)閱教師: _ 逢山開路問題 摘要：本文是逢山開路問題的研究，主要研究特定兩點(diǎn)之間的最短路，以及使得總成本最小。主要采用的方法是Dijkstra算法求兩點(diǎn)間的最短路徑，從而得到一條最優(yōu)的路線，再對(duì)其進(jìn)行細(xì)化獲得更加精確的路線。最后再進(jìn)行逐步定線，以局部最

2、優(yōu)為準(zhǔn)則，逐步逼近目標(biāo)點(diǎn)，得到較優(yōu)解。 由于在開路期間會(huì)遇到湖泊，山脈，山谷等問題，所以要進(jìn)行橋梁，隧道，一般路段的各種搭建與組合，在對(duì)這三種不同形式的選擇是，仔細(xì)劃分了三種形式在不同情況下應(yīng)該滿足的坡度條件，從而確定路徑的權(quán)值。 本問題保留了工程實(shí)際背景的一些基本特征,涉及到地貌環(huán)境等自然條件以及施工能力,費(fèi)用系數(shù)等人為因素,這些在實(shí)際的工程設(shè)計(jì)上必須考慮的重要因素我們?cè)诮鉀Q本題時(shí)則須注意取舍,在用數(shù)學(xué)模型解題時(shí),除了從數(shù)學(xué)角度上思考之外,適當(dāng)?shù)目紤]有關(guān)實(shí)際因素,從總體上設(shè)計(jì),這對(duì)于我們建立合理的數(shù)學(xué)模型提供了重要的依據(jù),也會(huì)使我們得到的方案行之有效,本題在這方面表現(xiàn)得很明顯 通過分析我們得

3、出比較滿意的結(jié)果，橋長(zhǎng)：73米，位置為：（2900，1800）至（3000，1900）之間的一段，隧道長(zhǎng)：300米，位置為（4000，2800）至（4000，3100）之間的一段，公路長(zhǎng)：12083米，得出最優(yōu)的解價(jià)格：375.8萬(wàn)。 關(guān)鍵詞：Dijkstra算法 目標(biāo)最優(yōu)化模型 逐步逼近 動(dòng)態(tài)規(guī)劃 一、問題重述 公路的修建是近幾年我們國(guó)家不斷進(jìn)行實(shí)施的工程，尤其在某些偏遠(yuǎn)地區(qū)，由于地理?xiàng)l件的影響，實(shí)施起來難度可能會(huì)很大，并且花費(fèi)大量的資金。就目前的情況來看，我國(guó)路段形式主要有三種：一般公路，隧道，橋梁。當(dāng)我們要為某地區(qū)修路時(shí)，可能會(huì)遇到湖泊，山脈，山谷，在這種情況下，顯然用一種形式是不能解決

4、的，要對(duì)其進(jìn)行組合。這時(shí)實(shí)施人員不僅僅要考慮資金問題，而且還要聯(lián)系實(shí)際。 我們通常會(huì)有一種想法：遇到湖泊繞道而走，遇到山谷搭建橋梁，遇到山峰就挖隧道。但實(shí)際情況不是這樣的，根據(jù)實(shí)際情況要考慮坡度的問題，由于三種形式所用到的資金差距較大，因此要進(jìn)行計(jì)算得出最優(yōu)路線，從而使所用到的資金最小。也就是用最少的資金，達(dá)到實(shí)際的目標(biāo)。 本問題要求是：要在一山區(qū)修建公路,首先測(cè)得一些地點(diǎn)的高程,數(shù)據(jù)見附錄B(平面區(qū)域0x5600,0y4800表中數(shù)據(jù)為坐標(biāo)點(diǎn)的高程,單位:米). 數(shù)據(jù)顯示:在y=3200處有一東西走向的山峰;從坐標(biāo)(2400,2400)到(4800,0)有一西北東南走向的山谷;在(2000，

5、2800)附近有一山口湖,其最高水位略高于1350米,雨季在山谷中形成一溪流,經(jīng)調(diào)查知,雨量最大時(shí)溪流最高水面寬度W與(溪流最深處的)x坐標(biāo)的關(guān)系可近似表示為 (2400x4000)公路從山腳(0,800)處開始,經(jīng)居民點(diǎn)(4000,2000)至礦區(qū)(2000,4000),已知路段工程成本及對(duì)路段坡度(上升高程與水平距離之比)的限制見附錄B 本文將研究下列問題：（1） 給出特定兩點(diǎn)之間的最短路線。（2） 進(jìn)一步給出精確的路線，包括隧道，橋梁，一般路段，再進(jìn)行總成本的計(jì)算，找出最優(yōu)解。（3） 當(dāng)兩點(diǎn)之間改變?yōu)辄c(diǎn)到面之間時(shí)，我們進(jìn)一步給出解法，求取最短路和總成本。（4） 對(duì)于給出的模型，我們將進(jìn)行

6、評(píng)價(jià)與改進(jìn)。2、 問題分析 首先我們看到題目中給出了好多的數(shù)據(jù)，面對(duì)這么多的數(shù)據(jù)，我們首先就要做出地形的三維圖形（matlab軟件）。但是我們要精確的測(cè)量，這些數(shù)據(jù)只能粗疏表現(xiàn)，因此可能要對(duì)這些數(shù)據(jù)進(jìn)行插值，擬合。 其次我們看到山腳到礦區(qū)要經(jīng)過居民區(qū)，這樣我們尋求最短路方可割裂成兩部分，從山腳到居民區(qū)建立一個(gè)動(dòng)態(tài)規(guī)劃，再?gòu)木用駞^(qū)到礦區(qū)建立一個(gè)動(dòng)態(tài)規(guī)劃，這樣就形成了一個(gè)雙階段的動(dòng)態(tài)規(guī)劃。當(dāng)建立好動(dòng)態(tài)模型時(shí)，我們需要細(xì)化兩個(gè)階段，分別對(duì)兩個(gè)階段不同的地形進(jìn)行三種道路形式的選擇。 最后我們要進(jìn)行最短路的尋求，利用Dijkstra算法。進(jìn)一步設(shè)計(jì)出第二種方案：逐步逼近方法尋求最優(yōu)解。 以上的分析我們可

7、以看出Dijkstra算法，逐步逼近，繪制三維圖等都需要對(duì)其進(jìn)行編程，因此編程在此問題中占得比重很大。3、 基本假設(shè)（1） 地貌假設(shè)：山區(qū)各處高度變化是連續(xù)的，不存在斷崖，斷層；（2） 路段假設(shè)：忽略公路、橋梁、隧道的寬度，路段按幾何線來處理；（3） 設(shè)計(jì)假設(shè)：不考慮修建分岔路，不考慮急轉(zhuǎn)彎，緩急的限制；（4） 幾何假設(shè)：除溪流處外，四個(gè)相鄰的測(cè)量點(diǎn)近似構(gòu)成矩形，因?yàn)橄噜弮牲c(diǎn)的高度差遠(yuǎn)小于它們的水平距離，實(shí)測(cè)點(diǎn)數(shù)據(jù)準(zhǔn)確無(wú)誤。（5） 環(huán)境假設(shè)：該地區(qū)工程地質(zhì)條件滿足工程建設(shè)的要求,不存在對(duì)工程建設(shè)有害因素,如地震帶、溶巖地區(qū)等因素，并且該地區(qū)無(wú)原公路可用；4、 基本符號(hào)說明 A 起始點(diǎn)（0，80

8、0） B 居民點(diǎn)（4000，2000） X 礦區(qū)（2000，4000）dij 網(wǎng)格中V i點(diǎn)和V j點(diǎn)間的徑向距離；Wij V i點(diǎn)和V j點(diǎn)連線的邊的權(quán)值；dist 兩點(diǎn)間的最短路； 坡度控制點(diǎn) 線路必須經(jīng)過的點(diǎn)A，B, C5、 模型的建立與求解1、由題目中的數(shù)據(jù)繪制三維圖形： 為了對(duì)該山區(qū)有一個(gè)立體形象,我們做出它的三維圖,讀者可以輕易的辨別河谷及山脈走勢(shì)，在matlab軟件中輸入代碼（見附錄A地貌代碼），進(jìn)一步進(jìn)行插值擬合方可得到精確的三維圖圖1山區(qū)立體圖我們對(duì)地貌進(jìn)行等勢(shì)線的描繪，在matlab軟件中輸入代碼（見附錄A等勢(shì)線代碼），進(jìn)一步進(jìn)行插值擬合得到精確的等勢(shì)線。圖2等勢(shì)線2 、

9、動(dòng)態(tài)模型建立： 畫出三維圖形后我們要建立雙階段動(dòng)態(tài)規(guī)劃，具體見下： （1）代表意義： ：整段路的總成本 ：公路的長(zhǎng)度 ：橋梁的長(zhǎng)度 ：隧道的長(zhǎng)度。 進(jìn)一步地，對(duì)各個(gè)階段有： 階段1： （從A到B，經(jīng)過溪流） （2） =3002000 階段2： （從B到C，經(jīng)過山脈） 3、不同的地形道路選擇方式分析： 由、的表達(dá)式可知，不同的道路形式具有不同的權(quán)值。山區(qū)地形復(fù)設(shè)計(jì)線路要綜合考慮山脈、湖泊、溪流以及地形起伏的影響。故對(duì)不同的地形應(yīng)有不同的道路形式： (1)公路由于公路的修建成本遠(yuǎn)小于橋梁和隧道，所以在0.125的情況下可以考慮修建“Z”形路。 “Z”形路的每一段的斜率都為0.125，所以，“Z”形

10、路的總長(zhǎng)度為L(zhǎng)8h。 圖3： Z形公路 (2) 隧道 在坡度較大的情況下，可以修建“Z”形路或隧道，而修建隧道的成本較高，只有在坡度滿足一定條件（見下面說明）時(shí)，修隧道比修“Z”形路節(jié)省資金。1 隧道長(zhǎng)度300米 修建隧道的條件為： 1500（x1x2）300米3 當(dāng)隧道垂直穿過山脈，即=90（見圖3）時(shí)，隧道長(zhǎng)度最短 ,我們按這種方式修建隧道 。(3) 橋梁 在兩種情況下可以修建橋梁：線路經(jīng)過溪流、湖泊，且滿足坡度相等的條件時(shí)；兩座相鄰高地的坡度滿足條件時(shí)，修建橋梁比修建公路節(jié)省資金。在本題中，不存在滿足這樣條件的相鄰高地，因此，在以下的討論中不考慮此情況。4、最優(yōu)路徑的選?。河?、3式可知

11、，都較短時(shí)，能得到較優(yōu)的、。此時(shí)，問題已轉(zhuǎn)變?yōu)榍髢牲c(diǎn)間的最短路。對(duì)于從山腳至居民區(qū)的AB段規(guī)劃，以溪谷為對(duì)稱軸，對(duì)溪岸的可修橋點(diǎn)進(jìn)行搜索，便可以從多個(gè)可能的最短路中找出最優(yōu)路徑；對(duì)于從居民區(qū)至礦區(qū)的BC段規(guī)劃，則有多種可選性：1 僅修建“Z”形公路。2 2修隧道。以山脊為對(duì)稱軸，對(duì)可修隧道點(diǎn)進(jìn)行搜索，就可以從多個(gè)可能的最短路中找出最優(yōu)路徑； 至于最短路徑的搜索，給出以下兩種方法：4.1最短路法采用Dijkstra算法(見算法說明)與邊界搜索相結(jié)合的方法求兩點(diǎn)間的最短路徑。分兩段進(jìn)行搜索。 4.1.1從起始點(diǎn)A到居民點(diǎn)B。 從A到B經(jīng)過一條溪流，要在溪流兩岸的等高點(diǎn)處修建橋梁。由于溪流各處的寬度

12、不同，因此橋所在的位置不同，將導(dǎo)致橋和公路的長(zhǎng)度同時(shí)變化，在這種情況下，無(wú)法直接確定橋的最佳位置。Dijkstra算法用于搜索兩固定點(diǎn)間的最短路，在橋梁位置不確定的情況下，先將橋設(shè)在溪流上的任一位置，搜索到橋在這一位置時(shí)對(duì)應(yīng)的最短路，改變橋的位置，即在溪流岸邊進(jìn)行遍歷，每一位置都對(duì)應(yīng)著一條最短路， 再找出所有最短路中最短的一條，得到段最佳路徑。由圖，可以觀察出：谷底成一條直線，且山谷兩岸的等高線關(guān)于谷底對(duì)稱。因此，我們將溪流和溪流兩岸都看作是關(guān)于谷底對(duì)稱。所以，橋梁與谷底沿線是垂直的。AB段的搜索步驟： a 取P0是溪流西岸的一點(diǎn)； b 找到P0關(guān)于谷底的對(duì)稱點(diǎn)Q0；c 用Dijkstra算法

13、分別求出AP0段、P0Q0段和BQ0段的最短路distA,P0 , distB,Q0 , distP0,Q0; d dist0=distA,P0distP0,Q0distB,Q0; e 對(duì)溪流西岸的另一點(diǎn)P1，用上述方法的點(diǎn)的最短路dist1; f dist0=min(dist0,dist1)； g 對(duì)溪流西岸的所有點(diǎn)，執(zhí)行步驟e和f，最后得到的dist0為AB間的最短路。 4.1.2 從居民點(diǎn)B到礦區(qū)X 從等勢(shì)圖中可以看出，在居民點(diǎn)和礦區(qū)之間有一條東西走向的山脈，首先,不考慮修隧道，在坡度0.125處修建“Z”形路，用Dijkstra算法可以在B點(diǎn)和X點(diǎn)之間搜索到一條最短路；然后，考慮修建隧

14、道，為保證隧道盡可能短，使隧道方向與山脈走向垂直。用與1)中相同的方法遍歷山脈兩側(cè)的點(diǎn)，找到一條最短路。 由4.1.1和4.1.2便可以得到從A經(jīng)B到X的最佳路線。以上方法求最佳路線可以先在400m400m的網(wǎng)格中求得粗略線路，然后進(jìn)行優(yōu)化，采用線形插值法將網(wǎng)格細(xì)化為100m100m的細(xì)網(wǎng)格,得到精確線路。 4.1.3 Dijkstra算法說明： 任意兩頂點(diǎn)V i , V j 之間的徑相距離為dij= 2 221/2權(quán)值為 圖5算法流程圖 4.2 逐步逼近法 這里給出另一種搜索公路線路的方法：首先確定起點(diǎn)和終點(diǎn)，然后再以坡度為約束條件，逐個(gè)確定線路經(jīng)過的各點(diǎn)。若起點(diǎn)、終點(diǎn)連線上的點(diǎn)滿足坡度條件

15、，則將此點(diǎn)定為新起點(diǎn)，否則，在鄰邊上尋找滿足坡度條件的點(diǎn)。若所有鄰邊上都不存在滿足坡度條件的點(diǎn)，則修建橋梁或隧道。 圖6 逐步逼近法 4.2.1 算法說明： step1: n=0,dist=0; step2: 連接anA,與棱邊交于點(diǎn)p； step3: 為anp的坡度，若0.125，dist=dist+distan,p , an=p , n=n+1; 返回step2；否則，執(zhí)行step4step4 ：在鄰近棱邊以一定步長(zhǎng)搜索與連線的坡度0.125的點(diǎn)， 記為p0,p1,pn，i為anpi與anA的夾角，若i=min(01n) dist=dist+distan,pi , an=pi , n=n+

16、1; 返回step2圖7 逐步逼近算法流程在400m400m的網(wǎng)格中，用逐步逼近法得到最佳線路的各點(diǎn)數(shù)據(jù)如下：5、模型求解：5.1方案一：Dijkstra算法5.1.1 當(dāng)網(wǎng)格為400m400m時(shí)，其最短路徑如下（不開隧道）表1：Dijkstra算法執(zhí)行結(jié)果X坐標(biāo)y坐標(biāo)X坐標(biāo)y坐標(biāo)X坐標(biāo)y坐標(biāo)08002400 40040002000400400280080036002400800032001200320028001200036001600280032001600040002000240036002000020004000 公路長(zhǎng)：13697米；橋長(zhǎng)：95米；總價(jià)為:429.9萬(wàn)。如修隧道，結(jié)果

17、為：公路長(zhǎng)：1406米；橋長(zhǎng)：95米；隧道長(zhǎng)：300米；總價(jià)：485.8萬(wàn)；（隧道位置為（4000，2800）（4000，3100）之間的一段）。結(jié)果比不開隧道大很多。因此，以后均不考慮修隧道。 5.1.2 細(xì)化為200200后，結(jié)果為：通過居民區(qū)的（3600，2000）點(diǎn)，橋的位置為：（2900，1800）至（3000，1900）的一段。公路長(zhǎng)：12083米；橋長(zhǎng)：73米；價(jià)格：375.8萬(wàn)。圖8：Dijkstra路徑可視化5.2 方案二：逐步逼近算法 表2：根據(jù)逐步逼近算法，可求得下表：xyxyxyxy0.00800.003200.001808.764400.002893.504600.0

18、03043.10400.00639.603600.001748.304580.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.0

19、02823.934390.002963.503600.003496.002800.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 相關(guān)參數(shù)為： 公路的總長(zhǎng)度為1.08672萬(wàn)米， 橋梁長(zhǎng)93.86米, 隧道長(zhǎng)2

20、17.94米,總成本377.479萬(wàn)元。圖9逐步逼近Z路徑可視化注意居民點(diǎn)（4000，2000）到隧道南邊（4400，3080）的公路。由于等高線過于密集，坡度過于陡峭，故修了較多的“Z”形路?？紤]到實(shí)際公路不應(yīng)過于曲折，改進(jìn)如下： 表3：逐步逼近路徑節(jié)點(diǎn)表xyxyxy0.00800.003053.321201.814400.003080.00400.00639.603097.501642.304400.003296.74800.00474.503146.611720.464000.003381.201200.00419.803200.001808.763600.003496.001600.0

21、0419.803600.001748.303262.003600.002000.00486.904000.002000.002800.003747.602400.00668.204053.132800.002400.003866.002800.00999.005296.332844.872000.004000.00 相關(guān)參數(shù)為：公路的總長(zhǎng)度為1.0714萬(wàn)米，橋梁長(zhǎng)93.86米，隧道長(zhǎng)217.94米，總成本372.889萬(wàn)元。圖10逐步逼近隧道路徑可視化6、 模型的評(píng)價(jià)6.1模型的優(yōu)點(diǎn)：（1） 本文用動(dòng)態(tài)規(guī)劃思想，化整為零，使模型簡(jiǎn)化，便于更大程度的推廣。（2） 目標(biāo)明確，有確定的目標(biāo)函數(shù)和問

22、題的分析方向。（3） 尋找最優(yōu)路段有兩種方法，它們各具特色。方案一適用于精確定線，方案二利用逐漸逼近思想，需求近似最優(yōu)解，雖然沒有方案一精確，但是花費(fèi)時(shí)間段，速度快。（4） 三維立體圖形與等勢(shì)圖使得模型更加直觀，可視化，這也是本文的一大特點(diǎn)。6.2模型的缺點(diǎn)：（1） 沒有考慮分岔路，或許在適當(dāng)?shù)奈恢媒ǚ植砺愤€可以大大降低成本。（2） 網(wǎng)絡(luò)沒有進(jìn)一步細(xì)化，細(xì)化后可能會(huì)更加精確。6.3模型的改進(jìn)：（1） 進(jìn)一步考慮分岔路，降低成本。（2） 橋梁，隧道候選點(diǎn)的選定比較粗疏，進(jìn)一步可以建立方程，求取最優(yōu)點(diǎn)。 （3） 進(jìn)一步進(jìn)行網(wǎng)絡(luò)優(yōu)化，縮小范圍，求取最優(yōu)近似解。 6.4模型的誤差分析：（1） 網(wǎng)絡(luò)沒有

23、進(jìn)一步細(xì)化，因此軟件編程運(yùn)行結(jié)果存在一定的誤差。（2） 模型本身建立的不是非常完善，存在一定的誤差。 6.5模型靈敏度分析： 對(duì)于模型的靈敏度我們首先看到兩種方法的誤差在110萬(wàn)元以上，尤其是在開隧道時(shí)，這是可以接受的。在網(wǎng)絡(luò)的細(xì)分中我們看到最后細(xì)分為200200，這在很大程度上已經(jīng)是比較精確的了。7、 參考文獻(xiàn)1 施光燕，董加禮編 最優(yōu)化方法 高等教育出版社 1999.92 周義倉(cāng)，阮曉青編 數(shù)學(xué)建模引論 高等教育出版社 2005.73 李學(xué)文，王宏洲編 數(shù)學(xué)建模優(yōu)秀論文 清華大學(xué)出版社 2011.94 馬莉編 MATLAB數(shù)學(xué)實(shí)驗(yàn)與建模 清華大學(xué)出版社2010.15 周義倉(cāng) ，赫孝良 數(shù)學(xué)

24、建模實(shí)驗(yàn) 西安交通大學(xué)出版社 2001.16 王素麗，高潔，孫新德 MATLAB混合編程與工程應(yīng)用 清華大學(xué)出版社 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,i+1,i,0,14;funx_,y_:=Sumf1.x,400.j 1j,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-400.(i-1)/;400(i-1)=x=400i&i! =0;1I_,x