第七章 动态规划.ppt

文档介绍：第七章动态规划
动态规划简介
多阶段决策过程最优化
多阶段决策过程,是指一类特殊的过程,它们可以按时间顺序分解成若干个相互联系的阶段,称为“时段”,在每个时段都要做决策,全部过程的决策是一个决策序列。多阶段决策问题也称为序贯决策问题。
多阶段决策问题的目标是要达到整个活动过程的总体最优。在每个阶段进行决策时不应仅考虑本阶段最优,尤其应考虑对最终目标的影响,从而做出对全局来说最优的决策。
动态规划是符合这种要求的一种决策方法。
第 1 阶段
第 2 阶段
第 n阶段
决策
决策
决策
多阶段决策过程图示
动态规划的基本概念
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
6
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
1
3
4
3
阶段: k=1,2,3,4,5
1
2
3
4
5
基本概念(续一)
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
6
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
1
3
4
3
状态:各阶段开始时的客观条件。表示状态的变量称为状态变量,常用sk表示第k阶段的状态变量,第k阶段所有状态变量的集合记为Sk。
基本概念(续二)
决策:当一个阶段的状态取定了后,就可以作出不同决定(或选择),从而确定下一阶段的状态,这种决定称为决策。
表示决策的变量称为决策变量,uk(sk)就表示第k阶段当状态为sk时的决策变量。
决策变量的取值常常限制在一定的范围内,这一范围称为允许决策集合,常用记号Dk(sk)表示第k阶段状态为sk时的允许状态集合。
基本概念(续三)
各阶段的决策确定后,整个过程各阶段的决策就构成一个决策序列,称为策略,用p1,n{u1(s1), u2(s2), …, un(sn)}表示。
有时还需要考虑后部子策略pk,n{uk(sk), …, un(sn)}。
动态规划要求的就是使整个问题达到最优的策略。
基本概念(续四)
状态转移方程:动态规划中一个阶段的状态常常是上一阶段的状态和决策的结果。如果给定了第k阶段的状态sk,和第k阶段的决策uk(sk),则第k+1阶段的状态sk+1也就完全确定了,这一关系可用下面的方程表示
sk+1=Tk(sk, uk)
称之为状态转移方程,它表示了由第k阶段到第k+1阶段状态转移的规律
基本概念(续五)
指标函数:用于衡量决策或策略优劣的数量指标称为指标函数。
阶段指标函数:它通常是指在第k阶段,从状态sk出发,采用决策uk时的效益,记为d(sk, uk)。
过程指标函数:它通常表示在第k阶段时的状态为sk时,采用后部子策略pk,n的效益值,记为Vk,n(sk, pk,n)。最优指标函数记为fk(sk),表示第k阶段的状态为sk时,采用了最优后部子策略p*k,n的指标函数值, Vk,n(sk, pk,n)与fk(sk)的关系是
f1(s1)就是从初始状态s1到全过程结束的整体最优函数。
对最短路线问题阶段指标函数就是两点间的距离。后部子过程pk,n的指标函数Vk,n(sk, pk,n)就是在第k阶段位于点sk时到终点的距离,而fk(sk)就是到终点的最短距离。
最短路线问题,就是要求f1(A)以及相应的路线。