1、圖與網(wǎng)絡(luò)優(yōu)化,周榮喜 北京化工大學(xué)經(jīng)濟(jì)管理學(xué)院,公路系統(tǒng)中的車輛流,4 網(wǎng)絡(luò)最大流問題,控制系統(tǒng)中的信息流,供水系統(tǒng)中的水流,金融系統(tǒng)中的現(xiàn)金流,問題背景,網(wǎng)絡(luò)最大流問題問題的提出,網(wǎng)絡(luò)中存在流量限制時(shí)，求解一條線路使得從起點(diǎn)與終點(diǎn)之間可通過的流量最大。,例：上圖為V1到V6的一交通網(wǎng)，權(quán)表示相應(yīng)運(yùn)輸線的最大通過能力，制定一方案，使從V1運(yùn)到V6的產(chǎn)品數(shù)量最多。,設(shè)有網(wǎng)絡(luò)D=(V, A, C)，其中C=cij， cij為弧(vi,vj)上的容量，現(xiàn)在D上要通過一個(gè)流f=fij， fij為弧(vi,vj)上的流量。 問題：如何安排fij，可使網(wǎng)絡(luò)D上的總流量最大？,一、一般提法：,二、最大流問題

2、的模型,max v=v（f）,容量約束,平衡約束,注：滿足兩約束條件的流f稱為可行流，v(f)稱為該可行流的流量,試分析下圖是否是可行流?,三、基本概念與定理,2. 增廣鏈,f為一可行流，u為vs至vt的鏈，令u+=正向弧， u-=反向弧。若u+中弧皆非飽和，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。,2. 增廣鏈,f為一可行流，u為vs至vt的鏈，令u+=正向弧， u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。,2. 增廣鏈,f為一可行流，u為vs至vt的鏈，令u+=正向弧， u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。,

3、2. 增廣鏈,f為一可行流，u為vs至vt的鏈，令u+=正向弧， u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。,3. 截集與截量,把V分成兩部分：VA和VB(VA VB= , VA VB= V)且vs VA、 vt VB，則弧集(VA,VB)稱為D的截集。 截集上的容量和稱為截量，記為C(VA,VB) 。,(vs,v2), (v1,v2), (v1,v3), (v1,v4)； 截量為： C(VA,VB) =8+4+5+3=20,例 若VA=vs,v1，則,截集為：,4. 流量與截量的關(guān)系,任一可行流的流量都不會(huì)超過任一截集的截量 因v(f)=f (VA,VB)

4、 - f (VB,VA) f (VA,VB) C (VA,VB) ）,最大流最小截定理：網(wǎng)絡(luò)的最大流量等于最小截量。,例. 如圖所示的網(wǎng)絡(luò)中，弧旁數(shù)字為(cij ,fij),v1,（1）確定所有的截集； （2）求最小截集的容量； （3）證明圖中的流為最大流；,v1,（1）所有的截集：, VA=vs，,截集為(vs,v1), (vs,v2)，截量為：6,v1,（1）所有的截集：, VA=vs，截集為(vs,v1), (vs,v2)，截量為：6 VA=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7,v1,（1）所有的截集：, VA=vs，截集為(vs,v1), (vs,v2)，截

5、量為：6 VA=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7 VA=vs ,v2，截集為，截量為：7,v1,（1）所有的截集：, VA=vs，截集為(vs,v1), (vs,v2)，截量為：6 VA=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7 VA=vs ,v2，截集為，截量為：7 Va=vs ,v3，截集為，截量為：12,v1,（1）所有的截集：,VA=vs，截集為(vs,v1), (vs,v2)，截量為：6 VA=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7 VA=vs ,v2，截集為，截量為：7 VA=vs ,v3，截集為，截

6、量為：12 VA=vs ,v1,v2，截集為，截量為：5,v1,（1）所有的截集：,VA=vs，截集為(vs,v1), (vs,v2)，截量為：6 VA=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7 VA=vs ,v2，截集為，截量為：7 VA=vs ,v3，截集為，截量為：12 VA=vs ,v1,v2，截集為，截量為：5,（2）最小截量min C (VA,VB)= 5 （3）v(f*)=5= min C (VA,VB) f*是最大流。,理論依據(jù)：定理8,網(wǎng)絡(luò)中的所有點(diǎn)：標(biāo)號(hào)點(diǎn)和未標(biāo)號(hào)點(diǎn)。 標(biāo)號(hào)點(diǎn)：已檢查和未檢查點(diǎn)。 標(biāo)號(hào)點(diǎn)包括兩部分：第一個(gè)標(biāo)號(hào)表明它的標(biāo)號(hào)的來源，以便找

7、出增廣鏈；第二個(gè)標(biāo)號(hào)是為確定增廣鏈的調(diào)整量用。,求最大流方法 Ford and Fulkerson標(biāo)號(hào)法,標(biāo)號(hào)法的思路,所有點(diǎn) 未標(biāo)號(hào) 未檢查,所有 標(biāo)號(hào)點(diǎn) 檢查,注: 給發(fā)點(diǎn)Vs標(biāo)上（0，），則Vs成為標(biāo)號(hào)未檢查,Vi 標(biāo)號(hào) 未檢查,Vi 標(biāo)號(hào) 檢查 Vj 標(biāo)號(hào) 未檢查,考查 （Vi, Vj),網(wǎng)絡(luò)最大流問題標(biāo)號(hào)法,1.標(biāo)號(hào)過程 給vs標(biāo)上(0，+)，這時(shí)vs是標(biāo)號(hào)而未檢查點(diǎn)，其余為未標(biāo)號(hào)點(diǎn)。 若在弧(vi，vj)上，fij0，則給vj標(biāo)(-vi，l(vj)， 其中 vi成為標(biāo)號(hào)而已檢查過的點(diǎn)，重復(fù)上述步驟， 一旦vt被標(biāo)號(hào)，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入 2.調(diào)整過程 如果所有標(biāo)號(hào)

8、已檢查過，而標(biāo)號(hào)不能進(jìn)行下去，則算法結(jié)束，這時(shí)可行流為最大流。,網(wǎng)絡(luò)最大流問題標(biāo)號(hào)法,1.標(biāo)號(hào)過程 2.調(diào)整過程,利用反向追蹤法找出增廣鏈。調(diào)整量為 = l(vt),去掉所有的標(biāo)號(hào)，對(duì)新的可行流f*重新進(jìn)行標(biāo)號(hào)過程。,步驟： (1)給vs標(biāo)號(hào)為0,+，,流出未飽和弧(vs , vj) ,給vj標(biāo)號(hào)vs ,j,其中j=csj- fsj,或流入非零弧 (vj , vs) ,給vj標(biāo)號(hào)-vs, j ,其中j=fsj,例. 圖中網(wǎng)絡(luò)弧旁數(shù)字為(cij ,fij)，用標(biāo)號(hào)法求最大流。,0,+,vs, 4,選與vs關(guān)聯(lián)的,考慮所有弧(vi , vj)或(vj , vi) ,其中vi VA, vj VB，若

9、該弧為,流出未飽弧,則給vj標(biāo)號(hào)vi , j,其中j=mini, cij- fij,流入非零弧,則給vj標(biāo)號(hào)-vi , j ,其中j= mini, fij,(3),-v1 , 1,(4),重復(fù)（2）,（3），依次進(jìn)行的結(jié)局可能為,vt已標(biāo)號(hào)，得到一條增廣鏈u(反向追蹤)，轉(zhuǎn)（5）；,vt未標(biāo)號(hào),且無法再標(biāo)號(hào),此時(shí)的流為最大流,此時(shí)的截集為最小截。,（3,0）,v2 , 1,V3,v4, 1,v2,Vs,v1,v4,v3,Vt,（3,3）,（5,2）,（1,0）,（2,2）,（1,1）,（5,4）,（2,1）,（4,4）,（3,0）,調(diào)整,0 ,+,vs, 3,此時(shí)標(biāo)號(hào)無法進(jìn)行，當(dāng)前流為最大流，

10、最大流量為5；最小截為(vs,v2), (v1,v3)，截量為：5,有三個(gè)發(fā)電站v1,v2,v3，發(fā)電能力分別為15、10和40兆瓦，經(jīng)輸電網(wǎng)可把電力送到8號(hào)地區(qū)，電網(wǎng)能力如圖所示。求三個(gè)發(fā)電站輸?shù)皆摰貐^(qū)的最大電力。,v0,10,10,15,15,15,0,10,10,10,10,15,25,課堂練習(xí),例1、圖中A、B、C、D、E、F分別表示陸地和島嶼，表示橋梁及其編號(hào)。河兩岸分別互為敵對(duì)的雙方部隊(duì)占領(lǐng)，問至少應(yīng)切斷幾座橋梁（具體指出編號(hào)）才能達(dá)到阻止對(duì)方部隊(duì)過河的目的。試用圖論方法進(jìn)行分析。,實(shí)際應(yīng)用,分析：轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖，弧的容量為兩點(diǎn)間的橋梁數(shù)。,則問題為求最小截。,分析：轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖，弧的容量為兩點(diǎn)間的橋梁數(shù)。,則問題為求最小截。,答案：最小截為AE、CD、CF,例2、有一批人從我國(guó)A城赴俄羅斯B城，可能的旅行路線如圖：,邊防隊(duì)擬建立足夠數(shù)量檢查站以便使每輛汽車至少必經(jīng)過一個(gè)檢查站，建立檢