动态规划PPT教学课件..ppt

动态规划第三章 动态规划 3.1 动态规划的基本概念和方法基本概念与名词解释最优化原理与动态规划的基本方法 3.2 动态规划模型的建立与求解步骤 建立动态规划模型的基本要求动态规划的求解步骤 3.3 动态规划的应用举例定价问题资源分配问题生产存储问题第一节 动态规划的基本概念与方法1 动态规划的基本概念一、动态决策问题： 决策过程具有阶段性和时序性(与时间有关)的决策问题即决策过程可划分为明显的阶段二、什么叫动态规划(D.P. Dynamic Program)： 多阶段决策问题最优化的一种方法 广泛应用于工业技术、生产管理、企业管理、经济、军事等领域三、动态规划(D.P.)的起源： 1951年,美国数学家R.Bellman(贝尔曼)等人提出最优化原理，从而建立动态规划，他的名著动态规划于1957年出版四、动态决策问题分类：1、按数据给出的形式分为： 离散型动态决策问题 连续型动态决策问题2、按决策过程演变的性质分为： 确定型动态决策问题 随机型动态决策问题名词解释 例3-1 某公司欲将一批货物从城市A运到城市E去，如图所示，走哪条路线最好？1、阶段(stage)k： 把所给问题的过程，恰当地分成若干个相互联系的阶段。

描述阶段的变量称为阶段变量，常用k表示k = 1、2、3、42、状态(state)Sk：状态表示每个阶段开始所处的自然状态，即是每一阶段的出发位置阶段的起点通常一个阶段有多个状态记为Sk S1=A，S2=B1,B2,B3，S3=C1,C2,C3， S4=D1,D23、决策(decision) uk(sk) ：从一个阶段某状态演变到下一个阶段某状态的选择常用uk(sk) 表示第k阶段当状态处于sk时的决策变量决策集用Dn(Sk)表示就是阶段的终点 D1(S1)=u1(A)=B1,B2,B3= S2， D2(S2)=U2(B1),U2(B2),U2(B3)=C1,C2;C1,C2,C3 ;C2,C3 =C1,C2,C3=S3， D3(S3)=U3(C1),U3(C2),U3(C3)=D1,D2;D1,D2,D3; D1,D2,D3=D1,D2,D3=S4， D4(S4)=U4(D1),U4(D2),U4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5， D5(S5)=X5(E1),X5(E2)=F;F=F4、策略(policy)：策略是一个按顺序排列的决策组成的集合即是全过程中各个阶段的决策Un组成的有序总体Un。

如 A B2 C1 D1 E 5、子策略(sub-policy) ：由过程的第k阶段开始到终止状态为止的过程，即是剩下的M个阶段构成M子过程，相应的决策系列叫M子策略 如 C1 D1 E6、状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过程，如果给定第k阶段的状态Sk ，本阶段决策为Uk( Sk) ，则第k+1阶段的状态Sk+1也就完全确定，它们的关系可表示为Sk+1Tk(Sk ,Uk),它描述了由k阶段到k+1阶段的状态转移规律，称为状态转移方程即是前一阶段的终点(决策)是后一阶段的起点(状态) 如 Uk( Sk) Sk+1 7、指标函数：用来衡量各个阶段优劣的数量指标，它是定义在全过程和所有后部子过程上确定的数量函数记为Vk,n(sk,Uk)如上例中，用dk(sk,Uk)表示距离d2(B3,C2)=8, d3(C2,D2)=2 等8、目标函数：策略的数量指标值，记为 Z=optv1(s1,u1)* vn(sn,un)其中：opt为max或min，*为运算符号如上例中，Z=mind1(s1,u1)+dn(sn,un)=mind1+d2+ dn最优化原理 一、R.Bellman最优化原理： 作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策形成状态而言，余下的诸决策必构成最优策略。

即：若M是从A到B最优路线上的任一点，则从M到B的路线也是最优路线A MB二、指标递推方程： fn*(Sn) = opt vn(sn,un) * vn(sn,un) xnDn(Sn) 如上例：fn*(Sn) = min vn(sn,un)+ fn+1*(Sn+1) ， n=3、2、1 xnDn(Sn) f4*(S4) = min v4(s4,u4) x4D4(S4) 三、求解过程： 用反向嵌套递推法：从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优， 形成最优策略，获得最优策略指标值第二节 动态规划模型的建立与求解步骤一、建立动态规划模型的基本要求 将问题划分成若干阶段有的问题阶段性很明显，有的则不明显，需要分析后人为假设 确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致 状态变量应当满足无后效性要求 明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致二、动态规划的求解步骤 正确划分阶段 确定状态变量和决策变量，并给出状态变量和决策变量的可行集合 确定求解的递推顺序，给出状态转移方程 确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。

递推求解 与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线例2：求图中A到F的最短路线及最短路线值AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、阶段(stage)n： n = 1、2、3、4、52、状态(state)Sn： S1=A，S2=B1,B2,B3，S3=C1,C2,C3，S4=D1,D2,D3，S5=E1,E23、决策(decision)un：决策集Dn(Sn) D1(S1)=u1(A)=B1,B2,B3= S2， D2(S2)=u2(B1),u2(B2),u2(B3)=C1,C2;C1,C2,C3 ;C2,C3 =C1,C2,C3=S3， D3(S3)=u3(C1),u3(C2),u3(C3) =D1,D2;D1,D2,D3; D1,D2,D3=D1,D2,D3=S4， D4(S4)=u4(D1),u4(D2),u4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5， D5(S5)=u5(E1),u5(E2)=F;F=F。

AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144、状态转移方程：un = Sn+15、指标函数(距离)：dn(sn,un) d2(B3,C2)=1, d3(C2,D3)=6 等6、指标递推方程：fn*(Sn) = min rn(sn,un)+ fn+1*(Sn+1) ， n=4、3、2、1 UnDn(Sn) f5*(S5) = min V5(s5,u5) X5D5(S5)AB1B2B3C1C2C3D1D2D3E1E2F3549543517158464422269751411F22F4 + 1 = 52 + 2 = 44 E26 + 1 = 79 + 2 = 117E17 + 1 = 85 + 2 = 77E2AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141 + 4 = 55 + 7 = 12 / / / 5D18+ 4 = 124 + 7 = 116 + 7 = 1311D24+ 4 = 84+ 7 = 112+ 7 = 98D19+ 5 = 145+ 11 = 16 / / /14C14+ 5 = 93+ 11 = 145+ 8 = 139C1 / / /1+ 11 = 127+ 8 = 15 12C2AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143+ 14 = 175+ 9 = 144+ 12 = 16 14B2最短路线值为：f1*(s1) = 14最短路线求解如下：11F22F4 + 1 = 52 + 2 = 44 E26 + 1 = 79 + 2 = 117E17 + 1 = 85 + 2 = 77E21 + 4 = 55 + 7 = 12 / / / 5D18+ 4 = 124 + 7 = 116 + 7 = 1311D24+ 4 = 84+ 7 = 112+ 7 = 98D19+ 5 = 145+ 11 = 16 / / /14C14+ 5 = 93+ 11 = 145+ 8 = 139C1 / / /1+ 11 = 127+ 8 = 15 12C23+ 14 = 175+ 9 = 144+ 12 = 16 14B2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即： A B2 C1 D1 E2 F 第三节 动态规划的应用举例 定价问题 资源分配问题 生产存储问题一、定价问题 某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。

表3-2 每年预计利润额单价第一年 第二年 第三年 第四年 第五年5元6元7元8元1012141612131415151616152020181425241814建立数学模型 按年划分阶段，k=1,2,.,5 每阶段的状态变量为本年(上一年已确定)的价格，状态变量的可行集合Sk=(5,6,7,8) 决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是： 采用逆序算法，因此状态转移方程是 最优值函数递推方程为进行各阶段的计算 采用逆序法，设 当k=5时，S5=(5,6,7,8)，由表3-1得到 当k=4时， S4=(5,6,7,8)，由递推方程 得继续求解 同理得其它各阶段的最优解反推得最优路线 按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量即从第一年单价应为8元开始，向后推算 得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元 最大利润值为92万元也可用决策图求解二、资源分配问题 某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂得设备后可产生如表3-2所示的利润，应怎么分配设备可使公司总利润最大？ 工厂设备数甲乙丙丁012345067101215037912130510111111046111212建立数学模型 按工厂次序划分阶段，k=1，2，3，4 状态变量为各阶段可用于分配的设备总台数 决策变量是分配给第k工厂的设备数 采用逆序算法，状态转移方程 最优值函数递推方程第4阶段的最优解 当k=4时，S4=(0,1,2,3,4,5)012345012345046111212046111212012345第3阶段的最优解 当k=3时，S3=(0,1,2)000000010105404551201205106406910102第3阶段的最优解（续） 当k=3时，S3=3301230510111164011111411142第3阶段的最优解（续） 当k=3时，S3=44012340510111112116401216161511161，2第3阶段的最优解（续） 当k=3时，S3=550123450510111111121211640121721171511212第2阶段的最优解 当k=2时，S2=(0,1,2)000000010103505350201203710501087100第2阶段的最优解（续）当k=2时，S2=33012303791410501413129140第2阶段的最优解（续）当k=2时，S2=4401234037912161410501617171412171，2第2阶段的最优解（续）当k=2时，S2=55012345037912132116141050211921191715210，2第1阶段的最。