(8.2.1)--第22讲动态规划的基本概念和方程.pdf
运运 筹筹 学学 第第2222讲讲 动态规划的基本概念与基本方程动态规划的基本概念与基本方程 一、动态规划的基本概念一、动态规划的基本概念 1.1.阶段阶段(stage)定义定义：把所给问题分解成若干个相互联系的阶段，以便能按一定的顺序求解。变量变量：描述阶段的变量称为阶段变量，用k表示。一般根据问题的时间和空间等自然特征来划分。2 A E B1 B2 4 5 C1 C2 C3 4 2 5 D1 D3 5 6 7 5 3 D2 4 3 6 5 4 5 4 6 第一阶段第一阶段 第二阶段第二阶段 第三阶段第三阶段 第四阶段第四阶段 由由A出发为出发为k=1，由由Bi(i=1,2)出发为出发为k=2，依此下去从依此下去从Di(i=1,2,3)出发为出发为k=4，共共n=4个阶段个阶段。3 2.状态状态 状态状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后无后向性向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。4 一、动态规划的基本概念一、动态规划的基本概念 状态集合状态集合：通常一个阶段有若干个状态。一般：第k阶段的状态就是第k阶段所有起始点的集合。状态变量状态变量：描述过程状态的变量，用Sk表示第k阶段的状态集合，用sk表示第k阶段的某个状态。一、动态规划的基本概念一、动态规划的基本概念 5 A E B1 B2 4 5 C1 C2 C3 4 2 5 D1 D3 5 6 7 5 3 D2 4 3 6 5 4 5 4 6 第一阶段第一阶段 第二阶段第二阶段 第三阶段第三阶段 第四阶段第四阶段 S1=A S2=B1,B2 S3=C1,C2,C3.（1 1）状态集合）状态集合 6 一、动态规划的基本概念一、动态规划的基本概念 n个阶段的决策过程有n+1个状态变量，sn+1表示sn演变的结果，在上例中s5取E。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。7 一、动态规划的基本概念一、动态规划的基本概念 8 3.决策决策(decision)定义定义：过程处于某状态时，可以作出的决定(或选择)。变量变量：描述决策的变量称为决策变量，用uk(sk)表示第k阶段在状态sk下的决策，显然uk是sk的函数。允许决策集合允许决策集合：sk下的决策往往有多个，它们构成的集合称为sk的允许决策集合，用Dk(sk)表示，uk(sk)Dk(sk)。一、动态规划的基本概念一、动态规划的基本概念 A E B1 B2 4 5 C1 C2 C3 4 2 5 D1 D3 5 6 7 5 3 D2 4 3 6 5 4 5 4 6 第一阶段第一阶段 s1=A u1(A)=B1 或 u1(A)=B2 ,D1(A)=B1,B2 9 4.策略策略 按阶段顺序排列的一组决策的集合称为策略策略(policy)。由 初 始 状 态 s1开 始 的 全 过 程 的 策 略 记 作 p1,n(s1)，即p1,n(s1)=u1(s1),u2(s2),.，un(sn)。k子过程子过程：从第k阶段的起始状态sk开始到终止状态sn+1结束的过程，称为问题的后部子过程或k子过程。10 一、动态规划的基本概念一、动态规划的基本概念 11 k子过程策略子过程策略(子策略子策略)：k子过程中，每阶段的决策按阶段顺序排列形成的集合，称为k子过程策略。用 p k,n(sk)=uk(sk),uk+1(sk+1),un(sn)允许子策略集合允许子策略集合：所有k子过程策略形成的集合。用P k,n(sk)表示，显然p k,n(sk)P k,n(sk)。全过程策略全过程策略：k1时，每阶段的决策按阶段顺序排列形成的集合。p 1,n(s1)=u1(s1),u2(s2),uk(sk),uk+1(sk+1),un(sn)。允许策略集合允许策略集合：所有全过程策略形成的集合。用P 1,n(s1)表示，显然p 1,n(s1)P 1,n(s1)。最优策略最优策略(optimal policy)：P k,n(sk)中具有最优效果的策略。k1时，为全过程最优策略。12 5.状态转移方程状态转移方程(state transformation equation)描述过程演化规律的方程。若已知sk，当uk(sk)确定后，则能确定sk1，即状态满足无后效性。sk1Tr(sk,uk(sk)一、动态规划的基本概念一、动态规划的基本概念 13 阶段指标函数阶段指标函数：vk(sk,uk)过程指标函数过程指标函数：用来衡量所实现过程优劣的数量指标，记作V k，n，对应k子过程的一个策略 p k,n(sk)产生的价值。6、阶段指标函数和最优指标函数、阶段指标函数和最优指标函数 一、动态规划的基本概念一、动态规划的基本概念 14 阶段指标函数之和阶段指标函数之和 Vk,n Vk,n(sk,uk,sn+1)vj(sj,uj)递推关系为：Vk,n sk,uk,Vk+1,n(sk+1,uk+1,sn+1)vk(sk,uk)Vk+1,n(sk+1,uk+1,sn+1)阶段指标函数之积阶段指标函数之积 Vk,n Vk,n(sk,uk,sn+1)vj(sj,uj)递推关系为：Vk,n sk,uk,Vk+1,n(sk+1,uk+1,sn+1)vk(sk,uk)Vk+1,n(sk+1,uk+1,sn+1)过程指标函数的形式：过程指标函数的形式：一、动态规划的基本概念一、动态规划的基本概念 当第k阶段的初始状态sk给定时，从第k阶段到最后一个阶段终止的后部子过程的最优指标值函数最优指标值函数(optimal value function)记作fkn(sk)，即)(,(),()(,)()(*,knkknksPspnkknkkknspsVoptPsVsfknkknk15 一、动态规划的基本概念一、动态规划的基本概念 动态规划的基本概念动态规划的基本概念 其中Opt是最优化（Optimum）的缩写，可根据题意取max或min。上式的意义是，对于某个阶段k的某个状态sk，从该阶段k到最终目标阶段n的最优指标函数值等于从sk出发取遍所有能策略pkn所得到的最优指标值中最优的一个。)(,(),()(,)()(*,knkknksPspnkknkkknspsVoptPsVsfknkknk16 由最短路问题可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系：fk(sk)=mindk(sk,uk(sk)+fk+1(sk+1),k=6,5,4,3,2,1 f7(S7)=0 一般情况下，k阶段与k+1阶段之间的递推关系可写为：二、动态规划的基本方程（递推关系式）二、动态规划的基本方程（递推关系式）)(0)(1,1,)(,)(),()(1111)(边界条件 optnnkkkkkkkksDukksfnnksDusfusvsfkkk17
