第九章-網(wǎng)絡(luò)優(yōu)化模型課件

教學(xué)要求：掌握圖論基礎(chǔ)，掌握最短路問題，最大流問題和最小費(fèi)用流問題等網(wǎng)絡(luò)優(yōu)化模型及其基本算法。會應(yīng)用模型和方法解決一些管理中的基本問題教學(xué)要求：掌握圖論基礎(chǔ)，掌握最短路問題，最大流問題和最小費(fèi)目錄圖與網(wǎng)絡(luò)樹最短路問題最大流問題最小費(fèi)用流問題第一節(jié)圖與網(wǎng)絡(luò)目錄第一節(jié)圖與網(wǎng)絡(luò)12341234一、圖的概念及分類圖是由作為研究對象的有限個集合和表達(dá)這些頂點之間關(guān)系的m條線的集合組成的,記頂點集合為V={v1,v2,……vn}，線集合為L={l1,l2,….lm}圖則記為G=(V，L)，線又分為弧和邊，頂點也稱為結(jié)點弧是由一對有序的頂點組成，表示兩個頂點之間可能運(yùn)動的方向取消弧的方向就變成了邊，邊是只要任兩點之間有連線，兩個方向均可使用，弧可作為城市道路的單行道，邊則是雙行道第一節(jié)圖與網(wǎng)絡(luò)12341234一、圖的概念及分類第一節(jié)圖與網(wǎng)絡(luò)頂點、弧、有向圖、無向圖、鏈、道路、環(huán)、連通圖、連通子圖、次的基本概念1234123412345213次道路頂點無向圖鏈有向圖弧環(huán)連通圖弧是由一對有序的頂點組成，表示了兩個頂點之間可能運(yùn)動的方向連通子圖

由頂點集和弧組成的圖稱為有向圖

由頂點集和邊組成的圖稱為無向圖

鏈有一序列弧，如果每一個弧與前一個弧恰有一個公共頂點，則稱這一序列弧為一個鏈。

道路如果鏈中每一個弧的終點是下面一個弧的起點，則這個鏈稱為一個道路。

環(huán)連接a點與b點的一條鏈，如果a與b是同一個點時，稱此鏈為環(huán)。

連通圖一個圖中任意兩點間至少有一個鏈相連，則稱此圖為連通圖。

任何一個不連通圖都可以分為若干個連通子圖，每一個子圖稱為原圖的一個分圖。

次:以a點為頂點的邊的條數(shù)稱為頂點的次

第一節(jié)圖與網(wǎng)絡(luò)頂點、弧、有向圖、無向圖、鏈、道路、環(huán)、連通圖、連通子圖、次點或邊帶有某種數(shù)量指標(biāo)的圖叫網(wǎng)絡(luò)圖，簡稱網(wǎng)絡(luò)。與點或邊有關(guān)的某些數(shù)量指標(biāo)，我們經(jīng)常稱之為權(quán)，權(quán)可以代表如距離、費(fèi)用、容量等。左圖可以看作：從發(fā)電廠（節(jié)點1）向某城市（節(jié)點6）輸送電力，必須通過中轉(zhuǎn)站（節(jié)點2，3，4，5）轉(zhuǎn)送，邊上數(shù)字代表兩節(jié)點間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。一個輸油管道網(wǎng)。節(jié)點1表示管道的起點，節(jié)點6表示管道的終點，節(jié)點2到5表示中轉(zhuǎn)站，旁邊的數(shù)字表示該段管道能通過的最大輸送量。應(yīng)怎樣安排輸油線路，使從節(jié)點1到節(jié)點6的總輸送量最大？一張城市分布圖?，F(xiàn)在要在各城市之間架設(shè)電話線，應(yīng)如何架設(shè)，使各城市之間既能通話，又使總的架設(shè)路線最短？二、網(wǎng)絡(luò)第一節(jié)圖與網(wǎng)絡(luò)點或邊帶有某種數(shù)量指標(biāo)的圖叫網(wǎng)絡(luò)圖，簡稱網(wǎng)絡(luò)。左圖可以看作一、樹：連通且不含環(huán)的無向圖

樹的性質(zhì)：任意兩頂點之間必有一條且僅有一條鏈。去掉任一條邊，則樹成為不連通圖。不相鄰的兩個頂點間添上一條邊，恰好得到一個環(huán)。如果樹有n個結(jié)點，則邊的數(shù)目剛好為n-1第二節(jié)樹一、樹：連通且不含環(huán)的無向圖樹的性質(zhì)：第二節(jié)樹部分圖生成子圖部分樹如果V1V，E1E則稱G1為G的部分圖；設(shè)G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1V，,則稱G1為G的生成子圖；如果G=(V，E)的部分圖G1=(V，E1)是樹，則稱G1為G的一個部分樹。二、部分圖、生成子圖、部分樹第二節(jié)樹部分圖生成子圖部分樹如果V1V，E1E則稱G1為求連通圖部分樹的方法(1)破圈法：在G中任取一個圈，去掉圈中的任何一條邊，對余下的圖重復(fù)這一步，直到無圈為止，最后得到一棵部分樹第二節(jié)樹求連通圖部分樹的方法第二節(jié)樹求連通圖部分樹的方法(2)避圈法：在G中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，然后再找一條與{e1,e2}不構(gòu)成圈的邊e3、、、直到無邊可選為止V1V3V2V5V4V6e1e2e3e6e7e5e8e8e4第二節(jié)樹求連通圖部分樹的方法V1V3V2V5V4V6e1e2e3e61325464332322最小生成樹不一定唯一三、最小生成樹：設(shè)有一連通圖G=(V，L)，對于每一條邊e=(vi,vj),有一個權(quán)wij，一棵生成樹所有樹枝上權(quán)的總和，稱為這個生成樹的權(quán)，具有最小權(quán)的生成樹稱為最小生成樹，簡稱最小樹第二節(jié)樹1325464332322最小生成樹不一定唯一三、最小生成樹(1)最小生成樹的求法破圈法:每一步任找一個圈，劃去權(quán)值為最大的邊，直到圖中沒圈為止，即得最小樹V1V3V2V5V4V6651532447第二節(jié)樹(1)最小生成樹的求法V1V3V2V5V4V66515324(2)最小生成樹的求法避圈法:每一步從未選的邊中，選一條權(quán)值最小的邊，使已選出的邊不構(gòu)成圈直至不能進(jìn)行為止，即得最小樹V1V3V2V5V4V6651532447第二節(jié)樹(2)最小生成樹的求法V1V3V2V5V4V66515324V1V4V2V5V7V864523854V3V64543637練習(xí)：用破圈法或避圈法求下圖的最小生成樹，并指出其權(quán)重和

第二節(jié)樹V1V4V2V5V7V864523854V3V6454363避圈法：V1V4V2V5V7V864523854V3V64543637最小生成樹如上圖紅線所示，最小權(quán)重為：4+3+3+3+4+5+2=24第二節(jié)樹避圈法：V1V4V2V5V7V864523854V3V645破圈法：V1V4V2V5V7V864523854V3V64543637最小生成樹如上圖所示，最小權(quán)重為：4+3+3+3+4+5+2=24第二節(jié)樹破圈法：V1V4V2V5V7V864523854V3V645練習(xí)：下圖是6個城市的交通圖，為將部分道路改造成高速公路，使各個城市均能通達(dá)，又要使高速公路的總長度最小，應(yīng)如何做使總長度最小,總長度是多少?第二節(jié)樹練習(xí)：第二節(jié)樹避圈法求解：第二節(jié)樹最優(yōu)改造路線如上圖紅線所示，最短路徑為：1400避圈法求解：第二節(jié)樹最優(yōu)改造路線如上圖紅線所示，求下面兩個連通圖的最小生成樹：第二節(jié)樹求下面兩個連通圖的最小生成樹：第二節(jié)樹第二節(jié)樹第二節(jié)樹某地有10個村莊，它們之間的交通道路如下圖所示，圖中邊旁權(quán)為道路長度(單位：百米)，現(xiàn)在要沿道架設(shè)電線，實現(xiàn)村村通電話工程，問應(yīng)如何架設(shè)電線才能使總長度最短？第二節(jié)樹某地有10個村莊，它們之間的交通道路如下圖所示，第二節(jié)樹解：本題實質(zhì)是最小樹問題，利用避圈法可求得最短路線，如下圖粗線所示：最優(yōu)架設(shè)路線如上圖粗線所示，架設(shè)電線最短長度為18(百米)。第二節(jié)樹解：本題實質(zhì)是最小樹問題，利用避圈法可求得最短路線，最優(yōu)架設(shè)某大學(xué)準(zhǔn)備對其所屬的7個學(xué)院辦公室計算機(jī)聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖所示，圖中vi表示7個學(xué)院辦公室，圖中的邊為可能聯(lián)網(wǎng)的途徑，邊上的所賦的權(quán)數(shù)為這條路線的長度，單位為百米，請設(shè)計一個網(wǎng)絡(luò)能聯(lián)系7個學(xué)院辦公室，并使總的線路長度為最短V1V6V5104873V2V7335V4V3124某大學(xué)準(zhǔn)備對其所屬的7個學(xué)院辦公室計算機(jī)聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能V1V6V5104873V2V7335V4V312破圈法求解：4最短路徑如上圖所示，最短為：19百米V1V6V5104873V2V7335V4V312破圈法求解V1V6V5104873V2V7335V4V312避圈法求解：最短路徑如上圖所示，最短為：19百米4V1V6V5104873V2V7335V4V312避圈法求解圖與網(wǎng)絡(luò)樹最短路問題最大流問題最小費(fèi)用流問題第三節(jié)最短路問題圖與網(wǎng)絡(luò)第三節(jié)最短路問題特點：從一特殊的節(jié)點出發(fā)，找出從該節(jié)點到網(wǎng)絡(luò)中任何其它節(jié)點的最短路徑問題某人買了一輛價值1200美元的新車，一輛車每年的維護(hù)費(fèi)用依賴于年初時的車齡，具體費(fèi)用見下表。為了避免舊車的高維護(hù)費(fèi)用，他決定賣掉舊車買新車。舊車的價格依賴于交易時的車齡，見下表。為計算簡單起見，假設(shè)任何時間新車的價格不變均為1200美元。他希望在今后5年內(nèi)的凈費(fèi)用最?。矗簝糍M(fèi)用=購買價+維護(hù)價-售出價）。

2112第三節(jié)最短路問題特點：從一特殊的節(jié)點出發(fā)，找出從該節(jié)點到網(wǎng)絡(luò)中任何其它節(jié)點的結(jié)點i表示第i年的年初，當(dāng)i<j時，弧(i,j)表示第i年年初購買一輛新車并一直用到第j年年初。弧的長度cij表示：如果第i年年初購買一輛新車并這輛車在第j年年初賣掉更換一輛新新，從第i年年初到第j年年初期間總的凈費(fèi)用，于是有cij=(i,i+1,..j-1年的維護(hù)費(fèi)用）＋（第i年年初購買新車的費(fèi)用）－（第j年年初該車的交易費(fèi)用）1234567777712121221313144122121第三節(jié)最短路問題結(jié)點i表示第i年的年初，當(dāng)i<j時，弧(i,j)表示第i年年c12=2+12-7=7c13=2+4+12-6=12c14=2+4+5+12-2=21c15=2+4+5+9+12-1=31c16=2+4+5+9+12+12-0=44c23=2+12-7=7c24=2+4+12-6=12c25=2+4+5+12-2=21c26=2+4+5+9+12-1=31c34=2+12-7=7c35=2+4+12-6=12c36=3+4+5+12-2=21c45=2+12-7=7c46=2+4+12-6=12c56=2+12-7=71234567777712121221313144122121第三節(jié)最短路問題c12=2+12-7=7c13=2+4+12-6=121Dijkstra最短路算法：假設(shè)每個弧的權(quán)是非負(fù)的，即wij≥0，給每個支點vi記一個數(shù)(稱標(biāo)號)，標(biāo)號分臨時性標(biāo)號T和永久性標(biāo)號P，永久性標(biāo)號表示從v1到該點vi的最短路權(quán)，得到永久性標(biāo)號的不再改變標(biāo)號，臨時性標(biāo)號表示從開始點v1到該點vi的最短路權(quán)的上界，算法每一步都把某一點的T標(biāo)號改為P標(biāo)號，開始時給初始支點v1標(biāo)號記為0，即P(v1)=0，其他支點(記為臨時性標(biāo)號)的標(biāo)號記為+∞，即T(vi)=+∞,若vi點是剛得到P標(biāo)號的點，考慮L中與vi點相連的弧(vi,vj)且vj是T標(biāo)號，對vj的標(biāo)號進(jìn)行如下更改：T(vj)=min{T(vj),P(vi)+Wij}比較所有具有T標(biāo)號的點，把最小者改為P標(biāo)號，當(dāng)存在兩個以上最小者時，可以同時改為P標(biāo)號，直到全部點均改為P標(biāo)號為止第三節(jié)最短路問題Dijkstra最短路算法：假設(shè)每個弧的權(quán)是非負(fù)的，即wij

例：從發(fā)電廠（記為節(jié)點1）向某城市（記為節(jié)點6）輸送電，必須通過中轉(zhuǎn)站（記為節(jié)點2，3，4，5）轉(zhuǎn)送。圖給出了兩節(jié)點間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。即從節(jié)點1到節(jié)點6的最短路徑。這就是一個最短路問題。第三節(jié)最短路問題例：從發(fā)電廠（記為節(jié)點1）向某城市（記為節(jié)點6）輸1325464332322第0步：P(1)=0,T(i)=+∞；第1步：與1相連的標(biāo)號為2,3，均是T標(biāo)號，修改2,3的標(biāo)號，T(2)=min{T(2),P(1)+w12}=4,T(3)=3；在所有的T標(biāo)號中，3的標(biāo)號最小，改3的標(biāo)號為P(3)=3；第2步：修改與3相連的T標(biāo)號；在所有剩下的T標(biāo)號中，2的標(biāo)號最小，改為P(2)=4；第3步：修改與2相連的T標(biāo)號；在所有剩下的T標(biāo)號中，5的標(biāo)號最小，改為P(5)=6；第4步：修改與5相連的T標(biāo)號；在所有剩下的T標(biāo)號中，4的標(biāo)號最小，改為P(4)=7；第5步：修改與4相連的T標(biāo)號；只剩下節(jié)點6是T標(biāo)號，修改6的標(biāo)號，P(6)=8。從節(jié)點6開始回退，得到最短路。P(1)=0T(3)=+∞T(2)=+∞T(3)=3T(5)=+∞P(3)=3T(5)=6T(2)=4T(4)=+∞T(6)=+∞P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短路問題1325464332322第0步：P(1)=0,T(i)=P(1)=0T(2)=+∞T(4)=+∞T(3)=+∞T(5)=+∞T(6)=+∞T(7)=+∞第2步：與4相連的標(biāo)號為2,3,5,6，均是T標(biāo)號，修改2,3,5,6的標(biāo)號，T(2)=min{T(2),P(4)+w42}=4,T(3)=min{T(3),P(4)+w43}=3T(5)=min{T(5),P(4)+w45}=7T(6)=min{T(6),P(4)+w46}=9在所有的T標(biāo)號中，3的標(biāo)號最小，改3的標(biāo)號為P(3)=3；T(2)=4T(3)=3T(4)=2P(4)=2第1步：與1相連的標(biāo)號為2,3，4，均是T標(biāo)號，修改2,3,4的標(biāo)號，T(2)=min{T(2),P(1)+w12}=4,T(3)=min{T(3),P(1)+w13}=3T(4)=min{T(4),P(1)+w14}=2在所有的T標(biāo)號中，4的標(biāo)號最小，改4的標(biāo)號為P(4)=2；T(2)=4T(3)=3T(5)=7T(6)=9第3步：與3相連的是T標(biāo)號,為5，修改5的標(biāo)號，T(5)=min{T(5),P(3)+w35}=6在所有的T標(biāo)號中，2的標(biāo)號最小，改2的標(biāo)號為P(2)=4；P(3)=3T(5)=6第4步：與2相連的是T標(biāo)號,為6，修改6的標(biāo)號，T(6)=min{T(6),P(4)+w46}=9在所有的T標(biāo)號中，5的標(biāo)號最小，改5的標(biāo)號為P(5)=6；P(2)=4P(5)=6第5步：與5相連的是T標(biāo)號,為6,7，修改6,7的標(biāo)號，T(6)=min{T(6),P(5)+w56}=8T(7)=min{T(7),P(5)+w56}=12在所有的T標(biāo)號中，6的標(biāo)號最小，改6的標(biāo)號為P(6)=8；1325464352326722572T(6)=8T(7)=12第6步：與6相連的是T標(biāo)號,為7，修改7的標(biāo)號，T(7)=min{T(7),P(6)+w67}=10在所有的T標(biāo)號中，7的標(biāo)號最小，改7的標(biāo)號為P(7)=10；P(6)=8T(7)=10P(7)=10最短路徑為P(7)-P(6)-P(5)-P(3)-P(1)最短路長度為10；T(6)=9求1到7的最短路第三節(jié)最短路問題P(1)=0T(2)=+∞T(4)=+∞T(3)=+∞1325465462352572求1到6的最短路最短路徑為1－3－5－6長度為9第三節(jié)最短路問題1325465462352572求1到6的最短路最短路徑為1用Excel求解最短路算法凈流量=流出該節(jié)點的流量—流入該節(jié)點的流量

中間節(jié)點的平衡值為0，起點為1，終點為-1。各個點的凈流量等于平衡值最短路平衡流第三節(jié)最短路問題用Excel求解最短路算法凈流量=流出該節(jié)點的流量—P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短路問題P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短

城市出租車公司在紐約市為出租車司機(jī)已經(jīng)確定了10個搭乘車站。為了減少運(yùn)行時間，提高服務(wù)質(zhì)量以及最大化利用公司的車隊，管理方希望出租車司機(jī)盡可能地選擇最短路線。使用下面公路與街道的網(wǎng)絡(luò)圖，請說明司機(jī)從車站1到車站10應(yīng)選擇什么樣的路線。運(yùn)行時間如圖所示。第三節(jié)最短路問題城市出租車公司在紐約市為出租車司機(jī)已經(jīng)確定了10個搭這里我們僅通過Excel電子表格求解，在表格中，我們并不是把每一對連接的點都輸入進(jìn)去，比如，我們輸入了從V7到V10，很明顯不需要再輸入從V7到V8，從V8到V10這兩對點對，因為他們加起來的距離明顯要比前者長。

第三節(jié)最短路問題這里我們僅通過Excel電子表格求解，在表格中，我最優(yōu)路線為：1－５－４－６－７－10，最短距離是25第三節(jié)最短路問題最優(yōu)路線為：1－５－４－６－７－10，最短距離是25第三節(jié)圖與網(wǎng)絡(luò)樹最短路問題最大流問題最小費(fèi)用流問題第四節(jié)最大流問題圖與網(wǎng)絡(luò)第四節(jié)最大流問題最大流量問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出發(fā)點到收點的最大流量第四節(jié)最大流問題最大流量問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容V1V4V2V5V76634252V3V62321例：某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點，這個網(wǎng)絡(luò)的一部分如圖所示，由于管理的直徑的變化，它的各段管道(vi,vj)的流量（容量）cij也是不一樣的，cij的單位為萬加侖/小時，如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運(yùn)送石油，問每小時能運(yùn)行多少加侖石油？第四節(jié)最大流問題V1V4V2V5V76634252V3V62321例：某石油設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上總的流量為F，則有目標(biāo)函數(shù)：maxF=f12+f14約束條件：f12=f23+f14f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fij≤cijfij≥0i=1,2,,,6j=2,3,,,,7守恒條件小于容量的可行流可行流中一組流量最大的稱為最大流第四節(jié)最大流問題設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上總的流量為F，則有守最大流問題網(wǎng)絡(luò)圖論的解法1、對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)，對條一條弧(vi,vj)的容量用一對數(shù)據(jù)cij,0標(biāo)在弧(vi,vj)上，以cij靠近vi點，0靠近vj點，表示從vi到vj容許通過的容量為cij，而從vj到vi容許通過的容量為0，這樣可能省云弧的方向vivjcijvivjcijc0對于存在兩條相反的弧(vi,vj)和(vj,vi)，也可以用一條過和一對數(shù)組cij，cji來表示它們的容量vivjcijvivjcijcji第四節(jié)最大流問題最大流問題網(wǎng)絡(luò)圖論的解法vivjcijvivjcijc0對于V1V4V2V5V76634252V3V6232100000000000第四節(jié)最大流問題V1V4V2V5V76634252V3V6232100000求最大流的基本算法（1）找出一條從發(fā)點到收點的路，在這條路上的每條弧順流方向的容量都大于零，如果不存在這樣的路，則已求得最大流（2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf(3)在這條路上，減少每條弧的順流容量pf，同時增加這些弧的逆流容量pf,返回步驟（1）由于所選路不一樣，計算過程也不一樣，但最終結(jié)果是一樣的，為了使算法快捷有效，我們一般在步驟（1）中盡量選擇包含弧數(shù)最少的路第四節(jié)最大流問題求最大流的基本算法第四節(jié)最大流問題第一次迭代選擇路為v1-v4-v7，弧（v4,v7)的順流容量為2，決定pf=2，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V76634252V3V62321000000000000422F=2第四節(jié)最大流問題第一次迭代V1V4V2V5V76634252V3V62321第二次迭代選擇路為v1-v2-v5－v7，?。╲2,v5)的順流容量c35=3，決定pf=3，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V763452V3V623210000000000422F=5032333第四節(jié)最大流問題第二次迭代V1V4V2V5V763452V3V6232100第三次迭代選擇路為v1-v4-v6－v7，弧（v4,v6)的順流容量c46=1，決定pf=1，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V742V3V623210000000422F=6032333303113第四節(jié)最大流問題第三次迭代V1V4V2V5V742V3V6232100000第四次迭代選擇路為v1-v4-v3－v6－v7，弧（v3,v6)的順流容量c36=2，決定pf=2，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V72V3V6232000002F=803233330311311015223第四節(jié)最大流問題第四次迭代V1V4V2V5V72V3V6232000002F第五次迭代選擇路為v1-v2-v3－v5－v7，?。╲2,v3)的順流容量c23=2，決定pf=2，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V72V3V620002F=10032333011101522310005225第四節(jié)最大流問題第五次迭代V1V4V2V5V72V3V620002F=100V1V4V2V5V7V3V602F=1003011101522310005225網(wǎng)絡(luò)圖中，逆流就是流過每條路徑的流量第四節(jié)最大流問題V1V4V2V5V7V3V602F=10030111015224531142010519152730流量容量

容量網(wǎng)絡(luò)：標(biāo)有弧容量的網(wǎng)絡(luò)。網(wǎng)絡(luò)流的兩個條件：每個弧的流量不能超過該弧的最大通過能力，即容量；中間支點的流量為零?？尚辛鳎褐虚g點的流量為零。而發(fā)點和收點的流量必須相等。156104610150可行流第四節(jié)最大流問題24531142010519152730流量容量容量網(wǎng)絡(luò)增廣鏈13425201051419152730156104610150飽和弧非飽和弧零弧增廣鏈增廣鏈:

設(shè)f是一個可行流，C是從發(fā)點Vs到收點Vt的一條鏈，若C滿足以下條件，則稱C為一條增廣鏈：(1)在弧(vi,vj)∈C+上，0≤fij≤cij，即C+(弧的方向與鏈的方向一致

)中每一條弧是非飽和弧(2)在弧(vi,vj)∈C+上，0≤fij≤cij，即C-(弧的方向與鏈的方向相反

)中每一條弧是非零流弧

C＋中每一條弧是非飽和弧;C－中每一條弧是非零流弧。

第四節(jié)最大流問題增廣鏈13425201051419152730156104621st28811任給一個包含收點但不包含發(fā)點的支點集V*，則稱i(弧起點)不屬于V*，j(弧終點)屬于V*的弧(i,j)的全體為割集。割集的容量是割集中所有弧的容量的總和。如果將割集從網(wǎng)絡(luò)中移去，則就不可能有從起點到終點的路徑。一個網(wǎng)絡(luò)可能有許多割集。任何從發(fā)點到收點的可行流小于等于任何割集的容量。

V*割集任何割集的容量是從起點到終點的最大流的上界。如果能找到一個可行流和一個割集使得割集從起點到終點的容量等于可行流的流量，則該可行流就是一個最大流。最大流---最小割定理

V*={1,t}割集是{(s,1)，(2,t)}

支點集V*={1,2,t},割集？{(s,1)，(s,2)}

第四節(jié)最大流問題21st28811任給一個包含收點但不包含發(fā)點的支點集V*求最大流的標(biāo)號算法從一個可行流f={fij}出發(fā)，（若網(wǎng)絡(luò)中沒有給定f，則可以設(shè)f是零流）需要經(jīng)過標(biāo)號過程與調(diào)整過程。1．標(biāo)號過程在這個過程中，網(wǎng)絡(luò)中的點或是標(biāo)號點或是未標(biāo)號點。每個標(biāo)號點的標(biāo)號包含兩部分：第一標(biāo)號表示它的標(biāo)號是從哪一點得到的，以便找出增廣鏈；第二個標(biāo)號是為確定增廣鏈的調(diào)整量用的。標(biāo)號過程開始時，總是先給發(fā)點Vs標(biāo)上(0,+∞)。其余各點標(biāo)號的規(guī)則是：設(shè)vi是已標(biāo)號的點，檢查與Vj點關(guān)聯(lián)的另一頂點未標(biāo)號的弧：（1）如果在弧(vi,vj)上（即前向?。?，fij<cij，則給vj標(biāo)號(vi,l(vj))，其中l(wèi)(vj)=min{l(vi),cij-fij}。如果fij=cij，則vj不標(biāo)號。（2）如果在弧(vj,vi)上（即后向弧），fji>0，則給vj標(biāo)號(-vi,l(vj))，其中l(wèi)(vj)=min{l(vi),fji}，負(fù)號說明經(jīng)后向弧到。如果fij=0，則vi不標(biāo)號。重復(fù)上述步驟，直到被vj標(biāo)上號，表明得到一條從vi到vj的增廣鏈C，轉(zhuǎn)入調(diào)整過程。第四節(jié)最大流問題求最大流的標(biāo)號算法從一個可行流f={fij}出發(fā)，（若網(wǎng)求最大流的標(biāo)號算法2．調(diào)整過程由收點標(biāo)號算出的作為調(diào)整量（即）。對增廣鏈各弧的調(diào)整如下：

增廣鏈以外各弧流量不變。去掉所有標(biāo)號，對新的可行流，重新進(jìn)入標(biāo)號過程。直到標(biāo)號過程中斷。當(dāng)前流就是最大流。第四節(jié)最大流問題求最大流的標(biāo)號算法2．調(diào)整過程增廣鏈以外各弧vsv2v1v3vt32223(0,+∞)

找到初始可行流。給網(wǎng)絡(luò)中的各個點標(biāo)號：總是先給發(fā)點vs標(biāo)上(0,+∞)。其余各點標(biāo)號的規(guī)則是：設(shè)vi是已標(biāo)號的點，檢查與點vi關(guān)聯(lián)的另一頂點未標(biāo)號的?。海?）如果在弧(vi,vj)上（即前向?。?，fij<cij，則給vj標(biāo)號(vi,l(vj))，其中l(wèi)(vj)=min{l(vi),cij-fij}。如果fij=cij，則vj不標(biāo)號。（2）如果在弧(vj,vi)上（即后向?。?，fij>0，則給vj標(biāo)號(-vi,l(vj))，其中l(wèi)(vj)=min{l(vi),fji}，負(fù)號說明經(jīng)后向弧到vi。如果fji=0，則vj不標(biāo)號。調(diào)整：按照第一標(biāo)號找到增廣鏈，按第二標(biāo)號的最小值調(diào)整可行流，得到新的可行流。重復(fù)標(biāo)號過程，直到?jīng)]有增廣鏈，即得到最大流。2112114(vs,2)(v3,1)(-v2,1)(v1,1)222022如下圖所示，弧上數(shù)字表示該弧的容量，求該網(wǎng)絡(luò)的最大流。增廣鏈以外各弧流量不變

第四節(jié)最大流問題32223(0,+∞)找到初始可行流。2112114(vsvsv2v1v3vt32223(0,+∞)重復(fù)標(biāo)號過程。給網(wǎng)絡(luò)中的各個點標(biāo)號：先給發(fā)點vs標(biāo)上(0,+∞)。檢查vs給v2標(biāo)上(vs,1)，檢查v2,在弧(v2,vt)上,f2t=c2t=2,不滿足標(biāo)號條件，在弧(v1,v2)上，f12=0,也不滿足標(biāo)號條件，標(biāo)號無法繼續(xù)。算法結(jié)束。4(vs,1)222022如下圖所示，弧上數(shù)字表示該弧的容量，求該網(wǎng)絡(luò)的最大流。最大流量為從發(fā)點流出的量這時的可行流就是所求的最大流

第四節(jié)最大流問題32223(0,+∞)重復(fù)標(biāo)號過程。4(vs,1)22202第四節(jié)最大流問題第四節(jié)最大流問題從一個費(fèi)用最小的可行流f={fij}出發(fā)（這樣的可行流一定存在，因為費(fèi)用bij>0，所以f=0就是一個流量為0的最小費(fèi)用流），找出這個可行流f的費(fèi)用最小的一條增廣鏈L，沿L調(diào)整f，直到找不到費(fèi)用最小的增廣鏈，就得到了最小費(fèi)用最大流。對于網(wǎng)絡(luò)圖G中的弧，除標(biāo)明弧的容量cij外，還要標(biāo)明流過該弧單位流量的費(fèi)用bij，G的一個可行流f={fij}，使得流的總運(yùn)輸費(fèi)用：達(dá)到最小。特別，如果可行流是最大流時，此問題就是最小費(fèi)用最大流問題。

最小費(fèi)用流問題最小費(fèi)用最大流的基本思路第五節(jié)最小費(fèi)用流問題對于網(wǎng)絡(luò)圖G中的弧，除標(biāo)明弧的容量cij外，還要標(biāo)明流過該弧用Excel求解最大流和最小費(fèi)用最大流問題

用Excel求解例9.5

第五節(jié)最小費(fèi)用流問題用Excel求解最大流和最小費(fèi)用最大流問題用Excel求解最小費(fèi)用最大流問題的Excel電子表格求解

用Excel求解例9.6

第五節(jié)最小費(fèi)用流問題最小費(fèi)用最大流問題的Excel電子表格求解用Excel求解第五節(jié)最小費(fèi)用流問題第五節(jié)最小費(fèi)用流問題例1，一個郵遞員應(yīng)選擇怎樣的送信路線，使得他走完所負(fù)責(zé)的全部街道后，回到郵局，所走的路程最短（不重復(fù)或少重復(fù)國郵遞員問題例1，一個郵遞員應(yīng)選擇怎樣的送信路線，使得他走完所負(fù)責(zé)的全部例2“七橋問題”哥尼斯堡（現(xiàn)叫加里寧格勒）有一條河，河中有二個島，河上有七座橋，數(shù)學(xué)家歐拉證明了從一點出發(fā)，經(jīng)過每座橋一次且僅一次，再回到原出發(fā)點是辦不到的。這就所謂的一筆畫問題CD中國郵遞員問題例2“七橋問題”哥尼斯堡（現(xiàn)叫加里寧格勒）有一條河，河中有一筆畫問題（1）歐拉圖：圖中每個頂點的次均為偶數(shù)的圖（2）歐拉鏈：經(jīng)過圖中G的每一條邊僅一次的鏈以下兩種圖可以一筆畫出（1）每個頂點的次均為偶數(shù)的圖，畫時可以從任一點出發(fā)（2）有且僅有兩個奇點的圖，畫時必須從其中一個奇點出發(fā)，在另一個奇點結(jié)束除以上兩種情形，其圖一律不能一筆畫出中國郵遞員問題一筆畫問題中國郵遞員問題在例1中，由于每個頂點的次均為偶數(shù)，所以可以一筆畫出，也即郵遞員可以一次走完所有街道，最后回到郵局，可任選一個點為出發(fā)點國郵遞員問題在例1中，由于每個頂點的次均為偶數(shù)，所以可以一筆畫出，也即郵可以把七橋問題看作為如下圖的一筆畫問題。由于d(A)=3,d(B)=3,d(C)=5,d(D)=3，即度為奇數(shù)的個數(shù)為4，所以不能一筆畫出，也即不能一次走完七座橋。DCBA中國郵遞員問題可以把七橋問題看作為如下圖的一筆畫問題。DCBA中國郵遞員問精品課件！精品課件！精品課件！精品課件！試確定以下圖能否一筆畫出？試確定以下圖能否一筆畫出？教學(xué)要求：掌握圖論基礎(chǔ)，掌握最短路問題，最大流問題和最小費(fèi)用流問題等網(wǎng)絡(luò)優(yōu)化模型及其基本算法。會應(yīng)用模型和方法解決一些管理中的基本問題教學(xué)要求：掌握圖論基礎(chǔ)，掌握最短路問題，最大流問題和最小費(fèi)目錄圖與網(wǎng)絡(luò)樹最短路問題最大流問題最小費(fèi)用流問題第一節(jié)圖與網(wǎng)絡(luò)目錄第一節(jié)圖與網(wǎng)絡(luò)12341234一、圖的概念及分類圖是由作為研究對象的有限個集合和表達(dá)這些頂點之間關(guān)系的m條線的集合組成的,記頂點集合為V={v1,v2,……vn}，線集合為L={l1,l2,….lm}圖則記為G=(V，L)，線又分為弧和邊，頂點也稱為結(jié)點弧是由一對有序的頂點組成，表示兩個頂點之間可能運(yùn)動的方向取消弧的方向就變成了邊，邊是只要任兩點之間有連線，兩個方向均可使用，弧可作為城市道路的單行道，邊則是雙行道第一節(jié)圖與網(wǎng)絡(luò)12341234一、圖的概念及分類第一節(jié)圖與網(wǎng)絡(luò)頂點、弧、有向圖、無向圖、鏈、道路、環(huán)、連通圖、連通子圖、次的基本概念1234123412345213次道路頂點無向圖鏈有向圖弧環(huán)連通圖弧是由一對有序的頂點組成，表示了兩個頂點之間可能運(yùn)動的方向連通子圖

由頂點集和弧組成的圖稱為有向圖

由頂點集和邊組成的圖稱為無向圖

鏈有一序列弧，如果每一個弧與前一個弧恰有一個公共頂點，則稱這一序列弧為一個鏈。

道路如果鏈中每一個弧的終點是下面一個弧的起點，則這個鏈稱為一個道路。

環(huán)連接a點與b點的一條鏈，如果a與b是同一個點時，稱此鏈為環(huán)。

連通圖一個圖中任意兩點間至少有一個鏈相連，則稱此圖為連通圖。

任何一個不連通圖都可以分為若干個連通子圖，每一個子圖稱為原圖的一個分圖。

次:以a點為頂點的邊的條數(shù)稱為頂點的次

第一節(jié)圖與網(wǎng)絡(luò)頂點、弧、有向圖、無向圖、鏈、道路、環(huán)、連通圖、連通子圖、次點或邊帶有某種數(shù)量指標(biāo)的圖叫網(wǎng)絡(luò)圖，簡稱網(wǎng)絡(luò)。與點或邊有關(guān)的某些數(shù)量指標(biāo)，我們經(jīng)常稱之為權(quán)，權(quán)可以代表如距離、費(fèi)用、容量等。左圖可以看作：從發(fā)電廠（節(jié)點1）向某城市（節(jié)點6）輸送電力，必須通過中轉(zhuǎn)站（節(jié)點2，3，4，5）轉(zhuǎn)送，邊上數(shù)字代表兩節(jié)點間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。一個輸油管道網(wǎng)。節(jié)點1表示管道的起點，節(jié)點6表示管道的終點，節(jié)點2到5表示中轉(zhuǎn)站，旁邊的數(shù)字表示該段管道能通過的最大輸送量。應(yīng)怎樣安排輸油線路，使從節(jié)點1到節(jié)點6的總輸送量最大？一張城市分布圖?，F(xiàn)在要在各城市之間架設(shè)電話線，應(yīng)如何架設(shè)，使各城市之間既能通話，又使總的架設(shè)路線最短？二、網(wǎng)絡(luò)第一節(jié)圖與網(wǎng)絡(luò)點或邊帶有某種數(shù)量指標(biāo)的圖叫網(wǎng)絡(luò)圖，簡稱網(wǎng)絡(luò)。左圖可以看作一、樹：連通且不含環(huán)的無向圖

樹的性質(zhì)：任意兩頂點之間必有一條且僅有一條鏈。去掉任一條邊，則樹成為不連通圖。不相鄰的兩個頂點間添上一條邊，恰好得到一個環(huán)。如果樹有n個結(jié)點，則邊的數(shù)目剛好為n-1第二節(jié)樹一、樹：連通且不含環(huán)的無向圖樹的性質(zhì)：第二節(jié)樹部分圖生成子圖部分樹如果V1V，E1E則稱G1為G的部分圖；設(shè)G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1V，,則稱G1為G的生成子圖；如果G=(V，E)的部分圖G1=(V，E1)是樹，則稱G1為G的一個部分樹。二、部分圖、生成子圖、部分樹第二節(jié)樹部分圖生成子圖部分樹如果V1V，E1E則稱G1為求連通圖部分樹的方法(1)破圈法：在G中任取一個圈，去掉圈中的任何一條邊，對余下的圖重復(fù)這一步，直到無圈為止，最后得到一棵部分樹第二節(jié)樹求連通圖部分樹的方法第二節(jié)樹求連通圖部分樹的方法(2)避圈法：在G中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，然后再找一條與{e1,e2}不構(gòu)成圈的邊e3、、、直到無邊可選為止V1V3V2V5V4V6e1e2e3e6e7e5e8e8e4第二節(jié)樹求連通圖部分樹的方法V1V3V2V5V4V6e1e2e3e61325464332322最小生成樹不一定唯一三、最小生成樹：設(shè)有一連通圖G=(V，L)，對于每一條邊e=(vi,vj),有一個權(quán)wij，一棵生成樹所有樹枝上權(quán)的總和，稱為這個生成樹的權(quán)，具有最小權(quán)的生成樹稱為最小生成樹，簡稱最小樹第二節(jié)樹1325464332322最小生成樹不一定唯一三、最小生成樹(1)最小生成樹的求法破圈法:每一步任找一個圈，劃去權(quán)值為最大的邊，直到圖中沒圈為止，即得最小樹V1V3V2V5V4V6651532447第二節(jié)樹(1)最小生成樹的求法V1V3V2V5V4V66515324(2)最小生成樹的求法避圈法:每一步從未選的邊中，選一條權(quán)值最小的邊，使已選出的邊不構(gòu)成圈直至不能進(jìn)行為止，即得最小樹V1V3V2V5V4V6651532447第二節(jié)樹(2)最小生成樹的求法V1V3V2V5V4V66515324V1V4V2V5V7V864523854V3V64543637練習(xí)：用破圈法或避圈法求下圖的最小生成樹，并指出其權(quán)重和

第二節(jié)樹V1V4V2V5V7V864523854V3V6454363避圈法：V1V4V2V5V7V864523854V3V64543637最小生成樹如上圖紅線所示，最小權(quán)重為：4+3+3+3+4+5+2=24第二節(jié)樹避圈法：V1V4V2V5V7V864523854V3V645破圈法：V1V4V2V5V7V864523854V3V64543637最小生成樹如上圖所示，最小權(quán)重為：4+3+3+3+4+5+2=24第二節(jié)樹破圈法：V1V4V2V5V7V864523854V3V645練習(xí)：下圖是6個城市的交通圖，為將部分道路改造成高速公路，使各個城市均能通達(dá)，又要使高速公路的總長度最小，應(yīng)如何做使總長度最小,總長度是多少?第二節(jié)樹練習(xí)：第二節(jié)樹避圈法求解：第二節(jié)樹最優(yōu)改造路線如上圖紅線所示，最短路徑為：1400避圈法求解：第二節(jié)樹最優(yōu)改造路線如上圖紅線所示，求下面兩個連通圖的最小生成樹：第二節(jié)樹求下面兩個連通圖的最小生成樹：第二節(jié)樹第二節(jié)樹第二節(jié)樹某地有10個村莊，它們之間的交通道路如下圖所示，圖中邊旁權(quán)為道路長度(單位：百米)，現(xiàn)在要沿道架設(shè)電線，實現(xiàn)村村通電話工程，問應(yīng)如何架設(shè)電線才能使總長度最短？第二節(jié)樹某地有10個村莊，它們之間的交通道路如下圖所示，第二節(jié)樹解：本題實質(zhì)是最小樹問題，利用避圈法可求得最短路線，如下圖粗線所示：最優(yōu)架設(shè)路線如上圖粗線所示，架設(shè)電線最短長度為18(百米)。第二節(jié)樹解：本題實質(zhì)是最小樹問題，利用避圈法可求得最短路線，最優(yōu)架設(shè)某大學(xué)準(zhǔn)備對其所屬的7個學(xué)院辦公室計算機(jī)聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖所示，圖中vi表示7個學(xué)院辦公室，圖中的邊為可能聯(lián)網(wǎng)的途徑，邊上的所賦的權(quán)數(shù)為這條路線的長度，單位為百米，請設(shè)計一個網(wǎng)絡(luò)能聯(lián)系7個學(xué)院辦公室，并使總的線路長度為最短V1V6V5104873V2V7335V4V3124某大學(xué)準(zhǔn)備對其所屬的7個學(xué)院辦公室計算機(jī)聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能V1V6V5104873V2V7335V4V312破圈法求解：4最短路徑如上圖所示，最短為：19百米V1V6V5104873V2V7335V4V312破圈法求解V1V6V5104873V2V7335V4V312避圈法求解：最短路徑如上圖所示，最短為：19百米4V1V6V5104873V2V7335V4V312避圈法求解圖與網(wǎng)絡(luò)樹最短路問題最大流問題最小費(fèi)用流問題第三節(jié)最短路問題圖與網(wǎng)絡(luò)第三節(jié)最短路問題特點：從一特殊的節(jié)點出發(fā)，找出從該節(jié)點到網(wǎng)絡(luò)中任何其它節(jié)點的最短路徑問題某人買了一輛價值1200美元的新車，一輛車每年的維護(hù)費(fèi)用依賴于年初時的車齡，具體費(fèi)用見下表。為了避免舊車的高維護(hù)費(fèi)用，他決定賣掉舊車買新車。舊車的價格依賴于交易時的車齡，見下表。為計算簡單起見，假設(shè)任何時間新車的價格不變均為1200美元。他希望在今后5年內(nèi)的凈費(fèi)用最?。矗簝糍M(fèi)用=購買價+維護(hù)價-售出價）。

2112第三節(jié)最短路問題特點：從一特殊的節(jié)點出發(fā)，找出從該節(jié)點到網(wǎng)絡(luò)中任何其它節(jié)點的結(jié)點i表示第i年的年初，當(dāng)i<j時，弧(i,j)表示第i年年初購買一輛新車并一直用到第j年年初。弧的長度cij表示：如果第i年年初購買一輛新車并這輛車在第j年年初賣掉更換一輛新新，從第i年年初到第j年年初期間總的凈費(fèi)用，于是有cij=(i,i+1,..j-1年的維護(hù)費(fèi)用）＋（第i年年初購買新車的費(fèi)用）－（第j年年初該車的交易費(fèi)用）1234567777712121221313144122121第三節(jié)最短路問題結(jié)點i表示第i年的年初，當(dāng)i<j時，弧(i,j)表示第i年年c12=2+12-7=7c13=2+4+12-6=12c14=2+4+5+12-2=21c15=2+4+5+9+12-1=31c16=2+4+5+9+12+12-0=44c23=2+12-7=7c24=2+4+12-6=12c25=2+4+5+12-2=21c26=2+4+5+9+12-1=31c34=2+12-7=7c35=2+4+12-6=12c36=3+4+5+12-2=21c45=2+12-7=7c46=2+4+12-6=12c56=2+12-7=71234567777712121221313144122121第三節(jié)最短路問題c12=2+12-7=7c13=2+4+12-6=121Dijkstra最短路算法：假設(shè)每個弧的權(quán)是非負(fù)的，即wij≥0，給每個支點vi記一個數(shù)(稱標(biāo)號)，標(biāo)號分臨時性標(biāo)號T和永久性標(biāo)號P，永久性標(biāo)號表示從v1到該點vi的最短路權(quán)，得到永久性標(biāo)號的不再改變標(biāo)號，臨時性標(biāo)號表示從開始點v1到該點vi的最短路權(quán)的上界，算法每一步都把某一點的T標(biāo)號改為P標(biāo)號，開始時給初始支點v1標(biāo)號記為0，即P(v1)=0，其他支點(記為臨時性標(biāo)號)的標(biāo)號記為+∞，即T(vi)=+∞,若vi點是剛得到P標(biāo)號的點，考慮L中與vi點相連的弧(vi,vj)且vj是T標(biāo)號，對vj的標(biāo)號進(jìn)行如下更改：T(vj)=min{T(vj),P(vi)+Wij}比較所有具有T標(biāo)號的點，把最小者改為P標(biāo)號，當(dāng)存在兩個以上最小者時，可以同時改為P標(biāo)號，直到全部點均改為P標(biāo)號為止第三節(jié)最短路問題Dijkstra最短路算法：假設(shè)每個弧的權(quán)是非負(fù)的，即wij

例：從發(fā)電廠（記為節(jié)點1）向某城市（記為節(jié)點6）輸送電，必須通過中轉(zhuǎn)站（記為節(jié)點2，3，4，5）轉(zhuǎn)送。圖給出了兩節(jié)點間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。即從節(jié)點1到節(jié)點6的最短路徑。這就是一個最短路問題。第三節(jié)最短路問題例：從發(fā)電廠（記為節(jié)點1）向某城市（記為節(jié)點6）輸1325464332322第0步：P(1)=0,T(i)=+∞；第1步：與1相連的標(biāo)號為2,3，均是T標(biāo)號，修改2,3的標(biāo)號，T(2)=min{T(2),P(1)+w12}=4,T(3)=3；在所有的T標(biāo)號中，3的標(biāo)號最小，改3的標(biāo)號為P(3)=3；第2步：修改與3相連的T標(biāo)號；在所有剩下的T標(biāo)號中，2的標(biāo)號最小，改為P(2)=4；第3步：修改與2相連的T標(biāo)號；在所有剩下的T標(biāo)號中，5的標(biāo)號最小，改為P(5)=6；第4步：修改與5相連的T標(biāo)號；在所有剩下的T標(biāo)號中，4的標(biāo)號最小，改為P(4)=7；第5步：修改與4相連的T標(biāo)號；只剩下節(jié)點6是T標(biāo)號，修改6的標(biāo)號，P(6)=8。從節(jié)點6開始回退，得到最短路。P(1)=0T(3)=+∞T(2)=+∞T(3)=3T(5)=+∞P(3)=3T(5)=6T(2)=4T(4)=+∞T(6)=+∞P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短路問題1325464332322第0步：P(1)=0,T(i)=P(1)=0T(2)=+∞T(4)=+∞T(3)=+∞T(5)=+∞T(6)=+∞T(7)=+∞第2步：與4相連的標(biāo)號為2,3,5,6，均是T標(biāo)號，修改2,3,5,6的標(biāo)號，T(2)=min{T(2),P(4)+w42}=4,T(3)=min{T(3),P(4)+w43}=3T(5)=min{T(5),P(4)+w45}=7T(6)=min{T(6),P(4)+w46}=9在所有的T標(biāo)號中，3的標(biāo)號最小，改3的標(biāo)號為P(3)=3；T(2)=4T(3)=3T(4)=2P(4)=2第1步：與1相連的標(biāo)號為2,3，4，均是T標(biāo)號，修改2,3,4的標(biāo)號，T(2)=min{T(2),P(1)+w12}=4,T(3)=min{T(3),P(1)+w13}=3T(4)=min{T(4),P(1)+w14}=2在所有的T標(biāo)號中，4的標(biāo)號最小，改4的標(biāo)號為P(4)=2；T(2)=4T(3)=3T(5)=7T(6)=9第3步：與3相連的是T標(biāo)號,為5，修改5的標(biāo)號，T(5)=min{T(5),P(3)+w35}=6在所有的T標(biāo)號中，2的標(biāo)號最小，改2的標(biāo)號為P(2)=4；P(3)=3T(5)=6第4步：與2相連的是T標(biāo)號,為6，修改6的標(biāo)號，T(6)=min{T(6),P(4)+w46}=9在所有的T標(biāo)號中，5的標(biāo)號最小，改5的標(biāo)號為P(5)=6；P(2)=4P(5)=6第5步：與5相連的是T標(biāo)號,為6,7，修改6,7的標(biāo)號，T(6)=min{T(6),P(5)+w56}=8T(7)=min{T(7),P(5)+w56}=12在所有的T標(biāo)號中，6的標(biāo)號最小，改6的標(biāo)號為P(6)=8；1325464352326722572T(6)=8T(7)=12第6步：與6相連的是T標(biāo)號,為7，修改7的標(biāo)號，T(7)=min{T(7),P(6)+w67}=10在所有的T標(biāo)號中，7的標(biāo)號最小，改7的標(biāo)號為P(7)=10；P(6)=8T(7)=10P(7)=10最短路徑為P(7)-P(6)-P(5)-P(3)-P(1)最短路長度為10；T(6)=9求1到7的最短路第三節(jié)最短路問題P(1)=0T(2)=+∞T(4)=+∞T(3)=+∞1325465462352572求1到6的最短路最短路徑為1－3－5－6長度為9第三節(jié)最短路問題1325465462352572求1到6的最短路最短路徑為1用Excel求解最短路算法凈流量=流出該節(jié)點的流量—流入該節(jié)點的流量

中間節(jié)點的平衡值為0，起點為1，終點為-1。各個點的凈流量等于平衡值最短路平衡流第三節(jié)最短路問題用Excel求解最短路算法凈流量=流出該節(jié)點的流量—P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短路問題P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短

城市出租車公司在紐約市為出租車司機(jī)已經(jīng)確定了10個搭乘車站。為了減少運(yùn)行時間，提高服務(wù)質(zhì)量以及最大化利用公司的車隊，管理方希望出租車司機(jī)盡可能地選擇最短路線。使用下面公路與街道的網(wǎng)絡(luò)圖，請說明司機(jī)從車站1到車站10應(yīng)選擇什么樣的路線。運(yùn)行時間如圖所示。第三節(jié)最短路問題城市出租車公司在紐約市為出租車司機(jī)已經(jīng)確定了10個搭這里我們僅通過Excel電子表格求解，在表格中，我們并不是把每一對連接的點都輸入進(jìn)去，比如，我們輸入了從V7到V10，很明顯不需要再輸入從V7到V8，從V8到V10這兩對點對，因為他們加起來的距離明顯要比前者長。

第三節(jié)最短路問題這里我們僅通過Excel電子表格求解，在表格中，我最優(yōu)路線為：1－５－４－６－７－10，最短距離是25第三節(jié)最短路問題最優(yōu)路線為：1－５－４－６－７－10，最短距離是25第三節(jié)圖與網(wǎng)絡(luò)樹最短路問題最大流問題最小費(fèi)用流問題第四節(jié)最大流問題圖與網(wǎng)絡(luò)第四節(jié)最大流問題最大流量問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出發(fā)點到收點的最大流量第四節(jié)最大流問題最大流量問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容V1V4V2V5V76634252V3V62321例：某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點，這個網(wǎng)絡(luò)的一部分如圖所示，由于管理的直徑的變化，它的各段管道(vi,vj)的流量（容量）cij也是不一樣的，cij的單位為萬加侖/小時，如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運(yùn)送石油，問每小時能運(yùn)行多少加侖石油？第四節(jié)最大流問題V1V4V2V5V76634252V3V62321例：某石油設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上總的流量為F，則有目標(biāo)函數(shù)：maxF=f12+f14約束條件：f12=f23+f14f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fij≤cijfij≥0i=1,2,,,6j=2,3,,,,7守恒條件小于容量的可行流可行流中一組流量最大的稱為最大流第四節(jié)最大流問題設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上總的流量為F，則有守最大流問題網(wǎng)絡(luò)圖論的解法1、對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)，對條一條弧(vi,vj)的容量用一對數(shù)據(jù)cij,0標(biāo)在弧(vi,vj)上，以cij靠近vi點，0靠近vj點，表示從vi到vj容許通過的容量為cij，而從vj到vi容許通過的容量為0，這樣可能省云弧的方向vivjcijvivjcijc0對于存在兩條相反的弧(vi,vj)和(vj,vi)，也可以用一條過和一對數(shù)組cij，cji來表示它們的容量vivjcijvivjcijcji第四節(jié)最大流問題最大流問題網(wǎng)絡(luò)圖論的解法vivjcijvivjcijc0對于V1V4V2V5V76634252V3V6232100000000000第四節(jié)最大流問題V1V4V2V5V76634252V3V6232100000求最大流的基本算法（1）找出一條從發(fā)點到收點的路，在這條路上的每條弧順流方向的容量都大于零，如果不存在這樣的路，則已求得最大流（2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf(3)在這條路上，減少每條弧的順流容量pf，同時增加這些弧的逆流容量pf,返回步驟（1）由于所選路不一樣，計算過程也不一樣，但最終結(jié)果是一樣的，為了使算法快捷有效，我們一般在步驟（1）中盡量選擇包含弧數(shù)最少的路第四節(jié)最大流問題求最大流的基本算法第四節(jié)最大流問題第一次迭代選擇路為v1-v4-v7，?。╲4,v7)的順流容量為2，決定pf=2，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V76634252V3V62321000000000000422F=2第四節(jié)最大流問題第一次迭代V1V4V2V5V76634252V3V62321第二次迭代選擇路為v1-v2-v5－v7，?。╲2,v5)的順流容量c35=3，決定pf=3，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V763452V3V623210000000000422F=5032333第四節(jié)最大流問題第二次迭代V1V4V2V5V763452V3V6232100第三次迭代選擇路為v1-v4-v6－v7，?。╲4,v6)的順流容量c46=1，決定pf=1，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V742V3V623210000000422F=6032333303113第四節(jié)最大流問題第三次迭代V1V4V2V5V742V3V6232100000第四次迭代選擇路為v1-v4-v3－v6－v7，?。╲3,v6)的順流容量c36=2，決定pf=2，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V72V3V6232000002F=803233330311311015223第四節(jié)最大流問題第四次迭代V1V4V2V5V72V3V6232000002F第五次迭代選擇路為v1-v2-v3－v5－v7，?。╲2,v3)的順流容量c23=2，決定pf=2，改進(jìn)網(wǎng)絡(luò)流量V1V4V2V5V72V3V620002F=10032333011101522310005225第四節(jié)最大流問題第五次迭代V1V4V2V5V72V3V620002F=100V1V4V2V5V7V3V602F=1003011101522310005225網(wǎng)絡(luò)圖中，逆流就是流過每條路徑的流量第四節(jié)最大流問題V1V4V2V5V7V3V602F=10030111015224531142010519152730流量容量

容量網(wǎng)絡(luò)：標(biāo)有弧容量的網(wǎng)絡(luò)。網(wǎng)絡(luò)流的兩個條件：每個弧的流量不能超過該弧的最大通過能力，即容量；中間支點的流量為零?？尚辛鳎褐虚g點的流量為零。而發(fā)點和收點的流量必須相等。156104610150可行流第四節(jié)最大流問題24531142010519152730流量容量容量網(wǎng)絡(luò)增廣鏈13425201051419152730156104610150飽和弧非飽和弧零弧增廣鏈增廣鏈:

設(shè)f是一個可行流，C是從發(fā)點Vs到收點Vt的一條鏈，若C滿足以下條件，則稱C為一條增廣鏈：(1)在弧(vi,vj)∈C+上，0≤fij≤cij，即C+(弧的方向與鏈的方向一致

)中每一條弧是非飽和弧(2)在弧(vi,vj)∈C+上，0≤fij≤cij，即C-(弧的方向與鏈的方向相反

)中每一條弧是非零流弧

C＋中每一條弧是非飽和弧;C－中每一條弧是非零流弧。

第四節(jié)最大流問題增廣鏈13425201051419152730156104621st28811任給一個包含收點但不包含發(fā)點的支點集V*，則稱i(弧起點)不屬于V*，j(弧終點)屬于V*的弧(i,j)的全體為割集。割集的容量是割集中所有弧的容量的總和。如果將割集從網(wǎng)絡(luò)中移去，則就不可能有從起點到終點的路徑。一個網(wǎng)絡(luò)可能有許多割集。任何從發(fā)點到收點的可行流小于等于任何割集的容量。

V*割集任何割集的容量是從起點到終點的最大流的上界。如果能找到一個可行流和一個割集使得割集從起點到終點的容量等于可行流的流量，則該可行流就是一個最大流。最大流---最小割定理

V*={1,t}割集是{(s,1)，(2,t)}

支點集V*={1,2,t},割集？{(s,1)，(s,2)}

第四節(jié)最大流問題21st28811任給一個包含收點但不包含發(fā)點的支點集V*求最大流的標(biāo)號算法從一個可行流f={fij}出發(fā)，（若網(wǎng)絡(luò)中沒有給定f，則可以設(shè)f是零流）需要經(jīng)過標(biāo)號過程與調(diào)整過程。1．標(biāo)號過程在這個過程中，網(wǎng)絡(luò)中的點或是標(biāo)號點或是未標(biāo)號點。每個標(biāo)號點的標(biāo)號包含兩部分：第一標(biāo)號表示它的標(biāo)號是從哪一點得到的，以便找出