基于Floyd算法的道路優(yōu)化設(shè)計問題

1、-. z.- - - z -數(shù)學(xué)建模基于Floyd算法的公園道路優(yōu)化設(shè)計問題 小組編號： 02 小組成員：隊員1 聰-建模隊員2 汪 濤-建模隊員3胡 娜-建模隊員4 薛向龍-建模 隊員5蔡詩聶-編程 隊員6 志誠-編程 2012年 7月 21日 基于Floyd算法的公園道路優(yōu)化設(shè)計問題摘要本文主要研究了以公園部道路修建為背景的路徑優(yōu)化問題。對于問題一，四個穿插點(diǎn)的情況下，考慮到邊緣道路不計入修建道路總長的題目要求和最短道路長不大于兩點(diǎn)連線1.4倍前提要求，首選邊緣路徑，將那些無需借助穿插點(diǎn)即可滿足1.4倍前提要求的點(diǎn)從考慮圍剔除。然后對剩余不滿足條件的路徑運(yùn)用Kruskal算法，生成最小生成

2、樹的路徑，再在此根底上，利用Floyd算法，找出其中不符合1.4倍約束的路徑的邊，綜合對其路徑進(jìn)展調(diào)整并將滿足條件的所有路徑的邊用窮舉法進(jìn)展篩選，最終選取最優(yōu)路徑，其總路程為393。對于問題二，我們在第一問結(jié)果上進(jìn)展改良，運(yùn)用兩點(diǎn)之間線段最短原理將第一問最短路徑進(jìn)展優(yōu)化，然后引入費(fèi)馬點(diǎn)定義，通過數(shù)理計算分析，劃分三角形區(qū)域，建立非線性規(guī)劃模型進(jìn)展局部優(yōu)化。遞增穿插點(diǎn)的個數(shù)，并在前一個穿插點(diǎn)的最優(yōu)路徑的根底上對后一個穿插點(diǎn)的取點(diǎn)圍進(jìn)展考量，用lingo對不同數(shù)目穿插點(diǎn)的情況下的最短路徑目標(biāo)函數(shù)進(jìn)展規(guī)劃，并以1.4倍的數(shù)學(xué)關(guān)系作為約束條件，進(jìn)展局部最優(yōu)解逼近全局最優(yōu)解，最終確定最優(yōu)穿插點(diǎn)個數(shù)為3個

3、，坐標(biāo)分別為、，計算出最短路徑。對于問題三，我們在比照道路穿過湖的情況下，考慮到湖邊的修路計算到總路程的情況，分析得到在以湖的頂點(diǎn)R2、R4為道路穿插點(diǎn)時比以湖邊其他點(diǎn)作為穿插點(diǎn)時的路徑要短，所以分別以湖的頂點(diǎn)R2、R4為道路穿插點(diǎn)時進(jìn)展討論，在問題二的最短路徑的根底上建立非線性規(guī)劃模型，然后利用費(fèi)馬點(diǎn)逐步進(jìn)展優(yōu)化，比擬兩種不同穿插點(diǎn)的優(yōu)化模型情況，最終確定出最優(yōu)方案下的四個穿插點(diǎn)的坐標(biāo)分別,，計算出該情況下最優(yōu)路程長為。關(guān)于模型的優(yōu)化，對于問題二，我們考慮到可以通過蒙特卡洛的方法對公園矩形區(qū)域圍進(jìn)展撒點(diǎn)，并借用橢圓法來約束1.4倍的條件關(guān)系，此方法可以求出選擇不同數(shù)目穿插點(diǎn)時的最優(yōu)路徑，結(jié)果

4、更準(zhǔn)確，但是計算量大、程序運(yùn)行緩慢。關(guān)鍵詞： Kruskal算法 Floyd算法局部優(yōu)化 費(fèi)馬點(diǎn) 非線性規(guī)劃 一、問題重述為了美化校園環(huán)境，同時為學(xué)生提供更好的生活條件，*大學(xué)方案建一個形狀為矩形或其他不規(guī)則圖形的公園。該公園方案有假設(shè)干個入口，讓任意兩個入口相連且任意的兩個入口之間的最短道路長不大于兩點(diǎn)連線的1.4倍。路線的選擇可以利用公園四周的邊，即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計入道路總長。矩形公園相關(guān)數(shù)據(jù)為：長200米，寬100米，1至8各入口的坐標(biāo)分別為：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,

5、100),P7(10,100),P8(0,25)。圖1 公園及入口示意圖我們的任務(wù)就是結(jié)合該公園已有的方案，對其進(jìn)展合理的道路安排，建立相應(yīng)的數(shù)學(xué)模型，解決以下問題：1、在公園假定要使用A(50,75)，B(40,40)，C(120,40)，D(115,70這4個點(diǎn)作為道路穿插點(diǎn)時，如何設(shè)計出新的道路在滿足1.4倍要求的前提下使公園道路總路程最短。2、在公園可以任意修建道路的情況下，如何確定穿插點(diǎn)的個數(shù)及坐標(biāo)設(shè)計道路使其在滿足1.4倍條件下使總路程最少。3、在公園有一條矩形的湖的，新修的道路不能通過，但可以到達(dá)湖四周的邊的前提下，如何設(shè)計穿插點(diǎn)的個數(shù)及坐標(biāo)設(shè)計道路使其在滿足1.4倍條件下使總路

6、程最少。注：以上問題中都要求公園新修的道路與四周的連接只能與8個路口相通，而不能連到四周的其它點(diǎn)。圖2 有湖的示意圖二、問題分析此題是一個道路設(shè)計的最優(yōu)化的問題，即是如何設(shè)計路徑使公園部新修路總長最小，但要滿足以下兩個控制條件：1、任意兩個入口連通；2、任意兩個入口的最短路徑不超過其直線距離的1.4倍。對于問題一，題中已給出A(50,75)，B(40,40)，C(120,40)，D(115,70這4個點(diǎn)作為道路穿插點(diǎn)，由于題設(shè)中說明公園四周存在修好的道路且允許通行，所以我們先利用四周道路，找出，這些沿邊道路不能滿足1.4倍關(guān)系的路徑。然后對剩余不滿足第2個控制條件的路徑運(yùn)用Kruskal算法，

7、生成最小生成樹，再在此根底上，利用Floyd算法，找出其中不符合條件2的路徑用窮舉法進(jìn)展優(yōu)化。對于問題二，我們在第一問結(jié)果上進(jìn)展改良，考慮到兩點(diǎn)之間線段最短原理我們將與、與直接相連。引入費(fèi)馬點(diǎn)定義，通過分析劃分三角形區(qū)域，建立非線性規(guī)劃模型進(jìn)展局部優(yōu)化。假設(shè)公園有m個穿插點(diǎn)，從m=0開場，我們繼續(xù)討論m=1、m=2和m=3這三種情況，進(jìn)展局部最優(yōu)解逼近全局最優(yōu)解，最終確定穿插點(diǎn)數(shù)及坐標(biāo)并求解出最短路徑。對于問題三，首先考慮問題二中設(shè)計的道路是否不通過矩形湖，假設(shè)不通過，則問題二的結(jié)果即為問題三的結(jié)果；否則，對問題二方案中穿過湖的道路進(jìn)展調(diào)整將其調(diào)整為穿過湖的頂點(diǎn)。利用費(fèi)馬點(diǎn)到三個頂點(diǎn)的距離最短

8、，建立出相應(yīng)的非線性規(guī)劃模型，求出相應(yīng)的穿插點(diǎn)，然后再利用費(fèi)馬點(diǎn)來進(jìn)展優(yōu)化，直到不能再優(yōu)化為止，最終可得到最優(yōu)方案。三、模型假設(shè)1、假設(shè)所有點(diǎn)間道路均修建為直線，且都在同一水平面；2、假設(shè)入口形狀與路寬忽略不計，即將入口抽象為點(diǎn)，道路抽象為線；3、假設(shè)穿插點(diǎn)位置的選取不受地理位置的限制，且穿插點(diǎn)的修建不會影響道路的總長4、假設(shè)湖的四周沒有修建好的道路，假設(shè)要沿湖則同樣需修建道路并計入道路總長。四、符號說明符號說明點(diǎn)的坐標(biāo)點(diǎn)、間的距離點(diǎn)與點(diǎn)間的距離、道路穿插點(diǎn)最優(yōu)路線長度道路穿插點(diǎn)的個數(shù)五、模型的建立與求解5.1問題一的模型建立與求解由題所給出的條件可以看出，這與最短路問題聯(lián)系密切，于是考慮用K

9、ruskal算法和Floyd算法來建立問題的模型。圖3、模型一流程圖Kruskal算法描述：kruskal算法每次選擇n- 1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會產(chǎn)生環(huán)路的具有最小消耗的邊參加已選擇的邊的集合中。注意到所選取的邊假設(shè)產(chǎn)生環(huán)路則不可能形成一棵生成樹。kruskal算法分e 步，其中e 是網(wǎng)絡(luò)中邊的數(shù)目。按消耗遞增的順序來考慮這e 條邊，每次考慮一條邊。當(dāng)考慮*條邊時，假設(shè)將其參加到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。算法步驟:1在公園的矩形區(qū)域的12個點(diǎn)中, 利用勾股定理算出任意兩點(diǎn)所構(gòu)成的各邊的權(quán)值。2逐步比擬各邊的權(quán)值，依次選出構(gòu)成權(quán)值最小的邊

10、的兩個點(diǎn)構(gòu)成連線，與此同時，利用邊與邊之間不能構(gòu)成連線的條件，對權(quán)值盡可能小的邊逐步篩選。3根據(jù)選出的邊逐步構(gòu)成連線，生成無圈的最小樹。 Floyd算法描述：1從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑有2種可能，1是直接從A到B，2是從A經(jīng)過假設(shè)干個節(jié)點(diǎn)*到B。2假設(shè)Dis(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對于每一個節(jié)點(diǎn)*，檢查Dis(A*) + Dis(*B) *(1,j) a=*(1,i);*(1,i)=*(1,j);*(1,j)=a; a=*(2,i);*(2,i)=*(2,j);*(2,j)=a; a=*(3,i);*(3,i)=*(3,j);*(3,j)=a; endendend%

11、給各點(diǎn)標(biāo)號賦初值for i=1:nl(i)=i;end%初始時選e1參加集合EE(1,1)=*(1,1); %E矩陣的第一行記錄最小生成樹的邊長E(2,1)=*(2,1); %E矩陣的第二行記錄邊的起點(diǎn)E(3,1)=*(3,1); %E矩陣的第三行記錄邊的終點(diǎn)a=min(l(E(2,1),l(E(3,1);l(E(2,1)=a;l(E(3,1)=a;b=1;%記錄E中邊數(shù)for i=2:k if b=n-1 %如果樹中邊數(shù)到達(dá)n-1 break %算法終止 endif l(*(2,i)=l(*(3,i) %如果兩頂點(diǎn)標(biāo)號不同 b=b+1; %將這條邊參加E E(1,b)=*(1,i); E(2

12、,b)=*(2,i); E(3,b)=*(3,i);for j=1:n %對于所有頂點(diǎn) if l(j)=ma*(l(E(2,b),l(E(3,b)%如果該頂點(diǎn)的標(biāo)號,等于=,新參加邊中的頂點(diǎn)標(biāo)號較大的值 l(j)=min(l(E(2,b),l(E(3,b);%將其改為較小的那一個以避圈 endendendend附錄3：問題一中Floyd算法程序：clc; n=12; a=zeros(n); a(1,2)=30;a(1,8)=32;a(1,2)=30;a(1,3)=140;a(2,10)=41;a(2,3)=100;a(3,4)=64;a(3,11)=57;a(5,6)=85;a(5,12)=3

13、0;a(6,7)=25;a(6,9)=29;a(9,10)=36;a(9,12)=65;a(11,12)=30;a(1,4)=230;a(1,5)=240;a(1,6)=155;a(1,7)=130;a(2,4)=200;a(2,5)=270;a(2,6)=185;a(2,7)=160;a(2,8)=70;a(3,5)=120;a(3,6)=295;a(3,7)=270;a(3,8)=180;a(4,5)=130;a(4,6)=215;a(4,7)=240;a(4,8)=270;a(5,8)=200;a(6,8)=115;a(7,8)=90;a=a+a; M=ma*(ma*(a)*n2; %M

14、為充分大的正實數(shù) a=a+(a=0)-eye(n)*M; path=zeros(n); for k=1:n for i=1:n for j=1:n if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; endendendenda, path 附錄4:問題二中1個穿插點(diǎn)情況時的lingo程序:min=sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+sqrt(*9-120)2+(y9-100)2)+16.0078*2+53.85165*2+32.01562*2;sqrt(*9-50)2+(y9)2

15、)+sqrt(*9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)=1.4*61.03278*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+30=0;-10*9+7*y9+500=0;y9=0;y9=

16、100;附錄5:問題二中2個穿插點(diǎn)情況時的lingo程序:min=sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+sqrt(*9-120)2+(y9-100)2)+sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y10-50)2)+sqrt(*10-120)2+(y10-100)2)+16.0078*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)=1.4*61.0

17、3278*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+30=1.4*50.55937*2;sqrt(*10-160)2+(y10)2)+sqrt(*10-120)2+(y10-100)2)=1.4*53.85165*2;sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y1

18、0-50)2)=0;-10*9+7*y9+500=0;5*10-4*y10-800=0;5*10+8*y10-1400=0;y9=0;y10=100;附錄6:問題二中3個穿插點(diǎn)情況時的lingo程序:min=sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y10-50)2)+sqrt(*11-*9)2+(y11-y9)2)+sqrt(*11-120)2+(y11-100)2)+sqrt(*11-*10)2+(y11-y10)2)+16.0078*2;sqrt(*9-50)2+(

19、y9)2)+sqrt(*9-35)2+(y9-100)2)=1.4*50.55937*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)=1.4*61.03278*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+25=1.4*53.85165*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-120)2+(y9-100)2)+30=1.4*70.71068*2;sqrt(*9-50)2+(y9)2)+sqrt(*9-35)2+(y9-100)2)+30=1.4*50.55937*2;sqrt(*10

20、-160)2+(y10)2)+sqrt(*10-120)2+(y10-100)2)=1.4*53.85165*2;sqrt(*10-160)2+(y10)2)+sqrt(*10-200)2+(y10-50)2)=1.4*32.01562*2;sqrt(*9-50)2+(y9)2)+sqrt(*11-*9)2+(y11-y9)2)+sqrt(*11-120)2+(y11-100)2)=1.4*61.03278*2;sqrt(160-*10)2+(0-y10)2)+sqrt(*10-*9)2+(y10-y9)2)+sqrt(35-*9)2+(100-y9)2)=1.4*80.03905*2;30+

21、sqrt(*9-50)2+(y9)2)+sqrt(*11-*9)2+(y11-y9)2)+sqrt(*11-120)2+(y11-100)2)=1.4*70.71068*2;sqrt(*10-160)2+(y10)2)+sqrt(*11-*10)2+(y11-y10)2)+sqrt(*11-120)2+(y11-100)2)+110=1.4*90.13878*2;sqrt(*10-160)2+(y10)2)+sqrt(*11-*10)2+(y11-y10)2)+sqrt(*11-120)2+(y11-100)2)=0;-10*9+7*y9+500=0;5*10-4*y10-800=0;5*10

22、+8*y10-1400=0;y9=0;y10=0;*11=0;y11=100;附錄7:問題三對過R4路徑的求解程序:min=sqrt(*12-165)2+(y12-70)2)+sqrt(*12-160)2+(y12-0)2)+sqrt(*12-200)2+(y12-50)2);sqrt(*12-160)2+(y12)2)+sqrt(*12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2)=1.4*107.7033;sqrt(*12-160)2+(y12)2)+sqrt(*12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2

23、)+85=1.4*160.07981;sqrt(*12-160)2+(y12)2)+sqrt(*12-165)2+(y12-70)2)+sqrt(120-165)2+(100-70)2)+110=1.4*180.2776;sqrt(*12-160)2+(y12)2)+sqrt(*12-200)2+(y12-50)2)=0;*12=0;y12=100; 附錄8:問題三對過R2路徑的求解程序:min=sqrt(*12-160)2+(y12)2)+sqrt(*12-200)2+(y12-50)2)+sqrt(*12-140)2+(y12-45)2)+sqrt(*13-61.69650)2+(y13-71.75212)2)+sqrt(*13-120)2+(y13-100)2)+sqrt(*13-140)2+(y13-45