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

1、2021-10-19數(shù)學(xué)建模數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 最短路問題最短路問題2021-10-19數(shù)學(xué)建模實(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最最 短短 路路 問問 題題 及及 其其 算算 法法3最最 短短 路路 的的 應(yīng)應(yīng) 用用4建模案例：最優(yōu)截?cái)嗲懈顔栴}建模案例：最優(yōu)截?cái)嗲懈顔栴}5實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè)2021-10-19數(shù)學(xué)建模圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的 概概 念念1圖的定義圖的定義2頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù) 3子圖子圖二

2、、二、 圖圖 的的 矩矩 陣陣 表表 示示1 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣2 鄰接矩陣鄰接矩陣返回返回2021-10-19數(shù)學(xué)建模定義定義有序三元組g=(v,e, )稱為一個(gè)圖圖,如果：圖的定義圖的定義2021-10-19數(shù)學(xué)建模定義定義定義定義規(guī)定用記號(hào)和分別表示圖的頂點(diǎn)數(shù)和邊數(shù).2021-10-19數(shù)學(xué)建模2021-10-19數(shù)學(xué)建模返回返回2021-10-19數(shù)學(xué)建模頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù)4()4dv5)(3)(2)(444vdvdvd2021-10-19數(shù)學(xué)建模定理定理)(2)()(gvdgvv推論推論任何圖中奇次頂點(diǎn)的總數(shù)必為偶數(shù)例例 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù).返回返回2021-

3、10-19數(shù)學(xué)建模子圖子圖返回返回2021-10-19數(shù)學(xué)建模關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣注：假設(shè)圖為簡(jiǎn)單圖返回返回2021-10-19數(shù)學(xué)建模鄰接矩陣鄰接矩陣注：假設(shè)圖為簡(jiǎn)單圖2021-10-19數(shù)學(xué)建模無向賦權(quán)圖的鄰接矩陣可類似定義返回返回2021-10-19數(shù)學(xué)建模最最 短短 路路 問問 題題 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路三、每三、每 對(duì)對(duì) 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路返回返回2021-10-19數(shù)學(xué)建模基基 本本 概概 念念通路44112544141vevevevevwvv道路433226452114

4、1vevevevevevtvv路徑4521141vevevpvv2021-10-19數(shù)學(xué)建模定義定義（）任意兩點(diǎn)均有路徑的圖稱為連通圖連通圖（）起點(diǎn)與終點(diǎn)重合的路徑稱為圈圈（）連通而無圈的圖稱為樹樹返回返回2021-10-19數(shù)學(xué)建模固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹 因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路2021-10-19數(shù)學(xué)建模2021-10-19數(shù)學(xué)建模算法步驟：算法步驟：（4） 若s ，轉(zhuǎn) 2，否則，停止.（2）更新l v(

5、 )、z v( )： vsvs,若l v( )l uw u v( )( , ) 則令l v( )=l uw u v( )( , ),z v( )= u2021-10-19數(shù)學(xué)建模 to matlab(road1)2021-10-19數(shù)學(xué)建模2021-10-19數(shù)學(xué)建模 1 2 34 5 6 7 8返回返回uuuuuuuu2021-10-19數(shù)學(xué)建模每每 對(duì)對(duì) 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1求距離矩陣的方法求距離矩陣的方法2求路徑矩陣的方法求路徑矩陣的方法3查找最短路路徑的方法查找最短路路徑的方法（一）算法的基本思想（一）算法的基本思想（三）算法步驟（三

6、）算法步驟返回返回2021-10-19數(shù)學(xué)建模算法的基本思想算法的基本思想返回返回2021-10-19數(shù)學(xué)建模算法原理算法原理 求距離矩陣的方法求距離矩陣的方法返回返回2021-10-19數(shù)學(xué)建模算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法)()0()0(ijrr, jrij)0(每求得一個(gè) 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)對(duì)之間最短路的路徑)(d)(r返回返回)(rv2

7、021-10-19數(shù)學(xué)建模i j算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn).pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12返回返回2021-10-19數(shù)學(xué)建模算法步驟算法步驟floyd 算法：算法：求任意兩點(diǎn)間的最短路(2) 更新 d(i,j), r(i,j)對(duì)所有 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)（） 2021-10-19數(shù)學(xué)建模例例 求下圖中加權(quán)圖

8、的任意兩點(diǎn)間的距離與路徑 tomatlab(road2(floyd)5333434331543243332344441,0646960243420256420793570rd951d，故從 v5到 v1的最短路為51r所以從 v5到 v1的最短路徑為：1435.返回返回2021-10-19數(shù)學(xué)建模最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題二、二、 選選 址址 問問 題題1 中心問題中心問題2 重心問題重心問題返回返回2021-10-19數(shù)學(xué)建?？苫癁樽疃搪穯栴}的多階段決策問題可化為最短路問題的多階段決策問題 例例 1 設(shè)備更新問

9、題：企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費(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)56811182021-10-19數(shù)學(xué)建模2021-10-19數(shù)學(xué)建模（3）問題轉(zhuǎn)化為頂點(diǎn)xb1到xrk6( )的最短路問題.五年的最優(yōu)購置費(fèi)為 kbrkd xx1 2 3 4 516, , , ,( )min (,)其中 d(xb1

10、,xrk6( )為頂點(diǎn)xb1到xrk6( )的最短路的權(quán).2021-10-19數(shù)學(xué)建模返回返回2021-10-19數(shù)學(xué)建模 選址問題選址問題-中心問題中心問題則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱為圖的中心點(diǎn)中心點(diǎn) to matlab(road3(floyd)2021-10-19數(shù)學(xué)建模05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .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處. 返回返回2021-10-19數(shù)學(xué)建模 選址問題選址問題-重心問題重心問題返回返回2021-10-19數(shù)學(xué)建模實(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)品大量積壓，使流動(dòng)資金不能及時(shí)回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場(chǎng)需要，使生產(chǎn)部門失去獲利的機(jī)會(huì).可見，生產(chǎn)部門在生產(chǎn)過程中必須時(shí)刻注意市場(chǎng)需求的變化，以便適時(shí)調(diào)整生產(chǎn)率，獲取最大收益. 某生