數(shù)學(xué)建模與數(shù)學(xué)實驗 最短路問題課件

數(shù)學(xué)建模與數(shù)學(xué)實驗-最短路問題數(shù)學(xué)建模與數(shù)學(xué)實驗-最短路問題1實驗?zāi)康膶嶒瀮?nèi)容2、會用Matlab軟件求最短路1、了解最短路的算法及其應(yīng)用1、圖論的基本概念2、最短路問題及其算法3、最短路的應(yīng)用4、建模案例：最優(yōu)截斷切割問題5、實驗作業(yè)實驗?zāi)康膶嶒瀮?nèi)容2、會用Matlab軟件求最短路1、了解最短2圖論的基本概念一、圖的概念1、圖的定義2、頂點的次數(shù)

3、子圖二、圖的矩陣表示1、關(guān)聯(lián)矩陣2、鄰接矩陣圖論的基本概念一、圖的概念1、圖的定義23定義有序三元組G=(V,E,)稱為一個圖.圖的定義定義有序三元組G=(V,E,)稱為一個圖.圖的定4定義定義定義定義5數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件6數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件7頂點的次數(shù)頂點的次數(shù)8例在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù)。例在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù)。9子圖子圖10關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖11鄰接矩陣注：假設(shè)圖為簡單圖鄰接矩陣注：假設(shè)圖為簡單圖12數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件13最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂點之間的最短路最短路問題及其算法一、基本概念二、固14基本概念基本概念15數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件16固定起點的最短路最短路是一條路徑，且最短路的任一段也是最短路．

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

因此,可采用樹生長的過程來求指定頂點到其余頂點的最短路．固定起點的最短路最短路是一條路徑，且最短路的任17數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件18算法步驟：算法步驟：19TOMATLAB(road1)TOMATLAB20數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件21u1u2u3u4u5u6u7u8u1u2u3u4u5u6u7u822每對頂點之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（三）算法步驟每對頂點之間的最短路1、求距離矩陣的方法223算法的基本思想算法的基本思想24算法原理——

求距離矩陣的方法算法原理——求距離矩陣的方法25算法原理——

求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R．即當(dāng)vk被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求時求得，可由來查找任何點對之間最短路的路徑．算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑26ij算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j(luò)的最短路的路徑為：ij算法原理——查找最短路路徑的方法pkp2p1p3q127算法步驟算法步驟28TOMATLAB(road2(floyd))TOMATLAB29一、可化為最短路問題的多階段決策問題二、選址問題1、中心問題2、重心問題一、可化為最短路問題的多階段決策問題二、選址問題130可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題31數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件32數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件33數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件34

選址問題--中心問題TOMATLAB(road3(floyd))選址問題--中心問題TOMATLAB35S(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處。S(v1)=10,S(v2)=7,S(v3)=6,S(36

選址問題--重心問題選址問題--重心問題37實驗作業(yè)

生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率。生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機會?？梢?，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取最大收益。

某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為a=6萬單位，并以b=1萬單位/月速度遞增。若生產(chǎn)產(chǎn)品過剩，則需付單位產(chǎn)品單位時間（月）的庫存保管費C2=0.2元；若產(chǎn)品短缺，則單位產(chǎn)品單位時間的短期損失費C3=0.4元。假定生產(chǎn)率每調(diào)整一次帶有固定的調(diào)整費C1=1萬元，試問工廠如何制定當(dāng)年的生產(chǎn)策略，使工廠的總損失最??？實驗作業(yè)生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門38數(shù)學(xué)建模與數(shù)學(xué)實驗-最短路問題數(shù)學(xué)建模與數(shù)學(xué)實驗-最短路問題39實驗?zāi)康膶嶒瀮?nèi)容2、會用Matlab軟件求最短路1、了解最短路的算法及其應(yīng)用1、圖論的基本概念2、最短路問題及其算法3、最短路的應(yīng)用4、建模案例：最優(yōu)截斷切割問題5、實驗作業(yè)實驗?zāi)康膶嶒瀮?nèi)容2、會用Matlab軟件求最短路1、了解最短40圖論的基本概念一、圖的概念1、圖的定義2、頂點的次數(shù)

3、子圖二、圖的矩陣表示1、關(guān)聯(lián)矩陣2、鄰接矩陣圖論的基本概念一、圖的概念1、圖的定義241定義有序三元組G=(V,E,)稱為一個圖.圖的定義定義有序三元組G=(V,E,)稱為一個圖.圖的定42定義定義定義定義43數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件44數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件45頂點的次數(shù)頂點的次數(shù)46例在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù)。例在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù)。47子圖子圖48關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖49鄰接矩陣注：假設(shè)圖為簡單圖鄰接矩陣注：假設(shè)圖為簡單圖50數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件51最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂點之間的最短路最短路問題及其算法一、基本概念二、固52基本概念基本概念53數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件54固定起點的最短路最短路是一條路徑，且最短路的任一段也是最短路．

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

因此,可采用樹生長的過程來求指定頂點到其余頂點的最短路．固定起點的最短路最短路是一條路徑，且最短路的任55數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件56算法步驟：算法步驟：57TOMATLAB(road1)TOMATLAB58數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件59u1u2u3u4u5u6u7u8u1u2u3u4u5u6u7u860每對頂點之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（三）算法步驟每對頂點之間的最短路1、求距離矩陣的方法261算法的基本思想算法的基本思想62算法原理——

求距離矩陣的方法算法原理——求距離矩陣的方法63算法原理——

求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R．即當(dāng)vk被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求時求得，可由來查找任何點對之間最短路的路徑．算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑64ij算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j(luò)的最短路的路徑為：ij算法原理——查找最短路路徑的方法pkp2p1p3q165算法步驟算法步驟66TOMATLAB(road2(floyd))TOMATLAB67一、可化為最短路問題的多階段決策問題二、選址問題1、中心問題2、重心問題一、可化為最短路問題的多階段決策問題二、選址問題168可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題69數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件70數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件71數(shù)學(xué)建模與數(shù)學(xué)實驗最短路問題課件72

選址問題--中心問題TOMATLAB(road3(floyd))選址問題--中心問題TOMATLAB73S(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處。S(v1)=10,S(v2)=7,S(v3)=6,S(74

選址問題--重心問題選址問題--重心問題75實驗作業(yè)

生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率。生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機會。可見，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取