动态规划1课件

第八章第八章 动态规划动态规划动态规划（Dynamic Programming)多阶段决策过程的最优化（简介）动态规划的基本概念和基本原理 动态规划模型的建立与求解动态规划的应用第八章第八章 动态规划动态规划一、动态规划简介动态规划是研究决策过程最优化的一种理论和方法，是解决多阶段决策过程最优化的一种数学方法。“动态”随着“时间”过程的发展而决定各时段的决策，产生一个决策序列。1951年，美国数学家R.Bellman动态规划提出：“最优化原理”-把多阶段过程转化为一系列相互联系的单阶段问题，逐个求解。并成功地解决了生产管理并成功地解决了生产管理 、工程技术等工程技术等方面的许多实际问题方面的许多实际问题.第八章第八章 动态规划动态规划多阶段决策过程多阶段决策过程多阶段决策过程多阶段决策过程是指这样一类特殊的活动是指这样一类特殊的活动是指这样一类特殊的活动是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相过程，他们可以按时间顺序分解成若干相过程，他们可以按时间顺序分解成若干相过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，互联系的阶段，在每个阶段都要做出决策，互联系的阶段，在每个阶段都要做出决策，互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多全部过程的决策是一个决策序列，所以多全部过程的决策是一个决策序列，所以多全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。阶段决策问题也称为序贯决策问题。阶段决策问题也称为序贯决策问题。阶段决策问题也称为序贯决策问题。第八章第八章 动态规划动态规划动态规划模型的分类动态规划模型的分类：以以“时间时间”角度可分成：角度可分成：离散型和连续型。离散型和连续型。从信息确定与否可分成：从信息确定与否可分成：确定型和随机型。确定型和随机型。组合：组合：1、离散确定型；2、离散随机型；3、连续确定型；4、连续随机型；第八章第八章 动态规划动态规划应用最短路问题资源分配问题生产调度问题库存问题排序问题设备更新问题生产过程最优控制问题第八章第八章 动态规划动态规划多阶段决策过程最优化问题举例AD2D1B3B2B1C3C1C2E23877356687463532434 第1阶段 第2阶段 第4阶段 第3阶段 第5阶段1、最短路问题：运输网络如下图，求从A到E的最短路。第八章第八章 动态规划动态规划2、机器负荷分配问题：某种机器，可以在高、低两种负荷下生产。高负荷下生产的产量多，但每生产一个阶段后机器的完好率低；低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内（如制定一个五年计划）的生产，问应该如何决定各阶段中机器的使用，使整个计划期内的总产量最大。(按时间分阶段)第八章第八章 动态规划动态规划3、资源（人力、物力等）分配问题：设某种资源总量为a,用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，才能使生产n种产品的总收入最大？(将每一种活动作为一个阶段)第八章第八章 动态规划动态规划 4、生产与存储问题 企业在生产和经营管理过程中，经常遇到合理安排生产与库存的问题.由于需求是随着时间变化的因素，因此企业为了获得全年最佳经济效益，就要在整个生产过程中逐月或逐季的根据库存和需求决定生产计划,并使总的生产成本费用和库存费用之和最小增加产量成本降低库存费增加一年总费用最低？第八章第八章 动态规划动态规划5、设备更新问题：某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变为故障多，耗油高，维修费用增加，经济效益差。使用时间愈长，处理价值也愈低。另外，每次更新都要付出更新费用。因此，应当如何决定设备的使用年限，使总的效益最佳。第八章第八章 动态规划动态规划二、动态规划的基本概念和基本原理u以书中例1最短路线问题为例，说明动态规划的基本概念。第八章第八章 动态规划动态规划1.阶段（stage)k阶段指作出决策的若干轮次。将所给问题的过程，按将所给问题的过程，按时间或空间特征分解成若干个相互联系的阶段，以时间或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，常用便按次序去求每阶段的解，常用k k表示阶段变量。表示阶段变量。如上例中我们把从我们把从A A到到G G看成一个六阶段问题，看成一个六阶段问题，k（阶段变量）分别等于1，2，3，4，5，62.状态（state)Sk状态表示每个阶段开始所处的自然状况或客观条件，也就是阶段的起点S1=A ,S2=B1,B2 ,S3=C1,C2,C3,C4S4=D1,D2,D3 ,S5=E1,E2,E3 S6=F1,F2第八章第八章 动态规划动态规划动态规划中的状态具有如下性质：动态规划中的状态具有如下性质：当某阶段状态给定以后，在这当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以阶段以后的过程的发展不受这段以前各段状态的影响。即：过程的过前各段状态的影响。即：过程的过去历史只能通过当前状态去影响它去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规就不能作为状态变量来构造动态规划模型。划模型。第八章第八章 动态规划动态规划.决策（Decision)uk(sk)决策指从一个阶段的某个状态演变到下一个阶段的某个状态的选择。uk(sk)表示第k阶段当状态处于sk时的决策变量。k(sk)表示决策集合。1(s1)=u1(A)=B1,B2 ;D2(S2)=u2(B1),u2(B2)=C1,C2,C3;C2,C3,C4D5(S5)=u5(E1),u5(E2),u5(E3)=F1,F2;F1,F2;F1,F2=F1,F2D6(S6)=u6(F1),u6(F2)=G,G=G第八章第八章 动态规划动态规划4.策略(policy)和子策略（sub-policy)策略是指全过程中按顺序排列的各阶段决策组成的集合。记为：p1,n(s1)（如 2C3 D3 E2 F1 G）子策略是指由第k个阶段开始到终止状态为止，其中的每段的决策按顺序排列组成决策函数序列uk(sk),un(sn)称为k子过程策略，简称子策略。（如：C3 D3 E2 F1 G）记为：pk,n(sk)第八章第八章 动态规划动态规划则：5.状态转移方程状态转移方程表示从阶段表示从阶段表示从阶段表示从阶段k k k k到阶段到阶段到阶段到阶段k+1k+1k+1k+1的状态转移规的状态转移规的状态转移规的状态转移规律的表达式律的表达式律的表达式律的表达式。多阶段过程的发展就是用阶段状态的相继演变来描多阶段过程的发展就是用阶段状态的相继演变来描述的。对具有无后效性的多段决策过程，如果给述的。对具有无后效性的多段决策过程，如果给定第定第k k阶段状态变量阶段状态变量s sk的值的值,且确定该段的决策变且确定该段的决策变量量u uk k,则第则第k+1k+1阶段的状态变量阶段的状态变量s sk+1k+1值也随之确定。值也随之确定。即即s sk+1k+1的值是由的值是由s sk k和和u uk k的值来确定的。的值来确定的。第八章第八章 动态规划动态规划系统由从阶段系统由从阶段k k到阶段到阶段k+1k+1的状态转移方程表的状态转移方程表示为：示为：s sk+1k+1=T=Tk k(s(sk k,u,uk k)T Tk k称为状态转移函数。该例中的状态转移方称为状态转移函数。该例中的状态转移方程为：程为：s sk+1k+1=u=uk k(s(sk k)，此指后一阶段的起点，此指后一阶段的起点（状态）是前一阶段的终点（决策）。（状态）是前一阶段的终点（决策）。6.6.指标函数和最优值函数指标函数和最优值函数指标函数指标函数（V Vk,nk,n)是指用来衡量所实现过程优是指用来衡量所实现过程优劣的一种数量指标。分为阶段指标函数和劣的一种数量指标。分为阶段指标函数和过程指标函数。过程指标函数。第八章第八章 动态规划动态规划阶段指标函数是指第阶段指标函数是指第k k阶段，从状态阶段，从状态s sk k出发，采取决策出发，采取决策u uk k时的效益，用时的效益，用d(sd(sk k,u,uk k)表示。表示。而一个而一个n n段决策过程，从段决策过程，从1 1到到n n叫做问题的原过程，对于叫做问题的原过程，对于任意一个给定的任意一个给定的k k（1k n)1k n)，从，从k k段到段到n n段的过程段的过程称为原过程的一个后部子过程。称为原过程的一个后部子过程。指标函数之值既与指标函数之值既与s sk k的状态值有关，又与的状态值有关，又与s sk k以后所选取以后所选取的策略有关，它是两者的函数值，记为：的策略有关，它是两者的函数值，记为：或记为表示第k阶段状态为 且采取策略 时，后部子过程的指标函数第八章第八章 动态规划动态规划对于能构成动态规划模型的指标函数，应具有可分离性，并满足递推关系，即Vk,n可且示为sk,uk,Vk+1,n的函数。常见的指标函数形式：（）过程和它的任一子过程的指标是它所包含的各阶段的指标的和。第八章第八章 动态规划动态规划（）过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。第八章第八章 动态规划动态规划最优值函数是指对某一确定状态选取最优策略后得到的最优函数值，是对应某一最优子策略的某种效益度量（产量、成本、距离等）。对应于从sk出发的最优子策略的效益值可记为fk(sk),于是有：在不同的问题中，指标函数的含义不同（距离、利润、成本、产量、资源消耗等），如，在最短路线问题中，指标函数vk,n表示在第k 阶段由点sk至终点的距离。第八章第八章 动态规划动态规划dk(sk,uk)=vk(sk,uk)表示在第k阶段由点sk到点sk+1=uk(sk)的距离。如d(,)=，表示在第阶段中由点到点的距离为。fk(sk)表示从第k阶段点到终点的最短距离，如f4(D1)就表示从第阶段中的点到点的最短距离,f4(D1)=7。第八章第八章 动态规划动态规划动态规划的基本概念小结阶段状态、状态变量 、状态空间决策 、允许决策集合 策略状态转移（方程）指标函数无后效性即未来与过去无关第八章第八章 动态规划动态规划指标函数表示初始状态为 且采取策略 时，原（全）过程的指标函数表示第k阶段状态为 且采取策略 时，后部子过程的指标函数表示第k阶段状态为 且采取最优策略 到终止时的最佳效益值最优值函数第八章第八章 动态规划动态规划u 动态规划的基本思想和基本方程以最短线路问题说明动态规划问题的基本思想。最短线路的特性：如果从起点经过点和点而到达终点是一条最短路线，则由点出发经过点到达终点的这条子路线也必是最短路线。因此，就可根据这一特性从过程最后一阶段开始，由逆序解法后向前逐步递推的方法，求出各点到点的最短路线，最终求得由点到点的最短路线动态规划的基本思想。第八章第八章 动态规划动态规划最短路的重要性质：AHPA到G的最短路P到G的最短路G第八章第八章 动态规划动态规划用逆序递推法求 例1的最短路第八章第八章 动态规划动态规划第一步：从阶段k=6开始，状态变量s6有两种状态F1,F2,到点的距离分别为4,3,即f6(F1)=4,f6(F2)=3.第二步：k=5,状态变量s5有三种状态，即1,E2,E3，经过一个中途阶段到达终点，该中途阶段双有两种选择：（）至；（）至。则从至有两条路线，取其最短的，即：第八章第八章 动态规划动态规划则由E1至终点的最短距离为，其最短路线为E1 F1 G,相应的决策为u5(E1)=F1.同理：则由E至终点的最短距离为，其最短路线为E F G,相应的决策为u5(E)=F.由3出发到终点有：第八章第八章 动态规划动态规划则由E至终点的最短距离为，其最短路线为E F G,相应的决策为u5(E)=F第三步：k=4，具有三个初始状态D1,D2,D3,需经过两个中途阶段才能到达终点。由于第阶段各点，到终点的最短距离已知，所以若求从到终点的最短距离，只需以此为基础，分别加上到，的一段距离即可。路径为：E F G,决策：u4(D1)=E2第八章第八章 动态规划动态规划同理有：第四步：k=3,同理有：第八章第八章 动态规划动态规划第五步：k=2第八章第八章 动态规划动态规划第六步：当k=1，只有一个状态点（出发点），则于是得到从起点到终点的最短距离为18。由最优决策函数序列 uk,即：组成一个最优策略，相应的最短路线为：第八章第八章 动态规划动态规划在求解上例的各个阶段，都利用了第k 个阶段与第k+1个阶段如下的递推关系：（）式这种递推关系称为动态规划的基本方程，（）式称为边界条件。动态规划基本方程第八章第八章 动态规划动态规划一般形式：基本方程：边界条件：第八章第八章 动态规划动态规划 现将动态规划方法的基本思想总结如下：（）将多阶段决策过程划分为阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而将一个大问题化成一簇同类型的子问题，然后逐个求解。（）求解时从边界条件开始，逆过程方向行进，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。第八章第八章 动态规划动态规划贝尔曼贝尔曼(BallmanBallman)最优化原理最优化原理 作为整个过程的最优策略具有作为整个过程的最优策略具有这样的性质，即无论过去的状态和这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成状态而言，余下的诸决策必须构成最优策略最优策略。这就是说，不管引导到。这就是说，不管引导到这个现时状态的头一个状态和决策这个现时状态的头一个状态和决策是什么，所有的未来决策应是最优是什么，所有的未来决策应是最优的。的。第八章第八章 动态规划动态规划标号法：（上述计算过程可）直接在图上作业的方法。第八章第八章 动态规划动态规划上图中每节点处上方方格内的数，表示该点到终点G的最短距离。用直线连接的点表示该点到终点G的最短路线。未用直线连接的点说明它不是该点到终点G的最短路线，故舍去。图中红线表示由始点A到终点G的最短路线。第八章第八章 动态规划动态规划顺序解法：41写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal