资源描述：
《《动态规划》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章动态规划§1多阶段决策过程及实例§2动态规划的基本概念和基本方程§3动态规划的最优性原理和最优性定理§4动态规划与静态规划的关系§1多阶段决策过程及实例在实际中，有一类问题可以看作是一活动的过程，由于它的特殊性，可将过程分为若干个相互联系阶段，在每个阶段都要依据该阶段所处的状态作出相应的决策，该决策又引起该阶段状态的转移，决定了下一阶段的状态，当每个阶段的决策确定后，由这些决策组成一个决策序列，即整个过程的一条活动路线。这类活动过程称为多阶段决策过程。这类问题称为多阶段决策问题。12n状态状态状态……状态状态决策决策决策例1最短路线问题如下图，是一线路网络，两点之间连线上的数字
2、表示两点之间的距离（或费用）试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。1状态状态状态状态状态决策决策决策23456状态状态决策决策决策B2C3D2E3F2GB2C3D2E3F2GAV6,6=3AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432V1,6=24V5,6=9V4,6=11V3,6=14V2,6=21V1,6=24例2机器负荷分配问题某种机器可以在高低两种不同负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数u的关系为在低负荷下进行生产时，产品的年产量h和投入生产的机器
3、数u的关系为1状态状态状态状态状态决策决策决策2345状态决策决策u1u2u3u4u5s2s3s4s5s6s1设：§2动态规划的基本概念和基本方程2.1动态规划的基本概念1.阶段把过程依据一定的时间和空间特征恰当地划分为若干个相互联系的阶段，以便利用动态规划的方法求解。描述阶段的变量称为阶段变量，用k表示。k=1，2，…，n2.状态每个阶段开始所处的自然状况或客观条件，称为状态。状态是不可控的，是客观存在的。描述状态的变量称为状态变量，用sk表示。状态变量可以是一个数或一个向量。状态变量sk的取值范围称为可达状态集合，用Sk表示。例1中，S3={C1,C2,C3,C4}。状态变量的性
4、质（无后效性）如果某阶段的状态给定后，则该阶段以后的过程的发展不受该阶段以前各阶段状态的影响。即过程的过去历史只能通过当前的状态去影响未来的发展，当前的状态是以往历史的总结，以后发展的依据。这个性质称为无后效性（即马尔科夫性）。无后效性的特征：在每个阶段所作的决策只依据当前的状态，和以往的状态无关。在选取状态变量时，一定要保证状态变量具有无后效性，否则不能利用动态规划的方法求解。3.决策在每个阶段所作的决定或选择称为决策或控制。决策依据与当前状态，又决定下一阶段的状态。描述决策的变量称为决策变量，用uk(sk)表示。他是状态变量sk的函数。决策变量的取值范围称为容许决策集合，用Dk(
5、sk)表示。在例1中D1(A)={B1,B2}D2(B1)={C1,C2,C3}，D2(B2)={C2,C3,C4}D4(D1)={E2,E3}在例2中D1(s1)={u1(s1)
6、0≤{u1(s1)≤s1}D2(s2)={u2(s2)
7、0≤{u2(s2)≤s2}Dk(sk)={uk(sk)
8、0≤{uk(sk)≤sk}4.策略按一定顺序排列的决策序列集合称为策略。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为k子过程）。由k子过程的每个阶段的决策函数组成的决策函数序列集合{uk(sk),uk+1(sk+1),…,un(sn)}称为k子过程策略，简称为子策略，记
9、为pk,n(sk)，即pk,n(sk)={uk(sk),uk+1(sk+1),…,un(sn)}当k=1时,此决策函数序列称为全过程的一个策略，简称为策略，记为p1,n(s1)。即p1,n(sk)={u1(s1),u2(s2),…,un(sn)}策略的取值范围称为容许策略集合，用P表示。在P中,使指标函数达到最优的策略称为最优策略。例1中，每一条线路就是一个策略，容许策略集合中有48个策略。A到G的最短线路就是最优策略。5.状态转移方程若给定第k个阶段状态变量sk的值，该阶段的决策变量uk的值一经确定，第k+1个阶段的状态变量sk+1的值也就完全确定了，即sk+1是sk和uk的函数，
10、记为sk+1=Tk(sk,uk)该函数描述由第k个阶段到第k+1个阶段的状态转移规律,称为状态转移方程。例1中，状态转移方程为例2中，状态转移方程为6.指标函数和最优值函数用来衡量过程和子过程（策略和子策略）优劣的一种数量指标，称为指标函数。它是定义在全过程和后部子过程上的数量函数，用Vk,n表示。即指标函数的性质：动态规划中的指标函数应具有可分离性，并满足地推关系，常见指标函数的形式（1）过程和子过程的指标函数可分解为它所包含的阶段的指标的和，即（2）过
