建模學(xué)習(xí)講座基于圖論的公園道路設(shè)計(jì)方案

公園內(nèi)的道路進(jìn)行設(shè)計(jì)，這樣有利于改善學(xué)校環(huán)境，同時(shí)為學(xué)校節(jié)約大量（0修道路的最短總路394.55968m。：模型二點(diǎn)最小樹(shù)距離的逐步調(diào)優(yōu)法。我們?cè)跊](méi)有確定交叉點(diǎn)的情況下，利用避圈法求出8個(gè)正則點(diǎn)的最小樹(shù)，通過(guò)在公園矩形內(nèi)增加6個(gè)輔助點(diǎn)來(lái)大致確定交叉點(diǎn)的位置再采用最小樹(shù)的逐步調(diào)優(yōu)法來(lái)逐步確定交叉點(diǎn)的G（65.94,71.59，H（168.96,40.25（117.26，87.72，357.6918m。：R2,R4R2(140,45),358.946m：最小生成樹(shù)逐步調(diào)優(yōu)法一、問(wèn)題重長(zhǎng)度和最小，前提要求是任意的兩個(gè)之間的最短道路長(zhǎng)不大于兩點(diǎn)連線1.4100米，1至8各的坐標(biāo)分別為P5(120,100),P6(35,100),P7(10,100),P8(0,25C(120,40)，D(115,70的邊，示意圖見(jiàn)圖3。重復(fù)完成問(wèn)題二的任務(wù)。其中矩形的湖為R1(140,70),R2(140,45),R3=(165,45),R4=(165,70

二、問(wèn)題假設(shè)和符號(hào)假設(shè)每個(gè)都可以看成是一個(gè)點(diǎn) 交叉xA,xB,xC,

A,B,C,DyA,yB,yC,

A,B,C,D三、問(wèn)題分（道路不計(jì)入總長(zhǎng)，并且要求滿足任意的兩個(gè)之間的最短道路長(zhǎng)不大于兩點(diǎn)1.4法，用編程畫(huà)出最小生成樹(shù)。再在考慮公園四周的道路不計(jì)入總長(zhǎng)（0的路程選擇滿足任意的兩個(gè)之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4倍算最后確定的方案的總路程，并畫(huà)出設(shè)計(jì)圖。公園內(nèi)總路程最短。我們首先利用避圈法求出8個(gè)正則點(diǎn)的最小樹(shù)，通過(guò)在公園矩形內(nèi)增加6個(gè)輔助點(diǎn)來(lái)確定交叉點(diǎn)的位置再采用最小樹(shù)的逐步調(diào)優(yōu)[2]來(lái)逐步確定交叉點(diǎn)的位置，找出最短總路程。最后，在滿足任意的兩個(gè)間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4倍的道路的條件下，進(jìn)行手動(dòng)修正，畫(huà)出四、模型建立與求基于避圈法[1]的公園里道路的最短總路生（2通過(guò)編程畫(huà)出公園內(nèi)部最小生成樹(shù)如圖ADB1則在考慮公園四周的道路計(jì)入總長(zhǎng)的情況下，公園內(nèi)部最短路道路為0),則公園內(nèi)部的最短路385.4214m。但是題目要求任意的兩個(gè)之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4P1P5P2P5ADB2394.55968m。基于點(diǎn)最小樹(shù)距離的逐步調(diào)優(yōu)（1）點(diǎn)的坐標(biāo)計(jì)算點(diǎn)的定義[3：要在ABCF,F形的三頂點(diǎn)的距離之和最小，則稱F點(diǎn)為點(diǎn)。xBxBxC，可得如下結(jié)論，證明見(jiàn)文獻(xiàn)[4]EEADFBC圖 點(diǎn)的幾何作當(dāng)點(diǎn)A段BC之上方，即

y(xAxByCyB) xxxAxB

3(2

AyB)

yE

yAyB2

32

AxB

xxAxC

3(2

AyC)

yyAyC

32

AxC

當(dāng)點(diǎn)A段BC之下方，即

y(xAxByCyB)x xC BCBxxAxB

3(

yB)

yE

yAyB2

3

xB

xxAxC

(2

AyC)

yyAyC

32

AxC

x然后求線段CE與BD的交點(diǎn)就得點(diǎn)F的坐標(biāo)。若分別用kCE與kBDxCEBD

yCyE,

yB

則易求 點(diǎn)F的坐

xC

B

x(kBDxByB)(kCExCyC

，yy (xx

kFk

利用（6）（2）樹(shù)的性質(zhì)1、樹(shù)上任何一個(gè)頂點(diǎn)v的度至多是3，即d(v)32、樹(shù)上每個(gè)輔助點(diǎn)都是點(diǎn)3、若樹(shù)的正則點(diǎn)共有n個(gè)，則點(diǎn)的數(shù)目至多是n-2個(gè)4、樹(shù)的每個(gè)點(diǎn)都必定包含在全部正則點(diǎn)的最小凸包內(nèi)5、樹(shù)的每個(gè)1度點(diǎn)都是正則點(diǎn)1Z的最小生成樹(shù)T0 圖4公園的8個(gè)所構(gòu)成的最小生成2、依次讓k16，在矩形R[0,200[0,100]內(nèi)隨機(jī)投放kFF,然后用避圈法計(jì)算出F

Tk3

1Sk1

nSj

(k1,2,,n

kkqkPi,(k1,2,,ni4、產(chǎn)生一個(gè)[0,1]均勻分布的隨機(jī)數(shù)r，若滿足qk1rqk，則對(duì)Tk的要好，則替換它，否則Tk不變。5重復(fù)步驟3和4，直到達(dá)到預(yù)設(shè)的最大迭代次數(shù)為止此時(shí)的最好解記為T(mén)6、統(tǒng)計(jì)T中各輔助點(diǎn)的度7T12邊。若有3度輔助點(diǎn)，一般它不是點(diǎn)，需要校正，調(diào)整后得到新的T。0867，10TT，則輸出T0出T0經(jīng)過(guò)編程，得到在沒(méi)有給出交叉點(diǎn)的情況下公園內(nèi)總路程最短5（168.96,40.25（117.2687.72路357.6918m。6圖66K-HK-H計(jì)。若借助湖邊的道路來(lái)使K到達(dá)H，由假設(shè)若沿湖建路，則所修道路的長(zhǎng)度要計(jì)入路程總長(zhǎng)，故需四條直線才使K到達(dá)H，不符合兩點(diǎn)之間直線最短，故考慮R4、R2KH，K、HR45K-R4-HG-K-5R4-K-5G-5-R4的坐標(biāo)為(x4,y4在△P4P3R4H-R4H-4、H-3d(x4min(x40

LINGO（8）H(184.09,48.95)所連之后的任意兩之間的最短道路長(zhǎng)全滿足不大于兩連線點(diǎn)之間的1.4361.4300m7圖7R4R25，K-R2-HG-K-5、R2-K-5G-5-的距離近似相等，故可將K5H點(diǎn)的坐標(biāo)為(x5y5，可以利用模型一的方法在△P4P3R2(x160)2(x160)2y555x34y38004x37y3115014x3y32240

(x(x200)2(50y55(x140)2(45y55圖8R2M

(x6y6。GH進(jìn)行確定，設(shè)調(diào)整后的GH(x7y7

(x8,y8

進(jìn)方案，建立非線性規(guī)劃模型，然后根 日原理建立出如下等式(xx)2(xx)2(yy (x50)2y77(x(x200)2(50y88(x140)2(45y66(x(x120)2(y66(x35)2(y77(x(x160)2y88(x35)2(y77

利用LINGOM,G,H(69.07,63.96)G，(112.32,74.27)M,(161.75,30.73)H99在圖9不存在三角形可繼續(xù)優(yōu)化在此方案下最短路程長(zhǎng)為358.946。經(jīng)過(guò)比較最短路程長(zhǎng)，最終選擇模型二作為最后方案，四個(gè)交叉點(diǎn)分別為(69.07,63.96)G,(112.32,74.27)M,(161.75,30.73)H,2(140,45)R，總路程長(zhǎng)358.946m。

五、模型評(píng)價(jià)與推1Kruskal2、在模型二中采用點(diǎn)的擴(kuò)展點(diǎn)，優(yōu)化解決問(wèn)題的方式，應(yīng)用逐步倉(cāng)庫(kù)、急救中心、消防站、處理中心、物流中心、倉(cāng)庫(kù)的選址等。2、最小生成樹(shù)可以網(wǎng)絡(luò)設(shè)計(jì)，城市高速公路，電子線路設(shè)計(jì)應(yīng)用六、參考文[1]，建模的數(shù)學(xué)方法和數(shù)學(xué)模型..科學(xué)[2]，，，.求解歐氏距離最小樹(shù)的逐步調(diào)優(yōu)法.2011.年青年通信國(guó)際會(huì)議（ICY2011） [3].數(shù)學(xué)模型 高等教育.2004,5:46-[4]，關(guān)于點(diǎn)的幾點(diǎn)注解[J].華南理工大學(xué)學(xué)報(bào)，2004,32（193-七、附第一問(wèn)生成最小生成樹(shù)的程序functionx=[20 1005040120y=[0005010010010025754040fori=1:nfor%KruskalM-格式 頂點(diǎn)Wt為最小生成樹(shù)的權(quán),Pp(:,1:2)為最小生成樹(shù)邊的兩頂點(diǎn)%Pp(:,3)為最小生成樹(shù)的邊權(quán),Pp(:,4)為最小生成樹(shù)邊的序號(hào)%%%%%%Byqinyuanw=W(tmpa);e=[tmpb,tmpc];%wWinf元素按列構(gòu)成的向量[nE,mE]=size(E);%sort數(shù)組排列while(rank(E)>0)forif(E(i,1)==temp1),E(i,1)=temp2;if(E(i,2)==temp1),E(i,2)=temp2;end;iffori=1:length(P(:,3));%viejdisp(['','e',num2str(P(i,4(v',...num2str(P(i,1)),'','v',num2str(P(i,2)),')']);axisequal;holdon[x,y]=cylinder(1,n);xm=min(x(1,:));ym=min(y(1,:));xx=max(x(1,:));yy=max(y(1,:));yy+abs(yy)*0.15]);plot(x(1,:),y(1,:),'ko')fori=1:n;temp=['text(x(1,i),y(1,i),temp);fori=1:nE;plot(x(1,e(i,:)),y(1,e(i,:)),'b');end;fori=1:length(P(:,4));text(-0.