天然氣管道的鋪設(shè)方案的優(yōu)化-文庫吧
2025-10-09 14:49 本頁面
【正文】 出精確求解最小生成樹的通用算法，得出距離總和最??；將邊按其權(quán)值由小到大的順序進行排序，按由大到小次序選取，若選某邊后不形成回路，則將其保留作為樹的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再考慮，如此依次進行， 直到選夠有效用戶的個數(shù)（ n ）減一條邊即得到最小生成樹。通過這種方法可求得近似最優(yōu)解。 另外，本文將會給出一個簡化的實用模型，用鄰接調(diào)整法求最小生成樹，用節(jié)點分類法調(diào)整均衡，在近似簡化的基礎(chǔ)上，用計算機解出滿意解（程序見附件[2]）。問題二在理論與實用模型中可分別得出總距離最優(yōu)的解。 三、模型的假設(shè) 1. 每一個有效用戶都需要鋪設(shè)天然氣管道； 2. 障礙區(qū)都只是由 表 2表 5 給出點，并覆蓋這些要覆蓋的點的最小凸集，不會出現(xiàn)其他形狀。 3．在不經(jīng)過障礙區(qū)的前提下，天然氣管道在其他任何地方都沿直線鋪設(shè)。 四、 符號說明 參數(shù) 說明 N（ V， E， W） 圖 Y 可能的用戶橫坐標 3 X 可能的用戶縱坐標 iS 障礙區(qū)域構(gòu)成的集合 V 圖中 節(jié)點集合 E 圖中邊的集合 W 圖中邊上權(quán)的集合。 iV 圖中的第 i 個節(jié)點 五、模型的建立與求解 問題一： 題目給出了 100 個用戶 的地址的橫縱坐標 ，把他們反映到直角坐標系中如下（見圖一）。表 2—— 表 5 是四個障礙區(qū)域必須要覆蓋的點的坐標，而對應(yīng)障礙區(qū)域就是覆蓋這些要覆蓋點的最小凸集。通過最小凸集的概念得到四個障礙區(qū)域在圖中的表示。題目所給條件 ：如果用戶的地址不在障礙區(qū) 域內(nèi)，那么該用戶就是需要使用天然氣的用戶（即有效用戶），否則如果用戶的地址在障礙區(qū)域內(nèi)，那么該用戶就是無效用戶（即不要將該用戶連接在網(wǎng)絡(luò)中）。 圖一： 100 個可能用戶的坐標直觀圖 由上圖 很容易觀察到，有效用戶 96 戶，無效用戶 4 戶， 4 戶無效用戶及所在障礙區(qū)域的分別為： （ 1）障礙區(qū)域 1 覆蓋了一戶用戶，該用戶的序號為 ，坐標為（ ，）； （ 2）障礙區(qū)域 2 覆蓋了兩戶用戶，用戶序號及坐標分別為： （ ，）， （ ， ） 4 （ 3）障礙區(qū)域 3 沒有覆蓋用戶； （ 4）障礙區(qū)域 4 覆蓋了一戶用戶，序號為 ，坐標為（ ， ）。 問題二： 設(shè)計一個算法將有效用戶連接起來，并且連接的距離總和最小。這是一個典型的求最短路徑的問題，通過問題分析我們決定用最小生成樹的方法來解決求解。 模型建立前的準備： 通過問題一知道，在題目中只有 96 個有效用戶，首先，我們將天然氣的管道轉(zhuǎn)化為一張圖，其中節(jié)點表示有效用戶，邊上的權(quán)表示任意兩有效用戶之間的連線長度。設(shè)其為 N（ V， E， W） ， V 為節(jié)點集合， E 為邊 的集合， W 為邊上的權(quán)。我們建立起一個包含 96 個頂點的完全圖，下面我們來確定各邊的權(quán)數(shù)。 首先，我們把 表 2—— 表 5 給出的四個障礙區(qū)域用集合表示出來，設(shè)他們分別為 1 2 3 4, , ,S S S S 。 其中： ??1 0 .4 5 0 5 6 9 1 1 .4 7 2 0 7 6 , 0 .0 5 2 1 5 2 0 .2 4 8 1 0 9 , 4 .5 6 5 2 2 3 1 .7 1 9 5 0 5S Y X Y X Y X? ? ? ? ? ? ? ?? ?2 4 . 9 2
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1