運(yùn)籌學(xué)基礎(chǔ)圖論方法(已修改)
2025-05-12 12:05 本頁(yè)面
【正文】 167。 最大流量問(wèn)題 當(dāng)以物體、能量或信息等作為流量流過(guò)網(wǎng)絡(luò)時(shí)，怎樣使流過(guò)網(wǎng)絡(luò)的流量最大，或者使流過(guò)網(wǎng)絡(luò)的流量費(fèi)用或時(shí)間最小。通常把設(shè)計(jì)為樣的流量模型問(wèn)題，叫做網(wǎng)絡(luò)的流量問(wèn)題。 本節(jié)主要討論最大流量問(wèn)題。即在一定條件下，要求 流過(guò)網(wǎng)絡(luò)的流量為最大 。 1 2 3 4 6 5 6 5 3 4 7 5 7 3 2 在有一個(gè) 起點(diǎn) 和一個(gè) 終點(diǎn) 的網(wǎng)絡(luò)中，最大流量問(wèn)題是企圖找出，在一定時(shí)期內(nèi)，能在起點(diǎn)進(jìn)入，并通過(guò)這個(gè)網(wǎng)絡(luò)，在終點(diǎn)輸出的最大流量。 (一 ) 網(wǎng)路的最大流的相關(guān)概念 s t 5 3 4 2 4(0) 3(0) 2(0) 1(0) 1(0) 5(0) 3(0) 2(0) 5(0) ? 定義網(wǎng)路上支路的 容量 為其最大通過(guò)能力 ,記為 cij ,支路上的實(shí)際 流量 記為 fij ? 圖中規(guī)定一個(gè)發(fā)點(diǎn) s，一個(gè)收點(diǎn) t cij( fij ) ? 容量限制條件： 0≤fij ≤cij，當(dāng)支路上 fij = cij，稱(chēng)為 飽和弧 ? 平衡條件： ??????????? ????tifvtsisifvffijij vBvjivAvij)(,0)()()(vi A(vi) B(vi) ? 滿足上述條件的網(wǎng)路流稱(chēng)為可行流，總存在最大可行流 （二）截集與截集容量 s t 4 2 3 1 9(4) 6(1) 9(9) 2(0) 5(4) 7(5) 8(8) 10(8) 5(5) 截集 ： 把網(wǎng)路中的發(fā)點(diǎn)和收點(diǎn)分開(kāi)，并使 s→t 的流中斷的正向弧的集合，也叫做 割 。 ? 福特 富克森定理 ： 網(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 流。 ? 若在當(dāng)前可行流下再也找不到增廣鏈，則已得到最大流 ! ? 增廣鏈 是從發(fā)點(diǎn)到收點(diǎn)的一條鏈，該鏈上所有指向?yàn)?s→t 的 前向弧 ，存在 f＜ c； 所有指向?yàn)?t→s 的 后向弧 ， 存在 f＞ 0， 這樣的鏈叫增廣鏈。 ? 基本算法：找一條從 s 到 t 點(diǎn)的增廣鏈。 s t 5 4 3 2 3(0) 5(3) 1(1) 5(1) 1(1) q s2 = 4 q 5t = 2 q 45 = 3 q 43 = 1 q 32 = 1 增廣量 q = min q ij = min (4,1,1,3,2)= 1 s t 5 4 3 2 3(1) 5(4) 1(0) 5(2) 1(0) ? 增廣過(guò)程： 前向弧 f39。ij=fij+θ, 后向弧 f39。ij=fij –θ,增廣后仍是可行流 ????? ?? 后向弧 前向弧ijijijij ffcq欲求增廣
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1