天然氣管道的鋪設(shè)方案的優(yōu)化-全文預(yù)覽
【正文】 [文迪、王宏芳、黃瓊 ] 。前者，具有堅(jiān)實(shí)的理論基礎(chǔ)，說服力強(qiáng)，后者是借助前者的思想方法對(duì)實(shí)際問題的簡(jiǎn)化，得到實(shí)用的求解方法，而且大大減少了工作量，方便計(jì)算機(jī)的運(yùn)行。 （ 5） 把（ 4）中所得的邊與（ 3）中樹 1 2 3, nN N N N的對(duì)應(yīng)節(jié)點(diǎn)相連，就得到了一個(gè)最小生成樹。 （ 2） 在每 個(gè)小區(qū)域中利用最小生成樹的算法得到樹 1 2 3, nN N N N。 權(quán)值排序法所得的有效用戶的最小距離為： 。 [2] 構(gòu)造網(wǎng)絡(luò)中的最小生成樹，下面我們給出這樣一種解法：（稱其為權(quán)值排序法） （ 1） 已知一個(gè)網(wǎng)，將網(wǎng)中的邊按其權(quán)值由小到大的次序順序選取。 （ 2） 在回路中去掉其中權(quán)數(shù)最大的 一條邊。 （ 2） 從 V 與 V 的連線中找出一條最小邊，若有兩條邊相等，任選一條即可，則這條邊一定包含在最小部分樹內(nèi)。矩陣中的元素表示對(duì)應(yīng)的兩節(jié)點(diǎn)間的權(quán)數(shù)。我們建立起一個(gè)包含 96 個(gè)頂點(diǎn)的完全圖，下面我們來確定各邊的權(quán)數(shù)。 問題二： 設(shè)計(jì)一個(gè)算法將有效用戶連接起來，并且連接的距離總和最小。表 2—— 表 5 是四個(gè)障礙區(qū)域必須要覆蓋的點(diǎn)的坐標(biāo)，而對(duì)應(yīng)障礙區(qū)域就是覆蓋這些要覆蓋點(diǎn)的最小凸集。 三、模型的假設(shè) 1. 每一個(gè)有效用戶都需要鋪設(shè)天然氣管道； 2. 障礙區(qū)都只是由 表 2表 5 給出點(diǎn)，并覆蓋這些要覆蓋的點(diǎn)的最小凸集，不會(huì)出現(xiàn)其他形狀。然后建立求最小生成樹的理論模型，利用避圈法和破圈法的思想，給出精確求解最小生成樹的通用算法，得出距離總和最小；將邊按其權(quán)值由小到大的順序進(jìn)行排序，按由大到小次序選取，若選某邊后不形成回路，則將其保留作為樹的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再考慮，如此依次進(jìn)行， 直到選夠有效用戶的個(gè)數(shù)（ n ）減一條邊即得到最小生成樹。 二、問題的分析 本題是一個(gè)典型的網(wǎng)絡(luò)組合運(yùn)籌學(xué)問題，主要是運(yùn)用圖論中最小生成樹的方法和理論解決。 表 1（見附件 [1]）給出了若干個(gè)可能的用戶的地址的橫縱坐標(biāo)，可能的用戶的含義是：如果用戶的地址不在障礙區(qū)域內(nèi)，那么該用戶就是需要使用天然 氣的用戶（即有效用戶），否則如果用戶的地址在障礙區(qū)域內(nèi)，那么該用戶就是無效用戶（即不要將該用戶連接在網(wǎng)絡(luò)中）。 對(duì)問題二：我們首先得出了任意兩用戶之間的距離，若兩點(diǎn)連線過障礙區(qū)則取無窮大。 1 天然氣管道的鋪設(shè)方案的優(yōu)化 摘要 本文對(duì)天然氣管道的鋪設(shè)問題進(jìn)行研究，利用運(yùn)籌學(xué)中的圖論知識(shí)，應(yīng)用最小生成樹的通用算法（避圈法和破圈法）和權(quán)值排序法建立了理論模型，求得連接有效用戶總距離最小的解。所以，有效用戶即為排除這 4 個(gè)用戶后的其他 96 個(gè)用戶。一般來說，我們假設(shè)任意兩個(gè) 2 用戶之間存在直線道相連，但是在連接過程中，有些區(qū)域是必須繞開的，這些必須繞開的區(qū)域我們稱為障礙區(qū)域。 （ 2）設(shè)計(jì)出一個(gè)算法將有效用戶連接起來，并且連接的距離總和最小。 把天然氣管道連接問題轉(zhuǎn)化為一張圖，本文開始算出了任意兩節(jié)點(diǎn)之間的權(quán)值，即對(duì)用戶之間的距離，規(guī)定如果兩節(jié)點(diǎn)之間的連線經(jīng)過障礙區(qū)，則把他當(dāng)作無窮大，建立了一張無向完全圖。問題二在理論與實(shí)用模型中可分別得出總距離最優(yōu)的解。 iV 圖中的第 i 個(gè)節(jié)點(diǎn) 五、模型的建立與求解 問題一： 題目給出了 100 個(gè)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1