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