文档介绍：动态规划
一、多阶段决策问题的最优化
二、动态规划基本概念和基本原理
三、动态规划模型的建立与求解
四、动态规划在经济管理中的应用
动态规划(.– Dynamic Program)是解决多阶段决策过程最优化问题的一种方法。
动态的含义:
动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。
一、多阶段决策问题的最优化
动态规划的起源:
1951年,(美),根据多阶段序贯决策问题的特点,提出了著名的“最优性原理”。将多阶段决策问题转变为一系列的互相联系的单阶段决策问题,然后,逐个阶段予以解决,最后再形成总体解决。从而创建了求解优化问题的新方法——动态规划。1957年,他的名著《动态规划》出版。
一、多阶段决策过程的最优化
最优性原理:
作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优子策略。简言之,最优策略的子策略总是最优的。
一、多阶段决策过程的最优化
动态决策问题分类:
1、按数据给出的形式分为:
离散型动态决策问题。
连续型动态决策问题。
2、按决策过程演变的性质分为:
确定型动态决策问题。
随机型动态决策问题。
一、多阶段决策过程的最优化
例1 生产与存贮问题
要求确定一个逐月的生产计划,在满足需求条件下,使一年的生产与存贮费用之和最小?
例2 投资决策问题
某公司现有资金Q万元,在今后5年内考虑给A,B,C,D 4个项目投资?
例3 设备更新问题
现企业要决定一台设备未来8年的更新计划,问应在哪些年更新设备可使总费用最小?
一、多阶段决策过程的最优化
例4 基建投资问题
一家公司有三个工厂,每个厂都需要进行扩建。公司用于扩建的资金总共为7万元。各个厂的投资方案及扩建后预期可获得的利润如表所示(单位:万元)。
现在公司要确定各厂投资多少才能使公司的总利润达到最大?
厂名
方案1
方案2
方案3
方案4
投资数
利润
投资数
利润
投资数
利润
投资数
利润
一厂
0
0
1
5
2
8
5
10
二厂
0
0
1
3
3
9
4
11
三厂
0
0
2
7
3
11
4
13
一、多阶段决策过程的最优化
例5 货船装运问题
有四种货物准备装到一艘货船上。第i(i=,3,4)种货物的每一箱重量是wi(单位:吨),其价值是vi(单位:干元),如表所示。
假定这艘货船的总载重量是10吨,现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大?
货物i
单位重量wi
单位价值vi
1
2
4
2
1
2
3
4
7
4
3
5
一、多阶段决策过程的最优化
例6 最短路程问题
假定从A地到E地要铺设一条管道,其中要经过若干个中间点(如图)。
图中两点之间连线上的数字表示两地间的距离,现在要选择一条铺设管道的路线使总长度最短。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
3
6
7
7
6
9
5
2
3
8
3
5
4
3
6
9
4
3
一、多阶段决策过程的最优化
动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问题是指这样的决策问题:其过程可分为若干个相互联系的阶段,每一阶段都对应着一组可供选择的决策,每一决策的选定即依赖于当前面临的状态,又影响以后总体的效果。当每一阶段的决策选定以后,就构成一个决策序列,称为一个策略,它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。
二、基本概念和基本原理