運籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型-文庫吧
2025-04-22 15:06 本頁面
【正文】 G=(V， E)，并且 V1? V ， ,則稱 G1為 G的生成子圖； },|),{(111 VvVuEvuE ????部分圖、生成子圖、部分樹 部分圖 生成子圖 部分樹 如果 V1? V， E1 ? E則稱 G1為 G的部分圖； 設(shè) G=(V， E)和 G1=(V1， E1) 如果 G1=(V1， E1)， G=(V， E)，并且 V1? V ， ,則稱 G1為 G的生成子圖； },|),{(111 VvVuEvuE ???? 如果 G=(V， E 的部分 圖 G1=(V， E1)是樹 ，則稱 G1為 G的一個部分樹。 1 3 2 5 4 6 4 3 3 2 3 2 2 最小生成樹不一定唯一 最小生成樹： 設(shè)有一連通圖 G=(V,L),對于每一邊 e=(vi,vj)，有一個權(quán) wij≥0。一棵生成樹所有樹枝上權(quán)的總和，稱為這個生成樹的權(quán)。具有最小權(quán)的生成樹稱為最小生成樹（最小樹）。 例：某大學(xué)準備對其所屬的 7個學(xué)院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中 v1,… ,v7 表示 7個學(xué)院辦公室，請設(shè)計一個網(wǎng)絡(luò)能聯(lián)通 7個學(xué)院辦公室，并使總的線路長度為最短。 v1 3 3 1 7 2 8 5 4 10 3 4 v7 v6 v5 v4 v2 v3 圖 611 方法一：破圈法 步驟： 在給定的賦權(quán)的連通圖上任找一個圈。 在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。 如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第 1步。 v1 3 3 1 7 2 8 5 4 10 3 4 v7 v6 v5 v4 v2 v1 3 3 1 7 2 8 5 4 3 4 v7 v6 v5 v4 v2 v1 3 3 7 2 5 4 3 4 v7 v6 v5 v4 v2 v3 v3 v3 1 v1 3 3 7 2 4 3 4 v7 v6 v5 v4 v2 v3 1 v1 3 3 7 2 3 4 v7 v6 v5 v4 v2 v3 1 v1 3 3 7 2 3 v7 v6 v5 v4 v2 v3 1 (a) (b) (c) (d) (e) (f) 解：按照圖 1611的 (f)設(shè)計，可使此網(wǎng)絡(luò)的總的線路長度為最短，為 1900米。 方法二： (加邊 )避圈法（ Kruskal） ?開始選一條最小權(quán)的邊，以后每一步中，總從未被選中的邊中選一條最小權(quán)的邊，使之與已選的邊不構(gòu)成圈，直到所有的邊都檢驗完，即可得最小樹。（每步中，若有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條）。 例：右圖 ,用避圈法求其最小生成樹。 類似地 ,可定義連通圖 G 的最大生成樹 . 練習(xí)：房屋開發(fā)商正規(guī)劃設(shè)計某居住新區(qū)的下水管道，圖中各數(shù)字表示各棟樓房之間鋪設(shè)管道的工程費用。房屋開發(fā)商應(yīng)怎樣設(shè)計最佳的管道鋪設(shè)方案，使總工程費用最少。 2 8 7 3 9 6 5 6 5 7 單位：十萬元 6 V1 V2 V3 V5 V4 V6 從一特殊的節(jié)點出發(fā)，找出從該節(jié)點到網(wǎng)絡(luò)中任何其它節(jié)點的最短路徑問題 某人買了一輛價值 12021美元的新車 ， 一輛車每年的維護費用依賴于年初時的車齡 ， 具體費用見下表 。為了避免舊車的高維護費用 ， 他決定賣掉舊車買新車 。 舊車的價格依賴于交易時的車齡 ， 見右表 。 為計算簡單起見 ， 假設(shè)任何時間新車的價格不變均為12021美元 。 他希望在今后 5年內(nèi)的凈費用最?。?即：凈費用 =購買價 +維護價 售出價 ） 。 車齡 每年的維護費用 售出價格 1 2 3 4 5 6 2021 4000 5000 9000 12021 7000 6000 2021 1000 0 1 2 3 4 5 6 21 7 7 7 7 7 12 12 12 21 31 31 44 12 21 第三節(jié) 最短路問題 節(jié)點 i表示第 i年年初，當(dāng) ij時，?。?i,j）表示第 i年年初買一輛新車并一直用到第 j年年初?；。?i,j）的長度為 cij， cij表示如果第 i年年初買車并在第 j年年初賣掉更換新車，從第 i年年初到第 j年年初期間總費用。 Cij=(i,i+1,,j1年的維護費 )+第 i年年初買新車的費用 第 j年年初該車的售出價格 C12=2+127=7 C13+c35+c56是 1到 6的最小費用，第 3年 年初與第五年初交易，今后 5年的凈費用最小。 算法 （ Dijkstra(迪杰斯特拉 ) 1959年提出的） 1 3 2 5 4 6 4 3 3 2 3 2 2 ? 第 0步： P(1)=0,T(i)=+∞ ； ? 第 1步：與 1相連的標號為 2,3，均是 T標號，修改 2,3的標號， T(2)=min{T(2),P(1)+w12} ?=min{+∞ ,P(1)+w12}=4,T(3)=3；在所有的 T標號中， 3的標號最小，改 3的標號為 P(3)=3； ? 第 2步：修改與 3相連的 T標號；在所有剩下的 T標號中， 2的標號最小，改為 P(2)=4； ? 第 3步：修改與 2相連的 T標號；在所有剩下的 T標號中， 5的標號最小，改為 P(5)=6； ? 第 4步：修改與 5相連的 T標號；在所有剩下的 T標號中， 4的標號最小，改為 P(4)=7； ? 第 5步：修改與 4相連的 T標號；只
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1