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

數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)

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

3．子圖二、圖的矩陣表示1．關(guān)聯(lián)矩陣2．鄰接矩陣返回9/10/2024數(shù)學(xué)建模定義有序三元組G=(V,E,)稱為一個(gè)圖,如果：圖的定義9/10/2024數(shù)學(xué)建模定義定義9/10/2024數(shù)學(xué)建模9/10/2024數(shù)學(xué)建模返回9/10/2024數(shù)學(xué)建模頂點(diǎn)的次數(shù)9/10/2024數(shù)學(xué)建模例在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù).返回9/10/2024數(shù)學(xué)建模子圖返回9/10/2024數(shù)學(xué)建模關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回9/10/2024數(shù)學(xué)建模鄰接矩陣注：假設(shè)圖為簡單圖9/10/2024數(shù)學(xué)建模返回9/10/2024數(shù)學(xué)建模最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對(duì)頂點(diǎn)之間的最短路返回9/10/2024數(shù)學(xué)建?；靖拍?/10/2024數(shù)學(xué)建模返回9/10/2024數(shù)學(xué)建模固定起點(diǎn)的最短路最短路是一條路徑，且最短路的任一段也是最短路．假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹．因此,可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路．9/10/2024數(shù)學(xué)建模9/10/2024數(shù)學(xué)建模算法步驟：9/10/2024數(shù)學(xué)建模

TOMATLAB(road1)9/10/2024數(shù)學(xué)建模9/10/2024數(shù)學(xué)建模

12

34

5

6

7

8返回9/10/2024數(shù)學(xué)建模每對(duì)頂點(diǎn)之間的最短路1．求距離矩陣的方法2．求路徑矩陣的方法3．查找最短路路徑的方法（一）算法的基本思想（三）算法步驟返回9/10/2024數(shù)學(xué)建模算法的基本思想返回9/10/2024數(shù)學(xué)建模算法原理——求距離矩陣的方法返回9/10/2024數(shù)學(xué)建模算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來查找任何點(diǎn)對(duì)之間最短路的路徑．返回)(nR9/10/2024數(shù)學(xué)建模i

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：返回9/10/2024數(shù)學(xué)建模算法步驟9/10/2024數(shù)學(xué)建模

TO

MATLAB

(road2(floyd))返回

9/10/2024數(shù)學(xué)建模一、可化為最短路問題的多階段決策問題二、選址問題1．中心問題2．重心問題返回9/10/2024數(shù)學(xué)建?？苫癁樽疃搪穯栴}的多階段決策問題9/10/2024數(shù)學(xué)建模9/10/2024數(shù)學(xué)建模9/10/2024數(shù)學(xué)建模返回9/10/2024數(shù)學(xué)建模

選址問題--中心問題

TOMATLAB

(road3(floyd))9/10/2024數(shù)學(xué)建模S(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處.返回9/10/2024數(shù)學(xué)建模

選址問題--重心問題返回9/10/2024數(shù)學(xué)建模實(shí)驗(yàn)作業(yè)

生產(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)率，獲取最大收益.

某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為a=6萬單位，并以b=1萬單位/月速度遞增.若生產(chǎn)產(chǎn)品過剩，則需付單位產(chǎn)品單位時(shí)間（月）的庫存保管費(fèi)C2=0.2元