文档介绍：1951年,美国数学家贝尔曼(RichardBellman)提出,它是解决多阶段决策问题的优化方法,也是考察问题的一种途径。
不是一种算法(如LP单纯形法)。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进1951年,美国数学家贝尔曼(RichardBellman)提出,它是解决多阶段决策问题的优化方法,也是考察问题的一种途径。
不是一种算法(如LP单纯形法)。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。
动态规划 
Dynamicprogrammingproblem
多阶段决策过程
在生产和科学实验中,有一类活动的过程,由于它的特殊性,可将过程分为若干个互相联系的阶段,在它的每一个阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成了一个决策序列,这个决策序列是在不断变化的状态产生的,即“动态”中产生的,我们把处理“动态”中产生的决策序列的方法称为动态规划。(DynamicProgramming).
把一个问题可看作是一个前后关联具有链状结构的多阶段过程如下图所示就称为多阶段决策过程,也称序贯决策过程。
第一节    多阶段决策过程最优化举例
一引例:最短路径问题
【特点】存在一个始点,一个终点,始点与终点间存在着若
干个中间点。
用逆序解法逐阶段分析,即从最后一个阶段开始,从后向前决策
确定每个阶段各个始点A到终点E的最短距离,从后向前推,当分析完第一阶段后,便可得到从起点A到终点E的最短路径。
A
B1
B2
B3
B4
C1
C2
C3
D1
D2
E
4
3
3
2
2
1
6
4
7
2
4
8
3
7
5
1
8
6
7
5
1
6
10
6
I
II
Ⅲ
Ⅳ
假如上图是一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),我们的问题是要将货物从A地运往E地,中间通过B、C、D三个区域,在区域内有多条路径可走,现求一条由A到E的线路,使总距离最短
(或总费用最小)。
I
II
Ⅲ
Ⅳ
A
B1
B2
B3
B4
C1
C2
C3
D1
D2
E
4
3
3
2
2
1
6
4
7
2
4
8
3
7
5
1
8
6
7
5
1
6
10
6
10
6
12
11
11
12
13
12
14
14
【具体作法】先研究最后一个阶段,找到每个阶段起点到
最后一个终点的最短距离,将其标在该点上方,同时划去多余路线,最后在未画“”的路线中确定最短路径。
图中各点上方框的数,。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
3
4
6
7
6
9
9
11
12
第二节动态规划的基本概念
一、动态规划的基本要素
1、阶段与阶段变量。阶段的划分,一般根据时序和空间的自然特征来划分,但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量,常用自然数k表示。如引例可划分为4个阶段求解,k=1,2,3,4。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
3
4
6
7
6
9
9
11
12
一、动态规划的基本要素
2、状态与状态变量。状态就是阶段的起始位置。它既是该阶段某支路的起点,又是前一阶段某支路的终点。
状态变量:描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量(多维情形)来描述,常用Sk表示第k阶段的状态变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集合。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
3
4
6
7
6
9
9
11
12
一、动态规划的基本要素
3、决策与决策变量。决策是在某阶段内的选择。决策变量常用Xk(Sk)表示第k阶段处于状态Sk时的决策变量。
A
B1
B2
B3
C1
C2
C