《圖論最短路問(wèn)題》PPT課件

《《圖論最短路問(wèn)題》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)學(xué)實(shí)驗(yàn)空軍工程大學(xué)理學(xué)院應(yīng)用數(shù)學(xué)教研室最短路問(wèn)題實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容2、會(huì)用Matlab軟件求最短路1、了解最短路的算法及其應(yīng)用1、圖論的基本概念2、最短路問(wèn)題及其算法3、最短路的應(yīng)用4、建模案例：最優(yōu)截?cái)嗲懈顔?wèn)題5、實(shí)驗(yàn)作業(yè)圖論的基本概念一、圖的概念1、圖的定義2、頂點(diǎn)的次數(shù)3、子圖二、圖的矩陣表示1、關(guān)聯(lián)矩陣2、鄰接矩陣返回定義有序三元組G=(V,E,)稱為一個(gè)圖.圖的定義定義定義返回頂點(diǎn)的次數(shù)例在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。返回子圖返回關(guān)聯(lián)矩陣注：假設(shè)圖為簡(jiǎn)單圖返回鄰接矩陣注：假設(shè)圖為簡(jiǎn)單圖返回最短路問(wèn)題及其算法一、基本概念二、固

2、定起點(diǎn)的最短路三、每對(duì)頂點(diǎn)之間的最短路返回基本概念返回固定起點(diǎn)的最短路最短路是一條路徑，且最短路的任一段也是最短路．假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹．因此,可采用樹生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路．算法步驟：TOMATLAB(road1)u1u2u3u4u5u6u7u8返回每對(duì)頂點(diǎn)之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（三）算法步驟返回算法的基本思想返回算法原理——求距離矩陣的方法返回算法原理——求路徑矩陣的方法在建立距離矩陣的同

3、時(shí)可建立路徑矩陣R．即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來(lái)查找任何點(diǎn)對(duì)之間最短路的路徑．返回ij算法原理——查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：返回算法步驟TOMATLAB(road2(floyd))返回一、可化為最短路問(wèn)題的多階段決策問(wèn)題二、選址問(wèn)題1、中心問(wèn)題2、重心問(wèn)題返回可化為最短路問(wèn)題的多階段決策問(wèn)題返回選址問(wèn)題--中心問(wèn)題TOMATLAB(road3(floyd))S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v

4、6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處。返回選址問(wèn)題--重心問(wèn)題返回實(shí)驗(yàn)作業(yè)生產(chǎn)策略問(wèn)題：現(xiàn)代化生產(chǎn)過(guò)程中，生產(chǎn)部門面臨的突出問(wèn)題之一，便是如何選取合理的生產(chǎn)率。生產(chǎn)率過(guò)高，導(dǎo)致產(chǎn)品大量積壓，使流動(dòng)資金不能及時(shí)回籠；生產(chǎn)率過(guò)低，產(chǎn)品不能滿足市場(chǎng)需要，使生產(chǎn)部門失去獲利的機(jī)會(huì)。可見，生產(chǎn)部門在生產(chǎn)過(guò)程中必須時(shí)刻注意市場(chǎng)需求的變化，以便適時(shí)調(diào)整生產(chǎn)率，獲取最大收益。某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為a=6萬(wàn)單位，并以b=1萬(wàn)單位/月速度遞增。若生產(chǎn)產(chǎn)品過(guò)剩，則需付單位產(chǎn)品單位時(shí)間（月）的庫(kù)存保管費(fèi)C2

5、=0.2元；若產(chǎn)品短缺，則單位產(chǎn)品單位時(shí)間的短期損失費(fèi)C3=0.4元。假定生產(chǎn)率每調(diào)整一次帶有固定的調(diào)整費(fèi)C1=1萬(wàn)元，試問(wèn)工廠如何制定當(dāng)年的生產(chǎn)策略，使工廠的總損失最??？返回