动态规划 (1)

动态规划

运筹学的一个主要分支 解决多阶段决策过程的最优化的一种方法 多阶段决策过程：一类特殊的活动过程， 这类活动可以按时间顺序分解成若干个相 互联系的阶段，每个阶段都有若干个方案 可供选择。 多阶段决策过程的最优化的目标：达到整 个活动过程的总体效果最优

主要用于解决：最优路径问题， 资源分配问题， 排序问题 ,投资问题， 装载问题 生产计划与库存问题， 生产过程的最优控制等

离散确定型 离散随机型 动态规划 连续确定型 连续随机型

例1 设从甘肃要铺一条煤气管道到北京，途中须经 过三个省：陕西、山西、河北，每省设一个中 最 间站。各省建站可供选择的地点及各段距离如 短 下图，现要求选择一条甘肃到北京的铺管线路， 路 10 5 使总距离最短。 5 ○ 2 问 8 9 ○ 8 多阶段决策问题 ○ 4 6 题 8 9 210 1 3 5 8 ○ ○ ○ ○ ○ 1 4 6 9 10 ○ ○ ○ ○ ○

铺设方案1: 路长=21 策略 铺设方案2: 路长=16

10 ○

7 4 3 甘肃 9 ○ 3 北京 6 1 8 ○ 4 7 ○ 河北 山西 陕西

6 6 ○

7

3 ○

1 ○

一个策略

每一个阶段的决策合在一起构成一个铺设方案 每个策略对应一个路长 寻找路长最短的铺设方案 寻找最优策略

例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个单位 产品的费用如下： 0 c j 3 j j 0 j 1,2, 6月 1 23

32

44

需求 2

每月库存i个单位产品的费用E(i)=0.5i(千元),该 厂最大库存容量为3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试 制定四个月的生产计划，在满足用户需求条件下， 使总费用最小。 四个阶段的 每个月视为一个阶段， 决策问题 每个阶段都须决定生产几个、库存几个 上一个阶段的决策直接影响下一个阶段的决策

例4(投资决策问题)某公司现有资金Q万 元，在今后5年内决定给A、B、C、D四 个项目投资，这些项目的投资期限、回 报率均不相同，问应如何确定这些项目 每年的投资额，使到第5年末拥有资金的 本利总额最大。5个阶段的决 策问题

例5(设备更新问题)某企业要决定一台设 备未来8年的更新

计划，已预测了第j年 的购买设备的价格为Kj, Gj为设备经过j 年后的残值， Cj为设备连续使用j-1年后 在第j年的维修费(j=1,2, …,8),问应在哪 一年更新设备可使总费用最小每一年视为一个阶段， 每个阶段都须做决策： 继续使用旧设备还是购买新设备？ 8个阶段的决 策问题

上一个阶段的决策直接影响下一个阶段的决策

二、基本概念1、阶段 2、状态 3、决策 4、策略 5、状态转移方程

6、指标函数

1、阶段： 通常用k表示阶段 阶段是指对整个过程的自然划分 划分阶段的规则： 根据时间顺序或空间特征来划分阶段 目的：以便按次序来解优化问题 如最短路问题： 问题分成4个阶段： k=1,2,3,455 ○

k=1:第一阶段，甘肃 线路： 1 2,1 3,1 4 k=3:第三阶段：山西 河北 线路： 5 8,5 9, 6 8,6 9, 7 8, 7 9

10 2 ○ 8 9 8 ○ 4 6 8 9 2 ○ 6 1 7 ○ 3 6 ○ 10 ○4 7 3 甘肃 9 3 北京 ○ 6 1 8 ○ 4 7 ○ 河北 陕西 山西 陕西

各阶段开始时所处的自然状况 2、状态： 状态变量 sk 第k阶段的状态变量

变量

描述各阶段状态的变量 ，简称为状态

Sk ={sk}

第k阶段的状态集合 5

如最短路问题： 第一阶段的状态： 1 ○

第二阶段的状态： ○ 2 ○ 3 ○ 4 s4 第4阶段的状态变量 s4=8 S3 ={s3} ={5,6,7} S5 ={10}

10 2 9 ○ 8 4 6 8 ○ 9 2 ○ 6 1 7 ○ ○ 3 6 10 ○ 4 7 3 甘肃 9 3 北京 ○ 6 1 4 8 7 ○ ○ 河北 山西 陕西8 第4阶段的状态○

5 ○ 8

注：n个阶段的决策过程有个n+1状态变量 sn+1,表示sn演变的结果

例3(生产与存储问题)某工厂生产并销售某种 产品。已知今四个月市场需求预测如下表，又 每月生产j个单位产品的费用为 0 c j 3 j j 0 j 1,2, 6i月 1 2 3 3 2 4 4 g(i)需求 2

每月库存i个单位产品的费用E(i)=0.5i(千元), 该厂最大库存容量为3个单位，每月最大生产 能力为6个单位，计划开始和计划期末库存量 都是零，试制定四个月的生产计划，在满足用 户需求条件下，使总费用最小。 阶段k=1,2,3,4 第k阶段的状态变量sk =第k个月月初的库存量 S1={0}, S2={0,1,2,3}, S3={0,1,2,3},S4={0,1,2,3}

动态规划中的状态应具有以下性质：1、能描述过程的特征 2、具有无后效性 无后效性： 当某阶段的状态给定时，这个阶段以后过 程的演变与该阶段以前各阶段的状态无关 3、状态是直接或间接可以观测的8 48 ○ 9 ○

5

10 ○

北京

河北

8 96 6 ○ 6 17 ○

5 ○

山西

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

当一个阶段的状态确定后，可以作出各种选 3、决策：允许决 择从而演变到下一阶段的某个状态，这种选 策集合 择手段称为决策 决策变 …… 此处隐藏：2550字，全部文档内容请下载后查看。喜欢就下载吧 ……