《动态规划方法》PPT课件.ppt

数学建模方法及其应用,韩中庚 编著,数 学 建 模 教 学 片,第十三章 动态规划方法,设计制作：,主要内容,第十三章 动态规划方法,3,2019年8月7日,动态规划的基本问题；,动态规划的基本概念与条件；,动态规划的基本方程；,动态规划的求解方法；,动态规划的应用案例分析。,一、动态规划的一般问题,4,2019年8月7日,动态规划（DP)是一种用于处理多阶段决策问题的数学方法。主要是先将一个复杂的问题分解成相互联系的若干阶段，每个阶段即为一个小问题，然后逐个解决，当每个阶段的决策确定之后，整个过程的决策也就确定了。 阶段一般用时间段表示(即与时间有关)，这就是“动态”的含义，把这种处理问题的方法称为动态规划方法。,5,2019年8月7日,1. 引例：最短路线问题,(1) 问题的提出,6,2019年8月7日,(2) 问题的分析,1. 引例：最短路线问题,7,2019年8月7日,2 .用动态规划的方法分步考虑,1. 引例：最短路线问题,8,2019年8月7日,2 .用动态规划的方法分步考虑,9,2019年8月7日,2 .用动态规划的方法分步考虑,10,2019年8月7日,2 .用动态规划的方法分步考虑,11,2019年8月7日,2 .用动态规划的方法分步考虑,（4)求四个阶段最优选择：,12,2019年8月7日,2 .用动态规划的方法分步考虑,13,2019年8月7日,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 种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：,利润表 单位：万元,16,2019年8月7日,二. 动态规划的基本概念与条件,1 . 动态规划的基本概念,(1)阶段（stage）和阶段变量,阶段是指一个问题需要作出决策的步骤，即把问题的过程分为若干个相互联系的阶段，使能按阶段的次序求解。 描述阶段的变量称为阶段变量,常用k表示。,17,2019年8月7日,在多阶段决策过程中，每一阶段都具有一些特征（自然状况，或客观条件），这就是状态，用来描述状态的变量称为状态变量。,(2)状态与状态变量,18,2019年8月7日,(3)决策和决策变量,19,(3) 决策(decision)表示在某一阶段处于某种状态时， 决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值范围称为决策集，用Dk(sk)表示。,多阶段决策过程如下：,20,2019年8月7日,策略是一个按顺序排列的决策组成的集合。,(4)策略与子策略,21,2019年8月7日,(4)策略与子策略,22,2019年8月7日,状态函数是在确定多阶段决策过程中，由一个状态到另个状态的演变过程。,(5)状态转移函数,23,(5)状态转移方程,(6)指标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。 阶段指标函数是对某一阶段的状态和决策产生的效益值的度量,用vk(sk,uk)表示。,若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为: sk+1= Tk(sk,uk) 称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。,24,2019年8月7日,在多阶段决策过程中，用来衡量所实现过程优劣的一种数量指标，称为指标函数。,(6) 指标函数（回收函数）,25,2019年8月7日,常见的两种指标函数,26,2019年8月7日,常见的两种指标函数,27,2019年8月7日,(7) 最优值函数,28,2019年8月7日,2 . 动态规划的基本条件,二. 动态规划的基本概念与条件,*无后效性：如果某阶段状态已给定，则以后过程的发展不受以前各阶段状态的影响，也就是说当前状态就是未来过程的初始状态；,*可知性：规定的各阶段状态变量的值，由直接或间接都是可以知道的。,29,2019年8月7日,2 . 动态规划的基本条件,1) 它是过程各阶段状态变量和决策变量的函数；,30,1) 加法型,逆序法:,三. 动态规划的基本方程,31,其中：fk(sk)表示第k阶段初始状态为sk 时，k后部子过程的最优值函数 。,状态转移方程：,（边界条件）k=1,2,n,由此得加法型逆序算法的递归方程如下：,32,2) 乘法型,33,状态转移方程：,（边界条件）k=1,2,n,动态规划方法的关键在于利用最优化原理给出最优值函数的递推关系式和边界条件，为此，必须先将问题的过程划分为几个相互联系的阶段，适当选取状态变量、决策变量、状态转移方程及最优值函数。从而把一个大问题化成一系列同类型的子问题，然后逐个求解。,由此得乘法型逆序算法的递归方程如下：,34,动态规划建模有以下过程： 将问题划分成恰当的阶段； 正确选择状态变量，使它能描述过程的演变。 确定决策变量和决策允许集合。 确定状态转移方程。 明确阶段指标、过程指标和最优值函数。,三、动态规划的建模,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-2)就n-2阶段每个可能状态sn-2 ，求出最优决策及相应的最优目标函数值fn-2(sn-2) 。,37,k=1时，动态规划的基本方程是,由于所有的 f2(s2) 都已经求出，因此可以根据 s2=T1(s1,u1)，就第1阶段每个可能状态s1 ,求最优决策及相应的最优目标函数值 f1(s1) .,依次下去 .,最后，顺序地求出最优目标值、最优策略和最优路径。,38,2019年8月7日,三. 动态规划的基本方程,1 . 动态规划的逆序解法,39,2019年8月7日,40,2019年8月7日,三. 动态规划的基本方程,2 . 动态规划的顺序解法,41,2019年8月7日,2 . 动态规划的顺序解法,42,2019年8月7日,四. 动态规划的求解方法,1 . 动态规划的逆序解法,43,2019年8月7日,1 . 动态规划的逆序解法,44,2019年8月7日,1 . 动态规划的逆序解法,45,解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。令变量x1，x2，x3为决策变量。,例2：用逆推解法求解下面问题:,则有：x3=s3, 0x2s2, 0x1s1=c,令状态变量为： s3= x3, s2 = x2+x3, s1=c = x1+x2+x3,即 s3= x3, s2 = s3+ x2, s1=c = s2+ 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 时，其收益分别为 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 的投资 ，即将问题人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。这样，可以将上述问题转化为一个 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 段按最优投资策略所获得的第 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,逆推实例,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 4x1 + f2（s2）,0 x1 10,= Max 4s1 + 2（s1 x1 ）2 ,同样可以证明极大值只可能在端点取得，比较两个端点： x1 = 0 时， f1（10）= 200 ， x1 = 10 时， f1（10）= 40 所以 x1* = 0,58,逆推实例,10、顺序确定最优策略。,s1= 10,x1* = 0,s2 = s1 x1* = 10 9/2,x2* = 0,s3 = s2 x2* = 10,x3* = 10,最优投资方案为全部资金投资于第 3 个项目，可获最大收益 200 万元。,59,例1 某公司新引进了 6 台高效率生产设备，该设备可用于生产 4 种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：,利润表 单位：万元,60,该公司这 6 台设备在 4 种产品的生产中能够发挥最大的效益，应该如何分配这 6 台设备，才能获得最大的总利润？ 分析、建模 此决策问题如按 4 种产品的一种顺序（可以任意排列，不妨按产品的自然顺序），将产品 1 分配的设备数量作为第一阶段需作出的决策，将产品 2 分配的设备数量作为第二阶段需作出的决策，将产品 3 分配的设备数量作为第三阶段需作出的决策，将产品 4 分配的设备数量作为第四阶段需作出的决策，这显然就是一个多阶段决策问题。因此有：,61,动态规划在经济管理中的应用 1、阶段 k ：第 k 种产品，k=1，2，3，4 2、状态变量 sk ：当按顺序应第 k 种产品分配设备时所余有的总量。 3、决策变量 uk ：分配给第 k 种产品的设备数量。 Dk（sk）= uk | uk =0，1，2， sk 4、状态转移方程： sk+1 = sk - uk 5、定义阶段指标值（函数） vk（sk，uk）= vk（ uk ）：即分配给第 k 种产品的设备数量为 uk 时，第 k 种产品所创造的利润（如利润表）。,62,动态规划在经济管理中的应用 6、定义 fk（sk）：第 k 种产品分配设备时所余有的设备数量为 sk ，第 k 种产品至第四种产品按最优分配策略分配所余有的设备，第 k 种产品至第四种产品所创造的利润总和 。（第 k 种产品至第四种产品按某种设备分配策略所创造的最大总利润 。 7、作出动态规划结构图：,sk,sk+1 = sk - uk,k阶段,fk（sk）,k+1阶段,fk+1（sk+1）,max,（ ）,vk（ uk）,uk =0，1，2， sk,63,动态规划在经济管理中的应用 8、建立动态规划基本方程：（逆序递推方程）,fk（sk）= max vk（ uk）+ fk+1（sk+1），k= 3，2，1,uk = 0，1，2，sk,f4（s4）= max v4（ u4）,u4 = 0，1，2，s4,9、逆序递推求解动态规划基本方程。,64,动态规划在经济管理中的应用 k= 4 时，状态集合 S4= 0，1，2，3，4，5，6 f4（s4）= max v4（ u4）,65,动态规划在经济管理中的应用 k= 3 时，状态集合 S3= 0，1，2，3，4，5，6 f3（s3）= max v3（ u3）+ f4（s4）,66,k= 2 时，状态集合 S2= 0，1，2，3，4，5，6 f2（s2）= max v2（ u2）+ f3（s3）,67,k= 1 时，状态集合 S1= 6 f1（s1）= max v1（ u1）+ f2（s2）,10、顺序确定最优策略之一。,s2= 6,s1= 6,u1= 0,u4= 1,u2= 2,u3= 3,s4= 1,s3= 4,68,动态规划在经济管理中的应用 该公司设备分配的所有最优方案：,69,2019年8月7日,四. 动态规划的求解方法,2 . 动态规划的顺序解法,70,2019年8月7日,2 . 动态规划的顺序解法,71,2019年8月7日,2 . 动态规划的顺序解法,72,解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。令变量x1，x2，x3为决策变量；,例4：用顺推法求解下面问题:,设状态变量为s0,3x1=s1, 3x1+2x2=s2, 3x1+2x2+ x3=s39,则: 3x1=s1, s1+2x2=s2, s2+x3=s39,则状态转移方程为：s1=s2-2x2, s2=s3-x3,73,由顺推解法,即最优解x1=s13。,(它不在决策集内),最优值函数f k(sk)表示为第k阶段的结束状态为sk，从第1阶段到第k阶段所得到的效益最大值。,74,则最大值在端点上，,最大值点为x2=0。故得到：,最优解x2=0。,75,而,最大值点为x3=s3，故得到：,最优解x3=s3 。,故该点为极小点.,76,由于s3不知道，故须再对s3求一次极值，即,反推回去即可得最优解为：由x1*=x2*=0，x3*=9。,最大值为：,例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。,解：依据题意，是要求 f4(60) 。,按顺序解法计算。 第一阶段：求 f1(x)。显然有 f1(x) g1(x)，得到下表,第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。,最优策略为（40，20），此时最大利润为120万元。,同理可求得其它 f2(x) 的值。,最优策略为（30，20），此时最大利润为105万元。,最优策略为（20，20），此时最大利润为90万元。,最优策略为（20，10），此时最大利润为70万元。,最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。,f2(0) 0。最优策略为（0，0），最大利润为0万元。 得到下表,最优策略为（20，0），此时最大利润为50万元。,第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。,最优策略为（20，10，30），最大利润为155万元。,同理可求得其它 f3(x) 的值。得到下表,第四阶段：求 f4(60)。即问题的最优策略。,最优策略为（20，0，30，10），最大利润为160万元。,87,2019年8月7日,1.问题的提出,现假设有20名队员准备参加数学建模竞赛