1,§5.2 动态规划的基本概念和基本方程,(一)基本概念,(1)阶段：k,(2)状态变量：Sk,(3)决策变量： uk(Sk),(4)策略,(5)状态转移方程： Sk＋1 ＝T (Sk ， uk),(6)指标函数： Vk，n (Sk),(7)最优指标函数： fk (Sk),2,(二)前例1,(1)阶段：k＝1，2，…，6 n=6,(2)状态变量：Sk－第k阶段所处的位置 状态集合 如S2 : (B1 , B2),(3)决策变量uk ：在第k段Sk状态时决定选 取的下一段的某点,(4)状态转移方程 ：Sk＋1 ＝uk,3,(6)阶段效益： d(Sk ，uk)为第k段，采取策略uk 到下一状 态的距离,(5)最优指标函数： fk (Sk)：第k段，在Sk状态时到终点G的最 短距离,4,例1 最短路径问题,5,k＝6， f6(F1)＝4 f6(F2)＝3,6,同理 f5(E2)＝5 u5(E2)＝ F2 f5(E3)＝9 u5(E3)＝ F2,7,同理 f4(D2)＝6 u4(D2)＝ E2 f4(D3)＝8 u4(D3)＝ E2,K=3,… …,8,9,(三)基本方程,或,10,例2,已知某种完好的机器1000台， 高负荷时 S1=8y1 a=0.7 低负荷时 S2=5y2 b=0.9,问：每年初应如何安排分配机器， 可使得5年总收益最大？,11,解,(1)阶段：k=1,2,3,4,5 n=5,(2)状态变量Sk ：第k年初始的完好设备数,(3)决策变量uk：第k年初始分到高负荷下 的机器数 Sk- uk：第k年初始分到低负荷下 的机器数,,12,(4)状态转移方程： Sk＋1 ＝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,13,基本方程,14,K=5,15,K=4,16,K=3,17,K=2,K=1,f1(S1)＝23.7 S1 u1* =0当S1＝1000时 f1(1000)＝23700,18,结论,第一年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 ＝ 567,19,第四年567台投入高负荷 S5＝ 0.9S4-0.2u4＝ 0.7S4 ＝397第五年397台投入高负荷,基本方程,。