會計學1運籌學運籌學 圖與網(wǎng)絡分析圖與網(wǎng)絡分析2022-6-15 第1頁/共33頁2022-6-15第2頁/共33頁2022-6-15續(xù)為止。續(xù)為止。第3頁/共33頁2022-6-15 T第4頁/共33頁2022-6-15 例例 用破圈法求下圖的最小樹用破圈法求下圖的最小樹12222312222333445第5頁/共33頁2022-6-15 第6頁/共33頁2022-6-15第7頁/共33頁2022-6-15 第8頁/共33頁2022-6-15第9頁/共33頁2022-6-15V1V4V2V3V6V9V8V7V542466234442第10頁/共33頁2022-6-15第11頁/共33頁2022-6-15第12頁/共33頁2022-6-15 例：例： 求下圖所示有向圖中從求下圖所示有向圖中從v1到各點的到各點的最短路。最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第13頁/共33頁2022-6-15 wij d(t)(v1,vj) v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v80 25-30 -2406400-3 0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910說明：表中空格處為說明：表中空格處為+ 。第14頁/共33頁2022-6-15例例 設備更新問題設備更新問題制訂一設備更新問題，使得總費用最小制訂一設備更新問題，使得總費用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購買費購買費 13 14 16 19 24 使用年數(shù)使用年數(shù) 0-1 1-2 2-3 3-4 4-5 維修費維修費 8 10 13 18 27 解解設以設以vi(i=1,2,3,4,5)表示表示“第第i年初購進一臺年初購進一臺新設備新設備”這種狀態(tài)，以這種狀態(tài)，以v6表示表示“第第5年末年末”這種狀態(tài)這種狀態(tài)；以??；以弧(vi, vj)表示表示“第第i年初購置的一臺設備一直使用年初購置的一臺設備一直使用到第到第j年初年初”這一方案，以這一方案，以wij表示這一方案所需購置表示這一方案所需購置費和維護費之和。費和維護費之和。第15頁/共33頁2022-6-15這樣，可建立本例的網(wǎng)絡模型。于是，該問題就這樣，可建立本例的網(wǎng)絡模型。于是，該問題就可歸結為從圖中找出一條從可歸結為從圖中找出一條從v1到到v6的最短路問題的最短路問題。用用Dijkstra標號法，求得最短路為標號法，求得最短路為 v1v3v6 即第一年初購置的設備使用到第三年初予以更即第一年初購置的設備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總新，然后一直使用到第五年末。這樣五年的總費用最少，為費用最少，為78。第16頁/共33頁2022-6-15v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31, V1)(44,V1)(62,V1)(78,V3)第17頁/共33頁2022-6-15第三節(jié)第三節(jié) 最大流問題最大流問題 如下是一運輸網(wǎng)絡，弧上的數(shù)字表示每條弧如下是一運輸網(wǎng)絡，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡的最大流量是多少？上的容量，問：該網(wǎng)絡的最大流量是多少？vsv2v1v3v4vt432312234第18頁/共33頁2022-6-15第19頁/共33頁2022-6-152、可行流與最大流、可行流與最大流定義定義2 滿足下列條件的流稱為滿足下列條件的流稱為可行流可行流：1) 0 fij cij2)平衡條件：平衡條件：中間點中間點 fij = fji(vi,vj) A(vj,vi) A發(fā)點發(fā)點vs fsj fjs=v(f)(vs,vj) A (vj,vs) A ftj fjt= v(f)(vt,vj) A收點收點vt，(vj,vt) A式中式中v(f)稱為這個可行流的流量，即發(fā)點的凈輸出量稱為這個可行流的流量，即發(fā)點的凈輸出量（或收點的凈輸入量）。（或收點的凈輸入量）。第20頁/共33頁2022-6-15最大流問題：求一流最大流問題：求一流fij滿足滿足0 fij cij v(f) i=s fij fji= 0 i s，t v(f) i=t且使且使v(f)達到最大。達到最大。第21頁/共33頁2022-6-153、增廣鏈、增廣鏈 給定可行流給定可行流f=fij，使，使fij=cij的弧稱為的弧稱為飽和弧飽和弧，使使fij0的弧稱為的弧稱為非零流弧非零流弧。 若若 是網(wǎng)絡中連接發(fā)點是網(wǎng)絡中連接發(fā)點vs和收點和收點vt的一條鏈，定的一條鏈，定義鏈的方向是從義鏈的方向是從vs到到vt，則鏈上的弧被分成兩類：，則鏈上的弧被分成兩類：前向?。夯〉姆较蚺c鏈的方向一致前向?。夯〉姆较蚺c鏈的方向一致 全體全體 +后向弧：弧的方向與鏈的方向相反后向?。夯〉姆较蚺c鏈的方向相反 全體全體 定義定義3 設設f是一可行流，是一可行流， 是從是從vs到到vt的一條鏈，的一條鏈，若若 滿足下列條件，則稱之為（關于流滿足下列條件，則稱之為（關于流f的）一條的）一條增廣鏈：增廣鏈： 在弧在弧(vi,vj)+上，上，0 fijcij 在弧在弧(vi,vj)上，上，0fij cij第22頁/共33頁2022-6-15 4、截集與截量、截集與截量 定義定義4 給定網(wǎng)絡給定網(wǎng)絡D=(V,A,C)，若點集，若點集V被被剖分為兩個非空集合剖分為兩個非空集合V1和和V1，使，使vs V1，vt V1，則把弧集，則把弧集(V1,V1)稱為是（分離稱為是（分離vs和和vt的的）截集。）截集。截集是從截集是從vs到到vt的必經(jīng)之路。的必經(jīng)之路。 定義定義5 給定一截集給定一截集(V1,V1)，把截集，把截集(V1,V1)中所有弧的容量之和稱為這個截集的容量中所有弧的容量之和稱為這個截集的容量(截量截量),記為記為C(V1,V1)。v(f) C(V1,V1)第23頁/共33頁2022-6-15 若對于一可行流若對于一可行流f*，網(wǎng)絡中有一截集，網(wǎng)絡中有一截集(V1*,V1*)，使得，使得v(f*)= C(V1*,V1*)，則，則f必是最大必是最大流，而流，而(V1*,V1*)，必定是容量最小的截集，即，必定是容量最小的截集，即最小截集。最小截集。 定理定理1 可行流可行流f*是最大流的充要條件是不存是最大流的充要條件是不存在關于在關于f*的最大流。的最大流。 若若f*是最大流，則網(wǎng)絡中必存在一個截集是最大流，則網(wǎng)絡中必存在一個截集(V1*,V1*)，使得，使得 v(f*)= C(V1*,V1*) 定理定理2 任一網(wǎng)絡任一網(wǎng)絡D中，中，從從vs到到vt的最大流的的最大流的流量等于分離流量等于分離vs，vt的最小截集的截量。的最小截集的截量。第24頁/共33頁2022-6-15步驟步驟：2、 標號過程標號過程1、選取一個可行流（可選擇零流?。⑦x取一個可行流（可選擇零流?。?從從Vs出發(fā)，出發(fā)，在在前向前向弧弧上上(vi,vj) ，若，若fij0，則給，則給vj標號標號( Vi,l(vj)，其中其中l(wèi)(vj)=minl(vi)，fji。二、尋找最大流的標號法二、尋找最大流的標號法(Ford Fulkerson) 思想：從一可行流出發(fā)，檢查關于此流是否思想：從一可行流出發(fā)，檢查關于此流是否存在增廣鏈。若存在增廣鏈，則增大流存在增廣鏈。若存在增廣鏈，則增大流量，使此量，使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。第25頁/共33頁2022-6-15 3、若標號延續(xù)到、若標號延續(xù)到vt，表明得到一條從，表明得到一條從vs到到vt的增的增廣鏈廣鏈 ，轉入調(diào)整階段，轉入調(diào)整階段4，否則當前流即為最大流。，否則當前流即為最大流。4、調(diào)整過程、調(diào)整過程令調(diào)整量為令調(diào)整量為 = l(vt)令令 fij+ (vi,vj)+ fij = fij (vi,vj) fij (vi,vj)去掉所有的標號，對新的可行流去掉所有的標號，對新的可行流f =fij ，重新進，重新進入標號過程。入標號過程。第26頁/共33頁2022-6-15可結合下圖理解其實際涵義。可結合下圖理解其實際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第27頁/共33頁2022-6-15vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例例 求下列網(wǎng)絡的最大流與最小截集。求下列網(wǎng)絡的最大流與最小截集。解解一、標號過程一、標號過程 （2）檢查）檢查vs,在弧在弧(vs,v1)上上,fs1=7,cs1=9,fs1cs1,則則v1的標號為的標號為(vs,l(v1)，其中，其中第28頁/共33頁2022-6-15l(v1)=minl(vs)，cs1fs1=min+ ，9 2=2（3）檢查）檢查v1,在弧在弧(v1,v4)上上,f14=7,c14=9,f140，則則v3的標號為的標號為(-v4, l(v3)，其中，其中l(wèi)(v3)=minl(v4)，f34=min2，1=1（5）檢查）檢查v3,在弧在弧(v3,vt)上上,f3t=3,c3t=6,f3tc3t,第29頁/共33頁2022-6-15則則vt的標號為的標號為(v3,l(vt)，其中，其中l(wèi)(vt)=minl(v3)，c3tf3t=min1，6-3=1這樣，我們得到了一增廣鏈這樣，我們得到了一增廣鏈 ,如圖所示。如圖所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0, )(vs,2)(v1,2)(-v4,1)(v3,1)其中其中 +=(vs,v1),(v1,v4),(v3,vt)， =(v3,v4)第30頁/共33頁2022-6-15二、調(diào)整過程二、調(diào)整過程取調(diào)整量為取調(diào)整量為 =1，在，在 上調(diào)整上調(diào)整f。在在 +上：上： fs1+ =7+1=8 f14+ =2+1=3 f4t+ =5+1=6在在 上：上： f43 =11=0其余弧上的流量不變，這樣得到一個新的流，如下圖所示。其余弧上的流量不變，這樣得到一個新的流，如下圖所示。s1vtv4v23(9,8)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)第31頁/共33頁2022-6-15 在上圖中重復上述標號過程，依次給在上圖中重復上述標號過程，依次給vs,v2,v1,v4標號標號后，由于標號無法繼續(xù)下去，算法結束。這時的流為最后，由于標號無法繼續(xù)下去，算法結束。這時的流為最大流，最大流的流量為大流，最大流的流量為vvv(4,4)v(f)=8+3=11 與此同時，可找到最小截集與此同時，可找到最小截集(V1,V1)，其中，其中V1為標號點為標號點集合，集合，V1為未標號點集合，弧集合為未標號點集合，弧集合(V1,V1) 即為最小截集。即為最小截集。此例中，此例中， V1=vs,v2,v1,v4, V1=v3,vt,(V1,V1)=(v1,v3)， (v4,vt)第32頁/共33頁