《动态规划方法》PPT课件

《《动态规划方法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模方法及其应用韩中庚编著数学建模教学片第十三章动态规划方法设计制作：主要内容第十三章动态规划方法32021年10月6日动态规划的基本问题；动态规划的基本概念与条件；动态规划的基本方程；动态规划的求解方法；动态规划的应用案例分析。一、动态规划的一般问题42021年10月6日动态规划（DP)是一种用于处理多阶段决策问题的数学方法。主要是先将一个复杂的问题分解成相互联系的若干阶段，每个阶段即为一个小问题，然后逐个解决，当每个阶段的决策确定之后，整个过程的决策也就确定了。阶段一般用时间段表示(即与时间有关)，这就是“动态”的含义，把这种处理问题的方法称为动态规划方法。52

2、021年10月6日1.引例：最短路线问题(1)问题的提出62021年10月6日(2)问题的分析1.引例：最短路线问题72021年10月6日2.用动态规划的方法分步考虑1.引例：最短路线问题82021年10月6日2.用动态规划的方法分步考虑92021年10月6日2.用动态规划的方法分步考虑102021年10月6日2.用动态规划的方法分步考虑112021年10月6日2.用动态规划的方法分步考虑（4)求四个阶段最优选择：122021年10月6日2.用动态规划的方法分步考虑132021年10月6日2.用动态规划的方法分步考虑14资源分配问题（背包问题）资源分配问题是动态规划的典

3、型问题之一，它的一般提法是：有某种资源，总量为a，用于n个项目，若分配数量ui用于第i个项目，则第i个项目所产生的效果（收益）为gi（ui）。问题是如何分配资源总量a才能获得n个项目所产生的总效果（收益）最优（max）？静态规划问题maxZ=g1（u1）+g2（u2）+…+gn（un）u1+u2+…+un≤（=）aui≥015例1某公司新引进了6台高效率生产设备，该设备可用于生产4种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下：利润表单位：万元设备数量4种产品产品1产品2产品3产品4012345602042607585900254

4、55765707301839617890950284765748085162021年10月6日二.动态规划的基本概念与条件1.动态规划的基本概念(1)阶段（stage）和阶段变量阶段是指一个问题需要作出决策的步骤，即把问题的过程分为若干个相互联系的阶段，使能按阶段的次序求解。描述阶段的变量称为阶段变量,常用k表示。172021年10月6日在多阶段决策过程中，每一阶段都具有一些特征（自然状况，或客观条件），这就是状态，用来描述状态的变量称为状态变量。(2)状态与状态变量182021年10月6日(3)决策和决策变量19(3)决策(decision)表示在某一阶段处于某种状态

5、时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值范围称为决策集，用Dk(sk)表示。T1s1s2v1u1T2s3v2u2Tksksk+1vkukTnsnsn+1vnun……多阶段决策过程如下：202021年10月6日策略是一个按顺序排列的决策组成的集合。(4)策略与子策略212021年10月6日(4)策略与子策略222021年10月6日状态函数是在确定多阶段决策过程中，由一个状态到另个状态的演变过程。(5)状态转移函数23(5)状态转移方程(6)指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数。阶

6、段指标函数是对某一阶段的状态和决策产生的效益值的度量,用vk(sk,uk)表示。若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为:sk+1=Tk(sk,uk)称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。242021年10月6日在多阶段决策过程中，用来衡量所实现过程优劣的一种数量指标，称为指标函数。(6)指标函数（回收函数）252021年10月6日常见的两种指标函数262021年10月6日常见的两种指标函数272021年10月6日(7

7、)最优值函数282021年10月6日2.动态规划的基本条件二.动态规划的基本概念与条件*无后效性：如果某阶段状态已给定，则以后过程的发展不受以前各阶段状态的影响，也就是说当前状态就是未来过程的初始状态；**可知性：规定的各阶段状态变量的值，由直接或间接都是可以知道的。292021年10月6日2.动态规划的基本条件1)它是过程各阶段状态变量和决策变量的函数；301)加法型逆序法:三.动态规划的基本方程31其中：fk(sk)表示第k阶段初始状态为sk时，k后部子过程的最优值函数。状态转移方程：（边界条件）k=1,2,…,n由此得加法型逆序算法