文档介绍：第九章动态规划
§1 多阶段决策过程最优化
§2 动态规划基本概念
§3 动态规划基本原理
§4 动态规划的应用
1
一、多阶段决策问题
动态规划是把多阶段决策问题作为研究对象。
多阶段决策问题:根据问题本身的特点,可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题),在它的每一阶段都需要作出决策,并且在一个阶段的决策确定以后再转移到下一个阶段。
2
多阶段决策过程(Multi-Stagedecision process):
前一个阶段的决策要影响到后一个阶段的决策,从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列,称为一个策略。一般来说,由于每一阶段可供选择的决策往往不止一个,因此,对于整个过程,就会有许多可供选择的策略。
3
最优策略:
若对应于一个策略,可以由一个量化的指标来确定这个策略所对应的活动过程的效果,那么不同的策略就有各自的效果。在所有可供选择的策略中,对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略,这类问题就是多阶段决策问题。
4
多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着,本段决策的执行将影响到下一段的决策,以至于影响总体效果,所以决策者在每段决策时不应仅考虑本阶段最优,还应考虑对最终目标的影响,从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。
5
图1 运输网络图示
6
多阶段决策过程特点:
要点:阶段,状态,决策,状态转移方程,k-后部子过程
状态
x1
阶段1
T1
决策u1
状态
x2
决策u2
阶段2
T2
状态
x3
...
状态
xk
决策uk
阶段k
Tk
状态
xk+1
...
状态
xn
决策un
阶段n
Tn
状态
xn+1
7
四、动态规划方法导引
例1:为了说明动态规划的基本思想方法和特点,下面以图1所示为例讨论的求最短路问题的方法。
第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种,第二三两段的走法各有两种,第四段的走法仅一种,因此共有3×2×2×1=12条可能的路线,分别算出各条路线的距离,最后进行比较,可知最优路线是v1 →v3 → v7 → v9 →v10 ,最短距离是18.
8
显然,当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算.
第二种方法即所谓“局部最优路径”法,是说某人从k出发,他并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是v1 →v3 →v5 → v8 → v10 ,全程长度是20;显然,这种方法的结果常是错误的.
9
第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是,首先将问题划分为4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到。
为了找出所有可能状态的最优后继过程,动态规划方法总是从过程的最后阶段开始考虑,然后逆着实际过程发展的顺序,逐段向前递推计算直至始点。
10