04 动态规划.ppt

网络优化
Network Optimization
/netopt
清华大学数学科学系谢金星
清华大学课号:40420213(本),70420133(研)
第4章动态规划(Dynamic Programming)
1
动态规划问题的例子
例()最短路问题(Shortest Path Problem)
许多网络优化问题要用到动态规划技术
S
T
特点:多阶段决策- 子决策仍然最优- 动态规划(DP)技术
动态规划– . Bellman (1950’s)
2
所谓决策(Decision Making),就是人们为了达到一定的目的,从若干个可能的策略(Policy)(如行动、方案)中选取最好的策略的过程. 一般来说,一个决策模型包含三个最基本的因素:
(1)自然状态(或简称状态, State):这是指决策活动中决策者无法控制的一些因素,即决策时客观对象所具备的基本条件. 状态的集合称为状态集合或状态空间.
(2)策略:这是指决策活动中决策者可以采取的行动方案. 策略的集合称为策略集合或策略空间.
(3)益损值:这是指决策活动中决策者可以采取不同的策略,在不同的自然状态下所获得的收益或损失值. 它是策略和状态的函数,也是决策活动的目标和基础.
多阶段决策模型
战略决策(高层决策)、战术决策(中层决策)、操作决策(基本决策)
单目标决策、多目标决策
单阶段决策(一次决策)、多阶段决策
确定型决策、非确定型决策或风险型决策(随机决策、模糊决策)
3
多阶段决策过程
多阶段决策(Multi-Stage Decision Making),是将决策问题的全过程恰当地划分为若干个相互联系的子过程(每个子过程为一个阶段),以便按照一定的次序去求解. 阶段一般是根据时间和空间的自然特征来划分,以便于问题的求解为目的. 描述阶段的变量称为阶段变量,一般用k表示. 从第k个阶段开始点到全过程终点的过程称为后部子过程,或k子过程.
在多阶段决策问题中,状态表示每个阶段开始时所处的自然状况或客观条件. 描述过程状态的变量称为状态变量,一般用xk表示第k个阶段的状态变量.
当过程处于某个阶段的某个状态时,从该状态演变为下一个阶段某状态的选择,称为决策(抉择,Decision). 描述决策的变量称为决策变量,一般用uk表示第k个阶段的决策变量,而用Uk(xk)表示第k个阶段xk状态下的所有允许决策的集合.
4
状态转移方程
无后效性的多阶段决策过程
动态规划中,多阶段决策问题具有无后效性(马尔科夫性质),即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响, 或者说“未来与过去无关”. 即由状态xk出发的后部子过程可以看成一个以xk为初始状态的独立过程.
相应于后部子过程(k子过程)的决策序列称为子策略,记为pk,n(xk) ,所有允许子策略的集合记为Pk,n(xk).
由所有各阶段的决策组成的决策序列称为全过程策略,或简称策略,记为p1,n(x1). 可供选择的所有全过程策略的集合构成允许策略集合,记为P1,n(x1) .其中能使总体性能达到最优的策略称为最优策略,一般记为
5
一般记为
无后效性的多阶段决策过程- 准则函数及可分性
准则函数/指标函数(Criterion Function)是衡量策略好坏的尺度(益损值).
定义在全过程上的准则函数相当于目标函数,一般记为 V1,n(x1; p1,n ) ,或简记为V1,n
定义在k子过程上的准则函数,记为Vk,n(xk; pk,n ) ,简记为Vk,n
准则函数在第k阶段一个阶段内的取值称为第k阶段的准则函数,记为vk(xk; uk)
最优性原理中,准则函数具有(阶段)可分性,即
6
最优性定理
设有一个准则函数可分的无后效性的多阶段决策过程,阶段变量k=1,2,…,n,允许策略是最优策略的充要条件是: 对任意1<k<n, 当初始状态为x1时, 有
()
式中, ,即是由给定的初始状态x1和子策略p1,k-1所确定的第k阶段的状态.
证明: 必要性. 设允许策略是最优策略,则
7
最优性定理
充分性. 设允许策略满足定理的条件(),
为任一允许策略,则
因为
所以, 是最优策略
证毕
8
“全过程的最优策略具有这样的性质:不管该最优策略上某状态以前的状态和决策如何,对该状态而言,余下的诸决策必定构成最优子策略. ”即:最优策略的任一后部子策略都是最优的.
最优化原理
这只是最优性定理的一个推论,即最优策略的必要条件.
9
建立动态规划模型的基本过程是:
(1)   正确划分阶段,选择阶段变量k.
(2