动态方法规划2

1、 物流系统工程动态规划方法动态规划方法 唐秋生重庆交通学院交通运输学院一、案例一：随即采购问题动态规划模型n1.假设某企业要在今后五周内采购一批原材料。事先只能估计未来五周的可能三种价格，而每种价格的概率变化如表所示。价格sk概率Pk4000.255000.356000.402.问题n该企业应该在哪周，按什么价格进行采该企业应该在哪周，按什么价格进行采购才是最佳的决策？购才是最佳的决策？3.动态规划原理第一步，首先要按问题的性质将问题划分为n个阶段，所划分的阶段必须既相互区分，又有一定的联系。一般按时间划分。第二步，确定状态变量sk表示第k阶段的状态Sk表示第k阶段的状态变量集合第三步，确定决

2、策变量uk表示第k阶段的决策变量Uk表示第k阶段的决策变量集合第五步，计算指标函数用于衡量所选定策略优劣的数量指标最有指标函数fk(sk)表示从地k阶段到最后一个阶段n采取最有策略所得到的最优效益值第四步，状态转移方程：sk+1=T(sk,uk)描述本阶段的状态与上一阶段状态和决策变量之间的关系方程3.动态规划原理2. 动态规划基本方程 fn+1(xn+1) = 0 或1 (边界条件) fk(xk) = opt urk ( xk , uk )* fk+1(xk+1) k = n,1二、案例一二、案例一n有一个物流公司打算向他的三个营业区有一个物流公司打算向他的三个营业区设立六个配送中心，每个区

3、至少一个，设立六个配送中心，每个区至少一个，所获利润如表所示。所获利润如表所示。n问设立的配送中心数应如何分配？问设立的配送中心数应如何分配？ 营业区配送中心数ABC12002101802280220230333022526043402302801.1.设设A Ai i表示在表示在A A区设立配送中心后还区设立配送中心后还剩有剩有i i家配送中心未设立；家配送中心未设立； B Bj j表示表示在在B B区设立配送中心后还剩有区设立配送中心后还剩有j j家配家配送中心未设立送中心未设立； C0 0表示公司已将六表示公司已将六家配送中心设立完毕；家配送中心设立完毕； S S6 6表示初始表示初始时

4、公司拥有六家配送中心待设立；时公司拥有六家配送中心待设立；如图所示。如图所示。n二、案例一二、案例一n2.动态规划发求解：将问题动态规划发求解：将问题划分为三个阶段，第一个阶划分为三个阶段，第一个阶段给段给A区分配物流中心，计区分配物流中心，计算从算从S6到到Ai的效益值。的效益值。决策过程效益值表K=1, f0(s0)=0 f1(s1)=maxd(S1,u1)+f0(s0)状态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.动态规划发求解：将问题划分为三个阶段，动态规划发求解：将问题划分为三个阶段，第一个阶段给第一个阶段给A区分配物流中心，计算从区分配物流中心，计算从S6到到Ai的效益值的效益值。A5A3A2B1B2B3B4C0A4S6200210225220230225220210180230260280280330340210220210B223020002803303402. 第二阶段，将剩下的中心数给第二阶段，将剩下的中心数给B区分区分配，计算从配，计算从Ai 到到Bj的效益值。的效益值。A5A3A2B1B2B3B4C0A4S62002102252

6、20230225220210180230260280280330340210220210B22302000770280330340540550490410A5A3A2B1B2B3B4C0A4S6200210225220230225220210180230260280280330340210220210B22302000770280330340540550490410决策过程效益值表K=2, （第二阶段）f2(s2)=maxd(S2,u2)+f1(s1)状态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. 第三阶段，将剩下的中心数第三阶段，将剩下的中心数给给C区分配，计算从区分配，计算从Bj到到C0的的效益值。效益值。决策过程效益值表K=3, f3(s3)=maxd(S3,u3)+f2(s2)状态f2(s2) +d(S3,u3)f3(s3)u3*u1=B4u1= B3u1=B2u1=B1C0410+280490+260540+230550+180770B22.动态规划发求解：第二阶段，将剩下的中心数给动态规划发求解：第二阶段，将剩下的中心数给B

8、区分配，计算从区分配，计算从Ai 到到Bj的效益值。的效益值。A5A3A2B1B2B3B4C0A4S6200210225220230225220210180230260280280330340210220210B223020007702803303405405504904102.动态规划发求解：将问题划分为三个阶段，第一个动态规划发求解：将问题划分为三个阶段，第一个阶段给阶段给A区分配物流中心，第二阶段，将剩下的中心区分配物流中心，第二阶段，将剩下的中心数给数给B区分配，第三阶段，再将剩下的全部分给区分配，第三阶段，再将剩下的全部分给C区区A5A3A2B1B2B3B4C0A4S62002102

9、25220230225220210180230260280280330340210220210B2230200200770280330340540550490410三、案例二三、案例二n1985年初，某公司考虑其设备卡车的更新问题。该卡车是1983型（1983年初出厂），一是用了两年。各种型号卡车的有关数据见表。文在这一年年初和以后的思念的年初应如何决策，才能使总的收益最大？各种车型使用年限及费用表各种车型使用年限及费用表车型1983型1985型已使用年数2345601234年收益1088641416161412年维修费3344511223根更新费25262728292022242526各种车

10、型使用年限及费用表各种车型使用年限及费用表车型1986型1987型1988型1989型已使用年数0123012010年收益16141412181616181220年维修费1122111111根更新费202224252092022212221第一步：设置变量第一步：设置变量nSk状态变量，第k阶段开始时汽车已使用的年数。nXk 决策变量，以采取该决策所达到的下一阶段的状态表示，各个阶段在每一状态下都只能取两个值：Sk+1和1。决策变量等于Sk+1时，表示这一年继续使用原有汽车（下一阶段状态等于Sk+1） ；决策变量等于1时，表示这一年年初更新汽车（下一阶段状态等于1）；nrk(sk)阶段k在状态

11、sk下汽车的年收益；第一步：设置变量第一步：设置变量rk(sk)阶段k在状态sk下汽车的年收益；uk(sk)阶段k在状态sk下汽车的年收益费ck(sk)阶段k在状态sk下更新汽车的费用；直接指标函数：1),()0()0(1),()()(,kkkkkkkkkkkkkkxscursxsusrxsd当当第一步：设置变量第一步：设置变量n状态转移方程nsk-1=xkn指标递推方程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年）已使用年数Sk01234601235年收益rk(sk)20161612124181614146年维修费uk(sk)11223511224根更新费ck(sk)2122242526292122242528第二步：绘制各阶段（各决策年第二步：绘制各阶段（各决策年份）资料表份）资料表截断k(年份)3（1987年）4（1986年）5（1985年）已使用年数Sk012401302年收益rk(sk)1814168161681410年维修费uk(sk)112411313根更新费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最优策略：最优策略：n1985年初更新汽车，n1986年至1989年一直使用原有汽车，5年纯收益为38。案例三：随即采购问题动态规划模型n1.假设某企业要在今后五周内采购一批原材料。事先只能估计未来五周的可能三种价格，而每种价格的概率变化如表所示。价格sk概率Pk4000.2

16、55000.356000.404.动态规划法求解过程n(1)划分阶段：每周为一个阶段，k=1,2,3,4,5.n(2)状态变量sk ：为第k周的原料价格（ sk=400，500，600 ）n(3)决策变量uk：第k周如果采购，则uk=1；否则， uk=0。n(4)SkE:表示当第k周决定等待，而在以后采购时的采购价格期望值。n(5)最有指标函数fk(sk):第k周实际价格为sk 市，从地k州至第5周采取最优策略所花费的最低期望价格(6)逆序递推公式为：逆序递推公式为：fk(sk)=minsk, SkEK=4,1SkE =f5(s5)=s5 s5 D5D5=400,500,600（7）第一步,当

17、k=5时n若前5周尚未购买，则无论本周价格如何，采购部门都必须购买，所以)(1700700)(1600600)(1500,500)(55555555采购，当采购，当采购，当ususussf（8）第二步,当k=4时n由于)(0700,610)(1600,600)(1500,500610,min,min)(6107004.06003.05003.0)700(4.0)600(3.0)500(3.044444444444555444等待，当采购，当采购，当所以，ususussSssffffSEDsE（9）第三步,当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等待，当等待，当采购，当所以，ususussSssffffSEDsE（10）第四步,当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等待，当等待，当采购，当所以，ususussSssffffSEDsE（11）第五步,当k=1时n由于)(0700, 2 .536)(0600, 2 .536)(1500,5002 .536,min,min)(2 .5368 .5514 .08 .5513 .05003 .