圖與網(wǎng)絡(luò)ppt課件(2)(參考版)
2025-05-06 18:49本頁面
【正文】 4 。 2。 至于每小時(shí)運(yùn)送 7萬加侖，我們可以在圖 1136的基礎(chǔ)上，再按第五次迭代所選的最短路運(yùn)送 1萬加侖即得最小費(fèi)用： 72+1*17=89百元，其運(yùn)送方式如圖 1135所示。已經(jīng)找不到從 v1到 v7的每條弧容量都大于零的路了，故已求得最小費(fèi)用最大流。(3,6)(0,4) (1,7)(2,5) (1,4)（ 0,3） (1,4)(0,3)(0,8)（ 0,2）v1v2v5v7v4v3v6(0,3)(6,3)(2,8)(1,3)（ 3,2）(3,6)(3,4)(0,5)（ 1,4） (4,7)(3,4)（ 2,3）圖 113399 第五次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ⑥ 第六次迭代：找到最短路 v1 → v2 → v3 → v5 → v7 。(6,6)(3,4) (4,7)(2,5) (1,4)（ 0,3） (1,4)(0,3)(0,8)（ 0,2）v1v2v5v7v4v3v6(0,3)(6,3)(2,8)(1,3)（ 3,2）(0,6)(0,4)(0,5)（ 1,4） (1,7)(3,4)（ 2,3）圖 113266第四次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ⑤ 第五次迭代：找到最短路 v1 → v2 → v5 → v7 。(6,6)(3,4) (5,7)(2,5) (0,4)（ 0,3） (1,4)(0,3)(0,8)（ 1,2）v1v2v5v7v4v3v6(1,3)(5,3)(2,8)(1,3)（ 2,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(3,4)（ 2,3）圖 113155第三次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ④ 第四次迭代：找到最短路 v1 → v4 → v3 → v5 → v7 。(6,6)(3,4) (5,7)(2,5) (0,4)（ 2,3） (3,4)(0,3)(0,8)（ 3,2）v1v2v5v7v4v3v6(3,3)(3,3)(2,8)(1,3)（ 0,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(1,4)（ 0,3）圖 113033第二次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ③ 第三次迭代：找到最短路 v1 → v4 → v3 → v6 → v7 。v5(6,6)(3,4) (5,7)(2,5) (0,4)（ 2,3） (3,4)(0,3)(2,8)（ 3,2）v1v2v7v4v3v6(5,3)(1,3)(0,8)(1,3)（ 0,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(1,4)（ 0,3）圖 112911第一次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ② 第二次迭代：找到最短路 v1 → v4 → v7。用上述方法對例 9求解： ① 第一次迭代：找到最短路 v1 → v4 → v6 → v7。 求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量 F改為 f即可。從采地 v1 向銷地 v7 運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最小？求出最大流量的最小費(fèi)用 ()。(6,6)(3,4) (5,7)(2,5)(2,4)（ 2,3） (4,4)(1,3)(2,8)（ 3,2）v1v2v5v7v4v3v6(6,3)22v1v2 v5v7v4v3v6123522 355 最小費(fèi)用最大流問題 例 8最大流問題可能有多種解法，如：12v1v2v5v7v4v3v6123632 345解 1解 2一、最小費(fèi)用最大流的數(shù)學(xué)模型 例 9. 由于輸油管道的長短不一，所以在例 6中每段管道（ vi,vj ）除了有不同的流量限制 cij外，還有不同的單位流量的費(fèi)用 bij ， cij的單位為萬加侖 /小時(shí)， bij的單位為百元 /萬加侖。得到最大流量為 10?；。? v3 , v6 ）的順流容量為 2，決定了 pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 22 2 33v1v2v5v7v4v3v611000 20320 3335031200213388 第四次迭代后的總流量1 最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法⑤ 第五次迭代：選擇路為 v1 → v2 → v3 → v5 → v7 ?；。? v2 , v5 ）的順流容量為 3，決定了 pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：63 522 2 413v1v2v5v7v4v3v600 000000420220 3330355第二次迭代后的總流量 最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法③ 第三次迭代：選擇路為 v1 → v4 → v6 → v7 。 最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法基本算法步驟：① 第一次迭代：選擇路為 v1 → v4 → v7 。（ 3）在這條路上，減少每一條弧的順流容量 pf ，同時(shí)增加這些弧的逆流容量 pf，返回步驟（ 1）。如果不存在這樣的路，則已經(jīng)求得最大流。如下圖 : (a)和 (b)、 (c)和 (d)的意義相同。 最大流問題一、最大流的數(shù)學(xué)模型二、最大流問題的網(wǎng)絡(luò)圖論解法 對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。對每一條弧 (vi,vj)的流量 fij要滿足流量的可行條件，應(yīng)小于等于弧 (vi,vj)的容量 cij，并大于等于零，即 0≤fij≤ cij。 cij的單位為萬加侖 /小時(shí)。一、最大流的數(shù)學(xué)模型 例 8. 某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。（零流即是可行流）網(wǎng)絡(luò)最大流問題：指滿足容量限制條件和中間點(diǎn)平衡的條件下，使 v(f)值達(dá)到最大。容量網(wǎng)絡(luò)上所有的弧滿足： 0≤fij≤cij 中間點(diǎn)平衡條件。滿足以下條件的一組流稱為 可行流 。3. 流與可行流 流 是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對加在弧 (vi,vj)上的負(fù)載量記為 fij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè) 發(fā)點(diǎn)發(fā)點(diǎn) (也稱源點(diǎn)，記為 s)和一個(gè) 收點(diǎn)收點(diǎn) (也稱匯點(diǎn)，記為 t)，網(wǎng)絡(luò)中其他點(diǎn)稱為 中間點(diǎn)中間點(diǎn) 。這就是一個(gè)網(wǎng)絡(luò)最大流問題。 最小生成樹問題v1 3317285410 34v7v6 v5v4v2 v3圖 1114 此問題實(shí)際上是求圖1114的最小生成樹，這在例 6中已經(jīng)求得，即按照圖 (f) 的設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線路長度為最短，為 19百米。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點(diǎn)點(diǎn)連通 (即 :n1條邊 )。求解最小生成樹的破圈算法Page 55v1v2 v4v5v64352 158 78破圈法 ：任取一圈，去掉圈中最長邊，直到無圈。v1v2v3v4v5v1v2v3v4v5G1 G2 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 46abcfedhgbfed 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 47abcfedhgbfdg 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 48bcedabcfedhg 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 49abchabcfedhg 最小生成樹問題最小生成樹問題l 圖的生成樹（支撐樹）Page 50a
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1