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