數(shù)學(xué)建模與數(shù)學(xué)實驗 最短路問題ppt課件

1、數(shù)學(xué)建模與數(shù)學(xué)實驗數(shù)學(xué)建模與數(shù)學(xué)實驗 最短路問題最短路問題docin/sundae_meng實驗?zāi)康膶嶒災(zāi)康膶嶒瀮?nèi)容實驗內(nèi)容2會用會用MATLAB軟件求最短路軟件求最短路1了解最短路的算法及其應(yīng)用了解最短路的算法及其應(yīng)用1圖圖 論論 的的 基基 本本 概概 念念2最最 短短 路路 問問 題題 及及 其其 算算 法法3最最 短短 路路 的的 應(yīng)應(yīng) 用用4建模案例：最優(yōu)截斷切割問題建模案例：最優(yōu)截斷切割問題5實驗作業(yè)實驗作業(yè)docin/sundae_meng圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的 概概 念念1圖的定義圖的定義2頂點的次數(shù)頂點的次數(shù) 3子圖二、二、 圖圖 的的

2、矩矩 陣陣 表表 示示1 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣2 鄰接矩陣鄰接矩陣前往前往docin/sundae_meng定義定義有序三元組G=(V,E, )稱為一個圖,假設(shè)：圖的定義圖的定義docin/sundae_meng定義定義定義定義規(guī)定用記號和分別表示圖的頂點數(shù)和邊數(shù).docin/sundae_mengdocin/sundae_meng前往前往docin/sundae_meng頂點的次數(shù)頂點的次數(shù)4()4dv5)(3)(2)(444vdvdvddocin/sundae_meng定定理理)(2)()(GvdGVv推推論論任何圖中奇次頂點的總數(shù)必為偶數(shù)例例 在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù)在一次

3、聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù).前往前往docin/sundae_meng子圖子圖前往前往docin/sundae_meng關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖前往前往docin/sundae_meng鄰接矩陣鄰接矩陣注：假設(shè)圖為簡單圖docin/sundae_meng無向賦權(quán)圖的鄰接矩陣可類似定義前往前往docin/sundae_meng最最 短短 路路 問問 題題 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 點點 的的 最最 短短 路路三、每三、每 對對 頂頂 點點 之之 間間 的的 最最 短短 路路前往前往docin/sundae_meng基基 本

4、本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路徑4521141vevevPvvdocin/sundae_meng定定義義（）任意兩點均有路徑的圖稱為連連通通圖圖（）起點與終點重合的路徑稱為圈圈（）連通而無圈的圖稱為樹樹前往前往docin/sundae_meng固固 定定 起起 點點 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構(gòu)成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點到其余頂點的最短路docin/sundae_

5、mengdocin/sundae_meng算法步驟：算法步驟：（4） 若S ，轉(zhuǎn) 2，否則，停止.（2）更新l v( )、z v ( )： vSVS,若l v( )l uW u v( )( , ) 則令l v( )=l uW u v( )( , ),z v ( )= udocin/sundae_meng TO MATLAB(road1)docin/sundae_mengdocin/sundae_meng 1 2 34 5 6 7 8前往前往uuuuuuuudocin/sundae_meng每每 對對 頂頂 點點 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1求距離矩陣的方法求距離

6、矩陣的方法2求路徑矩陣的方法求路徑矩陣的方法3查找最短路路徑的方法查找最短路路徑的方法（一算法的基本思想（一算法的基本思想（三算法步驟（三算法步驟前往前往docin/sundae_meng算法的基本思想算法的基本思想前往前往docin/sundae_meng算法原理算法原理 求距離矩陣的方法求距離矩陣的方法前往前往docin/sundae_meng算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法)()0()0(ijrR, jrij)0(每求得一個 D(k)時，按下列方式產(chǎn)生相應(yīng)的新的 R(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距離矩陣的同時可建

7、立路徑矩陣R 即當k被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求 時求得 ，可由 來查找任何點對之間最短路的路徑)(D)(R前往前往)(Rvdocin/sundae_mengi j算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點 p1是點 i 到點 j 的最短路的中間點.pkp2p1p3q1q2qm則由點i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12前往前往docin/sundae_meng算法步驟算法步驟Floyd算算法法：求任意兩點間的最短路(2) 更新 d(i,j), r(i,j)對所有 i,j，若 d(i,k)+d(k,j)d(i

8、,j)，則 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉(zhuǎn)（） docin/sundae_meng例例 求下圖中加權(quán)圖的任意兩點間的距離與路徑 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故從v5到v1的最短路為51r所以從 v5到 v1的最短路徑為：1435.前往前往docin/sundae_meng最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題二、二、 選選 址址 問

9、問 題題1 中心問題中心問題2 重心問題重心問題前往前往docin/sundae_meng可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題 例例 1 設(shè)備更新問題：企業(yè)使用一臺設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費用；若繼續(xù)使用，則需支付一定的維修費用.現(xiàn)要制定一個五年之內(nèi)的設(shè)備更新計劃，使得五年內(nèi)總的支付費用最少. 已知該種設(shè)備在每年年初的價格為：第一年第二年第三年第四年第五年1111121213 使用不同時間設(shè)備所需維修費為：使用年限0112233445維修費5681118docin/sundae_mengdocin

10、/sundae_meng（3）問題轉(zhuǎn)化為頂點Xb1到Xrk6( )的最短路問題.五年的最優(yōu)購置費為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點Xb1到Xrk6( )的最短路的權(quán).docin/sundae_meng前往前往docin/sundae_meng 選址問題-中心問題則kv就是要求的建立消防站的地點此點稱為圖的中中心心點點 TO MATLAB(road3(floyd)docin/sundae_meng05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .4

11、2502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處. 前往前往docin/sundae_meng 選址問題-重心問題前往前往docin/sundae_meng實驗作業(yè)實驗作業(yè) 生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率.生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機會.可見，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取最大收益. 某生產(chǎn)廠家年初要制定生產(chǎn)