matlab最短路問題ppt課件-資料下載頁
2025-05-05 18:17本頁面
【正文】 點 X i 與Xi ? 1 之間有弧 (Xi ,Xi ? 1 ) ，其權 W(Xi ,Xi ? 1 ) 代表第 i 年初到第 i + 1 年初之間的費用 . 例如，弧 ( , )( )X Xb r3 41代表第 3 年初買新設備，第四年初決定用第三年買的用過一年的舊設備，其權則為第三年初的購置費與三、四年間的維修費之和，為 12 ＋ 5 ＝ 17（ 3 ）問題轉(zhuǎn)化為頂點 X b1 到 X rk6( ) 的最短路問題 . 五年的最優(yōu)購置費為 kb rkd X X? 1 2 3 4 51 6, , , ,( )m i n { ( , )}其中 d( X b1 , X rk6( ) ) 為頂點 X b1 到 X rk6( ) 的最短路的權 .求得最短路的權為 53 ，而兩條最短路分別為 X X X X X Xb r r b r r1 2 1 3 2 4 5 1 6 2? ? ? ? ?( ) ( ) ( ) ( ) 。X X X X X Xb r b r r r1 2 1 3 4 1 5 2 6 3? ? ? ? ?( ) ( ) ( ) ( )因此，計劃為第一、三年初購置新設備，或第一、四年初購置新設備，五年費用均最省，為 53 .也可構造加權有向圖 G 2( V , E ) .（ 1 ）頂點集 V ={ V V V V V V1 2 3 4 5 6, , , , , } ，V i 表第 i 年初購置新設備的決策， V 6表第五年底 .（ 2 ）弧集 E ={ ( , )V Vi j， i = 1 , 2 , 3 , 4 , 5 。 i j ≤ 6 } ,弧 ( , )V Vi j表第 i 年初購進一臺設備一直使用到第 j 年初的決策，其權 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– –，權為 53 ，與圖 G 1 ( V , E ) 的解相同．返回 （ 2 ） 計算在各點iv 設立服務設施的最大服務距離 )(ivS ． }{m a x)(1ijjidvS???? ??,2,1?i 選址問題 中心問題 例 2 某城市要建立一個消防站，為該市所屬的七個區(qū)服務，如圖所示．問應設在那個區(qū)，才能使它至最遠區(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,故應將消防站設在 v3處。 返回 選址問題 重心問題 例 3 某礦區(qū)有七個礦點，如圖所示．已知各礦點每天的產(chǎn)礦量)( jvq （標在圖的各頂點上）．現(xiàn)要從這七個礦點選一個來建造礦廠．問應選在哪個礦點，才能使各礦點所產(chǎn)的礦運到選礦廠所在地的總運力（千噸公里）最小．（ 1 ）求距離陣 D= ?? ?)( ijd ．（ 2 ） 計算各頂點作為選礦廠的總運力 )( ivm ijjji dvqvm ?? ??)()(1? ??,2,1?i（ 3 ） 求 kv 使 )}({m i n)(1 iikvmvm???? ，則 kv 就是選礦廠應設之礦點．此點稱為圖 G 的 重心 或 中位點 ．返回 實驗作業(yè) 生產(chǎn)策略問題 ：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率。生產(chǎn)率過高，導致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機會。可見，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取最大收益。 某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預知其產(chǎn)品在年初的需求量為 a=6萬單位，并以 b=1萬單位 /月速度遞增。若生產(chǎn)產(chǎn)品過剩，則需付單位產(chǎn)品單位時間（月）的庫存保管費 C2=；若產(chǎn)品短缺，則單位產(chǎn)品單位時間的短期損失費 C3=。假定生產(chǎn)率每調(diào)整一次帶有固定的調(diào)整費C1=1萬元，試問工廠如何制定當年的生產(chǎn)策略，使工廠的總損失最小？ 返回
教學課件相關推薦
鄂ICP備17016276號-1