动态规划问题的基本要素和最优化原理.ppt

第二节动态规划问题的基本要素和最优化原理§§§、阶段:把一个问题的过程,恰当地分为若干个相互联系的阶段,以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分,一般是根据时间和空间的自然特征来进行的,但要便于问题转化为多阶段决策。2、状态:表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态,描述过程状态的变量称为状态变量。年、月、路段一个数、一组数、一个向量状态变量的取值有一定的允许集合或范围,此集合称为状态允许集合。§、决策:表示当过程处于某一阶段的某个状态时,可以作出不同的决定,从而确定下一阶段的状态,这种决定称为决策。描述决策的变量,称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量(多维情形)来描述。在实际问题中决策变量的取值往往在某一范围之内,此范围称为允许决策集合。系统在某一阶段的状态转移不但与系统的当前的状态和决策有关,而且还与系统过去的历史状态和决策有关。4、多阶段决策过程可以在各个阶段进行决策,去控制过程发展的多段过程;其发展是通过一系列的状态转移来实现的;图示如下:状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定,第k+1阶段状态变量sk+1的值也就确定。其状态转移方程如下(一般形式)12ks1u1s2u2s3skuksk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程,即具有无后效性的多阶段决策过程。如果状态变量不能满足无后效性的要求,应适当地改变状态的定义或规定方法。动态规划中能处理的状态转移方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下无后效性(马尔可夫性)如果某阶段状态给定后,则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响;过程的过去历史只能通过当前的状态去影响它未来的发展;构造动态规划模型时,要充分注意是否满足无后效性的要求;状态变量要满足无后效性的要求;5、策略:是一个按顺序排列的决策组成的集合。在实际问题中,可供选择的策略有一定的范围,称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。6、状态转移方程:是确定过程由一个状态到另一个状态的演变过程,描述了状态转移规律。7、指标函数和最优值函数:用来衡量所实现过程优劣的一种数量指标,为指标函数。指标函数的最优值,称为最优值函数。在不同的问题中,指标函数的含义是不同的,它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数,应具有可分离性,并满足递推关系。小结:方程:状态转移方程概念:阶段变量k﹑状态变量sk﹑决策变量uk;指标:动态规划本质上是多阶段决策过程;效益指标函数形式:和、积无后效性可递推解多阶段决策过程问题,求出最优策略,即最优决策序列f1(s1)最优轨线,即执行最优策略时的状态序列最优目标函数值从k到终点最优策略子策略的最优目标函数值1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件(简称基本方程)。要做到这一点,就必须将问题的过程分成几个相互联系的阶段,恰当的选取状态变量和决策变量及定义最优值函数,从而把一个大问题转化成一组同类型的子问题,然后逐个求解。即从边界条件开始,逐段递推寻优,在每一个子问题的求解中,均利用了它前面的子问题的最优化结果,依次进行,最后一个子问题所得的最优解,就是整个问题的最优解。§、在多阶段决策过程中,动态规划方法是既把当前一段和未来一段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法。因此,每段决策的选取是从全局来考虑的,:作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,相对于前面的决策所形成的状态而言,余下的决策序列必然构成最优子策略。”也就是说,一个最优策略的子策略也是最优的。3、在求整个问题的最优策略时,由于初始状态是已知的,而每段的决策都是该段状态的函数,故最优策略所经过的各段状态便可逐段变换得到,从而确定了最优路线。