運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析

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