《动态规划方法PPT课件》由会员分享，可在线阅读，更多相关《动态规划方法PPT课件（97页珍藏版）》请在金锄头文库上搜索。
1、1,数学建模方法及其应用,韩中庚 编著,2,数 学 建 模 教 学 片,第十三章 动态规划方法,设计制作：,3,主要内容,第十三章 动态规划方法,3,2020年11月27日,动态规划的基本问题；,动态规划的基本概念与条件；,动态规划的基本方程；,动态规划的求解方法；,动态规划的应用案例分析。,4,一、动态规划的一般问题,4,2020年11月27日,动态规划（DP)是一种用于处理多阶段决策问题的数学方法。主要是先将一个复杂的问题分解成相互联系的若干阶段，每个阶段即为一个小问题，然后逐个解决，当每个阶段的决策确定之后，整个过程的决策也就确定了。 阶段一般用时间段表示(即与时间有关)，这就是“动态”
2、的含义，把这种处理问题的方法称为动态规划方法。,5,5,2020年11月27日,1. 引例：最短路线问题,(1) 问题的提出,6,6,2020年11月27日,(2) 问题的分析,1. 引例：最短路线问题,7,7,2020年11月27日,2 .用动态规划的方法分步考虑,1. 引例：最短路线问题,8,8,2020年11月27日,2 .用动态规划的方法分步考虑,9,9,2020年11月27日,2 .用动态规划的方法分步考虑,10,10,2020年11月27日,2 .用动态规划的方法分步考虑,11,11,2020年11月27日,2 .用动态规划的方法分步考虑,（4)求四个阶段最优选择：,12,12,2
3、020年11月27日,2 .用动态规划的方法分步考虑,13,13,2020年11月27日,2 .用动态规划的方法分步考虑,14,资源分配问题（背包问题） 资源分配问题是动态规划的典型问题之一，它的一般提法是：有某种资源，总量为 a ，用于 n 个项目，若分配数量 ui 用于第 i 个项目，则第 i 个项目所产生的效果（收益）为 gi（ui）。问题是如何分配资源总量 a 才能获得 n 个项目所产生的总效果（收益）最优（ max ）？ 静态规划问题,max Z = g1（u1）+ g2（u2）+ + gn（un） u1 + u2 + + un （=）a ui 0,15,例1 某公司新引进了 6 台
4、高效率生产设备，该设备可用于生产 4 种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：,利润表 单位：万元,16,16,2020年11月27日,二. 动态规划的基本概念与条件,1 . 动态规划的基本概念,(1)阶段（stage）和阶段变量,阶段是指一个问题需要作出决策的步骤，即把问题的过程分为若干个相互联系的阶段，使能按阶段的次序求解。 描述阶段的变量称为阶段变量,常用k表示。,17,17,2020年11月27日,在多阶段决策过程中，每一阶段都具有一些特征（自然状况，或客观条件），这就是状态，用来描述状态的变量称为状态变量。,(2)状态与状态变量,18,
5、18,2020年11月27日,(3)决策和决策变量,19,(3) 决策(decision)表示在某一阶段处于某种状态时， 决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值范围称为决策集，用Dk(sk)表示。,多阶段决策过程如下：,20,20,2020年11月27日,策略是一个按顺序排列的决策组成的集合。,(4)策略与子策略,21,21,2020年11月27日,(4)策略与子策略,22,22,2020年11月27日,状态函数是在确定多阶段决策过程中，由一个状态到另个状态的演变过程。,(5)状态转移函数,23,(5)状态转移方程,(6)指
6、标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。 阶段指标函数是对某一阶段的状态和决策产生的效益值的度量,用vk(sk,uk)表示。,若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为: sk+1= Tk(sk,uk) 称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。,24,24,2020年11月27日,在多阶段决策过程中，用来衡量所实现过程优劣的一种数量指标，称为指标函数。,(6) 指标函数（回收函数）,25,25,2020年11月27日,常见的两
7、种指标函数,26,26,2020年11月27日,常见的两种指标函数,27,27,2020年11月27日,(7) 最优值函数,28,28,2020年11月27日,2 . 动态规划的基本条件,二. 动态规划的基本概念与条件,*无后效性：如果某阶段状态已给定，则以后过程的发展不受以前各阶段状态的影响，也就是说当前状态就是未来过程的初始状态；,*可知性：规定的各阶段状态变量的值，由直接或间接都是可以知道的。,29,29,2020年11月27日,2 . 动态规划的基本条件,1) 它是过程各阶段状态变量和决策变量的函数；,30,1) 加法型,逆序法:,三. 动态规划的基本方程,31,其中：fk(sk)表示
8、第k阶段初始状态为sk 时，k后部子过程的最优值函数 。,状态转移方程：,（边界条件）k=1,2,n,由此得加法型逆序算法的递归方程如下：,32,2) 乘法型,33,状态转移方程：,（边界条件）k=1,2,n,动态规划方法的关键在于利用最优化原理给出最优值函数的递推关系式和边界条件，为此，必须先将问题的过程划分为几个相互联系的阶段，适当选取状态变量、决策变量、状态转移方程及最优值函数。从而把一个大问题化成一系列同类型的子问题，然后逐个求解。,由此得乘法型逆序算法的递归方程如下：,34,动态规划建模有以下过程： 将问题划分成恰当的阶段； 正确选择状态变量，使它能描述过程的演变。 确定决策变量和决
9、策允许集合。 确定状态转移方程。 明确阶段指标、过程指标和最优值函数。,三、动态规划的建模,35,k=n时，动态规划基本方程是,边界条件：,即 ：,逆序地求出最优目标函数值集合和最优决策集合。,仅就逆序法说明求解步骤：,四、动态规划问题求解的一般步骤,36,k = n1时，动态规划的基本方程是,因所有的fn(sn)都已经求出，因此可以根据sn=Tn-1 (sn-1,un-1)就n-1阶段每个可能状态sn-1 ，求出最优决策及相应的最优目标函数值fn-1(sn-1) 。,k = n2时，动态规划的基本方程是,由于fn-1(sn-1)都已经求出，因此可以根据sn-1=Tn-2 (sn-2 ,un-
10、2)就n-2阶段每个可能状态sn-2 ，求出最优决策及相应的最优目标函数值fn-2(sn-2) 。,37,k=1时，动态规划的基本方程是,由于所有的 f2(s2) 都已经求出，因此可以根据 s2=T1(s1,u1)，就第1阶段每个可能状态s1 ,求最优决策及相应的最优目标函数值 f1(s1) .,依次下去 .,最后，顺序地求出最优目标值、最优策略和最优路径。,38,38,2020年11月27日,三. 动态规划的基本方程,1 . 动态规划的逆序解法,39,39,2020年11月27日,40,40,2020年11月27日,三. 动态规划的基本方程,2 . 动态规划的顺序解法,41,41,2020年
11、11月27日,2 . 动态规划的顺序解法,42,42,2020年11月27日,四. 动态规划的求解方法,1 . 动态规划的逆序解法,43,43,2020年11月27日,1 . 动态规划的逆序解法,44,44,2020年11月27日,1 . 动态规划的逆序解法,45,解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。令变量x1，x2，x3为决策变量。,例2：用逆推解法求解下面问题:,则有：x3=s3, 0 x2s2, 0 x1s1=c,令状态变量为： s3= x3, s2 = x2+x3, s1=c = x1+x2+x3,即 s3= x3, s2 = s3+ x2, s1=c = s2
12、+ x1。,于是状态转移方程为： s3=s2-x2, s2 =s1-x1,46,各阶段指标按乘积方式结合。即令:,由逆推解法：,即最优解 x3*=s3 。,令最优值函数f k(sk)表示第k阶段从初始状态sk出发，从第k阶段到第3阶段所得到的效益最大值。,47,得 和 x2=0(舍去),故 为极大值点，也就是最大值点。,48,同上对h1(s1, x1)求导并令导数等于0可得：,由于s1=c，,49,由s2 =s1x1，,由s3 =s2x2，,因此最优解为：,最大值为：,50,逆推实例,例 1 分配投资问题 某公司有资金 10 万元，若投资于项目 k （k = 1，2，3）的投资额为 xk 时，
13、其收益分别为 g1（x1）= 4x1 ， g2（x2）= 9x2 ， g3（x3）= 2x32 ，问应该如何分配投资数额才能使总收益最大？ 该问题表面上看与时间无明显关系，其静态模型：,Max z = 4x1 + 9x2 + 2x32 x1 + x2 + x3 = 10 xi 0 （i = 1，2，3）,51,建立 DP 模型与求解 如何应用动态规划方法求解此类静态规划问题？一般我们可以人为地给它赋予“时段”的概念，将投资项目按任意顺序进行排序，如首先考虑项目1 的投资，然后考虑项目2 的投资 ，即将问题人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。这样，可以将上述问题转化为一个
14、 n 阶段决策过程。 分配投资问题的分析求解如下：,逆推实例,52,逆推实例,建立 DP 模型与求解 （1）阶段 k = 1，2，3，分别表示项目1，2，3 （2）状态变量 sk ：第 k 段初拥有的资金总量（分配给第 k 至第 3 个项目的资金数量） （3）决策变量 uk ：第 k 段的投资量（分配给第 k 个项目的资金数量），决策集合 Dk（sk）= uk 0 uk sk （4）状态转移方程 sk+1 = sk - uk （5）阶段指标值（函数） vk（sk，uk）= gk（xk） （6）定义fk（sk）：第 k 段初拥有的资金总量为 sk 时，第 k 至第 3 段按最优投资策略所获得的第
15、 k 至第 3 段的总收益。,53,逆推实例,动态规划结构图,sk,sk+1 = sk - uk,k阶段,fk（sk）,k+1阶段,fk+1（sk+1）,max,（ ）,gk（xk）,0 uk sk,建立动态规划基本方程：（逆序递推方程）,fk（sk）= max gk（xk）+ fk+1（sk+1） ，k = 3，2，1,0 uk sk,f4（s4）= 0,54,逆推实例,7 逆序递推求解动态规划基本方程 k = 3,f3（s3）= Max 2x32 + f4（s4） = Max 2x32 + 0 ,0 u3 s3,0 u3 s3,f3 *（s3）= 2s32 ， uk* = s3,55,逆推
16、实例,8 建立 DP 模型与求解 k = 2,f2（s2）= Max 9x2 + f3（s3） = Max 9x2 + 2s32 ,0 u2 s2,= Max 9x2 + 2（s2 x2 ）2 ,可以证明极大值只可能在端点取得，即： f2（0）= 2s22 f2（s2）= 9s2 s2 9/2 时， f2（0） f2（s2），此时 x2* = 0 s2 9/2 时， f2（0） f2（s2），此时 x2* = s3,56,逆推实例,9 k = 1,当f2（s2 ）= 9s2 ， f1（10）= Max 4x1 + f2（s2）,0 x1 10,= Max 9s1 5x1 = 9s1 ， x1* = 0,但此时 s2 = s1 x1 =10 - 0 9/2 与s2 9/2 矛盾，故舍去。,57,逆推实例,9 k = 1,当f2（s2 ）= 2s22 ， f1（10）= Max
