运筹学 第05章 动态规划.ppt

运筹学 第五章动态规划 本章重点 动态规划的四大要素 一个方程动态规划问题的建模与求解 动态规划概念 1 前面介绍的线性规划研究的是一次性的决策线性规划决策过程可以总结为在给定资源和环境的情况下 决定变量的取值 使某个目标达到最大或最小值这个决策过程可以表示如下图 其中u表示决策变量x1表示决策所依赖的资源和环境Z表示目标函数x2表示决策后的资源和环境状况 动态规划概念 2 例如 前面讲过的生产计划问题就是一次决策某工厂用三种原料生产三种产品 已知的条件如下表所示 试制订总利润最大的日生产计划 动态规划概念 3 在这个模型中模型中的A b和C就是x1模型中的X就是u模型中的f X CX就是ZA C和剩余的原料为x2 设每天生产三种产品的件数分别为x1 x2 x3其线性规划模型为 动态规划概念 4 如果上例中的生产计划不是只在一天里进行 而是连续一周 每天投入一定量的原料 剩余的原料后面可以继续使用 每天只允许生产一种产品并获得相应的利润 问怎样决策才能使一周的总利润最大 解决这样的问题需要将决策过程分为多个阶段 本问题需要分为如下的7个阶段 动态规划概念 5 uk k 1 2 3 4 5 6 7 表示第k天生产三种产品中的哪一种以及生产多少x1 技术环境A 市场环境C和原料bxk 1 技术环境A 市场环境C和原料b 第k天剩余的原料 k 1 2 3 4 5 6 7 rk 第k天生产产品获得的利润总利润 r1 r2 r3 r4 r5 r6 r7 动态规划就是解决这种多阶段决策过程的方法 多阶段决策过程 1 其中包含n个决策子问题 每个子问题称为一个阶段 用变量k表示 称为阶段变量xk描述k阶段初系统的状况 称为状态变量每个阶段有一个输入状态和一个输出状态一般把输入状态称为该阶段的阶段状态 一般的多阶段决策过程表示如下 多阶段决策过程 2 uk代表k阶段对第k子问题进行的决策 称uk为k阶段的决策变量 uk的一组确定的取值称为一个决策rk表示k阶段从状态xk出发做决策uk之后产生的后果 称为k阶段的阶段效应若在上述的多阶段决策过程中 系统k阶段以后的决策只与k阶段系统的状态xk有关 而与系统以前的决策无关 则称该多阶段决策过程具有无后效性注 动态规划的建模和求解都是针对具有无后效性的多阶段决策过程 多阶段决策过程 3 在具有无后效性的多阶段决策过程中 uk由xk决定 rk和xk 1由xk和uk决定 因此决策可以写为uk xk 阶段效应可以写为rk xk uk 状态xk 1 Tk xk uk 称为状态转移方程 其中Tk是已知函数多阶段决策过程中 从第k阶段到最终阶段的过程称为k 后部子过程 简称k 子过程 动态规划模型 动态规划模型如下 表示求和或加权求和 opt表示求最优 最大值或最小值 Xk表示k阶段状态可能的取值范围 称为状态可能集合Uk表示k阶段决策可能的取值范围 称为决策允许集合 动态规划建模 确定阶段根据实际情况进行阶段划分明确状态变量xk和状态可能集合Xk确定决策变量uk xk 和决策允许集合Uk确定状态转移方程xk 1 Tk xk uk 明确阶段效应rk xk uk 和目标R 示例 5 1 1 前面讲过的生产计划问题某工厂用三种原料生产三种产品 已知的条件如下表所示 如连续生产一周 每天投入一定量的原料 剩余的原料后面可以继续使用 每天只允许生产一种产品并获得相应的利润 试制订总利润最大的周生产计划 只建模 不求解 示例 5 1 2 示例 5 1 3 动态规划解的概念 1 最优目标值在多阶段决策过程中 从起始状态x1开始 进行一系列的决策 使得目标R达到最优 我们把这种目标的值称为最优目标值 记为R 最优策略把使目标达到最优的决策序列称为最优策略 记为 u1 u2 un 最优路线在采用最优策略时 系统从x1开始所经过的状态序列称为最优路线 记为 x1 x2 xn 1 动态规划解的概念 2 求解动态规划问题就是要找到最优策略 最优路线和最优目标值 动态规划最优性原理 1 一个多阶段决策过程的最优策略具有这样的性质无论其初始状态及其初始决策如何 对于前面决策所形成的某一状态而言 下余的决策序列必定构成最优策略最优性原理的含义是最优策略的任何一个k 后部子策略 uk uk 1 un 是以xk 为初始状态的k 后部子过程的最优策略 动态规划最优性原理 2 如上图A到B之间的蓝线是由状态A到状态B的最优策略在线上任取一点M M到B之间的蓝线就是由状态M到状态B的最优策略 贝尔曼函数 1 在k阶段从初始状态xk出发 执行最优决策序列 到达过程终点时 整个k 后部子过程中的目标函数取值 称为条件最优目标函数 也称为贝尔曼函数 记为fk xk 则 为了将多阶段决策过程的任一阶段状态xk的最优策略和最终的最优策略相区别 称前者为条件最优策略 不一定等于最优路线中的k阶段状态 系统从xk出发 在k 后部子过程中的最优策略 贝尔曼函数 2 构成条件最优策略的决策称为条件最优决策将k阶段状态xk的条件最优决策表示为uk xk 简记为uk 相应的条件最优策略表示为 uk uk 1 un 执行条件最优策略时的阶段状态序列称为条件最优路线 表示为 xk xk 1 xn xn 1 贝尔曼函数 3 动态规划方法的原理就是建立起fk xk 与fk 1 xk 1 之间的递推关系 然后逐步求出所有的fk xk 贝尔曼方程 对于无后效性的多阶段决策过程 根据最优性原理和贝尔曼函数定义 可得 动态规划问题求解步骤 1 通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 k n时 不存在n 1阶段 必须就阶段n的所有可能状态计算和 动态规划问题求解步骤 2 k n 1时 根据 就阶段n 1的所有可能状态计算和 余者类推 直到阶段1 动态规划问题求解步骤 3 通过状态转移方程顺序求出最优决策序列和最优路线阶段1的状态x1唯一确定时 x1 x1 可得唯一确定的u1 x1 和f1 x1 则R f1 x1 u1 x1 u1 x1 当阶段1的状态x1不唯一时 由求得 求出 余者类推 直至阶段n 求出 和 动态规划的四大要素 一个方程 在动态规划的建模和求解过程中 有五个方面起着极其重要的作用四大要素 模型里的 状态变量及其可能集合决策变量及其可能集合状态转移方程xk 1 Tk xk uk 阶段效应rk xk uk 贝尔曼方程 动态规划应用举例 1 最短路线问题 从某地出发 途径若干个中间点最后到达目的地 试求距离最短或费用最省的路线用动态规划求解该问题分为三种情况考虑定步数问题不定步数问题 有限步 无循环 不定步数问题 无限步 有循环 示例 5 2 1 路线图如下所示 箭头表示通行方向 线上数字表示道路长度 试求s到t的最短路线 示例 5 2 2 该问题是一个定步数问题 分为3个阶段阶段1 决定由s到a b还是c阶段2 决定是到d e或是f阶段3 到t状态变量xk设为k阶段初始所在地x1 s x2 a b c x3 d e f x4 t k阶段决策uk是决定下一步走到哪里 有u1 a b c u2 a d f u2 b d e u2 c d e f u3 t 示例 5 2 3 状态转移方程xk 1 uk阶段效应rk xk uk 取为从xk走到uk的路线长度 如r1 s a 9贝尔曼函数fk xk 定义为从xk走到t的最短路线贝尔曼方程 示例 5 2 4 通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 f3 计算表 0 0 0 t t t 5 7 4 5 7 4 示例 5 2 5 f2 计算表 5 5 5 7 7 4 4 7 4 5 6 4 5 6 8 10 9 f d d 示例 5 2 6 f1 计算表 8 10 9 9 8 7 16 c 示例 5 2 7 通过状态转移方程顺序求出最优决策序列和最优路线R f1 s 16 x1 su1 x1 u1 s c x2 cu2 x2 u2 c d x3 du3 x3 u3 d t x4 t 示例 5 2 8 f4 u3 f3 u2 f2 u1 f1 End 0 t 5 t 7 t 4 f 8 d 10 d 9 c 16 示例 5 3 1 路线图如下所示 箭头表示通行方向 线上数字表示道路长度 试求s到t的最短路线 示例 5 3 2 该问题是一个无循环的不定步数问题 从s到t的路线最少可以经过3步 最多可以经过5步这样的问题 可以划分为5个 或3个 阶段来处理 其中允许某个阶段原地不动阶段1 决定由s到a或是b阶段2 决定是到a c或是d阶段3 决定是到c d或是t阶段4 决定是到d或是t阶段5 到t 示例 5 3 3 状态变量xk设为k阶段初始所在地x1 s x2 a b x3 a c d x4 c d t x5 d t x6 t k阶段决策uk是决定下一步走到哪里 有u1 a b u2 a c d u2 b a c d u3 a c d u3 c d t u3 d t u4 c d t u4 d t u4 t t u5 d t u5 t t u6 t 示例 5 3 4 状态转移方程xk 1 uk阶段效应rk xk uk 取为从xk走到uk的路线长度 如r1 s a 9贝尔曼函数fk xk 定义为从xk走到t的最短路线贝尔曼方程 示例 5 3 5 通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 f5 计算表 0 0 t t 4 0 4 0 示例 5 3 6 f4 计算表 4 4 0 0 3 0 4 0 2 4 0 t d t t 0 2 示例 5 3 7 f3 计算表 2 2 4 4 4 0 0 6 2 0 3 5 0 4 8 2 4 c c t d t 示例 5 3 8 f2 计算表 8 8 2 4 0 5 4 2 8 4 a c c 2 4 6 4 示例 5 3 9 f1 计算表 4 4 9 8 12 b 示例 5 3 10 通过状态转移方程顺序求出最优决策序列和最优路线R f1 s 12 x1 su1 x1 u1 s b x2 bu2 x2 u2 b c x3 cu3 x3 u3 c c t x4 c tu4 x4 u4 c t t x5 tu5 x5 u5 t t x6 t 示例 5 3 11 End 0 t 4 t 2 c 8 c 4 b 12 示例 5 4 1 路线图如下所示 箭头表示通行方向 线上数字表示道路长度 试求s到t的最短路线 示例 5 4 2 该问题是一个有循环的不定步数问题 循环一圈的路线长度为8若有一条从起点到终点经过循环上顶点或边但无循环的路线只要该循环的路线长度为非负值 只走该路线必定比走该路线且循环几圈的路线总长度要小或等若该循环的路线长度为负值 只要走一圈循环其路线总长度就减少一些 这种情况下无最短路线不算循环 从s到t的路线最少可以经过3步 最多可以经过5步 示例 5 4 3 这样的问题 可以划分为3个阶段来处理 其中允许第2个阶段走2或3条边阶段1 决定由s到a或是b阶段2 决定由a或b经过某条路线到c或d阶段3 由c或d到t状态变量xk设为k阶段初始所在地x1 s x2 a b x3 c d x4 t 示例 5 4 4 k阶段决策uk是决定下面要走的路线以及下一步走到哪里 有u1 a b u2 a c d cd cbd u2 b d ad ac acd u3 t 示例 5 4 5 状态转移方程xk 1 k阶段的目的地阶段效应rk xk uk 取为从uk中所走路线的长度 如r2 b ac 7贝尔曼函数fk xk 定义为从xk走到t的最短路线贝尔曼方程 示例 5 4 6 通过贝尔曼方程逆序求出条件最优目标函数值集合和条件最优决策集合 f3 计算表 0 0 t t 9 5 9 5 示例 5 4 7 f2 计算表 9 9 5 5 3 6 7 4 11 9 cd d 示例 5 4 8 f1 计算表 11 9 5 8 16 a 示例 5 4 9 通过状态转移方程顺序求出最优决策序列和最优路线R f1 s 16 x1 su1 x1 u1 s a x2 au2 x2 u2 a cd x3 du3 x3 u3 d t x4 t 示例 5 4 10 End 0 t 5 d 8 d 9 cd 11 a 16 动态规划应用举例 2 资源分配问题 设有某种资源 总量为M 可以投入n种生产活动 已知用于生产活动k的资源为uk时的收益是gk uk 问应如何分配资源才能使n种生产活动的总收益最大 该问题用分为两种情况uk连续变化 gk uk 是线性函数时 该问题是线性规划问题gk uk 不是线性函数时 该问题是非线性规划问题 可以利用动态规划方法求解 示例 5 5 1 某公司拟将50万元资金投放下属的A B C三个部门 各部门在获得资金后的收益如下表所示 试求总收益最大的投资分配方案 示例 5 5 2 该问题可以作为三阶段决策过程 对A B C三个部门的资金分配形成3个阶段决策变量uk设为给部门k分配的资金量 状态变量xk设为给部门k分配资金之前的资金拥有量 则x1 5 xk 1 xk uk xk 0 uk 0 k 1 2 3用gk uk 表示给部门k分配资金uk时从部门k获得的收益 示例 5 5 3 f3 计算表 0 0 0 0 0 0 0 0 0 10 10 20 20 30 30 1 3 2 40 40 4 50 50 5 示例 5 5 4 f2 计算表 0 10 0 0 10 20 0 10 20 30 0 10 20 30 40 0 10 20 30