《运筹》教学课件动态规划 8.2动态规划的基本原理.ppt

《《运筹》教学课件动态规划 8.2动态规划的基本原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.2动态规划的基本原理动态规划的目标有多个方案,且每个方案都有一个总指标函数值动态规划的目标是找到最优的方案,也就是找到使得总指标函数最优(最大或最小)方案,即在总指标函数中,一般来说s1是给定的，其它的变量都是不确定的，这样一来总指标函数有2n-1个变量，直接求极值非常困难。动态规划的最优化原理提供了另外一种求解思路。最优化原理的语言描述一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略。理解1：如果第一阶段到第k阶段形成的策略是最优策略的话，那么从第一阶段到第t阶段所形成的策

2、略也必须是最优策略（tk)例如在一个图中，若从点1到点5的最短路线为1→2→3→5则2→3→5是点2到点5的最短路线，3→5是点3到点5的最短路线1.利用前部子指标函数来描述

3、由于opt{V1,t+1}仅仅与状态st+1有关，因而也称opt{V1,t+1}为前部最优值函数，用ft{st+1}来表示，则上式可表示为最优化原理的数学描述——和形式为了递推方程形式的统一,可以引入f0(s1)=0,这样一来上面的递推公式就可写为下式由于f0(s1)=0是专门引入的，特称之为边界条件最优化原理的数学描述——和形式2.利用后部子指标函数由于opt{Vt,n+1}仅仅与状态st有关，因而也称opt{Vt,n+1}为后部最优值函数，用ft{st}来表示，则上式可表示为最优化原理的数学描述——和形式为了递推方程形式的统一,可以引入fn+1(sn

4、+1)=0,这样一来上面的递推公式就可写为下式由于fn+1(sn+1)=0是专门引入的，也称之为边界条件最优化原理的数学描述——和形式由于最优值指标函数fk(sk+1)中与状态变量st(1≤t≤k)和决策变量ut(1≤t≤k)无关，这意味着以前的状态和决策不影响后面的优化过程,也就是fk+1(sk+2)仅仅与fk(sk+1)有关，把这种特性称之为无后效性。动态规划的无后效性1.基于前部最优值指标函数递推方程由于最优值指标函数fk(sk)中与状态变量st+1(k≤t≤n)和决策变量ut(k≤t≤n)无关，这意味着以前的状态和决策不影响以后的优化过程，也就是

5、fk-1(sk-1)仅仅与fk(sk)有关，把这种特性称之为无后效性。2.基于后部最优值指标函数递推方程1.利用前部子指标函数来描述最优化原理的数学描述——积形式其中f0(s1)=1为引入的边界条件2.利用后部子指标函数最优化原理的数学描述——积形式其中fn+1(sn+1)=1是引入的边界条件