運(yùn)籌學(xué)設(shè)備更新問題解題步驟

1、設(shè)備更新問題解題步驟解：可將其轉(zhuǎn)化為最短路徑問題用點(diǎn)vi表示“第i年年初購進(jìn)一臺新設(shè)備”，加設(shè)V6表示第5年底，從Vi到Vi+1-V6各畫一條弧，?。╒i,Vj）表示在第i年年初購進(jìn)的設(shè)備一直使用到第j年年初，即第j-1年年底。對圖中的每一條弧賦予權(quán)數(shù)。對于弧（Vi,Vj）,它的權(quán)數(shù)即為從第i年年初購進(jìn)設(shè)備使用到第j-1年年底所花費(fèi)的購置費(fèi)及維修費(fèi)的總和。例如：?。╒2,V3）的權(quán)數(shù)應(yīng)為第2年年初購置設(shè)備的價格11與第2年年初到第2年年底一年的維修費(fèi)用5之和。如下表3所示。A123456116223041592162230413172331417235186將權(quán)數(shù)Cij賦到圖1中，這樣在圖1中

2、求出從v1到v6的最短路，即可得5年內(nèi)總的支付費(fèi)用最少的設(shè)備更新計劃。41用Dijkstra算法求解。解：1.給起點(diǎn)標(biāo)以v1(0,s)2 .I=v1,J=v2,v3,v4,v5,v6弧集合(vi,vj)|vdI,vjeJ=(v1,v2),(v并有:s12=1+c12=1613一1+53=2214一1+c14=30s15=i+Ci5=41s16=1+c16=591,v3),(v1,v4),(v1,v5),(v1,v6)min(s12,s13,s14,s15,s16)=s12=16給弧(v1,v2)的終點(diǎn)v2標(biāo)以(16，1)3 .此時I=v1,v2J=v3,v4,v5,v6弧集合3,vj)|v產(chǎn)I

3、，vjeJ=(v1,v3)(v1,v4)(v1,v5)(v1,v6)(v2,v3)(v2,v4)(v2,v5)(v2,v6»并有：s23=l2+c23=16+16=32s24=l2+C24=16+22=38s25=l2+c25=16+30=46s26=l2+c26=16+41=57min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22此時，給弧(v1,v3)的終點(diǎn)v3標(biāo)以(22，1)4 .此時I=v1,v2,v3J=v4,v5,v6弧集合(vVj)|V產(chǎn)I,VjwJ=(vrV4),(VnV5),(V1,V6),(V2,V4),(V2,V5),(V2,V

4、6),(V3,V4),(V3,V5),(V3,V6)并有：S34=l3+034=22+17=39S35=l3+035=22+23=4536=l3+c36=22+31=53min(s14,S15,S16,S24,S25,S26,S34,S35,S36)=S14=3。此時，給弧(v1,V4)的終點(diǎn)V4標(biāo)以(30,1)5 .此時I=V1,V2,V3,V4J=V5,V6弧集合(Vi,Vj)|VFI,VjwJ=(V1,V5),(V1,V6),(V2,V5),(V2,V6),(V3,V5),(V3,V6),(V4,V5),(V4,V6)并有：S45=14+045=30+17=47S46=l4+c46=30

5、+23=53min(S26,S36,S35,s45)=S35=7此時，給弧(V3,V5)的終點(diǎn)V5標(biāo)以(7,3)6 .此時I=V1,V2,V3,V4,V5J=V6弧集合(Vi,Vj)|V產(chǎn)I,VjwJ=(V1,V6),(V2,V6),(V3,V6),(V4,V6),(V5,V6)并有：S56=l5+056=41+18=59min(S16,S26,S36,S46,S56)=S36=S46=53此時,給弧(V3,V6)和(V4,V6)的終點(diǎn)V6標(biāo)以(53,3）和（53,4），此時最短路徑為：v1-v3-V6即為：第1年初購置新設(shè)備使用到第2年底（第3年初），第3年初購置新設(shè)備使用到第5年底（第6年初