文档介绍：动态规划、线性规划、和非线性规划都是属于数学规划的范围。所研究的对象本质上都是一个最优化问题。但是线性规划和非线性规划所研究的问题,通常与时间无关,所以,又称它们为静态规划。而动态规划所研究的的问题与时间有关系,它是研究具有多阶段决策过程的一种方法,它将问题的整体按时间或空间的特征分成若干个前后衔接的时空阶段,把多阶段决策问题表示为前后有关联的一系列单阶段决策问题,然后逐个加以解决,从而得到整个问题的最优决策。对于某些静态问题,我们也可以人为的引入时间因素,用动态规划的方法解决。
应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,必须对具体问题进行具体分析。
[实例]最短路线问题
如图2-1,给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),试求一条由A到G的铺管线路,使总距离(或总费用最小)
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
一、动态规划的基本概念
1、阶段
把所给问题的过程恰当地划分为若干个相互联系的阶段,以便按照
一定的次序去求解。描述阶段的变量称为阶段变量,常用
表示。阶段
的划分,一般是根据时间和空间的自然特征来划分,在上述最短路问题
中可分为6个阶段
2、状态
状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问
体过程的状况,在上例中,状态就是某阶段的出发位置,它既是该阶段
某支路的起点,又是前一阶段某之路的终点。通常一个阶段由若干个状
态,第一个阶段有一个状态就是
第二个阶段有两个状态,即点集合
一般第
个阶段的状态就是第
个阶段所有始点的集合。
描述状态的变量称为状态变量,可用一个数、一组数或一个向量来描述
常用
表示第
阶段的状态变量,在上例中,第三阶段有四个状态,即
状态变量
可取四个值,即
点集合
就称为第三阶段的可达状态集合,即
这里所说的状态应具有无后效性,如果某阶段的状态给定后,则在
这阶段以后过程的发展不受这阶段以前状态的影响。这个性质称为无
后效性。
所以,在构造决策过程的动态规划模型时,不能仅由描述过程的具体特征这点来规定状态变量,而要充分注意到是否满足无后效性的要求。
3、决策
决策表示当过程处于某个阶段的某个状态时,可以做出不同的
决定或选择,从而确定下一个阶段的状态,这种决定称为决策。
描述决策的变量称为决策变量,可用一个数或一组数或一个向量来描
述。常用
表示第
阶段当状态处于
时的决策变量,它是状态
变量的函数,在实际问题中决策变量的取值往往限制在某一范围之内,
此范围称为允许决策集合。常用
表示第
阶段从状态
出发的
允许决策集合,显然
在上述例子,在第二阶段中,若从状态
出发,就可做出三种不同
决策其允许决策集合
若选取的点为
则
是
状态
在决策
作用下的一个新的状态,记作
4、策略
策略是一个按顺序排列的决策组成的集合。由过程的第
阶段开始到
终止状态为止的过程,称为问题的后部子过程(或称为
子过程)。
由每段的决策按照顺序排列组成的决策函数序列
子过程策略,简称子策略。记为
称为
即
当
时,此决策函数序列称为全过程的一个策略,简称策略,记为
即
在实际问题中,可供选择的策略有一定的范围,此范围称为允许策略集
合,用
表示,从允许策略集合中找出达到最优的策略称为最优策略
5、状态转移方程
状态转移方程是确定过程由一个状态到另一个状态的演变过程,若给定第
阶段状态
的值,如果该段的决策变量
也确定,则第
的
状态
也就完全确定,即
的值随
的值变化而变化。这种
和
确定的对应关系记为
它描述了两个阶段状态转移的规律,称为状态转移方程。
称为状态转移函数。上例中的状态转移方程为
6、指标函数和最优函数
用来衡量所实现过程优虐的一种指标函数,成为指标函数,它是定义
在全过程和所有的后部子过程上确定的数量函数,常用
表示,即
对于动态规划模型的指标函数,应具有可分离性,并满足递推关系
在实际问题中指标函数都满足这个性质。
常见的指标函数有下列两种形式
(1)过程和任一子过程的指标是它所包含的各阶段指标的和,即
表示第
其中
阶段的阶段指标。此时上式可表示为
(2)过程和任一子过程的指标是它所包含的各阶段指标的乘积,即
也可以写成
指标函数的最优值,称为最优值函数,记作
它表示从第
阶段
的状态
开始到第
阶段的终止状态的过程,采取最优策略所得到的