文档介绍：work Optimization http:// /netopt 清华大学数学科学系谢金星办公室:理科楼 2266# (电话: 62787812 ) Email:******@. http:// ./~jxie/opt 清华大学课号: 70420133 第4章动态规划(Dynamic Programming) 2 动态规划问题的例子例(续例 )最短路问题(Shortest Path Problem) 许多网络优化问题要用到动态规划技术 ST 特点:多阶段决策- 子决策仍然最优- 动态规划(DP) 技术动态规划– . Bellman (1950 ’s) 3 所谓决策(Decision Making) , 就是人们为了达到一定的目的,从若干个可能的策略(Policy) (如行动、方案)中选取最好的策略的过程. 一般来说, 一个决策模型包含三个最基本的因素: (1 )自然状态(或简称状态, State ): 这是指决策活动中决策者无法控制的一些因素,即决策时客观对象所具备的基本条件. 状态的集合称为状态集合或状态空间. (2 )策略:这是指决策活动中决策者可以采取的行动方案. 策略的集合称为策略集合或策略空间. (3)益损值:这是指决策活动中决策者可以采取不同的策略,在不同的自然状态下所获得的收益或损失值. 它是策略和状态的函数,也是决策活动的目标和基础. 多阶段决策模型?战略决策(高层决策)、战术决策(中层决策)、操作决策(基本决策) ?单目标决策、多目标决策?单阶段决策(一次决策)、多阶段决策?确定型决策、非确定型决策或风险型决策(随机决策、模糊决策) 4 多阶段决策过程多阶段决策( Multi-Stage Decision Making ), 是将决策问题的全过程恰当地划分为若干个相互联系的子过程(每个子过程为一个阶段),以便按照一定的次序去求解. 阶段一般是根据时间和空间的自然特征来划分,以便于问题的求解为目的. 描述阶段的变量称为阶段变量,一般用 k表示. 从第 k个阶段开始点到全过程终点的过程称为后部子过程,或 k子过程. 在多阶段决策问题中, 状态表示每个阶段开始时所处的自然状况或客观条件. 描述过程状态的变量称为状态变量,一般用 x k表示第 k个阶段的状态变量. 当过程处于某个阶段的某个状态时,从该状态演变为下一个阶段某状态的选择,称为决策(抉择, Decision ). 描述决策的变量称为决策变量,一般用 u k 表示第 k 个阶段的决策变量,而用 U k(x k)表示第k个阶段 x k状态下的所有允许决策的集合. 5 状态转移方程),( 1kkkkuxTx??无后效性的多阶段决策过程动态规划中,多阶段决策问题具有无后效性(马尔科夫性质), 即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响, 或者说“未来与过去无关”. 即由状态 x k出发的后部子过程可以看成一个以 x k为初始状态的独立过程. 相应于后部子过程( k子过程)的决策序列称为子策略,记为 p k,n(x k) ,所有允许子策略的集合记为 P k,n(x k). 由所有各阶段的决策组成的决策序列称为全过程策略,或简称策略,记为 p 1,n(x 1). 可供选择的所有全过程策略的集合构成允许策略集合,记为 P 1,n(x 1) . 其中能使总体性能达到最优的策略称为最优策略,一般记为),,,( **2 *1 *,1n nuuup??6 一般记为 nkkkk nj jjjnkVuxvuxvV ,1 1 ,),(),( ??????无后效性的多阶段决策过程- 准则函数及可分性准则函数/指标函数( Criterion Function )是衡量策略好坏的尺度(益损值). ?定义在全过程上的准则函数相当于目标函数,一般记为 V 1,n(x 1; p 1,n) ,或简记为 V 1,n ?定义在 k子过程上的准则函数,记为 V k,n(x k ; p k,n) , 简记为 V k,n ?准则函数在第 k阶段一个阶段内的取值称为第 k阶段的准则函数,记为 v k(x k ; u k)最优性原理中, 准则函数具有(阶段)可分性,即算,如加法或乘法等。是满足单调性的某种运其中????????),,(),(),( 111 , nnnkkkkkknkuxvuxvuxvV? 7 最优性定理定理 设有一个准则函数可分的无后效性的多阶段决策过程,阶段变量 k =1,2, …,n,允许策略是最优策略的充要条件是: 对任意 1< k<n, 当初始状态为 x 1时, 有() 式中,