圖與網(wǎng)絡(luò)ppt課件(已改無錯字)
2023-06-12 07:51:22 本頁面
【正文】 還是繼續(xù)使用舊設(shè)備的決策。若購買新設(shè)備就要支付購置費；若繼續(xù)使用舊設(shè)備，則需支付維修費用。這種設(shè)備在四年之內(nèi)每年年初的價格以及使用不同時間（年）的設(shè)備的維修費用估計為： 年份 1 2 3 4 年初購價 10 11 12 13 維修費用 2 4 7 14 應(yīng)用舉例 ? 問題：制定一個四年之內(nèi)的設(shè)備更新計劃，使得四年之內(nèi)的設(shè)備購置費和維修費用之和最小。 ? 可以用求最短路問題的方法來解決總費用最少的設(shè)備更新計劃問題。 最短路求法（ 2） ? 構(gòu)造長度矩陣 L ? 計算 ( 2 ) ( 3 ) ( 2 ) ( )* , * , , 0nL L L L L L L? ? ?其中 * , [ ] , [ ] , [ ]ij m l ij ln ij m nA B C A a B b C c? ? ? ?1 1 2 2m i n{ * , * , , * }ij i j i j il ljc a b a b a b?0 0 0*00i k k ji k k ji k k j i k k ja o r baba b a b???? ?? ? ??最短路求法（ 2） ? 長度矩陣 0 1 2 0 0 00 0 3 3 0 70 0 0 2 2 00 0 0 0 0 30 0 0 0 0 60 0 0 0 0 0L????????? ??????????最短路求法（ 2） ( 2 ) ( 2 )0 0 4 4 4 80 0 0 5 5 60 0 0 0 0 5[ ] *0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0ijL l L L????????? ? ? ??????????( 2 ) 0ijl ?( 2 ) 0ijl ?表示 vi到 vj兩步中距離最短的一條 表示 vi到 vj兩步 不能 到達 最短路求法（ 2） ( 3 ) ( 3 )0006670 0 0 0 0 00 0 0 0 0 0[]0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0ijLl?????????? ??????????最短路求法（ 2） ( 4 ) ( 4 )0 0 0 0 0 9000000000000[]000000000000000000ijLl?????????? ??????????最短路求法（ 2） ( 5 ) ( 5 )000000000000000000[]000000000000000000ijLl?????????? ??????????最短路求法（ 2） ? 求任意兩點最短距離 A B C?? 均為 mxn矩陣 000 , 00 , 0m in( , ) , 0ij ijij ij ijijij ij ijij ij ij ijaba a bcb a ba b a b???????? ????? ??最短路求法（ 2） ( 2 ) ( 3 ) ( 4 ) ( 5 )m in0 1 2 4 4 70 0 3 3 5 60 0 0 2 2 50 0 0 0 0 30 0 0 0 0 60 0 0 0 0 0L L L L L L????????? ? ? ? ? ? ??????????矩陣中元素為兩點間最頓距離 最大流引入 ? 輸油管道網(wǎng)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1