運籌學圖與網(wǎng)絡(luò)ppt課件-資料下載頁
2025-05-12 13:31本頁面
【正文】 年內(nèi)購置費用和維修費用總的支付費用最小。 ? 已知：設(shè)備每年年初的價格表 ? 設(shè)備維修費如下表 年份 1 2 3 4 5 年初價格 11 11 12 12 13 使用年數(shù) 01 12 23 34 45 每年維修費用 5 6 8 11 18 ? 例 3的解：將問題轉(zhuǎn)化為最短路問題，如下圖： 用 vi表示“第 i年年初購進一臺新設(shè)備” ,?。?vi,vj）表示第 i年年初購進的 設(shè)備一直使用到第 j年年初。 ? 把所有弧的權(quán)數(shù)計算如下表： v1 v2 v3 v4 v5 v6 1 2 3 4 5 6 1 16 22 30 41 59 2 16 22 30 41 3 17 23 31 4 17 23 5 18 6 (繼上頁 ) 把權(quán)數(shù)賦到圖中，再用 Dijkstra算法求最短路。 最終得到下圖，可知， v1到 v6的距離是 53，最短路徑有兩條： v1 v3v6和 v1v4v6 v1 v2 v3 v4 v5 v6 16 22 30 41 59 16 22 30 41 31 23 17 18 17 23 V1 （ 0,s） v3 v4 (41,1) v5 v6 22 30 41 59 16 (22,1) 30 41 31 23 17 18 17 23 V2 （ 16,1） 16 (30,1) (53,3) (53,4) 網(wǎng)絡(luò)最大流問題 ? 所謂最大流問題就是在一定的條件下 ， 要求流過網(wǎng)絡(luò)的物流 、 能量流或信息流等流量為最大的問題 ， 在最大流問題中一般有如下規(guī)定： 1) 網(wǎng)絡(luò)有一個起點 υs和一個終點 υt 2) 網(wǎng)絡(luò)是有向網(wǎng)絡(luò) ， 即流有方向性 。 3) 在網(wǎng)絡(luò)各條弧上都有一個權(quán) ， 表示允許流過的最大流量 。 若以 bij表示由 υi到 υj的弧上允許流過的最大流量 ，以 xij表示實際流過該弧的流量 ， 則 0≤ xij ≤bij 4) 網(wǎng)絡(luò)中 ， 除起點 υs和終點 υt之外的任何頂點 ， 流入量總和應(yīng)該等于流出量的總和 。 一、最大流問題的數(shù)學模型 ???????????????????? ??ijijjijjjibx0tifs,ti0sifxxfMa x vs 10 11 6 5 4 7 3 9 15 vt v5 v3 v4 v2 二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進。為省去弧的方向，如下圖 : (a)和 (b)、 (c)和 (d)的意義相同。 vi vj vi vj cij 0 （ a） （ b） cij cij vi vj （ cji） （ c） vi vj cij cji （ d） 求最大流的基本算法 （ 1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。 （ 2）找出這條路上各條弧的最小的順流的容量 pf，通過這條路增加網(wǎng)絡(luò)的流量 pf。 （ 3）在這條路上，減少每一條弧的順流容量 pf ，同時增加這些弧的逆流容量 pf，返回步驟（ 1）。 例 6 某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這個網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（ vi,vj）的流量 cij（容量）也是不一樣的。 cij的單位為萬加侖 /小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地 v7運送石油，問每小時能運送多少加侖石油？ 6 3 5 2 2 2 4 1 2 6 3 v1 v2 v7 v4 v3 v6 迭代運算步驟請見演示 最小費用最大流問題 ? 最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，對每一條弧 （ vi,vj），除了給出容量 cij外，還給出了這條弧的單位流量的費用 bij，要 求一個最大流 F，并使得總運送費用最小。 一、最小費用最大流的數(shù)學模型 例 7 由于輸油管道的長短不一，所以在例 6中每段管道（ vi,vj ）除 了有不同的流量限制 cij外，還有不同的單位流量的費用 bij ， cij的單位為萬 加侖 /小時， bij的單位為百元 /萬加侖。如圖。從采地 v1向銷地 v7運送石 油，怎樣運送才能運送最多的石油并使得總的運送費用最?。壳蟪鲎畲罅? 量和最小費用。 (6,6) (3,4) (5,7) (2,5) (2,4) （ 2,3） (4,4) (1,3) (2,8) （ 3,2） v1 v2 v5 v7 v4 v3 v6 (6,3) 二、最小費用最大流的網(wǎng)絡(luò)圖論解法 對網(wǎng)絡(luò)上?。?vi,vj）的（ cij,bij）的表示作如下改動，用 (b)來表示 (a)。 vi vj vi vj （ cij,bij ） （ 0,bij ） （ a） （ b） （ cij,bij ） （ cij,bij ） vi vj （ cji,bji ） （ cij,bij ） vi vj （ cji,bji ） （ 0,bji) （ 0,bji) （ c） （ d）
教學課件相關(guān)推薦
鄂ICP備17016276號-1