數(shù)學(xué)建模提高班專題六網(wǎng)絡(luò)優(yōu)化模型及案例分析資料

1、從農(nóng)夫怎樣過河談起 農(nóng)夫過河 獨(dú)木橋 一般過河問題的解決策略 選課問題 農(nóng)夫過河 2 農(nóng)夫過河農(nóng)夫過河 擺渡人F 狼W 羊G 菜C 3 南岸狀態(tài)： 16種，其中WG,GC,WGC，從而 FC,FW,F為不允許狀態(tài)， FWGCFWGFWCFGCFG OC GWWC 10個允許狀態(tài)： 農(nóng)夫過河農(nóng)夫過河 4 FWGCFWG FWC FGCFG OC GWWC 尋求圖中從頂點(diǎn)“FWGC”到頂點(diǎn) “O”的最短路徑，這樣的路徑有 幾條？求出最優(yōu)的渡河方案。 語言描述時(shí) 未顯示的關(guān) 系躍然紙上 農(nóng)夫過河農(nóng)夫過河 5 FWGCFWG FWC FGCFG OC GWWC FWGC FWG FWC FGC FG

2、O C G W WC 農(nóng)夫過河農(nóng)夫過河 6 獨(dú)木橋 7 一般過河問題的解決策略 多少種狀態(tài) 狀態(tài)如何轉(zhuǎn)換 花的時(shí)間怎么計(jì)算 最后求什么 8 選課問題 學(xué)校要為一年級的研究生開設(shè)六門基礎(chǔ)數(shù) 學(xué)課：統(tǒng)計(jì)(S)，數(shù)值分析(N)，圖論(G)， 矩陣論(M)，隨機(jī)過程(R)和數(shù)理方程(P)。 按培養(yǎng)計(jì)劃，注冊的學(xué)生必須選修其中的 一門以上，你作為教務(wù)管理人員，要設(shè)法 安排一個課表，使每個學(xué)生所選的課程， 在時(shí)間上不會發(fā)生沖突。 9 選課問題 S N G M R P 李春蘭 鄭文國 姚南 陳奇峰 王潤惠 鄒文燕 萬華 李祖軍 黃大度 史武軍 劉昆 歐陽金 郭志偉 陳奇峰 劉云 劉元元 黃大度 董舟 鄒鑫

3、趙云 王凱 李白彤 甄軍 李欣 陳俊 于洪 化范文 李出榮 張惠 趙云 曹林軍 胡志強(qiáng) 張敏 陳修建 歐陽金 李曉 李白彤 萬華 曾光偉 張星 夏雯 邵桂芳 王學(xué)權(quán) 單富民 董舟 楊欣 吳軍 查小輝 王堅(jiān) 程靜波 鄒文燕 衛(wèi)迎新 趙小民 息志強(qiáng) 陳修建 鄒鑫 劉元兵 楊成寶 邱吉洲 許茂 陳俊 周清武 樊雪峰 劉偉 甄軍 姜永東 10 選課問題 為什么會出現(xiàn)時(shí)間上的沖突？ 時(shí)間沖突的本質(zhì)是什么？ 如何表示課程在時(shí)間上沖突？ 如果把一門課程看成圖中的頂點(diǎn)，那么連 接兩點(diǎn)的邊表示什么？ 11 S N G R P M 完成上述表示課程沖突關(guān) 系的線圖 直觀、清 晰地表達(dá) 已知信息 的方式 12 圖是

4、一種思考問題的方法 圖有兩個基本要素-頂點(diǎn)和邊 頂點(diǎn)表示事物 邊表示兩個事物之間的關(guān)系 增加第三個要素-邊的權(quán)值 可以表示關(guān)系深淺、大小、重要等程度 用圖來思考問題 本質(zhì)是考慮事物之間的聯(lián)系 13 圖是一種思考問題的方法 圖可以畫出來 v1 v2 v5 v6v7 v4 v3 a b j k c g h i d f e 14 圖是一種思考問題的方法 圖也可以用矩陣來表示，最常用的是鄰接 矩陣 0101000 1011110 0100010 1100101 0101010 0110101 0001010 7 6 5 4 3 2 1 7654321 v1 v2 v5 v6v7 v4 v3 a b j

5、 k c g h i d f e 15 鄰接矩陣的優(yōu)點(diǎn)： 容易理解 容易轉(zhuǎn)換為具體的圖 便于計(jì)算機(jī)編程計(jì)算 圖是一種思考問題的方法 16 最短路問題 固定起點(diǎn)的最短路 每對頂點(diǎn)之間的最短路 選址問題 固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路 最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其 余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn) 的最短路 18 19 算法步驟：算法步驟： （4） 若S ，轉(zhuǎn) 2，否則，停止. （2）更新l v( )、z v( )： vSVS,若l v( )l uW u v(

6、)( , ) 則令l v( )=l uW u v( )( , ),z v( )= u 20 TO MATLAB(road1) 21 22 1 2 3 4 5 6 7 8 uu u u u u u u 23 每每 對對 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路 (二二)算算法法原原理理 1求距離矩陣的方法求距離矩陣的方法 2求路徑矩陣的方法求路徑矩陣的方法 3查找最短路路徑的方法查找最短路路徑的方法 （一）算法的基本思想（一）算法的基本思想 （三）算法步驟（三）算法步驟 24 算法的基本思想算法的基本思想 25 算法原理算法原理 求距離矩陣的方法求距離矩陣的方法 26 算法原理算法原理 求

7、路徑矩陣的方法求路徑矩陣的方法 )( )0()0( ij rR, jrij )0( 每求得一個 D(k)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 R(k) 否則 若 )1()1()1( )1( )( k kj k ik k ij k ij k ij ddd r k r 在建立距離矩陣的同時(shí)可建立路徑矩陣R 即當(dāng)k被插入任何兩點(diǎn)間的最 短路徑時(shí)，被記錄在R(k)中，依 次求 時(shí)求得 ，可由 來查 找任何點(diǎn)對之間最短路的路徑 )( D )( R )( R v 27 i j 算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法 若 1 )( prij ，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn). p

8、kp2p1p3q1q2 qm 則由點(diǎn)i到j(luò)的最短路的路徑為：jqqqpppi mk , 21, 12 28 算法步驟算法步驟 Floyd 算法：算法：求任意兩點(diǎn)間的最短路 (2) 更新 d(i,j), r(i,j) 對所有 i,j，若 d(i,k)+d(k,j)=1; 24!For city i, except the base (city 1); 25for(cities(i) | i #gt# 1 : 26! It must be entered; 27 sum(cities(j)| j #ne# i: x(j,i)=1; 28! level(j)=levle(i)+1, if we li

9、nk j and i; 69 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33! The level of city is at least 1 but no more n-1, 34 and is 1 if it links to base (city 1); 35 bnd(1,level(i),999999); 36 level(i)=n-1-(n-2)*x(1,i); 37 ); 38! Make

10、 the xs 0/1; 39for(link : bin(x); END 70 利用水平變量利用水平變量(level)來保證所選的邊不構(gòu)成圈來保證所選的邊不構(gòu)成圈. Global optimal solution found at iteration: 34 Objective value: 60.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 1, 3) 1.000000 5.000000 X( 3, 4) 1.000000 7.000000 X( 3, 7) 1.000000 7.000000 X( 4, 5

11、) 1.000000 3.000000 X( 5, 8) 1.000000 6.000000 X( 7, 9) 1.000000 6.000000 X( 9, 6) 1.000000 8.000000 X( 9, 10) 1.000000 10.00000 71 連接這連接這10個城鎮(zhèn)的最小距離為個城鎮(zhèn)的最小距離為60公里，其連接情況如下公里，其連接情況如下. SV地區(qū)的最優(yōu)連線地區(qū)的最優(yōu)連線 72 旅行商問題 哈密頓的環(huán)游世界 環(huán)游世界游戲 騎士的環(huán)游 Forbruger-Kontakt公司送貨的路線 繪制基因圖譜 解法 哈密頓的環(huán)游世界 74 環(huán)游世界游戲 75 騎士的環(huán)游 76 Forb

12、ruger-Kontakt公司送貨的路 線 77 繪制基因圖譜 標(biāo)記 X光輻射使之?dāng)嗔?與嚙齒類動物遺傳物質(zhì)雜交 分析確定標(biāo)記位置 標(biāo)記A和標(biāo)記B如果在染色體 中距離近，則輻射就不太可 能將之?dāng)嚅_，二者可能處在 同一個細(xì)胞系中，反之在不 同細(xì)胞系中 測兩個標(biāo)記間距實(shí)驗(yàn)值，則 測染色體標(biāo)記順序就成為 TSP問題 輻 射雜交細(xì) 胞 78 解法 我們不滿足于僅僅知道是什么 我們還想知道為什么會這樣 我們最終會知道怎樣做到 79 最近鄰居法 80 無賴的做法 在最近鄰算法中 設(shè)計(jì)最后返回起點(diǎn)的那條路徑為 10000000000 則無論如何，我們得到的路徑必然包含它 事實(shí)上，合理的做法 三角不等式 81

13、 貪心算法 82 插入法 83 基于最優(yōu)樹的算法 84 奇點(diǎn)的最小代價(jià)完美匹配 85 Christofides算法，結(jié)果不大于最 優(yōu)解的3/2 86 結(jié)果的改進(jìn)，邊交換 87 其他啟發(fā)式算法 局部搜索和爬山算法 模擬退火算法 鏈?zhǔn)骄植孔顑?yōu)化 遺傳算法 蟻群算法 88 路線之王 Keld Helsgaun LKH算法1998 85900城市的TSP目 前最優(yōu)路線圖見左圖 ，由LKH改進(jìn)算法得 到 89 永田裕一 遺傳算法 求出了蒙娜麗莎 TSP挑戰(zhàn)的已知最 佳路線 90 Matlab的圖論工具箱 練習(xí)1 我們在課堂上介紹了獨(dú)木橋過河問題，請利用 Matlab編寫一個求解此問題的程序，最后輸出 過橋的過程，及花費(fèi)的時(shí)間。 93 練習(xí)2 求上圖的所有生成樹中，權(quán)值最大的生成樹和權(quán)值最 小的生成樹的權(quán)值之差。 94 算法的基本思想算法的基本思想 95 算法原理算法原理 求距離矩陣的方法求距離矩陣的方法 96 確定應(yīng)