当前位置:文档之家› 第六章动态规划ppt课件

第六章动态规划ppt课件

表6-2
本阶段始点 (状态)
C1 C2 C3
阶段3 本阶段各终点(决策)
D1 8+10=18 7+10=17 1+10=11
D2 6+6=12 5+6=11 6+6=12
到E的最短距离
12 11 11
本阶段最优终点 (最优决策)
D2 D2 D1
分析得知:如果经过C1,则最短路为C1-D2-E; 如果经过C2,则最短路为C2-D2-E; 如果经过C3,则最短路为C3-D1-E。
到E的最 本阶段最优终 短距离 点(最优决策)
12
C2
最后,可以得到:从A到E的最短路径为A B4 C3 D1 E
精品课件
管理运筹学
6
§1 问题的提出
以上计算过程及结果,可用图2表示,可以看到,以上方法
不仅
得到了从A到E的最短路径,同时,也得到了从图中任一点到E的最
短路径。
4 14
A
3
3
2
12 B1 2
3.决策与决策变量
决策:在某阶段对可供选择状态的决定(或选择)。
s 决策变量:描述决策的变量。常用xk(sk)表示第k阶段处于状态
的决策变量,它是状态变量的函数。
k时
4.策略与子策略
策略是一个决策序列的集合。由所有各阶段的决策组成的决 策函数序列称为全过程策略,简称策略,记为: P1,n(s1)。
子策略:从第k个阶段开始到最后阶段的决策组成的决策函数 序列称为k子过程策略,简称子策略,记为: Pk,n(sk)
管理运筹学
5
§1 问题的提出
第一阶段:只有1个始点A,终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题:
表6-4
本阶段始 点(状态)
A
阶段1 本阶段各终点(决策)
B1
B2
B3
B4
4+12=16 3+13=16 3+14=17 2+12=14
状态就是阶段的起始位置。它既是该阶段某支路的起点,又是 前一阶段某支路的终点。状态可以是数量,也可以是字符,数量状态 可以是连续的,也可以是离散的。
精品课件
管理运筹学
10
§2 基本概念、基本方程与最优化原理
状态变量:描述过程状态的变量称为状态变量。它可用一个数、
s 一 常组一数个或阶一段向有量若(干多个维状情态形。)第k来阶描段述的,状常态用就是k第该k阶阶段段所的有状始态点变的量集。合通。
精品课件
管理运筹学
4
§1 问题的提出
第二阶段:有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和终点进行分 析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题:
表6-3
本阶段始点 (状态)
B1 B2 B3 B4
阶段2 本阶段各终点(决策)
C1 2+12=14 4+12=16 4+12=16 7+12=19
C3
D2
6
75 1
4
精品课件
管理运筹学
E 2
§1 问题的提出
用穷举法的计算量,非常大。
讨论:
1、以上求从A到E的最短路径问题,可以转化为四个性质完全相同, 但规模较小的子问题,即分别从Di 、Ci、Bi、A到E的最短路径问题。
第四阶段:两个始点D1和D2,终点只有一个;
表6-1
本阶段始点 (状态)
阶段4 本阶段各终点(决策) 到E的最短距离
E
D1
10*
10
D2
6
6
分析得知:从D1和D2到E的最短路径唯一。
精品课件
管理运筹学
本阶段最优终点 (最优决策)
E E
3
§1 问题的提出
第三阶段:有三个始点C1,C2,C3,终点有D1,D2,对始点 和终点进行分析和讨论分别求C1,C2,C3到D1,D2 的最短路 径问题:
第六章 动态规划
§1 问题的提出 §2 基本概念、基本方程与最优化原理 §3 动态规划的应用
精品课件
管理运筹学
1
§1 问题的提出
一、引例—— 最短路径问题
下图表示从起点A到终点E之间各点的距离。求A到E的最短路径 。
4
3 A
3 2
2 B1
1 6
4
B2
7
2
C1
8
6
7 C2 5
D1
10
48 B3 3
1 6
多阶段决策问题:把一个问题看作是一个前后关联具有链状结 构的多阶段过程,也称为序贯决策过程。
2.适用范围
如果一个问题可将其过程划分为若干个相互联系的阶段问题, 且它的每一阶段都需要进行决策,则这类问题均可用动态规划方法进 行求解。
精品课件
管理运筹学

§2 基本概念、基本方程与最优化原理
一、基本概念
C2 1+11=12 7+11=18 8+11=19 5+11=16
C3 6+11=17 2+11=13 3+11=14 1+11=12
到E的最 短距离
12 13 14 12
本阶段最优终 点(最优决策)
C2 C3 C3 C3
分析得知:如果经过B1,则走B1-C2-D2-E; 如果经过B2,则走B2-C3-D1-E; 如果经过B3,则走B3-C3-D1-E; 如果经过B4,则走B4-C精3品-D课1-件E。
(2)对问题的求解是从全局考虑解决局部(阶段)的问题。
(3)各阶段选取的决策依赖于当前的状态,又随即引起状态的转移,整 个决策序列就是在变化的状态中产生出来,故有“动态”含义。
(4)决策过程是与阶段发展过程逆向而行。
精品课件
管理运筹学
8
§1 问题的提出
二、动态规划的含义及适用范围 1.动态规划
动态规划是解决一类多阶段决策问题的优化方法,它是考察 问题的一种途径,而不是一种算法。
61
13 4 B2 7
2
48 B3 3
12 C1 8
6
11 7 C2
5
1
C3 6
10
D 1 10
0
E
D2 6 6
14
11
75 1
B4 12
以上过程,仅用了22次加法,计精算品效课件率远高于穷举法。
管理运筹学
7
§1 问题的提出 从引例的求解过程中可以得到以下启示:
(1)对一个问题是否用上述方法求解,其关键在与能否将问题转化为相 互联系的多个阶段的决策问题。
1.阶段和阶段变量
用动态规划方法求解问题时,首先将问题的全过程适当地分 成若干个互相联系的阶段,以便能按一定的次序去求解。
阶段的划分,一般根据时序和空间的自然特征来划分。如引例 可按照空间划分为4个阶段。
阶段变量:描述阶段的变量称为阶段变量。用k表示,引例中, k=1,2,3,4.
2.状态和状态变量sk
最优策略:能够达到总体最优的策略。
精品课件
管理运筹学
11
§2 基本概念、基本方程与最优化原理
5. 状态转移方程
它是确定过程由某一阶段的一个状态到下一阶段另一状 态的演变过程,用sk+1=Tk(sk, xk)表示。该方程描述了第k阶段到第 k+1阶段的状态转移规律。因此又称为状态转移函数。
相关主题