指導chap7圖論與網(wǎng)絡優(yōu)化模型

1、第七章 圖論與網(wǎng)絡優(yōu)化模型 7.1 圖論基本概念與最小生成樹7.2 最短路問題7.3 網(wǎng)絡最大流7.4 二分圖與鎖具裝箱問題y實際背景 例1（公路連接問題）某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，使得從其中一個城市都可以經高速公路直接或間接到達另一個城市。假定已經知道了任意兩個城市之間修建高速公路的成本，那么如何決定在哪些城市間修建高速公路總成本最?。坷?（最短路問題）一名貨車司機奉命在最短的時間內將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨車的運行速度是恒定的，那么這個問題相當于需要找到一條從甲地到乙地的

2、最短路。例3（運輸問題）某種原材料有m個產地，現(xiàn)在需要將原材料從產地運往n個使用工廠。假定m個產地的產量和n個工廠的需求量已知，單位產品從任一產地到任一工廠的運費已知，那么，如何安排運輸方案可以使總運輸成本最低？實際背景 例4（指派問題）一家公司經理準備安排n名員工去完成n項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的收益不同，如何分配工作方案使總回報最大？例5（中國郵遞員問題）一名郵遞員負責投遞某個街區(qū)的郵件。如何為他設計一條最短的投遞路線？即從郵局出發(fā)，經過投遞區(qū)內每條街道至少一次，最后返回郵局。例6（旅行商問題）一名推銷員準備前往若干城市推銷產品。如何為他設

3、計一條最短的旅行路線？即從駐地出發(fā)，經過每個城市恰好一次，最后返回駐地。實際背景 共同特點：（1）它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學上把這種問題稱為優(yōu)化問題。（2）它們都易于用圖形的形式直觀的描述和表達，數(shù)學上把這種與圖相關的結構稱為網(wǎng)絡，與圖和網(wǎng)絡相關的優(yōu)化問題稱為網(wǎng)絡優(yōu)化。哥尼斯堡七橋問題 在無孤立結點的圖g中,若存在一條回路,它經過圖中每條邊一次且僅一次,稱此回路為歐拉回路. 無向圖g具有歐拉回路,當且僅當g是連通的,且所有結點的度都是偶數(shù).圖論基本概念與最小生成樹一、 圖 的 概 念1、圖的定義2、頂點的次數(shù) 3、子圖二、 圖 的 矩 陣 表 示

4、1、 關聯(lián)矩陣2、 鄰接矩陣三、 最 小 生 成 樹定義有序二元組g=(v,e )稱為一個圖.1 是有窮非空集，稱為頂點集 其中的元素叫圖g的頂點。2 e稱為邊集，其中的元素稱為圖g的邊。 例設g=(v,e),其中g的圖解如圖12,nvv vv123412345,vv v v vee e e e e定義定義在圖 g 中，與 v 中的有序偶(vi， vj)對應的邊 e，稱為圖的有有向向邊邊（或?。?，而與 v 中頂點的無序偶 vivj相對應的邊 e，稱為圖的無無向向邊邊.每一條邊都是無向邊的圖，叫無無向向圖圖；每一條邊都是有向邊的圖，稱為有有向向圖圖；既有無向邊又有有向邊的圖稱為混混合合圖圖.定

5、義定義若將圖 g 的每一條邊 e 都對應一個實數(shù) w(e)，稱 w(e)為邊的權權，并稱圖 g 為賦賦權權圖圖.規(guī)定用記號和分別表示圖的頂點數(shù)和邊數(shù).關聯(lián)矩陣對無向圖，其關聯(lián)矩陣)(ijm，其中：不關聯(lián)與若相關聯(lián)與若jijiijevevm01m=43215432110110011000101110001vvvveeeee對有向圖，其關聯(lián)矩陣)(ijm，其中：不關聯(lián)與若的終點是若的起點是若jijijiijevevevm011注：假設圖為簡單圖鄰接矩陣對無向圖，其鄰接矩陣)(ijaa，其中：不相鄰與若相鄰與若jijiijvvvva01注：假設圖為簡單圖a=432143210111101011011

6、010vvvvvvvv對有向圖（，） ，其鄰接矩陣)(ijaa，其中：evvevvajijiij），若（），若（01對有向賦權圖，其鄰接矩陣)(ijaa，其中：evvjiwevvwajiijjiijij),(0,),(若若為其權且若無向賦權圖的鄰接矩陣可類似定義a=4321432105375083802720vvvvvvvv樹的等價定義樹的等價定義無回路的連通圖無回路的連通圖.無回路且無回路且=v-1 其中其中是是t的邊數(shù)的邊數(shù),v是是t的結點數(shù)的結點數(shù).連通的且連通的且=v-1.無回路但添加一條新邊則得到一條僅有的回路無回路但添加一條新邊則得到一條僅有的回路.連通的連通的,但刪去任一條邊但刪

7、去任一條邊,t便不連通便不連通.每對結點之間有一條且僅有一條路每對結點之間有一條且僅有一條路. 如果圖如果圖g的生成子圖是樹的生成子圖是樹, 則稱此樹為則稱此樹為g的的生成樹生成樹.例：某地要建例：某地要建5個工廠，擬修筑道路連接這個工廠，擬修筑道路連接這5處。經勘測處。經勘測其道路可依下圖的無向邊鋪設。為使這其道路可依下圖的無向邊鋪設。為使這5處都有道路處都有道路相通，問至少要鋪設幾條路？怎樣鋪設？相通，問至少要鋪設幾條路？怎樣鋪設？v1v4v5v2v3v1v4v5v2v3v1v4v5v2v3最小生成樹（最小生成樹（kruskal（克魯斯克爾）算法）（克魯斯克爾）算法） 設圖設圖g有有n個結

8、點，以下算法產生的是最小生成樹個結點，以下算法產生的是最小生成樹1）選取最小權邊）選取最小權邊e1，置邊數(shù)，置邊數(shù)i1；2）i=n-1結束，否則轉入結束，否則轉入3）；）；3）設已選擇邊為）設已選擇邊為e1,e2,ei, 在在g中選取不同于中選取不同于e1,e2,ei的邊的邊ei+1，使，使e1,e2,ei,ei+1中無回路且中無回路且ei+1是滿足此條件的最小邊；是滿足此條件的最小邊；4） ii1,轉入轉入2）。）。注意：最小生成樹不唯一，但不同的最小生成樹的邊權之和是唯一的邊按升序排序邊按升序排序:邊邊(vi, vj)記成記成eij邊權邊權e28e34e23e38e17e24e45e57e

9、16e78e56e35e46e67e58e12e181 1 2 2 2 3 3 3 4 4 4 5 6 6 7 7 8v1 v5 v4v2 v3v8 v6v7 12213772486653443v1 v5 v4v2 v3v8 v6v7 1212433 to mtlb(kruskl.m)驗證：p95例11最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂點之間的最短路基 本 概 念通路44112544141vevevevevwvv道路4332264521141vevevevevevtvv路徑4521141vevevpvv定義定義（）任意兩點均有路徑的圖稱為連通圖連通圖（）起點與終點重合

10、的路徑稱為圈圈（）連通而無圈的圖稱為樹樹定定義義（）設 p(u,v)是賦權圖 g 中從 u 到 v的路徑， 則稱)()()(peeewpw為路徑 p 的權權(2) 在賦權圖 g 中，從頂點 u 到頂點 v的具有最小權的路 ),(*vup，稱為 u 到 v的最最短短路路固定起點的最短路最短路是一條路徑 假設在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點到其余頂點的最短路dijkstra 算法算法：求 g 中從頂點 u0到其余頂點的最短路設 g 為賦權有向圖或無向圖，g 邊上的權均非負對每個頂點，定義兩個標記（l v( )

11、，z v( )） ，其中: l v( )：表從頂點 u0到 v 的一條路的權 z v( )：v 的父親點，用以確定最短路的路線算法的過程就是在每一步改進這兩個標記，使最終l v( )為從頂點u0到 v 的最短路的權s：具有永久標號的頂點集輸入: g 的帶權鄰接矩陣),(vuw算法步驟：（3） 設v*是使l v( )取最小值的s中的頂點，則令 s=sv*， uv*（4） 若s ，轉 2，否則，停止.（2）更新l v( )、z v( )： vsvs,若l v( )l uw u v( )( , ) 則令l v( )=l uw u v( )( , ),z v( )= u例例 求下圖從頂點 u1到其余頂

12、點的最短路先寫出帶權鄰接矩陣： 03064093021509701608120w因 g 是無向圖，故 w是對稱陣 to mtlb(dijkstr.m)(iul迭代次數(shù)1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后標記:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u)(iul1u2u3u 4u5u6u 7u 8u最后標記:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8驗證

13、：p97例1每對頂點之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（二）算法原理（三）算法步驟算法的基本思想 直接在圖的帶權鄰接矩陣中用插入頂點的方法依次構造出個矩陣 d(1)、 d(2)、 、d()，使最后得到的矩陣 d()成為圖的距離矩陣，同時也求出插入點矩陣以便得到兩點間的最短路徑算法原理 求距離矩陣的方法把帶權鄰接矩陣 w 作為距離矩陣的初值，即 d(0)=)()0(ijd=w（）d(1)= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是從 vi到 vj的只允許以 v1作為中間點的路

14、徑中最短路的長度（2）d(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點的路徑中最短路的長度（）d()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點的路徑中最短路的長度即是從 vi到 vj中間可插入任何頂點的路徑中最短路的長，因此d()即是距離矩陣算法原理 求路徑矩陣的方法r=)(ijr, rij的含義是從 vi到 vj的最短路要經過點號為 rij的點)()0()0(ijrr, jri

15、j)0(每求得一個 d(k)時，按下列方式產生相應的新的 r(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距離矩陣的同時可建立路徑矩陣r 即當vk被插入任何兩點間的最短路徑時，被記錄在r(k)中，依次求 時求得 ，可由 來查找任何點對之間最短路的路徑)(d)(r)(rij算法原理查找最短路路徑的方法若1)(prij，則點 p1是點 i 到點 j 的最短路的中間點.然后用同樣的方法再分頭查找若：（） 向點 i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向點 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1

16、p3q1q2qm則由點i到j的最短路的路徑為：jqqqpppimk,21, 12算法步驟floyd 算法：算法：求任意兩點間的最短路d(i,j)：i 到 j 的距離r(i,j)：i 到 j 之間的插入點輸入: 帶權鄰接矩陣 w(i,j)（） 賦初值：對所有 i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新 d(i,j), r(i,j)對所有 i,j，若 d(i,k)+d(k,j)d(i,j)，則 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉（） 例、求下圖任意兩點之間的最短路徑的長度654321654321654321

17、654321654321654321r,022203230142221034301210d例例 求下圖中加權圖的任意兩點間的距離與路徑 to mtlb(rod2(floyd)5333434331543243332344441,0646960243420256420793570rd951d，故從 v5到 v1的最短路為51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以從 v5到 v1的最短路徑為：1435.可化為最短路問題的多階段決策問題最短路的應用（2）弧集 e=(,)v vij，i=1,2,3,4,5; ij6,弧(,)v vij表第 i 年初購進一臺設備一

18、直使用到第 j 年初的決策，其權 w(,)v vij表由這一決策在第 i 年初到第 j 年初的總費用，如w(,)v v14=11+5+6+8=30.（2） 計算在各點iv設立服務設施的最大服務距離)(ivs max)(1ijjidvs , 2 , 1i 選址問題-中心問題例例 2某城市要建立一個消防站，為該市所屬的七個區(qū)服務，如圖所示問應設在那個區(qū)，才能使它至最遠區(qū)的路徑最短（1）用 floyd 算法求出距離矩陣 d=)(ijd（3）求出頂點kv，使)(min)(1iikvsvs則kv就是要求的建立消防站的地點此點稱為圖的中心點中心點 to mtlb(rod3(floyd)05 .15 .55

19、 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530ds(v1)=10, s(v2)=7, s(v3)=6, s(v4)=8.5, s(v5)=7, s(v6)=7, s(v7)=8.5s(v3)=6,故應將消防站設在v3處。 7.3 7.3 網(wǎng)絡流問題網(wǎng)絡流問題 1、 網(wǎng)絡流圖2 、最大流問題及其解法3 、最小費用問題及其解法問題1：7種設備要用5架飛機運往目的地，每種設備各有4臺，這5架飛機的容量分別為8，8，5，4，4臺，問能否有一種裝載法，使同一種類型的設備不會有兩臺在同一架飛機上。問

20、題2：設有王二、張三、李四、趙五四人及小提琴、大提琴、鋼琴和吉他四種樂器，已知四人的特長如下： 王二擅長拉大提琴和彈鋼琴； 張三擅長拉小提琴、大提琴和吉他； 李四擅長拉小提琴和大提琴； 趙五只會彈吉他；今假設四人同臺演出，每人奏一種樂器，問四人同時各演奏一種樂器時所有可能的方案。網(wǎng)絡流圖是滿足下列條件的有向賦權圖網(wǎng)絡流圖是滿足下列條件的有向賦權圖),(wevg （1 1）有一個發(fā)點）有一個發(fā)點 和收點和收點（2 2）每條邊都有一個容量（權）每條邊都有一個容量（權）ss),(jivvw 實際含義是發(fā)點可以看作運輸問題的起點，收點可以看作運實際含義是發(fā)點可以看作運輸問題的起點，收點可以看作運輸問題

21、的終點，邊可以看作運輸路線，權數(shù)可以看作該線路的輸問題的終點，邊可以看作運輸路線，權數(shù)可以看作該線路的運輸能力。運輸能力。 設設 是定義在有向賦權圖是定義在有向賦權圖 邊集邊集 上的上的一個數(shù)值函數(shù)，滿足：一個數(shù)值函數(shù)，滿足：),(jivvf),(wevg e（2）除過發(fā)點和起點外，),(),( , ),(),(xvvyvyfxvfiiyixi和的邊。和離開分別是進入iivv),(),(jijivvwvvf（1 1）一、網(wǎng)絡流圖的流。是則稱),(),(. 0),(),(wevgvvfqysfsxfjiyx該定義的實際意義分別為：1、每條邊的實際流量不超過它的容量。2、流入和流出每個節(jié)點的流量相

22、等。（物質不滅，無損耗）3、從發(fā)點流出的流量等于流入收點的流量。稱 的流值。為流)(),(),()(,jiyxvvfsyfxsffq3、二、最大流問題及其求解方法 （一）最大流問題最大流問題 設有向網(wǎng)絡n（v，），在發(fā)點vs 有一批貨，要通過網(wǎng)絡上的弧運輸?shù)绞拯cvt 去，受運輸條件限制，每條弧ij在單位時間內通過的車輛數(shù)不能超過cij 輛，分析：如何組織運輸才能使從vs到vt 在單位時間內通過的車輛達到最多？ 上面描述的這類問題，稱為最大流問題。 最大流問題廣泛地應用在交通運輸、供水、油管供油、郵電通訊，也可以用在生產安排，管理優(yōu)化等實際問題上。例：如圖1中，有一批物資需要用汽車盡快從發(fā)點運到

23、收點，?。╥，j）上所標的數(shù)字表示該條道路在單位時間內最多能通過的車輛數(shù)（單位：百輛），問如何調運，才能使單位時間里有最多的車輛從調到。425136756385577113223圖1 點出發(fā)的車輛數(shù)應該與點到達的車輛數(shù)相同，除和以外的各中間點，進的車輛數(shù)應該與離去的車輛數(shù)應該相同。fxxxxx67571413126765564636575665352546341436353432231325233212xxxxxxxxxxxxxxxxxxxxxxxxij 是通過弧(i，j)的車輛數(shù)。（1）（4）（5）（6）（2）（3） 對所有?。╥，j），應滿足約束 滿足（1）（7）的解稱為從到的一個可行流，

24、 我們的目的：在所有可行流中求出一個方案，使得這個可行流得到的 f 最大。 若從收點到發(fā)點連接一條假想弧(7，1)，設它的容量c71=，那么 對點： 對點： 最大流問題的目標為 ijijcx 0（7）14131271xxxx716757xxx（8）（9）（10）max71x所以，對于發(fā)點為vs，收點為vt的網(wǎng)絡n（v，u），當增加一條約束為cts=的假想弧（t，s）后，最大流問題就成為： 容量約束： 平衡條件： 目標函數(shù)： ijijcx 0ujjijuijjixx),(),(maxstx（11）（12）（13）（二）求最大流的方法：弧標號法 盡管最大流問題可以用線性規(guī)劃模型描述，但是我們一般并

25、不用求解線性規(guī)劃的方法求最大流，而是用一種更為簡便明了的圖上作業(yè)法弧標號法，求解上述最大流問題。 為了便于弧標號法的計算，首先需要將最大流問題（譬如圖1）重新改畫成為圖2的形式。 2416357st650230081023730071000055圖2 在圖在圖2 2中，每條弧中，每條弧 上標有兩個數(shù)字，其中，上標有兩個數(shù)字，其中，靠近點靠近點 i 的是的是 ，靠近點，靠近點 j j 的是的是 。如。如 表示從表示從到到的最大通過量是的最大通過量是5 5（百輛），從（百輛），從到到的最大通過量是的最大通過量是0 0； 表示從表示從到到和從和從到到都可以通過都可以通過2 2（百輛）；等等。（百輛）

26、；等等。 ijcjic05222416357st650230081023730071000055ijv圖2 求最大流的基本步驟： 弧標號法求最大流的過程，就是對圖2反復地進行修改的過程，其計算步驟如下： 步驟1. 從發(fā)點s到收點t選定一條路，使這條路通過的所有弧vij的前面約束量cij都大于0，如果找不到這樣的路，說明已經求得最大流，轉步驟4。 步驟2. 在選定的路上，找到最小的容許量cij定為p。 步驟3. 對選定的路上每條弧的容量作以下修改，對于與路同向的弧，將cij修改為cij-p，對于與路反向的弧，將cij修改為cij+p。修改完畢后再轉入步驟1。步驟4.用原圖中各條弧上起點與終點數(shù)值

27、減去修改后的圖中對應點的數(shù)值，得到正負號相反的兩個數(shù)，并將從正到負的方向用箭頭表示。這樣，就得到一個最大流量圖。 下面，我們用弧標號法求解圖2中的最大流。 第一次修改第一次修改：（1）從發(fā)點）從發(fā)點s到收點到收點t找一條路，使得這條路上的找一條路，使得這條路上的所有弧前面的約束量所有弧前面的約束量 。從圖。從圖2 2中可以看出，中可以看出，顯然，顯然，就是滿足這樣的條件的一就是滿足這樣的條件的一條路。條路。 （2）在路中, , , ,所以取 。 0ijc613c736c767c613 cp（3）在路中，修改每一條弧的容量： 066613-pc660031pc660063pc16-7767pc1

28、6-7736pc660076pc通過第1次修改，得到圖3。 2416357st05023008162 3130611600055圖3返回步驟（1），進行第2次修改。 第二次修改：選定，在這條路中，由于 ，所以，將 改為2 ， 改為0， 改為5， 、 、 改為3。修改后的圖變?yōu)閳D4。 325 cp12c25c57c21c52c75c2416357st023203051623133611600055返回步驟（1），繼續(xù)做第3次修改。 圖4第三次修改：取，在這條，由于 ，所以將 改為0， 改為5， 改為0， 改為4， 改為1， 改為2， 改為3， 改為5。修改后的圖變?yōu)閳D5。 12c21c23c32

29、c35c53c57c75c2cp122416357st005003231641135611600055圖5返回步驟（1），繼續(xù)做第4次修改。 第四次修改：選定，在這條路中，由于 p =c67 =1，所以將c14改為4,c41改為1,c46改為4,c64改為1,c67改為0，c76 改為7。修改后的圖為變?yōu)閳D6 。 2416357st00500323164 1135701611044圖6返回步驟（1），繼續(xù)做第5次修改。 第五次修改：選定,在這條路中，由于 p = c65 = 1，所以將c14和c46均改為3，c65改為0，c57改為2，c41、c64、c56均改為2，c75改為6。修改后的圖變

30、為圖7。 2416357st005003222641136500622033圖7 需要注意的是，由圖7中可以看出，弧 本來在圖2中是無容量可通過的，但經過幾次修改，由 變成 ，即此時從到還可通過1（百輛），而從到，可以通過6（百輛）的容量，這說明，修改過程實際上是把計劃中從到的通過車輛數(shù)減少了。0761(6,3)取，在這條路中，由于p=c35=1，所以將 c14和 c46均改為2，c63改為5, c35改為0，c57改為1，c41、c64、c53均改為3，c36改為2，c75改為7。修改后的圖變?yōu)閳D8。 2416357st005003312640237500533022圖8 在圖8中，從發(fā)點到

31、收點，再也不存在連通的起點容量都大于零的弧了，所以圖8為最大流圖。 轉入步驟（4），用原圖中各條弧上起點與終點數(shù)值減去修改后的圖上各點的數(shù)值，將得到正負號相反的兩個數(shù)，將這個數(shù)標在弧上，并將從正到負的方向用箭頭表示,這樣就得到最大流量圖。例如原來弧 是 ，現(xiàn)在是 ，相減為5，那邊為正，我們就記作 。這樣，就得到圖9，即最大流量。依這樣的調度方式，可以從發(fā)點s調運14（百輛）汽車到收點t。 07525(3,6)6373371035542513672圖9 最大流量圖 圖10最大流fmx的大小是確定的，但最大流的路線可以不唯一。在上例中，如果從不同的路開始來修改圖，也可能得到另外一個最大流圖（圖10）。 2416357563233177235注意驗證：p104 例2應用舉例 一制造商需要把兩個車間d1,d2生產的同類商品通過運輸網(wǎng)絡送到三個銷售點m1,m2,m3去，如圖所示。設各銷售點計劃銷售量分別為10,8,8，問網(wǎng)絡的運輸能力能否滿足這一要求？兩個車間生產數(shù)量多少最為恰當？三、 最小費用