chap7_动态规划.ppt

第七章动态规划动态规划问题的基本概念和基本原理动态规划模型的建立与求解应用举例马氏决策规划例1:问题的引出例1:某运输公司有 500 辆运输卡车,超负荷运输(每天满载行驶 500 km 以上)时, 年利润 25万元/辆,卡车的年损坏率为 ; 低负荷运输(每天行驶 300 km 以下),年利润 16万元/辆,年损坏率为 。现要求制定5年计划,如何分配不同负荷下的卡车数量,使 5年的总利润最大。例1的线性规划模型???? 51)16 25 ( max i il ihxxz ia il ihxxx?? il hi iaxxx)()( ,1?????500 1? ax 51??i52??i0,,? ia il ihxxx :递归性动态规划的应用对象应用对象: 多阶段决策优化包括: 1)不同时间段的规划问题?动态规划的原意 2 )可化为不同地段、步骤的静态规划问题美国数学家 R. Bellman 于50年代提出动态规划例2:最短路线问题沿着线路网络,在 A、E之间铺设一条管路, 如何使总长度最小。 A B 1B 3B 2C 1C 2D 1D 3D 2E 321 431335 253142 315 动态规划的类型根据变量的类型,动态规划可化分为: 1)离散确定型: 2)连续确定型: 2)离散随机型: Markov 链 3)连续随机型: Markov 随机过程动态规划的基本概念 1。阶段: 2。状态 3。决策和策略 4。状态转移方程 5。指标函数阶段 1。阶段: 问题过程,按时间、空间的特征分解成若干相互联系的阶段。 A B 1B 3B 2C 1C 2D 1D 3D 2E 321 431335 253142 315 状态 2。状态: 各阶段开始时的客观条件,叫做状态。常用 s k代表第 k阶段的状态变量,其允许范围为 S k。如例 2中, S 1 ={A} S 2 ={B 1,B 2,B 3} S 3 ={C 1,C 2} S 4 ={D 1,D 2,D 3} 决策 3。决策: 对取定的状态,就可以作出不同的决定, 以确定下一阶段的状态,称为决策。表示决策的变量,称为决策变量,用 u k(s k)表示。决策变量的集合,称为允许决策集合。用 D k(s k)表示。