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

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

最短路問題2/26/20241實(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è)2/26/20242圖論的基本概念一、圖的概念1．圖的定義2．頂點(diǎn)的次數(shù)

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

TOMATLAB(road1)2/26/2024202/26/202421

12

34

5

6

7

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

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：返回2/26/202427算法步驟2/26/202428

TOMATLAB(road2(floyd))返回

2/26/202429一、可化為最短路問題的多階段決策問題二、選址問題1．中心問題2．重心問題返回2/26/202430可化為最短路問題的多階段決策問題2/26/2024312/26/2024322/26/202433返回2/26/202434

選址問題--中心問題

TOMATLAB(road3(floyd))2/26/202435S(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處.返回2/26/202436

選址問題--重心問題返回2/26/202437實(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ǎn)部門失去獲利的機(jī)會(huì).可見，生產(chǎn)部門在生產(chǎn)過程中必須時(shí)刻注意市場需求的變化，以便適時(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元；