第8章 动态规划.ppt

主要内容:
§7.1多阶段决策问题
§7.2动态规划的基本概念和基本原理
§7.3动态规划应用举例例求解最短路问题分阶段的最短路径最短路径最短路径解的特点§7.1多阶段决策问题动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的;
动态规划的各个决策阶段不但要考虑本阶段的决策目标,还要兼顾整个决策过程的整体目标,从而实现整体最优决策.动态规划的分类:动态规划的特点: 通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。
所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。
具有无后效性的多阶段决策过程的特点是系统过去的历史，只能通过现阶段的状态去影响系统的未来，当前的状态就是后过程发展的初始条件。
动态规划的应用使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式,要涉及以下概念:
(1)阶段 (2)状态
(3)决策与策略 (4)状态转移方程
(5)指标函数(6)基本方程(1)划分阶段
把一个复杂决策问题按时间或空间特征分解为若干(n)个相互联系的阶段(stage),以便按顺序求解;
阶段变量描述当前所处的阶段位置，一般用下标k表示;
每阶段有若干状态(state),表示某一阶段决策面临的条件或所处位置及运动特征的量,称为状态。反映状态变化的量叫作状态变量。k阶段的状态特征可用状态变量sk描述;
每一阶段的全部状态构成该阶段的状态集合Sk，并有skSk。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段的初始状态记作sk，终止状态记为sk+1，也是下个阶段的初始状态。(3)决策、决策变量决策变量的取值往往也有一定的容许范围，称之允许决策集合．决策变量xk(sk)的允许决策集用XK(SK)表示，xk(sk)XK(SK),允许决策集合实际是决策的约束条件。(4)策略和允许策略集合(5)状态转移方程(6)指标函数用vk(sk,xk)表示第k段处于状态sk且所作决策为xk时的指标，则它就是第k段指标函数，简记为vk。还跟该子过程策略pk(sk)有关,严格说来，应表示为fk(sk,pk(sk))。它是由各阶段的阶段指标函数vk(sk,xk)累积形成的，对于k部子过程的指标函数可以表示为：多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:(7)最优解例用动态规划求解最短路问题最短路的求解:
阶段:可分为4个阶段,k=1,...,4。
状态:可用城市编号,S1={Q},S2={A1,A2,A3},S3={B1,B2,B3},S4={C1,C2},S5={T}
决策:决策变量也可用城市编号;
状态转移方程:sk+1=xk;
阶段指标函数：

过程指标（阶段递推）函数:k=4
f4(C1)=3,f4(C2)=4
k=3
f3(B1)=min{1+f4(C1)=4*,4+f4(C2)=8}=4
f3(B2)=min{6+f4(C1)=9,3+f4(C2)=7*}=7
f3(B3)=min{3+f4(C1)=6*,3+f4(C2)=7}=6

k=2
f2(A1)=min{7+f3(B1),4+f3(B2),6+f3(B3)}=min{11*,11*,12}=11
f2(A2)=min{3+f3(B1),2+f3(B2),4+f3(B3)}=min{7*,9,10}=7
f2(A3)=min{4+f3(B1),1+f3(B2),5+f3(B3)}==min{8*,8*,11}=8
k=1
f1(Q)=min{2+f2(A1),4+f2(A2),3+f2(A3)}=min{13,11*,11*}=11
最短路是：QA2B1C1T，p={A2,B1,C1,T}
QA3B1C1T，p={A3,B1,C1,T}
QA3B2C2T，p={A3,B2,C2,T}整个过程的最优策略应具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,后续的诸决策必须构成最优策略；
上一条成立的条件是阶段递推函数严格单调。在例题中，求解最短路线的计算公式可以概括写成：一般地，对于n个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第k阶段和第k+1阶段间的递推公式可表示如下：相应的函数基本方程为:当过程指标函数为下列“积”的形式时相应的函数基本方程为:动态规划的优缺点