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

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

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

3、的含義是：如果用戶的地址不在障礙區(qū)域內，那么該用戶就是需要使用自來水的用戶（即有效用戶），否則如果用戶的地址在障礙區(qū)域內，那么該用戶就是無效用戶（即不要將該用戶連接在網(wǎng)絡中）。表2-表5是分別是4個障礙區(qū)域必須要覆蓋的點的坐標，而對應障礙區(qū)域就是覆蓋這些要覆蓋的點的最小凸集。(1)請您判定表1中那些用戶為有效用戶。(2)請設計一個算法將有效用戶連接起來，并且連接的距離總和最小。表1若干個可能的用戶的地址的橫縱坐標可能的用戶的序號可能的用戶橫坐標可能的用戶縱坐標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必須要覆蓋的點的坐標頂點序號頂點的橫坐標頂點的縱坐標13.2060 12.9166217.457119.337734.7576 20表3障礙區(qū)域2必須要覆蓋的點的坐標頂點序號頂點的

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

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

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

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

15、在障礙區(qū)內為有效用戶。運用向量的方法求解障礙區(qū)面積S若障礙區(qū)是三角形，對應各頂點坐標分別為(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ū)為五邊形，對應點為(x1,y1)，(x2,y2), (x3,y3), (x4,y4)，(x5,y5)。則劃分成三個三角形，各三角形的頂點分別為(x1,y1)，(x2,y2), (x3,y3)；(x3

16、,y3), (x4,y4)，(x5,y5)；(x1,y1)，(x3,y3), (x5,y5)。再用求三角形面積的方法求解即可。篩選完畢的結果如下：INSIGN = 4 23 36 99n = 96 所以在障礙區(qū)的點的序號分別為：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ū)域任意兩個頂點之間的直線的交點坐標，然后用向量法判斷該交點是否在兩用戶的線段上和障礙區(qū)頂點為端點的線段上，若在，則為無效線段，否則為有效線段。 5.2.1運用矩陣的方法求解兩直線之間的交點坐標 如果任意兩個有效用戶點的坐標分別為A、B，同一障礙區(qū)任意兩個頂點坐標為M、N。則由解線性方程組的方法有，運用Matlab求解該線性方程組=A。5.2.2運用向量法判斷線段是否為有效線段若求得的交點坐標為P(x,y)，則通過向量關系PM=PN

18、,可以求的。若0,則該線段為有效線段；若<0,則要考慮向量關系PA=PB,若0，則該線段為有效線段，否則，該線段為無效線段，生成的矩陣見附錄四，在m矩陣中存儲。5.3利用Prim算法求最小生成樹 學生實力有限，此步驟正凌亂進行中，以下為代碼片段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, :) =