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

*§5.2动态规划的基本概念和基本方程(一)基本概念(1)阶段：k(2)状态变量：Sk(3)决策变量：uk(Sk)(4)策略(5)状态转移方程：Sk＋1＝T(Sk，uk)(6)指标函数：Vk，n(Sk)(7)最优指标函数：fk(Sk)(二)前例1*01040203阶段：k＝1，2，…，6n=6状态变量：Sk－第k阶段所处的位置状态集合如S2:(B1,B2)决策变量uk：在第k段Sk状态时决定选取的下一段的某点状态转移方程：Sk＋1＝uk01d(Sk，uk)为第k段，采取策略uk到下一状态的距离(6)阶段效益：02fk(Sk)：第k段，在Sk状态时到终点G的最短距离(5)最优指标函数：例1最短路径问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766583338422213335526643k＝6，f6(F1)＝4f6(F2)＝3k＝5d(E1,F1)+f6(F1)f5(E1)＝mind(E1,F2)+f6(F2)3+4＝min=7u5(E1)=F15+3*同理f5(E2)＝5u5(E2)＝F2f5(E3)＝9u5(E3)＝F2k＝4d(D1,E1)+f5(E1)f4(D1)＝mind(D1,E2)+f5(E2)2+7＝min=7u4(D1)=E22+5030201同理f4(D2)＝6u4(D2)＝E2f4(D3)＝8u4(D3)＝E2K=3……5+13＝min=18u1(A)=B13+16k＝1d(A,B1)+f2(B1)f1(A)＝mind(A,B2)+f2(B2)(三)基本方程*fk(Sk)＝min{d(Sk,uk)+fk+1(Sk+1)}k=6,…1f7(S7)＝0或fk(Sk)＝min{d(Sk,uk)+fk+1(Sk+1)}k=5,…1f6(S6)＝min{d(S6,u6)}例2已知某种完好的机器1000台，高负荷时S1=8y1a=0.7低负荷时S2=5y2b=0.9问：每年初应如何安排分配机器，可使得5年总收益最大？解(1)阶段：k=1,2,3,4,5n=5(2)状态变量Sk：第k年初始的完好设备数(3)决策变量uk：第k年初始分到高负荷下的机器数Sk-uk：第k年初始分到低负荷下的机器数(6)一年收益：(4)状态转移方程：(5)最优指标函数：Sk＋1＝0.7uk+0.9(Sk-uk)=0.9Sk-0.2ukfk(Sk)—从第k-5年末采取最优策略的最大收益d(Sk,uk)=8uk+5(Sk-uk)=3uk+5Sk基本方程*fk(Sk)＝max{d(Skuk)+fk+1(Sk+1)}k=5,…1f6(S6)＝0uk即fk(Sk)＝max{(3uk+5Sk)+fk+1(0.9Sk-0.2uk)}k=4,…1f5(S5)＝max{3uk+5Sk}ukukK=5f5(S5)＝max{3u5+5S5}＝8S5u5*=S50≤u5≤S5*