東北大學(xué)數(shù)學(xué)模作業(yè)(抄襲后果自負(fù),僅供參考)

《東北大學(xué)數(shù)學(xué)模作業(yè)(抄襲后果自負(fù),僅供參考)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、自來(lái)水管道連接規(guī)劃模型摘要現(xiàn)代日常生活中，需要通過(guò)自來(lái)水管道將自來(lái)水運(yùn)輸至各個(gè)用戶(hù)處，本文主要分析討論自來(lái)水管道連接規(guī)劃問(wèn)題，即在自來(lái)水管道鋪設(shè)過(guò)程中在繞開(kāi)障礙物的前提下的最優(yōu)路徑且自來(lái)水管道中各個(gè)供水點(diǎn)及用戶(hù)以最短路徑連接的問(wèn)題。排除障礙區(qū)域：面積分析法即在二維坐標(biāo)系上標(biāo)定各點(diǎn)，障礙區(qū)域用由陰影覆蓋的凸多邊形表出，通過(guò)對(duì)點(diǎn)坐標(biāo)之間的向量運(yùn)算判定各點(diǎn)是否位于陰影區(qū)域。最優(yōu)路徑規(guī)劃：通過(guò)Prim算法計(jì)算最小生成樹(shù)，得出最優(yōu)連接方案（prim算法：在圖G=(V,E)（V表示頂點(diǎn)，E表示邊）中，從集合V中任取一個(gè)頂點(diǎn)（例如取

2、頂點(diǎn)v0）放入集合U中，這時(shí)U={v0}，集合T(E)為空。2.從v0出發(fā)尋找與U中頂點(diǎn)相鄰（另一頂點(diǎn)在V中）權(quán)值最小的邊的另一頂點(diǎn)v1，并使v1加入U(xiǎn)。即U={v0,v1}，同時(shí)將該邊加入集合T(E)中。3.重復(fù)2，直到U=V為止。這時(shí)T(E)中有n-1條邊，T=(U,T(E))就是一棵最小生成樹(shù)）。關(guān)鍵詞：管道連接面積法障礙點(diǎn)篩選Prim算法最小生成樹(shù)一．問(wèn)題重述自來(lái)水是人們?nèi)粘Ｉ钪胁豢扇鄙俚纳钜?，然而自?lái)水管網(wǎng)的組建卻有很多問(wèn)題需要解決。一般來(lái)說(shuō)，我們假設(shè)管網(wǎng)中任意兩個(gè)用戶(hù)之間存在直線段相連，但是在連接過(guò)程

3、中，有些區(qū)域是必須繞開(kāi)的，這些必須繞開(kāi)的區(qū)域我們稱(chēng)為障礙區(qū)域。表1給出了若干個(gè)可能的用戶(hù)的地址的橫縱坐標(biāo)，可能的用戶(hù)的含義是：如果用戶(hù)的地址不在障礙區(qū)域內(nèi)，那么該用戶(hù)就是需要使用自來(lái)水的用戶(hù)（即有效用戶(hù)），否則如果用戶(hù)的地址在障礙區(qū)域內(nèi)，那么該用戶(hù)就是無(wú)效用戶(hù)（即不要將該用戶(hù)連接在網(wǎng)絡(luò)中）。表2-表5是分別是4個(gè)障礙區(qū)域必須要覆蓋的點(diǎn)的坐標(biāo)，而對(duì)應(yīng)障礙區(qū)域就是覆蓋這些要覆蓋的點(diǎn)的最小凸集。(1)請(qǐng)您判定表1中那些用戶(hù)為有效用戶(hù)。(2)請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法將有效用戶(hù)連接起來(lái)，并且連接的距離總和最小。表1若干個(gè)可能的用戶(hù)的地址的

4、橫縱坐標(biāo)可能的用戶(hù)的序號(hào)可能的用戶(hù)橫坐標(biāo)可能的用戶(hù)縱坐標(biāo)1.000095.012958.27922.000023.113942.34963.000060.684351.55124.000048.598233.39515.000089.129943.29076.000076.209722.59507.000045.646857.98078.00001.850476.03659.000082.140752.982310.000044.470364.052611.000061.543220.906912.000079.193

5、737.981813.000092.181378.332914.000073.820768.084615.000017.626646.109516.000040.570656.782917.000093.547079.421118.000091.69045.918319.000041.027060.286920.000089.36505.026921.00005.789141.537522.000035.286830.499923.000081.316687.436724.00000.98611.500925.0000

6、13.889176.795026.000020.276597.084527.000019.872299.008328.000060.379278.886229.000027.218843.865930.000019.881449.831131.00001.527421.396332.000074.678664.349233.000044.509632.003634.000093.181596.009935.000046.599472.663236.000041.864941.195337.000084.622174.4

7、56638.000052.515226.794739.000020.264743.992440.000067.213793.338041.000083.811868.333242.00001.964021.256043.000068.127783.923844.000037.948162.878545.000083.179613.377346.000050.281320.713347.000070.947160.719948.000042.889262.988849.000030.461737.047750.00001

8、8.965457.514851.000019.343145.142552.000068.22234.389553.000030.27642.718554.000054.167431.268555.000015.08731.286356.000069.789838.396757.000037.837368.311658.000086