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

数学建模方法及其应用 韩中庚编著 数学建模教学片 第十三章动态规划方法 设计制作 主要内容 第十三章动态规划方法 3 2020年1月21日 动态规划的基本问题 动态规划的基本概念与条件 动态规划的基本方程 动态规划的求解方法 动态规划的应用案例分析 一 动态规划的一般问题 4 2020年1月21日 动态规划是一种用于处理多阶段决策问题的数学方法 主要是先将一个复杂的问题分解成相互联系的若干阶段 每个阶段即为一个小问题 然后逐个解决 当每个阶段的决策确定之后 整个过程的决策也就确定了 阶段一般用时间段表示 即与时间有关 这就是 动态 的含义 把这种处理问题的方法称为动态规划方法 5 2020年1月21日 1 引例 最短路线问题 1 问题的提出 6 2020年1月21日 2 问题的分析 1 引例 最短路线问题 7 2020年1月21日 2 用动态规划的方法分步考虑 1 引例 最短路线问题 8 2020年1月21日 2 用动态规划的方法分步考虑 9 2020年1月21日 2 用动态规划的方法分步考虑 10 2020年1月21日 2 用动态规划的方法分步考虑 11 2020年1月21日 2 用动态规划的方法分步考虑 4 求四个阶段最优选择 12 2020年1月21日 2 用动态规划的方法分步考虑 13 2020年1月21日 2 用动态规划的方法分步考虑 14 2020年1月21日 二 动态规划的基本概念与条件 1 动态规划的基本概念 1 阶段 stage 和阶段变量 阶段是指一个问题需要作出决策的步骤 即把问题的过程分为若干个相互联系的阶段 使能按阶段的次序求解 描述阶段的变量称为阶段变量 常用k表示 15 2020年1月21日 在多阶段决策过程中 每一阶段都具有一些特征 自然状况 或客观条件 这就是状态 用来描述状态的变量称为状态变量 2 状态与状态变量 16 2020年1月21日 3 决策和决策变量 17 2020年1月21日 策略是一个按顺序排列的决策组成的集合 4 策略与子策略 18 2020年1月21日 4 策略与子策略 19 2020年1月21日 状态函数是在确定多阶段决策过程中 由一个状态到另个状态的演变过程 5 状态转移函数 20 2020年1月21日 在多阶段决策过程中 用来衡量所实现过程优劣的一种数量指标 称为指标函数 6 指标函数 回收函数 21 2020年1月21日 常见的两种指标函数 22 2020年1月21日 常见的两种指标函数 23 2020年1月21日 7 最优值函数 24 2020年1月21日 2 动态规划的基本条件 二 动态规划的基本概念与条件 无后效性 如果某阶段状态已给定 则以后过程的发展不受以前各阶段状态的影响 也就是说当前状态就是未来过程的初始状态 可知性 规定的各阶段状态变量的值 由直接或间接都是可以知道的 25 2020年1月21日 2 动态规划的基本条件 1 它是过程各阶段状态变量和决策变量的函数 26 2020年1月21日 三 动态规划的基本方程 1 动态规划的逆序解法 27 2020年1月21日 28 2020年1月21日 三 动态规划的基本方程 2 动态规划的顺序解法 29 2020年1月21日 2 动态规划的顺序解法 30 2020年1月21日 四 动态规划的求解方法 1 动态规划的逆序解法 31 2020年1月21日 1 动态规划的逆序解法 32 2020年1月21日 1 动态规划的逆序解法 33 2020年1月21日 四 动态规划的求解方法 2 动态规划的顺序解法 34 2020年1月21日 2 动态规划的顺序解法 35 2020年1月21日 2 动态规划的顺序解法 36 2020年1月21日 1 问题的提出 现假设有20名队员准备参加数学建模竞赛 根据队员的能力和水平要选出18名优秀队员分别组成6个队 每个队3名队员去参加比赛 选择队员主要考虑的条件依次为有关学科成绩 智力水平 动手能力 写作能力 外语水平 协作能力和其它特长 五 案例分析 选拔队员与组队问题 假设所有队员接受了同样的培训 外部环境相同 竞赛中不考虑其他的随机因素 竞赛水平的发挥只取决于表中所给的各项条件 并且 参赛队员都能正常发挥自己的水平 37 2020年1月21日 现在的问题 1 在20名队员中选择18名优秀队员参加竞赛 2 确定一个最佳的组队使竞赛技术水平最高 3 给出由18名队员组成6个队的组队方案 使整体竞赛技术水平最高 并给出每个队的竞赛技术水平 五 案例分析 选拔队员与组队问题 1 问题的提出 38 2020年1月21日 五 案例分析 选拔队员与组队问题 1 假设问题中提供队员的基本条件充分地反映了每个队的真实能力和水平 假设每个队员的能力和水平在比赛中可以100 的发挥 不受外界因素和环境的影响 3 同一个队三名队员的单项条件互不影响 且具有互补性 即一个队的水平为最高者的水平 4 6个队整体技术水平最高是在确定的最佳组队保持不变的条件下整体技术水平最高 2 模型的假设 39 2020年1月21日 五 案例分析 选拔队员与组队问题 3 模型的建立与求解 问题 1 利用层次分析法得到每个队员的水平指标 按大小排序结果如下表 40 2020年1月21日 3 模型的建立与求解 问题 2 确定一个最佳的组队使竞赛技术水平最高 41 2020年1月21日 3 模型的建立与求解 42 2020年1月21日 3