天然氣管道的鋪設(shè)方案的優(yōu)化(編輯修改稿)
2024-12-18 14:49 本頁面
【文章內(nèi)容簡介】 4 3 2 9 2 1 6 . 2 1 6 4 5 , 0 . 5 8 7 8 5 5 9 . 3 9 2 5 ,3 . 8 2 1 1 2 2 5 3 . 8 2 0 8 2 6 , 0 . 2 1 0 1 8 9 4 7 . 2 5 9 6 9 , 1 . 6 8 6 5 1 7 1 6 . 3 9 0 9 2 7Y X Y XSY X Y X Y X? ? ? ? ? ?? ? ? ? ? ? ???3 21 .0 15 10 79 .4 82 6 , 1. 28 60 1 0. 34 24 32 , 1. 46 53 5 1 Y X Y X Y X? ? ? ? ? ? ? ? ? ??4 2 25 5 , 0. 25 97 .5 , 1. 5 25S Y X Y X Y X? ? ? ? ? ? ? ? ? 連接節(jié)點(diǎn)中的任意兩節(jié)點(diǎn) ( , ), ( , )i i i j j jV X Y V X Y得到他們兩點(diǎn)之間線段的方程為： ijX X tX?? ijY Y tY?? ? ?1,1t?? 當(dāng) ?? 1 2 3 4( , )X Y S S S S? 時(shí)令 ijE 邊上的權(quán) ijW 為 M。（ M 為一個(gè)無窮大的數(shù)） 當(dāng) ?? 1 2 3 4( , )X Y S S S S? 時(shí)令 ijE 邊上的權(quán) ijW 為： ? ? ? ?22ij i j i jW X X Y Y? ? ? ? 上式確定了任意兩節(jié)點(diǎn)之間權(quán)的算法，把他們用矩陣表示出來，就得到了一個(gè)96 階的矩陣。矩陣中的元素表示對(duì)應(yīng)的兩節(jié)點(diǎn)間的權(quán)數(shù)。 理論模型 利用最小生 成樹來求解最短路徑的問題，在得到任意兩節(jié)點(diǎn)權(quán)的條件下，我運(yùn)用以下方法來求解。 [1] 避圈法和破圈法來求圖的最小生成樹。 用避圈法在給定的圖中尋找最小生成樹的基本步驟是： （ 1） 從圖中 96 個(gè)節(jié)點(diǎn)中任選一點(diǎn) iV ，讓 iVV? ，圖中其余點(diǎn)均包含在 V 中。 （ 2） 從 V 與 V 的連線中找出一條最小邊，若有兩條邊相等，任選一條即可，則這條邊一定包含在最小部分樹內(nèi)。 5 （ 3） 令 jV V V? ， \ jV V V? 。 （ 4） 重復(fù)（ 2），（ 3）兩步，一直到土中 96 個(gè)點(diǎn)均包含在 V 中為止。 用破圈法在給定的圖中尋找最小生成樹的基本步驟是： （ 1） 從網(wǎng)絡(luò)圖 N 中任取一回路 C。 （ 2） 在回路中去掉其中權(quán)數(shù)最大的 一條邊。得子網(wǎng)絡(luò)圖 1N 。 （ 3） 再在 1N 中任取一回路，再去掉回路中權(quán)數(shù)最大的一條邊，得 2N 。 （ 4） 重復(fù)（ 3），一直到剩下的子圖中不再含回路為止，該圖就是 N 的最小部分樹。 [2] 構(gòu)造網(wǎng)絡(luò)中的最小生成樹，下面我們給出這樣一種解法：（稱其為權(quán)值排序法） （ 1） 已知一個(gè)網(wǎng)，將網(wǎng)中的邊按其權(quán)值由小到大的次序順序選取。 （ 2） 若選某邊后不形成回路，則將其保留作為樹的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再考慮。 （ 3）如此依次進(jìn)行，直到選夠 (n1)條邊即得到最小生成樹。 通過 MATLAB 對(duì)避圈法的編程，我們得到 以下結(jié)果： 表一：最小生成樹的節(jié)點(diǎn)連接情況及權(quán)值 起始節(jié)點(diǎn) 終止節(jié)點(diǎn) 距離 (權(quán)值 )
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1