校園景觀道路設(shè)計問題

1、1 隴東學院第二屆大學生數(shù)學建模競賽隴東學院第二屆大學生數(shù)學建模競賽 承承 諾諾 書書 我們仔細閱讀了隴東學院數(shù)學建模競賽的競賽規(guī)則. 我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子 郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關(guān) 的問題。 我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他 公開的資料（包括網(wǎng)上查到的資料） ，必須按照規(guī)定的參考文獻的表述方式在正 文引用處和參考文獻中明確列出。 我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違 反競賽規(guī)則的行為，我們將受到嚴肅處理。 我們參賽選擇的題號是（從 a/b/c

2、/d 中選擇一項填寫） b 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： 所屬院系（請?zhí)顚懲暾娜?參賽隊員 (打印并簽名) ：1. 2. 3. 指導教師或指導教師組負責人 (打印并簽名)： 日期： 2012 年 5 月 27 日 2 校園文化景觀中心道路設(shè)計問題校園文化景觀中心道路設(shè)計問題 摘要：摘要： 對于所給的校園文化景觀中心道路設(shè)計問題，我們主要使用了 matlab 軟件， 這樣在數(shù)值計算和調(diào)用函數(shù)方面有著很強的功能，尤其在編程解決具體問題時 它操作簡便，效率高，節(jié)省時間。 本文研究的是最短路線設(shè)計問題，屬于優(yōu)化問題。通過道路設(shè)計來探討如何 使得新修路總路程最小，為此，我們有了

3、了兩個基本的思路：一是充分利用邊 界上的道路，能通過邊界解決的問題盡量不再去另外修路。二是充分利用已經(jīng) 修過的道路，通過“少修多連”的方法，盡量減少路程，我們稱其為“借路原理”。 在問題的解決過程中，我們主要是計算出數(shù)據(jù)，然后考慮是否滿足思路一，緊 接著通過思路二來進一步優(yōu)化、減少路程。我們不是直接求出最優(yōu)路徑，而是 利用排除法思維，先找到一條優(yōu)化道路，但緊跟其后又找到了更優(yōu)化的路徑， 通過層層對比，最終確定出最優(yōu)路線。 關(guān)鍵字關(guān)鍵字：matlab 軟件 基本思路一 基本思路二 排除法 3 目錄 一、問題的重述一、問題的重述:.3 二問題的分析和符號說明二問題的分析和符號說明.5 三、模型假設(shè)

4、三、模型假設(shè).6 四、模型建立四、模型建立.6 五、模型求解：五、模型求解：.6 問題一：.6 1.求解前提條件：.6 2.開始求解：.8 問題二：.15 1.求解前提條件：.15 2.開始求解.15 六模型評價：六模型評價：.22 七參考文獻：七參考文獻：.22 4 一、問題的重述一、問題的重述: 我校計劃在逸夫教學樓與信息樓之間建一個形狀為矩形或其他不規(guī)則圖形 的校園文化景觀中心，不僅為了美化校園環(huán)境，也是想為其學生提供更的生活 條件。該中心計劃有若干個入口，現(xiàn)在你需要建立一個模型去設(shè)計道路讓任意 兩個入口相連（可以利用四周的邊，即默認矩形的四條邊上存在已經(jīng)建好的道 路，此道路不計入道路總

5、長） ，使總的道路長度和最小，前提要求是任意的兩個 入口之間的最短道路長不大于兩點連線的 1.4 倍。 主要設(shè)計對象可假設(shè)為如圖所示的矩形校園文化景觀中心，其相關(guān)數(shù)據(jù)為： 長 200 米，寬 100 米，1 至 8 各入口的坐標分別為： p1(20,0),p2(50,0),p3(160,0),p4(200,50), p5(120,100),p6(35,100),p7(10,100),p8(0,25). 問題一：假定校園文化景觀中心內(nèi)確定要使用4個道路交叉點為：a(50,75)， b(40,40)，c(120,40)，d(115,70） 。問如何設(shè)計道路可使公園內(nèi)道路的總路程最 短。建立模型并給

6、出算法。畫出道路設(shè)計，計算新修路的總路程。 問題二：現(xiàn)在校園文化景觀中心內(nèi)可以任意修建道路，如何在滿足條件下使總 路程最少。建立模型并給出算法。給出道路交叉點的坐標，畫出道路設(shè)計，計 算新修路的總路程。 注：以上問題中都要求景觀中心內(nèi)新修的道路與四周的連接只能與8個路口相通， 而不能連到四周的其它點。 圖 1 公園及入口示意圖 5 圖 2 一種可能的道路設(shè)計圖 二問題的分析和符號說明二問題的分析和符號說明 題目中有對道路建設(shè)的要求是:“任意的兩個入口之間的最短道路長不大于 兩點連線的 1.4 倍”，于是我們首先考慮 p1 與 p7 間的直線距離乘以 1.4 等于 141.0，而 p1 和 p7

7、 僅通過邊界路線相連接的最短距離為 130,由于 130=1.4*(m-n)的條件，需要重新規(guī)劃路線。從而問題變得很簡明。 三、模型假設(shè)三、模型假設(shè) 1.近似認為每個入口都是一個質(zhì)點，不占用空間位置，從而 mn 之間修的 直線路線的長度即為|mn|。 2.認為道路的寬度為 0，即所修的路都是線段，長分別是 a 和 b 的兩條路 線相交，則兩條路的總長度是 a+b。 3.認為公園的地面是完全平整無凹陷和突起的。 四、模型建立四、模型建立 根據(jù)上面的陳述，我們大致可總結(jié)出修路要遵循的兩個原理： a1: 滿足 mn（q）=1.4*（m-n）的兩點 m,n 間不需再專門修路。 a2：應(yīng)充分利用已有或已

8、經(jīng)修過的路作為條件來完成需修而未修的兩點 間的路。 下面是我們嘗試在這兩個原理的基礎(chǔ)上，根據(jù)兩個問題的不同要求，運用 排除比較的方法來盡量確定最優(yōu)道路。 五、模型求解：五、模型求解： 問題一： 1. 求解前提條件： 該問題有一個基本要求就是“確定要使用 4 個道路交叉點為：a(50,75)， b(40,40)，c(120,40)，d(115,70） 。首先要說明道路交叉點。我們?nèi)?” 任一個 交叉點 q，則至少有兩條不同的道路通過 q，下面列出的三種情況都是符合題 意的： 7 圖-2 情況一：一點通過三條不同道路 圖-3 情況二：一點通過多條不同道路 圖-4 情況三：一點通過兩條不同道路 這里

9、需要特別注意解題用圖-4 中所給的情況， 只有兩條道路以折線方式 相交仍視點 q 為道路交叉點。 前面所提到的“至少有兩條不同的道路通過 q”中的 “不同道路”具體指兩條 不能連成線段的道路，如圖-5， 8 圖- 5 此時認為只有一條路通過 q，即 q 不是道路交叉點，這是一種不符合 q 為交叉點的情況。 另一種不符合 q 為交叉點的情況是沒有任何道路通過 q。 2. 開始求解： 觀察需要重新修建道路的各點組合，即 15, 16, 18, 34, 35, 36, 37, 25, 26, 27，發(fā)現(xiàn) 1,2,3 均需要連到 5,6，所以選擇從 5,6 點開始著手。 先考慮 6 點。 一1，6 之

10、間需要滿足原理 a1，最簡單的辦法就是 1- -6，連接后， （如 圖-6）若不再修建其他道路，26（2- -1- -6）=131.11.4*s（2,6）=141.6，滿足 原理 a1（下面再有此種論斷則簡化些為 mn（q）=a150.8，不符 a1。 專門再為 27 修路代價太大，因此改變 16 之間的連接方法。 二考慮 16 通過 1- -b- -6 的方法，并且連接 2- -b（原理 a2） ，則 16（1- -b- -6）=104.9141.6，a1。 26（2- -b- -6）=141.4141.6，a1。 27（ 2- -b- -6- -7 ）=126.4150.8 ，a1。 如圖

11、-7 9 圖- 6 圖- 7 10 為了能使 1,2 能與 5 相連，當在連接 16(1- -6)時但 27（2- -b- -6- - 7）不符 a1，不能像連接 2- -b 一樣，從 2 或 7 到（1- -6）直線上修一條路 （a2） 。如圖-8 圖 8 同理檢驗可得 36（3- -2- -b- -6）=211.4224.1，a1。 37（3- -2-b- -6- -7）=236.4252.4，a1。 接著考慮 1,2,3 和 5 的連接。 35 較簡單，為使路程盡量短且通過 c，d 點，35 取 3- -c- -d- -5，又 35（3- -c- -d- -5）=117.4150.8，a

12、1。 15 由于 a 點還沒有通過任何道路，所以考慮 15（1- -b- -a- -5）, 此 時 15=155.4198，a1。 25 取 25（2- -b- -a- -5） （a2） ，此時 25=151.9170.9，不符 a1。所以不通過 15（1- -b- -a- -d- -5） ，25（2- -b- -a- -d- -5） ，這樣修路。 如圖-10 11 圖- 9 圖- 10 12 現(xiàn)在看 15, 16, 35, 36, 37, 25, 26, 27，之間的路程修建似乎可以 結(jié)束了， 但通過觀察現(xiàn)有圖形，考慮將 a- -6 代替 b- -6（a2） ，因為前者 明顯比后者短些。 下

13、面我們進行一些替換后的檢驗（主要靠 a1） ： 16（1- -b- -a- -6）=110.2140，a1。 26（2- -b- -a- -6）=106.7140.7，a1。 27（2- -b- -a- -6- -7）=131.7151.8，a1。 36（3- -2- -b- -a- -6）=216.7224.1，a1。 37（3- -2- -b- -a- -6- -7）=241.7（a- -5） ，路程反 而增加，舍棄不用。如圖-12 又有以下情況 25（2- -c- -d- -5） ，15（1- - 2- -c- -d- -5） 。 但經(jīng)過計算，雖然換線路后新數(shù)據(jù)完全符合 a1，但（2-

14、-c）（a- -5） ， 路 程反而增加，舍棄不用。 如圖-13 13 圖- 12 圖- 13 14 接下來考慮 18 和 34. 18： 最直接最簡便的方法當然是直接連接 1,8 兩點，但考慮（a2） ，我們可 以過 8 做 1- -b 的垂線， （如圖-14）設(shè)垂足為 o 顯然比直接連接減少了路長， 下面檢驗， 18（1- -p- -8）=42.944.8，a1。 34： 和 18 思路完全相同，過 4 做 3- -c 的垂線，垂足設(shè)為 p，檢驗。 34(3- -p- -4)=70.645 度 所以（ 43c）=180-23p -180 度-p34198.0,不符 a1。 26（2- -1

15、- -6）=131.1150.8，不符 a1。 25（2- -3- -5）=217.1170.9,不符 a1。 3- -5，則 35 符合 a1。 36（3- -5- -6）=192.1224.1，a1。 37（3- -5- -6- -7）=217.1150.8,不符 a1。 實驗二，過 2 做 1- -6 垂線，垂足為 n， （如圖-17） 。 則 27（2- -n- -6- -7）=150.9150.8,不符 a1。 試驗三：綜合試驗一二。 則 27（2- -n- -m- -7）=146.6150.8,a1。 但是考慮到做了兩條垂線，路程過長，應(yīng)該尋求更節(jié)省路長的畫法。因為原 來什么都沒做

16、時 27 超出規(guī)定的長度是 156.1-150.86，所以考慮 a2，從 2 向 1- -6 做線段，與 1- -6 交點去 n1，并設(shè) 1- -n1=x，2- -n1=a，通過 matlab，運 用余弦定 理，即（1- -2）2+x2-2*x*(1- -2)=a2,聯(lián)立（1- -2）+x-a=6，即可 算出比試驗三更優(yōu)化的試驗四： 此時 x=5.7，a=29.7,27（2- -n1- -6- -7）=149.9150.8，a1。 對應(yīng)地，過 7 做（1- -6）垂線垂足設(shè)為 m1，同樣可得試驗五： 此時 x=5.8，a=24.8,27（2- -1- -m- -7）=150.1150.8; 比

17、較試驗三四五所修路程長度，即可得最佳方案為方案五， （如圖-18）所修長 度 l=24.7. 17 圖- 17 圖- 18 18 再討論 15,25 若連接 2- -5， 則 25（2- -5）顯然符合 a1。 15（1- -2- -5）=152.1198.0, a1. （如圖-19） 圖- 19 考慮到 a2，我們可以過 2 做 3- -5 垂線垂足為 c， （如圖-20） 。 則 25（2- -c- -5）=159.2170.9, a1. 15(1- -2- -c- -5)=189.2198.0, a1. 所以此方案才是最佳方案 考慮 18,34： 同問題 1，我們過 8 做 1- -6

18、垂線垂足為 o，過 4 做 3- -5 垂線，垂足為 p【做垂線之前我們同樣要先判斷（角 816）和（角 435）是否為銳角的問題， 方法和問題一同理，經(jīng)判斷兩角都是銳角】 ， 18（1- -o- -8）=43.444.8, a1 43(4- -p- -3)=87.289.6, a1（如圖-21） 19 圖- 20 圖- 21 方案一已經(jīng)將問題二解決，最后的路線圖如圖-22： 20 圖- 22 且總路程 s=413.7。 方案二： 連接 2- -6，3- -5, 16（1- -2- -6）=131.1141.0，a1 26（2- -6）顯然符合 a1 27（2- -6- -7）=126.1150.8,a1 36(3- -2- -6)=211