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

第七章动态规划
2018/8/15
多阶段决策过程
多阶段决策问题是指这样一类问题,其整个过程可分为若干相互联系的阶段,每一阶段都要作出相应的决策,从而使整个过程达到最佳的活动效果。任何一个阶段(Stage,决策点)都是由输入(Input)、决策(Decision)、转移律(Transformation)和输出(output)构成的,如图6-1(a)所示。由于每一阶段都对应一个决策,所以每一阶段都应存在一个衡量决策效益大小的指标函数,这一指标函数称为阶段指标函数,用gn表示。显然gn是状态变量sn和决策变量dn的函数,即gn= rn(sn, dn),如图6-1(b)所示。

2018/8/15
多阶段决策过程

决策
输入阶段输出
转移律
图6-1(a)
dn
sn(in) n sn(out)
gn= rn(sn, dn)
图6-1(b)
2018/8/15
多阶段决策过程
d1 d2 dN
s1 s2 s3  sN sN+1
1 2 N
g1 g2 gN

图 6-2 N 阶段决策系统示意图
2018/8/15
Bellman最优性原理
作为整个过程的最优策略具有这样的性质: 即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优子策略。简而言之,一个最优策略的任一子策略都是最优子策略。
2018/8/15
动态规划的数学描述








2018/8/15
阶段
在多阶段决策过程中,决策点将整个过程划分为若干部分,其中的每一部分即为一个阶段。描述阶段的变量称为阶段变量,常用 k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的,一个N 个阶段的多阶段决策问题其阶段变量 k =1,2,,N。
2018/8/15
状态
状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问题过程的状况。状态反映前面各阶段决策的结局,又是本阶段决策的出发点和依据。状态是各阶段信息的传递点和结合点,各阶段的状态通常用状态变量Sk来描述。作为状态应具有这样的性质:在某阶段的状态给定后,该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说,过程的历史只能通过当前的状态来影响未来,当前的状态是过程以往历史的一个总结。这个性质称为无后效性或健忘性。
2018/8/15
决策
决策是指决策者在若干可行方案中所作出的选择。决策变量dk(Sk)表示第k 阶段、状态为Sk时的决策。决策变量的取值会受到一定的限制,用Dk(Sk)表示第k 阶段、状态为Sk 时决策变量允许的取值范围,称为允许决策集合,因而有dk(Sk) Dk(Sk) 。
2018/8/15
状态转移律
状态转移律是确定由一个状态到另一个状态演变过程的关系式,这种演变的对应关系记为Sk+1=Tk (Sk, dk)。
2018/8/15