动态规划理论部分ppt课件.ppt

第四章
动态规划动态规划是解决多阶段决策过程最优化问题的一种方法。在二十世纪五十年代由美国数学家理查德.贝尔曼(Richard．Ba11man)首先提出的。它可以把一个n维最优化问题转化为n个一维最优化问题来求解。一、多阶段决策问题例1：（最短路程问题）设从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线，使总长度最短。在这个问题中，从A到B1，B2，B3中的哪一个点要作出一项决策，从B1，B2，B3某点到C1，C2，C3中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此，我们可以把整个路程分为A，B(包括B1，B2，B3)，C(包括C1，C2，C3，)，D(包括D1和D2)，E五个阶段。这就是一个多阶段的决策问题。以上面的例1来说明动态规划解决问题的思想。设：例如，在最短路线问题中，如果找到了A到E的最短路：下面按上述思想，将例1从最后一段开始计算，由后向前逐步推移至A点。22222222222三、动态规划的基本概念T1(4)策略（policy）(5)状态转移方程过程指标函数是指从第k阶段至第n阶段所包含的各阶段的状态和决策所产生的总的效益值，记为:
Vk,n＝Vk,n(Sk,uk,Sk+1,uk+1,……,Sn,un)把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态Sk的函数，称为最优值函数或贝尔曼函数，记为:。即式中的“opt”（optimization）可根据具体问题的实际意而取min或max。由最优性定理可知：其中：fk(sk)表示第k阶段初始状态为sk时，k后部子过程的最优准则函数。正序递归方程：动态规划建模有以下过程：
①确定阶段与阶段变量
②明确状态变量和状态可能集合。
③确定决策变量和决策允许集合。
④确定状态转移方程。
⑤明确阶段效应和目标。k=n时，动态规划基本方程是k=n－1时，动态规划的基本方程是k=1时，动态规划的基本方程是解该问题可以作为三段决策过程。对A、B、C三个部门分配资金分别形成1，2，3三个阶段。sk表示给部门k分配资金时拥有的资金数。uk表示给部门k分配的资金数（万元为单位）。状态转移方程是sk+1=sk-uk。目标函数是阶段效应求和。递归方程为：s2＝1（3）K=1时（第1阶段）S1={5}应用顺序追踪可知：最优方案有两个：例3：逆推解法求解下面问题:令最优值函数fk(sk)表示为第k阶段的初始状态为sk时，从第k阶段到第3阶段所得到的最大值。由,得

和（舍去）
又，而

故为极大值点。求导并令导数等于0可得：，故因此最优解为：，，，例４：正推解法求解下面问题:由顺推解法，即最优解x1＊=s2,
最优解因此最优解为：，，，例５：用正推解法求解下面问题:设:3x1=s1,s1+2x2=s2,s2+x3=s3≤9
由,得(它不在决策集

内)
由,得
而作业用动态规划法求解：