運(yùn)籌學(xué)基礎(chǔ)圖論方法-預(yù)覽頁
【正文】 不標(biāo)號(hào)（即此路不通） ； (4) (j, i)是后向弧，若 fji0，則節(jié)點(diǎn) j 標(biāo)號(hào)為 [i?, θ(j)]，表示從節(jié)點(diǎn) j 流向 i， 可增廣 θ(j)=min[θ(i), fji] ； 最大流最小截集的標(biāo)號(hào)法步驟 重復(fù)步驟 2，可能出現(xiàn)兩種情況： (1)節(jié)點(diǎn) t 獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn) t 標(biāo)號(hào)回溯可找出該增廣鏈；到第二步 (2) 節(jié)點(diǎn) t 尚未標(biāo)號(hào)，但無法繼續(xù)標(biāo)記，說明網(wǎng)路中已不存在增廣鏈，當(dāng)前流 v(f) 就是最大流； 所有獲標(biāo)號(hào)的節(jié)點(diǎn)在 V 中， 未獲標(biāo)號(hào)節(jié)點(diǎn)在 中， V 與 間的弧即為最小截集，最小截集容量即為該網(wǎng)絡(luò) 最大流量 ； 算法結(jié)束 VV最大流最小截的標(biāo)號(hào)法步驟 第二步：增廣過程 對(duì) 增廣鏈中的前向弧，令 f?=f +q (t)， q(t) 為節(jié)點(diǎn) t 的標(biāo)記值 對(duì) 增廣鏈中的后向弧，令 f?=f?q (t) 非增廣鏈上的所有支路流量保持不變 第三步：抹除圖上所有標(biāo)號(hào)，回到第一步 以上算法是按廣探法描述的，但在實(shí)際圖上作業(yè)時(shí)，按深探法進(jìn)行更快捷 ? 一次只找一條增廣鏈，增廣一次換一張圖 ? 最后一次用廣探法，以便找出最小截集 最大流最小截集的標(biāo)號(hào)法舉例 s t 4 2 3 1 9(4) 6(1) 9(9) 2(0) 5(4) 7(5) 8(8) 10(8) 5(5) (s+,?) (s+,2) (2,2) (1+,2) (3,1) (4+,1) 第一條鏈： (s+,?)→ (s+,2) → (2,2) → (1+,2) → (3,1) → (4+,1) q = 1 前向弧 f39。 ? 若在當(dāng)前可行流下再也找不到增廣鏈，則已得到最大流 ! ? 增廣鏈 是從發(fā)點(diǎn)到收點(diǎn)的一條鏈，該鏈上所有指向?yàn)?s→t 的 前向弧 ，存在 f＜ c； 所有指向?yàn)?t→s 的 后向弧 ， 存在 f＞ 0， 這樣的鏈叫增廣鏈。即在一定條件下，要求 流過網(wǎng)絡(luò)的流量為最大 。167。 本節(jié)主要討論最大流量問題。 ? 福特 富克森定理 ： 網(wǎng)路的最大流等于最小截集容量 ? 一般包含 s 點(diǎn)的成分中的節(jié)點(diǎn)集合用 V表示，包含 t 點(diǎn)的成分中的節(jié)點(diǎn)集合用 表示 V? 截集容量 是指截集中弧的容量之和 V 截集 截集容量Vs 1 , 2 , 3 , 4 , t ( s , 1 ) ( s , 2 ) 15s , 1 2 , 3 , 4 , t ( s , 2 ) ( 1 , 2 ) ( 1 , 3 ) 21s , 2 1 , 3 , 4 , t ( s , 1 ) ( 2 , 4 ) 17s , 1 , 2 3 , 4 , t ( 1 , 3 ) ( 2 , 4 ) 18s , 1 , 3 2 , 4 , t ( s , 2 ) ( 1 , 2 ) ( 3 , 2 ) ( 3 , t ) 19s , 2 , 4 1 , 3 , t ( s , 1 ) ( 4 , 3 ) ( 4 , t ) 24s , 1 , 2 , 3 4 , t ( 2 , 4 ) ( 3 , t ) 14s , 1 , 2 , 4 3 , t ( 1 , 3 ) ( 4 , 3 ) ( 4 , t ) 25s , 1 , 2 , 3 , 4 t ( 3 , t ) ( 4 , t ) 15網(wǎng)路的最大流就是 最小截集容量 為 14 截集 1=｛（ s,1），（ s,2）｝ （三）確定網(wǎng)路最大流的標(biāo)號(hào)法 ? 從任一個(gè)初始可行流出發(fā)，如 0 流。ij=fij+θ, 后向弧 f39。ij=fij+θ 后向弧 f39。 最小費(fèi)用流量問題 實(shí)際物資調(diào)配問題，既要考慮流量通過各條弧時(shí)的容量限制，也需要考慮調(diào)動(dòng)費(fèi)用的節(jié)省，這就是 最小費(fèi)用流 要研究的問題。 s 3 2 t 1 (7,6) 0 (5,2) 0 (6,1) 0 (2,3) 0 (3,2) 0 (8,4) 0 (4,1) 0 (cij , bij ) fij 試求將發(fā)點(diǎn)物資調(diào)運(yùn)到收點(diǎn)（或從發(fā)點(diǎn)按最大流量調(diào)運(yùn)到收點(diǎn)），使總調(diào)運(yùn)費(fèi)用最小的問題
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1