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

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

3．子圖二、圖的矩陣表示1．關(guān)聯(lián)矩陣2．鄰接矩陣返回/sundae_meng定義有序三元組G=(V,E,)稱為一個(gè)圖,如果：圖的定義/sundae_meng定義定義/sundae_meng/sundae_meng返回/sundae_meng頂點(diǎn)的次數(shù)/sundae_meng例在一次聚會(huì)中，認(rèn)識奇數(shù)個(gè)人的人數(shù)一定是偶數(shù).返回/sundae_meng子圖返回/sundae_meng關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回/sundae_meng鄰接矩陣注：假設(shè)圖為簡單圖/sundae_meng返回/sundae_meng最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對頂點(diǎn)之間的最短路返回/sundae_meng基本概念/sundae_meng返回/sundae_meng固定起點(diǎn)的最短路最短路是一條路徑，且最短路的任一段也是最短路．

假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹．

因此,可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路．/sundae_meng/sundae_meng算法步驟：/sundae_meng

TOMATLAB(road1)/sundae_meng/sundae_meng

12

34

5

6

7

8返回/sundae_meng每對頂點(diǎn)之間的最短路1．求距離矩陣的方法2．求路徑矩陣的方法3．查找最短路路徑的方法（一）算法的基本思想（三）算法步驟返回/sundae_meng算法的基本思想返回/sundae_meng算法原理——

求距離矩陣的方法返回/sundae_meng算法原理——

求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來查找任何點(diǎn)對之間最短路的路徑．返回)(nR/sundae_mengi

j算法原理——

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

TO

MATLAB

(road2(floyd))返回

/sundae_meng一、可化為最短路問題的多階段決策問題二、選址問題1．中心問題2．重心問題返回/sundae_meng可化為最短路問題的多階段決策問題/sundae_meng/sundae_meng/sundae_meng返回/sundae_meng

選址問題--中心問題

TOMATLAB

(road3(floyd))/sundae_mengS(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處.返回/sundae_meng

選址問題--重心問題返回/sundae_meng實(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元；若