动态规划方法PPT课件

《动态规划方法PPT课件》由会员分享，可在线阅读，更多相关《动态规划方法PPT课件（97页珍藏版）》请在金锄头文库上搜索。

1、数数 学学 建建 模模 教教 学学 片片 第十三章第十三章 动态规划方法动态规划方法32024年年7月月21日日 动态规划的基本问题；动态规划的基本问题； 动态规划的基本概念与条件；动态规划的基本概念与条件； 动态规划的动态规划的基本方程；基本方程； 动态规划的求解方法；动态规划的求解方法； 动态规划的应用案例分析。动态规划的应用案例分析。 一、动态规划的一般问题一、动态规划的一般问题42024年年7月月21日日 动态规划（动态规划（DP)是一种用于处理多阶段决是一种用于处理多阶段决策问题的数学方法。主要是先将一个复杂的策问题的数学方法。主要是先将一个复杂的问题分解成相互联系的若干阶段，每个阶

2、段问题分解成相互联系的若干阶段，每个阶段即为一个小问题，然后逐个解决，当每个阶即为一个小问题，然后逐个解决，当每个阶段的决策确定之后，整个过程的决策也就确段的决策确定之后，整个过程的决策也就确定了。定了。阶段一般用时间段表示阶段一般用时间段表示(即与时间有关即与时间有关)，这就是这就是“动态动态”的含义，把这种处理问题的的含义，把这种处理问题的方法称为方法称为动态规划方法动态规划方法。52024年年7月月21日日 1. 1. 引例：最短路线问题引例：最短路线问题 (1) 问题的提出问题的提出62024年年7月月21日日 (2) 问题的分析问题的分析 1. 1. 引例：最短路线问题引例：最短路线

3、问题72024年年7月月21日日 2 .用动态规划的方法分步考虑用动态规划的方法分步考虑 1. 1. 引例：最短路线问题引例：最短路线问题82024年年7月月21日日2 .用动态规划的方法分步考虑用动态规划的方法分步考虑92024年年7月月21日日2 .用动态规划的方法分步考虑用动态规划的方法分步考虑102024年年7月月21日日2 .用动态规划的方法分步考虑用动态规划的方法分步考虑112024年年7月月21日日2 .用动态规划的方法分步考虑用动态规划的方法分步考虑（4)4)求四个阶段最优选择：求四个阶段最优选择：122024年年7月月21日日2 .用动态规划的方法分步考虑用动态规划的方法分步

4、考虑132024年年7月月21日日2 .用动态规划的方法分步考虑用动态规划的方法分步考虑14资源分配问题（背包问题）资源分配问题（背包问题） 资源分配问题是动态规划的典型问题之一，它的一般提法是：资源分配问题是动态规划的典型问题之一，它的一般提法是：有某种资源，总量为有某种资源，总量为 a ，用于，用于 n 个项目，若分配数量个项目，若分配数量 ui 用于第用于第 i 个个项目，则第项目，则第 i 个项目所产生的效果（收益）为个项目所产生的效果（收益）为 gi（ui）。问题是如何）。问题是如何分配资源总量分配资源总量 a 才能获得才能获得 n 个项目所产生的个项目所产生的总效果总效果（收益）最

5、优（收益）最优（ max ）？）？ 静态规划问题静态规划问题 max Z = g1（u1）+ g2（u2）+ + gn（un） u1 + u2 + + un （=）a ui 015例例1 某公司新引进了某公司新引进了 6 台高效率生产设备，该设备可用于生产台高效率生产设备，该设备可用于生产 4 种种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：润也不相同。其详细资料如下：利润表利润表 单位：万元单位：万元设备数量设备数量4 种种 产产 品品产产 品品 1产产 品品 2产产 品品 3产产 品品 40

6、1234560204260758590025455765707301839617890950284765748085162024年年7月月21日日 二二. . 动态规划的基本概念与条件动态规划的基本概念与条件 1 . 动态规划的基本概念动态规划的基本概念(1)阶段（阶段（stage）和阶段变量）和阶段变量阶段阶段是指一个问题需要作出决策的步是指一个问题需要作出决策的步骤，即把问题的过程分为骤，即把问题的过程分为若干个若干个相互联系相互联系的阶段，使能按的阶段，使能按阶段的次序阶段的次序求解。求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量, ,常用常用k k表示。表示。 172024

7、年年7月月21日日在多阶段决策过程中，每一阶段都具有一些特在多阶段决策过程中，每一阶段都具有一些特征（自然状况，或客观条件），这就是征（自然状况，或客观条件），这就是状态状态，用来，用来描述状态的变量称为描述状态的变量称为状态变量状态变量。(2)(2)状态与状态变量状态与状态变量182024年年7月月21日日(3)(3)决策和决策变量决策和决策变量 19 (3) 决策决策(decision)表示在某一阶段处于某种状态时，表示在某一阶段处于某种状态时， 决策者在若干种方案中作出的选择决定。描述决策的变量称决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量决策变量，第，第k阶段的决策变量

8、常用阶段的决策变量常用uk表示。表示。决策变量的取值决策变量的取值范围称为范围称为决策集决策集，用，用Dk(sk)表示。表示。T1s1s2v1u1T2s3v2u2Tksksk+1vkukTnsnsn+1vnun多阶段决策过程如下：多阶段决策过程如下：202024年年7月月21日日策略策略是一个是一个按顺序排列按顺序排列的决策组成的集合。的决策组成的集合。(4)(4)策略与子策略策略与子策略212024年年7月月21日日(4)(4)策略与子策略策略与子策略222024年年7月月21日日 状态函数状态函数是在确定多阶段决策过程中，由是在确定多阶段决策过程中，由一个一个状态到另个状态状态到另个状态的

9、演变过程。的演变过程。(5)状态转移函数状态转移函数23(5)状态转移方程状态转移方程 (6)指标函数指标函数和和最优值函数最优值函数指标函数分为阶段指标函数和过程指标函数。指标函数分为阶段指标函数和过程指标函数。阶阶段段指指标标函函数数是是对对某某一一阶阶段段的的状状态态和和决决策策产产生生的的效效益益值值的的度度量量,用用vk(sk,uk)表示。表示。 若若第第k阶阶段段的的状状态态变变量量值值为为sk，当当决决策策变变量量uk的的取取值值决决定定后后，下下一一阶阶段段状状态态变变量量sk+1的的值值也也就就完完全全确确定定。即即sk+1的的值值对对应应于于sk和和uk的值。这种对应关系记

10、为的值。这种对应关系记为: sk+1= Tk(sk,uk)称称为为状状态态转转移移方方程程。状状态态转转移移方方程程描描述述了了由由一一个个阶阶段段的的状状态态到到下下一阶段的状态的演变规律。一阶段的状态的演变规律。242024年年7月月21日日 在多阶段决策过程中，用来在多阶段决策过程中，用来衡量所实现过程优衡量所实现过程优劣的一种数量指标劣的一种数量指标，称为指标函数。，称为指标函数。 (6) 指标函数（回收函数）指标函数（回收函数）252024年年7月月21日日常见的两种指标函数常见的两种指标函数262024年年7月月21日日常见的两种指标函数常见的两种指标函数272024年年7月月21

11、日日(7) 最优值函数最优值函数282024年年7月月21日日 2 . 动态规划的基本条件动态规划的基本条件 二二. . 动态规划的基本概念与条件动态规划的基本概念与条件*无后效性：无后效性：如果某阶段状态已给定，则以后过程如果某阶段状态已给定，则以后过程的发展的发展不受不受以前各阶段状态的影响，也就是说当以前各阶段状态的影响，也就是说当前状态就是未来过程的前状态就是未来过程的初始状态初始状态；*可知性：可知性：规定的各阶段状态变量的值，由直接规定的各阶段状态变量的值，由直接或间接都是可以知道的。或间接都是可以知道的。292024年年7月月21日日2 . 动态规划的基本条件动态规划的基本条件1

12、) 它是过程各阶段状态变量和决策变量的函数；它是过程各阶段状态变量和决策变量的函数；301) 加法型加法型 逆序法逆序法: 三三. . 动态规划的基本方程动态规划的基本方程31 其中：其中：fk(sk)表示第表示第k阶段初始状态为阶段初始状态为sk 时，时，k后部子后部子过程的最优值函数过程的最优值函数 。状态转移方程：状态转移方程：（边界条件）（边界条件）k=1,2,n由此得由此得加法型加法型逆序算法的递归方程如下：逆序算法的递归方程如下：322) 乘法型乘法型33状态转移方程：状态转移方程：（边界条件）（边界条件）k=1,2,n 动态规划方法的关键在于动态规划方法的关键在于利用最优化原理给

13、出最优值函利用最优化原理给出最优值函数的递推关系式和边界条件数的递推关系式和边界条件，为此，必须先将问题的过程，为此，必须先将问题的过程划分为几个相互联系的阶段，划分为几个相互联系的阶段，适当选取状态变量、决策变适当选取状态变量、决策变量、状态转移方程及最优值函数量、状态转移方程及最优值函数。从而把一个大问题化成。从而把一个大问题化成一系列同类型的子问题，然后逐个求解。一系列同类型的子问题，然后逐个求解。由此得由此得乘法型乘法型逆序算法的递归方程如下：逆序算法的递归方程如下：34 动态规划建模有以下过程：动态规划建模有以下过程：将问题划分成恰当的阶段；将问题划分成恰当的阶段；正确选择状态变量，

14、使它能描述过程的演变。正确选择状态变量，使它能描述过程的演变。确定决策变量和决策允许集合。确定决策变量和决策允许集合。确定状态转移方程。确定状态转移方程。明确阶段指标、过程指标和最优值函数。明确阶段指标、过程指标和最优值函数。三、动态规划的建模三、动态规划的建模35k=n时，动态规划基本方程是时，动态规划基本方程是 边界条件：边界条件：即即 ： 逆序地求出最优目标函数值集合和最优决策集合。逆序地求出最优目标函数值集合和最优决策集合。仅就仅就逆序法逆序法说明求解步骤：说明求解步骤：四、动态规划问题求解的一般步骤四、动态规划问题求解的一般步骤36k = n1时，动态规划的基本方程是动态规划的基本方

15、程是 因所有的因所有的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

16、k=1时，动态规划的基本方程是时，动态规划的基本方程是 由于所有的由于所有的 f2(s2) 都已经求出，因此可以根据都已经求出，因此可以根据 s2=T1(s1,u1)，就第就第1阶段每个可能状态阶段每个可能状态s1 ,求最优决策及相应求最优决策及相应的最优目标函数值的最优目标函数值 f1(s1) . 依次下去依次下去 . 最后，顺序地求出最优目标值、最优策略和最优路径。最后，顺序地求出最优目标值、最优策略和最优路径。382024年年7月月21日日 三三. . 动态规划的基本方程动态规划的基本方程 1 . 动态规划的逆序解法动态规划的逆序解法392024年年7月月21日日 1 . 动态规划的逆序

17、解法动态规划的逆序解法402024年年7月月21日日 三三. . 动态规划的基本方程动态规划的基本方程 2 . 动态规划的顺序解法动态规划的顺序解法412024年年7月月21日日 2 . 动态规划的顺序解法动态规划的顺序解法422024年年7月月21日日 四四. . 动态规划的求解方法动态规划的求解方法 1 . 动态规划的逆序解法动态规划的逆序解法432024年年7月月21日日 1 . 动态规划的逆序解法动态规划的逆序解法442024年年7月月21日日 1 . 动态规划的逆序解法动态规划的逆序解法45解解: : 按按问问题题的的变变量量个个数数划划分分阶阶段段, ,把把它它看看作作一一个个三三

18、阶阶段段决决策策问题。问题。令变量令变量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- -x146各阶段指标按乘积方式结合。即令各阶段指标按乘积方式结合。即令: : 由逆推解法由逆推解法： 即最优解即最优解 x3 3* *=s=s3 3

19、 。 令最优值函数令最优值函数f k k(s(sk k) )表示第表示第k k阶段从初始状态阶段从初始状态s sk k出发，出发，从第从第k k阶段到第阶段到第3 3阶段所得到的效益最大值。阶段所得到的效益最大值。 47得得 和和 x2=0( (舍去舍去) )故故 为极大值点，也就是最大值点。为极大值点，也就是最大值点。48同上对同上对h h1 1( (s1, x1) )求导并令导数等于求导并令导数等于0 0可得：可得： 由于由于s s1 1=c=c， 49由由s2 =s1x1，由由s3 =s2x2，因此最因此最优优解解为为： 最大最大值为值为： 50逆推实例逆推实例逆推实例逆推实例例例 1

20、分配投资问题分配投资问题 某公司有资金某公司有资金 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 模型与求解模型与求

21、解 如何应用动态规划方法求解此类静态规划问题？一般我们可以如何应用动态规划方法求解此类静态规划问题？一般我们可以人为地给它赋予人为地给它赋予“时段时段”的概念，将投资项目按任意顺序进行排序，的概念，将投资项目按任意顺序进行排序，如首先考虑项目如首先考虑项目1 的投资，然后考虑项目的投资，然后考虑项目2 的投资的投资 ，即将问题，即将问题人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。这样，可以将上述问题转化为一个这样，可以将上述问题转化为一个 n 阶段决策过程。阶段决策过程。 分配投资问题的分析求解如下：分配投资问题的分析

22、求解如下：逆推实例逆推实例逆推实例逆推实例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

23、）阶段指标值（函数）阶段指标值（函数） 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

24、）+ fk+1（sk+1） ，k = 3，2，10 uk skf4（s4）= 054逆推实例逆推实例逆推实例逆推实例7 逆序递推求解动态规划基本方程逆序递推求解动态规划基本方程k = 3 f3（s3）= Max 2x32 + f4（s4） = Max 2x32 + 0 0 u3 s30 u3 s3f3 *（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 可以证明极大值只可

25、能在端点取得，即：可以证明极大值只可能在端点取得，即： 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逆推实例逆推实例

26、逆推实例逆推实例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= 10x1* = 0s2 = s1 x1* = 10 9/2 x2* = 0 s3 = s2 x2* = 10x

27、3* = 10最优投资方案为全部资金投资于第最优投资方案为全部资金投资于第 3 个项目，可获最大收益个项目，可获最大收益 200 万元。万元。59例例1 某公司新引进了某公司新引进了 6 台高效率生产设备，该设备可用于生产台高效率生产设备，该设备可用于生产 4 种种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：润也不相同。其详细资料如下：利润表利润表 单位：万元单位：万元设备数量设备数量4 种种 产产 品品产产 品品 1产产 品品 2产产 品品 3产产 品品 4012345602042607585

28、9002545576570730183961789095028476574808560该公司这该公司这 6 台设备在台设备在 4 种产品的生产中能够发挥最大的效益，应该种产品的生产中能够发挥最大的效益，应该如何分配这如何分配这 6 台设备，才能获得最大的总利润？台设备，才能获得最大的总利润？分析、建模分析、建模 此决策问题如按此决策问题如按 4 种产品的一种顺序（可以任意排列，不妨按种产品的一种顺序（可以任意排列，不妨按产品的自然顺序），将产品产品的自然顺序），将产品 1 分配的设备数量作为分配的设备数量作为第一阶段第一阶段需作出需作出的决策，将产品的决策，将产品 2 分配的设备数量作为分配的

29、设备数量作为第二阶段第二阶段需作出的决策，将需作出的决策，将产品产品 3 分配的设备数量作为分配的设备数量作为第三阶段第三阶段需作出的决策，将产品需作出的决策，将产品 4 分配分配的设备数量作为的设备数量作为第四阶段第四阶段需作出的决策，这显然就是一个多阶段决需作出的决策，这显然就是一个多阶段决策问题。因此有：策问题。因此有： 61动态规划在经济管理中的应用动态规划在经济管理中的应用1、阶段阶段 k ：第：第 k 种产品，种产品，k=1，2，3，42、状态变量状态变量 sk ：当按顺序应第：当按顺序应第 k 种产品分配设备时所余有的总量。种产品分配设备时所余有的总量。3、决策变量决策变量 uk

30、 ：分配给第：分配给第 k 种产品的设备数量。种产品的设备数量。 Dk（sk）= uk | uk =0，1，2， sk 4、状态转移方程：状态转移方程： sk+1 = sk - uk5、定义阶段指标值（函数）定义阶段指标值（函数） vk（sk，uk）= vk（ uk ）：即分配给第）：即分配给第 k 种产品的设备数量为种产品的设备数量为 uk 时，第时，第 k 种产品所创造的利润（如利种产品所创造的利润（如利润表）。润表）。62动态规划在经济管理中的应用动态规划在经济管理中的应用6、定义定义 fk（sk）：第）：第 k 种产品分配设备时所余有的设备数量为种产品分配设备时所余有的设备数量为 sk

31、 ，第，第 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、建立动态规划基本方程：（

32、逆序递推方程）建立动态规划基本方程：（逆序递推方程）fk（sk）= max vk（ uk）+ fk+1（sk+1），k= 3，2，1uk = 0，1，2，skf4（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） u4 s4v4（ u4）f4（s4）u*4012345600001028281202847472302847656534028476574744

33、5028476574808056028476574808585665动态规划在经济管理中的应用动态规划在经济管理中的应用k= 3 时，状态集合时，状态集合 S3= 0，1，2，3，4，5，6 f3（s3）= max v3（ u3）+ f4（s4） u3 s3v3（ u3）+ f4（s4）f3（s3）u*3012345600+00010+2818+028020+4718+2839+047030+6518+4739+2861+067240+7418+6539+4761+2878+089350+8018+7439+6561+4778+2890+0108360+8518+8039+7461+6578+

34、4790+2895+01263s40123456f4（s4）028476574808566k= 2 时，状态集合时，状态集合 S2= 0，1，2，3，4，5，6 f2（s2）= max v2（ u2）+ f3（s3） u2 s2v2（ u2）+ f3（s3）f2（s2）u*2012345600+00010+2825+028020+4725+2845+053130+6725+4745+2857+073240+8925+6745+4757+2865+0921，250+10825+8945+6757+4765+2870+0114160+12625+10845+8957+6765+4770+2873+

35、01342s30123456f3（s3）02847678910812667k= 1 时，状态集合时，状态集合 S1= 6 f1（s1）= max v1（ u1）+ f2（s2） u1 s1v1（ u1）+ f2（s2）f1（s1）u*1012345600+13420+11442+9260+7375+5385+2890+01340，1，210、顺序确定顺序确定最优策略之一。最优策略之一。s2= 6s1= 6u1= 0u4= 1u2= 2u3= 3s4= 1s3= 4s20123456f2（s2）02853739211413468动态规划在经济管理中的应用动态规划在经济管理中的应用该公司设备分配的

36、所有最优方案：该公司设备分配的所有最优方案：最大总利润最大总利润 （万元）（万元）产品产品1产品产品2产品产品3产品产品4方案方案10台台2台台3台台1台台134方案方案21台台1台台3台台1台台134方案方案32台台1台台1台台2台台134方案方案42台台2台台0台台2台台134692024年年7月月21日日 四四. . 动态规划的求解方法动态规划的求解方法 2 . 动态规划的顺序解法动态规划的顺序解法702024年年7月月21日日 2 . 动态规划的顺序解法动态规划的顺序解法712024年年7月月21日日 2 . 动态规划的顺序解法动态规划的顺序解法72解解: : 按按问问题题的的变变量量

37、个个数数划划分分阶阶段段, ,把把它它看看作作一一个个三三阶阶段段决决策策问问题。题。令变量令变量x1，x2，x3为决策变量；为决策变量；例例4：用用顺顺推推法法求求解解下面下面问题问题: : 设状态变量为设状态变量为s0,3x1=s1, 3x1+2x2=s2, 3x1+2x2+ x3=s39则则: : 3 3x1 1=s=s1 1, s, s1 1+2+2x2=s=s2 2, s, s2 2+ +x3 3=s=s3 39 9则状态转移方程为：则状态转移方程为：s s1 1=s=s2 2-2-2x2 2, s, s2 2=s=s3 3- -x3 373由顺推解法由顺推解法即最优解即最优解x1=

38、s13。 (它不在决策集内它不在决策集内) 最优值函数最优值函数f k k(s(sk k) )表示为第表示为第k k阶段的结束状态为阶段的结束状态为s sk k，从，从第第1 1阶段到第阶段到第k k阶段所得到的效益最大值。阶段所得到的效益最大值。 74则则最大最大值值在端点上，在端点上，最最大大值值点点为为x2 2=0=0。故得到。故得到：最最优优解解x2 2=0=0。 75而而最大值点为最大值点为x3 3=s=s3 3，故得到：，故得到：最优解最优解x3 3= =s s3 3 。故该点为极小点故该点为极小点. .76由于由于s s3 3不知道，故须再对不知道，故须再对s s3 3求一次极值

39、，即求一次极值，即反推回去即可得最反推回去即可得最优优解解为为：由：由x1 1* *= =x2 2* *=0=0，x3 3* *=9=9。最大最大值为值为： 例题：例题： 设国家拨给设国家拨给60万元投资，供四个工厂扩建使用，每万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。利润函数如下表所示。 投资投资利润利润0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，

40、是要求解：依据题意，是要求 f4(60) 。按顺序解法计算。按顺序解法计算。第一阶段：求第一阶段：求 f1(x)。显然有。显然有 f1(x) g1(x)，得到下表，得到下表 投资投资利润利润0102030405060f1(x) g1(x)0205065808585最优策略最优策略0102030405060第二阶段：求第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。何进行投资分配，以取得最大的总利润。最优策略为（最优策略为（40，20），此时最大利润为），此时最大利润为120万元。万元。同理可求得其它同理可求得其它 f2(x

41、) 的值。的值。最优策略为（最优策略为（30，20），此时最大利润为），此时最大利润为105万元。万元。最优策略为（最优策略为（20，20），此时最大利润为），此时最大利润为90万元。万元。最优策略为（最优策略为（20，10），此时最大利润为），此时最大利润为70万元。万元。最优策略为（最优策略为（10，0）或（）或（ 0 ， 10 ） ，此时最大利润，此时最大利润为为20万元。万元。 f2(0) 0。最优策略为（最优策略为（0，0），最大利润为），最大利润为0万元。万元。 得到下表得到下表最优策略为（最优策略为（20，0），此时最大利润为），此时最大利润为50万元。万元。 投资投资利润利润0

42、102030405060f2(x)020507090105120最优策略最优策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三阶段：求第三阶段：求 f3(x)。此时需考虑第一、第二及第三个。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。工厂如何进行投资分配，以取得最大的总利润。最优策略为（最优策略为（20，10，30），最大利润为），最大利润为155万元。万元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表 投资投资利润利润0102030405060f3(x)02560851101351

43、55最优最优策略策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四阶段：求第四阶段：求 f4(60)。即问题的最优策略。即问题的最优策略。最优策略为（最优策略为（20，0，30，10），最大利润为），最大利润为160万元。万元。872024年年7月月21日日 1. 1.问题的提出问题的提出现假设有现假设有2020名队员准备参加数学建模竞赛，根名队员准备参加数学建模竞赛，根据队员的能力和水平要选出据队员的能力和水平要选出1818名优秀队员分别组成名优秀队员分别组成6 6个队，每个队个队，每个队3 3名队员去参加比赛。选择

44、队员主要名队员去参加比赛。选择队员主要考虑的条件依次为考虑的条件依次为有关学科成绩有关学科成绩、智力水平智力水平、动手动手能力能力、写作能力写作能力、外语水平外语水平、协作能力协作能力和和其它特长其它特长。 假设所有队员接受了同样的培训，外部环境假设所有队员接受了同样的培训，外部环境相同，竞赛中不考虑其他的随机因素，竞赛水平的相同，竞赛中不考虑其他的随机因素，竞赛水平的发挥只取决于表中所给的各项条件，并且，参赛队发挥只取决于表中所给的各项条件，并且，参赛队员都能正常发挥自己的水平。员都能正常发挥自己的水平。882024年年7月月21日日 现在的问题现在的问题：（1 1）在在2020名队员中选择

45、名队员中选择1818名优秀队员参名优秀队员参加竞赛；加竞赛；（2 2）确定一个最佳的组队使竞赛技术水确定一个最佳的组队使竞赛技术水平最高；平最高；（3 3）给出由给出由1818名队员组成名队员组成6 6个队的组队方个队的组队方案，使整体竞赛技术水平最高；并给出每案，使整体竞赛技术水平最高；并给出每个队的竞赛技术水平。个队的竞赛技术水平。 1. 1.问题的提出问题的提出892024年年7月月21日日 (1)(1)假设问题中提供队员的基本条件充分地反映假设问题中提供队员的基本条件充分地反映了每个队的真实能力和水平；了每个队的真实能力和水平； ( () )假设每个队员的能力和水平在比赛中可以假设每个

46、队员的能力和水平在比赛中可以100100的发挥，不受外界因素和环境的影响；的发挥，不受外界因素和环境的影响； （3 3）同一个队三名队员的单项条件互不影响，）同一个队三名队员的单项条件互不影响，且具有互补性，即一个队的水平为最高者的水平；且具有互补性，即一个队的水平为最高者的水平； （4 4）6 6个队整体技术水平最高是在确定的最佳个队整体技术水平最高是在确定的最佳组队保持不变的条件下整体技术水平最高组队保持不变的条件下整体技术水平最高 2. 2.模型的假设模型的假设902024年年7月月21日日 3. 3.模型的建立与求解模型的建立与求解 问题（问题（1）：）：利用层次分析法得到每个队员的水

47、利用层次分析法得到每个队员的水平指标，按大小排序结果如下表：平指标，按大小排序结果如下表：912024年年7月月21日日 3. 3.模型的建立与求解模型的建立与求解问题问题(2)：确定一个最佳的组队使竞赛技术水平最高确定一个最佳的组队使竞赛技术水平最高.922024年年7月月21日日 3. 3.模型的建立与求解模型的建立与求解932024年年7月月21日日 3. 3.模型的建立与求解模型的建立与求解 3. 3.模型的建立与求解模型的建立与求解问题（问题（3）：）：给出由给出由18名队员组成名队员组成6个队的组队方案个队的组队方案 942024年年7月月21日日 3. 3.模型的建立与求解模型的建立与求解952024年年7月月21日日 3. 3.模型的建立与求解模型的建立与求解962024年年7月月21日日