文档介绍：第五节动态规划
动态规划是运筹学的一个分支,()等人,根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系单阶段问题,然后逐个加以解决。与此同时,他提出了解决这类问题的“最优性原理”,研究了许多实际问题,从而创建了解决最优化问题的一种新的方法——“动态规划”于1957年出版,该书是动态规划的第一本著作.
动态规划模型的分类,根据多阶段决策过程的时间参量是离散的还是连续的变量;,、离散随机性、连续确定性、,介绍动态规划的基本概念、理论和方法,并通过几个典型的问题来说明它的应用,这些都是整个动态规划的基本内容.
离散
决策过程
连续
决策过程
根据多阶段决策过程的
时间参量
根据决策过程的
演变
确定性
决策过程
随机性
决策过程
离散确定性
决策过程
离散确定性
决策过程
连续确定性
决策过程
连续随机性
决策过程
引例——有一批军用物资需要从 A 地调运到E地,如下图所示,请求出一条从 A 到 E 的一条线路,使总的运输距离最短。图中线条上的数字为距离。
A
E
B2
C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
10
12
9
4
5
8
9
7
7
3
4
11
1 多阶段决策过程及实例
B 地
C 地
D 地
E 地
A 地
在生产和科学实验中,有一类活动的过程,由于它的特殊性,可将过程分为若干个互相联系的阶段,在它的每一个阶段都需要作出决策,,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响到以后的决策。
A
E
B2
C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
10
12
9
4
5
8
9
7
7
3
4
11
如果一个问题的过程可以化分为若干个互相联系的阶段,而且每个阶段都需要作出决策,而且当每个阶段的决策都确定之后,整个问题也就确定了,那么,这个问题就叫做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法。
如上图所示的线路网络,求 A 到 E ,来说明动态规划方法的基本思想,并阐述它的基本概念。.
A
E
B2
C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
10
12
9
4
5
8
9
7
7
3
4
11
如上图可知,,从B到C为第二阶段…从D到E为第四阶段
在第一阶段,A为起点,终点有B1,B2,B3三个,因而这时走的路线有三个选择, 分别是走B1,B2,B3。
如果选择走B2的决策,,又是第二阶段路线的始点。
在第二阶段,再从B2点出发,对应于B2点就有一个可供选择的终点集合{C1,C2,C3};
如果选择由B2走至C2为第二阶段的决策,则C2 就是第二阶段的终点,同时又是第三阶段的始点.
同理递推下去,可看到:各个阶段的决策不同,,当某一阶段的始点给定时,它直接影响着后面各阶段的行进路线和整个路线的长短,:在各个阶段选取一个恰当的决策,使由这些决策组成的一个决策序列所决定的一条路线,其总路程最短。
A
E
B2
C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
10
12
9
4
5
8
9
7
7
3
4
11
如何解决这个问题呢?
,然后互相比较找出最短者,,由A到E一共有3 X 3 X 2 X 1=18条不同的路线,比较这18条不同的路线的距离值,才找出最短路线。
显然,,各段的不同选择也很多时,这种解法的计算将变得极其繁杂,甚至在电子计算机上计算都是不现实的.
A