文档介绍：动态规划
运筹学的一个主要分支
解决多阶段决策过程的最优化的一种方法
多阶段决策过程:一类特殊的活动过程,这类活动可以按时间顺序分解成若干个相互联系的阶段,每个阶段都有若干个方案可供选择。
多阶段决策过程的最优化的目标:达到整个活动过程的总体效果最优
资源分配问题,
生产计划与库存问题,
,投资问题,
装载问题
排序问题
生产过程的最优控制等
主要用于解决:最优路径问题,
动态规划
离散确定型
离散随机型
连续确定型
连续随机型
例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个阶段的决策问题
例3(生产与存储问题)某工厂生产并销售某种产品。已知今后四个月市场需求预测及每月生产j个单位产品的费用如下:
每月库存i个单位产品的费用E(i)=(千元),该厂最大库存容量为3个单位,每月最大生产能力为6个单位,计划开始和计划期末库存量都是零,试制定四个月的生产计划,在满足用户需求条件下,使总费用最小。
每个月视为一个阶段,
每个阶段都须决定生产几个、库存几个
上一个阶段的决策直接影响下一个阶段的决策
四个阶段的决策问题
月
1
2
3
4
需求
2
3
2
4
例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、阶段:
阶段是指对整个过程的自然划分
○
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: