十動態(tài)規(guī)劃的應(yīng)用---生產(chǎn)與存儲,設(shè)備更新問題

1、 生產(chǎn)與存貯問題生產(chǎn)與存貯問題 生產(chǎn)周期分為生產(chǎn)周期分為 n 個階段，已知個階段，已知 最初庫存量：最初庫存量： x1 階段市場的需求：階段市場的需求：dk 生產(chǎn)的固定成本：生產(chǎn)的固定成本：K 單位產(chǎn)品的消耗費(fèi)用：單位產(chǎn)品的消耗費(fèi)用：L 單位產(chǎn)品的階段庫存費(fèi)用：單位產(chǎn)品的階段庫存費(fèi)用：h 倉庫容量：倉庫容量：M 階段生產(chǎn)能力為階段生產(chǎn)能力為B 一個生產(chǎn)部門，如何在已知生產(chǎn)成本、庫存費(fèi)用和一個生產(chǎn)部門，如何在已知生產(chǎn)成本、庫存費(fèi)用和各階段市場需求條件下，決定各階段產(chǎn)量，使計劃內(nèi)的各階段市場需求條件下，決定各階段產(chǎn)量，使計劃內(nèi)的費(fèi)用總和為最小的問題。費(fèi)用總和為最小的問題。 問如何安排各階段產(chǎn)量，使

2、計劃周期內(nèi)的費(fèi)用總和問如何安排各階段產(chǎn)量，使計劃周期內(nèi)的費(fèi)用總和最小。最小。Mxk不能超過階段不能超過階段 k 至階段至階段 n 的需求總量的需求總量xk dk+ dk+1+ dn，k =1, 2, , n階段階段 k 的的初始庫存量初始庫存量，x1已知，已知，xn+1 = 00 xk min M， dk+ dk+1+ dn，（k =1, 2, , n）狀態(tài)變量狀態(tài)變量 xk：不能超過庫存容量不能超過庫存容量M，決策變量決策變量 uk：不超過生產(chǎn)能力不超過生產(chǎn)能力Bukkkkuxd階段階段 k 的產(chǎn)量的產(chǎn)量uk dk+ dk + 1+ + dn- xk不小于該階段的需求和庫存量之差，不小于該階

3、段的需求和庫存量之差， 不超過不超過 kn 階段的總需求減去第階段的總需求減去第 k 階段初的階段初的庫存量，庫存量，dk- -xk uk minB，dk+ dk+1+ dn- -xk 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程kkkkduxx1為階段生產(chǎn)費(fèi)用和庫存費(fèi)用之和，即為階段生產(chǎn)費(fèi)用和庫存費(fèi)用之和，即)(),(kkkkkkkduxhLuKuxg階段階段 k 的生產(chǎn)費(fèi)用的生產(chǎn)費(fèi)用k 階段末的庫存費(fèi)用階段末的庫存費(fèi)用動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程階段效益階段效益)()(min)(11)(kkkkkkxDukkxfduxhLuKxfkkkfn+1（xn+1）= 0，k = 1, 2, , ndk- -xk

4、uk minB，dk+ dk+1+ dn- -xk例5 已知 n = 3，K = 8，L = 2，h = 2，x1 = 1，M = 4，x4 = 0，B = 6，d1 = 3，d2 = 4，d3 = 3，求解生產(chǎn)與庫存問題。 解：遞推方程)()(min)(11)(kkkkkkxDukkxfduxhLuKxfkkkf 4 ( x4 ) = 0，k = 1, 2, 3 33 , 6min33333328min3xuxuxfk當(dāng)當(dāng)時時=8+2(3-x3)=14-2x3 3,min,min033dMdMxnkii倉庫容量：倉庫容量：4dk-xk uk minB，dk+ dk + 1+ dn-xk1kx

5、 若 x3 = 0, u*3 (0) = 3則 f3(0) =14若 x3 = 1, 則 f3 (1) = 12 u*3 (1) = 2若 x3 = 2, 則 f3 (2) = 10 u*3 (2) = 1 若 x3 = 3, 則 f3 (3) = 8 u*3 (0) = 0f3(x3)= 14-2x3 u3 =3-x3 x3：03 u3 x30123f3(x3)u*3(x3)0141431121222101013880kkkkduxx1k =22223duxx容量44+3uk dk-xk4-x2 u2 min6,7-x2 f2 (x2 )= min 8+2u2+2(x2 +u2-4)+ f3

6、 (x2 + u2-4)4-x2 u2 minB，d2+ d3-x2=min6,7-x20 x2 minM，d2+ d3 =min4,7=4u*2 (0) = 4x2 = 04-x2 u2 min6,7-x2 30104201221814016min)4()4(228min)0(23226, 5 , 422ufuufux2 = 1)3()3(228min) 1 (23226, 5 , 4, 322ufuufu288620104281221614014minu*2 (1) = 3 u3 x30123f3(x3)u*3(x3)01414311212221010138804-x2 u2 min6,7

7、-x2 x2 = 2u*2 (2) = 24-x2 u2 min6,7-x2 )2()2(228min)2(23225 , 4, 3 , 222ufuufu268618104161221414012minx2 = 3)1() 1(228min)3(23224, 3 , 2, 122ufuufu248616104141221214010minu*2 (3) = 1x2 = 4u*2(4)=04-x2 u2 min6,7-x2 )(228min)4(23223 , 2, 1 , 022ufuufu22861410412122101408min結(jié)果見下表： u1 x123456f1(x1) u*1(

8、x1)112+0+30 14+2+28 16+4+26 18+6+24 20+8+22422k =1f2=302 u1 6x2= x1+ u1-d1=1+ u1-3= u1- 2u*1 (1) = 2x1 =1)2()2(228min22116, 5 , 4, 3 , 21ufuuu)()(228min) 1 (2211116, 5 , 4, 3 , 211xfduxufu422282024618264162821430012min u2 x2 0 1 2 3 4 5 6 f2(x2) u*2(x2) 0 16+0+14 18+2+12 20+4+10 30 4 1 14+0+14 16+2+

9、12 18+4+10 20+6+8 28 3 2 12+0+14 14+2+12 16+4+10 18+6+8 26 2 3 10+0+14 12+2+12 14+4+10 16+6+8 24 1 4 8+0+14 10+2+12 12+4+10 14+6+8 22 0 f3=14 u3 x30123f3(x3)u*3(x3)01 41 4311 21 2221 01 013880最優(yōu)決策為最優(yōu)決策為 1，0，0，0 x2=u1-2=0 x3=x2+u2-d2=0+4-4=0最優(yōu)路線為最優(yōu)路線為最優(yōu)目標(biāo)函數(shù)值為最優(yōu)目標(biāo)函數(shù)值為42。（狀態(tài)變量）（狀態(tài)變量）u*1 (1) = 2，u*2 (0)

10、 = 4， u*3 (0) = 3 設(shè)備更新問題提法如下（以一臺機(jī)器為例）：設(shè)備更新問題提法如下（以一臺機(jī)器為例）： n為設(shè)備計劃使用年數(shù)。為設(shè)備計劃使用年數(shù)。 Ik(t) 為第為第k年（階段）機(jī)器役齡為年（階段）機(jī)器役齡為t年的一臺機(jī)器年的一臺機(jī)器運(yùn)行（在使用一年）所得的收入。運(yùn)行（在使用一年）所得的收入。 Ok(t) 為第為第k年機(jī)器役齡為年機(jī)器役齡為t年的一臺機(jī)器運(yùn)行（再年的一臺機(jī)器運(yùn)行（再使用一年）時所需運(yùn)行的費(fèi)用（或維修費(fèi)用）使用一年）時所需運(yùn)行的費(fèi)用（或維修費(fèi)用） 。 Ck(t) 為第為第k年機(jī)器役齡為年機(jī)器役齡為t年的一臺機(jī)器更新時所年的一臺機(jī)器更新時所需的凈費(fèi)用（處理一臺役齡為

11、需的凈費(fèi)用（處理一臺役齡為t的舊設(shè)備，買進(jìn)一臺新的舊設(shè)備，買進(jìn)一臺新設(shè)備的更新凈費(fèi)用）。設(shè)備的更新凈費(fèi)用）。 設(shè)備更新問題設(shè)備更新問題 為折扣因子，表示一年以后的收入是上一年的為折扣因子，表示一年以后的收入是上一年的 單單位。位。 要求在要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺新的，使設(shè)備還是更換一臺新的，使n年內(nèi)總效益最大？年內(nèi)總效益最大？建立動態(tài)規(guī)劃模型如下：建立動態(tài)規(guī)劃模型如下： 階段階段k（k=1，2，n）表示計劃使用該設(shè)備的）表示計劃使用該設(shè)備的年限數(shù)。年限數(shù)。 狀態(tài)變量狀態(tài)變量sk：第：第k年初，設(shè)備已使用過的年數(shù)，即年初，設(shè)

12、備已使用過的年數(shù)，即役齡。役齡。 決策變量決策變量xk：是第：是第k年初更新，還是保留使用舊設(shè)年初更新，還是保留使用舊設(shè)備，分別用備，分別用R ，K表示。表示。RxKxsskkkk111 階段效益為：階段效益為：RxKxscOIsOsIxsvkkkjjjkjkjkkj)() 0 () 0 ()()(),( 狀態(tài)轉(zhuǎn)移方程為：狀態(tài)轉(zhuǎn)移方程為： 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù)fk(sk)：表示第：表示第k年初，使用一臺已用了年初，使用一臺已用了sk年的設(shè)備，到第年的設(shè)備，到第n年末的最大收益。年末的最大收益。0)()(),(max)(1111nnkkkkjRorKxkksfsfxsvsfk實際上實際上11

13、1( )( )()( )max(0)(0)( )(1)kkkkkkkkkkkkkkkI sO sfsxKf sIOc sfxR例例7：設(shè)某臺新設(shè)備的年效益及年均維修費(fèi)用、更新：設(shè)某臺新設(shè)備的年效益及年均維修費(fèi)用、更新凈費(fèi)用如下表，試確定今后五年內(nèi)的更新策略，使總凈費(fèi)用如下表，試確定今后五年內(nèi)的更新策略，使總效益最大。（設(shè)效益最大。（設(shè) =1） 動態(tài)規(guī)劃的基本方程為動態(tài)規(guī)劃的基本方程為解：解：n=5RxKxscOIsOsIsfk555555555555)() 0() 0()()(max)(5狀態(tài)變量狀態(tài)變量s5可取可取1，2，3，4 役齡項目012345效益IK(t)54.543.7532.5運(yùn)

14、行費(fèi)OK(t) 0.511.522.53更新費(fèi)CK(t) 0.51.5 2.22.533.5單位：萬元單位：萬元KxRxKxcOIOIf) 1 (5 . 35 . 15 . 0515 . 4max) 1 () 0() 0() 1 () 1 (max) 1 (555555555KxRxKxcOIOIf)2(5 . 22 . 25 . 055 . 15 . 4max)2()0()0()2()2(max)2(555555555賣掉役齡賣掉役齡2年的設(shè)年的設(shè)備，買入新設(shè)備備，買入新設(shè)備的更新費(fèi)用的更新費(fèi)用RxRxKxcOIOIf)3(25 . 25 . 05275. 3max)3()0()0()3()

15、3(max)3(555555555RxRxKxcOIOIf)4(5 . 135 . 055 . 23max)4()0()0()4()4(max)4(555555555RxKxfscOIsfsOsIsfk445444445444444) 1 ()() 0 () 0 () 1()()(max)(4狀態(tài)變量狀態(tài)變量s4可取可取1，2，3RxRxKxfscOIsfsOsIfs) 1 (5 . 65 . 35 . 15 . 055 . 215 . 4max) 1 ()() 0() 0() 1()()(max) 1 (44454444454444144RxRxKxfscOIsfsOsIfs)2(8 . 5

16、5 . 32 . 25 . 0525 . 14max) 1 ()()0()0() 1()()(max)2(44454444454444244RxRxKxfscOIsfsOsIfs) 3(5 . 55 . 35 . 25 . 055 . 1275. 3max) 1 ()()0()0() 1()()(max) 3(44454444454444344RxKxfscOIsfsOsIsfk334333334333333) 1 ()() 0 () 0 () 1()()(max)(3此時此時s3可取可取1或或2RxRxKxfscOIsfsOsIfs) 1 (5 . 95 . 65 . 15 . 058 .

17、515 . 4max) 1 ()() 0() 0() 1()()(max) 1 (33343333343333133RxRxKxfscOIsfsOsIfs)2(8 . 85 . 62 . 25 . 055 . 55 . 14max) 1 ()()0()0() 1()()(max)2(33343333343333233RxKxfscOIsfsOsIsfk223222223222222) 1 ()() 0() 0() 1()()(max)(2由于狀態(tài)由于狀態(tài)s2只能取只能取1，所以有，所以有RxRxKxfscOIsfsOsIfs) 1 (5 .125 . 95 . 15 . 058 . 815 .

18、 4max) 1 ()()0()0() 1()()(max) 1 (22232222232222122RxKxfscOIsfsOsIsfk112111112111111) 1 ()() 0 () 0 () 1()()(max)(1由于狀態(tài)由于狀態(tài)s1只能取只能取0，所以有，所以有KxRxKxfscOIsfsOsIfs) 0(175 .125 . 05 . 055 .125 . 05max) 1 ()() 0() 0() 1()()(max) 0(11121111121111011尋找最優(yōu)解，上述過程遞推回去。尋找最優(yōu)解，上述過程遞推回去。當(dāng)當(dāng)x*1(0)=K，由狀態(tài)轉(zhuǎn)移方程，由狀態(tài)轉(zhuǎn)移方程 本例的最優(yōu)策略是本例的最優(yōu)策略是K，R，R，R，K，即第一，即第一年初購買的設(shè)備到第二、三、四年初各更換一次，用年初購買的設(shè)備到第二、三、四年初各更換一次，用到第五年年末，總效益為到第五年年末，總效益為17萬元。萬元。RxKxss111211s2=1，查，查f2(1)得得x*2=RRxKxss222311s3=1，查，查f3(1)得得x*3=Rs4=1，查，查f4(1)得得x*4=Rs5=1，查，查f5(1)得得x*5=K 練習(xí)