动态规划的基本概念和基本方程.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5.2 动态规划的基本概念和基本方程,(一)基本概念,(1)阶段：k,(2)状态变量：S,k,(3)决策变量：u,k,(S,k,),(4)策略,(5)状态转移方程：S,k1,T(S,k,，u,k,),(6)指标函数：V,k，n,(S,k,),(7)最优指标函数：f,k,(S,k,),1,(二)前例1,(1)阶段：k1，2，6 n=6,(2)状态变量：S,k,第k阶段所处的位置,状态集合 如S,2,:(B,1,B,2,),(3)决策变量u,k,：在第k段S,k,状态时决定选,取的下一段的某点,(4)状态转移方程：S,k1,u,k,2,(6)阶段效益：,d(S,k，,u,k,),为第k段，采取策略u,k,到下一状,态的距离,(5)最优指标函数：,f,k,(S,k,)：第k段，在S,k,状态时到终点G的最,短距离,3,例1 最短路径问题,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,E,3,F,1,F,2,G,5,3,1,3,6,8,7,6,6,5,8,3,3,3,8,4,2,2,2,1,3,3,3,5,5,2,6,6,4,3,4,k6，f,6,(F,1,)4 f,6,(F,2,)3,k5,d(E,1,F,1,)+f,6,(F,1,),f,5,(E,1,)min,d(E,1,F,2,)+f,6,(F,2,),3+4,min =7 u,5,(E,1,)=F,1,5+3,5,同理 f,5,(E,2,)5 u,5,(E,2,)F,2,f,5,(E,3,)9 u,5,(E,3,)F,2,k4,d(D,1,E,1,)+f,5,(E,1,),f,4,(D,1,)min,d(D,1,E,2,)+f,5,(E,2,),2+7,min =7 u,4,(D,1,)=E,2,2+5,6,同理 f,4,(D,2,)6 u,4,(D,2,)E,2,f,4,(D,3,)8 u,4,(D,3,)E,2,K=3,7,k1,d(A,B,1,)+f,2,(B,1,),f,1,(A)min,d(A,B,2,)+f,2,(B,2,),5+13,min =18 u,1,(A)=B,1,3+16,8,(三)基本方程,f,k,(S,k,)mind(S,k,u,k,)+f,k+1,(S,k+1,)k=6,1,f,7,(S,7,)0,或,f,k,(S,k,)mind(S,k,u,k,)+f,k+1,(S,k+1,)k=5,1,f,6,(S,6,)mind(S,6,u,6,),9,例2,已知某种完好的机器1000台，,高负荷时 S,1,=8y,1,a=0.7,低负荷时 S,2,=5y,2,b=0.9,问：每年初应如何安排分配机器，,可使得5年总收益最大？,10,解,(1)阶段：k=1,2,3,4,5 n=5,(2)状态变量S,k,：第k年初始的完好设备数,(3)决策变量u,k,：第k年初始分到高负荷下,的机器数,S,k,-u,k,：第k年初始分到低负荷下,的机器数,11,(4)状态转移方程：,S,k1,0.7 u,k,+0.9(S,k,-,u,k,)=0.9S,k,-0.2 u,k,(5)最优指标函数：,f,k,(S,k,),从第k-5年末采取最优策略的最大收益,(6)一年收益：,d(S,k,u,k,)=,8,u,k,+,5(S,k,-,u,k,)=3u,k,+5S,k,12,基本方程,f,k,(S,k,)maxd(S,k,u,k,)+f,k+1,(S,k+1,)k=5,1,f,6,(S,6,)0,u,k,即,f,k,(S,k,)max(3u,k,+5S,k,)+f,k+1,(0.9S,k,-0.2u,k,),k=4,1,f,5,(S,5,)max3u,k,+5S,k,u,k,u,k,13,K=5,f,5,(S,5,)max3u,5,+5S,5,8S,5,u,5,*,=S,5,0,u,5,S,5,14,K=4,f,4,(S,4,)max3u,4,+5S,4,+f,5,(S,5,),max3u,4,+5S,4,+8(0.9S,4,-0.2u,4,),max1.4u,4,+12.2S,4,13.6S,4,u,4,*,=S,4,0,u,4,S,4,0,u,4,S,4,0,u,4,S,4,15,K=3,f,3,(S,3,)max3u,3,+5S,3,+f,4,(S,4,),max3u,3,+5S,3,+13.6(0.9S,3,-0.2u,3,),max0.28u,3,+17.24S,3,17.5S,3,u,3,*,=S,3,0,u,3,S,3,0,u,3,S,3,0,u,3,S,3,16,K=2,f,2,(S,2,)max20.7S,2,-0.5u,2,20.7S,2,u,2,*,=0,0,u,2,S,2,K=1,f,1,(S,1,)23.7 S,1,u,1,*,=0,当S,1,1000时 f,1,(1000)23700,17,结论,第一年1000台投入低负荷,S,2,0.9S,1,-0.2u,1,0.9S,1,900,第二年900台投入低负荷,S,3,0.9S,2,-0.2u,2,0.9S,2,810,第三年810台投入高负荷,S,4,0.9S,3,-0.2u,3,0.7S,3,567,18,第四年567台投入高负荷,S,5,0.9S,4,-0.2u,4,0.7S,4,397,第五年397台投入高负荷,基本方程,f,k,(S,k,)OPTd(S,k,u,k,)+f,k+1,(S,k+1,)k=n,1,f,k+1,(S,k+1,)0,19,。