[小學(xué)教育]第7講圖與網(wǎng)絡(luò)模型-文庫吧資料
2024-10-22 18:12本頁面
【正文】 v7 v4 v3 v6 1 0 1 2 0 2 0 3 3 3 5 0 1 2 0 2 3 1 3 1 5 0 0 2 0 2 0 5 167?；。? v4 , v6 ）的順流容量為 1，決定了 pf=1，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 6 3 5 2 2 2 4 1 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 0 0 4 2 0 2 2 0 3 3 3 0 3 2 2 2 4 1 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 4 2 0 2 2 0 3 3 3 3 3 0 1 3 管 理 運 籌 學(xué) 24 第四次迭代：選擇路為 v1 v4 v3 v6 v7 。 4 最大流問題 第二次迭代：選擇路為 v1 v2 v5 v7 。 用此方法對例 6求解： 第一次迭代：選擇路為 v1 v4 v7 。 （ 2）找出這條路上各條弧的最小的順流的容量 pf，通過這條路增加網(wǎng)絡(luò)的流量 pf。 4 最大流問題 求最大流的基本算法 （ 1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。為省去弧的方向，如下圖 : (a)和 (b)、 (c)和 (d)的意義相同。 管 理 運 籌 學(xué) 21 167。 我們把例 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌學(xué)軟件”，馬上得到以下的結(jié)果： f12=5， f14=5， f23=2，f25=3， f43=2， f46=1， f47=2， f35=2， f36=2， f57=5， f67=3。其后面幾個約束條件表示對每一條弧(vi,vj)的流量 fij要滿足流量的可行條件，應(yīng)小于等于弧 (vi,vj)的容量 cij，并大于等于零，即 0≤ fij≤ cij。 1 , 2 , 712ij ijijm a x F = f ff f ff f f ff f f ff f ff f ff f f f ff c i jf i j???? ? ?? ? ?????? ? ? ?? ? ?? ? ?目 標(biāo) 函 數(shù) ：約 束 條 件 ：管 理 運 籌 學(xué) 20 167。 4 最大流問題 我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧 (vi,vj)上流量為 fij，網(wǎng)絡(luò)上的總的流量為 F，則有： ? ?? ?1412 23 2514 43 46 4723 43 35 3625 35 5736 46 6757 67 47 12 14, 1 , 2 , , 6 。 cij的單位為萬加侖 /小時。 一、最大流的數(shù)學(xué)模型 例 6 某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這個網(wǎng)絡(luò)的一部分如下圖所示。 v1 3 3 1 7 2 8 5 4 10 3 4 v7 v6 v5 v4 v2 v3 圖 1114 管 理 運 籌 學(xué) 18 167。 解：此問題實際上是求圖 1114的最小生成樹，這在例 4中已經(jīng)求得，也即按照圖 1113的 (f)設(shè)計，可使此網(wǎng)絡(luò)的總的線路長度為最短，為 19百米。 3 最小生成樹問題 例 4 用破圈算法求圖（ a）中的一個最小生成樹 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) 圖 1113 管 理 運 籌 學(xué) 17 167。 如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第 1步。 3 最小生成樹問題 一、求解最小生成樹的破圈算法 算法的步驟： 在給定的賦權(quán)的連通圖上任找一個圈。 最小生成樹問題就是指在一個賦權(quán)的連通的無向圖 G中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小。在圖 1112中，(b)和 (c)都是 (a)的生成子圖。 圖 1111 v1 v2 v3 v4 v5 v6 v7 v8 v9 v1 v2 v3 v5 v8 v7 v6 v4 v1 v2 v3 v4 v5 v7 v6 v8 v9 (a) (b) (c) 管 理 運 籌 學(xué) 14 167。 3 最小生成樹問題 ? 樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。 2 最短路問題 (繼上頁 ) 把權(quán)數(shù)賦到圖中，再用 Dijkstra算法求最短路。 2 最短路問題 例 3的解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用 vi表示“第 i年年初購進(jìn)一臺新設(shè)備” ,弧（ vi,vj）表示第 i年年初購進(jìn)的 設(shè)備一直使用到第 j年年初。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。如果購置新設(shè)備，就要支付一定的購置費，當(dāng)然新設(shè)備的維修費用就低。 2 最短路問題 例 3 設(shè)備更新問題。 V1 （甲地） 15 17 6 2 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1