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

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

由頂點(diǎn)集和弧組成的圖稱(chēng)為有向圖

由頂點(diǎn)集和邊組成的圖稱(chēng)為無(wú)向圖

鏈有一序列弧，如果每一個(gè)弧與前一個(gè)弧恰有一個(gè)公共頂點(diǎn)，則稱(chēng)這一序列弧為一個(gè)鏈。

道路如果鏈中每一個(gè)弧的終點(diǎn)是下面一個(gè)弧的起點(diǎn)，則這個(gè)鏈稱(chēng)為一個(gè)道路。

環(huán)連接a點(diǎn)與b點(diǎn)的一條鏈，如果a與b是同一個(gè)點(diǎn)時(shí)，稱(chēng)此鏈為環(huán)。

連通圖一個(gè)圖中任意兩點(diǎn)間至少有一個(gè)鏈相連，則稱(chēng)此圖為連通圖。

任何一個(gè)不連通圖都可以分為若干個(gè)連通子圖，每一個(gè)子圖稱(chēng)為原圖的一個(gè)分圖。

次:以a點(diǎn)為頂點(diǎn)的邊的條數(shù)稱(chēng)為頂點(diǎn)的次

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

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

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

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

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

中間節(jié)點(diǎn)的平衡值為0，起點(diǎn)為1，終點(diǎn)為-1。各個(gè)點(diǎn)的凈流量等于平衡值最短路平衡流第三節(jié)最短路問(wèn)題第三十五頁(yè)，共七十頁(yè)，2022年，8月28日P(6)=8P(5)=6P(3)=3P(1)=0第三節(jié)最短路問(wèn)題第三十六頁(yè)，共七十頁(yè)，2022年，8月28日

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

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

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

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

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

)中每一條弧是非零流弧

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

第四節(jié)最大流問(wèn)題第五十四頁(yè)，共七十頁(yè)，2022年，8月28日21st28811任給一個(gè)包含收點(diǎn)但不包含發(fā)點(diǎn)的支點(diǎn)集V*，則稱(chēng)i(弧起點(diǎn))不屬于V*，j(弧終點(diǎn))屬于V*的弧(i,j)的全體為割集。割集的容量是割集中所有弧的容量的總和。如果將割集從網(wǎng)絡(luò)中移去，則就不可能有從起點(diǎn)到終點(diǎn)的路徑。一個(gè)網(wǎng)絡(luò)可能有許多割集。任何從發(fā)點(diǎn)到收點(diǎn)的可行流小于等于任何割集的容量。

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

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

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

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

增廣鏈以外各弧流量不變。去掉所有標(biāo)號(hào)，對(duì)新的可行流，重新進(jìn)入標(biāo)號(hào)過(guò)程。直到標(biāo)號(hào)過(guò)程中斷。當(dāng)前流就是最大流。第四節(jié)最大流問(wèn)題第五十七頁(yè)，共七十頁(yè)，2022年，8月28日vsv2v1v3vt32223(0,+∞)

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

第四節(jié)最大流問(wèn)題第五十八頁(yè)，共七十頁(yè)，2022年，8月28日vsv2v1v3vt32223(0,+∞)重復(fù)標(biāo)號(hào)過(guò)程。給網(wǎng)絡(luò)中的各個(gè)點(diǎn)標(biāo)號(hào)：先給發(fā)點(diǎn)vs標(biāo)上(0,+∞)。檢查vs給v2標(biāo)上(vs,1)，檢查v2,在弧(v2,vt)上,f2t=c2t=2,