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

數(shù)學建模與數(shù)學實驗

最短路問題2/26/20241實驗目的實驗內(nèi)容2．會用MATLAB軟件求最短路1．了解最短路的算法及其應用1．圖論的基本概念2．最短路問題及其算法3．最短路的應用4．建模案例：最優(yōu)截斷切割問題5．實驗作業(yè)2/26/20242圖論的基本概念一、圖的概念1．圖的定義2．頂點的次數(shù)

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

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

12

34

5

6

7

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

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j的最短路的路徑為：返回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,故應將消防站設在v3處.返回2/26/202436

選址問題--重心問題返回2/26/202437實驗作業(yè)

生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率.生產(chǎn)率過高，導致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機會.可見，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取最大收益.某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預知其產(chǎn)品在年初的需求量為a=6萬單位，并以b=1萬單位/月速度遞增.若生產(chǎn)產(chǎn)品過剩，則需付單位產(chǎn)品單位時間（月）的庫存保管費C2=0.2元；