1、數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 最短路問題最短路問題實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容2會用會用MATLAB軟件求最短路軟件求最短路1了解最短路的算法及其運(yùn)用了解最短路的算法及其運(yùn)用1圖圖 論論 的的 基基 本本 概概 念念2最最 短短 路路 問問 題題 及及 其其 算算 法法3最最 短短 路路 的的 應(yīng)應(yīng) 用用4建模案例：最優(yōu)截斷切割問題建模案例：最優(yōu)截斷切割問題5實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè)圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的 概概 念念1圖的定義圖的定義2頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù) 3子圖二、二、 圖圖 的的 矩矩 陣陣 表表 示示1 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣2 鄰接矩陣鄰接矩陣前往前

2、往定義定義有序三元組G=(V,E, )稱為一個圖,假設(shè)：圖的定義圖的定義定義定義定義定義規(guī)定用記號和分別表示圖的頂點(diǎn)數(shù)和邊數(shù).前往前往頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù)4()4dv5)(3)(2)(444vdvdvd定定理理)(2)()(GvdGVv推推論論任何圖中奇次頂點(diǎn)的總數(shù)必為偶數(shù)例例 在一次聚會中，認(rèn)識奇數(shù)個人的人數(shù)一定是偶數(shù)在一次聚會中，認(rèn)識奇數(shù)個人的人數(shù)一定是偶數(shù).前往前往子圖子圖前往前往關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖前往前往鄰接矩陣鄰接矩陣注：假設(shè)圖為簡單圖無向賦權(quán)圖的鄰接矩陣可類似定義前往前往最最 短短 路路 問問 題題 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固

3、 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路三、每三、每 對對 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路前往前往基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路徑4521141vevevPvv定定義義（）任意兩點(diǎn)均有路徑的圖稱為連連通通圖圖（）起點(diǎn)與終點(diǎn)重合的路徑稱為圈圈（）連通而無圈的圖稱為樹樹前往前往固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路最短路是一條途徑，且最短路的任一段也是最短路 假設(shè)在u0-v0的最短路中只取一條，那么從u0到其他頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹 因此, 可采用樹生長的過

4、程來求指定頂點(diǎn)到其他頂點(diǎn)的最短路算法步驟：算法步驟：（4） 若S ，轉(zhuǎn) 2，否則，停止.（2）更新l v( )、z v ( )： vSVS,若l v( )l uW u v( )( , ) 則令l v( )=l uW u v( )( , ),z v ( )= u TO MATLAB(road1) 1 2 34 5 6 7 8前往前往uuuuuuuu每每 對對 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路(二二)算算法法原原理理1求間隔矩陣的方法求間隔矩陣的方法2求途徑矩陣的方法求途徑矩陣的方法3查找最短路途徑的方法查找最短路途徑的方法一一算法的根本思想算法的根本思想三三算法步驟算法步驟前往前往

5、算法的根本思想算法的根本思想前往前往算法原理算法原理 求間隔矩陣的方法求間隔矩陣的方法前往前往算法原理算法原理 求途徑矩陣的方法求途徑矩陣的方法)()0()0(ijrR, jrij)0(每求得一個 D(k)時，按下列方式產(chǎn)生相應(yīng)的新的 R(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立間隔矩陣的同時可建立途徑矩陣R 即當(dāng)k被插入任何兩點(diǎn)間的最短途徑時，被記錄在R(k)中，依次求 時求得 ，可由 來查找任何點(diǎn)對之間最短路的途徑)(D)(R前往前往)(Rvi j算法原理算法原理 查找最短路途徑的方法查找最短路途徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到

6、點(diǎn) j 的最短路的中間點(diǎn).pkp2p1p3q1q2qm那么由點(diǎn)i到j(luò)的最短路的途徑為：jqqqpppimk,21, 12前往前往算法步驟算法步驟Floyd算算法法：求任意兩點(diǎn)間的最短路(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，轉(zhuǎn)（） 例例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故從

7、v5到v1的最短路為51r所以從 v5到 v1的最短路徑為：1435.前往前往最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題二、二、 選選 址址 問問 題題1 中心問題中心問題2 重心問題重心問題前往前往可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題 例例 1 設(shè)備更新問題：企業(yè)使用一臺設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用.現(xiàn)要制定一個五年之內(nèi)的設(shè)備更新計(jì)劃，使得五年內(nèi)總的支付費(fèi)用最少. 已知該種設(shè)備在每年年初的價格為

8、：第一年第二年第三年第四年第五年1111121213 使用不同時間設(shè)備所需維修費(fèi)為：使用年限0112233445維修費(fèi)5681118（3）問題轉(zhuǎn)化為頂點(diǎn)Xb1到Xrk6( )的最短路問題.五年的最優(yōu)購置費(fèi)為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點(diǎn)Xb1到Xrk6( )的最短路的權(quán).前往前往 選址問題-中心問題則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱為圖的中中心心點(diǎn)點(diǎn) TO MATLAB(road3(floyd)05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065

9、 .42502545 .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,故應(yīng)將消防站設(shè)在v3處. 前往前往 選址問題-重心問題前往前往實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè) 消費(fèi)戰(zhàn)略問題：現(xiàn)代化消費(fèi)過程中，消費(fèi)部門面臨的突出問題之一，便是如何選取合理的消費(fèi)率.消費(fèi)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時回籠；消費(fèi)率過低，產(chǎn)品不能滿足市場需求，使消費(fèi)部門失去獲利的時機(jī).可見，消費(fèi)部門在消費(fèi)過程中必需時辰留意市場需求的變化，以便適時調(diào)整消費(fèi)率，獲取最大收益. 某消費(fèi)廠家年初要制定消費(fèi)戰(zhàn)略，已預(yù)知其產(chǎn)品在年初的需求量為a=