智能优化-动态规划概要

1、4 动态规划,4.1 多阶段决策问题与动态规划 4.2 动态规划的基本概念 4.3 动态规划的步骤 4.4 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 背包问题 4 库存问题,4.1 多阶段决策问题与动态规划,求AG的最短路径？,例2 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 gg(u), 这时机器的年完好率为a（0a1)在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为hh(v), 这时机器的年完好率为b（ab1）假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开

2、始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。,多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。,最优性原理,作为整个过程的最优策略具有这样的性质， 无论过去的状态和决策如何，相对于前面 决策所形成的状态，余下的决策序列必然 构成最优子序列。 这种过去的状态和决策对于今后的决策所 形成的状态没有影响，也称为无后效性或 者马尔可夫性。,(1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求

3、解。描述阶段的变量称阶段变量，常用k表示。,(2)状态（state）状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。,(3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。,4.2 动态规划的基本概念（一）,(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+1Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演

5、变规律。,(6)指标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量，用vk(sk,uk)表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值，记为 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un) 动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是： 各阶段指标函数的和 Vk,nvj(sj,uj)； 各阶段指标函数的积 Vk,nvj(sj,uj)。 把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态sk的函数，称

6、为最优值函数，记为fk(sk)。即 fk(sk) opt Vk,n(sk,uk,sn,un) uk,un 式中的“opt”（optimization）根据具体问题而取min或max。,(7)基本方程 通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,nvj(sj,uj)，则有 fk(sk) opt vk(sk,uk)+fk+1(sk+1) ukDk(sk) (kn,n-1,1) 递推方程 fn+1(sn+1)0 边界条件 递推方程和边界条件一起称为动态规划的基本方程。 可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值

7、，最后求出f1(s1)时，就得到整个问题的最优解。,此问题的基本方程为 fk(sk)Mindk(uk)+fk+1(sk+1) ukDk(sk) k6,5,4,3,2,1 f7(s7)0,4.3 动态规划的步骤（一）,当k=6时,按基本方程由后向前继续递推有:,当k=5时,当k=4时,当k=3时,当k=2时,当k=1时,由此可以看出，A到G的最短路长为18，路径为： AB1C2D1E2F2G,现在把动态规划法的步骤归纳如下： (1) 将所研究问题的过程划分为n个恰当的阶段， k 1,2,n； (2) 正确地选择状态变量Sk，并确定初始状态S1的值； (3) 确定决策变量uk以及各阶段的允许决策集

8、Dk(Sk)； (4) 给出状态转移方程； (5) 给出满足要求的过程指标函数Vk,n及相应的最优 值函数； (6) 写出递推方程和边界条件，建立基本方程； (7) 按照基本方程递推求解。 以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。,4.3 动态规划的步骤（二）,例2：机器负荷问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 g8u, 这时机器的年完好率为a=0.7在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h5v, 这时机器的年完好率为b=0.9假定开始生产时完好的机器数量

9、为s11000，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。,(1)按年数划分为5个阶段，k=1,2,3,4,5,(2)取第k年初完好的机器数sk为状态变量, s1=1000,(3)取第k年投入高负荷的机器数xk为决策变量, 0xksk,(4)状态转移方程为 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk,(5)指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj),(6)基本方程为 fk(sk) max 5sk+3xk +fk+1(sk+1) k=5,4,3,2,1 0xksk f6(s6)0,解:,当k=5时

10、,f5(s5) max5s5+3x5+f6(s6)= max5s5+3x5=8s5 (x5*=s5) 0x5s5 0x5s5,当k=4时,f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4) 0x4s4 0x4s4 = max12.2s4+1.4x4=13.6s4 (x4*=s4) 0x4s4,当k=3时,f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3) 0x3s3 0x3s3 = max17.24s3+0.28x3=17.5s3 (x3*=s3) 0x3s3,当k=2时,f2(s2)=max5s2

11、+3x2+17.52s3=max5s2+3x2+17.52(0.9s2-0.2x2) 0x2s2 0x2s2 = max20.77s2-0.504x2=20.7s4 (x2*=0) 0x2s2,当k=1时,f1(s1)=23.7s1 (x1*=0),f1(1000)=23700,s1=1000, x1*=0,s2=900, x2*=0,s3=810, x3*=810,s4=576, x4*=576,s5=397, x5*=397,某些静态规划问题可用动态规划法来求解。,例 用动态规划法求解 max z=x1.x22.x3 x1+x2+x3=c xi0 i=1,2,3,4.4 动态规划的应用(一

12、),1 求解静态规划问题,该题在课本p145页例3,解: 把问题看成一个三阶段决策问题，对应关系 状态变量: s1, s2, s3, s4; sk表示从第k阶段到最后 一个阶段可以分配的资源，s1=c 。 决策变量： x1,x2,x3,x3 ; s.t. 0=xk=sk; 允许决策集: Dk(sk)=xk| 0=xk0 所以 d2(x2)=d2|13-x2d217-x2 由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2,对于k=1 f1(x1)=minc1d1+f2(x2) d1D1(x1) =min11d1+442-18x2 d1D1(x1) =min11d1+442-18(x1-r1+d1) d1D1(x1) =min11d1+442-18(x1-0+d1) d1D1(x1) =min-7d1-18x1+442 d1D1(x1),D1(x1)=d1|d10,r2x1-r1+d1H =d1|d10,r2+r1-x1d1H+r1-x1 =d1|d10,8-x1d19-x1,根据题意 x1=2 所以 D1(x1)=d1| 6d17 由此 d1=7 f1(x1)=-7d1-18x1+442 =-77182442 =357,将以上结果总结成下表：,设 备 更 新 问 题,一台设备的价格为P，运行寿命为n年