chap7动态规划.ppt

chap7动态规划.ppt第七章动态规划动态规划问题的基本概念和基本原理动态规划模型的建立与求解应用举例马氏决策规划例1:问题的引出例1:某运输公司有500辆运输卡车,超负荷运输(每天满载行驶500km以上)时,年利润25万元/辆,;低负荷运输(每天行驶300km以下),年利润16万元/辆,。现要求制定5年计划,如何分配不同负荷下的卡车数量,使5年的总利润最大。:递归性动态规划的应用对象应用对象:多阶段决策优化包括:1)不同时间段的规划问题动态规划的原意2)可化为不同地段、:最短路线问题沿着线路网络,在A、E之间铺设一条管路,如何使总长度最小。AB1B3B2C1C2D1D3D2E321431335253142315动态规划的类型根据变量的类型,动态规划可化分为:1)离散确定型:2)连续确定型:2)离散随机型:Markov链3)连续随机型:Markov随机过程动态规划的基本概念1。阶段:2。状态3。决策和策略4。状态转移方程5。指标函数阶段1。阶段:问题过程,按时间、空间的特征分解成若干相互联系的阶段。AB1B3B2C1C2D1D3D2E321431335253142315状态2。状态:各阶段开始时的客观条件,叫做状态。常用sk代表第k阶段的状态变量,其允许范围为Sk。如例2中,S1={A} S2={B1,B2,B3} S3={C1,C2} S4={D1,D2,D3}决策3。决策:对取定的状态,就可以作出不同的决定,以确定下一阶段的状态,称为决策。表示决策的变量,称为决策变量,用uk(sk)表示。决策变量的集合,称为允许决策集合。用Dk(sk)表示。