文档介绍：运筹学第五章动态规划(山西财经大学)
运筹学
第五章动态规划
动态规划是解决多阶段决策过程最优先的一种方法。1951年美国数学家(R3>.Bellman)等人,根据一类多阶段决策问题的特性,提出了解决这种问题的“最优性原理”,并研究了许多实际问题,从而创建了最优化问题的一种新方法。
多阶段决策过程,是指这样一类活动的过程:由于它的特殊性可将它划分为若干个相互联系的过程,在它的每个阶段都需要作出决策,并且一个阶段的决策确定以后,常影响下一个阶段的决策,从而影响整个决策的效果。多阶段决策问题就是要在允许的各阶段的决策范围内,选择一个最优决策,使整个系统在预定的标准下达到最佳的效果。
多阶段决策过程特点
§1 动态规划的基本原理和模型
若有一辆汽车由S城出发,经若干个城市到达F城,如下图:
最短路问题图
1
F
S
P1
P2
P3
Q1
Q2
Q3
4
5
7
2
6
1
6
4
2
3
4
P1,P2,P3,Q1,Q2,Q3是一些可以通过的城镇,图中两点间标注的数字可表示两城镇间的距离,也可以是综合远近、路面好坏,是否拥挤等情况在两点间标出行驶这段路程所用的时间。
由S城出发可经多种途径到达F城,所谓最短路问题,就是在多种途径中决定一种途径,使由S到F所走的路程最短,如果两点间的数字代表行驶时间,则问题就是决定一种途径,使由S城到F城所用的时间最短。
求解最短路问题的一种方法叫决策树法,即把所有可能的途径所花的时间都算出来,从中取时间最短的。
4
F(15)
Q3
F(17)
S
P1
Q1
P2
Q2
P3
Q3
F(14)
Q2
P3
Q3
P2
P3
P3
Q3
F(16)
F(15)
F(14)
F(13)
F(18)
4
5
6
6
4
7
1
1
2
2
1
1
2
2
3
4
3
4
3
4
3
从上图可以看出最优策略是途径S-Q1-P2-Q3-F,总共只用了13个小时,但决策树法的运算量很大,尤其是中间节点(如P1,Q2等)较多时,这种方法是不可取的。
下面介绍一种较简捷的方法。也就是把上述问题看成一个含有4个阶段的多阶段决策问题,其详细解法如下表:
F
7
2
4
5
6
1
6
4
1
2
3
4
P3
Q3
P2
Q2
P1
Q1
S
[4,F]
[3,F]
[4,Q3]
[5,Q3]
〔10,P2]
[8,P2]
[13,Q1]
例二机器设备问题设有某种机器设备,,若以数量uk用于A,余下的(xK-uk)用于B,则该年的预期收入为g(uk)+h(xk-uk),其中g(uk),h(xk-uk)为已知函数,且g(0)=h(0)=,该机器用于工作A时,一年后的完好率为a,若用于B项工作时一年后的完好率为b,其中0<a<1,0<b<1,假定机器最初的完好的数量为x1,问在连续N年内每年应如何分配用于A和B两项工作的机器数,使N年的总收益为最大?
例三将一个数c(c>0)分成n个部分c1,c2,…,cn,问如何分法使其乘积为最大.
如果最短路线在第k站通过点Pk,则这一路线在由Pk出发到达终点的那部分路线,对于从点Pk到达终点的所有可能选择的不同路线来说,必定也是距离最短的。
“最优决策的一部分也是最优决策”,在动态规划中被称为“最优性原理”,它是动态规划实际运用时的基础。
建立动态规划模型时,一般有下列术语和步骤:
阶段
用动态规划求解多阶段决策系统问题时,要根据具体情况,将系统适当的分成若干个阶段,以便分阶段求解,描述阶段的变量称为阶段变量(用N表示)。
状态
状态表示系统在某一阶段所处的位置或状态,过程的状态可用状态变量(用xk表示)来描述,某个阶段所有可能状态的全体可用状态集合来描述。
决策
某一阶段的状态确定以后,从该状态演变到下一阶段某一状态所作的选择称为决策。描述决策的变量(用uk表示)称为决策变量。
策略: 由每一阶段的决策组成的决策函数序列成为全过程策略或简称策略(用p1,N(x1)表示);由第k阶段到最后阶段的决策组成的决策函数序列称为k子(过程)策略(用pk,N(xk)表示)。
状态转移: 某一阶段的状态变量及决策变量取定后,下一阶段的状态就随之而定,用xk+1=Tk(xk,uk)表示。
阶段效益: 系统某阶段的状态一经确定,执行某一决策所得的效益称为阶段效益(记为dk