數模公園內道路設計問題

1、B題 公園內道路設計問題目錄1.問題重述-12.問題分析-33.模型假設-44.符號說明-45.模型建立與求解-5問題一 -5 問題二-9 問題三-156.模型分析-187.參考文獻-188.附錄-198.1 附錄一 -198.2 附錄二 -208.3 附錄三 -21一.問題重述西安某大學計劃建一個形狀為矩形或其他不規(guī)則圖形的公園，不僅為了美化校園環(huán)境，也是想為其學生提供更的生活條件。公園計劃有若干個入口，現在你需要建立一個模型去設計道路讓任意兩個入口相連（可以利用公園四周的邊，即默認矩形的四條邊上存在已經建好的道路，此道路不計入道路總長），使總的道路長度和最小，前提要求是任意的兩個入口之間的

2、最短道路長不大于兩點連線的1.4倍。主要設計對象可假設為如圖所示的矩形公園，其相關數據為：長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).示意圖見圖1，其中圖2即是一種滿足要求的設計，但不是最優(yōu)的。現完成以下問題：問題一：假定公園內確定要使用4個道路交叉點為：A(50,75)，B(40,40)，C(120,40)，D(115,70）。問如何設計道路可使公園內道路的總路程最短。建立模型并給出算法。畫出道路設計，計算新修路的總路程。問

3、題二：現在公園內可以任意修建道路，如何在滿足條件下使總路程最少。建立模型并給出算法。給出道路交叉點的坐標，畫出道路設計，計算新修路的總路程。問題三：若公園內有一條矩形的湖，新修的道路不能通過，但可以到達湖四周的邊，示意圖見圖3。重復完成問題二 的任務。其中矩形的湖為R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。注：以上問題中都要求公園內新修的道路與四周的連接只能與8個路口相通，而不能連到四周的其它點。圖 1 公園及入口示意圖圖 2 一種可能的道路設計圖圖3 有湖的示意圖二.問題分析題目欲對公園內道路進行設計，通過預先設定公園四周的八個入口

4、，建立模型設計道路讓任意兩個路口相連，使總的道路總長最小，前提條件是任意兩個路口之間道路最短長度不大于兩點直線距離的1.4倍，同時道路總長中不包含公園四周的邊。在第一問中，題目已經給出公園內部確定的四個道路交叉點，要求設計道路使道路總長最小。由于內部的交叉點已經給定，解決該問題的關鍵是：建立合理模型在兩點最短路徑小于兩點直線距離的1.4倍的條件下，優(yōu)先運用矩形周邊的連線，使八個入口點能夠兩兩連通，并且總長度最小。在第二問中，公園內部的道路岔口沒有給出，這樣需要建立合理模型確定內部點的數量以及坐標。確定內部點的數量和坐標后利用相同方法生成最短路徑。在得出的最短路徑中需要人為修改以滿足路徑距離小于

5、直線距離1.4倍的條件。而在局部修改過程中需要確定一點到局部三點最短的問題，因此可以通過尋找費馬點進一步優(yōu)化最終的最短路徑。在第三問中，矩形內部存在一片區(qū)域，道路不能通過，但可以到區(qū)域的邊緣。因此可在第二問結論的基礎上合理簡化模型，設計不同方案，通過比較驗證，確立最終結論。三.模型假設1.不計道路寬度，將路徑簡化為直線處理。2.不直接相連的兩點間距離為無窮大。3.相鄰兩點且滿足限定條件的兩點間距離設為零。4.假設矩形內三點均勻分布在整個區(qū)域，且不靠近邊界。四.符號說明1.G: 表示連通圖。2.P: 表示G的最小生成樹中頂點的集合。3.Q：表示G的最小生成樹中邊的集合。4.X1，X2，X3：表示

6、大范圍內搜索點的橫坐標。5.Y1，Y2，Y3：表示大范圍內搜索點的縱坐標。6.X1，X2，X3：表示小范圍內搜索點的橫坐標。7.Y1，Y2，Y3：表示小范圍內搜索點的橫坐標。8.L：任意兩點最小直線距離的1.4倍矩陣。9.Z: 任意兩點最小路線距離矩陣。10.Q：L與Z的差值矩陣。11.W: 任意兩點間的路徑距離矩陣。12.P：任意兩點在周邊上距離的矩陣。五模型建立與求解問題一：假定公園內確定要使用4個道路交叉點為：A(50,75)，B(40,40)，C(120,40)，D(115,70）。問如何設計道路可使公園內道路的總路程最短。建立模型并給出算法。畫出道路設計，計算新修路的總路程。此部分針

7、對公園內部有四個交叉口的情況進行模型建立，模型建立過程中有一定的約束條件。需要對已有的模型算法進行改進使之符合題目的要求，編寫程序，讀出結果，做出圖形；1.建立模型:（1）.圖論的最小生成樹模型：最小生成樹概念：在一個具有幾個頂點的連通圖G中，如果存在子圖G'包含G中所有頂點和一部分邊，且不形成回路，則稱G'為圖G的生成樹，代價最小生成樹則稱為最小生成樹。最小生成樹性質：設G=(V，E）是一個連通網絡，U是頂點集V的一個真子集。若(u，v）是G中一條“一個端點在U中（例如：uU），另一個端點不在U中的邊（例如：vV-U），且（u，v）具有最小權值，則一定存在G的一棵最小生成樹包

8、括此邊（u，v）。最小生成樹算法prim算法的描述：設置兩個集合和,其中用于存放的最小生成樹中的頂點，集合存放的最小生成樹中的邊。令集合的初值為（假設構造最小生成樹時，從頂點出發(fā)），集合的初值為。prim算法的思想是從所有，的邊中，選取具有最小權值的邊，將頂點加入集合中，將邊加入集合中，如此不斷重復，直到時，最小生成樹構造完畢，這時集合中包含了最小生成樹的所有邊。prim算法如下：（i），；（ii）while end(2).模型的改進最小生成樹模型與最短路模型的結合：由于本題對最小生成樹模型加有一定的約束條件，就形成了帶有約束條件的最小生成樹問題。在最小生成樹模型基礎上結合最短路模型對兩路口之

9、間最短路徑小于兩路口連線的1.4倍加以限制，即采用最短路模型中dijkstra算法相互結合求解。Dijkstra算法簡介：Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijksta算法步驟：1. 初使時令 S=V0,T=其余頂點，T中頂點對應的距離值 ，若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值 ，若不存在<V0,Vi>，d(V0,Vi)為 。2.從T中選取一個其距離值為最小的頂點W且不在S中，加入S 。3.對T中頂點的距

10、離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值，重復上述步驟2、3，直到S中包含所有頂點，即S=T為止2.求解模型:第一步：先采用最小生成樹prim算法計算出在沒有約束條件下的總路徑最短的設計方法即沒有兩個路口之間最短路徑小于兩點之間直線距離的1.4倍及路徑長度中不包含周邊道路的條件。生成的最短路徑圖如圖4：圖4（程序見附錄一）第二步：程序輸出不滿足限制條件的路徑，進一步修改程序的輸入鄰接矩陣，即使不可能的路徑權值為無窮大，這里權值設置成1000達到無窮大效果。得到路徑解同時輸出不滿足約束條件的路徑，合理局部修改得到最優(yōu)解。最短路徑圖如圖5：圖5經計算

11、最短的總路徑長度為：w(1,8)+w(2,10)+w(9,5)+w(9,10)+w(9,6)+w(12,5)+w(11,12)+w(11,3)+w(3,4)= 394.55973.方案驗證：（1）任意兩點間直線距離的1.4倍矩陣為L：（2）任意兩點間的路徑距離矩陣為W：（3）兩矩陣的差值為Q： 經驗證，差值矩陣Q中元素全部為正數，表示任意兩點之間最短路徑不超過兩點直線距離的1.4倍，因此此方案合理。問題二 現在公園內可以任意修建道路，如何在滿足條件下使總路程最少。建立模型并給出算法。給出道路交叉點的坐標，畫出道路設計，計算新修路的總路程。此部分針對公園內可以任意修建道路，通過在公園內尋找合理數

12、目與位置的基點，在第一問的基礎上建立模型，利用最小生成樹的prim算法和每兩點最短路徑的Dijkstra算法求解模型，得出最短路徑，在此基礎上利用費馬點結論進一步優(yōu)化結果并驗證得出最優(yōu)路線。1.建立模型根據第一問得出的路線圖四個交叉點存在冗余交點，因此假設矩形區(qū)域存在三個交叉點。假設三點均勻分布在矩形區(qū)域內且不靠近邊界，合理計算三點坐標，以交叉點為中心確定適當大小的圓形區(qū)域。以此三點作為圓心，利用變化半徑和變化角度，在各自區(qū)域內循環(huán)搜索最小生成樹路線總長度最短的三個交叉點。在合理基點的基礎上，縮小半徑變化范圍，減小步長，利用相同方法尋找更合理的交叉點以實現更短路徑。得到基點以后建立同第一問中的

13、模型，利用最小生成樹模型結合prim算法和Dijkstra算法求解模型，得出最短路徑圖。通過制定任意兩點在周邊上距離的表格，查找出距離大于兩點直線距離1.4倍的所有點，在最短路徑圖的基礎上合理優(yōu)化，以滿足所有1.4倍條件。利用費馬點原理，由2,5,6三點和3,4,5三點分別構成三角形，通過幾何方法找出其費馬點，進一步優(yōu)化最短路徑圖，并驗證結果是否符合1.4倍條件。2.求解模型.大范圍基點搜索將公園矩形區(qū)域劃分成三等份，在每個區(qū)域中確定三個基點即A(50,30)，B(100,60)，C(150,30)，以此三點作為圓心，以R（0<=R<=25）為半徑，在基點周圍12個角度方向上取點即

14、：X1=50+R1*cos(a*/6) （R1=0,5,10,15,20,25） (a=0,1,2,3,4,5)Y1=30+R2*sin(a*/6) （R1=0,5,10,15,20,25） (a=0,1,2,3,4,5)X2=100+R1*cos(a*/6) （R2=0,5,10,15,20,25） (b=0,1,2,3,4,5)Y2=60+R2*sin(a*/6) （R2=0,5,10,15,20,25） (b=0,1,2,3,4,5)X3=150+R1*cos(a*/6) （R3=0,5,10,15,20,25） (c=0,1,2,3,4,5)Y3=30+R2*sin(a*/6) （R3

15、=0,5,10,15,20,25） (c=0,1,2,3,4,5)通過設計四重循環(huán)，以最短路徑作為約束條件，逐點排查，尋找大體的合理基點，結果為：A（70,30），B（70,75），C（170,30）.小范圍基點搜索一步基點確定為 ，以此四點為圓心，步長縮短為1m，以R（0<R<5）,在基點周圍12個角度方向上即：X1=50+R1*cos(a*/6) （R1=0,1,2,3,4，5） (a=0,1,2,3,4,5)Y1=75+R2*sin(a*/6) （R1=0,1,2,3,4，5） (a=0,1,2,3,4,5)X2=40+R1*cos(a*/6) （R2=0,1,2,3,4，5

16、） (b=0,1,2,3,4,5)Y2=40+R2*sin(a*/6) （R2=0,1,2,3,4，5） (b=0,1,2,3,4,5)X3=120+R1*cos(a*/6) （R3=0,1,2,3,4，5） (c=0,1,2,3,4,5)Y3=40+R2*sin(a*/6) （R3=0,1,2,3,4，5） (c=0,1,2,3,4,5)利用相同方法可得出進一步細化的合理交叉點，結果為：A（70,30），B（74,75），C（174,30）.生成最短路徑圖以上一步所得的基點為基礎，利用最小生成樹的方法和Dijkstra算法求解模型，可得出最短路徑圖，算法及結果為：圖5.合理優(yōu)化最短路徑圖任意

17、兩點在周邊上距離的矩陣P為： 通過以上矩陣將最短路徑圖優(yōu)化成為：圖6(5).最終的最短路徑圖分析以上所得最短路徑圖，通過尋找某些三角形的費馬點可以實現對最短路徑圖的進一步優(yōu)化。費馬點：定義：在一個三角形中，到3個頂點距離之和最小的點叫做這個三角形的費馬點。 費馬點作法： i.平面內一點P到ABC三頂點的之和為PA+PB+PC，當點P 為費馬點時，距離之和最小。 ii.三內角皆小于120°的三角形，分別以 AB,BC,CA，為邊，向三角形外側做正三角形ABC1,ACB1,BCA1,然后連接AA1,BB1,CC1,則三線交于一點P,則點P就是所求的費馬點. iii.若三角形有一內角大于或

18、等于120度,則此鈍角的頂點就是所求的費馬點. iv. 當ABC為等邊三角形時,此時外心與費馬點重合 通過分析上一步所得的最短路徑圖可得：分別以2,5,6和3,4,5為定點構成三角形，分別找出其費馬點，費馬點分別為（62.67,77.284）和（172.1,43.5），經演算發(fā)現1和6之間不滿足條，因此以此費馬點作為圓心，以1-5為步長尋找符合條件的交叉點，得出新的基地為（58.67,78.284），以此進一步優(yōu)化最短路徑圖如圖所示： 圖73.方案驗證：（1） 任意兩點間直線距離的1.4倍矩陣L為：（2）任意兩點間的路勁距離矩陣W為： （3）兩矩陣的差值Q為： 經驗證，差值矩陣中元素全部為正數

19、，表示任意兩點之間最短路徑不超過兩點直線距離的1.4倍，因此此方案符合題目條件，依此所求的最短總路程的長度為:w(1,8)+w(2,9)+w(9,5)+w(9,6)+w(10,5)+w(10,3)+w(10,4)=358.6042m問題三若公園內有一條矩形的湖，新修的道路不能通過，但可以到達湖四周的邊，示意圖見圖。重復完成問題二 的任務。圖8此部分針對公園內存在一條矩形湖，可以利用第二問所得結論進行分析調整，制定不同的設計方案，通過分析對比選擇最為合理的方案以實現滿足條件的最短路徑圖。1.建立模型分析第二問所得結論，由于三角形兩邊之和大于第三邊，顯然繞湖邊修路長度大于折線，排除所有繞

20、湖修建新路的方案。因此提出方案一為：以R2為交點，連接R2和3以及R2和5，并連接3和4，得出新的路徑圖，如圖9。分析第二問所得結論，提出方案二為：以R4為交點，以R4，3和4構成三角形，通過尋找此三角形的費馬點，并利用此費馬點和R4作為交叉點，得出新的路徑圖，設為方案二，如圖10。通過比較兩種方案的路徑長度和驗證任意兩點的距離是否小于直線距離1.4倍的條件，選擇合理的方案。2.求解模型根據方案一，連接連接R2和3， R2和5， 3和4，得出新的路徑圖如圖：圖9其路徑為: 5-R2-3-4 路徑長度: 171.798m并且滿足任意兩點的最短路徑距離小于直線距離的1.4倍。根據方案二，以R4為交

21、叉點，以R4，3和4構成三角形，通過尋找此三角形的費馬點，并利用此費馬點和R4作為新的交叉點，得出新的路徑圖如圖10：圖10其路徑為：5-R4-10-(3、4) 路徑長度為：152.7866 方案二中任意兩點的最短路徑距離小于直線距離的1.4倍。比較路徑總長度，顯然方案二更優(yōu)，故選擇方案二。3.方案驗證：（1） 任意兩點間直線距離的1.4倍矩陣L為：（2） 任意兩點間的路勁距離矩陣W為：（3） 兩矩陣的差值Q為：經驗證，差值矩陣中元素全部為正數，表示任意兩點之間最短路徑不超過兩點直線距離的1.4倍，因此此方案符合題目條件，依此所求得最短總路程的長度為:360.7485m六、模型的評價1. 本模

22、型第一問以最小生成樹模型為基礎，結合prim算法總路線和最短的特點和以最短路Dijkstra求每兩點最短路徑的優(yōu)點。2. 結合人工解析法和計算機編程算法得出最優(yōu)解。3. 巧妙應用費馬點原理使路線得到很大的優(yōu)化。4. 合理假設，對矩形內進行分區(qū)域逐層縮小范圍，減小步長循環(huán)搜索，使結果趨近最優(yōu)。5.模型求解采用人工與計算機結合方法，計算機編程較為復雜，并在人工分析中有一定的簡化，數據計算精度有一定的誤差，不一定能夠達到最優(yōu)解但也可趨近于最優(yōu)解。 6.算法中加入了人為地優(yōu)化及選擇，不利于模型的推廣應用。七、參考文獻：1 梁國業(yè)，廖健平，數學建模，北京：冶金工業(yè)出版社，20042 朱道元，數學建模案例

23、，北京：科學出版社，20033 蔣珉，MATLAB程序設計及應用，北京：北京郵電大學出版社，20104 趙東方，數學模型與計算，北京：科學出版社，2007附錄附錄一clc;clear allM=1000;a=0 1 140 186.8154 141.4214 101.1187 100.4988 32.0156 58.3095 92.4175 156.89491 0 1 158.1139 122.0656 101.1187 107.7033 55.9017 36.0555 78.7464 127.5774140 1 0 64.0312 107.7033 160.0781 180.2776 161

24、.9413 94.8683 114.1096 33.1059186.8154 158.1139 64.0312 0 94.3398 172.4094 196.4688 201.5564 131.5295 128.4562 1000141.4214 122.0656 107.7033 94.3398 0 85 1000 141.5097 86.0233 52.3546 88.4081101.1187 101.1187 160.0781 172.4094 85 0 1 82.7647 78.2624 46.3249 155.631100.4988 107.7033 180.2776 196.468

25、8 1000 1 0 75.6637 92.1954 68.7095 178.314332.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0 70.1783 89.3085 174.071858.3095 36.0555 94.8683 131.5295 86.0233 78.2624 92.1954 70.1783 0 45.1774 10492.4175 78.7464 114.1096 128.4562 52.3546 46.3249 68.7095 89.3085 45.1774 0 109.6586156.8949 1

26、27.5774 33.1059 1000 88.4081 155.631 178.3143 174.0718 104 109.6586 0; result=;p=1;tb=2:length(a);s=0;while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); jb,kb=find(a(p,tb)=d); j=p(jb(1);k=tb(kb(1); result=result,j;k;d;p=p,k;tb(find(tb=k)=; b(j,k)=d; s=s+d;endresultsb=b+b'b(

27、find(b=0)=M;c=b;c(1,2)=30;c(2,1)=30;c(2,3)=110;c(3,2)=110;c(5,6)=85;c(6,5)=85;c(6,7)=25;c(7,6)=25;for i0=1:8 for j0=1:8 min,path=dijkstra(c,i0,j0); if (min >a(i0,j0)*1.4) path end endend 附錄二三點搜索程序x3=150;y3=30;r3=0; for i3=1:5 for j3=1:12 x3=150+r3*cos(j3*pi/6);y3=30+r3*sin(j3*pi/6);x2=100;y2=60;r

28、2=0; for i2=1:5 for j2=1:12 x2=50+r2*cos(j2*pi/6);y2=75+r2*sin(j2*pi/6);x1=50;y1=30;r1=0; for i1=1:5 for j1=1:12 x1=r1*cos(j1*pi/6)+70;y1=r1*sin(j1*pi/6)+30; w=; for j=1:11 x=20,50,160,200,120,35, 10, 0, x1,x2,x3; y=0, 0, 0, 50, 100,100,100,25,y1,y2,y3; x0=x(j);y0=y(j); x=x-x0; y=y-y0; d0=sqrt(x.*x+

29、y.*y); w=w;d0; %w(1,2)=0;w(2,1)=0;w(5,6)=0;w(6,5)=0;w(6,7)=0;w(7,6)=0; end result=;p=1;tb=2:length(w);s=0; while ( length(result)=length(w)-1) temp=w(p,tb);temp=temp(:); d1=min(temp); jb,kb=find(w(p,tb)=d1); j0=p(jb(1);k=tb(kb(1); result=result,j0;k;d1;p=p,k;tb(find(tb=k)=; s=s+d1;s1=10000; end end

30、r1=r1+5; if (s<s1) s1=s; s1 x10=x1,y10=y1 x20=x2,y20=y2 x30=x3,y30=y3 end end endr2=r2+5; end end r3=r3+5; end 附錄三驗證程序z = 0 30 140 186.8154 141.4214 101.1187 100.4988 32.015630 0 110 158.1139 122.0656 101.1187 107.7033 55.9017140 110 0 64.0312 107.7033 160.0781 180.2776 161.9413186.8154 158.1139

31、64.0312 0 94.3398 172.4094 196.4688 201.5564141.4214 122.0656 107.7033 94.3398 0 85 110 141.5097101.1187 101.1187 160.0781 172.4094 85 0 25 82.7647100.4988 107.7033 180.2776 196.4688 110 25 0 75.663732.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0;%±ß×î¶Ìq =

32、 0 30 140 230 240 155 130 45 30 0 110 200 240 185 160 75 140 110 0 90 220 295 270 185 230 200 90 0 130 175 240 275 240 240 220 130 0 85 110 195 155 185 295 175 85 0 25 10 130 160 270 240 110 25 0 85 45 75 185 275 195 10 85 0 ;%1ͨ·¾ØÕót1=1000 30 1000 1000 100

33、0 1000 1000 32.016 1000 1000 1000 100030 1000 110 1000 1000 1000 1000 1000 1000 41.231 1000 10001000 110 1000 64.031 1000 1000 1000 1000 1000 1000 56.569 10001000 1000 64.031 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 1000 1000 1000 1000 74.33 1000 1000 30.4141000 1000 1000 1000

34、 1000 1000 25 1000 29.155 1000 1000 10001000 1000 1000 1000 1000 25 1000 1000 1000 1000 1000 100032.016 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 74.33 29.155 1000 1000 1000 36.401 1000 10001000 41.231 1000 1000 1000 1000 1000 1000 36.401 1000 1000 10001000 1000 56.56

35、9 1000 1000 1000 1000 1000 1000 1000 1000 30.4141000 1000 1000 1000 30.414 1000 1000 1000 1000 1000 30.414 1000;%2ͨ·¾ØÕót2=1000 30 1000 1000 1000 1000 1000 32.0156 1000 100030 1000 110 1000 1000 1000 1000 1000 78.7626 10001000 110 1000 1000 1000 1000 1000 10

36、00 1000 45.30761000 1000 1000 1000 1000 1000 1000 1000 1000 28.09231000 1000 1000 1000 1000 1000 1000 1000 65.0612 77.24231000 1000 1000 1000 1000 1000 25 1000 32.1225 10001000 1000 1000 1000 1000 25 1000 1000 1000 100032.016 1000 1000 1000 1000 1000 1000 1000 1000 10001000 78.7626 1000 1000 65.0612 32.1225 1000 1000 1000 10001000 1000 45.3076 28.0923 77.2423 1000 1000 1000 1000 1000;%3ͨ·¾ØÕót3=1000 30 1000 1000 1000 1000 1000 32.0156 1000 1000 100030 1000 110 1000 1000 1000 1000 1000 1000 1000 78.76261