數(shù)學(xué)建模案例分析第8講最短路問題課件

1、2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 最短路問題最短路問題2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容2會用會用MATLAB軟件求最短路軟件求最短路1了解最短路的算法及其應(yīng)用了解最短路的算法及其應(yīng)用1圖圖 論論 的的 基基 本本 概概 念念2最最 短短 路路 問問 題題 及及 其其 算算 法法3最最 短短 路路 的的 應(yīng)應(yīng) 用用4建模案例：最優(yōu)截?cái)嗲懈顔栴}建模案例：最優(yōu)截?cái)嗲懈顔栴}5實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè)2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的

2、 概概 念念1圖的定義圖的定義2頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù) 3子圖子圖二、二、 圖圖 的的 矩矩 陣陣 表表 示示1 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣2 鄰接矩陣鄰接矩陣返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題定義定義有序三元組G=(V,E, )稱為一個圖圖,如果：圖的定義圖的定義2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題定義定義定義定義規(guī)定用記號和分別表示圖的頂點(diǎn)數(shù)和邊數(shù).2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù)4()4dv5)(3)(2)(444vd

3、vdvd2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題定定理理)(2)()(GvdGVv推推論論任何圖中奇次頂點(diǎn)的總數(shù)必為偶數(shù)例例 在一次聚會中，認(rèn)識奇數(shù)個人的人數(shù)一定是偶數(shù).返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題子圖子圖返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題鄰接矩陣鄰接矩陣注：假設(shè)圖為簡單圖2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題無向賦權(quán)圖的鄰接矩陣可類似定義返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題最最 短短 路路 問問 題題 及

4、及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路三、每三、每 對對 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路徑4521141vevevPvv2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題定定義義（）任意兩點(diǎn)均有路徑的圖稱為連連通通圖圖（）起點(diǎn)與終點(diǎn)重合的路徑稱為圈圈（）連通而無圈的圖稱為樹樹返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最

5、短路問題固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題算法步驟：算法步驟：（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( )= u2022-4-22數(shù)學(xué)建模案例分

6、析第8講最短路問題 TO MATLAB(road1)2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題 1 2 34 5 6 7 8返回返回uuuuuuuu2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題每每 對對 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1求距離矩陣的方法求距離矩陣的方法2求路徑矩陣的方法求路徑矩陣的方法3查找最短路路徑的方法查找最短路路徑的方法（一）算法的基本思想（一）算法的基本思想（三）算法步驟（三）算法步驟返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題算法的基本思想算法的基本思

7、想返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題算法原理算法原理 求距離矩陣的方法求距離矩陣的方法返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法)()0()0(ijrR, jrij)0(每求得一個 D(k)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 R(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距離矩陣的同時(shí)可建立路徑矩陣R 即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求 時(shí)求得 ，可由 來查找任何點(diǎn)對之間最短路的路徑)(D)(R返回返回)(Rv2022-4-22數(shù)學(xué)建模案例

8、分析第8講最短路問題i j算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn).pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題算法步驟算法步驟Floyd算算法法：求任意兩點(diǎn)間的最短路(2) 更新 d(i,j), r(i,j)對所有 i,j，若 d(i,k)+d(k,j)d(i,j)，則 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉(zhuǎn)（） 2022-4-22數(shù)學(xué)建模案例分析第

9、8講最短路問題例例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故從v5到v1的最短路為51r所以從 v5到 v1的最短路徑為：1435.返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題二、二、 選選 址址 問問 題題1 中心問題中心問題2 重心問題重心問題返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題可化為最短路

10、問題的多階段決策問題可化為最短路問題的多階段決策問題 例例 1 設(shè)備更新問題：企業(yè)使用一臺設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用.現(xiàn)要制定一個五年之內(nèi)的設(shè)備更新計(jì)劃，使得五年內(nèi)總的支付費(fèi)用最少. 已知該種設(shè)備在每年年初的價(jià)格為：第一年第二年第三年第四年第五年1111121213 使用不同時(shí)間設(shè)備所需維修費(fèi)為：使用年限0112233445維修費(fèi)56811182022-4-22數(shù)學(xué)建模案例分析第8講最短路問題2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題（3）問題轉(zhuǎn)化為頂點(diǎn)Xb1到Xrk6( )的最

11、短路問題.五年的最優(yōu)購置費(fèi)為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點(diǎn)Xb1到Xrk6( )的最短路的權(quán).2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題 選址問題選址問題-中心問題中心問題則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱為圖的中中心心點(diǎn)點(diǎn) TO MATLAB(road3(floyd)2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .4250

12、2545 .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處. 返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題 選址問題選址問題-重心問題重心問題返回返回2022-4-22數(shù)學(xué)建模案例分析第8講最短路問題實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè) 生產(chǎn)策略問題生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率.生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時(shí)回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機(jī)會.可見，生產(chǎn)部門在生產(chǎn)過程中必須時(shí)刻注意市場需求的變化，