7动态规划.ppt

第七章动态规划
1
本章内容
多阶段决策过程的最优化
动态规划的基本概念和基本原理
动态规划模型的建立与求解
动态规划在经济管理中的应用
美国数学家贝尔曼
(Richard. Bellman)
创始时间
上个世纪50年代
创始人
是运筹学的一个主要分支
是解决多阶段决策过程的最优化的一种方法多阶段决策过程:
资源分配问题
生产计划与库存问题
投资问题
装载问题
排序问题
生产过程的最优控制等
多阶段决策过程的最优化的目标:
达到整个活动过程的总体效果最优
主要用于解决:
最优路径问题
设备更新问题
动态规划
模型分类
离散确定型
离散随机型
连续确定型
连续随机型
多阶段决策问题
(Multi-Stage decision process)
状态
x1
阶段1
T1
决策u1
状态
x2
决策u2
阶段2
T2
状态
x3
...
状态
xk
决策uk
阶段k
Tk
状态
xk+1
...
状态
xn
决策un
阶段n
Tn
状态
xn+1
§1多阶段决策过程的最优化

动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。
§1多阶段决策过程的最优化
一、动态规划的基本概念
使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义:
§2动态规划的基本概念和基本原理
(一) 阶段和阶段变量
为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段。
一个阶段,就是需要作出一个决策的子问题,通常,阶段是按决策进行的时间或空间上先后顺序划分的。
用以描述阶段的变量叫作阶段变量,,图7—1所示的最短路问题就是一个四阶段决策过程。
§2动态规划的基本概念和基本原理
(二)状态、状态变量和可能状态集
。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量,称为状态。
反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上,确定全部允许决策所需要的信息。
按照过程进行的先后,每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段k的初始状态记作sk,终止状态记为sk+1。通常定义阶段的状态即指其初始状态。
§2动态规划的基本概念和基本原理