運籌學圖與網(wǎng)絡(luò)模型

關(guān)于運籌學圖與網(wǎng)絡(luò)模型第1頁，課件共56頁，創(chuàng)作于2023年2月圖論

GraphTheory哥尼斯堡七橋問題(K?nigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年發(fā)表第一篇圖論方面的論文，奠基了圖論中的一些基本定理很多問題都可以用點和線來表示，一般點表示實體，線表示實體間的關(guān)聯(lián)BACD第2頁，課件共56頁，創(chuàng)作于2023年2月§1

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

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

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

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

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

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

是eij的端點(endvertex)，而eij

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

；次數(shù)為奇數(shù)的點稱為奇點(odd),次數(shù)為偶數(shù)的點稱為偶點(even)；圖中都是偶點的圖稱為偶圖(evengraph)第5頁，課件共56頁，創(chuàng)作于2023年2月

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

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

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

{v1,v2,…,vn}構(gòu)成一條鏈(link)，又稱為行走(walk)；首尾相連的鏈稱為圈(loop)，或閉行走在無向圖中，節(jié)點不重復出現(xiàn)的鏈稱為路徑(path)；在有向圖中，節(jié)點不重復出現(xiàn)且鏈中所有弧的方向一致，則稱為有向路徑(directedpath)首尾相連的路徑稱為回路(circuit)；第6頁，課件共56頁，創(chuàng)作于2023年2月

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

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

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

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

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

個節(jié)點的樹T的邊恰好為

n1條，反之，任何有n

個節(jié)點，n1條邊的連通圖必是一棵樹

2.2圖的生成樹樹T是連通圖G的生成樹(spanningtree)，若T是G的子圖且包含圖G的所有的節(jié)點；包含圖G中部分指定節(jié)點的樹稱為steinertree第9頁，課件共56頁，創(chuàng)作于2023年2月

2.3

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

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

1.

在G中找到一個圈（v1,v7,v6,v1），并知在此圈上邊[v1,v6]的權(quán)數(shù)10為最大，在G中去掉邊[v1,v6]得圖G1。第13頁，課件共56頁，創(chuàng)作于2023年2月v1v2v3v4v6v5v7334327541G2

2.

在G1中找到一個圈（v3,v4,v5,v7,v3），并知在此圈上邊[v4,v5]的權(quán)數(shù)8為最大，在G1中去掉邊[v4,v5]得圖G2。8第14頁，課件共56頁，創(chuàng)作于2023年2月v1v2v3v4v6v5v733432741G33.

在G2中找到一個圈（v2,v3,v5,v7,v2），并知在此圈上邊[v5,v7]的權(quán)數(shù)5為最大，在G2中去掉邊[v5,v7]得圖G3。5第15頁，課件共56頁，創(chuàng)作于2023年2月v1v2v3v4v6v5v733432741G44.

在G3中找到一個圈（v3,v5,v6,v7,v3），并知在此圈上邊[v5,v6]和[v3,v7]的權(quán)數(shù)4為最大，在G3中去掉邊[v5,v6]得圖G4。第16頁，課件共56頁，創(chuàng)作于2023年2月v1v2v3v4v6v5v73343271G55.

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

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