動態(tài)方法規(guī)劃2

1、 物流系統(tǒng)工程動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法 唐秋生重慶交通學(xué)院交通運(yùn)輸學(xué)院一、案例一：隨即采購問題動態(tài)規(guī)劃模型n1.假設(shè)某企業(yè)要在今后五周內(nèi)采購一批原材料。事先只能估計未來五周的可能三種價格，而每種價格的概率變化如表所示。價格sk概率Pk4000.255000.356000.402.問題n該企業(yè)應(yīng)該在哪周，按什么價格進(jìn)行采該企業(yè)應(yīng)該在哪周，按什么價格進(jìn)行采購才是最佳的決策？購才是最佳的決策？3.動態(tài)規(guī)劃原理第一步，首先要按問題的性質(zhì)將問題劃分為n個階段，所劃分的階段必須既相互區(qū)分，又有一定的聯(lián)系。一般按時間劃分。第二步，確定狀態(tài)變量sk表示第k階段的狀態(tài)Sk表示第k階段的狀態(tài)變量集合第三步，確定決

2、策變量uk表示第k階段的決策變量Uk表示第k階段的決策變量集合第五步，計算指標(biāo)函數(shù)用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)最有指標(biāo)函數(shù)fk(sk)表示從地k階段到最后一個階段n采取最有策略所得到的最優(yōu)效益值第四步，狀態(tài)轉(zhuǎn)移方程：sk+1=T(sk,uk)描述本階段的狀態(tài)與上一階段狀態(tài)和決策變量之間的關(guān)系方程3.動態(tài)規(guī)劃原理2. 動態(tài)規(guī)劃基本方程 fn+1(xn+1) = 0 或1 (邊界條件) fk(xk) = opt urk ( xk , uk )* fk+1(xk+1) k = n,1二、案例一二、案例一n有一個物流公司打算向他的三個營業(yè)區(qū)有一個物流公司打算向他的三個營業(yè)區(qū)設(shè)立六個配送中心，每個區(qū)

3、至少一個，設(shè)立六個配送中心，每個區(qū)至少一個，所獲利潤如表所示。所獲利潤如表所示。n問設(shè)立的配送中心數(shù)應(yīng)如何分配？問設(shè)立的配送中心數(shù)應(yīng)如何分配？ 營業(yè)區(qū)配送中心數(shù)ABC12002101802280220230333022526043402302801.1.設(shè)設(shè)A Ai i表示在表示在A A區(qū)設(shè)立配送中心后還區(qū)設(shè)立配送中心后還剩有剩有i i家配送中心未設(shè)立；家配送中心未設(shè)立； B Bj j表示表示在在B B區(qū)設(shè)立配送中心后還剩有區(qū)設(shè)立配送中心后還剩有j j家配家配送中心未設(shè)立送中心未設(shè)立； C0 0表示公司已將六表示公司已將六家配送中心設(shè)立完畢；家配送中心設(shè)立完畢； S S6 6表示初始表示初始時

4、公司擁有六家配送中心待設(shè)立；時公司擁有六家配送中心待設(shè)立；如圖所示。如圖所示。n二、案例一二、案例一n2.動態(tài)規(guī)劃發(fā)求解：將問題動態(tài)規(guī)劃發(fā)求解：將問題劃分為三個階段，第一個階劃分為三個階段，第一個階段給段給A區(qū)分配物流中心，計區(qū)分配物流中心，計算從算從S6到到Ai的效益值。的效益值。決策過程效益值表K=1, f0(s0)=0 f1(s1)=maxd(S1,u1)+f0(s0)狀態(tài)f0(s0) +d(S1,u1)f1(s1)u1*u1=(C0, A5) u1=(C0, A4) u1=(C0, A3) u1=(C0, A2)A5200280(C0, A5)A4280260(C0, A4)A3330

5、230(C0, A3)A2340180(C0, A2)2.動態(tài)規(guī)劃發(fā)求解：將問題劃分為三個階段，動態(tài)規(guī)劃發(fā)求解：將問題劃分為三個階段，第一個階段給第一個階段給A區(qū)分配物流中心，計算從區(qū)分配物流中心，計算從S6到到Ai的效益值的效益值。A5A3A2B1B2B3B4C0A4S6200210225220230225220210180230260280280330340210220210B223020002803303402. 第二階段，將剩下的中心數(shù)給第二階段，將剩下的中心數(shù)給B區(qū)分區(qū)分配，計算從配，計算從Ai 到到Bj的效益值。的效益值。A5A3A2B1B2B3B4C0A4S62002102252

6、20230225220210180230260280280330340210220210B22302000770280330340540550490410A5A3A2B1B2B3B4C0A4S6200210225220230225220210180230260280280330340210220210B22302000770280330340540550490410決策過程效益值表K=2, （第二階段）f2(s2)=maxd(S2,u2)+f1(s1)狀態(tài)f1(s1) +d(S2,u2)f2(s2)u2*u1=A5u1=A4u1= A3u1=A2B4200+210410A5B3200+2202

7、80+210490A4B2200+225280+220330+210540A3B1200+230280+225330+210340+210550A23. 第三階段，將剩下的中心數(shù)第三階段，將剩下的中心數(shù)給給C區(qū)分配，計算從區(qū)分配，計算從Bj到到C0的的效益值。效益值。決策過程效益值表K=3, f3(s3)=maxd(S3,u3)+f2(s2)狀態(tài)f2(s2) +d(S3,u3)f3(s3)u3*u1=B4u1= B3u1=B2u1=B1C0410+280490+260540+230550+180770B22.動態(tài)規(guī)劃發(fā)求解：第二階段，將剩下的中心數(shù)給動態(tài)規(guī)劃發(fā)求解：第二階段，將剩下的中心數(shù)給B

8、區(qū)分配，計算從區(qū)分配，計算從Ai 到到Bj的效益值。的效益值。A5A3A2B1B2B3B4C0A4S6200210225220230225220210180230260280280330340210220210B223020007702803303405405504904102.動態(tài)規(guī)劃發(fā)求解：將問題劃分為三個階段，第一個動態(tài)規(guī)劃發(fā)求解：將問題劃分為三個階段，第一個階段給階段給A區(qū)分配物流中心，第二階段，將剩下的中心區(qū)分配物流中心，第二階段，將剩下的中心數(shù)給數(shù)給B區(qū)分配，第三階段，再將剩下的全部分給區(qū)分配，第三階段，再將剩下的全部分給C區(qū)區(qū)A5A3A2B1B2B3B4C0A4S62002102

9、25220230225220210180230260280280330340210220210B2230200200770280330340540550490410三、案例二三、案例二n1985年初，某公司考慮其設(shè)備卡車的更新問題。該卡車是1983型（1983年初出廠），一是用了兩年。各種型號卡車的有關(guān)數(shù)據(jù)見表。文在這一年年初和以后的思念的年初應(yīng)如何決策，才能使總的收益最大？各種車型使用年限及費(fèi)用表各種車型使用年限及費(fèi)用表車型1983型1985型已使用年數(shù)2345601234年收益1088641416161412年維修費(fèi)3344511223根更新費(fèi)25262728292022242526各種車

10、型使用年限及費(fèi)用表各種車型使用年限及費(fèi)用表車型1986型1987型1988型1989型已使用年數(shù)0123012010年收益16141412181616181220年維修費(fèi)1122111111根更新費(fèi)202224252092022212221第一步：設(shè)置變量第一步：設(shè)置變量nSk狀態(tài)變量，第k階段開始時汽車已使用的年數(shù)。nXk 決策變量，以采取該決策所達(dá)到的下一階段的狀態(tài)表示，各個階段在每一狀態(tài)下都只能取兩個值：Sk+1和1。決策變量等于Sk+1時，表示這一年繼續(xù)使用原有汽車（下一階段狀態(tài)等于Sk+1） ；決策變量等于1時，表示這一年年初更新汽車（下一階段狀態(tài)等于1）；nrk(sk)階段k在狀態(tài)

11、sk下汽車的年收益；第一步：設(shè)置變量第一步：設(shè)置變量rk(sk)階段k在狀態(tài)sk下汽車的年收益；uk(sk)階段k在狀態(tài)sk下汽車的年收益費(fèi)ck(sk)階段k在狀態(tài)sk下更新汽車的費(fèi)用；直接指標(biāo)函數(shù)：1),()0()0(1),()()(,kkkkkkkkkkkkkkxscursxsusrxsd當(dāng)當(dāng)?shù)谝徊剑涸O(shè)置變量第一步：設(shè)置變量n狀態(tài)轉(zhuǎn)移方程nsk-1=xkn指標(biāo)遞推方程nfk(sk,xk)=dk(Sk,xk)，k=1;.nfk(sk,xk)=dk(Sk,xk)+fk-1(sk)，k=2，3，n;nfk(sk)=maxfk(sk,xk)第二步：繪制各階段（各決策年第二步：繪制各階段（各決策年份

12、）資料表份）資料表階段k（年份）1（1989年）2（1988年）已使用年數(shù)Sk01234601235年收益rk(sk)20161612124181614146年維修費(fèi)uk(sk)11223511224根更新費(fèi)ck(sk)2122242526292122242528第二步：繪制各階段（各決策年第二步：繪制各階段（各決策年份）資料表份）資料表截斷k(年份)3（1987年）4（1986年）5（1985年）已使用年數(shù)Sk012401302年收益rk(sk)1814168161681410年維修費(fèi)uk(sk)112411313根更新費(fèi)ck(sk)202224272022262025第三步：繪制各階段（各

13、決策年第三步：繪制各階段（各決策年份）決策表（逆序法份）決策表（逆序法k=1）S1f1(s1,x1)X1*f1(s1)X1=S1+1X1=1115-3215214-5314310-641049-7595-1-107-1計算說明計算說明f1(1，2)= d1(1，2)= r1(1)-u1(1)=16-1=15f1(1，1)= d1(1，1)= r1(0)-u1(0) -c1(1)=20-1-22=-3f1(6，7)= d1(6，7)= r1(6)-u1(6)=4-5=-1第三步：繪制各階段（各決策年第三步：繪制各階段（各決策年份）決策表（逆序法份）決策表（逆序法k=2）S2f2(s2,x2)X2

14、*f2(s2)X2=S2+1X2=1129102292228322321742151414計算說明計算說明f2(1，2)= d2(1，2)+f1(2)= r2(1)-u2(1)+ f1(2) =16-1+14=29f2(1，1)= d2(1，1)+ f1(1) = r2(0)-u2(0) c2(1)+ f1(1) =20-1-22+15=10第三步：繪制各階段（各決策年第三步：繪制各階段（各決策年份）決策表（逆序法份）決策表（逆序法k=3）S3f3(s3,x3)X3*f3(s3)X3=S3+1X3=113524235235223354819119第三步：繪制各階段（各決策年第三步：繪制各階段（

15、各決策年份）決策表（逆序法份）決策表（逆序法k=4）S4f4(s4,x4)X4*f4(s4)X4=S4+1X4=115028250324242或124第三步：繪制各階段（各決策年第三步：繪制各階段（各決策年份）決策表（逆序法份）決策表（逆序法k=5）S5f5(s5,x5)X5*f5(s5)X5=3X5=123138138n最優(yōu)策略：最優(yōu)策略：n1985年初更新汽車，n1986年至1989年一直使用原有汽車，5年純收益為38。案例三：隨即采購問題動態(tài)規(guī)劃模型n1.假設(shè)某企業(yè)要在今后五周內(nèi)采購一批原材料。事先只能估計未來五周的可能三種價格，而每種價格的概率變化如表所示。價格sk概率Pk4000.2

16、55000.356000.404.動態(tài)規(guī)劃法求解過程n(1)劃分階段：每周為一個階段，k=1,2,3,4,5.n(2)狀態(tài)變量sk ：為第k周的原料價格（ sk=400，500，600 ）n(3)決策變量uk：第k周如果采購，則uk=1；否則， uk=0。n(4)SkE:表示當(dāng)?shù)趉周決定等待，而在以后采購時的采購價格期望值。n(5)最有指標(biāo)函數(shù)fk(sk):第k周實(shí)際價格為sk 市，從地k州至第5周采取最優(yōu)策略所花費(fèi)的最低期望價格(6)逆序遞推公式為：逆序遞推公式為：fk(sk)=minsk, SkEK=4,1SkE =f5(s5)=s5 s5 D5D5=400,500,600（7）第一步,當(dāng)

17、k=5時n若前5周尚未購買，則無論本周價格如何，采購部門都必須購買，所以)(1700700)(1600600)(1500,500)(55555555采購，當(dāng)采購，當(dāng)采購，當(dāng)ususussf（8）第二步,當(dāng)k=4時n由于)(0700,610)(1600,600)(1500,500610,min,min)(6107004.06003.05003.0)700(4.0)600(3.0)500(3.044444444444555444等待，當(dāng)采購，當(dāng)采購，當(dāng)所以，ususussSssffffSEDsE（9）第三步,當(dāng)k=3時n由于)(0700,574)(0600,574)( 1500,500574,mi

18、n,min)(5746104 . 06003 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 033333333333444333等待，當(dāng)?shù)却?，?dāng)采購，當(dāng)所以，ususussSssffffSEDsE（10）第四步,當(dāng)k=2時n由于)(0700,8 .551)(0600,8 .551)(1500,500574,min,min)(8 .5515744 .05743 .05003 .0)700(4 .0)600(3 .0)500(3 .022222222222333222等待，當(dāng)?shù)却?，?dāng)采購，當(dāng)所以，ususussSssffffSEDsE（11）第五步,當(dāng)k=1時n由于)(0700, 2 .536)(0600, 2 .536)(1500,5002 .536,min,min)(2 .5368 .5514 .08 .5513 .05003 .