[小學(xué)教育]第7講圖與網(wǎng)絡(luò)模型(編輯修改稿)
2024-11-12 18:12 本頁面
【文章內(nèi)容簡(jiǎn)介】 擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（ vi,vj）的流量 cij（容量）也是不一樣的。 cij的單位為萬加侖 /小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地 v7運(yùn)送石油，問每小時(shí)能運(yùn)送多少加侖石油？ v5 6 3 5 2 2 2 4 1 2 6 3 v1 v2 v7 v4 v3 v6 圖 1126 管 理 運(yùn) 籌 學(xué) 19 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 。 1 , 2 , 70 , 1 , 2 , , 6 。 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ù) ：約 束 條 件 ：管 理 運(yùn) 籌 學(xué) 20 167。 4 最大流問題 在這個(gè)線性規(guī)劃模型中，其約束條件中的前 6個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。其后面幾個(gè)約束條件表示對(duì)每一條弧(vi,vj)的流量 fij要滿足流量的可行條件，應(yīng)小于等于弧 (vi,vj)的容量 cij，并大于等于零，即 0≤ fij≤ cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 {fij}稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。 我們把例 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運(yùn)籌學(xué)軟件”，馬上得到以下的結(jié)果： f12=5， f14=5， f23=2，f25=3， f43=2， f46=1， f47=2， f35=2， f36=2， f57=5， f67=3。最優(yōu)值（最大流量） =10。 管 理 運(yùn) 籌 學(xué) 21 167。 4 最大流問題 二、最大流問題網(wǎng)絡(luò)圖論的解法 對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖 : (a)和 (b)、 (c)和 (d)的意義相同。 用以上方法對(duì)例 6的圖的容量標(biāo)號(hào)作改進(jìn)，得下圖 vi vj vi vj cij 0 （ a） （ b） cij cij vi vj （ cji） （ c） vi vj cij cji （ d） 6 3 5 2 2 2 4 1 2 6 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 0 0 0 0 0 管 理 運(yùn) 籌 學(xué) 22 167。 4 最大流問題 求最大流的基本算法 （ 1）找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。 （ 2）找出這條路上各條弧的最小的順流的容量 pf，通過這條路增加網(wǎng)絡(luò)的流量 pf。 （ 3）在這條路上，減少每一條弧的順流容量 pf ，同時(shí)增加這些弧的逆流容量 pf，返回步驟（ 1）。 用此方法對(duì)例 6求解： 第一次迭代：選擇路為 v1 v4 v7 ?；。? v4 , v7 ）的順流容量為 2， 決定了 pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 6 3 5 2 2 2 4 1 2 6 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 0 0 0 0 0 4 2 0 2 管 理 運(yùn) 籌 學(xué) 23 167。 4 最大流問題 第二次迭代：選擇路為 v1 v2 v5 v7 。?。? v2 , v5 ）的順流容量為 3，決定了 pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 第三次迭代：選擇路為 v1 v4 v6 v7 ?；。? 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 管 理 運(yùn) 籌 學(xué) 24 第四次迭代：選擇路為 v1 v4 v3 v6 v7 。?。? v3 , v6 ）的順流容 量為 2，決定了 pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 第五次迭代：選擇路為 v1 v2 v3 v5 v7 ?；。? v2 , v3 ）的順流容 量為 2，決定了 pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖： 2 2 2 4 3 v1 v2 v5 v7 v4 v3 v6 1 0 0 0 0 1 2 0 3 2 0 3 3 3 5 0 3 1 2 0 0 2 3 1 3 2 2 v1 v2 v5 v7 v4 v3 v6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1