第13讲 动态规划方法(new).ppt

《第13讲 动态规划方法(new).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、法。52021年9月20日1.引例：最短路线问题(1)问题的提出62021年9月20日(2)问题的分析1.引例：最短路线问题72021年9月20日2.用动态规划的方法分步考虑1.引例：最短路线问题82021年9月20日2.用动态规划的方法分步考虑92021年9月20日2.用动态规划的方法分步考虑102021年9月20日2.用动态规划的方法分步考虑112021年9月20日2.用动态规划的方法分步考虑（4)求四个阶段最优选择：122021年9月20日2.用动态规划的方法分步考虑132021年9月20日2.用动态规划的方法分步考虑142021年9月20日二.动

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

4、日状态函数是在确定多阶段决策过程中，由一个状态到另个状态的演变过程。(5)状态转移函数202021年9月20日在多阶段决策过程中，用来衡量所实现过程优劣的一种数量指标，称为指标函数。(6)指标函数（回收函数）212021年9月20日常见的两种指标函数222021年9月20日常见的两种指标函数232021年9月20日(7)最优值函数242021年9月20日2.动态规划的基本条件二.动态规划的基本概念与条件*无后效性：如果某阶段状态已给定，则以后过程的发展不受以前各阶段状态的影响，也就是说当前状态就是未来过程的初始状态；**可知性：规定的各阶段状态变量的值，

5、由直接或间接都是可以知道的。252021年9月20日2.动态规划的基本条件1)它是过程各阶段状态变量和决策变量的函数；262021年9月20日三.动态规划的基本方程1.动态规划的逆序解法272021年9月20日1.动态规划的逆序解法282021年9月20日三.动态规划的基本方程2.动态规划的顺序解法292021年9月20日2.动态规划的顺序解法302021年9月20日四.动态规划的求解方法1.动态规划的逆序解法312021年9月20日1.动态规划的逆序解法322021年9月20日1.动态规划的逆序解法332021年9月20日四.动态规划的求解方法2.动态

6、规划的顺序解法342021年9月20日2.动态规划的顺序解法352021年9月20日2.动态规划的顺序解法362021年9月20日1.问题的提出现假设有20名队员准备参加数学建模竞赛，根据队员的能力和水平要选出18名优秀队员分别组成6个队，每个队3名队员去参加比赛。选择队员主要考虑的条件依次为有关学科成绩、智力水平、动手能力、写作能力、外语水平、协作能力和其它特长。五、案例分析:选拔队员与组队问题假设所有队员接受了同样的培训，外部环境相同，竞赛中不考虑其他的随机因素，竞赛水平的发挥只取决于表中所给的各项条件，并且，参赛队员都能正常发挥自己的水平。3720

7、21年9月20日现在的问题：（1）在20名队员中选择18名优秀队员参加竞赛；（2）确定一个最佳的组队使竞赛技术水平最高；（3）给出由18名队员组成6个队的组队方案，使整体竞赛技术水平最高；并给出每个队的竞赛技术水平。五、案例分析:选拔队员与组队问题1.问题的提出382021年9月20日五、案例分析:选拔队员与组队问题(1)假设问题中提供队员的基本条件充分地反映了每个队的真实能力和水平；(２)假设每个队员的能力和水平在比赛中可以100％的发挥，不受外界因素和环境的影响；（3）同一个队三名队员的单项条件互不影响，且具有互补性，即一个队的水平为最高者的水平；（

8、4）6个队整体技术水平最高是在确定的最佳组队保持不变的条件下整体技术水平最高．2