运筹学教案动态规划.pptVIP

决策空间：即决策变量可能取值的集合，用Dk(xk)表示第k个阶段xk状态下的所有允许决策的集合。状态转移方程状态转移：系统由某一阶段的一个状态因相关决策而转变到下一个阶段的另一个状态。与阶段、状态和决策有关，用下图示意：k阶段决策输入状态输出状态称为状态转移方程全过程与后部k子过程从k阶段开始到终止状态为止的过程称为动态规划问题的后部k子过程。如下图所示：全过程：k=1时的子过程。k=1k=nkk=2nkk+1k=n,n-1,n-2…3,2,1策略：设为k阶段作出的决策，则称其组成的决策序列为整个过程的一个全过程策略，简称为策略，记为p1,n(x1)。可供选择的所有全过程策略的集合构成允许策略集合，记为P1,n(x1)。最优策略：使总体效果达到最优的策略。记为k子策略:k部子过程对应决策形成的决策序列。记为pk,n(xk)=策略与k子策略指标函数与最优指标数阶段指标函数：指对某一个阶段的决策效果进行衡量其优劣的一种数量指标。一般记为：vk(xk;uk)K指过程的指标函数：描述k子过程策略效果优劣的数量函数，记为：Vk,n(xk;pk,n)或Vk,n。由阶段划分与状态选择的无后效性知，k阶段指标函数具有可分性，即可写为：K=1时称为全过程的指标函数。一般地，其可分性写为最优指标函数：指标函数的最优值称为最优指标函数，记为即有：注:指标函数的含义是多样的,如:距离、利润、成本、产品产量、资源消耗等。最优化原理“作为全过程的最优策略具有这样的性质：无论过去的状态和决策如何，对于前面决策所形成的状态（即该最优策略上某一状态）而言，余下的诸决策必须构成以此状态为初始状态的最优策略。即：最优策略的任一后部子策略都是最优的。最优化原理与动态规划问题基本方程即，为最优策略,对任意阶段k(1kn),他的子策略对于为始点的后部k子过程而言，也必须是最优的。利用动态规划最优性原理，可以把多阶段决策问题求解看成是对若干个相互联系的子问题逐个求解的反向递推过程。求解的过程可用如下基本方程描述：注：最优化原理只是最优性定理的一个推论，即最优策略的必要条件。即最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价。动态规划问题的基本方程k=1k=nkk=2逆序计算fk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数故逆序递推法的基本方程为：顺序递推算法的基本方程：k=1k=nkk=2顺序计算此两个基本方程描述多阶段决策问题的求解方法，可以处理广泛的实际优化问题，而且可以得到各阶段的一系列最优解。但是要受到维数限制。0102顺序递推算法的基本方程：求解动态规划问题的过程：将问题过程划分恰当阶段，选择阶段变量k.。正确选择状态变量xk.应注意：既能够正确描过程的演变，又要满足无后效性。正确选择决策变量uk，确定允许集合。正确写出状态转移方程xk+1=Tk(xk,uk)。列出按阶段可分的准则函数V1,n，要满足几个性质。根据求解方向，给出边界条件。利用基本方程逆推求解。设阶段为n的多阶段决策过程，决策变量k=1,2,…,n,允许策略是最优策略的充要条件是:对任意1kn,当初始状态为x1时,有：(4.3)式中,,即是由给定的初始状态x1和子策略p1，k-1所确定的第k阶段的状态.。动态规划的最优性定理最优性原理仅为策略最优的必要条件，是最优性定理的推论，为此下面介绍最优性定理。动态规划应用举例例一：前述最短距离问题逆向标注法AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141阶段2阶段3阶段4阶段5阶段首先求第五阶段各点到F点的最短距离12AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141阶段2阶段3阶段4阶段5阶段12逆推一个阶段，用基本方程求第4阶段和状态点到F点的最短距离。如：f4(D1)=min{4+1,2+2}=4,即D1经E