數學建模案例分析第8講最短路問題課件

1、2022-4-22數學建模案例分析第8講最短路問題數學建模與數學實驗數學建模與數學實驗 最短路問題最短路問題2022-4-22數學建模案例分析第8講最短路問題實驗目的實驗目的實驗內容實驗內容2會用會用MATLAB軟件求最短路軟件求最短路1了解最短路的算法及其應用了解最短路的算法及其應用1圖圖 論論 的的 基基 本本 概概 念念2最最 短短 路路 問問 題題 及及 其其 算算 法法3最最 短短 路路 的的 應應 用用4建模案例：最優(yōu)截斷切割問題建模案例：最優(yōu)截斷切割問題5實驗作業(yè)實驗作業(yè)2022-4-22數學建模案例分析第8講最短路問題圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的

2、 概概 念念1圖的定義圖的定義2頂點的次數頂點的次數 3子圖子圖二、二、 圖圖 的的 矩矩 陣陣 表表 示示1 關聯矩陣關聯矩陣2 鄰接矩陣鄰接矩陣返回返回2022-4-22數學建模案例分析第8講最短路問題定義定義有序三元組G=(V,E, )稱為一個圖圖,如果：圖的定義圖的定義2022-4-22數學建模案例分析第8講最短路問題定義定義定義定義規(guī)定用記號和分別表示圖的頂點數和邊數.2022-4-22數學建模案例分析第8講最短路問題2022-4-22數學建模案例分析第8講最短路問題返回返回2022-4-22數學建模案例分析第8講最短路問題頂點的次數頂點的次數4()4dv5)(3)(2)(444vd

3、vdvd2022-4-22數學建模案例分析第8講最短路問題定定理理)(2)()(GvdGVv推推論論任何圖中奇次頂點的總數必為偶數例例 在一次聚會中，認識奇數個人的人數一定是偶數.返回返回2022-4-22數學建模案例分析第8講最短路問題子圖子圖返回返回2022-4-22數學建模案例分析第8講最短路問題關聯矩陣關聯矩陣注：假設圖為簡單圖返回返回2022-4-22數學建模案例分析第8講最短路問題鄰接矩陣鄰接矩陣注：假設圖為簡單圖2022-4-22數學建模案例分析第8講最短路問題無向賦權圖的鄰接矩陣可類似定義返回返回2022-4-22數學建模案例分析第8講最短路問題最最 短短 路路 問問 題題 及

4、及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 點點 的的 最最 短短 路路三、每三、每 對對 頂頂 點點 之之 間間 的的 最最 短短 路路返回返回2022-4-22數學建模案例分析第8講最短路問題基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路徑4521141vevevPvv2022-4-22數學建模案例分析第8講最短路問題定定義義（）任意兩點均有路徑的圖稱為連連通通圖圖（）起點與終點重合的路徑稱為圈圈（）連通而無圈的圖稱為樹樹返回返回2022-4-22數學建模案例分析第8講最

5、短路問題固固 定定 起起 點點 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路 假設在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點到其余頂點的最短路2022-4-22數學建模案例分析第8講最短路問題2022-4-22數學建模案例分析第8講最短路問題算法步驟：算法步驟：（4） 若S ，轉 2，否則，停止.（2）更新l v( )、z v( )： vSVS,若l v( )l uW u v( )( , ) 則令l v( )=l uW u v( )( , ),z v( )= u2022-4-22數學建模案例分

6、析第8講最短路問題 TO MATLAB(road1)2022-4-22數學建模案例分析第8講最短路問題2022-4-22數學建模案例分析第8講最短路問題 1 2 34 5 6 7 8返回返回uuuuuuuu2022-4-22數學建模案例分析第8講最短路問題每每 對對 頂頂 點點 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1求距離矩陣的方法求距離矩陣的方法2求路徑矩陣的方法求路徑矩陣的方法3查找最短路路徑的方法查找最短路路徑的方法（一）算法的基本思想（一）算法的基本思想（三）算法步驟（三）算法步驟返回返回2022-4-22數學建模案例分析第8講最短路問題算法的基本思想算法的基本思

7、想返回返回2022-4-22數學建模案例分析第8講最短路問題算法原理算法原理 求距離矩陣的方法求距離矩陣的方法返回返回2022-4-22數學建模案例分析第8講最短路問題算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法)()0()0(ijrR, jrij)0(每求得一個 D(k)時，按下列方式產生相應的新的 R(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距離矩陣的同時可建立路徑矩陣R 即當k被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求 時求得 ，可由 來查找任何點對之間最短路的路徑)(D)(R返回返回)(Rv2022-4-22數學建模案例

8、分析第8講最短路問題i j算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點 p1是點 i 到點 j 的最短路的中間點.pkp2p1p3q1q2qm則由點i到j的最短路的路徑為：jqqqpppimk,21, 12返回返回2022-4-22數學建模案例分析第8講最短路問題算法步驟算法步驟Floyd算算法法：求任意兩點間的最短路(2) 更新 d(i,j), r(i,j)對所有 i,j，若 d(i,k)+d(k,j)d(i,j)，則 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉（） 2022-4-22數學建模案例分析第

9、8講最短路問題例例 求下圖中加權圖的任意兩點間的距離與路徑 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故從v5到v1的最短路為51r所以從 v5到 v1的最短路徑為：1435.返回返回2022-4-22數學建模案例分析第8講最短路問題最最 短短 路路 的的 應應 用用一、一、 可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題二、二、 選選 址址 問問 題題1 中心問題中心問題2 重心問題重心問題返回返回2022-4-22數學建模案例分析第8講最短路問題可化為最短路

10、問題的多階段決策問題可化為最短路問題的多階段決策問題 例例 1 設備更新問題：企業(yè)使用一臺設備，每年年初，企業(yè)領導就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設備，就要支付一定的購置費用；若繼續(xù)使用，則需支付一定的維修費用.現要制定一個五年之內的設備更新計劃，使得五年內總的支付費用最少. 已知該種設備在每年年初的價格為：第一年第二年第三年第四年第五年1111121213 使用不同時間設備所需維修費為：使用年限0112233445維修費56811182022-4-22數學建模案例分析第8講最短路問題2022-4-22數學建模案例分析第8講最短路問題（3）問題轉化為頂點Xb1到Xrk6( )的最

11、短路問題.五年的最優(yōu)購置費為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點Xb1到Xrk6( )的最短路的權.2022-4-22數學建模案例分析第8講最短路問題返回返回2022-4-22數學建模案例分析第8講最短路問題 選址問題選址問題-中心問題中心問題則kv就是要求的建立消防站的地點此點稱為圖的中中心心點點 TO MATLAB(road3(floyd)2022-4-22數學建模案例分析第8講最短路問題05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .4250

12、2545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故應將消防站設在v3處. 返回返回2022-4-22數學建模案例分析第8講最短路問題 選址問題選址問題-重心問題重心問題返回返回2022-4-22數學建模案例分析第8講最短路問題實驗作業(yè)實驗作業(yè) 生產策略問題生產策略問題：現代化生產過程中，生產部門面臨的突出問題之一，便是如何選取合理的生產率.生產率過高，導致產品大量積壓，使流動資金不能及時回籠；生產率過低，產品不能滿足市場需要，使生產部門失去獲利的機會.可見，生產部門在生產過程中必須時刻注意市場需求的變化，