文档介绍：动态规划
实际生产、经营活动中,有一类活动的过程,可以划分为若干个相互联系的阶段,在它的每一个阶段都需作出决策,并且一个阶段的决策确定后,常影响下一阶段的决策甚至整个决策问题的效果。现在,我们就是要找出每一个阶段的决策,从而使整个决策过程达到最好的活动效果。由各个阶段构成的决策序列称为策略。
动态规划(Dynamic Programming)是运筹学的另一个重要分支,是解决多阶段决策过程最优化的一种数量化方法。
§ 动态规划的基本原理和概念
枚举?
步步走近路?
一、多阶段决策问题
例1:如图1,给定一个线路网络,现在要铺设从A点到E点的铁路,中间需经过3个点,第1点可以是B1,B2,B3中的某一个点,第2个点可以是C1,C2,C3中的一个点,等等。各点之间若能铺设铁路,则在图中以连线表示,两点之间连线上的数字表示两点间的距离,要求选择一条A至E的最短路线。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
把从A到E的路线自然地分为4个阶段:从A→B为第l阶段,从B→C为第2阶段,从C→D为第3阶段,从D→E为第4阶段,每个阶段都有几条可供选择的路线,例如从A→B有3条路线:A→B1,A→B2或A→B3,等。总共有14条路线可供选择,这显然是一个多阶段决策问题。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
1、四个相互联系的阶段(怎样联系?)
2、问题是:找出每阶段的决策。
3、目的是:使整个决策过程达到最好的活动效果。
1、阶段
把所给的问题恰当地分为若干个相互联系的阶段,以便按一定的次序去求解。
阶段变量:描述阶段的变量,常用k表示。
阶段的划分常按时间或空间的状态来划分。如例1中,可划分为4个阶段,k=1,2,3,4。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
二、动态规划的基本概念
在例1中,状态就是某阶段的出发位置,它既是当前阶段某支路的起点,又是前一阶段某支路的终点。
状态变量:描述过程状态的变量,常用Sk表示第k阶段的状态变量。
如第三阶段,状态变量S3的取值,有S3={C1,C2,C3}或称第三阶段的可达状态集合。
通常,一个阶段有若干个状态,第一阶段有一个状态就是点A,第二个阶段有三个状态,即点集合{B1,B2,B3}。
2、状态
状态表示每个阶段开始所处的自然状态或客观条件,它描述了研究问题过程的状况,又称不可控因素。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
状态性质:无后效性
如果某阶段状态给定后,则以后过程的发展仅仅取决于这一时刻的状态,不受这阶段以前各段状态的影响。
3、决策
决策表示当过程处于某一阶段的某个状态时,所作出的不同的决定或选择,从而确定下一阶段的状态。
决策变量:描述决策的变量。常用uk(Sk)表示当状态处于Sk时的决策变量,它是状态变量的函数。
允许决策集合:决策变量的取值限制在某一范围内,用Dk(Sk)表示。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
如:从状态B1出发,其允许决策集合为:
D2(B1)={C1,C2},若选取的决策为C2,则u2(B1)=C2,显然有:uk(Sk)∈Dk(SK)。
4、策略
全过程的策略:由每一阶段的决策按顺序排列组成的决策函数序列,记作:P1,n={u1(s1),…un(sn)}。
子过程:由过程的第k阶段开始到终止状态为止的过程,或称k子过程。
子过程策略:由第k阶段开始到终止状态为止的决策序列。记作:Pk,n={uk(sk),…un(sn)}。
最优策略:允许策略