第七章_动态规划1.pptVIP

第七章 动态规划;1、 动态规划是解决多阶段决策过程最优化的一种有效的数学方法，它是美国学者Richard.bellman 在1951年提出的，1957年他的专著《动态规划》的问世标志着运筹学的一个重要分支——动态规划的诞生。;v2;v2;动态规划问题的基本特征： ; 5 . 状态具有无后效性: 当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：;动态规划基本原理: 是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。; 需要指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。 必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。; (1)阶段：为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。 一个阶段，就是需要作出一个决策的子问题. 通常，阶段可按时间或空间划分。 用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量．可以是确定数、不定数或无限数。 ; (2) 状态：表示每个阶段开始所处的自然状况或客观条件。 通常一个阶段有若干个状态，反映状态变化的量叫做状态变量 . sk (表示第k阶段的状态变量 )。 状态变量可以用一个数，一组数或一向量来描述 状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合 S K ={s1,s2, …, s k ,…}; 在最短路问题中，第一阶段状态为v1，状态变量s1的状态集合S1={v1}；每一状态可以取不同值 ,如v1取2,5,8. 第二阶段则有三个状态：v2 ,v3,v4 状态变量s2的状态集合S2={v2 ,v3,v4 } ； 第三阶段有二个状态:v5,v6状态变量s3的状态集合S3={v5,v6 } ； 第四阶段则有三个状态:v7,v8,v9, 状态变量s4的状态集合S4={v7,v8,v9 } ； 第五阶段则有一个状态v10状态变量s5的状态集合S5={v10 },; (3) 决策：当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。描述决策的变量，称为决策变量。 和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，也可以是状态变量的函数. 常用xk（sk）表示第k阶段当状态为sk时的决策变量。; 在状态sk下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。; (5) 状态转移方程：系统在阶段k处于状态sk，执行决策xk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1 之间的函数关系. 记为 sk+1=T(sk , xk) ; (6) 指标函数或收益函数：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为 k 阶段指标函数、k子过程指标函数及最优指标函数。; 最优指标函数:;动态规划要求子过程指标满足递推关系 ，即;连乘形式 (vj≠0) ：; 终端条件：为了使以上递推方程有递推起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(sn)的值。;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2; 用逆序法列表求解最短路径问题;;;; 建立动态规划模型的步骤 1、划分阶段k 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量sk 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量xk(sk)及允许决策集合Dk(sk) 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。; 4、确定状