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

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

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

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

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

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

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

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

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

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

第一節(jié)圖與網(wǎng)絡(luò)第5頁，課件共70頁，創(chuàng)作于2023年2月點或邊帶有某種數(shù)量指標的圖叫網(wǎng)絡(luò)圖，簡稱網(wǎng)絡(luò)。與點或邊有關(guān)的某些數(shù)量指標，我們經(jīng)常稱之為權(quán)，權(quán)可以代表如距離、費用、容量等。左圖可以看作：從發(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ò)第6頁，課件共70頁，創(chuàng)作于2023年2月一、樹：連通且不含環(huán)的無向圖

樹的性質(zhì)：任意兩頂點之間必有一條且僅有一條鏈。去掉任一條邊，則樹成為不連通圖。不相鄰的兩個頂點間添上一條邊，恰好得到一個環(huán)。如果樹有n個結(jié)點，則邊的數(shù)目剛好為n-1第二節(jié)樹第7頁，課件共70頁，創(chuàng)作于2023年2月部分圖生成子圖部分樹如果V1

V，E1

E則稱G1為G的部分圖；設(shè)G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1

V，,則稱G1為G的生成子圖；如果G=(V，E)的部分圖G1=(V，E1)是樹，則稱G1為G的一個部分樹。二、部分圖、生成子圖、部分樹第二節(jié)樹第8頁，課件共70頁，創(chuàng)作于2023年2月求連通圖部分樹的方法(1)破圈法：在G中任取一個圈，去掉圈中的任何一條邊，對余下的圖重復(fù)這一步，直到無圈為止，最后得到一棵部分樹第二節(jié)樹第9頁，課件共70頁，創(chuàng)作于2023年2月求連通圖部分樹的方法(2)避圈法：在G中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，然后再找一條與{e1,e2}不構(gòu)成圈的邊e3、、、直到無邊可選為止V1V3V2V5V4V6e1e2e3e6e7e5e8e8e4第二節(jié)樹第10頁，課件共70頁，創(chuàng)作于2023年2月1325464332322最小生成樹不一定唯一三、最小生成樹：設(shè)有一連通圖G=(V，L)，對于每一條邊e=(vi,vj),有一個權(quán)wij，一棵生成樹所有樹枝上權(quán)的總和，稱為這個生成樹的權(quán)，具有最小權(quán)的生成樹稱為最小生成樹，簡稱最小樹第二節(jié)樹第11頁，課件共70頁，創(chuàng)作于2023年2月(1)最小生成樹的求法破圈法:每一步任找一個圈，劃去權(quán)值為最大的邊，直到圖中沒圈為止，即得最小樹V1V3V2V5V4V6651532447第二節(jié)樹第12頁，課件共70頁，創(chuàng)作于2023年2月(2)最小生成樹的求法避圈法:每一步從未選的邊中，選一條權(quán)值最小的邊，使已選出的邊不構(gòu)成圈直至不能進行為止，即得最小樹V1V3V2V5V4V6651532447第二節(jié)樹第13頁，課件共70頁，創(chuàng)作于2023年2月V1V4V2V5V7V864523854V3V64543637練習(xí)：用破圈法或避圈法求下圖的最小生成樹，并指出其權(quán)重和

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

車齡每年的維護費用交易費用012345200040005000900012000700060002000100002112第三節(jié)最短路問題第27頁，課件共70頁，創(chuàng)作于2023年2月結(jié)點i表示第i年的年初，當(dāng)i<j時，弧(i,j)表示第i年年初購買一輛新車并一直用到第j年年初?；〉拈L度cij表示：如果第i年年初購買一輛新車并這輛車在第j年年初賣掉更換一輛新新，從第i年年初到第j年年初期間總的凈費用，于是有cij=(i,i+1,..j-1年的維護費用）＋（第i年年初購買新車的費用）－（第j年年初該車的交易費用）1234567777712121221313144122121第三節(jié)最短路問題第28頁，課件共70頁，創(chuàng)作于2023年2月車齡每年的維護費用交易費用01234520004000500090001200070006000200010000c12=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é)最短路問題第29頁，課件共70頁，創(chuàng)作于2023年2月Dijkstra最短路算法：假設(shè)每個弧的權(quán)是非負的，即wij≥0，給每個支點vi記一個數(shù)(稱標號)，標號分臨時性標號T和永久性標號P，永久性標號表示從v1到該點vi的最短路權(quán)，得到永久性標號的不再改變標號，臨時性標號表示從開始點v1到該點vi的最短路權(quán)的上界，算法每一步都把某一點的T標號改為P標號，開始時給初始支點v1標號記為0，即P(v1)=0，其他支點(記為臨時性標號)的標號記為+∞，即T(vi)=+∞,若vi點是剛得到P標號的點，考慮L中與vi點相連的弧(vi,vj)且vj是T標號，對vj的標號進行如下更改：T(vj)=min{T(vj),P(vi)+Wij}比較所有具有T標號的點，把最小者改為P標號，當(dāng)存在兩個以上最小者時，可以同時改為P標號，直到全部點均改為P標號為止第三節(jié)最短路問題第30頁，課件共70頁，創(chuàng)作于2023年2月

例：從發(fā)電廠（記為節(jié)點1）向某城市（記為節(jié)點6）輸送電，必須通過中轉(zhuǎn)站（記為節(jié)點2，3，4，5）轉(zhuǎn)送。圖給出了兩節(jié)點間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。即從節(jié)點1到節(jié)點6的最短路徑。這就是一個最短路問題。第三節(jié)最短路問題第31頁，課件共70頁，創(chuàng)作于2023年2月1325464332322第0步：P(1)=0,T(i)=+∞；第1步：與1相連的標號為2,3，均是T標號，修改2,3的標號，T(2)=min{T(2),P(1)+w12}=4,T(3)=3；在所有的T標號中，3的標號最小，改3的標號為P(3)=3；第2步：修改與3相連的T標號；在所有剩下的T標號中，2的標號最小，改為P(2)=4；第3步：修改與2相連的T標號；在所有剩下的T標號中，5的標號最小，改為P(5)=6；第4步：修改與5相連的T標號；在所有剩下的T標號中，4的標號最小，改為P(4)=7；第5步：修改與4相連的T標號；只剩下節(jié)點6是T標號，修改6的標號，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é)最短路問題第32頁，課件共70頁，創(chuàng)作于2023年2月P(1)=0T(2)=+∞T(4)=+∞T(3)=+∞T(5)=+∞T(6)=+∞T(7)=+∞第2步：與4相連的標號為2,3,5,6，均是T標號，修改2,3,5,6的標號，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標號中，3的標號最小，改3的標號為P(3)=3；T(2)=4T(3)=3T(4)=2P(4)=2第1步：與1相連的標號為2,3，4，均是T標號，修改2,3,4的標號，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標號中，4的標號最小，改4的標號為P(4)=2；T(2)=4T(3)=3T(5)=7T(6)=9第3步：與3相連的是T標號,為5，修改5的標號，T(5)=min{T(5),P(3)+w35}=6在所有的T標號中，2的標號最小，改2的標號為P(2)=4；P(3)=3T(5)=6第4步：與2相連的是T標號,為6，修改6的標號，T(6)=min{T(6),P(4)+w46}=9在所有的T標號中，5的標號最小，改5的標號為P(5)=6；P(2)=4P(5)=6第5步：與5相連的是T標號,為6,7，修改6,7的標號，T(6)=min{T(6),P(5)+w56}=8T(7)=min{T(7),P(5)+w56}=12在所有的T標號中，6的標號最小，改6的標號為P(6)=8；1325464352326722572T(6)=8T(7)=12第6步：與6相連的是T標號,為7，修改7的標號，T(7)=min{T(7),P(6)+w67}=10在所有的T標號中，7的標號最小，改7的標號為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é)最短路問題第33頁，課件共70頁，創(chuàng)作于2023年2月1325465462352572求1到6的最短路最短路徑為1－3－5－6長度為9第三節(jié)最短路問題第34頁，課件共70頁，創(chuàng)作于2023年2月用Excel求解最短路算法凈流量=流出該節(jié)點的流量—流入該節(jié)點的流量

中間節(jié)點的平衡值為0，起點為1，終點為-1。各個點的凈流量等于平衡值最短路平衡流第三節(jié)最短路問題第35頁，課件共70頁，創(chuàng)作于2023年2月P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短路問題第36頁，課件共70頁，創(chuàng)作于2023年2月

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

第三節(jié)最短路問題第38頁，課件共70頁，創(chuàng)作于2023年2月最優(yōu)路線為：1－５－４－６－７－10，最短距離是25第三節(jié)最短路問題第39頁，課件共70頁，創(chuàng)作于2023年2月圖與網(wǎng)絡(luò)樹最短路問題最大流問題最小費用流問題第四節(jié)最大流問題第40頁，課件共70頁，創(chuàng)作于2023年2月最大流量問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出發(fā)點到收點的最大流量第四節(jié)最大流問題第41頁，課件共70頁，創(chuàng)作于2023年2月V1V4V2V5V76634252V3V62321例：某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這個網(wǎng)絡(luò)的一部分如圖所示，由于管理的直徑的變化，它的各段管道(vi,vj)的流量（容量）cij也是不一樣的，cij的單位為萬加侖/小時，如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運送石油，問每小時能運行多少加侖石油？第四節(jié)最大流問題第42頁，課件共70頁，創(chuàng)作于2023年2月設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上總的流量為F，則有目標函數(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é)最大流問題第43頁，課件共70頁，創(chuàng)作于2023年2月最大流問題網(wǎng)絡(luò)圖論的解法1、對網(wǎng)絡(luò)上弧的容量的表示作改進，對條一條弧(vi,vj)的容量用一對數(shù)據(jù)cij,0標在弧(vi,vj)上，以cij靠近vi點，0靠近vj點，表示從vi到vj容許通過的容量為cij，而從vj到vi容許通過的容量為0，這樣可能省云弧的方向vivjcijvivjcijc0對于存在兩條相反的弧(vi,vj)和(vj,vi)，也可以用一條過和一對數(shù)組cij，cji來表示它們的容量vivjcijvivjcijcji第四節(jié)最大流問題第44頁，課件共70頁，創(chuàng)作于2023年2月V1V4V2V5V76634252V3V6232100000000000第四節(jié)最大流問題第45頁，課件共70頁，創(chuàng)作于2023年2月求最大流的基本算法（1）找出一條從發(fā)點到收點的路，在這條路上的每條弧順流方向的容量都大于零，如果不存在這樣的路，則已求得最大流（2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf(3)在這條路上，減少每條弧的順流容量pf，同時增加這些弧的逆流容量pf,返回步驟（1）由于所選路不一樣，計算過程也不一樣，但最終結(jié)果是一樣的，為了使算法快捷有效，我們一般在步驟（1）中盡量選擇包含弧數(shù)最少的路第四節(jié)最大流問題第46頁，課件共70頁，創(chuàng)作于2023年2月第一次迭代選擇路為v1-v4-v7，弧（v4,v7)的順流容量為2，決定pf=2，改進網(wǎng)絡(luò)流量V1V4V2V5V76634252V3V62321000000000000422F=2第四節(jié)最大流問題第47頁，課件共70頁，創(chuàng)作于2023年2月第二次迭代選擇路為v1-v2-v5－v7，?。╲2,v5)的順流容量c35=3，決定pf=3，改進網(wǎng)絡(luò)流量V1V4V2V5V763452V3V623210000000000422F=5032333第四節(jié)最大流問題第48頁，課件共70頁，創(chuàng)作于2023年2月第三次迭代選擇路為v1-v4-v6－v7，?。╲4,v6)的順流容量c46=1，決定pf=1，改進網(wǎng)絡(luò)流量V1V4V2V5V742V3V623210000000422F=6032333303113第四節(jié)最大流問題第49頁，課件共70頁，創(chuàng)作于2023年2月第四次迭代選擇路為v1-v4-v3－v6－v7，弧（v3,v6)的順流容量c36=2，決定pf=2，改進網(wǎng)絡(luò)流量V1V4V2V5V72V3V6232000002F=803233330311311015223第四節(jié)最大流問題第50頁，課件共70頁，創(chuàng)作于2023年2月第五次迭代選擇路為v1-v2-v3－v5－v7，?。╲2,v3)的順流容量c23=2，決定pf=2，改進網(wǎng)絡(luò)流量V1V4V2V5V72V3V620002F=10032333011101522310005225第四節(jié)最大流問題第51頁，課件共70頁，創(chuàng)作于2023年2月V1V4V2V5V7V3V602F=1003011101522310005225網(wǎng)絡(luò)圖中，逆流就是流過每條路徑的流量第四節(jié)最大流問題第52頁，課件共70頁，創(chuàng)作于2023年2月24531142010519152730流量容量

容量網(wǎng)絡(luò)：標有弧容量的網(wǎng)絡(luò)。網(wǎng)絡(luò)流的兩個條件：每個弧的流量不能超過該弧的最大通過能力，即容量；中間支點的流量為零?？尚辛鳎褐虚g點的流量為零。而發(fā)點和收點的流量必須相等。156104610150可行流第四節(jié)最大流問題第53頁，課件共70頁，創(chuàng)作于2023年2月增廣鏈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é)最大流問題第54頁，課件共70頁，創(chuàng)作于2023年2月21st28811任給一個包含收點但不包含發(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é)最大流問題第55頁，課件共70頁，創(chuàng)作于2023年2月求最大流的標號算法從一個可行流f={fij}出發(fā)，（若網(wǎng)絡(luò)中沒有給定f，則可以設(shè)f是零流）需要經(jīng)過標號過程與調(diào)整過程。1．標號過程在這個過程中，網(wǎng)絡(luò)中的點或是標號點或是未標號點。每個標號點的標號包含兩部分：第一標號表示它的標號是從哪一點得到的，以便找出增廣鏈；第二個標號是為確定增廣鏈的調(diào)整量用的。標號過程開始時，總是先給發(fā)點Vs標上(0,+∞)。其余各點標號的規(guī)則是：設(shè)vi是已標號的點，檢查與Vj點關(guān)聯(lián)的另一頂點未標號的弧：（1）如果在弧(vi,vj)上（即前向?。?，fij<cij，則給vj標號(vi,l(vj))，其中l(wèi)(vj)=min{l(vi),cij-fij}。如果fij=cij，則vj不標號。（2）如果在弧(vj,vi)上（即后向?。?，fji>0，則給vj標號(-vi,l(vj))，其中l(wèi)(vj)=min{l(vi),fji}，負號說明經(jīng)后向弧到。如果fij=0，則vi不標號。重復(fù)上述步驟，直到被vj標上號，表明得到一條從vi到vj的增廣鏈C，轉(zhuǎn)入調(diào)整過程。第四節(jié)最大流問題第56頁，課件共70頁，創(chuàng)作于2023年2月求最大流的標號算法2．調(diào)整過程由收點標號算出的作為調(diào)整量（即）。對增廣鏈各弧的調(diào)整如下：

增廣鏈以外各弧流量不變。去掉所有標號，對新的可行流，重新進入標號過程。直到標號過程中斷。當(dāng)前流就是最大流。第四節(jié)最大流問題第57頁，課件共70頁，創(chuàng)作于2023年2月vsv2v1v3vt32223(0,+∞)

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

第四節(jié)最大流問題第58頁，課件共70頁，創(chuàng)作于2023年2月vsv2v1v3vt32223(0,+∞)重復(fù)標號過程。給網(wǎng)絡(luò)中的各個點標號：先給發(fā)點vs標上(0,+∞)。檢查vs給v2標上(vs,1)，檢查v2,在弧(v2,vt)上,f2t=c2t=2,