目录绪论 ch1线性规划 ch2 对偶线性规划 ch3 运输问题 ch4 目标规划 ch5 整数规划 ch6 动态规划 ch7 图与网络分析 ch8 存储论 ch9 排队论 ch10 博弈论 ch11 决策论 HYX动态规划 Dynamic programming 五十年代贝尔曼( B. E. Bellman )为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理,可归结为一个递推公式 HYX HYX第五章动态规划引言最优化原理动态规划的基本概念和基本方程应用举例 HYX4 引言动态规划研究的问题“多阶段决策过程--最优化” 1234 n …………………………………… HYX5最优化原理 1951 年 Bellman 一个最优策略具有这样的性质,即不论初始状态与初始策略如何,对于先前决策所造成的状态而言,下余所有决策必构成最优决策最优性原理“最优策略的一部分也是最优的” HYX6 (1) 阶段: k (2) 状态变量: S k (3) 决策变量: u k (S k) (4) 策略: 各阶段的决策组成的决策函数序列,称为(全过程)策略。(5) 状态转移方程: S k+1= T (S k, u k) (6) 阶段效应:d k,n (S k , u k) (7) 最优指标函数: f k (S k) 动态规划的基本概念和基本方程(一)基本概念 HYX7 f k (S k)= min{d(S k , u k )+ f k+1 (S k+1 )} k=n, …1 F n+1 (S n+1 )=0或f k (S k)= min{d(S k ,u k )+ f k+1 (S k+1 )} k=n-1, …1 f n (S n)= min{d(S n ,u n )} (二)逆序解法基本方程?初始状态给定时用逆序解法?终止状态给定时用顺序解法 HYX8动态规划的步骤 1、确定问题的阶段和编号 2、确定状态变量–用S k表示第 k 阶段的状态变量及其值 3、确定决策变量–用u k (S k)表示第 k 阶段的决策变量,并以 u k (S k) *表示该阶段的最优决策 4、确定状态转移方程 S k-1 = T (S k, u k)反向编号,S k+1= T (S k, u k)正向编号 5、确定阶段效应–直接一步转移的效果 d k(s k, u k ) 6、确定总指标(效果)函数–指某一阶段某状态下到终端状态的总效果,它是一个递推公式 251 1214 10610 41311 12 3965810 52 C 1C 3 D 1 A B 1B 3B 2D 2E C 2求从 A到E的最短路径应用举例最短路径问题 HYX HYX (1) 阶段: k=1,2,…, 4 n=4 (2) 状态变量: S k-第k阶段所处的位置状态集合如S 2 : (B 1 , B 2) (3) 决策变量 u k:在第 k段S k状态时决定选取的下一段的某点(4) 状态转移方程:S k+1=u k 解:
动态规划00 来自淘豆网m.daumloan.com转载请标明出处.
