自來水管道規(guī)劃模型 數(shù)學(xué)建模

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

2、 2. 從v0出發(fā)尋找與U中頂點(diǎn)相鄰（另一頂點(diǎn)在V中）權(quán)值最小的邊的另一頂點(diǎn)v1，并使v1加入U。即U=v0,v1 ，同時將該邊加入集合T(E)中。 3. 重復(fù)2，直到U=V為止。 這時T(E)中有n-1條邊，T = (U, T(E)就是一棵最小生成樹）。關(guān)鍵詞：管道連接 面積法 障礙點(diǎn)篩選 Prim算法 最小生成樹 一問題重述自來水是人們?nèi)粘Ｉ钪胁豢扇鄙俚纳钜?，然而自來水管網(wǎng)的組建卻有很多問題需要解決。一般來說，我們假設(shè)管網(wǎng)中任意兩個用戶之間存在直線段相連，但是在連接過程中，有些區(qū)域是必須繞開的，這些必須繞開的區(qū)域我們稱為障礙區(qū)域。表1給出了若干個可能的用戶的地址的橫縱坐標(biāo)，可能的用戶

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

4、.598233.39515.000089.129943.29076.000076.209722.59507.000045.646857.98078.00001.850476.03659.000082.140752.982310.000044.470364.052611.000061.543220.906912.000079.193737.981813.000092.181378.332914.000073.820768.084615.000017.626646.109516.000040.570656.782917.000093.547079.421118.000091.69045.91831

5、9.000041.027060.286920.000089.36505.026921.00005.789141.537522.000035.286830.499923.000081.316687.436724.00000.98611.500925.000013.889176.795026.000020.276597.084527.000019.872299.008328.000060.379278.886229.000027.218843.865930.000019.881449.831131.00001.527421.396332.000074.678664.349233.000044.50

6、9632.003634.000093.181596.009935.000046.599472.663236.000041.864941.195337.000084.622174.456638.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.71

7、9948.000042.889262.988849.000030.461737.047750.000018.965457.514851.000019.343145.142552.000068.22234.389553.000030.27642.718554.000054.167431.268555.000015.08731.286356.000069.789838.396757.000037.837368.311658.000086.00129.284259.000085.36553.533860.000059.356361.239561.000049.655260.854062.000089

8、.97691.576063.000082.16291.635564.000064.491019.007565.000081.797458.691866.000066.02285.758167.000034.197136.756868.000028.972663.145169.000034.119471.763470.000053.407969.266971.000072.71138.407972.000030.929045.435573.000083.849644.182874.000056.807235.325075.000037.041415.360676.000070.274067.56

9、4577.000054.657169.921378.000044.488072.750979.000069.456747.838480.000062.131055.484281.000079.482112.104782.000095.684345.075483.000052.259071.588384.000088.014289.284285.000017.295627.310286.000097.974725.476987.000027.144786.560388.000025.232923.235089.000087.574280.487290.000073.730690.839891.0

10、00013.651923.189492.00001.175723.931393.000089.38984.975494.000019.91387.838495.000029.872364.081596.000066.144319.088797.000028.440984.386998.000046.922417.390099.00006.478117.0793100.000098.833599.4295表2障礙區(qū)域1必須要覆蓋的點(diǎn)的坐標(biāo)頂點(diǎn)序號頂點(diǎn)的橫坐標(biāo)頂點(diǎn)的縱坐標(biāo)13.2060 12.9166217.457119.337734.7576 20表3障礙區(qū)域2必須要覆蓋的點(diǎn)的坐標(biāo)頂點(diǎn)序號頂點(diǎn)的

11、橫坐標(biāo)頂點(diǎn)的縱坐標(biāo)150 30253.746548.4490346.922257.1195433.320739.8050543.112356.3187表4障礙區(qū)域3必須要覆蓋的點(diǎn)的坐標(biāo)頂點(diǎn)序號頂點(diǎn)的橫坐標(biāo)頂點(diǎn)的縱坐標(biāo)154.698270253.746590346.922280表5障礙區(qū)域4必須要覆蓋的點(diǎn)的坐標(biāo)頂點(diǎn)序號頂點(diǎn)的橫坐標(biāo)頂點(diǎn)的縱坐標(biāo)190752809537080二問題分析建立模型要達(dá)到的目的就是節(jié)省管道，即在滿足每個有效用戶用水的情況下，使得鋪設(shè)的管道最短。因此，自來水的管道問題可以看做是一個最優(yōu)化問題，目標(biāo)函數(shù)是求鋪設(shè)的管道最短。由實(shí)際可知不是每兩個用戶之間都可以用直線相連，必須繞開

12、一些障礙物也就是所謂的障礙區(qū)，所以我們應(yīng)該首先要解決的就是找出這些障礙區(qū)域，然后再判斷所給出的點(diǎn)是否位于障礙區(qū)域內(nèi)，這樣就篩選出了有效用戶。接下來就是要把剩下的點(diǎn)用直線連接起來，通過障礙區(qū)域的線段視為無效線段把其剔除，篩選出有效線段。最后就是計(jì)算出這些有效線段的總和。三模型假設(shè)3.1 基本假設(shè)1. 假設(shè)任意兩個用戶之間均可用直線連接；2. 文中給出所有點(diǎn)的坐標(biāo)值準(zhǔn)確無誤；3. 障礙區(qū)域就是障礙頂點(diǎn)圍成的凸多邊形區(qū)域；4. 有效用戶都能通過自來水管道獲得自來水供應(yīng)；5. 要保證在任意兩點(diǎn)間線段不過障礙區(qū)的情況下，求解連接形成的最短路徑；3.2符號和變量的說明表6 論文符號說明符號含義X記錄100

13、個用戶點(diǎn)的坐標(biāo)信息A障礙區(qū)1的各頂點(diǎn)坐標(biāo)信息B障礙區(qū)2的各頂點(diǎn)坐標(biāo)信息C障礙區(qū)3的各頂點(diǎn)坐標(biāo)信息D障礙區(qū)4的各頂點(diǎn)坐標(biāo)信息SIGN記錄各用戶點(diǎn)是否在障礙區(qū)，若在對應(yīng)位置記為1；若不在，則對應(yīng)位置記為0INSIGN記錄在障礙區(qū)的用戶點(diǎn)的序號n記錄保留用戶點(diǎn)的個數(shù)NUM記錄任意兩用戶點(diǎn)之間可用線段連接起來且不過障礙區(qū)的線段DIS記錄不在障礙區(qū)各用戶點(diǎn)之間可用不過障礙區(qū)線段連接的線段的長度EE記錄生成的最小生成樹的各點(diǎn)及各線段信息sum表示產(chǎn)生的最小生成樹中所有管道的總長四模型建立 5.1.問題一的模型建立問題一是判斷這100個點(diǎn)中哪些點(diǎn)屬于有效點(diǎn)，即有效用戶。首先利用matlab做出這一百個點(diǎn)的相

14、應(yīng)位置的圖，其代碼見附錄三做出此圖，分析可知：要求出哪些用戶為有效用戶，可用面積法對其進(jìn)行篩選。這樣就先得根據(jù)障礙區(qū)域的頂點(diǎn)坐標(biāo)求出每個障礙區(qū)域的面積，然后求出各用戶點(diǎn)與各障礙區(qū)域任意兩個頂點(diǎn)所圍成的三角形面積之和，比較面積，若兩面積相等，則該點(diǎn)在障礙區(qū)域內(nèi)，視為無效點(diǎn)，即無效用戶，否則用戶點(diǎn)不在障礙區(qū)域內(nèi)，為有效用戶。根據(jù)障礙區(qū)的頂點(diǎn)坐標(biāo)，可做出相應(yīng)的圖形，代碼見附錄三，圖如下：五模型求解5.1 篩選有效用戶用面積法確定是否為有效點(diǎn)。面積法的原理：確定各障礙區(qū)的面積以及用戶點(diǎn)與各障礙區(qū)任意兩個定點(diǎn)構(gòu)成的三角形的面積之和，比較上面兩個面積，若相等，則該用戶點(diǎn)在障礙區(qū)內(nèi)為無效用戶，否則，用戶點(diǎn)不

15、在障礙區(qū)內(nèi)為有效用戶。運(yùn)用向量的方法求解障礙區(qū)面積S若障礙區(qū)是三角形，對應(yīng)各頂點(diǎn)坐標(biāo)分別為(x1,y1)，(x2,y2), (x3,y3)。則a=(x2-x1,y2-y1),b=(x3-x1,y3-y1)。由于三角形面積S=|a|*|b|*sin<a,b>/2,向量a,b外積的模長|a×b|=|a|*|b|*sin<a,b>則有S=|a×b|/2;若障礙區(qū)為五邊形，對應(yīng)點(diǎn)為(x1,y1)，(x2,y2), (x3,y3), (x4,y4)，(x5,y5)。則劃分成三個三角形，各三角形的頂點(diǎn)分別為(x1,y1)，(x2,y2), (x3,y3)；(x3

16、,y3), (x4,y4)，(x5,y5)；(x1,y1)，(x3,y3), (x5,y5)。再用求三角形面積的方法求解即可。篩選完畢的結(jié)果如下：INSIGN = 4 23 36 99n = 96 所以在障礙區(qū)的點(diǎn)的序號分別為：4 23 36 99。 無效用戶的信息為：(4.0000,48.5982,33.3951);(23.0000,81.3166,87.4367); (36.0000,41.8649,41.1953); (99.0000,6.4781,17.0793);有效用戶的個數(shù)是：96。5.2有效線段的篩選 已篩選出有效用戶，就要求出有效用戶之間以最短的線段線段相連，但是這些線段必須

17、是有效線段，若兩用戶之間以線段相連了，但是這條線段通過了障礙區(qū)域，此時，這條線段就是無效線段。此時需要篩選出有效線段，首先要求出任意兩個有效用戶之間的直線與過各障礙區(qū)域任意兩個頂點(diǎn)之間的直線的交點(diǎn)坐標(biāo)，然后用向量法判斷該交點(diǎn)是否在兩用戶的線段上和障礙區(qū)頂點(diǎn)為端點(diǎn)的線段上，若在，則為無效線段，否則為有效線段。 5.2.1運(yùn)用矩陣的方法求解兩直線之間的交點(diǎn)坐標(biāo) 如果任意兩個有效用戶點(diǎn)的坐標(biāo)分別為A、B，同一障礙區(qū)任意兩個頂點(diǎn)坐標(biāo)為M、N。則由解線性方程組的方法有，運(yùn)用Matlab求解該線性方程組=A。5.2.2運(yùn)用向量法判斷線段是否為有效線段若求得的交點(diǎn)坐標(biāo)為P(x,y)，則通過向量關(guān)系PM=PN

18、,可以求的。若0,則該線段為有效線段；若<0,則要考慮向量關(guān)系PA=PB,若0，則該線段為有效線段，否則，該線段為無效線段，生成的矩陣見附錄四，在m矩陣中存儲。5.3利用Prim算法求最小生成樹 學(xué)生實(shí)力有限，此步驟正凌亂進(jìn)行中，以下為代碼片段function MST = Prim_algo(G)N = length(G); MST = ; k = 0;vis = zeros(1, N); vis(1) = 1; while k < N-1 minw = inf; u = 0; v = 0; for i = 1 : N for j = 1 : N if vis(i) = 1 && vis(j) = 0 if G(i, j) < minw minw = G(i, j); u = i; v = j; end end end % for j end % for i vis(v) = 1; k = k+1; MST(k, :) =