[理學(xué)]算法分析與設(shè)計第六章4可靠性設(shè)計(編輯修改稿)
2024-11-15 01:08 本頁面
【文章內(nèi)容簡介】 品，生產(chǎn)是周期性進(jìn)行的，即在每一個生產(chǎn)周期這 n種產(chǎn)品都要被制造。要生產(chǎn)這些產(chǎn)品有兩種開銷，一種是制造第 i種產(chǎn)品時所耗費(fèi)的資金 (1≤i≤n)，稱為生產(chǎn)成本，另一種是這些機(jī)器由制造第 i種產(chǎn)品變到制造第 j種產(chǎn)品時所耗費(fèi)的開支 cij ，稱為轉(zhuǎn)換成本。顯然，生產(chǎn)成本與生產(chǎn)順序無關(guān)。于是，希望找到一種制造這些產(chǎn)品的順序，使得制造這 n種產(chǎn)品的轉(zhuǎn)換成本和為最小。由于生產(chǎn)是周期進(jìn)行的，因此在開始下一周期生產(chǎn)時也要開支轉(zhuǎn)化成本，它等于由最后一種產(chǎn)品變到制造第一種產(chǎn)品的轉(zhuǎn)換成本。于是，可以把這個問題看成是一個具有 n個結(jié)點，邊成本為 cij的圖的貨郎擔(dān)問題。 20210901 版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 貨郎擔(dān)問題滿足最優(yōu)性原理 ? 不失一般性，假設(shè)周游路線是開始于結(jié)點 1并終止于結(jié)點 1的一條簡單路徑。每一條周游路線都由一條邊 1,k和一條由結(jié)點 k到結(jié)點 1的路徑所組成，其中 k∈ V{1}；而這條由結(jié)點 k到結(jié)點 1的路徑通過 V{1,k}的每個結(jié)點各一次。容易看出，如果這條周游路線是最優(yōu)的，那么這條由 k到 1的路徑必定是通過 V{1,k}中所有結(jié)點的由 k到 1的最短路徑，因此最優(yōu)性原理成立。 20210901 版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 g(i,S)： 表示由結(jié)點 i開始，通過 S中的所有結(jié)點，在結(jié)點 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) 當(dāng) |S|n1時， g(i,S)所需要的 i和 S的值是 i≠1， 1 S且 i S的值。 ??20210901 版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 例 ：考慮下圖，邊長由矩陣 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 版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 ?????????????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 } )
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1