圖與網絡模型及方法

圖與網絡模型及方法圖與網絡模型及方法PPT1圖與網絡模型及方法圖與網絡模型及方法PPT1圖與子圖圖的連通與割集樹與支撐樹最小樹最短有向路最大流最小費用流最大對集圖與網絡模型及方法圖與子圖圖與網絡模型及方法2圖與網絡

無向圖的基本概念網絡的基本概念關聯矩陣和鄰接矩陣

關聯矩陣鄰接矩陣主要結論子圖圖與網絡模型及方法圖與網絡圖與網絡模型及方法3緒論圖論起源于18世紀。第一篇圖論論文是瑞士數學家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。1847年，克希霍夫為了給出電網絡方程而引進了“樹”的概念。1857年，凱萊在計數烷n2n+2CH的同分異構物時，也發(fā)現了“樹”。哈密爾頓于1859年提出“周游世界”游戲，用圖論的術語，就是如何找出一個連通圖中的生成圈圖與網絡模型及方法緒論圖論起源于18世紀。圖與網絡模型及方法4緒論近幾十年來，由于計算機技術和科學的飛速發(fā)展，大大地促進了圖論研究和應用，圖論的理論和方法已經滲透到物理、化學、通訊科學、建筑學、運籌學，生物遺傳學、心理學、經濟學、社會學等學科中。圖與網絡模型及方法緒論近幾十年來，由于計算機技術和科學的飛速發(fā)展，大大地促進了5緒論圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯系。如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關系的離散系統(tǒng)提供了一個數學模型，借助于圖論的概念、理論和方法，可以對該模型求解。圖與網絡模型及方法緒論圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯系。6哥尼斯堡七橋問題這個圖是連通的，且每個點都與偶數線相關聯圖與網絡模型及方法哥尼斯堡七橋問題這個圖是連通的，且每個點都與偶數線相關聯圖與7緒論圖與網絡是運籌學（OperationsResearch）中的一個經典和重要的分支，所研究的問題涉及經濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術、通訊與網絡技術等諸多領域的最短路問題、最大流問題、最小費用流問題和匹配問題等都是圖與網絡的基本問題。圖與網絡模型及方法緒論圖與網絡是運籌學（OperationsResearch8圖------由若干個點和連接這些點的連線所組成的圖形vi——圖中的點，稱為頂點（代表具體事物，研究對象。ei——圖中的連線，稱為邊（對象之間的聯系）m(G)=|E|——G的邊數，簡記為mn(G)=|V|——G的頂點數，簡記為n一.圖的概念記V={vi}——點的集合，E={ei}——邊的集合G={V，E}G——一個圖m=6,n=5圖的基本概念圖與網絡模型及方法圖------由若干個點和連接這些點的連線所組成的圖形vi—9有向圖無向圖——邊e=(vi,vj)有方向vi為始點，vj為終點——邊e=(vi,vj)無方向，此時(vi,vj)=(vj,vi)e4=(v3，v4）=(v4，v3）e4=(v3，v4)≠(v4，v3）e5=(v3，v4）=(v4，v3）此時(vi,vj)≠(vj,vi)e5=(v4，v3)≠(v3，v4)圖有向圖無向圖圖與網絡模型及方法有向圖無向圖——邊e=(vi,vj)有方向vi為始點，vj10二.常用名詞：1、端點和關聯邊：2、相鄰點和相鄰邊：3、多重邊與環(huán)：4、多重圖和簡單圖：無環(huán)也無多重邊的圖稱為簡單圖。含有多重邊的圖稱為多重圖；圖與網絡模型及方法二.常用名詞：1、端點和關聯邊：2、相鄰點和相鄰邊：3、多重115、次：6、懸掛點和懸掛邊：次為1的點稱為懸掛點，與懸掛點相聯的邊稱為懸掛邊。7、孤立點：8、奇點與偶點：，G的邊數m=6圖與網絡模型及方法5、次：6、懸掛點和懸掛邊：7、孤立點：8、奇點與偶點：，G12性質1：在圖G=(V,E)中，所有點的次之和是邊數m的兩倍。證明：由于每條邊均與兩個頂點關聯，因此在計算頂點的次時每條邊都計算了兩遍，所以頂點次數的總和等于邊數的二倍。三.次（度）的性質性質2：在任何圖G=(V,E)中，奇點的個數為偶數證明：設V1，V2分別是圖G中奇點和偶點的集合，則V1∪V2=V,

V1∩V2=Φ,有性質1，，因為V2是偶點的集合，d(vi)(i∈V2)均為偶數，所以只有偶數個奇數相加才能得到偶數，所以V1中的點，即奇點的個數為偶數。圖與網絡模型及方法性質1：在圖G=(V,E)中，所有點的次之和是邊數m的兩倍。13四.鏈、路、連通圖1.鏈：對于無向圖G=(V，E)，若圖G中有一個點與邊的交替序列 μ={vi0,ei1,vi1,ei2,

,vik-1,eik,vik}，且eit=(vit-1,vit)(t=1,2,…,k), 則稱該交替序列

μ為連結vi0和vik的一條鏈。簡單鏈：μ中只有重復的點而無重復邊者為簡單鏈。初等鏈：μ中沒有重復的點和重復邊者為初等鏈。圈：無向圖G中，連結vi0與vik的一條鏈，當vi0與vik是同一個點時，稱此鏈為圈。圈中只有重復點而無重復邊者為簡單圈，既（除起點、終點重復外）無重復點也無重復邊者為初等圈不是鏈初等鏈簡單鏈圖與網絡模型及方法四.鏈、路、連通圖1.鏈：對于無向圖G=(V，E)，若圖G14（簡單圈）（初等圈）2路：在有向圖D=(V，A)中，若有從vi0到vik不考慮方向的鏈，且各邊方向一致，則稱之為從vi0到vik的一條路。

對于有向圖可以類似于無向圖定義鏈和圈，初等鏈、圈，簡單鏈、圈．此時不考慮邊的方向。而當鏈(圈)上的邊方向相同時，稱為道路(回路)。對于無向圖來說，道路與鏈、回路與圈意義相同圖與網絡模型及方法（簡單圈）（初等圈）2路：在有向圖D=(V，A)中，若有從153連通圖：一個圖中任意兩點間至少有一條鏈(或路)相連的圖。連通圖非連通圖五．網絡在實際問題中，往往只用圖來描述所研究對象之間的關系還不夠，與圖聯系在—起的，通常還有與點或邊有關的某些數量指標，通常稱之為“權”，權可以代表如距離、費用、通過能力(容量)等等。這種帶有某種數量指標的圖稱為網絡(賦權圖)。圖與網絡模型及方法3連通圖：一個圖中任意兩點間至少有一條鏈(或路)相連的圖。16如公路交通圖：vi表示城市,ei表示公路w(ei)表示公路ei的長度如w(e2)=50表示城市v2與城市v3之間的距離是50千米六.完全圖、偶圖1．完全圖：一個簡單圖，若任意兩個頂點之間均有一條邊相連，則稱這樣的圖為完全圖。對于完全圖，由于每個頂點與所有其余頂點都有一條邊相連，所以在有n個頂點的完全圖中，各個頂點的次均為（n-1）。圖與網絡模型及方法如公路交通圖：vi表示城市,ei表示公路w(ei)表示公路e172.偶圖：若圖G的頂點能分成兩個互不相交的非空集合V1和V2，使在同一集合中的任意兩個頂點均不相鄰，稱這樣的圖為偶圖，也稱為二部圖。若偶圖的頂點集合V1，V2之間的每一對不同頂點都有一條邊相連，稱這樣的圖為完全偶圖。v2v3v4v5v2v3v4v5??????????v1v1完全圖(完全)偶圖定理一個圖為偶圖的充分必要條件該圖無奇圈圖與網絡模型及方法2.偶圖：若圖G的頂點能分成兩個互不相交的非空集合V1和V218七.子圖、部分圖對于圖G1={V1,E1}和圖G2={V2,E2},若有，稱G1是G2的一個子圖。若有，稱G1是G2的一個部分圖（生成子圖）。*部分圖也是子圖，但子圖不一定是部分圖。生成子圖圖與網絡模型及方法七.子圖、部分圖*部分圖也是子圖，但子圖不一定是部分圖。生19七.子圖、部分圖*部分圖也是子圖，但子圖不一定是部分圖。生成子圖對于圖G1={V1,E1}和圖G2={V2,E2},若有，稱G1是G2的一個子圖。若有，稱G1是G2的一個部分圖（生成子圖）。圖與網絡模型及方法七.子圖、部分圖*部分圖也是子圖，但子圖不一定是部分圖。生20八.前向弧與后向弧設μ是一條從vs到vt的鏈，則鏈μ上與鏈的方向一致的弧稱為前向弧，記這些弧為μ+；鏈μ上與鏈的方向相反的弧稱為后向弧，記這些弧為μ-。???????vsv1v2v3v4v5vt前向弧與后向弧圖與網絡模型及方法八.前向弧與后向弧???????vsv1v2v3v4v5vt21子圖設G1=[V1,E1],G2=[V2,E2]子圖定義：如果V2

V1,E2

E1

稱G2

是G1

的子圖；真子圖：如果V2

V1,E2

E1

稱G2

是G1

的真子圖；部分圖：如果V2=V1,E2

E1

稱G2

是G1

的部分圖；導出子圖：如果V2

V1,E2={[vi,vj]∣vi,vj

V2}，稱G2

是G1

中由V2

導出的導出子圖。圖與網絡模型及方法子圖設G1=[V1,E1],G222九、圖的矩陣表示用矩陣表示圖對研究圖的性質及應用常常是比較方便的．定義：網絡(賦權圖)G＝(V，E)，其邊(vi,vj)有權ωij,構造矩陣A=(aij)n×n,其中：稱矩陣A為網絡G的權矩陣。例、寫出下圖的權矩陣v1v2v3v4?????v5765424938圖與網絡模型及方法九、圖的矩陣表示定義：網絡(賦權圖)G＝(V，E)，其邊(v23定義：對于圖G＝(V，E)，|V|=n,構造一個矩陣A=(aij)n×n,其中：稱矩陣A為圖G的鄰接矩陣。例、寫出下圖的鄰接矩陣v1v3v5??????v2v4v6當G為無向圖時，鄰接矩陣為對稱矩陣圖與網絡模型及方法定義：對于圖G＝(V，E)，|V|=n,構造一個矩陣A=(a24最短軌道問題給出了一個連接若干個城鎮(zhèn)的鐵路網絡，在這個網絡的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的頂點，兩城鎮(zhèn)間的直通鐵路為圖G相應兩頂點間的邊，得圖G。對G的每一邊e，賦以一個實數w(e)—直通鐵路的長度，稱為e的權，得到賦權圖G。G的子圖的權是指子圖的各邊的權和。問題就是求賦權圖G中指定的兩個頂點u0,v0間的具最小權的軌。這條軌叫做u0

,v0間的最短路，它的權叫做u0

,v0間的距離，亦記作d(u0

,v0)圖與網絡模型及方法最短軌道問題給出了一個連接若干個城鎮(zhèn)的鐵路網絡，在這個網絡的25最短軌道問題求法---Dijkstra算法基本思想是按距

u0從近到遠為順序，依次求得u0到G的各頂點的最短路和距離，直至v0（或直至G的所有頂點），算法結束。為避免重復并保留每一步的計算信息，采用了標號算法。圖與網絡模型及方法最短軌道問題求法---Dijkstra算法基本思想圖與網26最短軌道問題求法---Dijkstra算法圖與網絡模型及方法最短軌道問題求法---Dijkstra算法圖與網絡模型及27定義：連通且不含圈的無向圖稱為樹。記作T(V，E)二、樹樹可以有很多等價的定義,以下定理中的各命題都體現樹的特征.定理設G={V,E}是一無向圖，|V|=n，|E|=m。則以下命題是等價的.(1)G是樹;(2)G的每對頂點之間有唯一的一條路;(3)G連通且m=n-1;(4)G無圈且m=n-1;(5)G無圈,在G的任一對頂點上加一新邊后產生圈;(6)G連通，但刪去任何一邊后不再連通。圖與網絡模型及方法定義：連通且不含圈的無向圖稱為樹。記作T(V，E)二、樹樹28定理：無向圖G有生成樹當且僅當G連通。證明:必要性顯然,只證充分性。若G無圈，則G本身就是G的生成樹。若G有圈C，則在G中刪去C的一條邊，所得的圖是連通的，繼續(xù)這個過程，直到所得的圖T無圈為止，則T就是G的一棵生成樹。定義：若圖G的生成子圖是一棵樹，則稱該樹為G的生成樹(支撐樹)?；蚝喎Q為圖G的樹(b)為(a)圖的生成樹圖與網絡模型及方法定理：無向圖G有生成樹當且僅當G連通。定義：若圖G的生成子29最小生成樹的求法：避圈法與破圈法定義：樹的各條邊稱為樹枝。一般圖G的生成樹有多個，稱其中樹枝總長度最小的生成樹為最小樹。避圈法：在圖G中，每步選出一條邊e，使它與已選邊不構成圈，且e是未選邊中長度最小的邊，直到選夠n-1邊為止。?????????v1v2v3v8v7v6v5v4v04112131444523552?????????v1v2v3v8v7v6v5v4v011211232圖與網絡模型及方法最小生成樹的求法：避圈法與破圈法定義：樹的各條邊稱為樹枝。30?????????v1v2v3v8v7v6v5v4v04112131444523552?????????v1v2v3v8v7v6v5v4v011211232破圈法：從網絡圖N中任取一回路，去掉該回路中權數最大的一條邊，得一子網絡圖N1。在N1中再任取一回路，去掉該回路中權數最大的一條邊，得一子網絡圖N2。如此繼續(xù)下去，直到剩下的子圖中不再含回路為止。該子圖就是N的最小生成樹。?????????v1v2v3v8v7v6v5v4v04112131444523552圖與網絡模型及方法?????????v1v2v3v8v7v6v5v4v041131筑路選線問題欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為wij，設計一個線路圖使總造價最低連線問題的數學模型是在連通賦權圖上求權最小的生成樹。賦權圖的具最小權的生成樹叫做最小生成樹造最小生成樹的兩種常用算法---prim算法與Kruskal算法。圖與網絡模型及方法筑路選線問題欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵32prim算法構造最小生成樹設置兩個集合P和Q,其中P用于存放G的最小生成樹中的頂點，集合Q存放G的最小生成樹中的邊。令集合P的初值為{}1P=v（假設構造最小生成樹時，從頂點

v1出發(fā)），集合Q的初值為Q=Φ。prim算法的思想是：從所有p∈P，v∈V?P的邊中，選取具有最小權值的邊pv，將頂點v加入集合P中，將邊pv加入集合Q中，如此不斷重復，直到P=V時，最小生成樹構造完畢，這時集合Q中包含了最小生成樹的所有邊。圖與網絡模型及方法prim算法構造最小生成樹設置兩個集合P和Q,其中P用33圖與網絡模型及方法圖與網絡模型及方法34Kruskal算法構造最小生成樹圖與網絡模型及方法Kruskal算法構造最小生成樹圖與網絡模型及方法35可行遍問題定義1：經過G的每條邊的跡叫做G的Euler跡；閉的Euler跡叫做Euler回路或E回路；含Euler回路的圖叫做Euler圖。直觀地講，Euler圖就是從一頂點出發(fā)每邊恰通過一次能回到出發(fā)點的那種圖，即不重復地行遍所有的邊再回到出發(fā)點。圖與網絡模型及方法可行遍問題定義1：經過G的每條邊的跡叫做G的Eule36定理6（i）G是Euler圖的充分必要條件是G連通且每頂點皆偶次。（ii）G是Euler圖的充分必要條件是G連通且（iii）G中有Euler跡的充要條件是G連通且至多有兩個奇次點。圖與網絡模型及方法定理6（i）G是Euler圖的充分必要條件是G連通且37定義包含G的每個頂點的軌叫做Hamilton(哈密頓)軌；閉的Hamilton軌叫做Hamilton圈或H圈；含Hamilton圈的圖叫做Hamilton圖。直觀地講，Hamilton圖就是從一頂點出發(fā)每頂點恰通過一次能回到出發(fā)點的那種圖，即不重復地行遍所有的頂點再回到出發(fā)點。圖與網絡模型及方法定義包含G的每個頂點的軌叫做Hamilton(哈密頓)軌38圖與網絡模型及方法圖與網絡模型及方法39圖與網絡模型及方法圖與網絡模型及方法40圖與網絡模型及方法圖與網絡模型及方法41Euler回路的Fleury算法圖與網絡模型及方法Euler回路的Fleury算法圖與網絡模型及方法42可行遍問題的應用中國郵遞員問題一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當然他必須經過他負責投遞的每條街道至少一次，為他設計一條投遞路線，使得他行程最短。中國郵遞員問題的數學模型：在一個賦權連通圖上求一個含所有邊的回路，且使此回路的權最小。圖與網絡模型及方法可行遍問題的應用中國郵遞員問題圖與網絡模型及方法43若此連通賦權圖是Euler圖，則可用Fleury算法求Euler回路，此回路即為所求。對于非Euler圖，1973年，Edmonds和Johnson給出下面的解法：圖與網絡模型及方法若此連通賦權圖是Euler圖，則可用Fleury算法求44多郵遞員問題郵局有k(k≥2)位投遞員，同時投遞信件，全城街道都要投遞，完成任務返回郵局，如何分配投遞路線，使得完成投遞任務的時間最早？我們把這一問題記成kPP。kPP的數學模型如下：圖與網絡模型及方法多郵遞員問題郵局有k(k≥2)位投遞員，同時投遞信件，全45旅行商（TSP）問題一名推銷員準備前往若干城市推銷產品，然后回到他的出發(fā)地。如何為他設計一條最短的旅行路線（從駐地出發(fā)，經過每個城市恰好一次，最后返回駐地）？是在一個賦權完全圖中，找出一個有最小權的Hamilton圈。稱這種圈為最優(yōu)圈與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個方法以獲得相當好（但不一定最優(yōu)）的解。圖與網絡模型及方法旅行商（TSP）問題一名推銷員準備前往若干城市推銷產品，然后46改良圈算法。圖與網絡模型及方法改良圈算法。圖與網絡模型及方法47旅行商問題的數學表達式圖與網絡模型及方法旅行商問題的數學表達式圖與網絡模型及方法48對集圖與網絡模型及方法對集圖與網絡模型及方法49圖與網絡模型及方法圖與網絡模型及方法50圖與網絡模型及方法圖與網絡模型及方法51圖與網絡模型及方法圖與網絡模型及方法521957年，貝爾熱(Berge)得到最大對集的充要條件：定理2M是圖G中的最大對集當且僅當G中無M可增廣軌。1935年，霍爾(Hall)得到下面的許配定理：定理3G為二分圖，X與Y是頂點集的劃分，G中存在把X中頂點皆許配的對集的充要條件是，，?S?X，則|N(S)|≥|S|，其中N(S)是S中頂點的鄰集。圖與網絡模型及方法1957年，貝爾熱(Berge)得到最大對集的充要條件：圖53推論1：若G是k次（k>0)正則2分圖，則G有完美對集。所謂k次正則圖，即每頂點皆k度的圖。由此推論得出下面的婚配定理：定理4每個姑娘都結識k(k≥1)位小伙子，每個小伙子都結識k位姑娘，則每位姑娘都能和她認識的一個小伙子結婚，并且每位小伙子也能和他認識的一個姑娘結婚。圖與網絡模型及方法推論1：若G是k次（k>0)正則2分圖，則G有完54人員分派問題工作人員x1,x2,…,xn

去做n件工作y1,y2,…,yn

，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？這個問題的數學模型是：G是二分圖，頂點集劃分為V(G)=XUY，X={x1,…,xn}，Y={y1,…,yn}，當且僅當xi適合做工作yj時，xiyj

∈E(G)，求G中的最大對集。圖與網絡模型及方法人員分派問題工作人員x1,x2,…,xn去做55人員分派問題匈牙利算法1965年埃德門茲(Edmonds)提出匈牙利算法。匈牙利算法：（i）從G中任意取定一個初始對集M。（ii）若M把X中的頂點皆許配，停止，M即完美對集；否則取X中未被M許配的一頂點u，記S={u}，T=Φ。（iii）若N(S)=T，停止，無完美對集；否則取y∈N(S)?T。（iv）若y是被M許配的，設yz∈M，S=SU{z}，T=TU{y}，轉（iii）；否則，取可增廣軌P(u,y)，令M=(M?E(P))U(E(P)?M)，轉（ii）。圖與網絡模型及方法人員分派問題匈牙利算法1965年埃德門茲(Edmonds)56最優(yōu)分派問題在人員分派問題中，工作人員適合做的各項工作當中，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。這個問題的數學模型是：在人員分派問題的模型中，圖G的每邊加了權w(xi

，

yj)≥0表示xi干yj工作的效益，求加權圖G上的權最大的完美對集。解決這個問題可以用庫恩—曼克萊斯（Kuhn-Munkres）算法圖與網絡模型及方法最優(yōu)分派問題在人員分派問題中，工作人員適合做的各項工作當中，57定義若映射l:V(G)→R，滿足?x∈X,y∈Y，l(x)+l(y)≥w(x,y)，則稱l是二分圖G的可行頂點標號。令El

={xy|xy∈E(G),l(x)+l(y)=w(xy)}，稱以lE為邊集的G的生成子圖為相等子圖，記作Gl?？尚许旤c標號是存在的。例如定理5G

l的完美對集即為G的權最大的完美對集。圖與網絡模型及方法定義若映射l:V(G)→R，滿足?x∈X,y∈Y58Kuhn-Munkres算法圖與網絡模型及方法Kuhn-Munkres算法圖與網絡模型及方法59最短路問題最短路問題是網絡理論中應用最廣泛的問題之一。許多優(yōu)化問題可以便用這個模型．如設備更新、管道鋪設、線路安排、廠區(qū)布局等。最短路問題的一般提法：設G={V，E}為連通圖，圖中各邊(vi,vj)有權l(xiāng)ij(lij=∞表示vi,vj間無邊)。vs,vt為圖中任意兩點，求一條路μ，使它是從vs到vt的所有路中總權最小的路。即最小有些最短路問題是求網絡中某指定點到其余所有點的最短路，或求網絡中任意兩點間的最短路。下面介紹三種算法，可分別用于求解這幾種最短路問題。圖與網絡模型及方法最短路問題最小有些最短路問題是求網絡中某指定點到其余所有點的60(2)使用條件——網絡中所有的弧(邊)權均非負，即：(1)基本思路基于以下原理：若序列{vs,v1,…,vn-1,vn}是從vs到vn的最短路，則序列{vs,v1,…,vn-1}必為從vs到vn-1的最短路。

1、Dijkstra算法本算法由Dijkstra于1959年提出，可用于求解指定兩點vs、vt間的最短路，或從指定點vs到其余各點的最短路。下面給出Dijkstra算法基本步驟，采用標號法。圖與網絡模型及方法(2)使用條件——網絡中所有的弧(邊)權均非負，即：(1)61可用兩種標號：T標號與P標號，T標號為試探性標號，P為永久性標號，給vi點一個P標號時，表示從vs到點vi的最短路權,vi點的標號不再改變。給vi點一個T標號時．表示從vs到點vi的估計最短路權的上界，是一種臨時標號．凡沒有得到P標號的點都有T標號。算法每一步都把某一點的T標號改為P標號，當終點vt得到P標號時，全部計算結束。對于有n個頂點的圖，最多經n一1步就可以得到從始點到終點的最短路。標號的意義：①標號P(永久性標號)—從始點到該標號點的最短路權。②標號T(臨時性標號—從始點到該標號點的最短路權上界。圖與網絡模型及方法可用兩種標號：T標號與P標號，T標號為試探性標號，P為永久性62計算步驟：第二步：若vi為剛得到P標號的點，考慮這樣的點vj：(vi,vj)屬于E，且vj為T標號。對vj的T標號進行如下的更改：T(vj)=min{T(vj),P(vi)+lij}第三步：比較所有具有T標號的點，把最小者改為P標號，即

第一步：給始點vs標上永久性標號P(vs)=0，其余各點標臨時性標號T(vj)=+,當存在兩個以上最小者時，可同時改為P標號。若全部點均為P標號則停止。否則用代vi轉回第二步。圖與網絡模型及方法計算步驟：第二步：若vi為剛得到P標號的點，考慮這樣的點vj63例、用Dijkstar算法求下圖中v1到v7點的最短路。???????v1v3v2v7v5v4v6171344452572(1)首先給v1以P標號,P(v1)=0,其余所有點給T標號,T(vi)=+∞（圖中()內的數表示P標號；[]內的數表示T標號）???????v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7圖與網絡模型及方法例、用Dijkstar算法求下圖中v1到v7點的最短路。??64???????v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞](2)由于邊(v1,v2)、(v1,v3)、(v1,v4)屬于E，且v2,v3,v4為T標號，所以修改這三個點的標號：

T(v2)=min{T(v2),P(v1)+l12}=min{∞,0+4}=4 T(v3)=min{T(v3),P(v1)+l13}=min{∞,0+2}=2

T(v4)=min{T(v4),P(v1)+l14}=min{∞,0+5}=57(3)比較所有T標號，T(v3)最小，所以令P(v3)=2圖與網絡模型及方法???????v1v2v7v5v411344452572v365???????v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]7???????v1(0)v2v7v5v411344452572v3(2)v6[4][4][9][∞][∞]7(4)v3為剛得到P標號的點，考察邊(v3,v4),(v3,v6)的端點v4,v6。

T(v4)=min{T(v4),P(v3)+l34}=min{5,2+2}=4 T(v6)=min{T(v6),P(v3)+l36}=min{∞,2+7}=9(5)比較所有T標號，T(v2),T(v4)最小，所以令P(v2)=P(v4)=4圖與網絡模型及方法???????v1v2v7v5v411344452572v366???????v1(0)v2v7v5v411344452572v3(2)v6(4)(4)[9][∞][∞]7(6)v2,v4為剛得到P標號的點,考察邊(v2,v5),),(v4,v5),(v4,v6)的端點v5,v6。

T(v5)=min{T(v5),P(v4)+l45,P(v2)+l25}=min{∞,4+3,4+4}=7 T(v6)=min{T(v6),P(v4)+l46}=min{9,4+4}=8???????v1(0)v2v7v5v411344452572(4)(4)[8][7][∞]7v3(2)v6圖與網絡模型及方法???????v1v2v7v5v411344452572v367(7)比較所有T標號，T(v5)所以令P(v5)=7???????v1(0)v2v7v5v411344452572(4)(4)(7)[∞][8]v3(2)v6???????v1(0)v2v7v5v411344452572(4)(4)(7)[14][8]v3(2)v6(8)v5為剛得到P標號的點，考察邊(v5,v6),(v5,v7)的端點v6,v7。

T(v6)=min{T(v6),P(v5)+l56}=min{8,7+1}=8 T(v7)=min{T(v7),P(v5)+l57}=min{∞,7+7}=1477圖與網絡模型及方法(7)比較所有T標號，T(v5)所以令P(v5)=7??68(9)比較所有T標號，T(v6)最小，所以令P(v6)=8???????v1(0)v2v7v5v411344452572(4)(4)(7)[14](8)v3(2)v6(10)v6為剛得到P標號的點，考察邊(v6,v7)的端點v7。

T(v7)=min{T(v7),P(v6)+l67}=min{14,8+5}=13???????v1(0)v2v7v5v411344452572(4)(4)(7)[13](8)v3(2)v677圖與網絡模型及方法(9)比較所有T標號，T(v6)最小，所以令P(v6)=869(11)只有一個T標號T(v7)，令P(v7)=13，停止。???????v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67計算結果見上圖，v1到v7的最短路為：同時得到v1到其余各點的最短路*這個算法只適用于全部權為非負情況．如果某邊的權為負，算法失效。圖與網絡模型及方法(11)只有一個T標號T(v7)，令P(v7)=13，70上面的例題是針對無向圖求最短路的問題，對有向圖最短路的求法類似。下面以設備更新問題為例說明有向圖最短路的計算方法。例(設備更新問題)某企業(yè)在四年內都要使用某種設備，在每年年初作出是購買新設備還是繼續(xù)使用舊設備的決策。若購買新設備就要支付購置費；若繼續(xù)使用舊設備，則需支付維修費用。這種設備在四年之內每年年初的價格以及使用不同時間（年）的設備的維修費用估計為：年份1234年初購價10111213維修費用24714問題：制定一個四年之內的設備更新計劃，使得四年之內的設備購置費和維修費用之和最小。圖與網絡模型及方法上面的例題是針對無向圖求最短路的問題，對有向圖最短路的求法類71可以用求最短路問題的方法來解決總費用最少的設備更新計劃問題。符號的含義：vi—第i年年初購進一臺新設備(v5表示第四年年底)弧(vi,vj)—表示第i年年初購進的設備一直使用到第j年年初(即第j-1年年底)弧(vi,vj)的權數表示從第i年年初購進的設備一直使用到第j年年初所花費的購置費和維修費用的總和。如何制定使得總費用最少的設備更新計劃問題可以轉化最短路問題。此最短路問題如圖所示。圖與網絡模型及方法可以用求最短路問題的方法來解決總費用最少的設備更新計劃問題。72圖中權數

ij的確定：

12=10+2=12；13=10+2+4=16；14=10+2+4+7=23；15=10+2+4+7+14=37；23=11+2=13；24=11+2+4=17；25=11+2+4+7=24；34=12+2=14；35=12+2+4=18；45=13+2=15下面用Dijkstra算法求v1到v5的最短路。給v1以P標號，P(v1)=0,其余各點給以T標號，T(vi)=+∞(i=2,3,4,5)。（圖中()內的數表示P標號；[]內的數表示T標號）圖與網絡模型及方法圖中權數ij的確定：下面用Dijkstra算法求v1到v573(2)由于（v1,v2）,(v1,v3),（v1,v4）,（v1,v5）∈A，且v2,v3,v4,v5為T標號，所以修改這四個點的標號：T(v2)=min{T(v2),P(v1)+

12}=min{+∞,0+12}=12T(v3)=min{T(v3),P(v1)+13}=min{+∞,0+16}=16T(v4)=min{T(v4),P(v1)+14}=min{+∞,0+23}=23T(v5)=min{T(v5),P(v1)+15}=min{+∞,0+37}=37(3)比較所有具有T標號的點，把最小者改為P標號。T(v2)最小，令P(v2)=12。圖與網絡模型及方法(2)由于（v1,v2）,(v1,v3),（v1,v4）,（74(4)v2為剛得到P標號的點，考察弧(v2,v3),(v2,v4),(v2,v5)的端點v3,v4,v5。T(v3)=min{T(v3),P(v2)+

23}=min{16,12+13}=16T(v4)=min{T(v4),P(v2)+24}=min{23,12+17}=23T(v5)=min{T(v5),P(v2)+25}=min{37,12+24}=36(5)比較所有具有T標號的點，把最小者改為P標號。T(v3)最小，令P(v3)=16。圖與網絡模型及方法(4)v2為剛得到P標號的點，考察弧(v2,v3),(v275(6)考察點v3

T(v4)=min{T(v4),P(v3)+

34}=min{23,16+14}=23T(v5)=min{T(v5),P(v3)+35}=min{36,16+18}=34(7)所有T標號中，T(v4)最小，令P(v4)=23圖與網絡模型及方法(6)考察點v3圖與網絡模型及方法76(8)考察點v4T(v5)=min{T(v5),P(v4)+

45}=min{34,23+15}=34(9)只有一個T標號T(v5)，令P(v5)=34，計算結束。由上可知：v1到v5的最短路為v1→v3→v5,長度為34。其含義為：最佳更新計劃為第一年年初購買新設備使用到第二年年底(第三年年初)，第三年年初再購買新設備使用到第四年年底，這個計劃使得總的支付最小，其值為34。圖與網絡模型及方法(8)考察點v4圖與網絡模型及方法77???????v1v3v2v7v5v4v617134452572練習、求下圖中任意兩點間的最短路4圖與網絡模型及方法???????v1v3v2v7v5v4v617134452578例、某地7個村莊之間的現有交通道路如下圖所示，邊旁數字為各村莊之間道路的長度。現要在某一村莊修建一所小學，該小學應建在哪個村莊,可使離該村最遠的村莊的學生所走的路程最少？該問題可分作兩步來考慮：1）求出任意兩個村莊之間的最短路長；2）找出每一點到其余各點按照最短路線的最遠點,大中取小即可。圖與網絡模型及方法例、某地7個村莊之間的現有交通道路如下圖所示，邊旁數字為各村79首先寫出權矩陣用Floyd算法求出任意兩點之間的最短路的長度找出每一點到其余各點按照最短路線的最遠點取這些最遠距離中的最小者(小學應建在v4村)max作業(yè):P227

習題4.4圖與網絡模型及方法首先寫出權矩陣用Floyd算法求出任意兩點之間的最短路的長度80覆蓋與點獨立集圖與網絡模型及方法覆蓋與點獨立集圖與網絡模型及方法81圖與網絡模型及方法圖與網絡模型及方法82圖與網絡模型及方法圖與網絡模型及方法83圖與網絡模型及方法圖與網絡模型及方法84圖與網絡模型及方法圖與網絡模型及方法85圖與網絡模型及方法圖與網絡模型及方法86圖與網絡模型及方法圖與網絡模型及方法87圖與網絡模型及方法圖與網絡模型及方法88圖與網絡模型及方法圖與網絡模型及方法89圖與網絡模型及方法圖與網絡模型及方法90圖與網絡模型及方法圖與網絡模型及方法91圖與網絡模型及方法圖與網絡模型及方法92最大流問題最大流問題是在一個給定網絡上求流量最大的可行流，即給一個網絡的每條弧規(guī)定一個流量的上界，求從點vs到vt的最大流。下圖是一個輸油管道網，vs為起點，vt為終點，v1~v6為中轉站，弧旁的數表示該管道的最大輸油量。問題：如何安排，才能使從vs到vt的輸油量最大？圖與網絡模型及方法最大流問題最大流問題是在一個給定網絡上求流量最大的可行流，即93最大流問題1最大流問題的數學描述1.1網絡中的流定義在以V為節(jié)點集，A為弧集的有向圖G=(V,A)上定義如下的權函數：圖與網絡模型及方法最大流問題圖與網絡模型及方法94（i）L:A→R為孤上的權函數，弧(i,j)∈A對應的權L(i,j)記為lij，稱為孤(i,j)的容量下界（lowerbound）；（ii）U:A→R為弧上的權函數，弧(i,j)∈A對應的權U(i,j)記為uij，稱為孤(i,j)的容量上界，或直接稱為容量（capacity）；（iii）D:V→R為頂點上的權函數，節(jié)點i∈V對應的權D(i)記為di，稱為頂點i的供需量（supply／demand）；此時所構成的網絡稱為流網絡，可以記為N=(V,A,L,U,D)。圖與網絡模型及方法（i）L:A→R為孤上的權函數，弧(i,j)∈A95由于我們只討論V,A為有限集合的情況，所以對于弧上的權函數L,U和頂點上的權函數D，可以直接用所有孤上對應的權和頂點上的權組成的有限維向量表示，因此L,U,D有時直接稱為權向量，或簡稱權。由于給定有向圖G=(V,A)后，我們總是可以在它的弧集合和頂點集合上定義各種權函數，所以流網絡一般也直接簡稱為網絡。圖與網絡模型及方法由于我們只討論V,A為有限集合的情況，所以對于弧上的權函數96定義對于流網絡N=(V,A,L,U,D)，其上的一個流（flow）f是指從N的弧集A到R的一個函數，即對每條弧(i,j)賦予一個實數fij

（稱為弧(i,j)的流量）。如果流f滿足則稱f為可行流（feasibleflow）。至少存在一個可行流的流網絡稱為可行網絡（feasiblenetwork）．約束（1）稱為流量守恒條件（也稱流量平衡條件），約束（2）稱為容量約束。圖與網絡模型及方法定義對于流網絡N=(V,A,L,U,D)，其上的一97定義：設有向連通圖G＝(V,E)，G的每條邊(vi,vj)上有非負數cij稱為邊的容量，僅有一個入次為0的點vs稱為發(fā)點(源)，一個出次為0的點vt稱為收點(匯)，其余點為中間點，這樣的網絡G稱為容量網絡，常記做G＝(V,E,C)。對任一G中的邊(vi,vj)有流量fij,，稱集合f＝{fij}網絡G上的一個流。稱滿足下列條件的流f為可行流：

(1)容量限制條件：對G中每條邊(vi,vj)，有0≤fij≤cij(2)平衡條件：對中間點vi，

(即中間點vi的物資的輸入量與輸出量相等)

對收、發(fā)點vs,vt,有

(即從vs點發(fā)出的物資總量等于vt點輸入的量。)W為網絡流的總流量。圖與網絡模型及方法定義：設有向連通圖G＝(V,E)，G的每條邊(vi,vj98可行流總是存在的，例如f＝{0}就是一個流量為0的可行流。最大流問題就是在容量網絡中，尋找流量最大的可行流。一個流f={fij},當fij=cij，則稱流f對邊(vi,vj)是飽和的，否則稱f對(vi,vj)不飽和。根據弧的流量是否為0，可把弧分為零流弧和非零流弧兩類。最大流問題實際是個線性規(guī)劃問題，但是利用它與圖的緊密關系，能更為直觀簡便地求解。圖與網絡模型及方法可行流總是存在的，例如f＝{0}就是一個流量為0的可行流。圖99把網絡D=(V,E,C)的點集V剖分為兩個非空集合Vs和Vt(即Vs∩Vt=

，Vs∪Vt=V)，使vs∈Vs,vt∈Vt，把從Vs指向Vt的弧的全體稱為（分離vs和vt的）截集。稱截集中所有弧的容量之和為這個截集的容量（簡稱為截量）。分離vs和vt的截集往往不只一個，稱其中截量最小的為最小截集。。圖與網絡模型及方法把網絡D=(V,E,C)的點集V剖分為兩個非空集合Vs和Vt100由截集的定義可知：截集是從vs到vt的必經之路，無論去掉哪個截集，從vs到vt就不存在路了，因此任何一個可行流的流量不會超過任何一個截集的容量。因而若能找到一個可行流和一個截集，使得可行流的流量等于這個截集的容量，則該可行流一定是最大流，該截集一定是最小截集。在上圖中，若令Vs={vs,v1,v6},Vt={v2,v3,v4,v5,vt},則：截集為{(vs,v5)(v1,v2),(v1,v5),(v6,v5),(v6,v4)},截量為3+2+4+2+3=14；圖與網絡模型及方法由截集的定義可知：截集是從vs到vt的必經之路，無論去101設

是網絡中從vs到vt的一條鏈，給定向為從vs到vt，沿此方向上的弧可分為兩類：一類是與鏈的方向一致的弧稱為正向弧，用

+

表示正向弧的全體，另一類是與鏈的方向相反的弧稱為反向弧，用-

表示反向弧的全體。在上圖中，在鏈

={vs,v5,v6,v4,v3,vt}中，+={(vs,v5),(v6,v4),(v3,vt)},

-={(v5,v6),(v4,v3)}。增廣鏈：對于可行流f，是一條從vs到vt的一條鏈，如果+中的弧均為非飽和弧，-中的弧均為非零流弧，則稱為從vs到vt的關于f的增廣鏈。定理（最大流量—最小截量定理）：在網絡N中，從vs到vt的最大流的流量等于分離vs到vt的最小截集的截量。圖與網絡模型及方法設是網絡中從vs到vt的一條鏈，給定向為從vs到vt，沿102計算網絡最大流的方法增廣鏈的實際意義在于沿著這條鏈存在增大輸送能力的潛力。如沿著增廣鏈

1={vs,v2,v5,v4,v6,vt}，凡是正向弧的流量都增加1，反向弧的流量都減少1（見上圖），結果整個網絡的流增加了1，即由6增加到7。用這種方法調整后的流仍為可行流。這樣就得到了一個尋找最大流的方法：從一個可行流開始，尋找關于這個可行流的增廣鏈，若增廣鏈存在，則可以經過調整，得到一個新的可行流，其流量比調整前的可行流大，重復這個過程，直到不存在增廣鏈時就得到了最大流。圖與網絡模型及方法計算網絡最大流的方法圖與網絡模型及方法103下面介紹計算網絡最大流的標號算法標號法是由Ford和Fulkerson在1957年提出的設已有一個可行流f(若網絡中沒有給出可行流,則可設f為零流)，標號法可分為兩步：（一）標號過程在這個過程中,網絡中的點或者是標號點，或者是未標號點。每個標號點的標號包含兩個部分：第一個標號表明它的標號是從哪一點得到的，以便找出增廣鏈；第二個標號是為確定增廣鏈的調整量

用的。(1)給發(fā)點vs以標號（0，+∞），第二個數值表示從上一標號點到這個標號點的最大允許調整量。vs為發(fā)點，不限允許調整量，故為+∞。最大流的一種算法—標號法圖與網絡模型及方法下面介紹計算網絡最大流的標號算法最大流的一種算法—標號法圖與104(2)選擇一個已標號的點vi,對于vi的所有未標號的鄰點vj,按下列規(guī)則處理：若邊(vi,vj)∈E,且fij<cij,則令vj=min{vi,cij-fij},并給vj以標號（vi,vj）。若邊(vj,vi)∈E,且fji>0,則令vj=min{fji,vi},并給vj以標號(-vi,vj)(3)重復(2)直到收點vt被標號或不再有點可標號時為止。若vt得到標號，說明存在一條增廣鏈，轉(二)調整過程。若vt未得到標號，標號過程已無法進行時，說明f已是最大流。（二）調整過程

(1)確定調整量

=

vt，

(2)若vt的標號為（vj,vt）,則以fit+代替fit;若vt的標號為 （-vj,vt）,則以fit-代替fit。

(3)令vj代替vt，返回(2)；若vj=vs，則去掉所有標號轉(一)。圖與網絡模型及方法(2)選擇一個已標號的點vi,對于vi的所有未標號的鄰點v105標號法尋求網絡中最大流的基本思想。用標號法尋求網絡中最大流的基本思想是尋找可增廣軌，使網絡的流量得到增加，直到最大為止。即首先給出一個初始流，這樣的流是存在的，例如零流。如果存在關于它的可增廣軌，那么調整該軌上每條弧上的流量，就可以得到新的流。對于新的流，如果仍存在可增廣軌，則用同樣的方法使流的值增大，繼續(xù)這個過程，直到網絡中不存在關于新得到流的可增廣軌為止，則該流就是所求的最大流。圖與網絡模型及方法標號法尋求網絡中最大流的基本思想。用標號法尋求網絡中最大流的106標號法過程A.標號過程：通過標號過程尋找一條可增廣軌。B.增流過程：沿著可增廣軌增加網絡的流量。這兩個過程的步驟分述如下圖與網絡模型及方法標號法過程A.標號過程：通過標號過程尋找一條可增廣軌。圖與網107圖與網絡模型及方法圖與網絡模型及方法108圖與網絡模型及方法圖與網絡模型及方法109例、用標號法求下圖所示的網絡中從vs到vt的最大流量，圖中弧旁數值為容量cij(1)圖中沒有給出初始可行流,可設零流為出初始可行流.如圖1。先給vs標以標號（0，+∞）。(2)檢查vs的鄰點v1,v2可知（vs,v1）∈E，且fs1=0<cs1=10,令

v1=min{+∞,10-0}=10,給v1以標號（vs,10）。用同樣的方法給v2以標號（vs,14）。見圖2圖與網絡模型及方法例、用標號法求下圖所示的網絡中從vs到vt的最大流量，圖中弧110(3)檢查v1的尚未標號的鄰點v3,v4可知(v1,v3)∈E，且f13=0<c13=10,令

v3=min{v1,10-0}=min{10,10}=10,給v3以標號(v1,10),用同樣的方法給v4以標號(v1,10)。圖與網絡模型及方法(3)檢查v1的尚未標號的鄰點v3,v4可知(v1,v3)111(4)檢查v3的尚未標號的鄰點v5,v6可知(v3,v5）∈E，且f35=0<c35=4,令

v5=min{v3,4-0}=min{10,4}=4,給v5以標號(v3,4),對于v6，由于(v6,v3)∈E，且f63=0，不滿足標號條件。檢查v4的尚未標號的鄰點vt可知(v4,vt)∈E，且f4t=0<c4t=13,令vt=min{v4,13-0}=min{10,13}=10,給vt以標號(v4,10)。圖與網絡模型及方法(4)檢查v3的尚未標號的鄰點v5,v6可知(v3,v5）112(5)由于vt已得到標號，則存在增廣鏈，標號過程結束，轉入調整過程。令

=

vt=10為調整量，從vt開始，按標號(v4,10)找到v4并用f4t+10代替f4t，由標號(v1,10)找到v1并用f14+10代替f14，再由標號(vs,10)找到vs并用fs1+10代替fs1，調整過程結束。調整后的可行流見圖5。去掉所有標號，重新開始標號過程。圖5圖與網絡模型及方法(5)由于vt已得到標號，則存在增廣鏈，標號過程結束，轉入調113先給vs標以標號（0，+∞）。檢查vs的鄰點v1,v2可知（vs,v1）∈E但fs1=10=cs1=10,不滿足標號條件。（vs,v2）∈E且fs2=0<cs2=14,令

v2=min{+∞，14-0}=14,給v2以標號（vs,14）。（圖6）(v6,5)用同樣的方法可得v6的標號(v2,5),vt的標號(v6,5)圖與網絡模型及方法先給vs標以標號（0，+∞）。(v6,5)用同樣的方法可得v114令

=5為調整量，從vt開始進行調整，調整后的可行流見下圖。去掉所有標號，重新開始標號過程。(0.+∞)(vs,9)(v2,.5)(v3,5)(v3,4)不滿足標號條件（反向零流?。?v4,3)圖與網絡模型及方法令=5為調整量，從vt開始進行調整，調整后的可行流見下圖。115去掉所有標號，重新開始標號過程。令

=3為調整量，從vt開始進行調整，調整后的可行流見下圖。(0.+∞)(v2,.2)(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)圖與網絡模型及方法去掉所有標號，重新開始標號過程。令=3為調整量，從vt開始116令

=2為調整量，從vt開始進行調整，調整后的可行流見下圖。(0.+∞)(v2,.2)(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)圖與網絡模型及方法令=2為調整量，從vt開始進行調整，調整后的可行流見下圖。117用標號法在得到最大流的同時也得到最小截集(如圖中虛線所示)。標號點集合為VS,即VS={vs,v2}，未標號點集合為Vt

，即Vt={v1,v3,v4,v5,v6,vt}，最小截集{(vs,v1),(v2,v3),(v2,v6)}。最小截集的意義：最小截集中各弧的容量總和決定了網絡的通過能力，為了提高網絡的通過能力，就必須增大最小截集中弧的容量。去掉所有標號，重新開始標號過程。(0.+∞)(vs,4)vt未得到標號，但標號過程已無法進行,說明已得到最大流.其值為20。圖與網絡模型及方法用標號法在得到最大流的同時也得到最小截集(如圖中虛線所示)。118352圖與網絡模型及方法352圖與網絡模型及方法119最小費用流問題上面我們介紹了一個網絡上最短路以及最大流的算法，但是還沒有考慮到網絡上流的費用問題，在許多實際問題中，費用的因素很重要。例如，在運輸問題中，人們總是希望在完成運輸任務的同時，尋求一個使總的運輸費用最小的運輸方案。這就是下面要介紹的最小費用流問題。圖與網絡模型及方法最小費用流問題上面我們介紹了一個網絡上最短路以及最大流的算法1204.6最小費用流問題最小費用最大流問題:給了一個帶收發(fā)點的網絡,對每一條弧(vi,vj),除了給出容量cij外,還給出了這條弧的單位流量的費用bij,要求一個最大流F,并使得總運送費用最小。最小費用最大流的網絡圖論解法較麻煩,因此下面介紹用線性規(guī)劃模型結合運籌學軟件求解最小費用最大流問題例.某石油公司擁有一個管道網絡,使用這個網絡可以把石油從采地運送到一些銷售點,這個網絡的一部分如下圖所示.由于管道的直徑的變化,它的各段管道(vi,vj)的容量cij(單位:萬加侖/小時,各段管道單位流量的費用為bij(單位:百元/萬加侖).如圖,從采地v1向銷地v7運送石油,怎樣運送才能運送最多的石油并使得總的運送費用最小?求出最大流量和最小費用.(弧旁括號中第一個數表示容量cij,第二個數表示單位流量的費用bij)圖與網絡模型及方法4.6最小費用流問題最小費用最大流問題:給了一個帶收發(fā)121(6,6)(3,4)(5,7)(2,5)(2,4)(2,3)(4,4)(1,3)(2,8)(6,3)(3,2)v1v2v7v4v3v6用線性規(guī)劃模型求解該問題,可分為兩個步驟:第一步先求出此網絡圖中的最大流量F,通過運籌學軟件獲得以下結果.f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最大流量=10。圖與網絡模型及方法(6,6)(3,4)(5,7)(2,5)(2,4)(2,3)122第二步在最大流量F的所有解中,找出一個最小費用的解.下面建立第二步中的線性規(guī)劃模型如下：仍然設弧(vi,vj)上的流量為fij,這時已知網絡中最大流量為F.線性規(guī)劃模型如下：s.t.圖與網絡模型及方法第二步在最大流量F的所有解中,找出一個最小費用的解.下面123用管理運籌學軟件,可求得如下結果：f12=4,f14=6,f25=3,f23=1,f43=3,f57=5,f36=2,f46=1,f47=2,f67=3,f35=2.其最優(yōu)值(最小費用)=145.與前面求最大流的結果對比.f12=5,f14=5,f23=2,f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3最大流量=10。圖與網絡模型及方法用管理運籌學軟件,可求得如下結果：f12=5,f14=5,f124如果把上例的問題改為：每小時運送6萬加侖的石油從采地v1到銷地v7最小費用是多少？應怎樣運送？這就變成了一個最小費用流的問題。一般來說，所謂最小費用流的問題就是：在給定了收點和發(fā)點并對每條弧(vi,vj)賦權以容量cij及單位費用bij的網絡中，求一個給定值f的流量的最小費用，這個給定值f的流量應小于等于最大流量F，否則無解。求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模型中的約束條件中的發(fā)點流量F改為f即可。在上例中只要把f12+f14=F改為f12+f14=f=6得到了最小費用流的線性規(guī)劃的模型。圖與網絡模型及方法如果把上例的問題改為：每小時運送6萬加侖的石油從采地v1到銷1254.7分配問題一、最大匹配例、考慮有n個工人，m件工作的工作分配問題。每個工人能力不同，各能勝任某幾項工作。假設每件工作只需一人做，每人只做一件工作