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