matlab最短路問題ppt課件-wenkub.com
2025-05-02 18:17 本頁面
【正文】 某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為 a=6萬單位，并以 b=1萬單位 /月速度遞增。 i j ≤ 6 } ,弧 ( , )V Vi j表第 i 年初購進(jìn)一臺設(shè)備一直使用到第 j 年初的決策，其權(quán) W ( , )V Vi j 表由這一決策在第 i 年初到第 j 年初的總費用，如W ( , )V V1 4 =1 1 +5 +6 +8 =3 0 .（ 3 ）問題轉(zhuǎn)化為求 V 1 到 V 6 的最短路問題，求得兩條最短路為 V V V1 4 6– – ， V V V1 3 6– –，權(quán)為 53 ，與圖 G 1 ( V , E ) 的解相同．返回 （ 2 ） 計算在各點iv 設(shè)立服務(wù)設(shè)施的最大服務(wù)距離 )(ivS ． }{m a x)(1ijjidvS???? ??,2,1?i 選址問題 中心問題 例 2 某城市要建立一個消防站，為該市所屬的七個區(qū)服務(wù)，如圖所示．問應(yīng)設(shè)在那個區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短．（ 1 ）用 F l o y d 算法求出距離矩陣 D= ?? ?)( ijd ．（ 3 ）求出頂點 kv ，使 )}({m i n)( 1 iik vSvS ????則 kv 就是要求的建立消防站的地點．此點稱為圖的 中心點 ． TO MATLAB (road3(floyd)) ???????????????????????DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=, S(v5)=7, S(v6)=7, S(v7)= S(v3)=6,故應(yīng)將消防站設(shè)在 v3處。 k =1 , 2 , … , i 1 } ,每個頂點代表年初的一種決策，其中頂點 X ib 代表第 i 年初購置新設(shè)備的決策，頂點 X ir k( ) 代表第 i 年初修理用過 k 年的舊設(shè)備的決策（ 2 ）弧集 E= { ( , ), ( , ),( ),X X X Xib i b irki b? ?1 1i= 1 , 2 , 3 , 4 。數(shù)學(xué)建模與數(shù)學(xué)實驗 最短路問題 實驗?zāi)康? 實驗內(nèi)容 會用 Matlab軟件求最短路 了解最短路的算法及其應(yīng)用 圖 論 的 基 本 概 念 最 短 路 問 題 及 其 算 法 最 短 路 的 應(yīng) 用 建模案例：最優(yōu)截斷切割問題 實驗作業(yè) 圖 論 的 基 本 概 念 一、 圖 的 概 念 圖的定義 頂點的次數(shù) 子圖 二、 圖 的 矩 陣 表 示 關(guān)聯(lián)矩陣 鄰接矩陣 返回 定義 有序三元組 G=(V,E, )稱為一個 圖 . ?[ 1 ] V= },{21 nvvv ? 是有窮非空集，稱為 頂點集 ， 其中的元素叫圖 G 的 頂點 .[ 2 ] E 稱為 邊集 ，其中的元素叫圖 G 的 邊 .[ 3 ] ? 是從邊集 E 到頂點集 V 中的有序或無序的元素 偶對的集合的映射，稱為 關(guān)聯(lián)函數(shù) .例 1 設(shè) G = ( V , E , ? ) ，其中 V = { v1 ,v2 , v3 , v4} ， E = { e1, e2 , e3, e4, e5},335414413312211)(,)(,)(,)(,)( vvevvevvevvevve ?????????? .G 的圖解如圖 .圖的定義 定義 在圖 G 中，與 V 中的有序偶 (vi ， v j ) 對應(yīng)的邊 e ，稱為圖的 有向邊 （或?。?，而與 V 中頂點的無序偶 v i v j 相對應(yīng)的邊 e ，稱為圖的 無向邊 . 每一條邊都是無向邊的圖，叫 無向圖 ；每一條邊都是有向邊的圖，稱為 有向圖 ；既有無向邊又有有向邊的圖稱為 混合圖 .定義 若將圖 G 的每一條邊 e 都對應(yīng)一個實數(shù) w (e ) ，稱 w (e ) 為邊的 權(quán) ，并稱圖 G 為 賦權(quán)圖 .規(guī)定用記號 ? 和 ? 分別表示圖的頂點數(shù)和邊數(shù) .常用術(shù)語：（１） 端點相同的邊稱為 環(huán) ．（２） 若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為 重邊 ．（３） 有邊聯(lián)結(jié)的兩個頂點稱為 相鄰的頂點 ，有一個公共端點的邊 稱為 相鄰的邊 ．（４） 邊和它的端點稱為互相 關(guān)聯(lián) 的． （５） 既沒有環(huán)也沒有平行邊的圖，稱為 簡單圖 ．（６） 任意兩頂點都相鄰的簡單圖，稱為 完備圖 ，記為 Kn，其中 n 為頂點的數(shù)目．( 7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1