運籌學(xué)圖與網(wǎng)絡(luò)分析.ppt

《運籌學(xué)圖與網(wǎng)絡(luò)分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《運籌學(xué)圖與網(wǎng)絡(luò)分析.ppt（130頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第5章圖論與網(wǎng)絡(luò)分析,,圖的基本概念,,網(wǎng)絡(luò)分析,最小支撐樹問題最短路徑問題網(wǎng)絡(luò)最大流問題,圖論起源：哥尼斯堡七橋問題,,,問題：一個散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點？,結(jié)論：每個結(jié)點關(guān)聯(lián)的邊數(shù)均為偶數(shù),1圖的基本概念,由點和邊組成，記作G=(V，E)，其中V=(v1，v2，……，vn)為結(jié)點的集合，E=(e1，e2，……，em)為邊的集合。,點表示研究對象,邊表示研究對象之間的特定關(guān)系,1.圖,p114,圖,,無向圖，記作G=(V，E),有向圖，記作D=(V，A),例1：哥尼斯堡橋問題的圖為一個無向圖。,有向圖的邊稱為弧。,2、圖的分類,例,圖1,圖2,3、鏈與路、圈與回路,鏈,點邊交錯的序列,路,點弧交錯的序列,回路,起點=終點的路,,,,,,,,無向圖：,有向圖：,,,,,,,鏈與路中的點均不相同，則稱為初等鏈(路)類似可定義初等圈（回路）,4、連通圖,G1為不連通圖，G2為連通圖,例：,5、支撐子圖,圖G=(V，E)和G=(V，E)，若V=V且EE，則稱G為G的支撐子圖。,G2為G1的支撐子圖,例：,G2是G1的子圖；,例：,6、賦權(quán)圖（網(wǎng)絡(luò)）,圖的每條邊都有一個表示一定實際含義的權(quán)數(shù)，稱為賦權(quán)圖。記作D=(V，A，C)。,例：,2最小支撐樹問題,本節(jié)主要內(nèi)容：,樹,支撐樹,最小支撐樹,,,樹：無圈的連通圖，記為T。,一、樹的概念與性質(zhì),樹的性質(zhì)：（1）樹的任2點間有且僅有1鏈；（2）在樹中任去掉1邊，則不連通；故樹是使圖保持連通且具有最少邊數(shù)的一種圖形（3）在樹中不相鄰2點間添1邊，恰成1圈；（4）若樹T有m個頂點，則T有m-1條邊。,若一個圖G=（V,E）的支撐子圖T=（V,E）構(gòu)成樹，則稱T為G的支撐樹，又稱生成樹。,二、圖的支撐樹,例,,[例]某地新建5處居民點，擬修道路連接5處，經(jīng)勘測其道路可鋪成如圖所示。為使5處居民點都有道路相連，問至少要鋪幾條路？,解：,該問題實為求圖的支撐樹問題，共需鋪4條路。,圖的支撐樹的應(yīng)用舉例,用破圈法求出下圖的一個生成樹。,,,,,最小支撐樹：求網(wǎng)絡(luò)的支撐樹，使其權(quán)和最小。,三、最小支撐樹問題,算法1（破圈法）：①在給定的賦權(quán)的連通圖上找一個圈；②在所找的圈中去掉一條權(quán)數(shù)最大的邊(若有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條)：③若所余下的圖已不含圈，則計算結(jié)束，所余下的圖即為最小支撐樹，否則，返問①。,[例]求上例中的最小支撐樹,解：,5,5.5,,,,,,v1,v2,v3,v4,v5,3.5,7.5,4,2,3,4,,算法2（避圈法）：從某一點開始，把邊按權(quán)從小到大依次添入圖中，若出現(xiàn)圈，則刪去其中最大邊，直至填滿n-1條邊為止（n為結(jié)點數(shù)）。,最小生成樹舉例：某六個城市之間的道路網(wǎng)如圖所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使電話線的總長度最短。,,,,,,,,,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,,,,,[聯(lián)系]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,,,[練習(xí)]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,[例]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,[例]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,[例]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,[例]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,[例]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,此即為最經(jīng)濟的煤氣管道路線，所需的總費用為25萬元,3最短路徑問題,最短路問題是在一個網(wǎng)絡(luò)（賦權(quán)有向圖）中尋找從起點到某個節(jié)點之間一條最短的路線?，F(xiàn)欲求出υ1至υ6距離最短的路徑。,基本思想：從起點vs開始，逐步給每個結(jié)點vj標(biāo)號[dj,vi]，其中dj為起點vs到vj的最短距離，vi為該最短路線上的前一節(jié)點.若給終點vt標(biāo)上號[dt,vi],表示已求出v1至vt的最短路其最短路長為dt，最短路徑可根據(jù)標(biāo)號vi反向追蹤而得,最短路問題的Dijstra解法（狄克拉斯）,,[0,v1],[1,v1],(3)考慮所有這樣的邊[vi,vj]，其中vi∈VA，vj∈VB，挑選其中與起點v1距離最短（min{di+cij}）的vj，對vj進行標(biāo)號,(4)重復(fù)(2)、(3)，直至終點vn標(biāo)上號[dn,vi]，則dn即為v1→vn的最短距離，反向追蹤可求出最短路。,(1)給起點v1標(biāo)號[0,v1],,[0,v1],[1,v1],(3)考慮所有這樣的邊[vi,vj]，其中vi∈VA，vj∈VB，挑選其中與起點v1距離最短（min{di+cij}）的vj，對vj進行標(biāo)號,(4)重復(fù)(2)、(3)，直至終點vn標(biāo)上號[dn,vi]，則dn即為v1→vn的最短距離，反向追蹤可求出最短路。,(1)給起點v1標(biāo)號[0,v1],[3,v1],,[0,v1],[1,v1],[3,v1],[5,v3],,[0,v1],[1,v1],[3,v1],[5,v3],[6,v2],,[0,v1],[1,v1],[3,v1],[5,v3],[6,v2],[9,v5],,,,[0,v1],[1,v1],[3,v1],[5,v3],[6,v2],[9,v5],[10,v5],,,[0,v1],[1,v1],[3,v1],[5,v3],[6,v2],[9,v5],[10,v5],[12,v5],此時終點v9已標(biāo)號[12,v5]，則12即為v1→vn的最短距離，反向追蹤可求出最短路,[0,v1],[1,v1],[3,v1],[5,v3],[6,v2],[9,v5],[10,v5],[12,v5],v1到v9的最短路為：v1→v3→v2→v5→v9，最短距離為12,p119,練習(xí)：用Dijkstra算法求下圖中V1至V8的最短路及最短路長。,關(guān)鍵線路：1.V1--V2--V4--V6--V82.V1--V2--V4—V7--V8最短路長：12,[課堂練習(xí)]無向圖情形,求網(wǎng)絡(luò)中v1至v7的最短路。,,,[課堂練習(xí)]無向圖情形,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,[0,v1],[2,v1],[3,v1],[4,v2/v4],[7,v3],[8,v5],[13,v6],,,,,[課堂練習(xí)]無向圖情形,答案（2）：,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,[0,v1],[2,v1],[3,v1],[4,v2/v4],[7,v3],[8,v5],[13,v6],最短路模型的應(yīng)用——設(shè)備更新問題,例某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購置設(shè)備，每年需支付購置費用；若繼續(xù)使用舊設(shè)備，需要支付維修與運行費用。計劃期（五年）內(nèi)中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設(shè)備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內(nèi)的總費用最小。,最短路模型的應(yīng)用——設(shè)備更新問題,分析：,結(jié)點：V={v1，…，v6}，vi表示第i年初；,?。篈={(vi，vj)}表示第i年初購買，用至第j年初；i=1,…,5;j=2,…,6,權(quán)cij：i年初~j年初的費用，即cij=i年初購買費+（j-i）年里的維修費,通路：表示一個更新策略。例如v1-v2-v6表示第一年購買用到第二年更新，繼續(xù)用至第五年末的一個更新策略,最短路模型的應(yīng)用——設(shè)備更新問題,[0,v1],[16,v1],[22,v1],[30,v1],[41,v1],[53,v3/v4],16,30,22,41,59,16,22,30,41,17,23,31,17,23,18,建模：,求解：,求得兩個最優(yōu)更新策略：v1-v4-v6，即第一年購買設(shè)備，用到第四年更新，再用至第五年年末V1-v3-v6，即第一年購買設(shè)備，用到第三年更新，再用至第五年年末最優(yōu)費用為53,計劃期（五年）內(nèi)中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設(shè)備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內(nèi)的總費用最小。,練習(xí)：設(shè)備更新問題,28,,,,,,,,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,,,,,,,,,,,23,25,26,29,30,42,60,85,32,44,62,33,45,30,算法的基本思路與步驟：首先設(shè)任一點vi到任一點vj都有一條弧。無弧相連的點之間假設(shè)存在權(quán)為+∞的弧相連。從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個點vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程：,(二)Ford法(逐次逼近法)（權(quán)有負(fù)數(shù)）,開始時，令即用v1到vj的直接距離做初始解。,從第二步起，使用遞推公式：,求，當(dāng)進行到第t步，若出現(xiàn),即為v1到各點的最短路長。,則停止計算，,例:,從第二步起，使用遞推公式,從第二步起，使用遞推公式,,,,,,,,,,,,,,,,,,,,,,,,,,,,為了求出從v1到各個點的最短路，一般采用反向追蹤的方法：如果已知d(vs,vj),那么尋求一個點vk,使得d(vs,vk)+wkj=d(vs,vj),然后記錄下(vk,vj)；在看d(vs,vk),尋求一個點vi,使得d(vs,vi)+wik=d(vs,vk)…依次類推，一直到達為止。這樣，從vs到vj的最短路是（vs,…vi,vk,vj）,,d(v1,v8)=6,由于d(v1,v6)+w68=(-1)+7記錄下v6由于d(v1,v3)+w36=d(v1,v6),記錄下v3由于d(v1,v1)+w13=d(v1,v3),于是，從v1到v8的最短路是(v1,v3,v6,v8)。,4網(wǎng)絡(luò)最大流問題,引例：下圖為V1到V6的一交通網(wǎng)，權(quán)表示相應(yīng)運輸線的最大通過能力，制定一方案，使從V1到V6的運輸產(chǎn)品數(shù)量最多。,已知網(wǎng)絡(luò)D=（V，A，C），其中V為頂點集，A為弧集，C={cij}為容量集，cij為弧（vi，vj）上的容量?，F(xiàn)D上要通過一個流f={fij}，其中fij為?。╲i，vj）上的流量。問題：應(yīng)如何安排流量fij可使D上通過的總流量v最大？,一、一般提法,二、最大流問題的數(shù)學(xué)模型,maxv=v（f）,容量約束,平衡約束,P125,滿足上述所有約束條件的流成為可行流。,（1）容量條件：對于每一個弧（vi,vj）∈A，有0≤fij≤cij。（2）平衡條件：對于發(fā)點vs，有對于收點vt，有對于中間點，有為可行流f的流量(發(fā)點的凈輸出量或收點的凈輸入量),1、稱滿足下列條件的流f為可行流：,三、基本概念和定理,可行流特征：（1）容量條件：每一個弧上的流量不能超過該弧的容量。（2）每一個中間點的流入量與流出量的代數(shù)和為零。（轉(zhuǎn)運的作用）（3）出發(fā)點的總流出量與收點的總流入量必相等。,任意一個網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個可行流f,其流量v(f)達到最大值。,可行流中fij＝cij的弧叫做飽和?。籪ij＜cij的弧叫做非飽和弧；fij＞0的弧叫做非零流弧；fij＝0的弧叫做零流弧。,2、飽和弧與零流弧,f為一可行流，u為vs至vt的鏈，令u+={正向弧}，u-={反向弧}。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。,,,,,3、增廣鏈,增廣鏈,,,,,,顯然圖中增廣鏈不止一條,增廣鏈,,,,,,,容量網(wǎng)絡(luò)D=（V，A，C），vs為始點，vt為終點。如果把V分成兩個非空集合使則所有始點屬于V1，而終點屬于的弧的集合，稱為分離vs和vt的截集。,4、截集和截集的截量,截集是連接起點和終點的必經(jīng)之路。,截集中所有弧的容量之和，稱為這個截集的截量，記為,,,,則截集為,設(shè),,容量為24,,,,,設(shè),則截集為,容量為20,流量與截量的關(guān)系：,任一可行流的流量都不會超過任一截集的截量,,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,最大流最小截定理：任一網(wǎng)絡(luò)D中，從vs至vt的最大流的流量等于分離vs、vt的最小截集的容量。,例.如圖所示的網(wǎng)絡(luò)中，弧旁數(shù)字為(cij,fij),v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）確定所有的截集；（2）求最小截集的容量；（3）證明圖中的流為最大流；,,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,①V1={vs}，,截集為{(vs,v1),(vs,v2)}，截量為：6,,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,①V1={vs}，截集為{(vs,v1),(vs,v2)}，截量為：6,②V1={vs,v1}，截集為{(vs,v2),(v1,vt)}，截量為：7,,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,①V1={vs}，截集為{(vs,v1),(vs,v2)}，截量為：6②V1={vs,v1}，截集為{(vs,v2),(v1,vt)}，截量為：7③V1={vs,v2}，截集為{……}，截量為：7,①V1={vs}，截集為{(vs,v1),(vs,v2)}，截量為：6②V1={vs,v1}，截集為{(vs,v2),(v1,vt)}，截量為：7③V1={vs,v2}，截集為{……}，截量為：7④V1={vs,v3}，截集為{……}，截量為：12,,,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,①V1={vs}，截集為{(vs,v1),(vs,v2)}，截量為：6②V1={vs,v1}，截集為{(vs,v2),(v1,vt)}，截量為：7③V1={vs,v2}，截集為{……}，截量為：7④V1={vs,v3}，截集為{……}，截量為：12⑤V1={vs,v1,v2}，截集為{……}，截量為：5,……,（2）最小截量minC(V1,V2)=5；（3）∵v(f*)=5=minC(V1,V2)∴f*是最大流。,最大流判定定理：可行流f*是最大流的充分必要條件是當(dāng)且僅當(dāng)不存在從vs到vt的關(guān)于f*的增廣鏈。,p124,尋求網(wǎng)絡(luò)最大流問題的主要步驟：（1）確定初始可行流（觀察法和零流法）（2）檢驗當(dāng)前可行流是否是網(wǎng)絡(luò)中的最大流(對已知可行流用標(biāo)號法尋找可擴充鏈，若存在，則當(dāng)前可行流不是最大流，轉(zhuǎn)(3)；若不存在，則是最大流）（3）將當(dāng)前的可行流調(diào)整成一個流量更大的新可行流．再由(2)檢驗,四、求最大流方法——標(biāo)號法,思路：從始點開始標(biāo)號，尋找是否存在增廣鏈。給vj標(biāo)號為[θj,vi]，其中θj為調(diào)整量，vi為前一節(jié)點。,標(biāo)號具體步驟：,（b）標(biāo)號終止，說明不存在可擴充鏈，當(dāng)前即為流為最大流，并得最小截集,（a）說明存在可擴充鏈,反向追蹤找出,轉(zhuǎn)(4),,例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。,,,,,,,,,,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,,,步驟：(1)給vs標(biāo)號為[∞,vs]，選與vs關(guān)聯(lián)的流出未飽和弧(vs,vj),給vj標(biāo)號[θj,vs],其中θj=csj-fsj,,,例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。,,,,,,,,,,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,,,,例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。,,,,,,,,,,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,,,,,,,,,,,,,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,,,例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。,vt已標(biāo)號，得到一條增廣鏈u(反向追蹤)，轉(zhuǎn)（5）；vt未標(biāo)號，且無法再標(biāo)號,此時的流為最大流,此時的截集為最小截。,（4）重復(fù)（2）,（3），依次進行的結(jié)局可能為：,,,,,,,,,,,,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,,,例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。,vt已標(biāo)號，得到一條增廣鏈u(反向追蹤)，轉(zhuǎn)（5）；vt未標(biāo)號，且無法再標(biāo)號,此時的流為最大流,此時的截集為最小截。,（4）重復(fù)（2）,（3），依次進行的結(jié)局可能為：,,,,,,,,,,,,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,,,,,,例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。,vt已標(biāo)號，得到一條增廣鏈u(反向追蹤)，轉(zhuǎn)（5）；vt未標(biāo)號，且無法再標(biāo)號,此時的流為最大流,此時的截集為最小截。,（4）重復(fù)（2）,（3），依次進行的結(jié)局可能為：,,例5用標(biāo)號法求下面網(wǎng)絡(luò)的最大流。,(5)調(diào)整。取=θt，令,，得新流{fij}轉(zhuǎn)(1)。,,,,,,,,,,,,,（2,2）,（1,0）,（3,3）,（1,1）,（4,4）,（5,2）,（3,0）,（2,1）,（5,4）,,,此時標(biāo)號無法進行，當(dāng)前流為最大流，最大流量為5；最小截為{(vs,v2),(v1,v3)}，截量為：5,練習(xí)：有三個發(fā)電站v1,v2,v3，發(fā)電能力分別為15、10和40兆瓦，經(jīng)輸電網(wǎng)可把電力送到8號地區(qū)，電網(wǎng)能力如圖所示。求三個發(fā)電站輸?shù)皆摰貐^(qū)的最大電力。,v0,,,（1）由于網(wǎng)絡(luò)圖中只有一個發(fā)點和一個收點，所以有必要添加一個虛設(shè)的起點和弧弧上各容量為，分別為三點的發(fā)電能力，如圖所示：,v0,10,10,15,15,15,0,10,10,10,10,15,25,(2)由觀察法得一初始可行流即圖上所標(biāo)。為弧上容量，為弧上流量。,(2)由觀察法得一初始可行流即圖上所標(biāo)。為弧上容量，為弧上流量。,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),(3)用標(biāo)號法尋找可擴充鏈,v0,||,||,v6,||,v5,v4,||,v2,v1,v7,v8,反向追蹤，得一v0-v8的可擴充鏈:v0-v3-v6-v5-v2-v7-v8,,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),v0,||,||,v6,||,v5,v4,||,v2,v1,v7,v8,,,(4)調(diào)整流量。由可擴充鏈確定一新可行流，可擴充鏈上前向弧上流量均增加,(45,35),(40,20),(10,10),(20,20),(30,20),(40,20),(5)繼續(xù)用標(biāo)號法檢驗當(dāng)前可行流是否為最大流,v3,(40,20),(15,15),(30,20),(15,15),(45,35),(10,10),(15,15),(10,10),(20,20),v0,(10,10),(15,15),(40,20),v0,||,||,v6,||,v5,v4,v2,v1,v7,v8,||,標(biāo)號完畢，且終點未標(biāo)號。這說明網(wǎng)絡(luò)中已找不到可擴充鏈，當(dāng)前即為最大流，最大流流量為：20+15+10＝45即三個發(fā)電站輸送到8號地區(qū)的最大電力為45兆瓦。,練習(xí)：圖中A、B、C、D、E、F分別表示陸地和島嶼，①②……⒁表示橋梁及其編號。河兩岸分別互為敵對的雙方部隊占領(lǐng)，問至少應(yīng)切斷幾座橋梁（具體指出編號）才能達到阻止對方部隊過河的目的。試用圖論方法進行分析。,分析：轉(zhuǎn)化為一個網(wǎng)絡(luò)圖，弧的容量為兩點間的橋梁數(shù)。,則問題為求最小截。,步驟（1）確定初始可行流,1(1),1(0),分析：轉(zhuǎn)化為一個網(wǎng)絡(luò)圖，弧的容量為兩點間的橋梁數(shù)。,則問題為求最小截。,答案：最小截為{AE、CD、CF},A,B,C,D,E,F,,,,,,2(1),1(1),1(1),1(1),1(0),2(2),2(1),2(1),2(1),2(2),2(2),,步驟（1）確定初始可行流,（2）標(biāo)號法求最大流得最小截,,,1(0),,1(0),,2(0),,2(0),,2(0),案例：有一批人從我國A城赴俄羅斯B城，可能的旅行路線如圖：,邊防隊擬建立足夠數(shù)量檢查站以便使每輛汽車至少必經(jīng)過一個檢查站，建立檢查站的費用根據(jù)各路段條件有所不同（如圖數(shù)字所示），求最小費用解。,（分析：最小截問題）,分析：轉(zhuǎn)化為一個網(wǎng)絡(luò)圖，弧的容量為各路段得費用。則問題為求最小截。步驟,a,B,A,b,c,d,e,f,g,4,6,8,2,3,2,5,7,3,8,4,3,7,6,4,4(4),6(6),8(3),2(2),3(3),2(2),5(5),7(6),3(0),8(4),4(3),3(3),7(3),6(6),4(4),,,（1）確定初始可行流,（2）標(biāo)號法求最大流得最小截,答案：最小截為{Aa、Ab、cb}，即在這三個路段修建檢查站，最小費用為13,案例：垃圾處理問題某地區(qū)有3個城鎮(zhèn)，各城鎮(zhèn)每天產(chǎn)生的垃圾要運往該地區(qū)的4個垃圾處理場處理，現(xiàn)考慮各城鎮(zhèn)到各處理場的道路對各城鎮(zhèn)垃圾外運的影響。假設(shè)各城鎮(zhèn)每日產(chǎn)生的垃圾量、各處理場的日處理能力及各條道路（可供運垃圾部分）的容量（其中容量為0表示無此直接道路）如右表所示，試用網(wǎng)絡(luò)流方法分析目前的道路狀況能否使所有垃圾都運到處理場得到處理，如果不能，應(yīng)首先拓寬哪條道路。,分析：轉(zhuǎn)化為一個網(wǎng)絡(luò)圖，弧的容量為各路段能處理垃圾的數(shù)量。,a,b,c,1,2,3,4,s,t,,,,,,,,,,,,,,,,,80,50,40,20,50,60,40,90,30,20,70,30,50,10,20,40,則問題為求最小截。,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),80,50,40,20,50,60,40,90,20,70,30,50,10,20,40,s,,,,,,,,,,,,,,,,,（1）確定初始可行流,30,（2）標(biāo)號法求最大流得最小截,4,c,3,2,1,a,t,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),s,,,,,,,,,,,,,,,,,（3）反向追蹤，找可擴充鏈,4,c,3,2,1,a,t,,90(40),,20(20),,50(10),,40(20),,70(40),,得一s-t的可擴充鏈:,s-b-4-c-3-t，調(diào)整量,b,90(40),50(10),40(20),70(40),80(80),50(30),40(20),20(20),60(60),40(40),30(30),20(20),30(30),50(50),10(0),20(20),,,,,,,,,,,,,,,,,（4）重復(fù)標(biāo)號,3,2,1,a,t,s,4,c,a,2,1,a,3,（5）反向追蹤，找可擴充鏈,,,,,（6）找到可擴充流S-b-4-c-3-t,調(diào)整量為10,,,,b,80(80),50(40),40(20),20(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),,,,,,,,,,,,,,,,,3,2,1,a,t,s,4,c,a,2,1,a,3,,,,,（6）找到可擴充流S-b-4-c-3-t,調(diào)整量為10,90(50),50(0),40(30),70(50),,,,90(50),20(20),50(0),40(30),70(50),80(80),50(40),40(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),,,,,,,,,,,,,,,,,（4）重復(fù)標(biāo)號，直至終止,3,2,1,a,t,c,3,2,1,a,t,s,b,4,答案：最小截為{sa、sc、b3、4t},垃圾最大處理量為180<50+70+80,,,,,答案,綜上，目前的道路狀況不能使所有垃圾都運到處理場得到處理。從圖上不難發(fā)現(xiàn)，理論上應(yīng)當(dāng)拓寬割集所在的道路。但由于sa,sc和4t都是添加的虛擬道路，所以只有拓寬割集中的b3道路的路寬，或者增大4號處理場處理垃圾的能力，才能解決問題。,練習(xí)：過紐約ALBANY的北-南高速公路，路況通過能力如下圖所示，圖中弧上數(shù)字單位：千輛/小時。求（1）該路網(wǎng)能承受的北-南向最大流量；（2）若要擴充通過能力，應(yīng)在那一組路段上擴充，說明原因。,(1)選取一個可行流,,,,,,,1,2,3,5,4,6,,,,,,,（,,進入Albany(北),離開Albany(南),2(2),4(1),3(0),1(1),6(5),3(3),2(2),3(3),6(2),,,,1(1),,,,,,,,V1—V4—V2—V5—V6，可擴充量為1，調(diào)整成新流，繼續(xù)標(biāo)號,,,,,,,,,,,用標(biāo)號法得可擴充鏈,,,,,,,,,1,2,3,5,4,6,,,,,,（,進入Albany(北),離開Albany(南),2(2),4(2),3(1),1(1),6(5),3(3),2(2),3(3),6(3),,,,1(0),,,,標(biāo)號終止，當(dāng)前流為最大流，最大流量為8割集為：12,45，46，36應(yīng)該在割集弧上擴大流量,,,,,,,,[練習(xí)1],[0,v1],[4,v1],[3,v1],[5,v2],[6,v2],[9,v7],[7,v4/v6],[8.5,v6],[6,v2],有9個城市v1、v2、…v9，其公路網(wǎng)如圖所示。弧旁數(shù)字是該段公路的長度，有一批物資要從v1運到v9，問走哪條路最近？,習(xí)題課練習(xí)（最小支撐樹）,已知有A、B、C、D、E、F六個城鎮(zhèn)間的道路網(wǎng)絡(luò)如圖，現(xiàn)要在六個城鎮(zhèn)間架設(shè)通訊網(wǎng)絡(luò)（均沿道路架設(shè)），每段道路上的架設(shè)費用如圖。求能保證各城鎮(zhèn)均能通話且總架設(shè)費用最少的架設(shè)方案。,[練習(xí)2],第四節(jié)最小費用最大流問題,在實際的網(wǎng)絡(luò)系統(tǒng)中，當(dāng)涉及到有關(guān)流的問題的時候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網(wǎng)絡(luò)流，即要考慮網(wǎng)絡(luò)流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問題。,設(shè)一個網(wǎng)絡(luò)D=（V，A，C），對于每一個弧(vi,vj)∈A,給定一個單位流量的費用bij?0，網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流f，并且流的總費用達到最小。,而此時總費用b(f)比b(f)增加了,我們將叫做這條增廣鏈的費用。,我們首先考察，在一個網(wǎng)絡(luò)D中，當(dāng)沿可行流f的一條增廣鏈μ，以調(diào)整量θ=1改進f，得到的新可行流f的流量，有v(f)=v(f)+1,顯然，零流f={0}是流量為0的最小費用流。一般地，尋求最小費用流，總可以從零流f={0}開始。問題是：如果已知f是流量為v(f)的最小費用流，如何尋找關(guān)于f的最小費用增廣鏈？,結(jié)論：若f是流量為v(f)的所有可行流中的費用最小，而?是關(guān)于f的所有增廣鏈中的費用最小的增廣鏈，則f沿增廣鏈μ調(diào)整量為1得到的新可行流f，一定是流量為v(f)+1的所有可行流中的最小費用流。依次類推，當(dāng)f是最大流時，就是所要求的最小費用最大流。,若u是從vs到vt關(guān)于f的增廣鏈，它的費用,若果把u-中的邊(vi,vj)反向，并且令它的權(quán)是-bij，而u+中的方向不變，并且的它的權(quán)是bij，這樣就把求從vs到vt關(guān)于f的最小費用增廣鏈就轉(zhuǎn)換成尋求從vs到vt的最短路。,構(gòu)造一個賦權(quán)有向圖M(f)，其頂點是原網(wǎng)絡(luò)D的頂點，他的邊根據(jù)f的情況確定：,若原圖中（vi，vj）邊中fij=0，則M(f)中連接（vi，vj）,并令其權(quán)L(vi,vj)=bij；若原圖中（vi，vj）邊中fij=cij，則M(f)中連接（vi，vj）,并令其權(quán)L(vi,vj)=-bij；若原圖中（vi，vj）邊中fij=0，則M(f)中連接（vi，vj）和(vj,vi),并令其權(quán)L(vi,vj)=bij,L(vi,vj)=-bij；,步驟：（1）取零流為初始可行流，f(0)={0}。（2）一般地，如果在第k-1步得到最小費用流f(k-1)，則構(gòu)造圖L(f(k-1))。（3）在L(f(k-1))中，尋求從vs到vt的最短路。若不存在最短路，則f(k-1)就是最小費用最大流；否則轉(zhuǎn)(4)。（4）如果存在最短路，則在可行流f(k－1)的圖中得到與此最短路相對應(yīng)的增廣鏈，在增廣鏈上，對f(k－1)進行調(diào)整，調(diào)整量為：,得到新可行流f(k)。對f(k)重復(fù)上面步驟，返回（2）。,例求圖8-24所示網(wǎng)絡(luò)中的最小費用最大流，弧旁的權(quán)是（bij,cij）.,圖8-24,4,由于在M(f(4))中已經(jīng)不存在從vs到vt的最短路，因此，可行流f(4)，v(f(4))=11是最小費用最大流。,例8.11求網(wǎng)絡(luò)的最小費用最大流，弧旁權(quán)是（bij,cij）,