運籌學圖與網絡分析課件

第5章圖論與網絡分析

圖的基本概念網絡分析最小支撐樹問題

最短路徑問題網絡最大流問題運籌學圖與網絡分析ABCDACBD圖論起源：哥尼斯堡七橋問題問題：一個散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點？結論：每個結點關聯(lián)的邊數均為偶數運籌學圖與網絡分析§1圖的基本概念由點和邊組成，記作G=(V，E)，其中V=(v1，v2，……，vn)為結點的集合，E=(e1，e2，……，em)為邊的集合。點表示研究對象邊表示研究對象之間的特定關系1.圖p114運籌學圖與網絡分析圖無向圖，記作G=(V，E)有向圖，記作D=(V，A)例1：哥尼斯堡橋問題的圖為一個無向圖。有向圖的邊稱為弧。例2：五個球隊的比賽情況，v1v2表示v1勝v2。v1v2v3v4v52、圖的分類運籌學圖與網絡分析v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例圖1運籌學圖與網絡分析v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}圖2運籌學圖與網絡分析v1v2v3v4v53、鏈與路、圈與回路鏈點邊交錯的序列圈起點=終點的鏈路點弧交錯的序列回路起點=終點的路v1v2v3v4v5無向圖：有向圖：鏈與路中的點均不相同，則稱為初等鏈

(路)類似可定義初等圈（回路）運籌學圖與網絡分析4、連通圖任何兩點之間至少存在一條鏈的圖稱為連通圖，否則稱為不連通圖。G1G2G1為不連通圖，G2為連通圖例：運籌學圖與網絡分析5、支撐子圖圖G=(V，E)和G'=(V'，E')，若V=V'且E'E，則稱G'為G的支撐子圖。G2為G1的支撐子圖v1v2v3v4v5G1v1v2v3v4v5G2例：運籌學圖與網絡分析G2是G1的子圖；v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)例：運籌學圖與網絡分析6、賦權圖（網絡）圖的每條邊都有一個表示一定實際含義的權數，稱為賦權圖。記作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例：運籌學圖與網絡分析§2最小支撐樹問題本節(jié)主要內容：樹支撐樹最小支撐樹

[例]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222225452634531運籌學圖與網絡分析樹：無圈的連通圖，記為T。一、樹的概念與性質樹的性質：（1）樹的任2點間有且僅有1鏈；（2）在樹中任去掉1邊，則不連通；故樹是使圖保持連通且具有最少邊數的一種圖形（3）在樹中不相鄰2點間添1邊，恰成1圈；（4）若樹T有m個頂點，則T有m-1條邊。(A)(B)(C)運籌學圖與網絡分析若一個圖G=（V,E）的支撐子圖T=（V,E′）構成樹，則稱T為G的支撐樹，又稱生成樹。二、圖的支撐樹(G)(G1)(G2)(G3)(G4)例運籌學圖與網絡分析[例]某地新建5處居民點，擬修道路連接5處，經勘測其道路可鋪成如圖所示。為使5處居民點都有道路相連，問至少要鋪幾條路？解：該問題實為求圖的支撐樹問題，共需鋪4條路。v1v2v3v4v5

圖的支撐樹的應用舉例v1v2v3v4v555.53.57.5423運籌學圖與網絡分析用破圈法求出下圖的一個生成樹。

v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8運籌學圖與網絡分析最小支撐樹：求網絡的支撐樹，使其權和最小。三、最小支撐樹問題算法1（破圈法）：①在給定的賦權的連通圖上找一個圈；②在所找的圈中去掉一條權數最大的邊(若有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條)：③若所余下的圖已不含圈，則計算結束，所余下的圖即為最小支撐樹，否則，返問①。運籌學圖與網絡分析55.5v1v2v3v4v53.57.5423[例]求上例中的最小支撐樹解：55.5v1v2v3v4v53.57.5423運籌學圖與網絡分析55.5v1v2v3v4v53.57.54233v12v4v545v23.5v3算法2（避圈法）：從某一點開始，把邊按權從小到大依次添入圖中，若出現(xiàn)圈，則刪去其中最大邊，直至填滿n-1條邊為止（n為結點數）。運籌學圖與網絡分析最小生成樹舉例：某六個城市之間的道路網如圖所示，要求沿著已知長度的道路聯(lián)結六個城市的電話線網，使電話線的總長度最短。

v1v2v3v4v5v66515723445v1v4v5v6v2v31234運籌學圖與網絡分析v1v2v3v4v514231352運籌學圖與網絡分析

[聯(lián)系]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222225452634531運籌學圖與網絡分析

[練習]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS222222452634531運籌學圖與網絡分析

[例]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222252634531運籌學圖與網絡分析

[例]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222222634531運籌學圖與網絡分析

[例]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。ABCDEFGHIJKS2222222634531運籌學圖與網絡分析

[例]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。IABCDEFGHJKS222222234531運籌學圖與網絡分析

[例]今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。IJABCDEFGHKS22222223431此即為最經濟的煤氣管道路線，所需的總費用為25萬元運籌學圖與網絡分析§3最短路徑問題最短路問題是在一個網絡（賦權有向圖）中尋找從起點到某個節(jié)點之間一條最短的路線?，F(xiàn)欲求出υ1至υ6距離最短的路徑。運籌學圖與網絡分析基本思想：從起點vs開始，逐步給每個結點vj標號[dj,vi]，其中dj為起點vs到vj的最短距離，vi為該最短路線上的前一節(jié)點.

若給終點vt標上號[dt,vi],表示已求出v1至vt的最短路其最短路長為dt，最短路徑可根據標號vi反向追蹤而得最短路問題的Dijstra解法（狄克拉斯）運籌學圖與網絡分析v2v1v3v4v5v6v7v8v9163222266133101044例題：求網絡中v1到v9的最短路運籌學圖與網絡分析10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](3)考慮所有這樣的邊[vi,vj]，其中vi∈VA，vj∈VB，挑選其中與起點v1距離最短（min{di+cij}）的vj，對vj進行標號(4)重復(2)、(3)，直至終點vn標上號[dn,vi]，則dn即為v1→vn的最短距離，反向追蹤可求出最短路。(1)給起點v1標號[0,v1](2)把頂點集V分成VA:已標號點集VB：未標號點集運籌學圖與網絡分析10v2v1v3v4v5v6v7v8v91632222661331044[0,v1][1,v1](3)考慮所有這樣的邊[vi,vj]，其中vi∈VA，vj∈VB，挑選其中與起點v1距離最短（min{di+cij}）的vj，對vj進行標號(4)重復(2)、(3)，直至終點vn標上號[dn,vi]，則dn即為v1→vn的最短距離，反向追蹤可求出最短路。(1)給起點v1標號[0,v1](2)把頂點集V分成VA:已標號點集VB：未標號點集[3,v1]運籌學圖與網絡分析[0,v1][1,v1][3,v1][5,v3]10v2v1v3v4v5v6v7v8v91632222661331044運籌學圖與網絡分析[0,v1][1,v1][3,v1][5,v3][6,v2]10v2v1v3v4v5v6v7v8v91632222661331044運籌學圖與網絡分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5]10v2v1v3v4v5v6v7v8v91632222661331044運籌學圖與網絡分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5]10v2v1v3v4v5v6v7v8v91632222661331044運籌學圖與網絡分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]此時終點v9已標號[12,v5]，則12即為v1→vn的最短距離，反向追蹤可求出最短路10v2v1v3v4v5v6v7v8v91632222661331044運籌學圖與網絡分析[0,v1][1,v1][3,v1][5,v3][6,v2][9,v5][10,v5][12,v5]v1到v9的最短路為：v1→v3→v2→v5→v9，最短距離為1210v2v1v3v4v5v6v7v8v91632222661331044p119運籌學圖與網絡分析

5V5V24541V612455V4V1V8238V7V37練習：用Dijkstra算法求下圖中V1至V8的最短路及最短路長。運籌學圖與網絡分析關鍵線路：1.V1--V2--V4--V6--V82.V1--V2--V4—V7--V8最短路長：12V3

5V5V24541V612455V4V1V8238V77(0,V1)(1,V1)(2,V1)(6,V2)(5,V2)(9,V4)(7,V4)(12,V6/V7)運籌學圖與網絡分析[課堂練習]無向圖情形求網絡中v1至v7的最短路。v1v2v3v4v5v6v7225355715713運籌學圖與網絡分析[課堂練習]無向圖情形v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]運籌學圖與網絡分析[課堂練習]無向圖情形答案（2）：v1v2v3v4v5v6v7225355715713[0,v1][2,v1][3,v1][4,v2/v4][7,v3][8,v5][13,v6]運籌學圖與網絡分析最短路模型的應用——設備更新問題第i年12345價格ai1111121213使用壽命0~11~22~33~44~5費用bj5681118例某工廠使用一種設備，這種設備在一定的年限內隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設備是否更新。若購置設備，每年需支付購置費用；若繼續(xù)使用舊設備，需要支付維修與運行費用。計劃期（五年）內中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內的總費用最小。

運籌學圖與網絡分析最短路模型的應用——設備更新問題分析：結點：V={v1，…，v6}，vi表示第i年初；?。篈={(vi，vj)}表示第i年初購買，用至第j年初；i=1,…,5;j=2,…,6權cij：i年初~j年初的費用，即cij=i年初購買費+（j-i）年里的維修費通路：表示一個更新策略。例如v1-v2-v6表示第一年購買用到第二年更新，繼續(xù)用至第五年末的一個更新策略運籌學圖與網絡分析最短路模型的應用——設備更新問題v2v1v3v4v5v6第i年12345價格ai1111121213使用壽命0~11~22~33~44~5費用bj5681118[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]163022415916223041172331172318建模：求解：運籌學圖與網絡分析v2v1v3v4v5v6[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]163022415916223041172331172318求得兩個最優(yōu)更新策略：v1-v4-v6，即第一年購買設備，用到第四年更新，再用至第五年年末V1-v3-v6，即第一年購買設備，用到第三年更新，再用至第五年年末最優(yōu)費用為53運籌學圖與網絡分析計劃期（五年）內中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內的總費用最小。

年份12345購置費1820212324使用年數0~11~22~33~44~5維修費57121825練習：設備更新問題運籌學圖與網絡分析年份12345購置費1820212324使用年數0~11~22~33~44~5維修費5712182528v1v2v3v4v5v62325262930426085324462334530運籌學圖與網絡分析算法的基本思路與步驟：首先設任一點vi到任一點vj都有一條弧。無弧相連的點之間假設存在權為+∞的弧相連。從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個點vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程：

(二)Ford法(逐次逼近法)

（權有負數）運籌學圖與網絡分析開始時，令即用v1到vj的直接距離做初始解。從第二步起，使用遞推公式：求，當進行到第t步，若出現(xiàn)即為v1到各點的最短路長。則停止計算，運籌學圖與網絡分析例:

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837運籌學圖與網絡分析從第二步起，使用遞推公式

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837運籌學圖與網絡分析從第二步起，使用遞推公式

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837運籌學圖與網絡分析

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66運籌學圖與網絡分析

為了求出從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）v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66運籌學圖與網絡分析v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66d(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網絡最大流問題引例：下圖為V1到V6的一交通網，權表示相應運輸線的最大通過能力，制定一方案，使從V1到V6的運輸產品數量最多。v2v1v3v4v5v681041755311635312213362運籌學圖與網絡分析已知網絡D=（V，A，C），其中V為頂點集，A為弧集，C={cij}為容量集，cij為?。╲i，vj）上的容量。現(xiàn)D上要通過一個流f={fij}，其中fij為?。╲i，vj）上的流量。問題：應如何安排流量fij可使D上通過的總流量v最大？v2v1v3v4v5v681041755311635312213362一、一般提法運籌學圖與網絡分析二、最大流問題的數學模型maxv=v（f）容量約束平衡約束s.t.v2Vsv3v4v5Vt81041755311635312213362P125滿足上述所有約束條件的流成為可行流。運籌學圖與網絡分析

（1）容量條件：對于每一個弧（vi,vj）∈A，有0≤

fij

≤

cij

。（2）平衡條件：對于發(fā)點vs，有對于收點vt

，有對于中間點，有為可行流f的流量(發(fā)點的凈輸出量或收點的凈輸入量)1、稱滿足下列條件的流f為可行流：三、基本概念和定理運籌學圖與網絡分析

可行流特征：（1）容量條件：每一個弧上的流量不能超過該弧的容量。（2）每一個中間點的流入量與流出量的代數和為零。（轉運的作用）（3）出發(fā)點的總流出量與收點的總流入量必相等。任意一個網絡上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。

網絡系統(tǒng)中最大流問題就是在給定的網絡上尋求一個可行流f,其流量v(f)達到最大值。運籌學圖與網絡分析可行流中fij＝cij

的弧叫做飽和弧；

fij＜cij的弧叫做非飽和??；

fij＞0的弧叫做非零流弧；

fij＝0的弧叫做零流弧。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2、飽和弧與零流弧運籌學圖與網絡分析f為一可行流，u為vs至vt的鏈，令u+={正向弧}，u-={反向弧}。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關于f的一條增廣鏈。v2v1v3v4v5v6810417553116353122133623、增廣鏈運籌學圖與網絡分析增廣鏈v2v1v3v4v5v681041755311635312213362顯然圖中增廣鏈不止一條運籌學圖與網絡分析增廣鏈v2v1v3v4v5v681041755311635312213362運籌學圖與網絡分析

容量網絡D=（V，A，C），vs為始點，vt為終點。如果把V分成兩個非空集合使則所有始點屬于V1，而終點屬于的弧的集合，稱為分離vs和vt的截集。4、截集和截集的截量截集是連接起點和終點的必經之路。

截集中所有弧的容量之和，稱為這個截集的截量，記為運籌學圖與網絡分析vsv1v2v4v3vt374556378V運籌學圖與網絡分析13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)則截集為設容量為24運籌學圖與網絡分析13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設則截集為容量為20運籌學圖與網絡分析流量與截量的關系：任一可行流的流量都不會超過任一截集的截量v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）最大流最小截定理：任一網絡D中，從vs至vt的最大流的流量等于分離vs、vt的最小截集的容量。運籌學圖與網絡分析例.如圖所示的網絡中，弧旁數字為(cij,fij)v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）確定所有的截集；（2）求最小截集的容量；（3）證明圖中的流為最大流；運籌學圖與網絡分析v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①V1={vs}，截集為{(vs,v1),(vs,v2)}，截量為：6運籌學圖與網絡分析v1vsv2v3vt（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運籌學圖與網絡分析v1vsv2v3vt（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}，截集為{……}，截量為：12v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：運籌學圖與網絡分析v1vsv2v3vt（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……運籌學圖與網絡分析v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（2）最小截量minC(V1,V2)=5；（3）∵v(f*)=5=minC(V1,V2)∴f*是最大流。運籌學圖與網絡分析最大流判定定理：

可行流f*是最大流的充分必要條件是當且僅當不存在從vs到vt

的關于f*的增廣鏈。

p124運籌學圖與網絡分析尋求網絡最大流問題的主要步驟：

（1）確定初始可行流（觀察法和零流法）

（2）檢驗當前可行流是否是網絡中的最大流(對已知可行流用標號法尋找可擴充鏈，若存在，則當前可行流不是最大流，轉(3)；若不存在，則是最大流）

（3）將當前的可行流調整成一個流量更大的新可行流．再由(2)檢驗四、求最大流方法——標號法思路：從始點開始標號，尋找是否存在增廣鏈。給vj標號為[θj,vi]，其中θj為調整量，vi為前一節(jié)點。運籌學圖與網絡分析標號具體步驟：檢查所有已標號點與沒標號點的關聯(lián)弧流出弧和流入弧運籌學圖與網絡分析（b）標號終止，說明不存在可擴充鏈，當前即為流為最大流，并得最小截集（a）說明存在可擴充鏈,反向追蹤找出,轉(4)運籌學圖與網絡分析例5用標號法求下面網絡的最大流。（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6步驟：(1)給vs標號為[∞,vs]，選與vs關聯(lián)的流出未飽和弧(vs,vj),給vj標號[θj,vs],其中θj=csj-fsj運籌學圖與網絡分析例5用標號法求下面網絡的最大流。（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6(2)把節(jié)點集V分為VA：已標號點集VB：未標號點集運籌學圖與網絡分析例5用標號法求下面網絡的最大流。（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6（3）考慮所有弧(vi,vj)或(vj,

vi),其中vi∈VA,vj∈VB，若該弧為流出未飽弧,則給vj標號[θj,vi],其中θj=min(cij-fij，θi）流入非零弧,則給vj標號[θj,-vi],其中θj=min(fij，θi）運籌學圖與網絡分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用標號法求下面網絡的最大流。vt已標號，得到一條增廣鏈u(反向追蹤)，轉（5）；vt未標號，且無法再標號,此時的流為最大流,此時的截集為最小截。（4）重復（2）,（3），依次進行的結局可能為：運籌學圖與網絡分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用標號法求下面網絡的最大流。vt已標號，得到一條增廣鏈u(反向追蹤)，轉（5）；vt未標號，且無法再標號,此時的流為最大流,此時的截集為最小截。（4）重復（2）,（3），依次進行的結局可能為：運籌學圖與網絡分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用標號法求下面網絡的最大流。vt已標號，得到一條增廣鏈u(反向追蹤)，轉（5）；vt未標號，且無法再標號,此時的流為最大流,此時的截集為最小截。（4）重復（2）,（3），依次進行的結局可能為：運籌學圖與網絡分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6例5用標號法求下面網絡的最大流。(5)調整。取=θt，令，得新流{fij'}轉(1)。運籌學圖與網絡分析（2,2）（1,1）（3,3）（1,1）（4,3）（5,1）（3,0）（2,1）（5,3）vsv2v1v3v4v6（2,2）（1,0）（3,3）（1,1）（4,4）（5,2）（3,0）（2,1）（5,4）vsv2v1v3v4v6運籌學圖與網絡分析（2,2）（1,0）（3,3）（1,1）（4,4）（5,2）（3,0）（2,1）（5,4）vsv2v1v3v4v6此時標號無法進行，當前流為最大流，最大流量為5；最小截為{(vs,v2),(v1,v3)}，截量為：5運籌學圖與網絡分析練習：有三個發(fā)電站v1,v2,v3，發(fā)電能力分別為15、10和40兆瓦，經輸電網可把電力送到8號地區(qū)，電網能力如圖所示。求三個發(fā)電站輸到該地區(qū)的最大電力。v2v1v3v4v5v6v7v8401530154510151020運籌學圖與網絡分析v0101540v2v1v3v4v5v6v7v8401530154510151020（1）由于網絡圖中只有一個發(fā)點和一個收點，所以有必要添加一個虛設的起點和弧弧上各容量為，分別為三點的發(fā)電能力，如圖所示：運籌學圖與網絡分析v2v1v3v4v5v6v7v8401530154510151020v010154010101515150101010101525(2)由觀察法得一初始可行流即圖上所標。

為弧上容量，為弧上流量。運籌學圖與網絡分析(2)由觀察法得一初始可行流即圖上所標。

為弧上容量，為弧上流量。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)用標號法尋找可擴充鏈v0||||v6||v5v4||v2v1v7v8反向追蹤，得一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||v5v4||v2v1v7v8(4)調整流量。由可擴充鏈確定一新可行流，可擴充鏈上前向弧上流量均增加(45,35)(40,20)(10,10)(20,20)(30,20)(40,20)運籌學圖與網絡分析(5)繼續(xù)用標號法檢驗當前可行流是否為最大流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||v5v4v2v1v7v8||標號完畢，且終點未標號。這說明網絡中已找不到可擴充鏈，當前即為最大流，最大流流量為：20+15+10＝45即三個發(fā)電站輸送到8號地區(qū)的最大電力為45兆瓦。運籌學圖與網絡分析練習：圖中A、B、C、D、E、F分別表示陸地和島嶼，①②……⒁表示橋梁及其編號。河兩岸分別互為敵對的雙方部隊占領，問至少應切斷幾座橋梁（具體指出編號）才能達到阻止對方部隊過河的目的。試用圖論方法進行分析。ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁運籌學圖與網絡分析分析：轉化為一個網絡圖，弧的容量為兩點間的橋梁數。則問題為求最小截。ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁步驟（1）確定初始可行流2112ABCDEF21112122221122運籌學圖與網絡分析1(1)1(0)分析：轉化為一個網絡圖，弧的容量為兩點間的橋梁數。則問題為求最小截。答案：最小截為{AE、CD、CF}ABCDEF2(1)1(1)1(1)1(1)1(0)2(2)2(1)2(1)2(1)2(2)2(2)步驟（1）確定初始可行流（2）標號法求最大流得最小截1(0)1(0)2(0)2(0)2(0)ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁運籌學圖與網絡分析ABDEFC①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁F2ABCDE21111122222211221答案：至少應當切掉3座橋，分別是AE：（12）號橋，CD：(7)號橋，CF：(6)號橋運籌學圖與網絡分析案例：有一批人從我國A城赴俄羅斯B城，可能的旅行路線如圖：邊防隊擬建立足夠數量檢查站以便使每輛汽車至少必經過一個檢查站，建立檢查站的費用根據各路段條件有所不同（如圖數字所示），求最小費用解。aBAbcdefg468232573843764（分析：最小截問題）運籌學圖與網絡分析分析：轉化為一個網絡圖，弧的容量為各路段得費用。則問題為求最小截。步驟aBAbcdefg4682325738437644(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）標號法求最大流得最小截答案：最小截為{Aa、Ab、cb}，即在這三個路段修建檢查站，最小費用為13運籌學圖與網絡分析案例：垃圾處理問題某地區(qū)有3個城鎮(zhèn)，各城鎮(zhèn)每天產生的垃圾要運往該地區(qū)的4個垃圾處理場處理，現(xiàn)考慮各城鎮(zhèn)到各處理場的道路對各城鎮(zhèn)垃圾外運的影響。假設各城鎮(zhèn)每日產生的垃圾量、各處理場的日處理能力及各條道路（可供運垃圾部分）的容量（其中容量為0表示無此直接道路）如右表所示，試用網絡流方法分析目前的道路狀況能否使所有垃圾都運到處理場得到處理，如果不能，應首先拓寬哪條道路。處理場城鎮(zhèn)1234垃圾量a302010050b00204070c5040205080處理量60409030運籌學圖與網絡分析分析：轉化為一個網絡圖，弧的容量為各路段能處理垃圾的數量。abc1234st80504020506040903020703050102040則問題為求最小截。運籌學圖與網絡分析b80(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)805040205060409020703050102040s（1）確定初始可行流30（2）標號法求最大流得最小截4c321at運籌學圖與網絡分析b80(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）反向追蹤，找可擴充鏈4c321at90(40)20(20)50(10)40(20)70(40),得一s-t的可擴充鏈:s-b-4-c-3-t，調整量運籌學圖與網絡分析b90(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）重復標號321ats4ca21a3（5）反向追蹤，找可擴充鏈（6）找到可擴充流S-b-4-c-3-t,調整量為10運籌學圖與網絡分析b80(80)50(40)40(20)20(20)60(60)40(40)30(30)20(20)30(20)50(50)10(10)20(20)321ats4ca21a3（6）找到可擴充流S-b-4-c-3-t,調整量為1090(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）重復標號，直至終止321atc321atsb4答案：最小截為{sa、sc、b3、4t},垃圾最大處理量為180<50+70+80運籌學圖與網絡分析答案綜上，目前的道路狀況不能使所有垃圾都運到處理場得到處理。從圖上不難發(fā)現(xiàn)，理論上應當拓寬割集所在的道路。但由于sa,sc和4t都是添加的虛擬道路，所以只有拓寬割集中的b3道路的路寬，或者增大4號處理場處理垃圾的能力，才能解決問題。

運籌學圖與網絡分析練習：過紐約ALBANY的北-南高速公路，路況通過能力如下圖所示，圖中弧上數字單位：千輛/小時。求（1）該路網能承受的北-南向最大流量；（2）若要擴充通過能力，應在那一組路段上擴充，說明原因。2143562366241331進入Albany（北）離開Albany（南）運籌學圖與網絡分析(1)選取一個可行流123546（進入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，調整成新流，繼續(xù)標號,用標號法得可擴充鏈運籌學圖與網絡分析123546（進入Albany(北)離開Albany(南)2(2)4(2)3(1)1(1)6(5)3(3)2(2)3(3)6(3)1(0)標號終止，當前流為最大流，最大流量為8割集為：12,45，46，36應該在割集弧上擴大流量運籌學圖與網絡分析[練習1][0,v1][4,v1][3,v1][5,v2][6,v2][9,v7][7,v4/v6][8.5,v6][6,v2]v2v1v5v4v3v6v8v7v943232.533523421有9個城市v1、v2、…v9，其公路網如圖所示?；∨詳底质窃摱喂返拈L度，有一批物資要從v1運到v9，問走哪條路最近？運籌學圖與網絡分析習題課練習（最小支撐樹）已知有A、B、C、D、E、F六個城鎮(zhèn)間的道路網絡如圖，現(xiàn)要在六個城鎮(zhèn)間架設通訊網絡（均沿道路架設），每段道路上的架設費用如圖。求能保證各城鎮(zhèn)均能通話且總架設費用最少的架設方案。EACBFD51069353978284[練習2]運籌學圖與網絡分析第四節(jié)最小費用最大流問題

在實際的網絡系統(tǒng)中，當涉及到有關流的問題的時候，我們往往不僅僅考慮的是流量，還經常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網絡流，即要考慮網絡流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問題。

設一個網絡D=（V，A，C），對于每一個弧(vi,vj)∈A,給定一個單位流量的費用bij

0，網絡系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流f，并且流的總費用達到最小。運籌學圖與網絡分析而此時總費用b(f'

)比b(f)增加了我們將叫做這條增廣鏈的費用。我們首先考察，在一個網絡D中，當沿可行流f的一條增廣鏈μ，以調整量θ=1改進f，得到的新可行流f'的流量，有v(f'

)=v(f)+1運籌學圖與網絡分析顯然，零流f={0}是流量為0的最小費用流。一般地，尋求最小費用流，總可以從零流f={0}開始。問題是：如果已知f是流量為v(f)的最小費用流，如何尋找關于f的最小費用增廣鏈？結論：若f是流量為v(f)的所有可行流中的費用最小，而是關于f的所有增廣鏈中的費用最小的增廣鏈，則f沿增廣鏈μ調整量為1得到的新可行流f'

，一定是流量為v(f'

)+1的所有可行流中的最小費用流。依次類推，當f'是最大流時，就是所要求的最小費用最大流。運籌學圖與網絡分析若u是從vs到vt關于f的增廣鏈，它的費用若果把u-中的邊(vi

,vj)反向，并且令它的權是-bij，而u+中的方向不變，并且的它的權是bij，這樣就把求從vs到vt關于f的最小費用增廣鏈就轉換成尋求從vs

到vt

的最短路。構造一個賦權有向圖M(f)，其頂點是原網絡D的頂點，他的邊根據f的情況確定：若原圖中（vi，vj