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

1、5.2 5.2 动态规划的基本概念和基本方程动态规划的基本概念和基本方程(一一)基本概念基本概念(1)阶段：阶段：k(2)状态变量：状态变量：Sk(3)决策变量：决策变量：uk(Sk)(4)策略策略(5)状态转移方程：状态转移方程：Sk1 T(Sk，uk)(6)指标函数：指标函数：Vk，n(Sk)(7)最优指标函数：最优指标函数：fk(Sk)1(二二)前例前例1(1)阶段：阶段：k1，2，6 n=6(2)状态变量：状态变量：Sk第第k阶段所处的位置阶段所处的位置 状态集合状态集合 如如S2:(B1,B2)(3)决策变量决策变量uk：在第在第k段段Sk状态时决定状态时决定选选 取的下一段的某点取

2、的下一段的某点(4)状态转移方程状态转移方程：Sk1 uk2(6)阶段效益：阶段效益：d(Sk，uk)为第为第k段，采取策略段，采取策略uk 到下一到下一状状 态的距离态的距离(5)最优指标函数：最优指标函数：fk(Sk)：第：第k段，在段，在Sk状态时到终点状态时到终点G的的最最 短距离短距离3例例1 最短路径问题最短路径问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876658333 84222133355266434k6，f6(F1)4 f6(F2)3k5 d(E1,F1)+f6(F1)f5(E1)min d(E1,F2)+f6(F2)3+4 min =7 u

3、5(E1)=F1 5+35同理同理 f5(E2)5 u5(E2)F2 f5(E3)9 u5(E3)F2k4 d(D1,E1)+f5(E1)f4(D1)min d(D1,E2)+f5(E2)2+7 min =7 u4(D1)=E2 2+56同理同理 f4(D2)6 u4(D2)E2 f4(D3)8 u4(D3)E2K=3 7k1 d(A ,B1)+f2(B1)f1(A)min d(A ,B2)+f2(B2)5+13 min =18 u1(A)=B1 3+168(三三)基本方程基本方程fk(Sk)mind(Sk,uk)+fk+1(Sk+1)k=6,1f7(S7)0或或fk(Sk)mind(Sk,u

4、k)+fk+1(Sk+1)k=5,1f6(S6)mind(S6,u6)9例例2已知某种完好的机器已知某种完好的机器1000台，台，高负荷时高负荷时 S1=8y1 a=0.7 低负荷时低负荷时 S2=5y2 b=0.9 问：每年初应如何安排分配机器，问：每年初应如何安排分配机器，可使得可使得5年总收益最大？年总收益最大？10解解(1)阶段：阶段：k=1,2,3,4,5 n=5(2)状态变量状态变量Sk：第：第k年初始的完好设备数年初始的完好设备数(3)决策变量决策变量uk：第：第k年初始分到高负荷年初始分到高负荷下下 的机器数的机器数 Sk-uk：第：第k年初始分到低负荷下年初始分到低负荷下 的

5、机器数的机器数11(4)状态转移方程：状态转移方程：Sk1 0.7 uk+0.9(Sk-uk)=0.9Sk-0.2 uk(5)最优指标函数：最优指标函数：fk(Sk)从第从第k-5年末采取最优策略的最大收益年末采取最优策略的最大收益(6)一年收益：一年收益：d(Sk,uk)=8uk+5(Sk-uk)=3uk+5Sk 12基本方程基本方程fk(Sk)maxd(Sk uk)+fk+1(Sk+1)k=5,1f6(S6)0uk即即fk(Sk)max(3uk+5Sk)+fk+1(0.9Sk-0.2uk)k=4,1f5(S5)max3uk+5Sk ukuk13K=5f5(S5)max3u5+5S58S5

6、u5*=S50u5S514K=4f4(S4)max3u4+5S4+f5(S5)max3u4+5S4+8(0.9S4-0.2u4)max1.4u4+12.2S4 13.6S4 u4*=S40 u4 S40 u4 S40 u4 S415K=3f3(S3)max3u3+5S3+f4(S4)max3u3+5S3+13.6(0.9S3-0.2u3)max0.28u3+17.24S3 17.5S3 u3*=S30 u3 S30 u3 S30 u3 S316K=2f2(S2)max20.7S2-0.5u2 20.7S2 u2*=00 u2 S2K=1f1(S1)23.7 S1 u1*=0当当S11000时时 f1(1000)2370017结论结论第一年第一年1000台投入低负荷台投入低负荷 S2 0.9S1-0.2u1 0.9S1 900第二年第二年900台投入低负荷台投入低负荷 S3 0.9S2-0.2u2 0.9S2 810第三年第三年810台投入高负荷台投入高负荷 S4 0.9S3-0.2u3 0.7S3 56718第四年第四年567台投入高负荷台投入高负荷 S5 0.9S4-0.2u4 0.7S4 397第五年第五年397台投入高负荷台投入高负荷 基本方程基本方程fk(Sk)OPTd(Sk uk)+fk+1(Sk+1)k=n,1fk+1(Sk+1)019