沒(méi)有幻燈片標(biāo)題-大學(xué)數(shù)學(xué)網(wǎng)-我們致力于廣大學(xué)生和

1、數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn),最短路問(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、 鄰接矩陣,返回,圖的定義,定義,定義

2、,返回,頂點(diǎn)的次數(shù),例 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。,返回,子圖,返回,關(guān)聯(lián)矩陣,注：假設(shè)圖為簡(jiǎn)單圖,返回,鄰接矩陣,注：假設(shè)圖為簡(jiǎn)單圖,返回,最 短 路 問(wèn) 題 及 其 算 法,一、 基 本 概 念,二、固 定 起 點(diǎn) 的 最 短 路,三、每 對(duì) 頂 點(diǎn) 之 間 的 最 短 路,返回,基 本 概 念,,,,,,,,,,,,返回,固 定 起 點(diǎn) 的 最 短 路,最短路是一條路徑，且最短路的任一段也是最短路．,假設(shè)在u

3、0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹(shù)．,因此, 可采用樹(shù)生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路．,算法步驟：,TO MATLAB(road1),,,,,,,,,u1,u2,u3,,u4,u5,u6,u7,u8,,,,,,,,返回,每 對(duì) 頂 點(diǎn) 之 間 的 最 短 路,,1、求距離矩陣的方法,2、求路徑矩陣的方法,3、查找最短路路徑的方法,（一）算法的基本思想,（三）算法步驟,返回,算

4、法的基本思想,返回,算法原理—— 求距離矩陣的方法,返回,算法原理—— 求路徑矩陣的方法,在建立距離矩陣的同時(shí)可建立路徑矩陣R．,即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求 時(shí)求得 ，可由 來(lái)查找任何點(diǎn)對(duì)之間最短路的路徑．,返回,算法原理—— 查找最短路路徑的方法,,,,,,,,pk,p2,p1,p3,q1,q2,qm,則由點(diǎn)i到j(luò)的最短路的路徑為：,返回,算法步驟,TO MATLAB

5、(road2(floyd)),,,,,,返回,一、 可化為最短路問(wèn)題的多階段決策問(wèn)題,二、 選 址 問(wèn) 題,1、 中心問(wèn)題,2、 重心問(wèn)題,返回,可化為最短路問(wèn)題的多階段決策問(wèn)題,返回,選址問(wèn)題--中心問(wèn)題,TO MATLAB(road3(floyd)),S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5,S(v3)=6,故應(yīng)將消防站設(shè)在v3處。,返

6、回,選址問(wèn)題--重心問(wèn)題,返回,實(shí)驗(yàn)作業(yè),生產(chǎn)策略問(wèn)題：現(xiàn)代化生產(chǎn)過(guò)程中，生產(chǎn)部門(mén)面臨的突出問(wèn)題之一，便是如何選取合理的生產(chǎn)率。生產(chǎn)率過(guò)高，導(dǎo)致產(chǎn)品大量積壓，使流動(dòng)資金不能及時(shí)回籠；生產(chǎn)率過(guò)低，產(chǎn)品不能滿足市場(chǎng)需要，使生產(chǎn)部門(mén)失去獲利的機(jī)會(huì)?？梢?jiàn)，生產(chǎn)部門(mé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)