1、2010年5月管理工程学院运筹学运筹学1一、动态规划方法导引一、动态规划方法导引 1.1.全枚举法或穷举法。全枚举法或穷举法。共有共有18条可能路线，条可能路线，进行比较，求得最优路线进行比较，求得最优路线Q A3 B1 C1T。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学22.“.“局部最优路径局部最优路径”法法：选择当前最短途径，：选择当前最短途径，“逢近便走逢近便走”。所取决策必是所取决策必是Q A1 B2 C2T，全程长度，全程长度是是13。QTA1A2A3B1B2B3C1C224374642442514633334
2、2010年5月管理工程学院运筹学运筹学3全枚举法全枚举法计算工作量将会十分庞大。计算工作量将会十分庞大。局部最优求出的解不一定是最优解。局部最优求出的解不一定是最优解。2010年5月管理工程学院运筹学运筹学4 3.动态规划方法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下：把问题划分为几个阶段。按阶段顺序首先考虑最后阶段如第四阶段的最优决策，也就是走哪条路线最短。按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段上各初始点的最优决策即可。2010年5月管理工程学院运筹学运筹学5用动态规划方法逐段求解时，每个阶段上的求优方法基本相同，而且比较简单，每一阶段的计算都要
3、利用上一阶段的计算结果，因而减少了很多计算量。阶段数愈多，这种效果愈明显。2010年5月管理工程学院运筹学运筹学6二、动态规划解题二、动态规划解题 标号法标号法：最短路径：最短路径：Q A3 B1 C1TQTA1A2A3B1B2B3C1C224374642442514633334阶段阶段1阶段阶段2阶段阶段3阶段阶段40，T3,T4,T4,C17,C26,C111,B1,B28,B18,B111,A3 2010年5月管理工程学院运筹学运筹学7三、动态规划的基本概念。三、动态规划的基本概念。1.阶段阶段(stage)和阶段变量。和阶段变量。把所给问题恰当地划分为把所给问题恰当地划分为若干个相互联
4、系又有若干个相互联系又有区别区别的子问题，称之为多段决策问题的的子问题，称之为多段决策问题的阶段阶段。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学8用以描述阶段的变量叫作用以描述阶段的变量叫作阶段变量阶段变量，一般以，一般以k表示阶段量表示阶段量阶段数阶段数k的编号法有两种：的编号法有两种：(1)(1)顺序编号；顺序编号；(2)(2)逆序编号法。逆序编号法。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学92.状态状态(state)、状态变量和可能状态集、状态
5、变量和可能状态集(1)状态与状态变量。状态与状态变量。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学10(2)动态规划维数动态规划维数。(3)可能状态集：可能状态集：用用S(sk)表示。表示。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学113.3.决策决策(decision)、决策变量和允许决策集合、决策变量和允许决策集合(1)决策决策。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学12(2
6、)决策变量决策变量:xk=xk(sk)决策变量决策变量xk(sk)的的允许决策集允许决策集用用Dk(sk)表示表示,xk(sk)Dk(sk)允许决策集合实际是决策的约束条件。允许决策集合实际是决策的约束条件。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学134.策略和允许策略集合策略和允许策略集合策略策略(Policy)全过程策略全过程策略指具有指具有n个阶段全部过程，个阶段全部过程，简称策简称策略略。表示为。表示为 x1(s1),x2(s1),xn(sn)。k后后部子过程策略部子过程策略,表示为表示为pk(xk)QTA1A2
7、A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学14(2)允许策略集合允许策略集合记作记作P。最优策略最优策略:从允许策略集中，找出的具有最从允许策略集中，找出的具有最优效果的策略。优效果的策略。QTA1A2A3B1B2B3C1C2243746424425146333342010年5月管理工程学院运筹学运筹学155.状态转移方程状态转移方程(状态转移律状态转移律)：多阶段决策过程：多阶段决策过程的发展就是用的发展就是用阶段状态的相继演变阶段状态的相继演变来描述的。来描述的。或简写为或简写为),(1kkkxsTs kkkkkksxsxsTs)
8、(,(12010年5月管理工程学院运筹学运筹学166.指标函数指标函数(1)阶段指标函数阶段指标函数(也称阶段收益也称阶段收益)vk(sk,xk)简记为简记为vk。(2)过程指标函数过程指标函数(指标函数指标函数)。Vk,n(sk,xk,sk+1,xk+1,sn,xn)。简记为。简记为Vk,n。2010年5月管理工程学院运筹学运筹学17动态规划求解的问题的过程指标函数动态规划求解的问题的过程指标函数(指标函数指标函数)，必须具有关于阶段指标的必须具有关于阶段指标的可分离形式可分离形式(和、积或其和、积或其他形式他形式)：),(),(),(),(11111,nnnkkkkkknnkkkknknk
9、xsvxsvxsvxsxsxsVV 表示某种运算，可为加、减、乘、除、开方等。表示某种运算，可为加、减、乘、除、开方等。2010年5月管理工程学院运筹学运筹学18常见有常见有:nkiiiinkxsvV),(,nkiiiinkxsvV),(,和和2010年5月管理工程学院运筹学运筹学19相应的子策略称为相应的子策略称为sk状态下的最优子策略，状态下的最优子策略，记为记为pk*(sk)；而构成该子策赂的各段决策称；而构成该子策赂的各段决策称为该过程上的为该过程上的最优决策最优决策，记为，记为)(,),(),(11nnkkkksxsxsx 7.最优指标函数：最优指标函数：fk(sk)nkVsfnkk
10、k,2,1,opt)(,有有简记为简记为nksxsxsxspnnkkkkkk,2,1),(,),(),()(11nkxxxpnkkk,2,1,12010年5月管理工程学院运筹学运筹学208.概念的关系。状态状态sk阶段阶段kT(sk,xk)决策决策xk(sk)vk(sk,xk)状态状态sk+1阶段阶段k+1T(sk+1,xk+1)决策决策xk+1(sk+1)vk+1(sk+1,xk+1)状态状态sk+22010年5月管理工程学院运筹学运筹学21四、四、最优化原理与动态规划的数学模型最优化原理与动态规划的数学模型 1.1.最优化原理最优化原理 (贝尔曼最优化原理贝尔曼最优化原理)若某一全过程最优
11、策略为：若某一全过程最优策略为：)(),(,),(),()(221111nnkksxsxsxsxsp 则则)(,),(),()(11nnkkkkkksxsxsxsp2010年5月管理工程学院运筹学运筹学222.动态规划的数学模型动态规划的数学模型(逆序法时逆序法时)01,),(opt),(1111,csfnksfxsvsfxsvVnnkkkkksDxkknkiiiinkkkkL(8.3a)(8.3b)2010年5月管理工程学院运筹学运筹学2301,),(opt),(1111,csfnksfxsvsfxsvVnnkkkkksDxkknkiiiinkkkkL(8.3c)(8.3d)或或(8.3b)
12、和和(8.3d)称为边界条件。称为边界条件。2010年5月管理工程学院运筹学运筹学24五、五、动态规划方法的基本步骤动态规划方法的基本步骤1.阶段的划分阶段的划分2.正确地定义状态变量正确地定义状态变量sk2010年5月管理工程学院运筹学运筹学25(1)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。(2)包含到达这个状态前的足够信息，且满足无后包含到达这个状态前的足够信息，且满足无后效性。效性。(3)要满足可知性。要满足可知性。2010年5月管理工程学院运筹学运筹学263.正确地定义决策变量及各阶段的允许决策正确地定义决策变量及各阶段的允许决策集合集合Dk(sk)4.
13、能够正确地写出状态转移方程，至少要能够正确地写出状态转移方程，至少要能正确反映状态转移规律。能正确反映状态转移规律。2010年5月管理工程学院运筹学运筹学275.根据题意根据题意,正确地构造出指标函数，应满正确地构造出指标函数，应满足下列性质：足下列性质：(1)可分性，可分性，。(2)为了进行动态规划计算为了进行动态规划计算满足递推性，满足递推性，nkkkknkVxsvV,1,),(或或nkkkknkVxsvV,1,),(6.确立边界条件写出动态规划函数基本方程。确立边界条件写出动态规划函数基本方程。2010年5月管理工程学院运筹学运筹学28阶段阶段1阶段阶段2阶段阶段k阶段阶段k+1阶段阶段
14、n状态状态S1决决策策x1状态状态S2v1决决策策x2状态状态S3v2决决策策xk状态状态Sk+1vk决决策策xk+1vk+1决决策策xnvn寻求最优解的方向寻求最优解的方向2010年5月管理工程学院运筹学运筹学29六、动态规划的分类六、动态规划的分类离散离散决策过程决策过程连续连续决策过程决策过程根据多阶段决策过程的根据多阶段决策过程的时间参量时间参量根据决策过程的根据决策过程的演变演变确定性确定性决策过程决策过程随机性随机性决策过程决策过程离散确定性离散确定性决策过程决策过程连续连续确定性确定性决策过程决策过程离散随机离散随机性性决策过程决策过程连续随机性连续随机性决策过程决策过程2010
15、年5月管理工程学院运筹学运筹学30七七、学习方法建议、学习方法建议第一步第一步 先看问题，充分理解问题的条件、先看问题，充分理解问题的条件、情况及求解目标。情况及求解目标。第二步第二步 分析针对该动态规划问题的分析针对该动态规划问题的“四大四大要素、一个方程要素、一个方程”。第三步第三步 动手把求解思路整理出来，或者动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。说，把该问题作为习题独立的来做。精品课件精品课件！精品课件精品课件！2010年5月管理工程学院运筹学运筹学33第四步第四步 把自己的求解放到一边，看书中把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。的求解方法，要充分理解教材中的论述。第五步第五步 对照自己的求解，分析成败。对照自己的求解，分析成败。动态规划的四大要素动态规划的四大要素 状态变量及其可能集合状态变量及其可能集合 sk Sk 决策变量及其允许集合决策变量及其允许集合 xk Dk 状态转移方程状态转移方程 sk+1=Tk(sk,xk)阶段收益阶段收益 vk(sk,xk)
