管理运筹学07动态规划课件.ppt

《管理运筹学07动态规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.多阶段决策过程2.Bellman最优性原理3.动态规划的数学描述4.例6.15.确定性动态规划问题6.随机性动态规划问题第七章动态规划2021/9/21多阶段决策过程多阶段决策问题是指这样一类问题，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，从而使整个过程达到最佳的活动效果。任何一个阶段(Stage，决策点)都是由输入(Input)、决策(Decision)、转移律(Transformation)和输出(output)构成的，如图6-1(a)所示。由于每一阶段都对应一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用

2、gn表示。显然gn是状态变量sn和决策变量dn的函数，即gn=rn(sn,dn)，如图6-1(b)所示。2021/9/21多阶段决策过程决策输入阶段输出转移律图6-1(a)dnsn(in)nsn(out)gn=rn(sn,dn)图6-1(b)2021/9/21多阶段决策过程d1d2dNs1s2s3sNsN+112Ng1g2gN图6-2N阶段决策系统示意图2021/9/21Bellman最优性原理作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优子策略。简而言之，一个最优策略的任一子策略都是最优子策略。202

3、1/9/21动态规划的数学描述1.阶段2.状态3.决策4.状态转移律5.策略与子策略6.阶段指标函数7.过程指标函数8.最优指标函数2021/9/21阶段在多阶段决策过程中，决策点将整个过程划分为若干部分，其中的每一部分即为一个阶段。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，一个N个阶段的多阶段决策问题其阶段变量k=1，2，，N。2021/9/21状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态反映前面各阶段决策的结局，又是本阶段决策的出发点和依据。状态是各阶段信息的传递点和结合点，各阶段的状态通

4、常用状态变量Sk来描述。作为状态应具有这样的性质：在某阶段的状态给定后，该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是过程以往历史的一个总结。这个性质称为无后效性或健忘性。2021/9/21决策决策是指决策者在若干可行方案中所作出的选择。决策变量dk(Sk)表示第k阶段、状态为Sk时的决策。决策变量的取值会受到一定的限制，用Dk(Sk)表示第k阶段、状态为Sk时决策变量允许的取值范围，称为允许决策集合，因而有dk(Sk)Dk(Sk)。2021/9/21状态转移律状态转移律是确定由一个状态到另一个状态演变过程的关系

5、式，这种演变的对应关系记为Sk+1=Tk(Sk,dk)。2021/9/21策略与子策略各阶段决策所组成的决策序列称为一个策略，具有N个阶段的动态规划问题的策略可表示为{d1(S1),d2(S2),…,dN(SN)}。从某一阶段开始到过程终点为止的决策序列，称为子过程策略或子策略。从第k个阶段起的子策略可表示为{dk(Sk),dk+1(Sk+1),…,dN(SN)}。2021/9/21阶段指标函数阶段指标函数是对应某一阶段决策的效率度量，用gk=rk(Sk,dk)来加以表示。2021/9/21过程指标函数过程指标函数是用来衡量所实现过程优劣的数量指标，它是定义在全过程（策略）或后续子

6、过程（子策略）上的数量函数。过程指标函数常用Rk,,N来表示，构成动态规划的过程指标函数应具有可分性并满足递推关系，即Rk,,N可表示为rk和Rk+1,N二者的函数。最常见的过程指标函数与阶段指标函数的关系有如下两种：1.过程指标函数是阶段指标函数的和，此时Rk,,N=rk+Rk+1,N2.过程指标函数是阶段指标函数的积，此时Rk,,N=rkRk+1,N2021/9/21最优指标函数2021/9/21ABCDB1129C1156A4B220D81610C216B39例12021/9/21例1的构模阶段：k=1,2,3状态：选各阶段所处的位置为状态变量，因此有S1=A。决策：所选

7、择的路线；D1(S1)={B1,B2,B3}状态转移：目前状态一定，选择的线路一定，下一个状态一定。阶段指标函数：该阶段行进的路程过程指标函数：阶段指标函数的和最优指标函数：fk(Sk)=min{rk+fk+1(Sk+1)}其中，边界条件fk+1(Sk+1)=0。2021/9/21例1的求解K=3时：f3(C1)=min{15}=15,C1Df3(C2)=min{16}=16,C2DK=2时：f2(B1)=min{12+15,9+16}=25,B1C2f2(B