天然氣管道的鋪設(shè)方案的優(yōu)化(已修改)
2024-11-28 14:49 本頁(yè)面
【正文】 1 天然氣管道的鋪設(shè)方案的優(yōu)化 摘要 本文對(duì)天然氣管道的鋪設(shè)問(wèn)題進(jìn)行研究，利用運(yùn)籌學(xué)中的圖論知識(shí)，應(yīng)用最小生成樹(shù)的通用算法（避圈法和破圈法）和權(quán)值排序法建立了理論模型，求得連接有效用戶總距離最小的解。另外，我們?cè)诶碚撃Ｐ偷幕A(chǔ)上建立了一個(gè)實(shí)用簡(jiǎn)化模型，得到鋪設(shè)有效用戶管道總距離最小的近似最優(yōu)解并對(duì)其進(jìn)行了推廣。 對(duì)問(wèn)題一：我們利用 MATLAB 軟件包把 100 個(gè)可能用戶繪制成一張直觀圖（見(jiàn)下圖一），在圖中標(biāo)明 4 個(gè)障礙區(qū)的位置，通過(guò)直觀圖我們很容易得到，障礙區(qū)域內(nèi)覆蓋的無(wú)效用戶的個(gè)數(shù)為 4，這 4 個(gè)無(wú)效用戶序號(hào)及坐標(biāo) 分別為： （ ， ）， （ ， ）， （ ，）， （ ， ）。所以，有效用戶即為排除這 4 個(gè)用戶后的其他 96 個(gè)用戶。 對(duì)問(wèn)題二：我們首先得出了任意兩用戶之間的距離，若兩點(diǎn)連線過(guò)障礙區(qū)則取無(wú)窮大。再利用求最小生成樹(shù)的理論算法（避圈法和破圈法）建立模型，求出鋪設(shè) 96 個(gè)有效用戶天然氣管道總長(zhǎng)度的最小值為： 然后，我們又應(yīng)用權(quán)值排序法建立了一個(gè)理論模型，其基本思 想是把 96 個(gè)有效用戶及連線看成一個(gè)網(wǎng)，將網(wǎng)中的邊按其權(quán)值由小到大的順序排序，然后進(jìn)行選取，在保證后選取的邊不與前面所選邊構(gòu)成的回路的情況下，這樣反復(fù)選擇排除，最終找到 95 條邊，即得到 96 個(gè)有效用戶的最小生成樹(shù)，求得其近似最優(yōu)解為： 。 最后，我們依據(jù)上面的理論模型建立了一個(gè)簡(jiǎn)化的實(shí)用簡(jiǎn)化模型，即把 96個(gè)有效用戶分成 n 個(gè)小區(qū)域（ n96），在每個(gè)小區(qū)域內(nèi)求它的最小生成數(shù)，再利用鄰接調(diào)整法，把 n 個(gè)小區(qū)域連接成一個(gè)大的最小生成樹(shù)，該樹(shù)求得的權(quán)數(shù)總和即為連接 96 個(gè)有效用戶的總距離最小的近似最優(yōu)解， 其值為： 關(guān)鍵詞： 最小生成樹(shù) 避圈法 破圈法 權(quán)值排序法 一、問(wèn)題的重述 如今使用天然氣的人越來(lái)越多，作為天然氣的供應(yīng)商如何向用戶供氣，即如何使用戶之間連接成一個(gè)樹(shù)形網(wǎng)絡(luò)是很重要的。一般來(lái)說(shuō)，我們假設(shè)任意兩個(gè) 2 用戶之間存在直線道相連，但是在連接過(guò)程中，有些區(qū)域是必須繞開(kāi)的，這些必須繞開(kāi)的區(qū)域我們稱為障礙區(qū)域。 表 1（見(jiàn)附件 [1]）給出了若干個(gè)可能的用戶的地址的橫縱坐標(biāo)，可能的用戶的含義是：如果用戶的地址不在障礙區(qū)域內(nèi)，那么該用戶就是需要使用天然 氣的用戶（即有效用戶），否則如果用戶的地址在障礙區(qū)域內(nèi)，那么該用戶就是無(wú)效用戶（即不要將該用戶連接在網(wǎng)絡(luò)中）。表 2表 5（見(jiàn)附件 [2]）是分別是 4個(gè)障礙區(qū)域必須要覆蓋的點(diǎn)的坐標(biāo)，而對(duì)應(yīng)障礙區(qū)域就是覆蓋這些要覆蓋的點(diǎn)的最小凸集。 （ 1）根據(jù)題意判定表 1 中那些用戶為有效用戶。 （ 2）設(shè)計(jì)出一個(gè)算法將有效用戶連接起來(lái)，并且連接的距離總和最小。 二、問(wèn)題的分析 本題是一個(gè)典型的網(wǎng)絡(luò)組合運(yùn)籌學(xué)問(wèn)題，主要是運(yùn)用圖論中最小生成樹(shù)的方法和理論解決。但對(duì)于求最短路等問(wèn)題，到目前為止還沒(méi)有一個(gè)有效和固定的算法。例如單人巡回 的 Hamilton 路，精確最優(yōu)的求解往往因時(shí)間復(fù)雜度過(guò)大而難以實(shí)現(xiàn)。 把天然氣管道連接問(wèn)題轉(zhuǎn)化為一張圖，本文開(kāi)始算出了任意兩節(jié)點(diǎn)之間的權(quán)值，即對(duì)用戶之間的距離，規(guī)定如果兩節(jié)點(diǎn)之間的連線經(jīng)過(guò)障礙區(qū)，則把他當(dāng)作無(wú)窮大，建立了一張無(wú)向完全圖。然后建立求最小生成樹(shù)的理論模型，利用避圈法和破圈法的思想，給
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1