第四章动态规划 (Dynamic Programming 上个世纪50年代 创始时间 美国数学家贝尔曼 创始人 (Richard. Bellman)
美国数学家贝尔曼 （Richard. Bellman) 创始时间 上个世纪50年代 创始人
是运筹学的一个主要分支 ·是解决多阶段决策过程的最优化的一种方法 多阶段决策过程:是一类特殊的活动过程 这类活动可以按时间顺序 分解成若干个相互联系的 阶段,每个阶段都有若干 个方案可供选择。 多阶段决策过程的最优化的目标: 达到整个活动过程的总体效果最优 ·主要用于解决:最优路径问题,资源分配问题, 排序问题投资问题,装载问题 生产计划与库存问题, 生产过程的最优控制等
• 是运筹学的一个主要分支 • 是解决多阶段决策过程的最优化的一种方法 多阶段决策过程： 资源分配问题， 生产计划与库存问题， 排序问题 ,投资问题，装载问题 生产过程的最优控制等 是一类特殊的活动过程， 这类活动可以按时间顺序 分解成若干个相互联系的 阶段，每个阶段都有若干 个方案可供选择。 多阶段决策过程的最优化的目标： 达到整个活动过程的总体效果最优 •主要用于解决：最优路径问题
离散确定型 动态规划离散随机型 连续确定型 连续随机型
动态规划 离散确定型 离散随机型 连续确定型 连续随机型
4.1动态规划的基本概念 和方法 几个典型的例题
4.1 动态规划的基本概念 和方法 一、几个典型的例题
例1没从甘肃要铺一条煤气管道到北京,途中须经 过三个省:陕西、山西、河北,每省设一个中 最间站。各省建站可供选择的地点及各段距离如 短 路/下图,现要求选择一条甘肃到北京的铺管线路, 问使总距离最短。 题 多阶段决策问题 铺设方案l:骆埏策略y北京、6Q ③20 ①→④→⑤⑧ 河北G8价 铺设方案2:路长=16 山西 陕西 ①4→ 个策略 每一个阶段的决策合在一起构成一个铺设方案 每个策略对应一个路长 寻找路长最短的铺设方案 寻找最优策略
例1 设从甘肃要铺一条煤气管道到北京，途中须经 过三个省：陕西、山西、河北，每省设一个中 间站。各省建站可供选择的地点及各段距离如 下图，现要求选择一条甘肃到北京的铺管线路， 使总距离最短。 ○1 ○2 ○3 ○4 ○5 ○6 ○7 ○8 ○9 ○10 北京 河北 山西 陕西 甘肃 8 4 5 8 9 6 1 6 10 9 6 7 7 3 8 4 2 3 最 短 路 问 题 多阶段决策问题 ○1 ○3 ○5 ○8 ○10 路长=21 ○1 ○4 ○6 ○9 ○10 路长=16 每一个阶段的决策合在一起构成一个铺设方案 铺设方案1： 铺设方案2： 一个策略 每个策略对应一个路长 寻找路长最短的铺设方案 寻找最优策略 策略
例2(多阶段资源分配问题) 设有数量为y的某种资源将它分别投入两种 生产方式A和B,已知收益函数分别是g(x)和 h(x),x为资源投入量。设这种资源用于生产后 还可以回收一部分用于生产,A、B的回收率分 别为a和b(0<a≤1,0<b≤1) 问:对总数量为y的资源进行n个阶段的生产, 应如何分配每个阶段投入A、B印資源数量,才 能使总收益最大 n个阶段的决策问题
例2 （多阶段资源分配问题） 设有数量为y的某种资源，将它分别投入两种 生产方式A和B，已知收益函数分别是g(x)和 h(x)，x为资源投入量。设这种资源用于生产后 还可以回收一部分用于生产，A、B的回收率分 别为a和b（ 0≤a≤1，0≤b≤1 ）， 问：对总数量为y的资源进行n个阶段的生产， 应如何分配每个阶段投入A、B的资源数量，才 能使总收益最大？ n个阶段的决策问题
例3(生产与存储问题)某工厂生产并销售某种产品 已知今后四个月市场需求预测及每月生产j个单位 品的费用如下: 0j=0 月123 4 3+ 需求232 4 每月库存个单位产品的费用E()=0.5〔千元),该 厂最大库存容量为3个单位,每月最大生产能力为6 个单位,计划开始和计划期末库存量都是零,试制 定四个月的生产计划在满足用户需求条件下,使 总费用最小。 四个阶段的 每个月视为一个阶段, 决策问题 每个阶段都须决定生产几个、库存几个 上一个阶段的决策直接影响下一个阶段的决策
例3（生产与存储问题）某工厂生产并销售某种产品。 已知今后四个月市场需求预测及每月生产j个单位 产品的费用如下： 每月库存i个单位产品的费用E(i)=0.5i(千元），该 厂最大库存容量为3个单位，每月最大生产能力为6 个单位，计划开始和计划期末库存量都是零，试制 定四个月的生产计划，在满足用户需求条件下，使 总费用最小。 ( ) + = = = 3 1,2, 6 0 0 j j j c j 每个月视为一个阶段， 每个阶段都须决定生产几个、库存几个 上一个阶段的决策直接影响下一个阶段的决策 四个阶段的 决策问题 月 1 2 3 4 需求 2 3 2 4
例4(投资决策问题)某公司现有资金Q万 元,在今后5年内决定给A、B、C、D四 个项目投资,这些项目的投资期限、回 报率均不相同,应如何确定这些项目 每年的投资额,使叫第5年末拥有资金的 本利总额最大。 5个阶段的决 策问题
例4（投资决策问题）某公司现有资金Q万 元，在今后5年内决定给A、B、C、D四 个项目投资，这些项目的投资期限、回 报率均不相同，问应如何确定这些项目 每年的投资额，使到第5年末拥有资金的 本利总额最大。 5个阶段的决 策问题
例5(设备更新问题)某企业要决定一台设 备未来8年的更新计划,已预测了第j年的 购买设备的价格为K,G为设备经过j年 后的残值,C为设合连续使用-1年后在 第j年的维修费=1,2,应在哪一年 更新设备可使总费用最小 每一年视为一个阶段, 8个阶段的决 策问题 每个阶段都须做决策: 继续使用旧设备还是购买新设备? 上一个阶段的决策直接影响下一个阶段的决策
例5（设备更新问题）某企业要决定一台设 备未来8年的更新计划，已预测了第j年的 购买设备的价格为Kj，Gj为设备经过j年 后的残值， Cj为设备连续使用j-1年后在 第j年的维修费(j=1,2, …,8),问应在哪一年 更新设备可使总费用最小 每一年视为一个阶段， 每个阶段都须做决策： 继续使用旧设备还是购买新设备？ 上一个阶段的决策直接影响下一个阶段的决策 8个阶段的决 策问题
基本概念 阶段 2、状态 3、决策 4、策略 5、状态转移方程 6、指标函数
二、基本概念 1、阶段 2、状态 3、决策 4、策略 5、状态转移方程 6、指标函数