中央财经大学：《运筹学》 第四章（4-1） 动态规划的基本概念和方法

第四章动态规划 (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、指标函数