運(yùn)籌學(xué)-圖與網(wǎng)絡(luò)模型以及最小費(fèi)用最大流ppt課件

.,Chapter11圖與網(wǎng)絡(luò)分析(GraphTheoryandNetworkAnalysis),圖與網(wǎng)絡(luò)的基本概念與模型最短路問(wèn)題最小生成樹(shù)問(wèn)題最大流問(wèn)題最小費(fèi)用最大流問(wèn)題,本章主要內(nèi)容：,.,圖與網(wǎng)絡(luò)的基本概念與模型,長(zhǎng),江,漢,江,武昌,漢口,漢陽(yáng),您能從武漢理工大學(xué)出發(fā)走過(guò)每座橋且只走一次然后回到學(xué)校嗎?,.,近代圖論的歷史可追溯到18世紀(jì)的七橋問(wèn)題穿過(guò)Knigsberg城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。,圖與網(wǎng)絡(luò)的基本概念與模型,Knigsberg橋?qū)?yīng)的圖,.,圖與網(wǎng)絡(luò)的基本概念與模型,圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。,圖的定義(P230)若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖G可以定義為點(diǎn)和邊的集合，記作：,其中:V點(diǎn)集E邊集,圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。,.,圖與網(wǎng)絡(luò)的基本概念與模型,可見(jiàn)圖論中的圖與幾何圖、工程圖是不一樣的。,例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示。,.,6,1圖與網(wǎng)絡(luò)的基本概念,如果我們把上面例子中的“相互認(rèn)識(shí)”關(guān)系改為“認(rèn)識(shí)”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。圖11-3就是一個(gè)反映這七人“認(rèn)識(shí)”關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。,.,圖與網(wǎng)絡(luò)的基本概念與模型,定義:圖中的點(diǎn)用v表示，邊用e表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：e1=v1,v1;e2=v1,v2;,端點(diǎn),關(guān)聯(lián)邊,相鄰,若有邊e可表示為e=vi,vj，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。,.,圖與網(wǎng)絡(luò)的基本概念與模型,環(huán),多重邊,簡(jiǎn)單圖,如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖。,.,圖與網(wǎng)絡(luò)的基本概念與模型,鏈，圈，連通圖(P231),圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意Vi-1,Vi和vi+1均相鄰稱為鏈。用表示：,起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。,.,圖與網(wǎng)絡(luò)的基本概念與模型,網(wǎng)絡(luò)（賦權(quán)圖）(P232),設(shè)圖G（V，E），對(duì)G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量)等等。端點(diǎn)無(wú)序的賦權(quán)圖稱為無(wú)向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。,.,11,圖與網(wǎng)絡(luò)的基本概念與模型,主要概念(p231-p232)無(wú)向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。連通圖：對(duì)無(wú)向圖G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖?；芈罚喝袈返牡谝粋€(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則該路為回路。賦權(quán)圖：對(duì)一個(gè)無(wú)向圖G的每一條邊(vi,vj)，相應(yīng)地有一個(gè)數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。網(wǎng)絡(luò)：在賦權(quán)的有向圖D中指定一點(diǎn)，稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為收點(diǎn)，其它點(diǎn)稱為中間點(diǎn)，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就稱為網(wǎng)絡(luò)。,.,最短路問(wèn)題,如何用最短的線路將三部電話連起來(lái)？此問(wèn)題可抽象為設(shè)ABC為等邊三角形，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯然是二邊之和（如ABAC）。,A,B,C,.,最短路問(wèn)題,A,B,C,P,但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接4點(diǎn)的新網(wǎng)絡(luò)的最短路線為PAPBPC。最短新路徑之長(zhǎng)N比原來(lái)只連三點(diǎn)的最短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好。,.,最短路問(wèn)題,問(wèn)題描述：要求：就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路.有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短路的問(wèn)題。因此這類問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。,.,最短路問(wèn)題,例渡河游戲一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過(guò)河到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問(wèn)應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過(guò)河去，并且在河上來(lái)回次數(shù)最少？這個(gè)問(wèn)題就可以用求最短路方法解決。,.,最短路問(wèn)題,定義：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）點(diǎn)Vi表示河岸的狀態(tài)3）邊ek表示由狀態(tài)vi經(jīng)一次渡河到狀態(tài)vj4）權(quán)邊ek上的權(quán)定為1,我們可以得到下面的加權(quán)有向圖：,.,最短路問(wèn)題,狀態(tài)說(shuō)明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戲轉(zhuǎn)化為在下面的二部圖中求從v1到u1的最短路問(wèn)題。,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,.,最短路問(wèn)題,求最短路有兩種算法:,狄克斯屈拉(Dijkstra)（雙標(biāo)號(hào)）算法逐次逼近算法,最短路問(wèn)題：對(duì)一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)Vs和Vt找到一條從Vs到Vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。,.,最短路問(wèn)題,狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法的基本思路：若序列vs,v1.vn-1,vn是從vs到vt間的最短路，則序列vs,v1.vn-1必為從vs到vn-1的最短路。,假定v1v2v3v4是v1v4的最短路，則v1v2v3一定是v1v3的最短路，v2v3v4也一定是v2v4的最短路。,.,最短路問(wèn)題,最短路的Dijkstra算法(雙標(biāo)號(hào)法）的步驟：1.給出點(diǎn)V1以標(biāo)號(hào)(0,s)2.找出已標(biāo)號(hào)的點(diǎn)的集合I，沒(méi)標(biāo)號(hào)的點(diǎn)的集合J以及弧的集合3.如果上述弧的集合是空集，則計(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)下一步。4.對(duì)上述弧的集合中的每一條弧，計(jì)算sij=li+cij。在所有的sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號(hào)（scd,c）,返回步驟2。,.,最短路問(wèn)題,(P233)例1求下圖中v1到v6的最短路解：采用Dijkstra算法，可解得最短路徑為v1v3v4v6各點(diǎn)的標(biāo)號(hào)圖如下：,.,最短路問(wèn)題,(P234)例2電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題?？梢园褵o(wú)向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來(lái)求解。也可直接在無(wú)向圖中用Dijkstra算法來(lái)求解。只要在算法中把從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的弧的集合改成已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的邊的集合即可。,.,最短路問(wèn)題,（0,s）V1（甲地）,15,17,6,2,4,4,3,10,6,5,(13,3)v2,(22,6)V7（乙地）,V5(14,3),V6(16,5),V3(10,1),V4(18,5),.,最短路問(wèn)題,例3設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價(jià)格表設(shè)備維修費(fèi)如下表,.,最短路問(wèn)題,例3的解：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：用vi表示“第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備”,弧（vi,vj）表示第i年年初購(gòu)進(jìn)的設(shè)備一直使用到第j年年初。把所有弧的權(quán)數(shù)計(jì)算如下表：,.,最短路問(wèn)題,(繼上頁(yè))把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條：v1v3v6和v1v4v6,.,最短路問(wèn)題,課堂練習(xí)：1.用Dijkstra算法求下圖從v1到v6的最短距離及路線。,v3,v5,4,v1到v6的最短路為：,.,最短路問(wèn)題,2.求從v1到v8的最短路徑,.,最短路問(wèn)題,v1到v8的最短路徑為v1v4v7v5v8，最短距離為10,.,最短路問(wèn)題,3.求下圖中v1點(diǎn)到另外任意一點(diǎn)的最短路徑,v1,v2,v3,v4,v6,v5,3,2,2,7,6,2,1,3,3,.,最短路問(wèn)題,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,.,最短路問(wèn)題,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,.,最短路問(wèn)題,算法適用條件：Dijkstra算法只適用于全部權(quán)為非負(fù)情況，如果某邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近算法。,例6.7如右圖所示中按dijkstra算法可得P(v1)=5為從vsv1的最短路長(zhǎng)顯然是錯(cuò)誤的，從vsv2v1路長(zhǎng)只有3。,v2,vs,v1,5,-5,8,.,最小生成樹(shù)問(wèn)題,樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。,例6.2乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。,運(yùn)動(dòng)員,.,最小生成樹(shù)問(wèn)題,例某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。,.,樹(shù)與圖的最小樹(shù),樹(shù)：無(wú)圈的連通圖即為樹(shù),性質(zhì)1：任何樹(shù)中必存在次為1的點(diǎn)。(一個(gè)點(diǎn)Vi的相關(guān)聯(lián)邊的數(shù)目稱為點(diǎn)Vi的次)性質(zhì)2：n個(gè)頂點(diǎn)的樹(shù)必有n-1條邊。性質(zhì)3：樹(shù)中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)4：樹(shù)連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹(shù)無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。,.,37,最小生成樹(shù)問(wèn)題,樹(shù)是圖論中的重要概念，所謂樹(shù)就是一個(gè)無(wú)圈的連通圖。,圖11-11中，(a)就是一個(gè)樹(shù)，而(b)因?yàn)閳D中有圈所以就不是樹(shù)，(c)因?yàn)椴贿B通所以也不是樹(shù)。,.,最小生成樹(shù)問(wèn)題,圖的最小部分樹(shù)(支撐樹(shù)),如果G2是G1的部分圖，又是樹(shù)圖，則稱G2是G1的部分樹(shù)（或支撐樹(shù)）。樹(shù)圖的各條邊稱為樹(shù)枝，一般圖G1含有多個(gè)部分樹(shù)，其中樹(shù)枝總長(zhǎng)最小的部分樹(shù)，稱為該圖的最小部分樹(shù)（或最小支撐樹(shù)）。,G1,G2,.,最小生成樹(shù)問(wèn)題,.,最小生成樹(shù)問(wèn)題,.,最小生成樹(shù)問(wèn)題,.,最小生成樹(shù)問(wèn)題,.,最小生成樹(shù)問(wèn)題,.,44,最小生成樹(shù)問(wèn)題,給了一個(gè)無(wú)向圖G=(V,E)，我們保留G的所有點(diǎn)，而刪掉部分G的邊或者說(shuō)保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖11-12中，(b)和(c)都是(a)的生成子圖。如果圖G的一個(gè)生成子圖還是一個(gè)樹(shù)，則稱這個(gè)生成子圖為生成樹(shù)，在圖11-12中，(c)就是(a)的生成樹(shù)。最小生成樹(shù)問(wèn)題就是指在一個(gè)賦權(quán)的連通的無(wú)向圖G中找出一個(gè)生成樹(shù)，并使得這個(gè)生成樹(shù)的所有邊的權(quán)數(shù)之和為最小。,(a),(b),(c),.,最小生成樹(shù)問(wèn)題,求樹(shù)的方法：破圈法和避圈法,破圈法,.,最小生成樹(shù)問(wèn)題,部分樹(shù),.,最小生成樹(shù)問(wèn)題,避圈法,.,最小生成樹(shù)問(wèn)題,賦權(quán)圖中求最小樹(shù)的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,邊數(shù)n-1=5,.,最小生成樹(shù)問(wèn)題,得到最小樹(shù)：,MinC(T)=15,.,最小生成樹(shù)問(wèn)題,避圈法:去掉G中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。加邊的原則為：從最短邊開(kāi)始添加，加邊的過(guò)程中不能形成圈，直到點(diǎn)點(diǎn)連通(即:n-1條邊)。,.,最小生成樹(shù)問(wèn)題,v1,v2,v3,v4,v5,v6,4,3,5,2,1,MinC(T)=15,.,最小生成樹(shù)問(wèn)題,練習(xí)：應(yīng)用破圈法求最小樹(shù),.,最小生成樹(shù)問(wèn)題,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,.,最小生成樹(shù)問(wèn)題,練習(xí)：應(yīng)用避圈法求最小樹(shù),v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹(shù)問(wèn)題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,.,最小生成樹(shù)問(wèn)題,課堂練習(xí)：,MinC(T)=12,MinC(T)=15,答案：,.,最小生成樹(shù)問(wèn)題,3,4,1,2,2,3,2,3,2,4,2,MinC(T)=12,MinC(T)=18,.,74,最小生成樹(shù)問(wèn)題,例5、某大學(xué)準(zhǔn)備對(duì)其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中v1,v7表示7個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通7個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度為最短。,解：此問(wèn)題實(shí)際上是求圖11-14的最小生成樹(shù)，這在例4中已經(jīng)求得，也即按照?qǐng)D11-13的(f)設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線路長(zhǎng)度為最短，為19百米?！肮芾磉\(yùn)籌學(xué)軟件”有專門的子程序可以解決最小生成樹(shù)問(wèn)題。,.,網(wǎng)絡(luò)的最大流,如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。,.,網(wǎng)絡(luò)的最大流,基本概念：1.容量網(wǎng)絡(luò)：隊(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過(guò)能力，稱為該弧的容量，簡(jiǎn)記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)(也稱源點(diǎn)，記為s)和一個(gè)收點(diǎn)(也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為中間點(diǎn)。,s,t,4,8,4,4,1,2,2,6,7,9,.,網(wǎng)絡(luò)的最大流,2.網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。,3.流與可行流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧(vi,vj)上的負(fù)載量記為fij。若fij=0，稱為零流。滿足以下條件的一組流稱為可行流。,容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0fijcij中間點(diǎn)平衡條件。,若以v(f)表示網(wǎng)絡(luò)中從st的流量，則有：,.,網(wǎng)絡(luò)的最大流,結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）,網(wǎng)絡(luò)最大流問(wèn)題：指滿足容量限制條件和中間點(diǎn)平衡的條件下，使v(f)值達(dá)到最大。,.,79,網(wǎng)絡(luò)的最大流,一、最大流的數(shù)學(xué)模型例6某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬(wàn)加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運(yùn)送石油，問(wèn)每小時(shí)能運(yùn)送多少加侖石油？,v5,.,80,網(wǎng)絡(luò)的最大流,我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，則有：,.,81,網(wǎng)絡(luò)的最大流,在這個(gè)線性規(guī)劃模型中，其約束條件中的前6個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。其后面幾個(gè)約束條件表示對(duì)每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量cij，并大于等于零，即0fijcij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流fij稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。我們把例6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運(yùn)籌學(xué)軟件”，馬上得到以下的結(jié)果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最優(yōu)值（最大流量）=10。,.,82,網(wǎng)絡(luò)的最大流,二、最大流問(wèn)題網(wǎng)絡(luò)圖論的解法對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖:(a)和(b)、(c)和(d)的意義相同。用以上方法對(duì)例6的圖的容量標(biāo)號(hào)作改進(jìn)，得下圖,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,.,83,網(wǎng)絡(luò)的最大流,求最大流的基本算法（1）找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的最小的順流的容量pf，通過(guò)這條路增加網(wǎng)絡(luò)的流量pf。（3）在這條路上，減少每一條弧的順流容量pf，同時(shí)增加這些弧的逆流容量pf，返回步驟（1）。用此方法對(duì)例6求解：第一次迭代：選擇路為v1v4v7。弧（v4,v7）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,.,84,網(wǎng)絡(luò)的最大流,第二次迭代：選擇路為v1v2v5v7?；。╲2,v5）的順流容量為3，決定了pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：第三次迭代：選擇路為v1v4v6v7?；。╲4,v6）的順流容量為1，決定了pf=1，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,.,85,網(wǎng)絡(luò)的最大流,第四次迭代：選擇路為v1v4v3v6v7?；。╲3,v6）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：第五次迭代：選擇路為v1v2v3v5v7?；。╲2,v3）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：,.,86,網(wǎng)絡(luò)的最大流,經(jīng)過(guò)第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一條路，路上的每一條弧順流容量都大于零，運(yùn)算停止。得到最大流量為10。最大流量圖如下圖：,“管理運(yùn)籌學(xué)軟件”中還有專門的子程序用于解決最大流問(wèn)題。,.,87,最小費(fèi)用最大流問(wèn)題,最小費(fèi)用最大流問(wèn)題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條弧（vi,vj），除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流F，并使得總運(yùn)送費(fèi)用最小。一、最小費(fèi)用最大流的數(shù)學(xué)模型例7由于輸油管道的長(zhǎng)短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，還有不同的單位流量的費(fèi)用bij，cij的單位為萬(wàn)加侖/小時(shí)，bij的單位為百元/萬(wàn)加侖。如圖。從采地v1向銷地v7運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大流量和最小費(fèi)用。,.,88,最小費(fèi)用最大流問(wèn)題,這個(gè)最小費(fèi)用最大流問(wèn)題也是一個(gè)線性規(guī)劃的問(wèn)題。解：我們用線性規(guī)劃來(lái)求解此題，可以分兩步走。第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過(guò)管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。第二步，在最大流量F的所有解中，找出一個(gè)最小費(fèi)用的解，我們來(lái)建立第二步中的線性規(guī)劃模型如下：仍然設(shè)?。╲i,vj）上的流量為fij，這時(shí)已知中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用fij.bij。由此得到線性規(guī)劃模型如下：,.,89,最小費(fèi)用最大流問(wèn)題,.,90,最小費(fèi)用最大流問(wèn)題,用管理運(yùn)籌學(xué)軟件，可求得如下結(jié)果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最優(yōu)值(最小費(fèi)用)=145。對(duì)照前面例6的結(jié)果，可對(duì)最小費(fèi)用最大流的概念有一個(gè)深刻的理解。如果我們把例7的問(wèn)題改為：每小時(shí)運(yùn)送6萬(wàn)加侖的石油從采地v1到銷地v7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問(wèn)題。一般來(lái)說(shuō)，所謂最小費(fèi)用流的問(wèn)題就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對(duì)每條弧(vi,vj)賦權(quán)以容量cij及單位費(fèi)用bij的網(wǎng)絡(luò)中，求一個(gè)給定值f的流量的最小費(fèi)用，這個(gè)給定值f的流量應(yīng)小于等于最大流量F，否則無(wú)解。求最小費(fèi)用流的問(wèn)題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量F改為f即可。在例6中只要把f12+f14=F改為f12+f14=f=6得到了最小費(fèi)用流的線性規(guī)劃的模型了。,.