數(shù)學(xué)建模案例分析第講最短路問題公開課一等獎(jiǎng)優(yōu)質(zhì)課大賽微課獲獎(jiǎng)?wù)n件

1、數(shù)學(xué)建模與數(shù)學(xué)試驗(yàn) 最短路問題10/10/數(shù)學(xué)建模第1頁實(shí)驗(yàn)?zāi)吭囼?yàn)內(nèi)容2會用MATLAB軟件求最短路1了解最短路算法及其應(yīng)用1圖 論 基 本 概 念2最 短 路 問 題 及 其 算 法3最 短 路 應(yīng) 用4建模案例：最優(yōu)截?cái)嗲懈顔栴}5試驗(yàn)作業(yè)10/10/數(shù)學(xué)建模第2頁圖 論 基 本 概 念一、 圖 概 念1圖定義2頂點(diǎn)次數(shù) 3子圖二、 圖 矩 陣 表 示1 關(guān)聯(lián)矩陣2 鄰接矩陣返回10/10/數(shù)學(xué)建模第3頁定義有序三元組G=(V,E, )稱為一個(gè)圖,假如：圖定義10/10/數(shù)學(xué)建模第4頁定義定義10/10/數(shù)學(xué)建模第5頁10/10/數(shù)學(xué)建模第6頁返回10/10/數(shù)學(xué)建模第7頁頂點(diǎn)次數(shù)10/10

2、/數(shù)學(xué)建模第8頁例 在一次聚會中，認(rèn)識奇數(shù)個(gè)人人數(shù)一定是偶數(shù).返回10/10/數(shù)學(xué)建模第9頁子圖返回10/10/數(shù)學(xué)建模第10頁關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回10/10/數(shù)學(xué)建模第11頁鄰接矩陣注：假設(shè)圖為簡單圖10/10/數(shù)學(xué)建模第12頁返回10/10/數(shù)學(xué)建模第13頁最 短 路 問 題 及 其 算 法一、 基 本 概 念二、固 定 起 點(diǎn) 最 短 路三、每 對 頂 點(diǎn) 之 間 最 短 路返回10/10/數(shù)學(xué)建模第14頁基 本 概 念10/10/數(shù)學(xué)建模第15頁返回10/10/數(shù)學(xué)建模第16頁固 定 起 點(diǎn) 最 短 路最短路是一條路徑，且最短路任一段也是最短路 假設(shè)在u0-v0最短路中只取一

3、條，則從u0到其余頂點(diǎn)最短路將組成一棵以u0為根樹 所以, 可采取樹生長過程來求指定頂點(diǎn)到其余頂點(diǎn)最短路10/10/數(shù)學(xué)建模第17頁10/10/數(shù)學(xué)建模第18頁算法步驟：10/10/數(shù)學(xué)建模第19頁 TO MATLAB(road1)10/10/數(shù)學(xué)建模第20頁10/10/數(shù)學(xué)建模第21頁 1 2 34 5 6 7 8返回10/10/數(shù)學(xué)建模第22頁每 對 頂 點(diǎn) 之 間 最 短 路1求距離矩陣方法2求路徑矩陣方法3查找最短路路徑方法（一）算法基本思想（三）算法步驟返回10/10/數(shù)學(xué)建模第23頁算法基本思想返回10/10/數(shù)學(xué)建模第24頁算法原理 求距離矩陣方法返回10/10/數(shù)學(xué)建模第25頁

4、算法原理 求路徑矩陣方法在建立距離矩陣同時(shí)可建立路徑矩陣R 即當(dāng)k被插入任何兩點(diǎn)間最短路徑時(shí)，被統(tǒng)計(jì)在R(k)中，依次求 時(shí)求得 ，可由 來查找任何點(diǎn)對之間最短路路徑返回)(nR10/10/數(shù)學(xué)建模第26頁i j算法原理 查找最短路路徑方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)最短路路徑為：返回10/10/數(shù)學(xué)建模第27頁算法步驟10/10/數(shù)學(xué)建模第28頁 TOMATLAB(road2(floyd)返回10/10/數(shù)學(xué)建模第29頁一、 可化為最短路問題多階段決議問題二、 選 址 問 題1 中心問題2 重心問題返回10/10/數(shù)學(xué)建模第30頁可化為最短路問題多階段決議問題10/10/數(shù)學(xué)建模

5、第31頁10/10/數(shù)學(xué)建模第32頁10/10/數(shù)學(xué)建模第33頁返回10/10/數(shù)學(xué)建模第34頁 選址問題-中心問題 TO MATLAB(road3(floyd)10/10/數(shù)學(xué)建模第35頁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處. 返回10/10/數(shù)學(xué)建模第36頁 選址問題-重心問題返回10/10/數(shù)學(xué)建模第37頁試驗(yàn)作業(yè) 生產(chǎn)策略問題：當(dāng)代化生產(chǎn)過程中，生產(chǎn)部門面臨突出問題之一，便是怎樣選取合理生產(chǎn)率.生產(chǎn)率過高，造成產(chǎn)品大量積壓，使流動資金不能及時(shí)回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去贏利機(jī)會.可見，生產(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元；若產(chǎn)品短缺，