數(shù)學(xué)建模提高班第六講網(wǎng)絡(luò)優(yōu)化模型及案例分析市公開課金獎市賽課一等獎?wù)n件

網(wǎng)絡(luò)優(yōu)化模型及案例分析趙承業(yè)/4/24第1頁第1頁本專項學(xué)習(xí)目掌握把實際問題轉(zhuǎn)化為圖或網(wǎng)絡(luò)問題辦法理解圖基本概念和矩陣表示辦法掌握最短路問題、最小生成樹問題算法理解旅行商問題第2頁第2頁一個表示工具——圖最小生成樹主要內(nèi)容一個時間安排問題圖論起源人、狼、羊、菜渡河問題最短路問題圖矩陣表示辦法第3頁第3頁練習(xí)題主要內(nèi)容旅行商問題第4頁第4頁圖論起源：七橋問題第5頁第5頁

c

a

b

d

c

a

b

d

圖論起源：七橋問題圖1圖2第6頁第6頁歐拉——圖論之父■定理1：一個圖存在通過每邊正好一次回到出發(fā)點路線充要條件是：

1）圖要是連通2）與圖中每一頂點相連邊必須是偶數(shù)條。于是得出結(jié)論：七橋問題無解。圖論起源：七橋問題返回第7頁第7頁無向圖，普通用大寫字母G,H表示。一個表示工具——圖頂點邊

d

c

ab圖3第8頁第8頁無向圖：G=(V,E)，頂點集：V；邊集：E。

e與頂點u,v相關(guān)聯(lián)。

u與v相鄰。

兩邊相鄰。

重邊

c

a

b

d

一個表示工具——圖圖4第9頁第9頁兩種特殊圖：

簡樸圖

完全圖，記為Knb

d

c

a

b

d

c

a

一個表示工具——圖圖6圖5第10頁第10頁有向圖：V1V2V3V5V4

想你能給出一個可用有向圖描述實際例子嗎？一個表示工具——圖圖7第11頁第11頁網(wǎng)絡(luò)這些數(shù)字能夠代表距離，費用，可靠性或其它相關(guān)參數(shù)。12345869157103一個表示工具——圖圖8第12頁第12頁

(G)和

(G)分別表示圖G頂點數(shù)和邊數(shù)在無向圖中，v度數(shù)，記為d(v)；在有向圖中，v出度，記為d+(v);v入度，記為d-(v)。一個表示工具——圖返回第13頁第13頁一個時間安排問題學(xué)校要為一年級碩士開設(shè)六門基礎(chǔ)數(shù)學(xué)課：統(tǒng)計(S)，數(shù)值分析(N)，圖論(G)，矩陣論(M)，隨機過程(R)和數(shù)理方程(P)。按培養(yǎng)計劃，注冊學(xué)生必須選修其中一門以上，你作為教務(wù)管理人員，要設(shè)法安排一個課表，使每個學(xué)生所選課程，在時間上不會發(fā)生沖突。第14頁第14頁一個時間安排問題表1第15頁第15頁SNGRPM?完畢上述表示課程沖突關(guān)系圖直觀、清楚地表示已知信息方式一個時間安排問題返回圖9第16頁第16頁人狼羊菜渡河問題擺渡人F狼W羊G菜C圖10第17頁第17頁南岸狀態(tài)：

16種，其中WG,GC,WGC，從而FC,FW,F為不允許狀態(tài)，F(xiàn)WGCFWGFWCFGCFGOCGWWC10個允許狀態(tài)：人狼羊菜渡河問題第18頁第18頁FWGCFWGFWCFGCFGOCGWWC尋求圖中從頂點“FWGC”到頂點“O”最短路徑，這樣路徑有幾條？求出最優(yōu)渡河方案。

想語言描述時未顯示關(guān)系躍然紙上人狼羊菜渡河問題圖11第19頁第19頁FWGCFWGFWCFGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河問題返回圖12第20頁第20頁圖矩陣表示辦法鄰接矩陣關(guān)聯(lián)矩陣邊矩陣鄰接順序表返回第21頁第21頁v1v2v5v6v7v4v3abjkcghidfe鄰接矩陣圖13第22頁第22頁

無向圖鄰接矩陣：A=(aij)n

n，其中無向圖鄰接矩陣有何特點？由鄰接矩陣是否能作出原圖？

想鄰接矩陣返回第23頁第23頁關(guān)聯(lián)矩陣v1v2v5v6v7v4v3abjkcghidfe圖13第24頁第24頁

無向圖關(guān)聯(lián)矩陣：M=(mij)n

m,其中

想無向圖關(guān)聯(lián)矩陣有哪些特性？由關(guān)聯(lián)矩陣能否作出原圖？關(guān)聯(lián)矩陣返回第25頁第25頁邊矩陣v1v2v5v6v7v4v3abjkcghidfe返回圖13第26頁第26頁最短路問題及算法最短路問題是圖論應(yīng)用基本問題，諸多實際問題，如線路布設(shè)、運送安排、運送網(wǎng)絡(luò)最小費用流等問題,都可通過建立最短路問題模型來求解.最短路定義最短路問題兩種辦法：Dijkstra和Floyd算法.1)求賦權(quán)圖中從給定點到其余頂點最短路.2)

求賦權(quán)圖中任意兩點間最短路.第27頁第27頁

2)

在賦權(quán)圖G中，從頂點u到頂點v含有最小權(quán)定義11)若H是賦權(quán)圖G一個子圖，則稱H各邊權(quán)和為H權(quán).類似地，若稱為路P權(quán)．若P(u,v)是賦權(quán)圖G中從u到v路,稱路P*(u,v)，稱為u到v最短路．

3)

把賦權(quán)圖G中一條路權(quán)稱為它長，把(u,v)路最小權(quán)稱為u和v之間距離，并記作d(u,v).第28頁第28頁1)賦權(quán)圖中從給定點到其余頂點最短路假設(shè)G為賦權(quán)有向圖或無向圖，G邊上權(quán)均非負．若，則要求最短路是一條路，且最短路任一節(jié)也是最短路．例求下面賦權(quán)圖中頂點u0到其余頂點最短路．圖14第29頁第29頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第30頁第30頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第31頁第31頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第32頁第32頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第33頁第33頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第34頁第34頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第35頁第35頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第36頁第36頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第37頁第37頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第38頁第38頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第39頁第39頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第40頁第40頁Dijkstra算法:

求G中從頂點u0到其余頂點最短路.

1)

置，對，，且.

2)

對每個，用代替，計算，并把達到這個最小值一個頂點記為，置

3)

若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第41頁第41頁第42頁第42頁定義2依據(jù)頂點v標號l(v)取值路徑，使到v最短路中與v相鄰前一個頂點w，稱為v先驅(qū)點，記為z(v),即z(v)=w.先驅(qū)點可用于追蹤最短路徑.例5標號過程也可按下列方式進行：首先寫出左圖帶權(quán)鄰接矩陣因G是無向圖，故W是對稱陣．第43頁第43頁表2第44頁第44頁續(xù)表2圖8第45頁第45頁2)求賦權(quán)圖中任意兩頂點間最短路算法基本思想（I）求距離矩陣辦法.（II）求路徑矩陣辦法.（III）查找最短路路徑辦法.Floyd算法：求任意兩頂點間最短路.舉例闡明第46頁第46頁

算法基本思想

第47頁第47頁（I）求距離矩陣辦法.第48頁第48頁（II）求路徑矩陣辦法.在建立距離矩陣同時可建立路徑矩陣R．第49頁第49頁（III）查找最短路路徑辦法.然后用同樣辦法再分頭查找．若：圖16第50頁第50頁（IV）Floyd算法：求任意兩頂點間最短路.第51頁第51頁例2求下圖中加權(quán)圖任意兩點間距離與路徑.圖17第52頁第52頁插入點v1，得：矩陣中帶“=”項為經(jīng)迭代比較以后有改變元素.第53頁第53頁插入點v2，得：矩陣中帶“=”項為經(jīng)迭代比較以后有改變元素.第54頁第54頁插入點v3，得：第55頁第55頁插入點v4，得：插入點v5，得：第56頁第56頁插入點v6，得：第57頁第57頁故從v5到v2最短路為8

由v6向v5追溯:由v6向v2追溯:因此從到最短路徑為：返回第58頁第58頁最小生成樹及算法許多應(yīng)用問題都是一個求無向連通圖最小生成樹問題。比如：要在n個城市之間鋪設(shè)光纜，主要目標是要使這n個城市任意兩個之間都能夠通信，但鋪設(shè)光纜費用很高，且各個城市之間鋪設(shè)光纜費用不同；另一個目標是要使鋪設(shè)光纜總費用最低。這就需要找到帶權(quán)最小生成樹。第59頁第59頁1)樹定義與樹特性定義3連通且不含圈無向圖稱為樹．慣用T表示.樹中邊稱為樹枝.樹中度為1頂點稱為樹葉.孤立頂點稱為平凡樹.平凡樹圖18第60頁第60頁定理2設(shè)G是含有n個頂點圖，則下述命題等價：1)G是樹（G無圈且連通）；2)G無圈，且有n-1條邊；3)G連通，且有n-1條邊；4)G無圈，但添加任一條新邊正好產(chǎn)生一個圈;5)G連通，且刪去一條邊就不連通了（即G為最最小連通圖）；6)G中任意兩頂點間有唯一一條路.第61頁第61頁2）圖生成樹定義4若T是包括圖G所有頂點子圖,它又是樹,則稱T是G生成樹.圖G中不在生成樹邊叫做弦.定理3

圖G=(V,E)有生成樹充要條件是圖G是連通.證實

必要性是顯然.第62頁第62頁第63頁第63頁（II）找圖中生成樹辦法可分為兩種：避圈法和破圈法A避圈法:深探法和廣探法

B破圈法第64頁第64頁A避圈法

定理3充足性證實提供了一個結(jié)構(gòu)圖生成樹辦法.這種辦法就是在已給圖G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止.這種辦法可稱為“避圈法”或“加邊法”在避圈法中，按照邊選法不同，找圖中生成樹方法可分為兩種：深探法和廣探法.第65頁第65頁a)深探法若這樣邊另一端均已有標號，就退到標號為環(huán)節(jié)下列：i)在點集V中任取一點u,ii)若某點v已得標號，檢端是否均已標號.若有邊vw之w未標號,則給w代v，重復(fù)ii).i-1r點,以r代v,重復(fù)ii),直到所有點得到標號為止.給以標號0.查一端點為v各邊，另一w以標號i+1，記下邊vw.令例3用深探法求出下圖10一棵生成樹

圖19012345678910111213圖20第66頁第66頁3b)廣探法環(huán)節(jié)下列：i)在點集V中任取一點u,ii)令所有標號i點集為是否均已標號.對所有未標號之點均標以i+1,記下這些iii)對標號i+1點重復(fù)步環(huán)節(jié)ii)，直到所有點得到給u以標號0.Vi,檢查[Vi,V\Vi]中邊端點邊.例4用廣探法求出下圖10一棵生成樹

圖191012213212234標號為止.圖21第67頁第67頁B破圈法相對于避圈法，尚有一個求生成樹辦法叫做“破圈法”.這種辦法就是在圖G中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復(fù)這個環(huán)節(jié)直到圖G中沒有圈為止.例5用破圈法求出下圖一棵生成樹.圖22第68頁第68頁B破圈法例6用破圈法求出下圖另一棵生成樹.不難發(fā)覺，圖生成樹不是唯一.圖23第69頁第69頁3)最小生成樹與算法簡介最小樹兩種算法：Kruskal算法（或避圈法）和破圈法.5第70頁第70頁AKruskal算法（或避圈法）環(huán)節(jié)下列：1)選擇邊e1，使得w(e1)盡也許??；2)若已選定邊，則從中選取，使得:i)為無圈圖，ii)是滿足i)盡也許小權(quán)，

3)當?shù)?)步不能繼續(xù)執(zhí)行時，則停止.定理4

由Kruskal算法構(gòu)作任何生成樹都是最小樹.第71頁第71頁例7用Kruskal算法求下圖最小樹.在左圖中權(quán)值最小邊有任取一條在中選取權(quán)值最小邊中權(quán)值最小邊有,從中選任取一條邊會與已選邊構(gòu)成圈,故停止,得中選取在中選取中選取.但與都圖24第72頁第72頁B破圈法算法2

環(huán)節(jié)下列：1)從圖G中任選一棵樹T1.2)加上一條弦e1，T1+e1中馬上生成一個圈.去掉此圈中最大權(quán)邊，得到新樹T2,以T2代T1,重復(fù)2)再檢查剩余弦，直到全部弦檢查完畢為止.例8用破圈法求下圖最小樹.先求出上圖一棵生成樹.

加以弦e2,得到圈v1v3v2v1,去掉最大權(quán)邊e2,得到一棵新樹仍是本來樹；

再加上弦e7，得到圈v4v5v2v4,去掉最大權(quán)邊e6，得到一棵新樹；如此重復(fù)進行，直到全所有弦均已試過,得最小樹.返回圖25第73頁第73頁旅行售貨員問題定義6設(shè)G=(V,E)是連通無向圖，包括圖G每個頂點路稱為G哈密爾頓路(Hamilton路或H路).包括圖G每個頂點圈，稱為G哈密爾頓圈(或Hamilton圈或H圈).含Hamilton圈圖稱為哈密爾頓圖(或Hamilton圖或H圖).第74頁第74頁旅行售貨員問題或貨郎擔(dān)問題一個旅行售貨員想去訪問若干城鄉(xiāng)，然后回到出發(fā)地.給定各城鄉(xiāng)之間距離后，應(yīng)如何計劃他旅行路線，使他能對每個城鄉(xiāng)正好通過一次而總距離最??？它可歸結(jié)為這樣圖論問題：在一個賦權(quán)完全圖中,找出一個最小權(quán)H圈,稱這種圈為最優(yōu)圈.但這個問題是NP-hard問題，即不存在多項式時間算法.也就是說,對于大型網(wǎng)絡(luò)(賦權(quán)圖),當前還沒有一個求解旅行售貨員問題有效算法，因此只能找一個求出相稱好（不一定最優(yōu)）解.第75頁第75頁一個可行辦法:是先求一個H圈,然后適當修改,以得到含有較小權(quán)另一個H圈.圖26第76頁第76頁定義7若對于某一對i和j，有則圈Cij將是圈C一個改進.定義8二邊逐次修正法:在接連進行一系列修改之后,最后得一個圈,不能再用此辦法改進了，這個最后圈也許不是最優(yōu),但是它是比較好，為了得到更高精度，這個程序能夠重復(fù)幾次，每次都以不同圈開始.這種辦法叫做二邊逐次修正法.第77頁第77頁例9對下圖,用二邊逐次修正法求較優(yōu)H圈.較優(yōu)H圈:其權(quán)為W(C3)=192圖27第78頁第78頁分析:

找出這個解好壞可用最優(yōu)H圈權(quán)下界與其比較而得出.即利用最小生成樹可得最優(yōu)H圈一個下界，辦法下列：設(shè)C是G一個最優(yōu)H圈，則對G任一頂點v,C-v是G-v路，也G-v是生成樹.假如T是G-v最小生成樹,且e1是e2與v關(guān)聯(lián)邊中權(quán)最小兩條邊,則w(T)+w(e1)+w(e2)將是w(C)一個下界.取v=v3,得G-v3一最小生成樹(實線),其權(quán)w(T)=122,與v3關(guān)聯(lián)權(quán)最小兩條邊為w(T)+w(v1v3)+w(v2v3)=178.故最優(yōu)H圈權(quán)v1v3和v2v3,故w(C)應(yīng)滿足178w(C)192.返回第79頁第79頁1.設(shè)某校田徑選拔賽共設(shè)六個項目標比賽，即跳高，跳遠，標槍，鉛球，100米和200米短跑，要求每個選手至多參加三個項目標比賽?，F(xiàn)有七名選手報名，選手所選項目如表1所表示?，F(xiàn)在要求設(shè)計一個比賽日程安排表，使得在盡也許短時間內(nèi)完成比賽。田徑賽時間安排練習(xí)題第80頁第80頁表1參賽選手比賽項目表

第81頁第81頁第82頁第82頁附錄：圖論算法matlab實現(xiàn)第83頁第83頁最短路問題例某公司在六個都市中有分公司，從ci到cj直接航程票價記在下述矩陣位置上。（表示無直接航路），請幫助該公司設(shè)計一張都市c1到其它都市間票價最廉價路線圖。第84頁第84頁用矩陣（為頂點個數(shù)）存儲各邊權(quán)鄰接矩陣，行向量pb、index1、index2、d分別用來存儲標號信息、標號頂點順序、標號頂點索引、最短通路值。其中分量

index2(i)存儲始點到第點最短通路中第頂點前一頂點序號；

d(i)存儲由始點到第點最短通路值。第85頁第85頁DijkstraMatlab程序下列：M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);a=a+a';第86頁第86頁pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));d(1:length(a))=M;d(1)=0;temp=1;whilesum(pb)<length(a)tb=find(pb==0);d(tb)=min(d(tb),d(temp)+a(temp,tb));tmpb=find(d(tb)==min(d(tb)));temp=tb(tmpb(1));pb(temp)=1;第87頁第87頁index1=[index1,temp];index=index1(find(d(index1)==d(temp)-a(temp,index1)));iflength(index)>=2index=index(1);endindex2(temp)=index;endd,index1,index2第88頁第88頁Floyd算法Matlab程序下列：clear;clc;M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);b=a+a';path=zeros(length(b));第89頁第89頁fork=1:6fori=1:6forj=1:6ifb(i,j)>b(i,k)+b(k,j)b(i,j)=b(i,