【正文】 型都是針對這種情況的 . ?B. 假設(shè)工廠的產(chǎn)量有上下限 ?C. 工廠的產(chǎn)量 ∈ {0, [500,L i ]} ?我們這里只討論 A的情況 Page ? 54 線性費(fèi)用流網(wǎng)絡(luò)模型一 Page ? 55 線性費(fèi)用流網(wǎng)絡(luò)模型一 ?圖中邊上的 (A ,B ) ,A 表示邊的流量限制 ,B 表示邊的單位流量的費(fèi)用 , 下同 . ?1) 網(wǎng)絡(luò)有一個源點(diǎn) Sou rce, 從 Sou rce 到每個 S 點(diǎn)有一條邊 , 邊的流量限制為 S i 的最大產(chǎn)量 L i, 單位費(fèi)用為 S i 生產(chǎn)鋼管的單價 R i . ?2) 從 S i 到 A j 有一條邊 , 邊的流量限制為 + ∞, 單位費(fèi)用為SA P ij , 即從 S i 到 A j 運(yùn)輸單位長度鋼管的費(fèi)用 . ?3) 對于每一條要鋪設(shè)的管道 P , 設(shè)其長度為 L en, 兩端點(diǎn)為A j ,A k , 則 P 對應(yīng)著 L en 個點(diǎn) , 分別表示要鋪設(shè)的一個單位長度的鋼管 (如圖中 P 11, P 12, P 13) , 從 A j 到這 L en 個點(diǎn)各有一條邊 , 邊的流量限制為 1, 單位費(fèi)用分別為 1, 2, 3…,L en, 從 A k 到這 L en 個點(diǎn)也各有一條邊 , 邊的流量限制為 1, 單位費(fèi)用分別為 L en, L en 1, … 3, 2, 1. Page ? 56 線性費(fèi)用流網(wǎng)絡(luò)模型一 ?4) 從 3)中的點(diǎn) (代表每單位長度的鋼管的點(diǎn) )到圖的匯點(diǎn)Target 各有一條邊 , 流量限制為 1, 單位費(fèi)用為 0. ?這種流網(wǎng)絡(luò)模型最簡單 , 效率也較低 . 設(shè)鋪設(shè)的管道共有 T l 公里 , 顯然 T l n 與 m. ?網(wǎng)絡(luò)中的點(diǎn)數(shù)大約為 T l 個 , 邊數(shù)大約為 3 T l, 最大流量為T l . 標(biāo)準(zhǔn)的網(wǎng)絡(luò)流算法的時間復(fù)雜度為 O (V 3 M ax F low ) , 因此 , 這個模型的復(fù)雜度為 O (T l4). 對于題中的數(shù)據(jù) , T l 大約在 5000 左右 , T l4≈ 1015 ?不可承受 . ?優(yōu)點(diǎn)：可用標(biāo)準(zhǔn)的最小費(fèi)用最大流算法（如最小費(fèi)用路算法）來求解 . Page ? 57 最小費(fèi)用路算法 ?標(biāo)準(zhǔn)的最小費(fèi)用最大流算法 —— 最小費(fèi)用路算法 : ?Step 0: 取零流 f 為初始可行流 . ?Step 1: 如果 v (f ) = 最大流量 vmax , 則 f 為 D 中流值為 vmax的最小費(fèi)用流 。 否則轉(zhuǎn) Step 2。 ?Step 2: 構(gòu)造增量網(wǎng)絡(luò) D (f ). 如果 D (f )中不存在 (Sou rce, Target)路 , 則 D (f )中沒有流值為 vmax的可行流 , 停止 , 否則在 D (f )中找一條最小費(fèi)用路 U , 轉(zhuǎn) Step 3. ?Step 3: 用 c (U )表示 U 的容量 , 對 f 沿 U 增廣流值 , 增廣量為 c (U ) , 得到新流 f , 轉(zhuǎn) Step 1. Page ? 58 線性費(fèi)用流網(wǎng)絡(luò)模型二 ?模型一之所以效率低 , 最主要的問題是流網(wǎng)絡(luò)中的點(diǎn)太多了 . ?通過點(diǎn)的合并 , 可以大幅減小流網(wǎng)絡(luò)中點(diǎn)的個數(shù) . ? 將線性費(fèi)用流網(wǎng)絡(luò)模型一中對應(yīng)同一段要鋪設(shè)的管道的點(diǎn)合并成一個點(diǎn) (即模型一圖中的 P 11, P 12, P 13合并為 P 1) , 從 A 點(diǎn)到這些點(diǎn)的邊現(xiàn)在全部轉(zhuǎn)到一個點(diǎn)上 (如圖 ) , 從這些點(diǎn)到 T a rg et 的邊合并為流量限制為 P i (P i 即要鋪設(shè)的管道的長度 ) , 單位費(fèi)用為 0 的一條邊 . Page ? 59 線性費(fèi)用流網(wǎng)絡(luò)模型二 Page ? 60 線性費(fèi)用流網(wǎng)絡(luò)模型二 ?模型二中的點(diǎn)數(shù)為 n+ m + P coun t+ 2, 邊數(shù)大約為 2 T l 個 . ?均比模型一有了大幅減小 . 然而邊數(shù)仍然太多 , 而且這張流網(wǎng)絡(luò)不是一張簡單圖 (A 層與 P 層中兩個點(diǎn)之間的邊數(shù) 1) , 因此 , 不能直接套用標(biāo)準(zhǔn)最小費(fèi)用最大流的復(fù)雜度計算公式 . Page ? 61 非線性費(fèi)用流網(wǎng)絡(luò)模型 Page ? 62 非線性費(fèi)用流網(wǎng)絡(luò)模型 ?第三種模型是非線性費(fèi)用網(wǎng)絡(luò)流模型 . ?1) 模型中所有的點(diǎn)與模型二相同 。 ?2) 模型中除了 A 層與 P 層之間的邊以外 , 均與模型二相同 。 ?3) A 層與 P 層之間的邊的流量限制與模型二相同 , 但是沒有單位費(fèi)用的概念 , 因?yàn)橘M(fèi)用是非線性的 , ?費(fèi)用 = 流量 (流量 + 1)/ 2. Page ? 63 非線性費(fèi)用流網(wǎng)絡(luò)模型 ?最小費(fèi)用路算法在找最小費(fèi)用路時要用到邊的單位費(fèi)用 , 而非線性模型中的非線性費(fèi)用邊沒有單位費(fèi)用的概念 . 為此 , 將最小費(fèi)用路算法做一點(diǎn)修改 : ?上邊際費(fèi)用 定義為 : 流量增加 1, 非線性費(fèi)用邊的費(fèi)用的增加值 ?下邊際費(fèi)用定義為 : 流量減小 1, 非線性費(fèi)用邊的費(fèi)用的減小值 ?當(dāng)最小費(fèi)用路算法查詢正向流過這條邊的單位費(fèi)用時 , 用上邊際費(fèi)用作為單位費(fèi)用 。 ?當(dāng)最小費(fèi)用路算法查詢負(fù)向流過這條邊的單位費(fèi)用時 , 用下邊際費(fèi)用作為單位費(fèi)用 。 ?經(jīng)過這個修改 , 最小費(fèi)用路算法就能應(yīng)用于本題的非線性模型了 . 練習(xí) 學(xué)而時習(xí)之，不亦說乎 論語 學(xué)而 Page ? 65 練習(xí) 1 求下圖的 Hamilton回路 Page ? 66 某工廠使用一臺設(shè)備，每年年初工廠要作出決定：繼續(xù)使用，購買新的？如果繼續(xù)使用舊的，要付維修費(fèi)；若要購買一套新的，要付購買費(fèi)。試確定一個 5年計劃，使總支出最小。 若已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時的殘值與維修費(fèi)，如表 1所示 項目 第 1年 第 2年 第 3年 第 4年 第 5年 購買費(fèi) 11 11 12 12 13 機(jī)器役齡 01 12 23 34 45 維修費(fèi) 5 6 8 11 18 殘值 4 3 2 1 0 練習(xí) 2 設(shè)備更新問題 提示：建立圖模型求最短路