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

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

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

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

4、中沒(méi)有重復(fù)的點(diǎn)。初等圈：圈中沒(méi)有重復(fù)的點(diǎn)。簡(jiǎn)單鏈：鏈中沒(méi)有重復(fù)的邊。簡(jiǎn)單圈：圈中沒(méi)有重復(fù)的邊。第1節(jié) 圖的基本概念圖例：?jiǎn)枺海╲1，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有向圖 中一條鏈， ， ， ,，若滿足=( ，)(， ， ，)，則稱這個(gè)點(diǎn)弧序列為從 到 的一條路。112211()KKKiiiiiiiDvavavavG DD有向圖 中一個(gè)點(diǎn)、弧交錯(cuò)序列， ， ， ,，若此序列在基礎(chǔ)圖 ( )中所對(duì)應(yīng)的點(diǎn)邊序列是一條鏈，則稱這個(gè)點(diǎn)弧序列是 的鏈。第1節(jié) 圖的基本概念回路：初等路：路中沒(méi)有重復(fù)的點(diǎn)。初等回路：回路中沒(méi)有重復(fù)的點(diǎn)。第1節(jié) 圖的基本概念圖例：?jiǎn)枺?（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é) 樹(shù)一、樹(shù)的概念o連通圖：無(wú)向圖中任意兩點(diǎn)間至少有一條鏈相連。（不連通圖）o連通分圖：不連通圖中每個(gè)連通的部分。o樹(shù)：連通且不含圈的無(wú)向圖。第2節(jié) 樹(shù)二、樹(shù)的性質(zhì)o任何樹(shù)中必然存在次為1的點(diǎn)。（1）樹(shù)中次為1的點(diǎn)稱為樹(shù)葉（2）樹(shù)中次大于1的點(diǎn)稱為分枝點(diǎn)o樹(shù)的點(diǎn)有n個(gè)，則該樹(shù)的邊必有（n-1）條。o任何具有n個(gè)點(diǎn)、（n-1）條邊的連通圖必是樹(shù)。o樹(shù)中任意兩點(diǎn)之間有且只有唯一一條鏈。o從一個(gè)樹(shù)中去掉任一條邊，則余下的圖必是不連通圖。o在樹(shù)中不相鄰的兩

7、個(gè)點(diǎn)之間添上一條邊，則必得到一個(gè)圈；反之再?gòu)脑撊χ腥我馊サ粢粭l邊，則必得到一個(gè)樹(shù)。第2節(jié) 樹(shù)圖例：v2v4v1v3v5第2節(jié) 樹(shù)三、支撐樹(shù)o支撐子圖：o支撐樹(shù)：如果圖G的支撐子圖是一個(gè)樹(shù)T，則稱樹(shù)T是圖G的一個(gè)支撐樹(shù)。o支撐樹(shù)的性質(zhì)：圖G有支撐樹(shù)的充分必要條件是圖G是連通圖。第2節(jié) 樹(shù)圖例：v2v4v1v3v5v2v4v1v3v5第2節(jié) 樹(shù)四、最小支撐樹(shù)o賦權(quán)圖：o最小支撐樹(shù)：()ijijijijGVEGvvwGwvv圖，對(duì) 中每一條邊 ， ，相應(yīng)地有一個(gè)數(shù)，則稱圖 為賦權(quán)圖，稱為邊 ， 上的權(quán)，表示距離、時(shí)間、費(fèi)用等。( )( )()ijijvvTTGTTw Tw TwTw TGTG，設(shè) 是

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

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

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

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

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

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

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

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

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

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

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