自來(lái)水管道連接規(guī)劃模型

1、數(shù)學(xué)建模作業(yè)：自來(lái)水管道連接規(guī)劃模型自來(lái)水管道連接規(guī)劃模型【摘要】：生活中需要通過(guò)自來(lái)水管道將自來(lái)水運(yùn)輸至各個(gè)用戶處，本文分析討論自來(lái)水管道連接規(guī)劃問(wèn)題，即在自來(lái)水管道鋪設(shè)過(guò)程中在繞開(kāi)障礙物的前提下的最優(yōu)路徑問(wèn)題，使自來(lái)水管道將各個(gè)供水點(diǎn)用最短路徑鏈接。根據(jù)對(duì)100個(gè)目標(biāo)點(diǎn)的數(shù)據(jù)進(jìn)行篩選與分析，得出在用面積法排除障礙區(qū)域的前提下，對(duì)剩余點(diǎn)采用Kruskal算法生成最優(yōu)路的方案。初始給定的100個(gè)供水點(diǎn)中存在位于障礙區(qū)域中的點(diǎn)，采用合理的方法排除障礙區(qū)域中的點(diǎn)，將對(duì)管道鏈接的效率、能耗、可行性起到?jīng)Q定性作用，是一個(gè)非常實(shí)際的問(wèn)題。本文將采用面積分析的方法，提供一種解決障礙區(qū)域判定的切實(shí)可行的方法

2、，在二維坐標(biāo)系上標(biāo)定各點(diǎn)，障礙區(qū)域用由陰影覆蓋的凸多邊形表出，通過(guò)對(duì)點(diǎn)坐標(biāo)之間的向量運(yùn)算判定各點(diǎn)是否位于陰影區(qū)域，最終通過(guò)MatlabR2010a編程實(shí)現(xiàn)。在確定并剔除障礙區(qū)中的點(diǎn)位后，采用Kruskal閉圈算法生成最優(yōu)路徑，對(duì)于通過(guò)陰影區(qū)域的線段，采用將其權(quán)值設(shè)定為（無(wú)窮大）的處理方法，最終通過(guò)MatlabR2010a編程、繪圖，給出管道最優(yōu)連接方案，解決本問(wèn)題。最后我們對(duì)模型的可行性，合理性，科學(xué)性進(jìn)行了闡述，得到對(duì)模型的整體評(píng)價(jià)以及需改進(jìn)之處?！娟P(guān)鍵詞】：管道連接 面積法 障礙點(diǎn)篩選Kruskal算法 權(quán)值 最小生成樹(shù)一. 問(wèn)題重述自來(lái)水是人們?nèi)粘Ｉ钪胁豢扇鄙俚纳钜?，然而自?lái)水管網(wǎng)

3、的組建卻有很多問(wèn)題需要解決。一般來(lái)說(shuō)，我們假設(shè)管網(wǎng)中任意兩個(gè)用戶之間存在直線段相連，但是在連接過(guò)程中，有些區(qū)域是必須繞開(kāi)的，這些必須繞開(kāi)的區(qū)域我們稱為障礙區(qū)域。表1給出了若干個(gè)可能的用戶的地址的橫縱坐標(biāo)，可能的用戶的含義是：如果用戶的地址不在障礙區(qū)域內(nèi)，那么該用戶就是需要使用自來(lái)水的用戶（即有效用戶），否則如果用戶的地址在障礙區(qū)域內(nèi)，那么該用戶就是無(wú)效用戶（即不要將該用戶連接在網(wǎng)絡(luò)中）。表2-表5是分別是4個(gè)障礙區(qū)域必須要覆蓋的點(diǎn)的坐標(biāo)，而對(duì)應(yīng)障礙區(qū)域就是覆蓋這些要覆蓋的點(diǎn)的最小凸集。(1) 請(qǐng)您判定表1中那些用戶為有效用戶。(2) 請(qǐng)?jiān)O(shè)計(jì)算法篩選有效用戶之間的有效線段。(3)請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法將

4、有效用戶用有效線段連接起來(lái)，并且連接的距離總和最小。表1（見(jiàn)附錄一）表2障礙區(qū)域1必須要覆蓋的點(diǎn)的坐標(biāo)頂點(diǎn)序號(hào)頂點(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)序號(hào)頂點(diǎn)的橫坐標(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)序號(hào)頂點(diǎn)的橫坐標(biāo)頂點(diǎn)的縱坐標(biāo)154.698270253.746590346.922280表5障礙區(qū)域4必須要覆蓋的點(diǎn)的坐標(biāo)頂點(diǎn)序號(hào)頂點(diǎn)的橫坐標(biāo)頂點(diǎn)的縱

5、坐標(biāo)190752809537080二模型假設(shè)1， 假設(shè)任意兩個(gè)用戶之間以直線連接；2， 不在障礙區(qū)中的用戶都通過(guò)自來(lái)水管道獲得自來(lái)水供應(yīng)；3， 以所有管道總距離最小為目的；4， 障礙區(qū)域就是障礙頂點(diǎn)圍成的凸多邊形區(qū)域；5， 文中給出所有點(diǎn)的坐標(biāo)值準(zhǔn)確無(wú)誤；6， 在非障礙區(qū)用戶之間可確保用直線連接；7， 要保證在任意兩點(diǎn)間線段不過(guò)障礙區(qū)的情況下，求解連接形成的最短路徑；三符號(hào)說(shuō)明表6 論文符號(hào)說(shuō)明符號(hào)含義A記錄100個(gè)用戶點(diǎn)的坐標(biāo)信息B障礙區(qū)1的各頂點(diǎn)坐標(biāo)信息C障礙區(qū)2的各頂點(diǎn)坐標(biāo)信息D障礙區(qū)3的各頂點(diǎn)坐標(biāo)信息E障礙區(qū)4的各頂點(diǎn)坐標(biāo)信息SIGN記錄各用戶點(diǎn)是否在障礙區(qū)，若在對(duì)應(yīng)位置記為1；若不在

6、，則對(duì)應(yīng)位置記為0OUTSIGN記錄在障礙區(qū)的用戶點(diǎn)的序號(hào)p記錄保留用戶點(diǎn)的個(gè)數(shù)NUM記錄任意兩用戶點(diǎn)之間可用線段連接起來(lái)且不過(guò)障礙區(qū)的線段DIS記錄不在障礙區(qū)各用戶點(diǎn)之間可用不過(guò)障礙區(qū)線段連接的線段的長(zhǎng)度EE記錄生成的最小生成樹(shù)的各點(diǎn)及各線段信息sum表示產(chǎn)生的最小生成樹(shù)中所有管道的總長(zhǎng)四問(wèn)題分析解決問(wèn)題的第一步是排除障礙區(qū)域的影響。如果用戶點(diǎn)位于障礙區(qū)域之外，則為有效用戶，否則，為無(wú)效線段。解決問(wèn)題第二步，將任意兩個(gè)有效用戶用線段連接，如果任意兩個(gè)用戶點(diǎn)之間的線段通過(guò)障礙區(qū)域之內(nèi)，則為無(wú)效線段，作剔除處理，篩選出有效線段。解決問(wèn)題第三步，根據(jù)篩選出來(lái)的有效用戶點(diǎn)和有效線段生成最小生成樹(shù)連接

7、有效用戶點(diǎn)，畫出連接路線圖形，并計(jì)算生成樹(shù)長(zhǎng)度。根據(jù)對(duì)模型的合理假設(shè)，障礙區(qū)域即為已知若干障礙區(qū)頂點(diǎn)圍成的凸多邊形，故解決此問(wèn)題的關(guān)鍵在于在已建立的二維坐標(biāo)系中，尋找到一種合理的算法能夠判定出點(diǎn)是否位于障礙區(qū)域中。通過(guò)直觀判斷，陰影區(qū)域的構(gòu)成由表7給出：表7 障礙區(qū)域構(gòu)成障礙區(qū)域編號(hào)構(gòu)成1由3個(gè)無(wú)效用戶坐標(biāo)點(diǎn)圍成的三角形2由5個(gè)無(wú)效用戶坐標(biāo)點(diǎn)圍成的凸五邊形3由3個(gè)無(wú)效用戶坐標(biāo)點(diǎn)圍成的三角形4由3個(gè)無(wú)效用戶坐標(biāo)點(diǎn)圍成的三角形通過(guò)設(shè)計(jì)運(yùn)用面積法進(jìn)行篩選點(diǎn)的程序，對(duì)所有點(diǎn)進(jìn)行篩選，找到并排除障礙區(qū)域中的無(wú)效用戶，完成解決問(wèn)題的第一步。接下來(lái)我們要做的是把任意兩個(gè)有效用戶點(diǎn)之間用線段連接，運(yùn)用向量法設(shè)

8、計(jì)篩選線段的程序，篩選出所有不過(guò)障礙區(qū)的線段，完成解決問(wèn)題的第二步。解決自來(lái)水管道連接問(wèn)題的第三步需要我們?cè)O(shè)計(jì)一個(gè)程序，將所有有效用戶點(diǎn)連接起來(lái)，并使管道總距離最小。這是一個(gè)典型的最小生成樹(shù)問(wèn)題，但相較以往最小生成樹(shù)問(wèn)題又有著其特別之處，就是障礙區(qū)域的干擾，即管道無(wú)法穿過(guò)障礙區(qū)，這使得坐標(biāo)系并非是一個(gè)連通區(qū)域，眾多算法無(wú)法直接使用。這就需要我們?cè)趯?duì)問(wèn)題進(jìn)行合理假設(shè)的前提下，對(duì)已有算法進(jìn)行改良。我們通過(guò)對(duì)穿過(guò)障礙區(qū)的線段賦權(quán)值為無(wú)窮大的方法，利用Kruskal算法，生成最優(yōu)路徑。五模型的建立與求解： 5.1.問(wèn)題一的模型建立和求解由問(wèn)題分析可知，本問(wèn)題的關(guān)鍵有二個(gè)：一是求確定各障礙區(qū)的面積以及用

9、戶點(diǎn)與各障礙區(qū)任意兩個(gè)定點(diǎn)構(gòu)成的三角形的面積之和；二是比較上面兩個(gè)面積，若相等，則該用戶點(diǎn)在障礙區(qū)內(nèi)為無(wú)效用戶，否則，用戶點(diǎn)不在障礙區(qū)內(nèi)為有效用戶。5.1.1運(yùn)用向量的方法求解障礙區(qū)面積S若障礙區(qū)是三角形，對(duì)應(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外積的模長(zhǎng)|a×b|=|a|*|b|*sin<a,b>則有S=|a×b|/2;若障礙區(qū)為五邊形，對(duì)應(yīng)點(diǎn)為(x1,y1)，(x2,y2), (x3,y

10、3), (x4,y4)，(x5,y5)。則劃分成三個(gè)三角形，各三角形的頂點(diǎn)分別為(x1,y1)，(x2,y2), (x3,y3)；(x3,y3), (x4,y4)，(x5,y5)；(x1,y1)，(x3,y3), (x5,y5)。再用求三角形面積的方法求解即可。5.1.2運(yùn)用向量的方法求用戶點(diǎn)與任意兩個(gè)同一障礙區(qū)的頂點(diǎn)構(gòu)成三角形的面積之和S1 該求解三角形面積的方法和5.1.1中求解三角形面積的方法相同。5.1.3判斷有效用戶 如果S=S1，則該用戶在障礙區(qū)內(nèi)，為無(wú)效用戶。反之，為有效用戶。則篩選完畢的結(jié)果如下： 在障礙區(qū)的點(diǎn)的序號(hào)分別為：4 23 36 99。 無(wú)效用戶的信息為：(4.000

11、0,48.5982,33.3951);(23.0000,81.3166,87.4367); (36.0000,41.8649,41.1953); (99.0000,6.4781,17.0793);有效用戶的個(gè)數(shù)是：96。 100個(gè)點(diǎn)是否在障礙區(qū)的情況如下圖：5.2問(wèn)題二的模型建立和求解 由問(wèn)題分析可知，要篩選出有效用戶點(diǎn)之間的有效線段，主要有兩個(gè)問(wèn)題需要解決：一是求出過(guò)任意兩個(gè)有效用戶點(diǎn)的直線m與過(guò)各障礙區(qū)中任意兩個(gè)頂點(diǎn)的直線L的交點(diǎn)坐標(biāo)；二是運(yùn)用向量法判斷該交點(diǎn)是否在以上述兩有效用戶點(diǎn)為端點(diǎn)上的線段m1和以上述障礙區(qū)頂點(diǎn)為端點(diǎn)的線段L1上，然后判斷過(guò)該兩個(gè)有效用戶點(diǎn)的線段是否為有效線段。5.

12、2.1運(yùn)用矩陣的方法求解兩直線之間的交點(diǎn)坐標(biāo) 如果任意兩個(gè)有效用戶點(diǎn)的坐標(biāo)分別為A(x1,y1)、B(x2,y2)，同一障礙區(qū)任意兩個(gè)頂點(diǎn)坐標(biāo)為M(x3,y3)、N(x4,y4)。則兩直線方程分別為：（1）（2）；則由解線性方程組的方法有，線性方程組的的系數(shù)矩陣為： ；在運(yùn)用Matlab求解該線性方程組時(shí)，不妨把 分別設(shè)為： 可以求得=A。5.2.2運(yùn)用向量法判斷線段是否為有效線段若求得的交點(diǎn)坐標(biāo)為P(x,y)，則通過(guò)向量關(guān)系PM=PN,可以求的。若0,則該線段為有效線段；若<0,則要考慮向量關(guān)系PA=PB,若0，則該線段為有效線段，否則，該線段為無(wú)效線段。5.3問(wèn)題三的模型建立與求解若

13、要在N個(gè)用戶之間連接自來(lái)水管道，由于每一個(gè)用戶與其余N-1個(gè)用戶之間都可能連接自來(lái)水管道。因此，在N個(gè)用戶之間，最多可能連接N(N-1)/2條自來(lái)水管道然而，在連接N個(gè)用戶之間的管道時(shí)，最少只需連接N-1條管道。也就是說(shuō)只需要N-1條管道線路就可以把N個(gè)用戶之間的自來(lái)水管道連通?，F(xiàn)在要考慮在連接N個(gè)用戶的自來(lái)水管道的同時(shí)要保證所有的管道長(zhǎng)度之和最短，這就涉及了最優(yōu)化的問(wèn)題。則顯然，要解決問(wèn)題三需要兩個(gè)步驟：一是利用Kruskal算法思想設(shè)計(jì)Matlab程序進(jìn)行最小生成樹(shù)所需邊的篩選；二是設(shè)計(jì)算法將篩選出來(lái)的構(gòu)成最小生成樹(shù)的各邊連接起來(lái)，求出最短路徑長(zhǎng)度，并畫出連接圖形。5.3.1利用Krusk

14、al算法思想求解最小生成樹(shù)把用戶看作圖的頂點(diǎn)，把用戶之間的自來(lái)水管道看做邊，把連接各條線路的長(zhǎng)度當(dāng)作權(quán)值賦給相應(yīng)的邊，這樣便構(gòu)成一個(gè)帶權(quán)的圖，即網(wǎng)。為了解決上述問(wèn)題的數(shù)學(xué)模型就是求上述圖中的網(wǎng)狀圖的最小生成樹(shù)的問(wèn)題。由問(wèn)題一可知，有效用戶的個(gè)數(shù)為96，因此我們只需要考慮這96個(gè)點(diǎn)之間的連接，這96個(gè)點(diǎn)中任意兩點(diǎn)之間的的關(guān)系只有兩種，連接或不連接。我們可以先求出由96個(gè)用戶點(diǎn)中任意兩個(gè)用戶點(diǎn)之間的距離構(gòu)成的鄰接矩陣DIS,再根據(jù)問(wèn)題二中求得的有效線段與無(wú)效線段對(duì)鄰接矩陣進(jìn)行修改，將鄰接矩陣中對(duì)應(yīng)無(wú)效線段的位置的值修改為inf，可以得到一個(gè)新的鄰接矩陣DIS。接下來(lái)，用冒泡排序法對(duì)所有有效線段長(zhǎng)度

15、按從小到大的順序進(jìn)行排序。這時(shí)，需要借助Kruskal算法進(jìn)行最小生成樹(shù)的計(jì)算。然后把最小生成樹(shù)對(duì)應(yīng)邊的線段長(zhǎng)度、起點(diǎn)、終點(diǎn)信息記錄在矩陣EE中。生成最小生成樹(shù)時(shí)，從長(zhǎng)度最短的邊開(kāi)始選取，這就涉及如何防止在選擇過(guò)程中形成回路的問(wèn)題。為了解決這個(gè)問(wèn)題，首先不妨設(shè)一個(gè)1×96的標(biāo)記向量l用于記錄被選取的點(diǎn)的序號(hào)，初始狀態(tài)向量l的各元素依次為各用戶序號(hào)，在選取線段為邊后，將對(duì)應(yīng)兩點(diǎn)的序號(hào)m與n取最小值，并將向量l中所有與m位置元素相等的元素位置及所有與n位置的元素相等的元素位置都賦值為該最小值，如此循環(huán)知道向量l中所有元素均相等時(shí)停止；同時(shí)可以設(shè)一向量R來(lái)依次記錄被選點(diǎn)的序號(hào)，直到所有用戶

16、點(diǎn)被無(wú)重復(fù)地被記錄。在按線段長(zhǎng)度從小到大的順序選擇邊時(shí)，設(shè)線段端點(diǎn)用戶的序號(hào)為m與n。這時(shí)需要考慮如下4種情況：<1>如果在向量R中m和n均沒(méi)有被記錄,則該線段可以被選為最小生成樹(shù)的邊，將對(duì)應(yīng)線段的信息記錄在矩陣EE中，同時(shí)在R中添加記錄m和n的值，并按照上述步驟更新向量l。<2>如果在向量R中m被記錄而n沒(méi)有被記錄，則該線段可以被選為最小生成樹(shù)的邊，將對(duì)應(yīng)線段的信息記錄在矩陣EE中，同時(shí)在R中添加記錄n的值，并按照上述步驟更新向量l。<3>如果在向量R中n被記錄而m沒(méi)有被記錄，則該線段可以被選為最小生成樹(shù)的邊，將對(duì)應(yīng)線段的信息記錄在矩陣EE中，同時(shí)在R中添

17、加記錄m的值，并按照上述步驟更新向量l。<4>如果在向量R中m和n均被記錄,則需要借助向量l來(lái)判斷是否該線段可以被選為最小生成樹(shù)的邊：a. 如果向量l中對(duì)應(yīng)的m位置與n位置的元素值相等，則該線段不是最小生成樹(shù)的邊，直接跳過(guò)到下一步判斷。b. 如果向量l中對(duì)應(yīng)的m位置與n位置的元素值不相等，則該線段是最小生成樹(shù)的邊，將對(duì)應(yīng)線段的信息記錄在矩陣EE中，同時(shí)只需要更新向量l。通過(guò)上述方法，即可產(chǎn)生最小生成樹(shù)，其各邊信息記錄在矩陣EE中。 5.3.2設(shè)計(jì)Matlab程序求出最小生成樹(shù)長(zhǎng)度并將各邊連接起來(lái)要計(jì)算最小生成樹(shù)的長(zhǎng)度，只需要借助for循環(huán)將EE矩陣中記錄長(zhǎng)度相加即可。具體算發(fā)如下：

18、 sum=0;for i=1:p-1 sum=sum+EE(1,i);endsum可以求得最小生成樹(shù)的長(zhǎng)度為：sum= 653.0196；最后，借助plot函數(shù)畫出最小生成樹(shù)的圖形。算法如下： hold on; for i=1:100 x=A(i,2); y=A(i,3); plot(x,y,'o')end for i=1:n-1 x1=AL(EE(2,i),2); y1=AL(EE(2,i),3); x2=AL(EE(3,i),2); y2=AL(EE(3,i),3); X=x1,x2; Y=y1,y2; plot(X,Y)endfor i=1:3 x1=B(i,2); y1

19、=B(i,3); x2=B(mod(i,3)+1,2); y2=B(mod(i,3)+1,3); X=x1,x2; Y=y1,y2; plot(X,Y,'m')endfor i=1:5 x1=C(i,2); y1=C(i,3); x2=C(mod(i,5)+1,2); y2=C(mod(i,5)+1,3); X=x1,x2; Y=y1,y2; plot(X,Y,'m')endfor i=1:3 x1=D(i,2); y1=D(i,3); x2=D(mod(i,3)+1,2); y2=D(mod(i,3)+1,3); X=x1,x2; Y=y1,y2; plot(

20、X,Y,'m')end for i=1:3 x1=E(i,2); y1=E(i,3); x2=E(mod(i,3)+1,2); y2=E(mod(i,3)+1,3); X=x1,x2; Y=y1,y2; plot(X,Y,'m')end連接形成的最小生成樹(shù)的圖形如下圖所示：由圖可知，該最小生成數(shù)是合理的。 六模型檢驗(yàn) 首先可以通過(guò)對(duì)所畫最小生成樹(shù)圖形的觀察，看是否有回路，由圖易知圖形中無(wú)回路，則通過(guò)修改最小生成樹(shù)中任意邊的連接，計(jì)算修改后的最小生成樹(shù)的長(zhǎng)度sum與sum進(jìn)行比較。可得sum>sum,則該模型所生成的最小生成樹(shù)的長(zhǎng)度最短，即運(yùn)用該模型進(jìn)行自來(lái)

21、水管道的連接所需要的自來(lái)水管長(zhǎng)度最短。七模型的評(píng)價(jià)運(yùn)用該模型進(jìn)行最小生成樹(shù)的生成可以一步到位，不需要進(jìn)行人工的修改。因?yàn)樵撃Ｐ驮谏勺钚∩蓸?shù)之前就已經(jīng)就進(jìn)行了有效用戶與有效線段的篩選，所以，最小生成樹(shù)中所選擇的所有線段都是有效的不經(jīng)過(guò)障礙區(qū)的。但是由于模型的需要計(jì)算的信息量比較的，在設(shè)計(jì)程序的時(shí)候變量的運(yùn)用比較混亂，不方便閱讀與修改，同時(shí)，由于算法設(shè)計(jì)繁瑣且反復(fù)運(yùn)用for循環(huán)，計(jì)算所需次數(shù)較多。如果在上述問(wèn)題中多注意，則該模型將會(huì)更加完美。 八模型的推廣 可以在保證障礙區(qū)不變的情況下，任意改變用戶點(diǎn)的信息，運(yùn)用該模型同樣可以求得連接自來(lái)水管道的最短長(zhǎng)度。且不需要過(guò)多改動(dòng)，不需要人工進(jìn)行修改計(jì)

22、算的結(jié)果。但是在障礙區(qū)變化的情況下，則需要較大改動(dòng)。同時(shí)該模型可以應(yīng)用到修建連接若干個(gè)地點(diǎn)之間的公路長(zhǎng)度和最短的問(wèn)題中。九參考書(shū)目1 姜啟源等，數(shù)學(xué)模型（第三版），北京：高等教育出版社，20032 薛定宇，陳陽(yáng)泉，高等應(yīng)用數(shù)學(xué)問(wèn)題的Matlab求解，清華大學(xué)出版社，20083 趙靜，但琦等，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)，高等教育出版社，2008十附錄附錄一：小組成員分工及數(shù)學(xué)建模過(guò)程感想分工：羅圣：負(fù)責(zé)符號(hào)說(shuō)明、模型建立及求解、模型檢驗(yàn)、算法設(shè)計(jì)及Matlab程序等部分的編寫。喬世俊：負(fù)責(zé)組織論文總體結(jié)構(gòu)，及編寫摘要、問(wèn)題重述、模型假設(shè)等部分。王博：負(fù)責(zé)構(gòu)思解決各問(wèn)題的算法及編寫問(wèn)題分析、模型推廣、參考

23、書(shū)目及附錄等部分。感想：羅圣：通過(guò)此次數(shù)學(xué)建模作業(yè)的完成過(guò)程，考驗(yàn)了我分析問(wèn)題、解決問(wèn)題的能力，同時(shí)也考驗(yàn)了我在不懂如何入手解決問(wèn)題時(shí)是否具有堅(jiān)持的耐心。我認(rèn)為能完成這次數(shù)學(xué)建模作業(yè)對(duì)我是一個(gè)極大鼓勵(lì)，讓我可以相信自己能在面臨一個(gè)陌生問(wèn)題時(shí)可以獨(dú)立解決它。在編寫Matlab程序時(shí)遇到過(guò)很多問(wèn)題，有很多問(wèn)題需要自己的千方百計(jì)地思考才能解決，通過(guò)這次鍛煉，學(xué)會(huì)了很多函數(shù)的使用，提升了自己編寫程序解決實(shí)際問(wèn)題的能力。從剛開(kāi)始不知從何下手的煎熬到最后完成之后的滿足，享受了團(tuán)隊(duì)合作的愉快，在這個(gè)過(guò)程中收獲了很多。喬世?。哼@次數(shù)學(xué)建模，是對(duì)我分析解決問(wèn)題方面能力的一個(gè)考驗(yàn)，包括如何分析問(wèn)題、如何查閱資料、

24、如何掌握模型結(jié)構(gòu)等。能完成這次數(shù)學(xué)建模，讓我信心倍增，我相信在以后遇到問(wèn)題時(shí)，我可以更快得尋求到解決問(wèn)題的方法。雖然這是第一次完成數(shù)學(xué)建模，但我相信它會(huì)是我的一次蛻變。王博：在剛接觸這個(gè)數(shù)學(xué)建模作業(yè)的時(shí)候，我不知道如何進(jìn)行問(wèn)題的分析，不知道從什么方面進(jìn)行入手，為此我十分苦惱。為了擺脫這中困境，我積極查找資料，希望能尋求到一些幫助。在這個(gè)過(guò)程中，我慢慢地找到了解決問(wèn)題的思路。直到最后能完整解決這個(gè)問(wèn)題，我學(xué)到了很多東西，同時(shí)，體會(huì)到了團(tuán)隊(duì)合作的重要性，整個(gè)過(guò)程我獲益匪淺。附錄二：若干個(gè)可能的用戶的地址的橫縱坐標(biāo)可能的用戶的序號(hào)可能的用戶橫坐標(biāo)可能的用戶縱坐標(biāo)1.000095.012958.279

25、22.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.193737.981813.000092.181378.332914.000073.820768.084615.000017.626646.109516.000040.5706

26、56.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.000013.889176.795026.000020.276597.084527.000019.872299.008328.000060.379278.886229.000027.218843.865930.000019.881449.831131.0

27、0001.527421.396332.000074.678664.349233.000044.509632.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.17

28、9613.377346.000050.281320.713347.000070.947160.719948.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

29、.000059.356361.239561.000049.655260.854062.000089.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.80

30、7235.325075.000037.041415.360676.000070.274067.564577.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.2

31、35089.000087.574280.487290.000073.730690.839891.000013.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附錄三：解決該自來(lái)水管道連接問(wèn)題的Matlab程序：%問(wèn)題一，進(jìn)行有效點(diǎn)的篩選A=1.0000

32、95.0129 58.2792;2.0000 23.1139 42.3496;3.0000 60.6843 51.5512;4.0000 48.5982 33.3951;5.0000 89.1299 43.2907;6.0000 76.2097 22.5950;7.0000 45.6468 57.9807;8.0000 1.8504 76.0365;9.0000 82.1407 52.9823;10.0000 44.4703 64.0526;11.0000 61.5432 20.9069;12.0000 79.1937 37.9818;13.0000 92.1813 78.3329;14.00

33、00 73.8207 68.0846;15.0000 17.6266 46.1095;16.0000 40.5706 56.7829;17.0000 93.5470 79.4211;18.0000 91.6904 5.9183;19.0000 41.0270 60.2869;20.0000 89.3650 5.0269;21.0000 5.7891 41.5375;22.0000 35.2868 30.4999;23.0000 81.3166 87.4367;24.0000 0.9861 1.5009;25.0000 13.8891 76.7950;26.0000 20.2765 97.084

34、5;27.0000 19.8722 99.0083;28.0000 60.3792 78.8862;29.0000 27.2188 43.8659;30.0000 19.8814 49.8311;31.0000 1.5274 21.3963;32.0000 74.6786 64.3492;33.0000 44.5096 32.0036;34.0000 93.1815 96.0099;35.0000 46.5994 72.6632;36.0000 41.8649 41.1953;37.0000 84.6221 74.4566;38.0000 52.5152 26.7947;39.0000 20.

35、2647 43.9924;40.0000 67.2137 93.3380;41.0000 83.8118 68.3332;42.0000 1.9640 21.2560;43.0000 68.1277 83.9238;44.0000 37.9481 62.8785;45.0000 83.1796 13.3773;46.0000 50.2813 20.7133;47.0000 70.9471 60.7199;48.0000 42.8892 62.9888;49.0000 30.4617 37.0477;50.0000 18.9654 57.5148;51.0000 19.3431 45.1425;

36、52.0000 68.2223 4.3895;53.0000 30.2764 2.7185;54.0000 54.1674 31.2685;55.0000 15.0873 1.2863;56.0000 69.7898 38.3967;57.0000 37.8373 68.3116;58.0000 86.0012 9.2842;59.0000 85.3655 3.5338;60.0000 59.3563 61.2395;61.0000 49.6552 60.8540;62.0000 89.9769 1.5760;63.0000 82.1629 1.6355;64.0000 64.4910 19.

37、0075;65.0000 81.7974 58.6918;66.0000 66.0228 5.7581;67.0000 34.1971 36.7568;68.0000 28.9726 63.1451;69.0000 34.1194 71.7634;70.0000 53.4079 69.2669;71.0000 72.7113 8.4079;72.0000 30.9290 45.4355;73.0000 83.8496 44.1828;74.0000 56.8072 35.3250;75.0000 37.0414 15.3606;76.0000 70.2740 67.5645;77.0000 5

38、4.6571 69.9213;78.0000 44.4880 72.7509;79.0000 69.4567 47.8384;80.0000 62.1310 55.4842;81.0000 79.4821 12.1047;82.0000 95.6843 45.0754;83.0000 52.2590 71.5883;84.0000 88.0142 89.2842;85.0000 17.2956 27.3102;86.0000 97.9747 25.4769;87.0000 27.1447 86.5603;88.0000 25.2329 23.2350;89.0000 87.5742 80.48

39、72;90.0000 73.7306 90.8398;91.0000 13.6519 23.1894;92.0000 1.1757 23.9313;93.0000 89.3898 4.9754;94.0000 19.9138 7.8384;95.0000 29.8723 64.0815;96.0000 66.1443 19.0887;97.0000 28.4409 84.3869;98.0000 46.9224 17.3900;99.0000 6.4781 17.0793;100.0000 98.8335 99.4295;B=1 3.2060 12.9166;2 17.4571 19.3377

40、;3 4.7576 20;C=1 50 30;2 53.7465 48.4490;3 46.9222 57.1195;5 43.1123 56.3187;4 33.3207 39.8050;D=1 54.6982 70;2 53.7465 90;3 46.9222 80;E=1 90 75; 2 80 95; 3 70 80;%準(zhǔn)備用戶坐標(biāo)矩陣和障礙區(qū)坐標(biāo)矩陣SIGN=zeros(1,100);%生成1行100列的記錄矩陣，若點(diǎn)不在障礙區(qū)則對(duì)應(yīng)位置記為1，否則記為0for n=1:100a1=B(2,2)-B(1,2),B(2,3)-B(1,3),0;a2=B(3,2)-B(2,2),B(3,

41、3)-B(2,3),0;a3=B(1,2)-B(3,2),B(1,3)-B(3,3),0;S=norm(cross(a1,a2)/2;%該障礙區(qū)面積x=A(n,2);y=A(n,3);z1=x-B(1,2),y-B(1,3),0;z2=x-B(2,2),y-B(2,3),0;z3=x-B(3,2),y-B(3,3),0;s1=norm(cross(z1, a1)/2;s2=norm(cross(z2, a2)/2;s3=norm(cross(z3, a3)/2;S1=s1+s2+s3;%由用戶點(diǎn)和任意對(duì)應(yīng)兩個(gè)該障礙區(qū)頂點(diǎn)構(gòu)成的三角形面積之和if(S1=S)m1=0 ;else m1=1;end

42、%第一個(gè)障礙區(qū)內(nèi)的點(diǎn)判斷b1=C(2,2)-C(1,2),C(2,3)-C(1,3),0;b2=C(3,2)-C(2,2),C(3,3)-C(2,3),0;b3=C(4,2)-C(3,2),C(4,3)-C(3,3),0;b4=C(5,2)-C(4,2),C(5,3)-C(4,3),0;b5=C(1,2)-C(5,2),C(1,3)-C(5,3),0;s1=norm(cross(b1,b2)/2;s2=norm(cross(b3,b4)/2;s3=norm(cross(b1+b2,b3+b4)/2;S=s1+s2+s3;%該障礙區(qū)面積x=A(n,2);y=A(n,3);z1=x-C(1,2),

43、y-C(1,3),0;z2=x-C(2,2),y-C(2,3),0;z3=x-C(3,2),y-C(3,3),0;z4=x-C(4,2),y-C(4,3),0;z5=x-C(5,2),y-C(5,3),0;s1=norm(cross(z1,b1)/2;s2=norm(cross(z2,b2)/2;s3=norm(cross(z3,b3)/2;s4=norm(cross(z4,b4)/2;s5=norm(cross(z5,b5)/2;S1=s1+s2+s3+s4+s5;%由用戶點(diǎn)和任意對(duì)應(yīng)兩個(gè)該障礙區(qū)頂點(diǎn)構(gòu)成的三角形面積之和if(S1=S)m2=0;else m2=1;end%第二個(gè)障礙區(qū)內(nèi)的點(diǎn)

44、判斷c1=D(2,2)-D(1,2),D(2,3)-D(1,3),0;c2=D(3,2)-D(2,2),D(3,3)-D(2,3),0;c3=D(1,2)-D(3,2),D(1,3)-D(3,3),0;S=norm(cross(c1,c2)/2;%該障礙區(qū)面積x=A(n,2);y=A(n,3);z1=x-D(1,2),y-D(1,3),0;z2=x-D(2,2),y-D(2,3),0;z3=x-D(3,2),y-D(3,3),0;s1=norm(cross(c1,z1)/2;s2=norm(cross(c2,z2)/2;s3=norm(cross(c3,z3)/2;S1=s1+s2+s3;%由

45、用戶點(diǎn)和任意對(duì)應(yīng)兩個(gè)該障礙區(qū)頂點(diǎn)構(gòu)成的三角形面積之和if(S1=S)m3=0;else m3=1;end%第三個(gè)障礙區(qū)內(nèi)的點(diǎn)判斷d1=E(2,2)-E(1,2),E(2,3)-E(1,3),0;d2=E(3,2)-E(2,2),E(3,3)-E(2,3),0;d3=E(1,2)-E(3,2),E(1,3)-E(3,3),0;S=norm(cross(d1,d2)/2;%該障礙區(qū)面積x=A(n,2);y=A(n,3);z1=x-E(1,2),y-E(1,3),0;z2=x-E(2,2),y-E(2,3),0;z3=x-E(3,2),y-E(3,3),0;s1=norm(cross(d1,z1)/

46、2;s2=norm(cross(d2,z2)/2;s3=norm(cross(d3,z3)/2;S1=s1+s2+s3;%由用戶點(diǎn)和任意對(duì)應(yīng)兩個(gè)該障礙區(qū)頂點(diǎn)構(gòu)成的三角形面積之和if(S1=S)m4=0 ;else m4=1;end%第四個(gè)障礙區(qū)內(nèi)的點(diǎn)判斷if(m1&m2&m3&m4)SIGN(n)=1;else SIGN(n)=0;endendSIGN ;%以上判斷不在障礙區(qū)的點(diǎn)，其標(biāo)號(hào)記錄在SIGN矩陣中用1表示OUTSIGN=find(SIGN=0)%記錄在障礙區(qū)的用戶點(diǎn)p=0;for i=1:100 p=p+SIGN(i);endp%計(jì)算保留用戶點(diǎn)的個(gè)數(shù)p%問(wèn)題二

47、，進(jìn)行有效線段的篩選NUM=zeros(100,100);for i=1:100 for j=i+1:100 NUM(i,j)=1; endendb1=(B(1,3)-B(2,3)/(B(1,2)-B(2,2);bb1=(B(1,3)*B(2,2)-B(1,2)*B(2,3)/(B(1,2)-B(2,2);b2=(B(2,3)-B(3,3)/(B(2,2)-B(3,2);bb2=(B(2,3)*B(3,2)-B(2,2)*B(3,3)/(B(2,2)-B(3,2);b3=(B(3,3)-B(1,3)/(B(3,2)-B(1,2);bb3=(B(3,3)*B(1,2)-B(3,2)*B(1,3)/(B(3,2)-B(1,2);BB=b1 bb1;b2 bb2;b3 bb3;c1=(C(1,3)-C(2,3)/(C(1,2)-C(2,2);cc1=(C(