最短路徑問題

1、數(shù)學(xué)建模與數(shù)學(xué)實驗 最短路問題1實驗?zāi)康膶嶒瀮?nèi)容2、會用Matlab軟件求最短路1、了解最短路的算法及其應(yīng)用1、圖 論 的 基 本 概 念2、最 短 路 問 題 及 其 算 法3、最 短 路 的 應(yīng) 用4、建模案例：最優(yōu)截斷切割問題5、實驗作業(yè)2圖 論 的 基 本 概 念一、 圖 的 概 念1、圖的定義2、頂點的次數(shù) 3、子圖二、 圖 的 矩 陣 表 示1、 關(guān)聯(lián)矩陣2、 鄰接矩陣返回3定義有序三元組G=(V,E, )稱為一個圖.圖的定義4定義定義5返回6頂點的次數(shù)7例 在一次聚會中，認(rèn)識奇數(shù)個人的人數(shù)一定是偶數(shù)。返回8子圖返回9關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回10鄰接矩陣注：假設(shè)圖為簡單圖11

2、返回12最 短 路 問 題 及 其 算 法一、 基 本 概 念二、固 定 起 點 的 最 短 路三、每 對 頂 點 之 間 的 最 短 路返回13基 本 概 念14返回15固 定 起 點 的 最 短 路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構(gòu)成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點到其余頂點的最短路16算法步驟：17 TO MATLAB(road1)18u1u2u3u4u5u6u7u8返回19每 對 頂 點 之 間 的 最 短 路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法

3、的基本思想（三）算法步驟返回20算法的基本思想返回21算法原理 求距離矩陣的方法返回22算法原理 求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R 即當(dāng)vk被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求 時求得 ，可由 來查找任何點對之間最短路的路徑返回23ij算法原理 查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j(luò)的最短路的路徑為：返回24算法步驟25 TO MATLAB(road2(floyd)返回26一、 可化為最短路問題的多階段決策問題二、 選 址 問 題1、 中心問題2、 重心問題返回27可化為最短路問題的多階段決策問題28返回29 選址問題-中心問題 T

4、O MATLAB(road3(floyd)30S(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處。 返回31 選址問題-重心問題返回32實驗作業(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)品單位時間的短