圖與網(wǎng)絡(luò)ppt課件(2)-資料下載頁
2025-05-03 18:49本頁面
【正文】 流 F，并使得總運(yùn)送費(fèi)用最小。(6,6)(3,4) (5,7)(2,5)(2,4)（ 2,3） (4,4)(1,3)(2,8)（ 3,2）v1v2v5v7v4v3v6(6,3)22v1v2 v5v7v4v3v6123522 355 最小費(fèi)用最大流問題 例 8最大流問題可能有多種解法，如：12v1v2v5v7v4v3v6123632 345解 1解 2一、最小費(fèi)用最大流的數(shù)學(xué)模型 例 9. 由于輸油管道的長短不一，所以在例 6中每段管道（ vi,vj ）除了有不同的流量限制 cij外，還有不同的單位流量的費(fèi)用 bij ， cij的單位為萬加侖 /小時， bij的單位為百元 /萬加侖。如下圖所示。從采地 v1 向銷地 v7 運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大流量的最小費(fèi)用 ()。 最小費(fèi)用最大流問題(6,6)(3,4) (5,7)(2,5)(2,4)（ 2,3） (4,4)(1,3)(2,8)（ 3,2）v1v2v5v7v4v3v6(6,3) 第 1步，建立最大流的數(shù)學(xué)模型：一、一、最小費(fèi)用最大流的數(shù)學(xué)模型 最小費(fèi)用最大流問題 一、最小費(fèi)用最大流的數(shù)學(xué)模型 最小費(fèi)用最大流問題 第 2步，建立求最小費(fèi)用的數(shù)學(xué)模型：一、最小費(fèi)用最大流的數(shù)學(xué)模型 一般來說，所謂最小費(fèi)用流的問題就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對每條弧 (vi,vj)賦權(quán)以容量 cij及單位費(fèi)用 bij的網(wǎng)絡(luò)中， 求一個給定流量 f 的最小費(fèi)用 ，這個給定流量 f 應(yīng)小于等于最大流量 F，否則無解。 求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量 F改為 f即可。 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 對網(wǎng)絡(luò)上?。?vi,vj）的（ cij,bij）的表示作如下改動 最小費(fèi)用最大流問題vi vj（ cij,bij ） （ 0,bij ）（ b）vi vj（ a）（ cij,bij ）（ cij,bij ）vi vj（ cji,bji ）（ c）（ cij,bij ）vi vj（ cji,bji ）（ 0,bij)（ 0,bji)（ d） 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法用以上方法對例 9的圖形進(jìn)行改進(jìn)，得下圖：(6,6)(3,4) (5,7)(2,5) (0,4)（ 2,3） (4,4)(1,3)(2,8)（ 3,2）v1v2v5v7v4v3v6(6,3)(0,3)(0,8)(0,3)（ 0,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(0,4)（ 0,3）圖 1128 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法最小費(fèi)用最大流的基本算法： 在對弧的標(biāo)號作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法，與求最大流的算法基本一樣，不同的只是： **** 在步驟（ 1）中要選擇一條總的單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。用上述方法對例 9求解： ① 第一次迭代：找到最短路 v1 → v4 → v6 → v7。第一次迭代后總流量為 1，決定了 pf=1,總費(fèi)用為 10。v5(6,6)(3,4) (5,7)(2,5) (0,4)（ 2,3） (3,4)(0,3)(2,8)（ 3,2）v1v2v7v4v3v6(5,3)(1,3)(0,8)(1,3)（ 0,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(1,4)（ 0,3）圖 112911第一次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ② 第二次迭代：找到最短路 v1 → v4 → v7。第二次迭代后總流量為 3，總費(fèi)用 32。(6,6)(3,4) (5,7)(2,5) (0,4)（ 2,3） (3,4)(0,3)(0,8)（ 3,2）v1v2v5v7v4v3v6(3,3)(3,3)(2,8)(1,3)（ 0,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(1,4)（ 0,3）圖 113033第二次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ③ 第三次迭代：找到最短路 v1 → v4 → v3 → v6 → v7 。第三次迭代后總流量為 5，總費(fèi)用 56。(6,6)(3,4) (5,7)(2,5) (0,4)（ 0,3） (1,4)(0,3)(0,8)（ 1,2）v1v2v5v7v4v3v6(1,3)(5,3)(2,8)(1,3)（ 2,2）(0,6)(0,4)(0,5)（ 2,4） (0,7)(3,4)（ 2,3）圖 113155第三次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ④ 第四次迭代：找到最短路 v1 → v4 → v3 → v5 → v7 。第四次迭代后總流量為 6，總費(fèi)用 72。(6,6)(3,4) (4,7)(2,5) (1,4)（ 0,3） (1,4)(0,3)(0,8)（ 0,2）v1v2v5v7v4v3v6(0,3)(6,3)(2,8)(1,3)（ 3,2）(0,6)(0,4)(0,5)（ 1,4） (1,7)(3,4)（ 2,3）圖 113266第四次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ⑤ 第五次迭代：找到最短路 v1 → v2 → v5 → v7 。第五次迭代后總流量為 9，總費(fèi)用 123。(3,6)(0,4) (1,7)(2,5) (1,4)（ 0,3） (1,4)(0,3)(0,8)（ 0,2）v1v2v5v7v4v3v6(0,3)(6,3)(2,8)(1,3)（ 3,2）(3,6)(3,4)(0,5)（ 1,4） (4,7)(3,4)（ 2,3）圖 113399 第五次迭代后的總流量 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 ⑥ 第六次迭代：找到最短路 v1 → v2 → v3 → v5 → v7 。第六次迭代后總流量為 10，總費(fèi)用 145。已經(jīng)找不到從 v1到 v7的每條弧容量都大于零的路了，故已求得最小費(fèi)用最大流。(2,6)(0,4) (0,7)(1,5) (2,4)（ 0,3） (1,4)(0,3)(0,8)（ 0,2）v1v2v5v7v4v3v6(0,3)(6,3)(2,8)(1,3)（ 3,2）(4,6)(3,4)(1,5)（ 0,4） (5,7)(3,4)（ 2,3）圖 1134 最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法 如果對例 7求一個最小費(fèi)用流的問題：每小時運(yùn)送 6萬加侖石油從 v1到v7的最小費(fèi)用是多少，或者每小時運(yùn)送 7萬加侖呢？ 我們可以從第四次迭代及圖 1132即可得到運(yùn)送 6萬加侖最小費(fèi)用 72百元，其運(yùn)送方式通過比較圖 1128及圖 1132即得圖 1136所示。 至于每小時運(yùn)送 7萬加侖，我們可以在圖 1136的基礎(chǔ)上，再按第五次迭代所選的最短路運(yùn)送 1萬加侖即得最小費(fèi)用： 72+1*17=89百元，其運(yùn)送方式如圖 1135所示。3 512 31 26v1v2v5v4v3v61034 2 v7 10第六次迭代后總流量圖 1135 12 31 26v1v2v5v4v3v6631 v7圖 11361 22 31 26v1v2v5v4v3v631 1 v7圖 11371117本章完第 九 章 目標(biāo)規(guī)劃教材 P255256 ： 1。 2。 3 。 4 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1