運(yùn)籌學(xué)chap6網(wǎng)絡(luò)優(yōu)化模型-全文預(yù)覽
【正文】 流。 ijij cf ?}{ ijff ?sv ),0( ??iv iv),( ji vv ijij cf ? ))(,( ji vlvjv}),(m i n {)( ijijij fcvlvl ??jv),( ij vv}),(m i n {)( jiij fvlvl ? iv 0?ijfjvtv))(,( ji vlv?sv求最大流的標(biāo)號(hào)算法 tv0?jif?求最大流的標(biāo)號(hào)算法 2．調(diào)整過(guò)程 由收點(diǎn) 標(biāo)號(hào)算出的 作為調(diào)整量（即 ）。如果 ，則 不標(biāo)號(hào)。 1．標(biāo)號(hào)過(guò)程 在這個(gè)過(guò)程中，網(wǎng)絡(luò)中的點(diǎn)或是標(biāo)號(hào)點(diǎn)或是未標(biāo)號(hào)點(diǎn)。直觀上說(shuō)，截集是從 vs到 vt的必經(jīng)之道。 ? 割集的容量是割集中所有弧的容量的總和。將會(huì)看到利用圖的特點(diǎn)，解決這個(gè)問(wèn)題的方法較之線性規(guī)劃的一般方法要方便、直觀得多。比如令所有弧的流量 fij=0，就得到一個(gè)可行流 (稱(chēng)為零流 )。 因?yàn)閷?duì)于每個(gè)點(diǎn)，運(yùn)出這點(diǎn)的產(chǎn)品總量與運(yùn)進(jìn)這點(diǎn)的產(chǎn)品總量之差，是這點(diǎn)的凈輸出量，簡(jiǎn)稱(chēng)為是這一點(diǎn)的流量； 由于中間點(diǎn)只起轉(zhuǎn)運(yùn)作用，所以中間點(diǎn)的流量必為零。 15 6 10 4 6 10 15 0 可行流 ? 網(wǎng)絡(luò)流的兩個(gè)條件： 每個(gè)弧的流量不能超過(guò)該弧的最大通過(guò)能力，即 容量； 中間支點(diǎn)的流量為零。為了減少運(yùn)行時(shí)間，提高服務(wù)質(zhì)量以及最大化利用公司的車(chē)隊(duì)，管理方希望出租車(chē)司機(jī)盡可能地選擇最短路線。 ?按求解最短路的計(jì)算方法， ?｛ v1， v3， v6｝及｛ v1， v4， v6｝均為最短路，即有兩個(gè)最優(yōu)方案。 ? 又如決定在第一、三、五年各購(gòu)進(jìn)一臺(tái)，這個(gè)方案的設(shè)備購(gòu)置費(fèi)為 11+12+13=36，維修費(fèi)為5+6+5+6+5=27?，F(xiàn)在的問(wèn)題是如何制定一個(gè)幾年之內(nèi)的設(shè)備更新計(jì)劃，使得總的支付費(fèi)用最少。 ? 這樣從 v1到 v8的最短鏈為 (v1， v3， v2， v5， v9， v8)，總權(quán)為 11。 P(1)=0 T(3)=+∞ T(2)=+∞ 3 T(5)=+∞ P 6 4 T(4)=+∞ T(6)=+∞ P 7 P8 PPP(6)=8 P(5)=6 P(3)=3 P(1)=0 ? Dijkstra方法 的基本思想： ? 從 vs出發(fā)，逐步向外探尋最短路。 他希望在今后 5年內(nèi)的凈費(fèi)用最?。?即：凈費(fèi)用 =購(gòu)買(mǎi)價(jià) +維護(hù)價(jià) 售出價(jià) ） 。 2 8 7 3 9 6 5 6 5 7 單位：十萬(wàn)元 6 V1 V2 V3 V5 V4 V6 從一特殊的節(jié)點(diǎn)出發(fā)，找出從該節(jié)點(diǎn)到網(wǎng)絡(luò)中任何其它節(jié)點(diǎn)的最短路徑問(wèn)題 某人買(mǎi)了一輛價(jià)值 12021美元的新車(chē) ， 一輛車(chē)每年的維護(hù)費(fèi)用依賴(lài)于年初時(shí)的車(chē)齡 ， 具體費(fèi)用見(jiàn)下表 。（每步中，若有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條）。 在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。一棵生成樹(shù)所有樹(shù)枝上權(quán)的總和，稱(chēng)為這個(gè)生成樹(shù)的權(quán)。 ? 去掉任一條邊，則樹(shù)成為不連通圖。節(jié)點(diǎn) 1表示管道的起點(diǎn)，節(jié)點(diǎn) 6表示管道的終點(diǎn)，節(jié)點(diǎn) 2到 5表示中轉(zhuǎn)站，旁邊的數(shù)字表示該段管道能通過(guò)的最大輸送量。 ? 與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，我們經(jīng)常稱(chēng)之為 權(quán) ，權(quán)可以代表如距離、費(fèi)用、容量等。 連通圖 一個(gè)圖中任意兩點(diǎn)間至少有一個(gè)鏈相連，則稱(chēng)此圖為連通圖。 ? 例如，如果球隊(duì) v1勝了球隊(duì) v2，可以從 v1引一條帶箭頭的連線到 v2 ? 類(lèi)似勝負(fù)這種非對(duì)稱(chēng)性的關(guān)系，在生產(chǎn)和生活中是常見(jiàn)的，如交通運(yùn)輸中的“單行線”，部門(mén)之間的領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)的關(guān)系，一項(xiàng)工程中各工序之間的先后關(guān)系等。 比賽情況圖 圖 63 ? 關(guān)系的對(duì)稱(chēng)性和非對(duì)稱(chēng)性： ? 幾個(gè)例子中涉及到的對(duì)象之間的“關(guān)系”具有“對(duì)稱(chēng)性”，就是說(shuō)，如果甲與乙有這種關(guān)系，那么同時(shí)乙與甲也有這種關(guān)系。 鐵路交通示意圖 圖 62 圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。 一、 圖的基本概念 ? 人們?yōu)榉从骋恍?duì)象之間關(guān)系時(shí)，常會(huì)用示意圖。圖 81(a) 圖 61 ? 歐拉在 1736年發(fā)表了圖論方面的第一篇論文，解決了著名的哥尼斯堡 七橋問(wèn)題 。 ?一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的路線走，所走的路程最短。 第六章 圖與網(wǎng)絡(luò)優(yōu)化模型 第一節(jié) 圖與網(wǎng)絡(luò) ? 運(yùn)籌學(xué)的重要分支 ? 主要應(yīng)用領(lǐng)域：物理學(xué)、化學(xué)、控制論、信息論、科學(xué)管理、電子計(jì)算機(jī)等 ? 圖論理論和方法應(yīng)用實(shí)例： ?在組織生產(chǎn)中，為完成某項(xiàng)生產(chǎn)任務(wù)，各工序之間怎樣銜接，才能使生產(chǎn)任務(wù)完成得既快又好。當(dāng)時(shí)那里的居民熱衷于這樣的問(wèn)題：一個(gè)散步者能否走過(guò)七座橋，且每座橋只走過(guò)一次，最后回到出發(fā)點(diǎn)。歐拉證明了這是不可能的，因?yàn)閳D 61(b)中的每個(gè)點(diǎn)都只與奇數(shù)條線相關(guān)聯(lián)，不可能將這個(gè)圖不重復(fù)地一筆畫(huà)成。 ? 其他示意圖的例子 ?電話線分布圖、煤氣管道圖、航空線圖等。為了反映這個(gè)情況，可以用點(diǎn)分別代表這五個(gè)隊(duì)，某兩個(gè)隊(duì)之間比賽過(guò)，就在這兩個(gè)隊(duì)所相應(yīng)的點(diǎn)之間聯(lián)一條線，這條線不過(guò)其他的點(diǎn)，如圖 63所示。為了反映這一類(lèi)關(guān)系，可以用一條帶箭頭的連線表示。 環(huán) 連接 a點(diǎn)與 b點(diǎn)的一條鏈，如果 a與 b是同一個(gè)點(diǎn)時(shí)，稱(chēng)此鏈為環(huán)。 或 二、網(wǎng)絡(luò) ? 點(diǎn)或邊帶有某種數(shù)量指標(biāo)的圖叫 網(wǎng)絡(luò)圖 ，簡(jiǎn)稱(chēng) 網(wǎng)絡(luò) 。 ? 一個(gè)輸油管道網(wǎng)。 ? 例 1 某工廠的組織機(jī)構(gòu)如下所示 工廠組織機(jī)構(gòu)圖 樹(shù)的性質(zhì) ： ? 任意兩頂點(diǎn)之間必有一條且僅有一條鏈。 1 3 2 5 4 6 4 3 3 2 3 2 2 最小生成樹(shù)不一定唯一 最小生成樹(shù)： 設(shè)有一連通圖 G=(V,L),對(duì)于每一邊 e=(vi,vj)，有一個(gè)權(quán) wij≥0。 v1 3 3 1 7 2 8 5 4 10 3 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1