《动态规划基本方法.ppt》由会员分享，可在线阅读，更多相关《动态规划基本方法.ppt（18页珍藏版）》请在三一办公上搜索。
1、第8章 动态规划基本方法,第1节 多阶段决策问题与动态规划,动态规划是运筹学的一个分支，产生于20世纪50年代，1951年由美国数学家贝尔曼等人提出。,例 最短路问题 给定下列道路网络，试求由节点A到G的最短路。,例2 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 gg(u)，这时机器的年完好率为a（0a1)；在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为hh(v)，这时机器的年完好率为b（ab1）。假定开始生产时完好的机器数量为s，要求制定一个五年计划，在每年开始时决定机器在两种不同负荷下生产
2、的数量，使五年内产品的总产量最高。,多阶段决策问题和前面遇到的决策问题不同，它是和时间有关的，状态（所处自然状况和客观条件）是随着决策进程而变化的，故有“动态”的含义。与时间有关的活动过程称为动态过程，处理它的方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的处理方法称为静态规划。,以上两个问题都可以划分为先后多个决策阶段。这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示：,第2节 动态规划的基本概念和基本方程,（1）阶段（stage）,（2）状态（state）,把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。这些决策步骤就称为阶段。
3、,描述阶段的变量称阶段变量，常用k表示。,状态表示每个阶段开始时所处的自然状况或客观条件。它描述了影响决策的因素随决策进程的变化情况。它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。,描述状态的变量称状态变量，第k阶段的状态变量常用sk表示。通常，第一阶段的状态变量s1是确定的，称初始状态。,2.1 动态规划的基本概念,描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内，称为允许决策集，记为Dk(sk)。,决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。,（3）决策（decision）,（4）
4、策略（policy）,把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。,在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n=u1,u2,un称为全过程策略，简称策略；而在k-子过程上的决策序列pk,n=uk,uk+1,un称为k-子过程策略，也简称子策略。,（5）状态转移方程,若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定了，即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1=Tk(sk,uk)，称为状态转移方程。,状态转移方程描述了由一个阶段的状态到
5、下一阶段的状态的演变规律。,（6）指标函数和最优值函数,指标函数分为阶段指标函数和过程指标函数。,阶段指标函数是对某一阶段上（由状态和决策产生的）目标损益值的度量，用vk(sk,uk)表示。,过程指标函数是指过程所包含的各阶段上（由状态和决策所产生的）总的目标损益值，记为 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un),动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数。,常见的两种过程指标函数形式是：各阶段指标函数的和 Vk,n=vj(sj,uj)；各阶段指标函数的积 Vk,n=vj(sj,uj)。,把过程指标函数Vk,n对k-子过程策略pk
6、,n求最优，得到一个关于状态sk的函数，称为（k-子过程）最优值函数，记为fk(sk)。即 fk(sk)opt Vk,n(sk,uk,sn,un)uk,un 式中的“opt”（optimization）可根据具体问题而取min或max。,2.2 动态规划的基本方程,动态规划的最优性原理（贝尔曼原理）：作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简言之，最优策略的子策略也必是最优的。,根据此原理，要求全过程最优策略，可从子过程策略的最优化入手。对于过程指标函数是阶段指标函数和的形式，考虑k-子过程最优值函数fk(s
7、k):,则有递推方程：,还需有边界条件，一般取：,利用基本方程，由后向前逆序递推，就可实现对动态规划问题的求解。,例 最短路问题,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,于是得A到G的最短距离为18，最短路线为：AB1C2D1E2F2G,k=6时：f6(F1)=4 f6(F2)=3,k=5时：f5(E1)=7 f5(E2)=5 f5(E3)=9,k=4时：f4(D1)=7 f4(D2)=6 f4(D3)=8,k=3时：f3(C1)=13 f3(C2)=10 f3(C3)=9 f3(C4)=8,k=2时：f2(B1)=13 f2(B2)=16;,k=1时：f1(A
8、)=18,现在把动态规划法的步骤归纳如下：,（1）将所研究问题的决策过程划分为n个恰当的阶段，k=1,2,n；,（2）合理正确地选择状态变量sk，并确定初始状态s1的值；,（3）确定决策变量uk及允许决策集Dk(sk)；,（4）给出状态转移方程 sk+1=Tk(sk,uk)；,（5）给出满足要求的过程指标函数Vk,n及相应的最优值函数；,（6）写出递推方程和边界条件，建立基本方程；,（7）按照基本方程递推求解。,以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。,例：机器负荷问题 某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入
9、生产的机器数量u的关系为 g=8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h=5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为1000，要求制定一个五年计划，在每年开始时决定机器在两种不同负荷下生产的数量，使五年产品的总产量最高。,按年数划分为5个阶段，k=1,2,3,4,5。,取第k年初完好的机器数sk为状态变量，则s1=1000。,解：,取第k年投入高负荷的机器数xk为决策变量，0 xksk,状态转移方程sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk,指标函数为Vk,5=8xj+5(sj-xj)
10、=(5sj+3xj),基本方程为 fk(sk)max 5sk+3xk+fk+1(sk+1)k=5,4,3,2,1 0 xksk f6(s6)0,当k=5时：,f5(s5)max5s5+3x5+f6(s6)=max5s5+3x5 0 x5s5 0 x5s5,=8s5(x5*=s5),当k=4时：,f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4)0 x4s4 0 x4s4=max12.2s4+1.4x4 0 x4s4,=13.6s4(x4*=s4),当k=3时：,f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-
11、0.2x3)0 x3s3 0 x3s3=max17.24s3+0.28x3 0 x3s3,当k=2时：,f2(s2)=max5s2+3x2+17.52s3=max5s2+3x2+17.52(0.9s2-0.2x2)0 x2s2 0 x2s2=max20.77s2-0.504x2 0 x2s2,当k=1时：,f1(1000)=23.71000=23700,s1=1000 x1*=0s1-x1*=1000,=17.52s3(x3*=s3),=20.77s2(x2*=0),f1(s1)=max5s1+3x1+20.77s2 0 x1s1,=23.7s1(x1*=0),s2=900 x2*=0s2-x
12、2*=900,s3=810 x3*=810s3-x3*=0,s4=567x4*=567s4-x4*=0,s5=397x5*=397s5-x5*=0,第4节 动态规划和静态规划的关系,静态规划所研究的问题是与时间无关的，而动态规划所研究的问题是和时间有关的。对于某些静态规划问题，也可人为地引入时间因素，把它看做一个按阶段进行的动态规划问题，用动态规划的方法求解。,解：,按变量划分为3个阶段，k=1,2,3,取k阶段初常数项的剩余量sk为状态变量，s1=9,取xk为决策变量，0 xksk ak（a1=3,a2=2,a3=1）,状态转移方程为 sk+1=sk-akxk,指标函数为 Vk,n=vj(x
13、j)（v1(x1)=4x12,v2(x2)=-x22,v3(x3)=2x32+12）,当k=3时：f3(s3)=max 2x32+12+0=2s32+12(x3*=s3)0 x3s3,当k=2时：f2(s2)=max-x22+2s32+12=max-x22+2(s2-2x2)2+12 0 x2s2 2 0 x2s2 2,=max7x22-8s2x2+2s22+12 0 x2s2 2,=2s22+12(x2*=0),当k=1时：f1(s1)=max4x12+2s22+12=max4x12+2(s1-3x1)2+12 0 x1s1 3 0 x1s1 3,=max22x12-12s1x1+2s12+
14、12 0 x1s1 3,=2s12+12(x1*=0),F*=f1(9)=292+12=174,s1=9x1*=0,s2=9x2*=0,s3=9x3*=9,解：,按变量划分为3个阶段，k=1,2,3,取k阶段初常数项的剩余量sk为状态变量，s1=c,取xk为决策变量，0 xksk（k=1,2）,x3=s3,状态转移方程为 sk+1=sk-xk,指标函数为 Vk,n=vj(xj)（v1(x1)=x1,v2(x2)=x22,v3(x3)=x3）,当k=2时:,f2(s2)=maxv2(x2)s3=maxx22(s2-x2)0 x2s2 0 x2s2,当k=1时:,z*=f1(c)=1/64c4,s1=cx1*=1/4c,s2=3/4cx2*=1/2c,s3=1/4cx3*=1/4c,设h2(s2,x2)=x22(s2-x2),且令dh2(s2,x2)/dx2=0,解得:x2=0(舍去),x2=2/3 s2,于是 f2(s2)=4/27 s23(x2*=2/3s2),f1(s1)=maxv1(x1)4/27 s23=maxx1 4/27(s1-x1)3 0 x2s2 0 x2s2,设h1(s1,x1)=x1 4/27(s1-x1)3,且令dh1(s1,x1)/dx1=0,解得:x1=s1(舍去),x1=1/4 s1,于是 f1(s1)=1/64 s14(x1*=1/4 s1),
