4.1动态规划的基本概念和方法.pptVIP

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