分解第六章運籌學(xué)圖與網(wǎng)絡(luò)優(yōu)化

1、分解第六章運籌學(xué)圖與網(wǎng)絡(luò)優(yōu)化第六章-運籌學(xué)圖與網(wǎng)絡(luò)優(yōu)化第六章 圖與網(wǎng)絡(luò)優(yōu)化第1節(jié) 圖的基本概念第2節(jié) 樹第3節(jié) 最短路問題第4節(jié) 網(wǎng)絡(luò)最大流問題第1節(jié) 圖的基本概念例1：我國北京、上海等十個城市間的鐵路交通圖如下圖所示：北京徐州青島天津濟南武漢南京上海連云港鄭州第1節(jié) 圖的基本概念例2：有甲、乙、丙、丁、戊五個球隊，他們之間的比賽情況如下圖所示：v甲v乙v丙v丁v戊第1節(jié) 圖的基本概念一、圖的基本概念o圖：由一些點及一些點之間的連線組成。o邊：兩點之間不帶箭頭的連線。o?。簝牲c之間帶箭頭的連線。o無向圖：由點及邊組成。o有向圖：由點及弧組成。第1節(jié) 圖的基本概念圖例：v2v1e3e2e1v2a

2、1a2a3v3v1第1節(jié) 圖的基本概念二、無向圖的基本概念o端點：兩個點vi，vj屬于V，邊vi，vj屬于E，稱vi，vj是邊的端點。o關(guān)連邊：邊vi，vj是點vi及點vj的關(guān)連邊。o環(huán)：邊的兩個端點相同。o多重邊：兩個點之間多于一條的邊。o簡單圖：不含環(huán)和多重邊的無向圖。o多重圖：不含環(huán)，但含有多重邊的無向圖。第1節(jié) 圖的基本概念次：以點vi為端點的邊的個數(shù)。懸掛點：次為1的點。懸掛邊：連結(jié)懸掛點的邊。奇點：次為奇數(shù)的點。偶點：次為偶數(shù)的點。孤立點：次為零的點。第1節(jié) 圖的基本概念圖例：v2e1v4v3v1e2v2v1e3e2e1第1節(jié) 圖的基本概念三、無向圖的基本性質(zhì)o任何無向圖中，頂點次

3、數(shù)的總和等于邊數(shù)的2倍。o任何無向圖中，次為奇數(shù)的頂點必為偶數(shù)個。第1節(jié) 圖的基本概念四、有向圖的基本概念o基礎(chǔ)圖：去掉有向圖中所有弧上的箭頭得到的無向圖。o始點、終點：弧(vi，vj)中，稱vi為弧的始點，vj為弧的終點。第1節(jié) 圖的基本概念五、圖的綜合概念（一）無向圖o鏈：o圈：11221111(),(121)KKKtttkiiiiiiiiiiiiGvevevevev vtkvv無向圖 中一個點、邊交錯序列， ， ， ， ,，若滿足， ， ，稱這個點邊序列為連接 ， 的鏈。11kkiiiiGvvvv無向圖 中，連結(jié) 與的一條鏈，當(dāng) 與是同一個點時，稱此鏈為圈。第1節(jié) 圖的基本概念初等鏈：鏈

4、中沒有重復(fù)的點。初等圈：圈中沒有重復(fù)的點。簡單鏈：鏈中沒有重復(fù)的邊。簡單圈：圈中沒有重復(fù)的邊。第1節(jié) 圖的基本概念圖例：問：（v1，v2， v3， v4， v5， v3， v6， v7）？（v1， v2， v3， v6， v7）？（v1， v2， v3， v4， v1）？（v4， v1， v2， v3， v5， v7， v6， v3， v4）？（v1， v2， v3， v5， v4， v3， v4， v1）？v2e1v4v3v1e2v5v6v7e3e4e5e6e7e8e9第1節(jié) 圖的基本概念（二）有向圖o鏈：o路：11221111()121KKKtttkiiiiiiiiiiiiDvavavav

5、avvtkvv有向圖 中一條鏈， ， ， ,，若滿足=( ，)(， ， ，)，則稱這個點弧序列為從 到 的一條路。112211()KKKiiiiiiiDvavavavG DD有向圖 中一個點、弧交錯序列， ， ， ,，若此序列在基礎(chǔ)圖 ( )中所對應(yīng)的點邊序列是一條鏈，則稱這個點弧序列是 的鏈。第1節(jié) 圖的基本概念回路：初等路：路中沒有重復(fù)的點。初等回路：回路中沒有重復(fù)的點。第1節(jié) 圖的基本概念圖例：問： （v3，a3， v2， a5， v4， a6， v5， a8， v3）？（v1， a2， v3， a4， v4，a7， v6）？（v1， a2， v3， a8， v5，a10， v6）？（v

6、1，a2， v3， a4， v4， a6， v5， a8， v3）？v2a1v4v3v1a2v5v6v7a6a5a4a3a10a9a8a7a11第2節(jié) 樹一、樹的概念o連通圖：無向圖中任意兩點間至少有一條鏈相連。（不連通圖）o連通分圖：不連通圖中每個連通的部分。o樹：連通且不含圈的無向圖。第2節(jié) 樹二、樹的性質(zhì)o任何樹中必然存在次為1的點。（1）樹中次為1的點稱為樹葉（2）樹中次大于1的點稱為分枝點o樹的點有n個，則該樹的邊必有（n-1）條。o任何具有n個點、（n-1）條邊的連通圖必是樹。o樹中任意兩點之間有且只有唯一一條鏈。o從一個樹中去掉任一條邊，則余下的圖必是不連通圖。o在樹中不相鄰的兩

7、個點之間添上一條邊，則必得到一個圈；反之再從該圈中任意去掉一條邊，則必得到一個樹。第2節(jié) 樹圖例：v2v4v1v3v5第2節(jié) 樹三、支撐樹o支撐子圖：o支撐樹：如果圖G的支撐子圖是一個樹T，則稱樹T是圖G的一個支撐樹。o支撐樹的性質(zhì)：圖G有支撐樹的充分必要條件是圖G是連通圖。第2節(jié) 樹圖例：v2v4v1v3v5v2v4v1v3v5第2節(jié) 樹四、最小支撐樹o賦權(quán)圖：o最小支撐樹：()ijijijijGVEGvvwGwvv圖，對 中每一條邊 ， ，相應(yīng)地有一個數(shù)，則稱圖 為賦權(quán)圖，稱為邊 ， 上的權(quán)，表示距離、時間、費用等。( )( )()ijijvvTTGTTw Tw TwTw TGTG，設(shè) 是

8、 的一個支撐樹，稱 中所有邊的權(quán)之和為支撐樹 的權(quán)，記為，即。如果支撐樹的權(quán)是 所有支撐樹的權(quán)中最小的，則稱為 的最小支撐樹。第2節(jié) 樹最小支撐樹的求解方法方法一：避圈法基本做法：首先選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈（每一步中，如果有兩條或兩條以上最小權(quán)的邊，則任選一條）。第2節(jié) 樹例3：某工廠內(nèi)聯(lián)結(jié)六個車間的道路網(wǎng)如下圖所示。已知每條道路的長，要求沿道路架設(shè)聯(lián)結(jié)六個車間的 線網(wǎng)，使 線的總長最小。v3v2v4v1v5v6615572344第2節(jié) 樹方法二：破圈法基本做法：任取一個圈，從圈中去掉一條權(quán)最大的邊，（如果有兩條或兩條以上

9、最大權(quán)的邊，則任去一條），在余下圖中重復(fù)這個步驟，一直到得到一個不含圈的圖為止。習(xí)題6-1習(xí)題6-1：分別用避圈法和破圈法求下述圖的最小支撐樹。1、 2、2314974363231457435741第3節(jié) 最短路問題一、最短路的含義第3節(jié) 最短路問題例4：某單行線交通網(wǎng)如下圖所示，每弧旁的數(shù)字表示通過這條單行線所需要的費用?，F(xiàn)在某人要從v1出發(fā)，通過這個交通網(wǎng)到v8去，求使總費用最小的旅行路線。v41v6v2v16v5v74106v3310124v8v9322263第3節(jié) 最短路問題二、最短路問題的求解方法（一）Dijkstra方法o適用條件：無負權(quán)（ij0）的最短路問題o基本思路：第3節(jié) 最

10、短路問題基本解法：標號采用兩種標號：T(Temporary)標號和P(Permanent)標號，T標號為臨時標號，P標號為固定標號。給vi點一個P標號時，表示從vs到vi的最短路權(quán)，vi點的標號不再改變；給vi點一個T標號時，表示從vs到vi的最短路權(quán)的上界，凡沒有得到P標號的點都有T標號。方法的每一步就是把某一點的T標號改為P標號，當(dāng)終點vt點得到P標號時，計算結(jié)束。第3節(jié) 最短路問題具體步驟：第一，給vs標上P標號P(vs)=0，其余各點為T標號，T(vj)=+。第二，若vi是剛標上P標號的點，選取所有與vi有關(guān)聯(lián)的弧( vi，vj )中的vj點，且vj點為T標號，去修改vj點的T標號：

11、。第三，比較所有具有T標號的點，把最小的T標號值所對應(yīng)的點改為P標號，即 （如果存在兩個或兩個以上的最小T標號，則同時改為P標號），若所有點都獲得P標號，停止計算（除去從vs到vj之間無路可走，即T(vj)=+=P(vj)）；否則轉(zhuǎn)入第二。第3節(jié) 最短路問題例5：用Dijkstra方法求解下圖中從v1到v8的最短路。v4v6v2v1v5v7v3v84677956444155習(xí)題6-2習(xí)題6-2：用Dijkstra方法求解下列各圖從v1到v7的最短路。1、v3v45v6v2v14v5v71487561246習(xí)題6-22、v3v4v6v2v1v5v759118751225612第3節(jié) 最短路問題（

12、二）賦權(quán)無向圖的最短路問題的求解方法賦權(quán)無向圖G=(V，E)，邊vi，vj表示既可以從vi到達vj，也可以從vj到達vi，所以邊vi，vj可以看作是兩條弧(vi，vj)和(vj，vi)，且它們具有相同的權(quán)ij。第3節(jié) 最短路問題例6：計算下圖所示賦權(quán)無向圖中v1到v7的最短路 。v3v45v6v2v14v5v71487561256第3節(jié) 最短路問題小結(jié)對于賦權(quán)無向圖G=(V，E)，從始點vs到各個點的最短路，即為最短鏈Dijkstra方法不僅適用于賦權(quán)有向圖D，也適用于賦權(quán)無向圖GDijkstra方法直接給出某點（設(shè)為vs）到其他所有點的最短路；不能直接給出賦權(quán)圖上任意兩點間的最短路Dijks

13、tra方法只適用于全部權(quán)為非負情況，如果某權(quán)為負，則算法失效。第3節(jié) 最短路問題例7：求下圖中從vs到v1的最短路。vsv1v285-5習(xí)題6-3習(xí)題6-3：用Dijkstra方法求解下圖從v1到v9的最短路。v1v3v4v7v2v5v8v93424116562784v653第3節(jié) 最短路問題三、最短路問題的應(yīng)用o設(shè)備更新問題第3節(jié) 最短路問題例10：某工廠使用一臺設(shè)備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付維修費；若購買一臺新設(shè)備，要付購買費。試制定一個5年的更新計劃，使總支出最少。已知設(shè)備在各年的購買費，及不同機器役齡時的維修費如下表所示：項目第1年 第2年 第3年 第4年 第5

14、年購買費 11 11 12 12 13機器役齡 0-1 1-2 2-3 3-4 4-5維修費 5 6 8 11 18第3節(jié) 最短路問題例10：解：轉(zhuǎn)化為最短路問題o點vi表示第i年年初購進一臺新設(shè)備o?。╲i，vj）表示第i年年初購進的設(shè)備一直使用到第j年年初o權(quán)ij表示第i年年初購進設(shè)備，一直使用到第j年年初所需支付的購買、維修的全部費用第3節(jié) 最短路問題最短路問題圖示：1641302218171617413022592331v1v2v3v4v5v623第4節(jié) 網(wǎng)絡(luò)最大流問題例11：已知聯(lián)結(jié)某產(chǎn)品產(chǎn)地v1和銷地v6的交通網(wǎng)，如下圖所示。每一弧(vi，vj)代表從vi到vj的運輸線，產(chǎn)品經(jīng)過這

15、條弧由vi輸送到vj，弧旁的數(shù)字表示這條運輸線的最大通過能力。產(chǎn)品經(jīng)過交通網(wǎng)從v1輸送到v6。要求制定一個運輸方案，使從v1運輸?shù)絭6的產(chǎn)品數(shù)量最多。v38v5v2v110v4v63654113517第4節(jié) 網(wǎng)絡(luò)最大流問題一、基本概念和性質(zhì)o發(fā)點、收點、中間點、容量、網(wǎng)絡(luò)：有向圖D=(V，A)，D的每條弧(vi，vj)上有非負數(shù)cij稱為弧的容量，在V中指定一點稱為發(fā)點（記為vs），另一點稱為收點（記為vt），其余點稱為中間點，這樣的D稱為一個網(wǎng)絡(luò)，記作D=(V，A，C)。o流、流量：定義在網(wǎng)絡(luò)D中的弧集合A上的一個函數(shù)f=fij稱為流，稱fij為弧(vi，vj)上的流量。流的性質(zhì)：每個弧上的

16、流量不超過該弧的容量。中間點的凈輸出量為零。第4節(jié) 網(wǎng)絡(luò)最大流問題可行流：滿足下述條件的流f稱為可行流，記作v(f)。（1）容量限制條件：對網(wǎng)絡(luò)D中每條弧(vi，vj)，有0fijcij（2）平衡條件：中間點每條弧vi：流出量與流入量相等發(fā)點vs、收點vt：從點vs流出的量等于點vt流入的量可行流的性質(zhì)：可行流總是存在的。零流：網(wǎng)絡(luò)D中所有弧的流量fij=0的可行流。第4節(jié) 網(wǎng)絡(luò)最大流問題v38v5v2v110v4v63654113517v3v5v2v1v4v6第4節(jié) 網(wǎng)絡(luò)最大流問題最大流問題：在網(wǎng)絡(luò)D中，求流量最大的可行流，記作v(f)。飽和弧、非飽和弧、零流弧、非零流弧：（1）飽和?。壕W(wǎng)絡(luò)

17、D中fij=cij的?。?）非飽和弧：網(wǎng)絡(luò)D中fijcij的?。?）零流?。壕W(wǎng)絡(luò)D中fij=0的弧（4）非零流?。壕W(wǎng)絡(luò)D中fij0的弧第4節(jié) 網(wǎng)絡(luò)最大流問題鏈：網(wǎng)絡(luò)D中聯(lián)結(jié)發(fā)點vs和收點vt的一條鏈，定義鏈的方向是從vs到vt。（1）前向弧+：弧的方向與鏈的方向一致（2）后向弧-：弧的方向與鏈的方向相反增廣鏈：f是一個可行流，是從vs到vt的一條鏈，若滿足則稱為從vs到vt關(guān)于f的增廣鏈。增廣鏈的實際意義：沿著鏈從vs到vt輸送的流還有潛力可挖，即可以把流量提高。定理：可行流f是最大流的充分必要條件是不存在從vs到vt關(guān)于f的增廣鏈。第4節(jié) 網(wǎng)絡(luò)最大流問題根據(jù)例11所描述的問題：找出鏈（v1，

18、v2，v3，v4，v5，v6）的前向弧和后向弧。v38v5v2v110v4v63654113517第4節(jié) 網(wǎng)絡(luò)最大流問題根據(jù)例11所描述的問題：給出一個運輸方案，如下圖所示。試說明鏈（v1，v2，v3，v4，v5，v6）是否為增廣鏈？v3v5v2v1v4v61054317第4節(jié) 網(wǎng)絡(luò)最大流問題二、求解方法標號法o解題過程：從一個可行流f出發(fā)，（1）標號過程：通過標號尋找增廣鏈（2）調(diào)整過程：沿增廣鏈調(diào)整f以增加流量o基本解法：標號點：用vj（，）表示表示vj點標號是從哪一點得到的，用vi表示表示vj點與之間的關(guān)系，用+或-表示第4節(jié) 網(wǎng)絡(luò)最大流問題具體步驟（一）標號過程第一，給vs標上（0，+），則vs是標號未檢查點，其余各點都是未標號點。第二，取標號未檢查點vi，對所有未標號點vj有：1）若在?。╲i，vj）上，fijcij，則給vj標上（vi，+）；2）若在弧（vk，vi）上，fki0，則給vk標上（vi，-）。則vj（vk）成為標號未檢查點，而vi成為標號已檢查點，在vi標號下面劃一橫線重復(fù)1）2），直至vt被標上號，則得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整過程。第三，若所有標號都已檢查過，而標號過程進行不下去時，則停止計算，此時獲得的可行流為最大流f 。第4節(jié) 網(wǎng)絡(luò)最大流問題（二）調(diào)整過程第一，按照vt及其它各點標號的第一個部