[理學]算法分析與設計第六章4可靠性設計(編輯修改稿)
2024-11-15 01:08 本頁面
【文章內容簡介】 品，生產是周期性進行的，即在每一個生產周期這 n種產品都要被制造。要生產這些產品有兩種開銷，一種是制造第 i種產品時所耗費的資金 (1≤i≤n)，稱為生產成本，另一種是這些機器由制造第 i種產品變到制造第 j種產品時所耗費的開支 cij ，稱為轉換成本。顯然，生產成本與生產順序無關。于是，希望找到一種制造這些產品的順序，使得制造這 n種產品的轉換成本和為最小。由于生產是周期進行的，因此在開始下一周期生產時也要開支轉化成本，它等于由最后一種產品變到制造第一種產品的轉換成本。于是，可以把這個問題看成是一個具有 n個結點，邊成本為 cij的圖的貨郎擔問題。 20210901 版權所有：楊波，武漢科技大學理學院 貨郎擔問題滿足最優(yōu)性原理 ? 不失一般性，假設周游路線是開始于結點 1并終止于結點 1的一條簡單路徑。每一條周游路線都由一條邊 1,k和一條由結點 k到結點 1的路徑所組成，其中 k∈ V{1}；而這條由結點 k到結點 1的路徑通過 V{1,k}的每個結點各一次。容易看出，如果這條周游路線是最優(yōu)的，那么這條由 k到 1的路徑必定是通過 V{1,k}中所有結點的由 k到 1的最短路徑，因此最優(yōu)性原理成立。 20210901 版權所有：楊波，武漢科技大學理學院 g(i,S)： 表示由結點 i開始，通過 S中的所有結點，在結點 1終止的一條最短路徑長度。 g(1,V{1})： 表示一條最優(yōu)的周游路線長度。 } ) },1{,({m i n})1{,1( 12 kVkgcVg knk ???? ??} ) }{,({m in),( jSjgcSig ijSj ??? ?nicig i ???? 1,),( 1求解過程： |S|=1， 求 g(i,S) |S|=2， 求 g(i,S) 當 |S|n1時， g(i,S)所需要的 i和 S的值是 i≠1， 1 S且 i S的值。 ??20210901 版權所有：楊波，武漢科技大學理學院 例 ：考慮下圖，邊長由矩陣 c給出： 1 2 4 3 ?????????????0988120216109052021100c5),2( 21 ??? cg 6),3( 31 ??? cg15),3(})3{,2( 23 ???? gcg 18),4(})4{,2( 24 ???? gcg18),2(})2{,3( 32 ???? gcg 20),4(})4{,3( 34 ???? gcg13),2(})2{,4( 42 ???? gcg 15),3(})3{,4( 43 ???? gcg} ) }{,({m in),( jSjgcSig ijSj ??? ?8),4( 41 ??? cg20210901 版權所有：楊波，武漢科技大學理學院 ?????????????0988120216109052021100c( 2 , ) 5g ?? (3 , ) 6g ??( 2 , { 3 }) 1 5g ? ( 2 , { 4 } ) 18g ?( 3 , { 2 }) 1 8g ? ( 3 , { 4 }) 20g ?( 4 , { 2 } ) 13g ? ( 4 , { 3 }) 1 5g ?} ) }{,({m in),( jSjgcSig ijSj ??? ?( 4 , ) 8g ??23 24( 2 , { 3 , 4 } ) m i n { ( 3 , { 4 } ) , ( 4 , { 3 } ) } 2 5cgg c g ?? ? ?32 34( 3 , { 2 , 4 } ) m i n { ( 2 , { 4 } ) , ( 4 , { 2 } )
教學課件相關推薦
鄂ICP備17016276號-1