第13讲 动态规划基本理论讲解.ppt

第八章 动态规划 第13讲 动态规划的基本理论(6.1) 多阶段决策过程 动态规划的基本概念和基本方程 动态规划的最优性原理 最短路问题（逆推法、顺推法） 引例：如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。 多阶段决策过程最优化问题：有一些活动，它在时间或空间上可以分成若干个阶段，需要对每个阶段进行决策，使得活动的整体效果最好。 每个阶段的决策都不是可以任意确定的，它依赖于当前的状况，同时，它的决策结果又影响到以后的决策。组成了一个决策序列。 这样的决策过程是在变化的过程中产生的，故有动态的含义。处理它的方法称为动态规划的方法。 方法：多阶段问题转化成一系列互相联系的较容易的单阶段问题。 常见的指标函数有： 1)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的和。 Vk,n（Sk，Uk ，Sk＋1 ，…,Sn+1）＝ Vk,n（Sk，Uk，Sk＋1，…,Sn+1） ＝vk(sk,uk)+ Vk+1,n（Sk+1，Uk+1 ，Sk＋2 ，…,Sn+1） 2)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的乘积，即： Vk,n（Sk，Uk ，Sk＋1 ，…,Sn+1）＝ 指标函数的最优值称为最优值函数，记为fk(sk)。 表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。如：f1(A)＝18，f2(B1)＝13。 即 fk(sk)＝ opt Vk,n(sk,uk,……,sn,un) （uk,…,un） 式中的“opt”（optimization）可根据具体问题而取min或max。 一般情况下，k阶段和k+1阶段之间的递推关系式可写成： fk(Sk)＝opt{ vk(Sk,Uk(Sk))+ fk+1(Sk+1) } k=n,n-1,…,2,1 fk(Sk)＝opt{ vk(Sk,Uk(Sk))+ fk+1(Uk(Sk)) } k=n,n-1,…,2,1 ① 边界条件为: fn+1(Sn+1)=0 这种递推关系式①称为动态规划的基本方程。 （二）、动态规划的基本思想和基本方程 最短路问题：如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。 从A点到G点可分成6个阶段。以A为起点，终点有两个B1、B2，有两个选择。若选择B2，则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果，直接影响到后面的选择和决策的结果。 最短路线有一个重要特性： 如果从起点A经过C2点和D1点到达终点G是一条最短的路线，则由C2 点经过D1 点到达G点的这条子路线，是由C2 点出发到达G点所有路线中的最短路线。 寻找最短路线的方法，从最后一段开始，由后向前逐步推进，找出各点到G点的最短路线，最后就能确定一条从A点到G点的最短路线。 最短路线为A→B1→C2→D1→E2→F2→G 动态规划模型分类 状态转移图 标号法 最短路线为A→B1→C2→D1→E2→F2→G 逆序解法 顺序解法 顺序解法 最优性原理：美国运筹学家贝尔曼提出 无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。 将决策问题划分为若干个阶段，全过程的优化问题就分解为子过程的优化问题，由后向前逐步倒推，最优化的子过程逐渐成为全过程最优。 作为全过程的最优策略P*1,n的组成部分的任一子策略P*k,n(Sk)，一定是从状态Sk 出发直至终点的最优策略。 过程 变量 随机 确定 连续 离散 连续随机型 连续确定型 离散随机型 离散确定型 7、写出恰当的边界条件 ，从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优结果，就是这个问题的最优解，并找到相应的最优策略。 fk(sk)＝Min{dk(uk)+fk+1(sk+1)} uk∈Dk(sk) k＝6,5,4,3,2,1 f7(s7)＝0 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 用dk(sk,uk)＝vk(sk,uk)表示从点Sk到Sk＋1的距离。 Vk,n表示在第k阶段从点Sk到终点的距离。fk(Sk) 表示第k阶段状态为Sk时，从第k阶段开始到第n阶段的最短距离。 f7(S7)＝0 此问