第七章圖論與網絡優化模型

7.1圖論基本概念與最小生成樹7.2最短路問題7.3網絡最大流7.4二分圖與鎖具裝箱問題y第七章圖論與網絡優化模型7.1圖論基本概念與最實際背景

例1（公路連接問題）某一地區有若干個主要城市，現準備修建高速公路把這些城市連接起來，使得從其中一個城市都可以經高速公路直接或間接到達另一個城市。假定已經知道了任意兩個城市之間修建高速公路的成本，那么如何決定在哪些城市間修建高速公路總成本最??？例2（最短路問題）一名貨車司機奉命在最短的時間內將一車貨物從甲地運往乙地。從甲地到乙地的公路網縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨車的運行速度是恒定的，那么這個問題相當于需要找到一條從甲地到乙地的最短路。例3（運輸問題）某種原材料有M個產地，現在需要將原材料從產地運往N個使用工廠。假定M個產地的產量和N個工廠的需求量已知，單位產品從任一產地到任一工廠的運費已知，那么，如何安排運輸方案可以使總運輸成本最低？實際背景例1（公路連接問題）某一地區有若干個主要城市，現準實際背景

例4（指派問題）一家公司經理準備安排n名員工去完成n項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的收益不同，如何分配工作方案使總回報最大？例5（中國郵遞員問題）一名郵遞員負責投遞某個街區的郵件。如何為他設計一條最短的投遞路線？即從郵局出發，經過投遞區內每條街道至少一次，最后返回郵局。例6（旅行商問題）一名推銷員準備前往若干城市推銷產品。如何為他設計一條最短的旅行路線？即從駐地出發，經過每個城市恰好一次，最后返回駐地。實際背景例4（指派問題）一家公司經理準備安排n名員工去完成實際背景

共同特點：（1）它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優安排或方案，數學上把這種問題稱為優化問題。（2）它們都易于用圖形的形式直觀的描述和表達，數學上把這種與圖相關的結構稱為網絡，與圖和網絡相關的優化問題稱為網絡優化。實際背景共同特點：哥尼斯堡七橋問題

在無孤立結點的圖G中,若存在一條回路,它經過圖中每條邊一次且僅一次,稱此回路為歐拉回路.無向圖G具有歐拉回路,當且僅當G是連通的,且所有結點的度都是偶數.哥尼斯堡七橋問題在無孤立結點的圖G中,若存在一條圖論基本概念與最小生成樹一、圖的概念1、圖的定義2、頂點的次數3、子圖二、圖的矩陣表示1、關聯矩陣2、鄰接矩陣三、最小生成樹圖論基本概念與最小生成樹一、圖的概念1、圖的定義2、定義有序二元組G=(V,E)稱為一個圖.[1]

是有窮非空集，稱為頂點集

其中的元素叫圖G的頂點。[2]

E稱為邊集，其中的元素稱為圖G的邊。

例設G=(V,E),其中G的圖解如圖定義有序二元組G=(V,E)稱為一個圖.[1]是有窮非空定義定義定義定義關聯矩陣注：假設圖為簡單圖關聯矩陣注：假設圖為簡單圖鄰接矩陣注：假設圖為簡單圖鄰接矩陣注：假設圖為簡單圖chap7圖論與網絡優化模型課件樹的等價定義⑴無回路的連通圖.⑵無回路且ε=v-1其中ε是T的邊數,v是T的結點數.⑶連通的且ε=v-1.⑷無回路但添加一條新邊則得到一條僅有的回路.⑸連通的,但刪去任一條邊,T便不連通.⑹每對結點之間有一條且僅有一條路.如果圖G的生成子圖是樹,則稱此樹為G的生成樹.樹的等價定義例：某地要建5個工廠，擬修筑道路連接這5處。經勘測其道路可依下圖的無向邊鋪設。為使這5處都有道路相通，問至少要鋪設幾條路？怎樣鋪設？例：某地要建5個工廠，擬修筑道路連接這5處。經勘測其道路可依最小生成樹（Kruskal（克魯斯克爾）算法）

設圖G有n個結點，以下算法產生的是最小生成樹1）選取最小權邊e1，置邊數i←1；2）i=n-1結束，否則轉入3）；3）設已選擇邊為e1,e2,…,ei,在G中選取不同于e1,e2,…,ei的邊ei+1，使{e1,e2,…,ei,ei+1}中無回路且ei+1是滿足此條件的最小邊；4）i←i＋1,轉入2）。注意：最小生成樹不唯一，但不同的最小生成樹的邊權之和是唯一的最小生成樹（Kruskal（克魯斯克爾）算法）注意：最小生成邊按升序排序:邊(vi,vj)記成eij邊權邊權e28e34e23e38e17e24e45e57e16e78e56e35e46e67e58e12e1811222333444566778v1v5v4v2v3v8v6v712213772486653443v1v5v4v2v3v8v6v71212433TOMATLAB(kruskal.m)驗證：P95例11邊按升序排序:邊(vi,vj)記成eij邊權邊權e28e3最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂點之間的最短路最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂基本概念基本概念chap7圖論與網絡優化模型課件固定起點的最短路最短路是一條路徑假設在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構成一棵以u0為根的樹．因此,可采用樹生長的過程來求指定頂點到其余頂點的最短路．固定起點的最短路最短路是一條路徑假設在u0-vchap7圖論與網絡優化模型課件算法步驟：算法步驟：TOMATLAB(dijkstra.m)TOMATLABchap7圖論與網絡優化模型課件u1u2u3u4u5u6u7u8驗證：P97例1u1u2u3u4u5u6u7u8驗證：P97例1每對頂點之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（二）算法原理（三）算法步驟每對頂點之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法算法的基本思想算法的基本思想算法原理——求距離矩陣的方法算法原理——求距離矩陣的方法算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R．即當vk被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求時求得，可由來查找任何點對之間最短路的路徑．算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑ij算法原理—查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j的最短路的路徑為：ij算法原理—查找最短路路徑的方法pkp2p1p3q1q2q算法步驟算法步驟例、求下圖任意兩點之間的最短路徑的長度例、求下圖任意兩點之間的最短路徑的長度TOMATLAB(road2(floyd))TOMATLAB可化為最短路問題的多階段決策問題最短路的應用可化為最短路問題的多階段決策問題最短路的應用chap7圖論與網絡優化模型課件

選址問題--中心問題TOMATLAB(road3(floyd))選址問題--中心問題TOMATLABS(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處。S(v1)=10,S(v2)=7,S(v3)=6,S(§7.3網絡流問題1、網絡流圖2、最大流問題及其解法3、最小費用問題及其解法§7.3網絡流問題1、網絡流圖問題1：7種設備要用5架飛機運往目的地，每種設備各有4臺，這5架飛機的容量分別為8，8，5，4，4臺，問能否有一種裝載法，使同一種類型的設備不會有兩臺在同一架飛機上。問題2：設有王二、張三、李四、趙五四人及小提琴、大提琴、鋼琴和吉他四種樂器，已知四人的特長如下：王二擅長拉大提琴和彈鋼琴；張三擅長拉小提琴、大提琴和吉他；李四擅長拉小提琴和大提琴；趙五只會彈吉他；今假設四人同臺演出，每人奏一種樂器，問四人同時各演奏一種樂器時所有可能的方案。問題1：7種設備要用5架飛機運往目的地，每種設備各有4臺，這網絡流圖是滿足下列條件的有向賦權圖（1）有一個發點和收點（2）每條邊都有一個容量（權）實際含義是發點可以看作運輸問題的起點，收點可以看作運輸問題的終點，邊可以看作運輸路線，權數可以看作該線路的運輸能力。設是定義在有向賦權圖邊集上的一個數值函數，滿足：（2）除過發點和起點外，（1）一、網絡流圖網絡流圖是滿足下列條件的有向賦權圖（1）有一個發點和收該定義的實際意義分別為：1、每條邊的實際流量不超過它的容量。2、流入和流出每個節點的流量相等。（物質不滅，無損耗）3、從發點流出的流量等于流入收點的流量。稱

3、該定義的實際意義分別為：3、二、最大流問題及其求解方法

（一）最大流問題最大流問題——設有向網絡N（V，A），在發點Vs

有一批貨，要通過網絡上的弧運輸到收點Vt去，受運輸條件限制，每條弧aij在單位時間內通過的車輛數不能超過cij

輛，分析：如何組織運輸才能使從Vs到Vt

在單位時間內通過的車輛達到最多？上面描述的這類問題，稱為最大流問題。最大流問題廣泛地應用在交通運輸、供水、油管供油、郵電通訊，也可以用在生產安排，管理優化等實際問題上。二、最大流問題及其求解方法（一）最大流問題最大流問題——最例：如圖1中，有一批物資需要用汽車盡快從發點①運到收點⑦，?。╥，j）上所標的數字表示該條道路在單位時間內最多能通過的車輛數（單位：百輛），問如何調運，才能使單位時間里有最多的車輛從①調到⑦。425136756385577113223圖1例：如圖1中，有一批物資需要用汽車盡快從發點①運到收點⑦，弧點①出發的車輛數應該與點⑦到達的車輛數相同，除①和⑦以外的各中間點，進的車輛數應該與離去的車輛數應該相同。xij

是通過弧(i，j)的車輛數。（1）（4）（5）（6）（2）（3）點①出發的車輛數應該與點⑦到達的車輛數相同，除①和⑦對所有?。╥，j），應滿足約束滿足（1）～（7）的解稱為從①到⑦的一個可行流，我們的目的：在所有可行流中求出一個方案，使得這個可行流得到的f最大。

若從收點到發點連接一條假想弧(7，1)，設它的容量c71=∞，那么對點①：對點⑦：

最大流問題的目標為（7）（8）（9）（10）對所有?。╥，j），應滿足約束（7）（8）（9）（1所以，對于發點為Vs，收點為Vt的網絡N（V，U），當增加一條約束為cts=∞的假想?。╰，s）后，最大流問題就成為：

容量約束：

平衡條件：

目標函數：（11）（12）（13）所以，對于發點為Vs，收點為Vt的網絡N（V，U），當增加一（二）求最大流的方法：弧標號法

盡管最大流問題可以用線性規劃模型描述，但是我們一般并不用求解線性規劃的方法求最大流，而是用一種更為簡便明了的圖上作業法——弧標號法，求解上述最大流問題。（二）求最大流的方法：弧標號法盡管最大流問題可以用①為了便于弧標號法的計算，首先需要將最大流問題（譬如圖1）重新改畫成為圖2的形式。2416357st650230081023730071000055圖2①為了便于弧標號法的計算，首先需要將最大流問題（譬如圖1）重在圖2中，每條弧上標有兩個數字，其中，靠近點i的是，靠近點j的是。如①②表示從①到②的最大通過量是5（百輛），從②到①的最大通過量是0；②③表示從②到③和從③到②都可以通過2（百輛）；等等。

2416357st650230081023730071000055圖2在圖2中，每條弧上標有兩個數字，其中，靠近點②

求最大流的基本步驟：

弧標號法求最大流的過程，就是對圖2反復地進行修改的過程，其計算步驟如下：

步驟1.從發點s到收點t選定一條路，使這條路通過的所有弧Vij的前面約束量cij都大于0，如果找不到這樣的路，說明已經求得最大流，轉步驟4。

步驟2.在選定的路上，找到最小的容許量cij定為P。

②求最大流的基本步驟：步驟3.對選定的路上每條弧的容量作以下修改，對于與路同向的弧，將cij修改為cij-P，對于與路反向的弧，將cij修改為cij+P。修改完畢后再轉入步驟1。步驟4.用原圖中各條弧上起點與終點數值減去修改后的圖中對應點的數值，得到正負號相反的兩個數，并將從正到負的方向用箭頭表示。這樣，就得到一個最大流量圖。

步驟3.對選定的路上每條弧的容量作以下修改，對于與路同向的下面，我們用弧標號法求解圖2中的最大流。

第一次修改：（1）從發點s到收點t找一條路，使得這條路上的所有弧前面的約束量。從圖2中可以看出，顯然，①—③—⑥—⑦就是滿足這樣的條件的一條路。

（2）在路①—③—⑥—⑦中,,,,所以取。下面，我們用弧標號法求解圖2中的最大流。第一次修改：（2）（3）在路①—③—⑥—⑦中，修改每一條弧的容量：（3）在路①—③—⑥—⑦中，修改每一條弧的容量：通過第1次修改，得到圖3。

2416357st050230081623130611600055圖3返回步驟（1），進行第2次修改。通過第1次修改，得到圖3。2416357st0502300

第二次修改：選定①—②—⑤—⑦，在這條路中，由于，所以，將改為2，改為0，改為5，、、改為3。修改后的圖變為圖4。

2416357st023203051623133611600055返回步驟（1），繼續做第3次修改。圖4第二次修改：2416357st02320305162第三次修改：取①—②—③—⑤—⑦，在這條，由于，所以將改為0，改為5，改為0，改為4，改為1，改為2，改為3，改為5。修改后的圖變為圖5。

2416357st005003231641135611600055圖5返回步驟（1），繼續做第4次修改。第三次修改：2416357st005003231641135

第四次修改：選定①—④—⑥—⑦，在這條路中，由于P=c67

=1，所以將c14改為4,c41改為1,c46改為4,c64改為1,c67改為0，c76改為7。修改后的圖為變為圖6。

2416357st005003231641135701611044圖6返回步驟（1），繼續做第5次修改。第四次修改：2416357st0050032316

第五次修改：選定①—④—⑥—⑤—⑦,在這條路中，由于P=c65

=1，所以將c14和c46均改為3，c65改為0，c57改為2，c41、c64、c56均改為2，c75改為6。修改后的圖變為圖7。

2416357st005003222641136500622033圖7第五次修改：2416357st00500322264需要注意的是，由圖7中可以看出，弧本來在圖2中是無容量可通過的，但經過幾次修改，由③⑥變成③⑥，即此時從③到⑥還可通過1（百輛），而從⑥到③，可以通過6（百輛）的容量，這說明，修改過程實際上是把計劃中從③到⑥的通過車輛數減少了。需要注意的是，由圖7中可以看出，弧本來在圖2取①—④—⑥—③—⑤—⑦，在這條路中，由于P=c35=1，所以將c14和c46均改為2，c63改為5,c35改為0，c57改為1，c41、c64、c53均改為3，c36改為2，c75改為7。修改后的圖變為圖8。

2416357st005003312640237500533022圖8?、佟堋蕖邸荨?，在這條路中，由于P=c35=1，所在圖8中，從發點①到收點⑦，再也不存在連通的起點容量都大于零的弧了，所以圖8為最大流圖。

轉入步驟（4），用原圖中各條弧上起點與終點數值減去修改后的圖上各點的數值，將得到正負號相反的兩個數，將這個數標在弧上，并將從正到負的方向用箭頭表示,這樣就得到最大流量圖。例如原來弧是③⑥，現在是③⑥，相減為±5，③那邊為正，我們就記作③⑥。這樣，就得到圖9，即最大流量。依這樣的調度方式，可以從發點s調運14（百輛）汽車到收點t。

(3,6)在圖8中，從發點①到收點⑦，再也不存在連通的起點容量6373371035542513672圖9最大流量圖

6373371035542513672圖9最大流量圖圖10最大流fmax的大小是確定的，但最大流的路線可以不唯一。在上例中，如果從不同的路開始來修改圖，也可能得到另外一個最大流圖（圖10）。

2416357563233177235注意驗證：P104例2圖10最大流fmax的大小是確定的，但最大流的路線可以不唯一應用舉例

一制造商需要把兩個車間D1,D2生產的同類商品通過運輸網絡送到三個銷售點M1,M2,M3去，如圖所示。設各銷售點計劃銷售量分別為10,8,8，問網絡的運輸能力能否滿足這一要求？兩個車間生產數量多少最為恰當？應用舉例三、最小費用流及其求解方法

（補充）（一）最小費用流問題如果在考慮網絡上流量的同時，還要使得所安排流量的費用或者代價達到最小，就是所謂的最小費用流問題。

在上例中，如果單位車輛數通過某一條弧要付出一定的代價，其代價如圖11。

三、最小費用流及其求解方法（補充）（一）最小費用流問題425136743313324223222圖11代價條件

425136756385577113223圖1約束條件

425136743313324223222圖11代價條件現在要從發點①調動若干車輛到收點⑦去，約束條件為圖1，代價條件為圖11，要使所花費的代價達到最小，用式子表示，就是要在（1）～（7）式的約束條件下，找到一個可行流f的流量（15）

使其代價最小，即

（16）

式中：指單位車輛數通過弧的代價。

現在要從發點①調動若干車輛到收點⑦去，約束條件為圖1（二）求解最小流問題求最小費用流的步驟和求最大流的步驟幾乎完全一致，只是在步驟（1）中，選代價和最小的路，即最短路。具體算法如下：①求發點s到收點t的最小費用通路P(s,t)，記該通路的邊集合為E(P);②給P(s,t)分配最大可能流量f0=min{c(x,y)|(x,y)∈E(P)},對所有的(x,y)∈E(P),令c(x,y)=c(x,y)-f0;對E(P)飽和邊，將單位費用改為∞，且當x或y≠s或t時，將飽和邊(x,y)變為反向邊(y,x),令c(y,x)=f0,w(y,x)=-w(x,y)構成新網絡。

③在新網絡中重復①②，直至從發點到收點的流值等于最大流或再找不到最小費用通路（二）求解最小流問題求最小費用流的步驟和求最大例：求下圖網絡中的最小費用流，圖中每邊上的第一個數字是容量c(i,j)=cij,第二個數字是單位費用w(i,j)解：（1）求s到t的最小費用通路sbat，單位費用和為4，最大流為11，邊ba飽和。例：求下圖網絡中的最小費用流，圖中每邊上的第一個數字是容量c（2）在新的網絡中求s到t的最小費用通路sat，單位費用和為5，最大流為3，邊at飽和。（3）在新的網絡中求s到t的最小費用通路sbct，單位費用和為6，最大流為5，邊sb飽和。（2）在新的網絡中求s到t的最小費用通路sat，單位費用和為（4）在新的網絡中求s到t的最小費用通路sabct，單位費用和為7，最大流為3，邊ct飽和。于是，圖中的流分布為最小費用為：4×11＋5×3＋6×5＋7×3＝110（4）在新的網絡中求s到t的最小費用通路sabct，單位費用42513675,46,33,38,15,35,37,27,41,21,23,32,22,23,242513675,46,33,38,15,35,37,27,表1最小費用流的求解過程

將各條路的流量相加，就得到最小費用流，如圖12所示。

表1最小費用流的求解過程將各條路的流量相加，就得到最小費用2416357365303351770圖12最小費用流

這個最小費用流的總代價為：

2416357365303351770圖12最小費用流小結重點：1、最短路問題結果分析；2、最小費用最大流算法；小結重點：第七章圖論與網絡優化模型

7.1圖論基本概念與最小生成樹7.2最短路問題7.3網絡最大流7.4二分圖與鎖具裝箱問題y第七章圖論與網絡優化模型7.1圖論基本概念與最實際背景

例1（公路連接問題）某一地區有若干個主要城市，現準備修建高速公路把這些城市連接起來，使得從其中一個城市都可以經高速公路直接或間接到達另一個城市。假定已經知道了任意兩個城市之間修建高速公路的成本，那么如何決定在哪些城市間修建高速公路總成本最??？例2（最短路問題）一名貨車司機奉命在最短的時間內將一車貨物從甲地運往乙地。從甲地到乙地的公路網縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨車的運行速度是恒定的，那么這個問題相當于需要找到一條從甲地到乙地的最短路。例3（運輸問題）某種原材料有M個產地，現在需要將原材料從產地運往N個使用工廠。假定M個產地的產量和N個工廠的需求量已知，單位產品從任一產地到任一工廠的運費已知，那么，如何安排運輸方案可以使總運輸成本最低？實際背景例1（公路連接問題）某一地區有若干個主要城市，現準實際背景

例4（指派問題）一家公司經理準備安排n名員工去完成n項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的收益不同，如何分配工作方案使總回報最大？例5（中國郵遞員問題）一名郵遞員負責投遞某個街區的郵件。如何為他設計一條最短的投遞路線？即從郵局出發，經過投遞區內每條街道至少一次，最后返回郵局。例6（旅行商問題）一名推銷員準備前往若干城市推銷產品。如何為他設計一條最短的旅行路線？即從駐地出發，經過每個城市恰好一次，最后返回駐地。實際背景例4（指派問題）一家公司經理準備安排n名員工去完成實際背景

共同特點：（1）它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優安排或方案，數學上把這種問題稱為優化問題。（2）它們都易于用圖形的形式直觀的描述和表達，數學上把這種與圖相關的結構稱為網絡，與圖和網絡相關的優化問題稱為網絡優化。實際背景共同特點：哥尼斯堡七橋問題

在無孤立結點的圖G中,若存在一條回路,它經過圖中每條邊一次且僅一次,稱此回路為歐拉回路.無向圖G具有歐拉回路,當且僅當G是連通的,且所有結點的度都是偶數.哥尼斯堡七橋問題在無孤立結點的圖G中,若存在一條圖論基本概念與最小生成樹一、圖的概念1、圖的定義2、頂點的次數3、子圖二、圖的矩陣表示1、關聯矩陣2、鄰接矩陣三、最小生成樹圖論基本概念與最小生成樹一、圖的概念1、圖的定義2、定義有序二元組G=(V,E)稱為一個圖.[1]

是有窮非空集，稱為頂點集

其中的元素叫圖G的頂點。[2]

E稱為邊集，其中的元素稱為圖G的邊。

例設G=(V,E),其中G的圖解如圖定義有序二元組G=(V,E)稱為一個圖.[1]是有窮非空定義定義定義定義關聯矩陣注：假設圖為簡單圖關聯矩陣注：假設圖為簡單圖鄰接矩陣注：假設圖為簡單圖鄰接矩陣注：假設圖為簡單圖chap7圖論與網絡優化模型課件樹的等價定義⑴無回路的連通圖.⑵無回路且ε=v-1其中ε是T的邊數,v是T的結點數.⑶連通的且ε=v-1.⑷無回路但添加一條新邊則得到一條僅有的回路.⑸連通的,但刪去任一條邊,T便不連通.⑹每對結點之間有一條且僅有一條路.如果圖G的生成子圖是樹,則稱此樹為G的生成樹.樹的等價定義例：某地要建5個工廠，擬修筑道路連接這5處。經勘測其道路可依下圖的無向邊鋪設。為使這5處都有道路相通，問至少要鋪設幾條路？怎樣鋪設？例：某地要建5個工廠，擬修筑道路連接這5處。經勘測其道路可依最小生成樹（Kruskal（克魯斯克爾）算法）

設圖G有n個結點，以下算法產生的是最小生成樹1）選取最小權邊e1，置邊數i←1；2）i=n-1結束，否則轉入3）；3）設已選擇邊為e1,e2,…,ei,在G中選取不同于e1,e2,…,ei的邊ei+1，使{e1,e2,…,ei,ei+1}中無回路且ei+1是滿足此條件的最小邊；4）i←i＋1,轉入2）。注意：最小生成樹不唯一，但不同的最小生成樹的邊權之和是唯一的最小生成樹（Kruskal（克魯斯克爾）算法）注意：最小生成邊按升序排序:邊(vi,vj)記成eij邊權邊權e28e34e23e38e17e24e45e57e16e78e56e35e46e67e58e12e1811222333444566778v1v5v4v2v3v8v6v712213772486653443v1v5v4v2v3v8v6v71212433TOMATLAB(kruskal.m)驗證：P95例11邊按升序排序:邊(vi,vj)記成eij邊權邊權e28e3最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂點之間的最短路最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂基本概念基本概念chap7圖論與網絡優化模型課件固定起點的最短路最短路是一條路徑假設在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構成一棵以u0為根的樹．因此,可采用樹生長的過程來求指定頂點到其余頂點的最短路．固定起點的最短路最短路是一條路徑假設在u0-vchap7圖論與網絡優化模型課件算法步驟：算法步驟：TOMATLAB(dijkstra.m)TOMATLABchap7圖論與網絡優化模型課件u1u2u3u4u5u6u7u8驗證：P97例1u1u2u3u4u5u6u7u8驗證：P97例1每對頂點之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（二）算法原理（三）算法步驟每對頂點之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法算法的基本思想算法的基本思想算法原理——求距離矩陣的方法算法原理——求距離矩陣的方法算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R．即當vk被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求時求得，可由來查找任何點對之間最短路的路徑．算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑ij算法原理—查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j的最短路的路徑為：ij算法原理—查找最短路路徑的方法pkp2p1p3q1q2q算法步驟算法步驟例、求下圖任意兩點之間的最短路徑的長度例、求下圖任意兩點之間的最短路徑的長度TOMATLAB(road2(floyd))TOMATLAB可化為最短路問題的多階段決策問題最短路的應用可化為最短路問題的多階段決策問題最短路的應用chap7圖論與網絡優化模型課件

選址問題--中心問題TOMATLAB(road3(floyd))選址問題--中心問題TOMATLABS(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處。S(v1)=10,S(v2)=7,S(v3)=6,S(§7.3網絡流問題1、網絡流圖2、最大流問題及其解法3、最小費用問題及其解法§7.3網絡流問題1、網絡流圖問題1：7種設備要用5架飛機運往目的地，每種設備各有4臺，這5架飛機的容量分別為8，8，5，4，4臺，問能否有一種裝載法，使同一種類型的設備不會有兩臺在同一架飛機上。問題2：設有王二、張三、李四、趙五四人及小提琴、大提琴、鋼琴和吉他四種樂器，已知四人的特長如下：王二擅長拉大提琴和彈鋼琴；張三擅長拉小提琴、大提琴和吉他；李四擅長拉小提琴和大提琴；趙五只會彈吉他；今假設四人同臺演出，每人奏一種樂器，問四人同時各演奏一種樂器時所有可能的方案。問題1：7種設備要用5架飛機運往目的地，每種設備各有4臺，這網絡流圖是滿足下列條件的有向賦權圖（1）有一個發點和收點（2）每條邊都有一個容量（權）實際含義是發點可以看作運輸問題的起點，收點可以看作運輸問題的終點，邊可以看作運輸路線，權數可以看作該線路的運輸能力。設是定義在有向賦權圖邊集上的一個數值函數，滿足：（2）除過發點和起點外，（1）一、網絡流圖網絡流圖是滿足下列條件的有向賦權圖（1）有一個發點和收該定義的實際意義分別為：1、每條邊的實際流量不超過它的容量。2、流入和流出每個節點的流量相等。（物質不滅，無損耗）3、從發點流出的流量等于流入收點的流量。稱

3、該定義的實際意義分別為：3、二、最大流問題及其求解方法

（一）最大流問題最大流問題——設有向網絡N（V，A），在發點Vs

有一批貨，要通過網絡上的弧運輸到收點Vt去，受運輸條件限制，每條弧aij在單位時間內通過的車輛數不能超過cij

輛，分析：如何組織運輸才能使從Vs到Vt

在單位時間內通過的車輛達到最多？上面描述的這類問題，稱為最大流問題。最大流問題廣泛地應用在交通運輸、供水、油管供油、郵電通訊，也可以用在生產安排，管理優化等實際問題上。二、最大流問題及其求解方法（一）最大流問題最大流問題——最例：如圖1中，有一批物資需要用汽車盡快從發點①運到收點⑦，?。╥，j）上所標的數字表示該條道路在單位時間內最多能通過的車輛數（單位：百輛），問如何調運，才能使單位時間里有最多的車輛從①調到⑦。425136756385577113223圖1例：如圖1中，有一批物資需要用汽車盡快從發點①運到收點⑦，弧點①出發的車輛數應該與點⑦到達的車輛數相同，除①和⑦以外的各中間點，進的車輛數應該與離去的車輛數應該相同。xij

是通過弧(i，j)的車輛數。（1）（4）（5）（6）（2）（3）點①出發的車輛數應該與點⑦到達的車輛數相同，除①和⑦對所有?。╥，j），應滿足約束滿足（1）～（7）的解稱為從①到⑦的一個可行流，我們的目的：在所有可行流中求出一個方案，使得這個可行流得到的f最大。

若從收點到發點連接一條假想弧(7，1)，設它的容量c71=∞，那么對點①：對點⑦：

最大流問題的目標為（7）（8）（9）（10）對所有弧（i，j），應滿足約束（7）（8）（9）（1所以，對于發點為Vs，收點為Vt的網絡N（V，U），當增加一條約束為cts=∞的假想?。╰，s）后，最大流問題就成為：

容量約束：

平衡條件：

目標函數：（11）（12）（13）所以，對于發點為Vs，收點為Vt的網絡N（V，U），當增加一（二）求最大流的方法：弧標號法

盡管最大流問題可以用線性規劃模型描述，但是我們一般并不用求解線性規劃的方法求最大流，而是用一種更為簡便明了的圖上作業法——弧標號法，求解上述最大流問題。（二）求最大流的方法：弧標號法盡管最大流問題可以用①為了便于弧標號法的計算，首先需要將最大流問題（譬如圖1）重新改畫成為圖2的形式。2416357st650230081023730071000055圖2①為了便于弧標號法的計算，首先需要將最大流問題（譬如圖1）重在圖2中，每條弧上標有兩個數字，其中，靠近點i的是，靠近點j的是。如①②表示從①到②的最大通過量是5（百輛），從②到①的最大通過量是0；②③表示從②到③和從③到②都可以通過2（百輛）；等等。

2416357st650230081023730071000055圖2在圖2中，每條弧上標有兩個數字，其中，靠近點②

求最大流的基本步驟：

弧標號法求最大流的過程，就是對圖2反復地進行修改的過程，其計算步驟如下：

步驟1.從發點s到收點t選定一條路，使這條路通過的所有弧Vij的前面約束量cij都大于0，如果找不到這樣的路，說明已經求得最大流，轉步驟4。

步驟2.在選定的路上，找到最小的容許量cij定為P。

②求最大流的基本步驟：步驟3.對選定的路上每條弧的容量作以下修改，對于與路同向的弧，將cij修改為cij-P，對于與路反向的弧，將cij修改為cij+P。修改完畢后再轉入步驟1。步驟4.用原圖中各條弧上起點與終點數值減去修改后的圖中對應點的數值，得到正負號相反的兩個數，并將從正到負的方向用箭頭表示。這樣，就得到一個最大流量圖。

步驟3.對選定的路上每條弧的容量作以下修改，對于與路同向的下面，我們用弧標號法求解圖2中的最大流。

第一次修改：（1）從發點s到收點t找一條路，使得這條路上的所有弧前面的約束量。從圖2中可以看出，顯然，①—③—⑥—⑦就是滿足這樣的條件的一條路。

（2）在路①—③—⑥—⑦中,,,,所以取。下面，我們用弧標號法求解圖2中的最大流。第一次修改：（2）（3）在路①—③—⑥—⑦中，修改每一條弧的容量：（3）在路①—③—⑥—⑦中，修改每一條弧的容量：通過第1次修改，得到圖3。

2416357st050230081623130611600055圖3返回步驟（1），進行第2次修改。通過第1次修改，得到圖3。2416357st0502300

第二次修改：選定①—②—⑤—⑦，在這條路中，由于，所以，將改為2，改為0，改為5，、、改為3。修改后的圖變為圖4。

2416357st023203051623133611600055返回步驟（1），繼續做第3次修改。圖4第二次修改：2416357st02320305162第三次修改：取①—②—③—⑤—⑦，在這條，由于，所以將改為0，改為5，改為0，改為4，改為1，改為2，改為3，改為5。修改后的圖變為圖5。

2416357st005003231641135611600055圖5返回步驟（1），繼續做第4次修改。第三次修改：2416357st005003231641135

第四次修改：選定①—④—⑥—⑦，在這條路中，由于P=c67

=1，所以將c14改為4,c41改為1,c46改為4,c64改為1,c67改為0，c76改為7。修改后的圖為變為圖6。

2416357st005003231641135701611044圖6返回步驟（1），繼續做第5次修改。第四次修改：2416357st0050032316

第五次修改：選定①—④—⑥—⑤—⑦,在這條路中，由于P=c65

=1，所以將c14和c46均改為3，c65改為0，c57改為2，c41、c64、c56均改為2，c75改為6。修改后的圖變為圖7。

2416357st005003222641136500622033圖7第五次修改：2416357st00500322264需要注意的是，由圖7中可以看出，弧本來在圖2中是無容量可通過的，但經過幾次修改，由③⑥變成③⑥，即此時從③到⑥還可通過1（百輛），而從⑥到③，可以通過6（百輛）的容量，這說明，修改過程實際上是把計劃中從③到⑥的通過車輛數減少了。需要注意的是，由圖7中可以看出，弧本來在圖2取①—④—⑥—③—⑤—⑦，在這條路中，由于P=c35=1，所以將c14和c46均改為2，c63改為5,c35改為0，c57改為1，c41、c64、c53均改為3，c36改為2，c75改為7。修改后的圖變為圖8。

2416357st005003312640237500533022圖8?、佟堋蕖邸荨?，在這條路中，由于P=c35=1，所在圖8中，從發點①到收點⑦，再也不存在連通的起點容量都大于零的弧了，所以圖8為最大流圖。

轉入步驟（4），用原圖中各條弧上起點與終點數值減去修改后的圖上各點的數值，將得到正負號相反的兩個數，將這個數標在弧上，并將從正到負的方向用箭頭表示,這樣就得到最大流量圖。例如原來弧是③⑥，現在是③⑥，相減為±5，③那邊為正，我們就記作③