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

關(guān)于運(yùn)籌學(xué)圖與網(wǎng)絡(luò)模型圖論

GraphTheory哥尼斯堡七橋問題(K?nigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年發(fā)表第一篇圖論方面的論文，奠基了圖論中的一些基本定理很多問題都可以用點(diǎn)和線來表示，一般點(diǎn)表示實(shí)體，線表示實(shí)體間的關(guān)聯(lián)BACD第2頁,共56頁，2024年2月25日，星期天§1

圖與網(wǎng)絡(luò)的基本概念

1.1圖與網(wǎng)絡(luò)節(jié)點(diǎn)(Vertex)物理實(shí)體、事物、概念一般用vi

表示邊(Edge)節(jié)點(diǎn)間的連線，表示有關(guān)系一般用eij

表示圖(Graph)節(jié)點(diǎn)和邊的集合，一般用G(V,E)表示點(diǎn)集V={v1,v2,…,vn}邊集E={eij}網(wǎng)絡(luò)(Network)邊上具有表示連接強(qiáng)度的權(quán)值，如wij又稱加權(quán)圖(Weightedgraph)第3頁,共56頁，2024年2月25日，星期天1.2無向圖與有向圖邊都沒有方向的圖稱為無向圖，如圖1在無向圖中eij=eji，或(vi,vj)=(vj,vi)當(dāng)邊都有方向時(shí)，稱為有向圖，用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij表示，i,j的順序是不能顛倒的，圖中弧的方向用箭頭標(biāo)識(shí)圖中既有邊又有弧，稱為混合圖第4頁,共56頁，2024年2月25日，星期天

1.3端點(diǎn)，關(guān)聯(lián)邊，相鄰，次圖中可以只有點(diǎn)，而沒有邊；而有邊必有點(diǎn)若節(jié)點(diǎn)vi,vj

之間有一條邊eij，則稱vi,vj

是eij的端點(diǎn)(endvertex)，而eij

是節(jié)點(diǎn)vi,vj的關(guān)聯(lián)邊(incid%ntedge)同一條邊的兩個(gè)端點(diǎn)稱為相鄰(adjacent)節(jié)點(diǎn)，具有共同端點(diǎn)的邊稱為相鄰邊一條邊的兩個(gè)端點(diǎn)相同，稱為自環(huán)(self-loop)；具有兩個(gè)共同端點(diǎn)的兩條邊稱為平行邊(paralleledges)既沒有自環(huán)也沒有平行邊的圖稱為簡(jiǎn)單圖(simplegraph)在無向圖中，與節(jié)點(diǎn)相關(guān)聯(lián)邊的數(shù)目，稱為該節(jié)點(diǎn)的“次”(degree)，記為d

；次數(shù)為奇數(shù)的點(diǎn)稱為奇點(diǎn)(odd),次數(shù)為偶數(shù)的點(diǎn)稱為偶點(diǎn)(even)；圖中都是偶點(diǎn)的圖稱為偶圖(evengraph)第5頁,共56頁，2024年2月25日，星期天

1.3端點(diǎn)，關(guān)聯(lián)邊，相鄰，次有向圖中，由節(jié)點(diǎn)指向外的弧的數(shù)目稱為正次數(shù)，記為d+，指向該節(jié)點(diǎn)的弧的數(shù)目稱為負(fù)次數(shù)，記為d–次數(shù)為0的點(diǎn)稱為孤立點(diǎn)(isolatedvertex)

，次數(shù)為1的點(diǎn)稱為懸掛點(diǎn)(pendantvertex)定理1：圖中奇點(diǎn)的個(gè)數(shù)總是偶數(shù)個(gè)

1.4鏈，圈，路徑，回路，歐拉回路相鄰節(jié)點(diǎn)的序列

{v1

,v2

,…,vn

}構(gòu)成一條鏈(link)，又稱為行走(walk)；首尾相連的鏈稱為圈(loop)，或閉行走在無向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)的鏈稱為路徑(path)；在有向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)且鏈中所有弧的方向一致，則稱為有向路徑(directedpath)首尾相連的路徑稱為回路(circuit)；第6頁,共56頁，2024年2月25日，星期天

1.4鏈，圈，路徑，回路，連通圖走過圖中所有邊且每條邊僅走一次的閉行走稱為歐拉回路定理2：偶圖一定存在歐拉回路(一筆畫定理)1.4連通圖，子圖，成分設(shè)有兩個(gè)圖G1(V1,E1),G2(V2,E2),若V2

V1,E2

E1，則G2是G1的子圖無向圖中，若任意兩點(diǎn)間至少存在一條路徑，則稱為連通圖(connectedgraph)，否則為非連通圖(discon-nectedgraph)；非連通圖中的每個(gè)連通子圖稱為成分

(component)鏈，圈，路徑(簡(jiǎn)稱路)，回路都是原圖的子圖平面圖(planargraph)，若在平面上可以畫出該圖而沒有任何邊相交第7頁,共56頁，2024年2月25日，星期天§2樹圖與最小生成樹一般研究無向圖樹圖：倒置的樹，根(root)在上，樹葉(leaf)在下多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是典型的樹圖第8頁,共56頁，2024年2月25日，星期天

2.1樹的定義及其性質(zhì)任兩點(diǎn)之間有且只有一條路徑的圖稱為樹(tree)，記為T

樹的性質(zhì)：最少邊的連通子圖，樹中必不存在回路任何樹必存在次數(shù)為1的點(diǎn)具有n

個(gè)節(jié)點(diǎn)的樹T的邊恰好為

n

1條，反之，任何有n

個(gè)節(jié)點(diǎn)，n

1條邊的連通圖必是一棵樹

2.2圖的生成樹樹T是連通圖G的生成樹(spanningtree)，若T是G的子圖且包含圖G的所有的節(jié)點(diǎn)；包含圖G中部分指定節(jié)點(diǎn)的樹稱為steinertree第9頁,共56頁，2024年2月25日，星期天

2.3

最小生成樹有n個(gè)鄉(xiāng)村，各村間道路的長(zhǎng)度是已知的，如何鋪設(shè)光纜線路使n個(gè)鄉(xiāng)村連通且總長(zhǎng)度最短顯然，這要求在已知邊長(zhǎng)度的網(wǎng)路圖中找最小生成樹

第10頁,共56頁，2024年2月25日，星期天2.4求解最小生成樹的破圈算法所謂的最小生成樹問題就是在一個(gè)賦權(quán)的連通的無向圖G中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。算法的具體步驟如下：在給定的賦權(quán)的連通圖上任找一個(gè)圈；在所找的圈中去掉一條權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條。如果所余下的圖中已不含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成數(shù)，否則返回第1步。第11頁,共56頁，2024年2月25日，星期天應(yīng)用舉例：某大學(xué)準(zhǔn)備對(duì)其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能連通的路徑如圖G所示，圖中v1,…,v7表示7個(gè)學(xué)院辦公室，圖中的邊為可能聯(lián)網(wǎng)的路徑，邊上所賦的權(quán)數(shù)為這條路線的長(zhǎng)度，單位為百米。請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能連通7個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度最短。v1v2v3v4v6v5v7103343278541G第12頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v7103343278541G1

1.

在G中找到一個(gè)圈（v1,v7,v6,v1），并知在此圈上邊[v1,v6]的權(quán)數(shù)10為最大，在G中去掉邊[v1,v6]得圖G1。第13頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v7334327541G2

2.

在G1中找到一個(gè)圈（v3,v4,v5,v7,v3），并知在此圈上邊[v4,v5]的權(quán)數(shù)8為最大，在G1中去掉邊[v4,v5]得圖G2。8第14頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v733432741G33.

在G2中找到一個(gè)圈（v2,v3,v5,v7,v2），并知在此圈上邊[v5,v7]的權(quán)數(shù)5為最大，在G2中去掉邊[v5,v7]得圖G3。5第15頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v733432741G44.

在G3中找到一個(gè)圈（v3,v5,v6,v7,v3），并知在此圈上邊[v5,v6]和[v3,v7]的權(quán)數(shù)4為最大，在G3中去掉邊[v5,v6]得圖G4。第16頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v73343271G55.

在G4中找到一個(gè)圈（v2,v3,v7,v2），并知在此圈上邊[v3,v7]的權(quán)數(shù)5為最大，在G2中去掉邊[v5,v7]得圖G3。第17頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v7333271G56.在G5中已找不到任何一個(gè)圈了，可知G5即為圖G的最小生成樹。這個(gè)最小生成樹的所有邊的總權(quán)數(shù)為3+3+3+1+2+7=19。第18頁,共56頁，2024年2月25日，星期天§3最短路問題最短路問題是對(duì)一個(gè)賦權(quán)的有向圖G（權(quán)數(shù)可能是路程的長(zhǎng)度、花費(fèi)的成本等等）中的指定的兩個(gè)點(diǎn)Vs和Vt找到一條從Vs到Vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱為從Vs到Vt的最短路，這條路上所有弧的權(quán)數(shù)的總和被稱之為從Vs到Vt的距離。第19頁,共56頁，2024年2月25日，星期天3.1求解最短路的Dijkstra算法（Dijkstraalgorithm,1959）

Dijkstra算法也稱為雙標(biāo)號(hào)算法。所謂雙標(biāo)號(hào)，也就是對(duì)圖中的點(diǎn)vj賦予兩個(gè)標(biāo)號(hào)(lj,kj)，第一個(gè)標(biāo)號(hào)lj表示從起點(diǎn)vs到vj的最短路的長(zhǎng)度，第二個(gè)標(biāo)號(hào)kj表示在vs到vj的最短路上vj前面一個(gè)鄰點(diǎn)的下標(biāo)。給起點(diǎn)v1以標(biāo)號(hào)(0,s)表示從v1到v1的距離為0，v1為起點(diǎn)。找出已標(biāo)號(hào)的點(diǎn)的集合I，沒標(biāo)號(hào)的點(diǎn)的集合J以及弧的集合{(vi,vj)|vi∈I,vj∈J}，這里這個(gè)弧的集合是指所有從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的弧的集合。如果上述弧的集合是空集，則計(jì)算結(jié)束。如果vt已標(biāo)號(hào)(lt,kt)，則vs到vt的距離即為lt，而從vs到vt的最短路徑，則可以從kt反向追蹤到起點(diǎn)vs而得到。如果vt未標(biāo)號(hào)，則可以斷言不存在從vs到vt的有向路。否則轉(zhuǎn)下一步。對(duì)上述弧的集合中的每一條弧，計(jì)算sij=li+cij在所有的sij中，找到其值為最小的弧，不妨設(shè)此弧為(vc,vd)，則給此弧的終點(diǎn)以雙標(biāo)號(hào)(scd,c),返回第2步。第20頁,共56頁，2024年2月25日，星期天例1.求下圖中v1到v6的最短路。v1v4v3v2v5v62531255173第21頁,共56頁，2024年2月25日，星期天給起始點(diǎn)v1標(biāo)以(0,s)，表示從v1到v1的距離為0。已標(biāo)號(hào)點(diǎn)集I={v1}，未標(biāo)號(hào)點(diǎn)集J={v2,v3,v4,v5,v6}，弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4)}，并有s12=l1+c12=0+3=3,s13=l1+c13=0+2=2,s14=l1+c14=0+5,min(s12,s13,s14)=s13=2.我們給弧(v1,v3)的終點(diǎn)v3標(biāo)以(2,1).I={v1,v3},J={v2,v4,v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v4),(v3,v4)}且s34=l3+c34=2+1=3,min(s12,s14,s34)=s12=s34=3.給弧(v1,v2)的終點(diǎn)標(biāo)以(3,1),弧(v3,v4)的終點(diǎn)標(biāo)以(3,3).I={v1,v2,v3,v4},J={v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v2,v6),(v4,v6)},并有s26=l2+c26=3+7=10,s46=l4+c46=3+5=8,min(s26,s46)=s46=8.I={v1,v2,v3,v4,v6},J={v5},弧集為?，計(jì)算結(jié)束。v5沒有標(biāo)號(hào)表明從v1到v5沒有有向路。最短路徑為v1?v3?v4?v6.第22頁,共56頁，2024年2月25日，星期天例1的各點(diǎn)的標(biāo)號(hào)如下(v1到v5沒有有向路）v1v4v3v2v5v62531255173(0,s)(3,3)(8,4)(3,1)(2,1)第23頁,共56頁，2024年2月25日，星期天3.2最短路問題的應(yīng)用例2.電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給了甲、乙兩地間的交通圖，圖中的點(diǎn)v1,v2,...,v7表示7個(gè)地點(diǎn)，其中v1表示甲地，v7表示乙地，點(diǎn)之間的聯(lián)線（邊）表示兩地之間的公路，邊所賦的權(quán)數(shù)表示兩地間的公路長(zhǎng)度。v1甲地v7乙地v3v4v6v2v51510173465642第24頁,共56頁，2024年2月25日，星期天起始點(diǎn)v1標(biāo)號(hào)為(0,s).I={v1},J={v2,v3,v4,v5,v6,v7},邊集{[vi,vj]|vi,vj中一個(gè)∈I,另一個(gè)∈J}={[v1,v2],[v1,v3]}，且s12=l1+c12=0+15=15，s13=l1+c13=0+10=10，min(s12,s13)=s13=10，邊[v1,v3]中未標(biāo)號(hào)點(diǎn)v3標(biāo)以(10,1).I={v1,v3},J={v2,v4,v5,v6,v7},邊集{[vi,vj]}={[v1,v2],[v3,v2],[v3,v5]},且s32=l3+c32=10+3=13，s35=l3+c35=10+4=14，min(s12,s32,s35)=s32=13.邊[v3,v2]中未標(biāo)號(hào)的點(diǎn)v2標(biāo)以(13,3).I={v1,v3,v2},J={v4,v5,v6,v7},邊集{[vi,vj]}={[v3,v5],[v2,v4],[v2,v7]},且s24=l2+c24=13+6=19,s27=l2+c27=13+17=30,min(s35,s24,s27)=s35=14.邊[v3,v5]中未標(biāo)號(hào)的點(diǎn)v5標(biāo)以(14,3).I={v1,v2,v3,v5},J={v4,v6,v7},邊集{[vi,vj]}={[v2,v4],[v5,v4],[v2,v7],[v5,v6]},并有s54=l5+c54=14+4=18,s56=l5+c56=14+2=16,min(s24,s54,s27,s56)=s56=16.邊[v5,v6]中未標(biāo)號(hào)的點(diǎn)v6標(biāo)以(16,5).第25頁,共56頁，2024年2月25日，星期天I={v1,v2,v3,v5,v6},J={v4,v7}.邊集{[vi,vj]}={[v2,v4],[v2,v7],[v5,v4],[v6,v7]},且s67=l6+c67=16+6=22,min(s24,s27,s54,s67)=s54=18.邊[v5,v4]中未標(biāo)號(hào)的點(diǎn)v4標(biāo)以(18,5).I={v1,v2,v3,v4,v5,v6},J={v7}.邊集{[vi,vj]}={[v2,v7],[v4,v7],[v6,v7]},且s47=l4+c47=18+8=23,min(s27,s47,s67)=s67=22.邊[v6,v7]中未標(biāo)號(hào)的點(diǎn)v7標(biāo)以(22,6).此時(shí)I={v1,v2,v3,v4,v5,v6,v7},J=?.邊集合{[vi,vj]}為空集，計(jì)算結(jié)束。從v1到v7的最短距離為22,其最短路徑為v1?v3?v5?v6?v7.第26頁,共56頁，2024年2月25日，星期天例2的各點(diǎn)標(biāo)號(hào)如下：v1甲地v7乙地v3v4v6v2v51510173465642(0,s)(18,5)(10,1)(16,5)(14,3)(13,3)(22,6)第27頁,共56頁，2024年2月25日，星期天例3.設(shè)備更新問題。某公司試用一臺(tái)設(shè)備，在每年年初，公司就要決定是購買新設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了?，F(xiàn)在需要我們制定一個(gè)五年之內(nèi)的更新設(shè)備計(jì)劃，使得五年內(nèi)購置費(fèi)和維修總的支付費(fèi)用最小。這種設(shè)備每年年初的價(jià)格以及使用不同時(shí)間的設(shè)備所需要的維修費(fèi)如下表所示。年份12345年初價(jià)格1111121213使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用5681118第28頁,共56頁，2024年2月25日，星期天將該問題轉(zhuǎn)化成求最短路問題，vi表示“第i年年初購進(jìn)一臺(tái)新設(shè)備”，對(duì)于弧(vi,vj)，它的權(quán)數(shù)定義為從第i年年初購進(jìn)設(shè)備使用到第j-1年年底所花費(fèi)的購置費(fèi)及維修費(fèi)的總和，計(jì)算結(jié)果如下：ji1234561—16223041592——162230413———1723314————17235—————186——————第29頁,共56頁，2024年2月25日，星期天v1v2v3v4v5v6161817171623312322304159413022第30頁,共56頁，2024年2月25日，星期天起始點(diǎn)v1標(biāo)以(0,s).I={v1},J={v2,v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v1,v6)}并有s12=l1+c12=0+16=16,s13=l1+c13=0+22=22,s14=l1+c14=0+30=30,s15=l1+c15=0+41=41,s16=l1+c16=0+59=59,min(s12,s13,s14,s15,s16)=s12=16.給弧(v1,v2)的終點(diǎn)v2標(biāo)以(16,1).I={v1,v2},J={v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v3),(v1,v4),(v1,v5),(v1,v6),(v2,v3),(v2,v4),(v2,v5),(v2,v6)}并有s23=l2+c23=16+16=32,s24=l2+c24=16+22=38,s25=l2+c25=16+30=46,s26=l2+c26=16+41=57,min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22.給弧(v1,v3)的終點(diǎn)v3標(biāo)以(22,1).第31頁,共56頁，2024年2月25日，星期天I={v1,v2,v3},J={v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v4),(v1,v5),(v1,v6),(v2,v4),(v2,v5),(v2,v6),(v3,v4),(v3,v5),(v3,v6)}并有s34=l3+c34=22+17=39,s35=l3+c35=22+23=45,s36=l3+c36=22+31=53,min(s14,s15,s16,s24,s25,s26,s34,s35,s36)=s14=30.給弧(v1,v4)的終點(diǎn)v4標(biāo)以(30,1).I={v1,v2,v3,v4},J={v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v5),(v1,v6),(v2,v5),(v2,v6),(v3,v5),(v3,v6),(v4,v5),(v4,v6)}并有s45=l4+c45=30+17=47,s46=l4+c46=30+23=53,min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41.給弧(v1,v5)的終點(diǎn)v5標(biāo)以(41,1).I={v1,v2,v3,v4,v5},J={v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v6),(v2,v6),(v3,v6),(v4,v6),(v5,v6)}并有s56=l5+c56=41+18=59,min(s16,s26,s36,s46,s56)=s36=s46=53.給弧(v3,v6)和(v4,v6)的終點(diǎn)v6標(biāo)以(53,3)和(53,4).第32頁,共56頁，2024年2月25日，星期天v1v2v3v4v5v6161817171623312322304159413022(0,s)(16,1)(30,1)(41,1)(53,4)(53,3)(22,1)第33頁,共56頁，2024年2月25日，星期天§4最大流問題最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。第34頁,共56頁，2024年2月25日，星期天4.1最大流的數(shù)學(xué)模型例：某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從開采地運(yùn)送到一些銷售點(diǎn)。由于管道的直徑的變化，他的各段管道(vi,vj)的流量cij也不一樣，如下圖所示。cij的單位為萬加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從開采地v1向銷地v7運(yùn)送石油，問每小時(shí)能運(yùn)送多少加侖石油？v1v6v3v4v5v2v761223236542第35頁,共56頁，2024年2月25日，星期天設(shè)弧(vi,vj)上的流量為fij，網(wǎng)絡(luò)上的總的流量為F，則上述問題的線性規(guī)劃模型為：目標(biāo)函數(shù)：maxF=f12+f14約束條件：f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fijcij,(i=1,2,...,6;j=2,...,7)fij0,(i=1,2,...,6;j=2,...,7)第36頁,共56頁，2024年2月25日，星期天4.2最大流問題網(wǎng)絡(luò)圖論的解法對(duì)一條弧(vi,vj)的容量用一對(duì)數(shù)(cij,0)標(biāo)在弧(vi,vj)上，cij表示從vi到vj容許通過的容量，0表示從vj到vi容許通過的容量。vivjvivjvivjcijvivj0cjicijcijcjicij第37頁,共56頁，2024年2月25日，星期天求最大流的基本算法找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于0。如果不存在這樣的路，則已求得最大流。找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。在這條路上，減少每一條弧的順流容量pf，同時(shí)增加這些弧的逆流容量pf，返回步驟①。注意：在步驟①中盡量選擇包含弧數(shù)最少的路。第38頁,共56頁，2024年2月25日，星期天引例的Ford-Fulkerson標(biāo)號(hào)算法：(貝爾曼-福特算法)第一次迭代：選擇路為：v1v4v7.弧(v4,v7)的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量如圖所示：v1v6v3v4v5v7612232365422000000000042020v2第39頁,共56頁，2024年2月25日，星期天第二次迭代：選擇路為：v1v2v5v7.弧(v2,v5)的順流容量為c25=3，決定了pf=3，改進(jìn)的網(wǎng)絡(luò)流量如圖所示：v1v6v3v4v5v7612323542200000000420233230350v2第40頁,共56頁，2024年2月25日，星期天第三次迭代：選擇路為：v1v4v6v7.弧(v4,v6)的順流容量為c46=1，決定了pf=1，改進(jìn)的網(wǎng)絡(luò)流量如圖所示：v1v6v3v4v5v7122342500000420233230363301310v2第41頁,共56頁，2024年2月25日，星期天第四次迭代：選擇路為：v1v4v3v6v7.弧(v3,v6)的順流容量為c36=2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量如圖所示：v1v6v3v4v5v702234261000033023323038151321020v2第42頁,共56頁，2024年2月25日，星期天第五次迭代：選擇路為：v1v2v3v5v7.弧(v2,v3)的順流容量為c23=2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量如圖所示：v1v6v3v4v5v7022110812032150233230310105022005v2第43頁,共56頁，2024年2月25日，星期天最大流如圖所示：v1v6v3v4v5v72101223252355v2第44頁,共56頁，2024年2月25日，星期天§5最小費(fèi)用最大流問題最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條弧(vi,vj),除了給出了容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流F,并使總運(yùn)送費(fèi)用最小。第45頁,共56頁，2024年2月25日，星期天5.1最小費(fèi)用最大流的數(shù)學(xué)模型例：在上例中，假設(shè)不同的單位流量的費(fèi)用為bij，對(duì)每段管道(vi,vj)用(cij,bij)表示流量和費(fèi)用，如圖所示。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從開采地v1向銷地v7運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最少？求出每小時(shí)的最大流量及相應(yīng)的最小費(fèi)用。v1v6v3v4v5v2v7(6,6)(6,3)(3,4)(2,3)(2,4)(1,3)(3,2)(2,8)(2,5)(4,4)(5,7)第46頁,共56頁，2024年2月25日，星期天設(shè)弧(vi,vj)上的流量為fij，網(wǎng)絡(luò)上的總的流量為F，則上述問題的線性規(guī)劃模型為：目標(biāo)函數(shù)：minz=fij

bij=6f12+3f14+4f25+5f23+2f43+4f35+7f57+3f36+3f46+8f47+4f67約束條件：f12+f14=F=10f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fijcij,(i=1,2,...,6;j=2,...,7)fij0,(i=1,2,...,6;j=2,...,7)第47頁,共56頁，2024年2月25日，星期天5.2最小費(fèi)用最大流問題網(wǎng)絡(luò)圖論的解法對(duì)一條弧(vi,vj)的容量用一對(duì)數(shù)(cij,0)標(biāo)在弧(vi,vj)上，cij表示從vi到vj容許通過的容量，0表示從vj到vi容許通過的容量。vivjvivjvivj(cij,bij)(cij,bij)(0,-bij)(0,-bji)(0,-bij)(cji,bji)(cij,bij)vjvi(cji,bji)(cij,bij)第48頁,共56頁，2024年2月25日，星期天求最小費(fèi)用最大流的基本算法找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于0。如果不存在這樣的路，則已求得最大流。找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。在這條路上，減少每一條弧的順流容量pf，同時(shí)增加這些弧的逆流容量pf，返回步驟①。注意：在步驟①中選擇一條從發(fā)點(diǎn)到收點(diǎn)的費(fèi)用的最短路。第49頁,共56頁，2024年2月25日，星期天第一次迭代：選擇最短路為：v1v4v6v7，此路的總單位費(fèi)用為3+3+4=10，弧(v4,v6)的順流容量為1，決定了pf=1，改進(jìn)的網(wǎng)絡(luò)流量如圖所示：v1v6v3v4v5v2v7(6,6)(5,3)(3,4)(2,3)(2,4)(0,3)(3,2)(2,8)(2,5)(3,4)(5,7)第一次迭代后總流量為1，總的費(fèi)用為10×1=10.(0,-3)(0,-4)(0,-5)(0,-2)(1,-3)(1,-3)(1,-4)(0,-7)(0,-4)(0,-6)(0,-8)1第50頁,共56頁，2024年2月25日，星期天第二次迭代：選擇最短路為：v1v4v7，此路的總單位費(fèi)用為3+8=11，弧(v4,v7)的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量如圖所示：