數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 最短路問(wèn)題ppt課件

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

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

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

4、本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路徑4521141vevevPvvdocin/sundae_meng定定義義（）任意兩點(diǎn)均有路徑的圖稱(chēng)為連連通通圖圖（）起點(diǎn)與終點(diǎn)重合的路徑稱(chēng)為圈圈（）連通而無(wú)圈的圖稱(chēng)為樹(shù)樹(shù)前往前往docin/sundae_meng固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹(shù) 因此, 可采用樹(shù)生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路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每每 對(duì)對(duì) 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1求距離矩陣的方法求距離

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

7、立路徑矩陣R 即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求 時(shí)求得 ，可由 來(lái)查找任何點(diǎn)對(duì)之間最短路的路徑)(D)(R前往前往)(Rvdocin/sundae_mengi j算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn).pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12前往前往docin/sundae_meng算法步驟算法步驟Floyd算算法法：求任意兩點(diǎn)間的最短路(2) 更新 d(i,j), r(i,j)對(duì)所有 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)圖的任意兩點(diǎn)間的距離與路徑 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故從v5到v1的最短路為51r所以從 v5到 v1的最短路徑為：1435.前往前往docin/sundae_meng最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問(wèn)題的多階段決策問(wèn)題可化為最短路問(wèn)題的多階段決策問(wèn)題二、二、 選選 址址 問(wèn)

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

10、/sundae_meng（3）問(wèn)題轉(zhuǎn)化為頂點(diǎn)Xb1到Xrk6( )的最短路問(wèn)題.五年的最優(yōu)購(gòu)置費(fèi)為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點(diǎn)Xb1到Xrk6( )的最短路的權(quán).docin/sundae_meng前往前往docin/sundae_meng 選址問(wèn)題-中心問(wèn)題則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱(chēng)為圖的中中心心點(diǎn)點(diǎn) 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 選址問(wèn)題-重心問(wèn)題前往前往docin/sundae_meng實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè) 生產(chǎn)策略問(wèn)題：現(xiàn)代化生產(chǎn)過(guò)程中，生產(chǎn)部門(mén)面臨的突出問(wèn)題之一，便是如何選取合理的生產(chǎn)率.生產(chǎn)率過(guò)高，導(dǎo)致產(chǎn)品大量積壓，使流動(dòng)資金不能及時(shí)回籠；生產(chǎn)率過(guò)低，產(chǎn)品不能滿足市場(chǎng)需要，使生產(chǎn)部門(mén)失去獲利的機(jī)會(huì).可見(jiàn)，生產(chǎn)部門(mén)在生產(chǎn)過(guò)程中必須時(shí)刻注意市場(chǎng)需求的變化，以便適時(shí)調(diào)整生產(chǎn)率，獲取最大收益. 某生產(chǎn)廠家年初要制定生產(chǎn)