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