第5章动态规划优秀PPT.ppt

第5章动态规划现在学习的是第1页，共90页什么是动态规划o动态规划是解决多阶段决策过程最优化的动态规划是解决多阶段决策过程最优化的一种方法。一种方法。o19511951年美国数学家贝尔曼（年美国数学家贝尔曼（R RBellmanBellman）等人提出了解决这类问题的等人提出了解决这类问题的“最优化原理最优化原理”，并研究了许多实际问题。，并研究了许多实际问题。现在学习的是第2页，共90页o在工程技术、企业管理、工农业生产及军在工程技术、企业管理、工农业生产及军事部门中都有广泛应用：解决最优路径问事部门中都有广泛应用：解决最优路径问题、资源分配问题、生产调度问题、库存题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等。题、生产过程最优控制问题等等。o动态规划模型分类：离散确定型、离散随动态规划模型分类：离散确定型、离散随机型、连续确定型、连续随机型。机型、连续确定型、连续随机型。什么是动态规划现在学习的是第3页，共90页5.15.1多阶段决策问题的最优化多阶段决策问题的最优化 o多阶段决策问题，是指可将过程划分为多阶段决策问题，是指可将过程划分为若干个互相联系的阶段，在它的每一个若干个互相联系的阶段，在它的每一个阶段都需要作出决策，并且一个阶段的阶段都需要作出决策，并且一个阶段的决策确定以后，常影响下一阶段的决策，决策确定以后，常影响下一阶段的决策，从而影响整个过程的活动。从而影响整个过程的活动。o各个阶段所确定的决策就构成一个决策各个阶段所确定的决策就构成一个决策序列，通常称为策略。序列，通常称为策略。现在学习的是第4页，共90页o由于每一个阶段可供选择的决策往往不只由于每一个阶段可供选择的决策往往不只一个，因而就有许多策略可供选择。一个，因而就有许多策略可供选择。o多阶段的决策问题，就是要在允许选择的多阶段的决策问题，就是要在允许选择的那些策略中，选择一个最优策略，使在预那些策略中，选择一个最优策略，使在预定的标准下达到最好的效果。定的标准下达到最好的效果。5.15.1多阶段决策问题的最优化多阶段决策问题的最优化 现在学习的是第5页，共90页5.15.1多阶段决策问题的最优化多阶段决策问题的最优化o阶段往往可以用时段来表示。阶段往往可以用时段来表示。o在各个时间阶段，采用不同的决策是随在各个时间阶段，采用不同的决策是随时间而变动的，这就有时间而变动的，这就有“动态动态”的含义。的含义。o它是在时间的推移过程中要在每一段选它是在时间的推移过程中要在每一段选择最恰当的决策，以期整体上达到最优。择最恰当的决策，以期整体上达到最优。现在学习的是第6页，共90页o动态规划在一定条件下也可以解决一些与动态规划在一定条件下也可以解决一些与时间无关的问题，只要人为地引进时间无关的问题，只要人为地引进 时段时段 因素以后，这些问题就可变为一个多阶段因素以后，这些问题就可变为一个多阶段决策问题。决策问题。5.15.1多阶段决策问题的最优化多阶段决策问题的最优化现在学习的是第7页，共90页5.15.1多阶段决策问题的最优化多阶段决策问题的最优化o例例1 1 生产与存贮问题生产与存贮问题o 某工厂每月需供应市场一定数量的产某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月品，并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最件下，使一年的生产与存贮费用之和最小。小。o全年分为全年分为1212个阶段逐次决策。个阶段逐次决策。现在学习的是第8页，共90页5.15.1多阶段决策问题的最优化多阶段决策问题的最优化o例例2 2投资决策问题投资决策问题o某公司现有资金某公司现有资金Q Q万元，在今后万元，在今后5 5年内考年内考虑给虑给A A，B B，C C，D 4D 4个项目投资，这些项个项目投资，这些项目投资的回收期限、回报率均不相同，目投资的回收期限、回报率均不相同，问该公司应如何确定这些项目每年的投问该公司应如何确定这些项目每年的投资额，使到第资额，使到第5 5年末拥有资金的本利总额年末拥有资金的本利总额最大。最大。o这是一个这是一个5 5阶段决策问题。阶段决策问题。现在学习的是第9页，共90页5.15.1多阶段决策问题的最优化多阶段决策问题的最优化o例例3 3设备更新问题设备更新问题o 企业在使用设备时都要考虑设备的更企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大越多，但购买新设备则要一次性支出较大的费用；现某企业要决定一台设备未来的费用；现某企业要决定一台设备未来8 8年的更新计划，已预测了第年的更新计划，已预测了第j j年购买设备年购买设备的价格为的价格为KjKj，设，设GjGj为设备经过为设备经过j j年后的残年后的残值，值，CjCj为设备连续使用为设备连续使用j-1j-1年后在第年后在第j j年的年的维修费维修费(j(j1 1，2 2，8)8)，问应在哪些年，问应在哪些年更新设备可使总费用最小。更新设备可使总费用最小。o这是一个这是一个8 8阶段决策问题阶段决策问题现在学习的是第10页，共90页o例例4 4：最短路线问题：最短路线问题5.15.1多阶段决策问题的最优化多阶段决策问题的最优化图图5-3现在学习的是第11页，共90页5.25.2动态规划的基本概念和基本原理动态规划的基本概念和基本原理5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念 使用动态规划方法解决多阶段决策使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划问题，首先要将实际问题写成动态规划模型，此时要用到以下概念：模型，此时要用到以下概念：(1)(1)阶段；阶段；(2)(2)状态；状态；(3)(3)决策和策略；决策和策略；(4)(4)状态转移；状态转移；(5)(5)指标函数。指标函数。现在学习的是第12页，共90页o例例4 4最短路线问题最短路线问题 5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念图图53如图如图5-35-3所示，给定所示，给定一个线路网络图，要一个线路网络图，要从从A A地向地向F F地铺设一条地铺设一条输油管道，各点间连输油管道，各点间连线上的数字表示距离，线上的数字表示距离，问应选择什么路线，问应选择什么路线，可使总距离最短。可使总距离最短。现在学习的是第13页，共90页o阶段和阶段变量：阶段和阶段变量：n将所给问题的过程，按时间或空间特征分解成将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段若干互相联系的阶段，以便按次序去求每阶段的解，常用字母的解，常用字母k k表示表示阶段变量阶段变量。n例例4 4中，从中，从A A到到F,F,可以分成从可以分成从A A到到B(BB(B有两种选有两种选择择)，从，从B B到到C(CC(C有四种选择有四种选择)，从，从C C到到D(DD(D有三有三种选择种选择)，从，从D D到到E(EE(E有两种选择有两种选择)，再从，再从E E到到F,F,五个阶段。五个阶段。k k1 1，2 2，3 3，4 4，5 5。5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第14页，共90页状态和状态变量：状态和状态变量：-状态表示某一阶段初所处的位置或状况。状态表示某一阶段初所处的位置或状况。-通常一个阶段包含若干个状态。通常一个阶段包含若干个状态。描述状态的变量称为状态变量，常用描述状态的变量称为状态变量，常用sksk表示第表示第k k阶段阶段的某一状态，状态变量的某一状态，状态变量sksk的集合称为状态集合，用的集合称为状态集合，用SkSk表示。表示。5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第15页，共90页在例在例4 4中，第一阶段状态为中，第一阶段状态为A,A,第二阶段状态：第二阶段状态：B1B1，B2B2，或，或s1=As1=A，s21=B1 s21=B1，s22=B2s22=B2。状态变量的集合状态变量的集合:S1=AS1=AS2 S2 B1 B1，B2 B2 S3 S3 C1 C1，C2C2，C3 C3，C4 C4 S4 S4 D1 D1，D2D2，D3 D3 S5 S5 E1 E1，E2 E2 5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第16页，共90页动态规划中的状态应具有如下性质：动态规划中的状态应具有如下性质：1.1.代表性。能够反映过程的演变特征。代表性。能够反映过程的演变特征。2.2.可知性。能够通过某种方式，直接或间接地可知性。能够通过某种方式，直接或间接地确定下来。确定下来。3.3.无后效性。所谓无后效性，是指某阶段的状无后效性。所谓无后效性，是指某阶段的状态，只对该阶段状态以后过程的演变起作用，态，只对该阶段状态以后过程的演变起作用，而不受以前各阶段状态的影响。而不受以前各阶段状态的影响。n这就是说，过程的过去历史只能通过当前的这就是说，过程的过去历史只能通过当前的状态去影响它的未来的发展，当前的状态就状态去影响它的未来的发展，当前的状态就是未来过程的初始状态是未来过程的初始状态 5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第17页，共90页5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第18页，共90页n要正确地定义状态变量，就必须对问题具有深要正确地定义状态变量，就必须对问题具有深入的观察和理解，可以从下面两个方面来考虑：入的观察和理解，可以从下面两个方面来考虑：1)1)把阶段连系在一起的因素是什么把阶段连系在一起的因素是什么?2)2)需要用什么信息来进行当前的决策，而不用检查需要用什么信息来进行当前的决策，而不用检查以前阶段所作决策的可行性。以前阶段所作决策的可行性。5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第19页，共90页决策和决策变量决策和决策变量:决策就是某阶段状态给定以后，从该状态演变到决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。下一阶段某状态的选择。描述决策的变量，称为决策变量。描述决策的变量，称为决策变量。常用常用u uk k(s(sk k)表示第表示第k k阶段当状态为阶段当状态为s sk k时的决策变量。时的决策变量。在实际问题中，决策变量的取值往往限制在一定在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，常用范围内，我们称此范围为允许决策集合，常用D Dk k(s(sk k)表示第表示第k k阶段从状态阶段从状态s sk k出发的允许决策集合，出发的允许决策集合，显然有：显然有：u uk k(s(sk k)D Dk k(s(sk k)。5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第20页，共90页在例在例4中，从第二阶段的状态集合为中，从第二阶段的状态集合为S2=B1,B2，从，从B1出出发，允许决策集合为：发，允许决策集合为：D2(B1)C1，C2，C3如我们决定选择如我们决定选择C3：，则可表为：，则可表为：u2(B1)C35.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第21页，共90页策略和最优策略策略和最优策略:由第由第1阶段开始到最后一个阶段终点为止的过程，阶段开始到最后一个阶段终点为止的过程，称为问题的全过程。由每阶段的决策称为问题的全过程。由每阶段的决策uk(sk)组成的组成的决策序列就构成一个全过程策略，简称为策略，记决策序列就构成一个全过程策略，简称为策略，记为为P1,n：P1,n(s1)=u1(s1),u2(s2),un(sn)由过程的第由过程的第k阶段开始到终点为止的过程，称为原阶段开始到终点为止的过程，称为原过程的后部子过程过程的后部子过程(或称为或称为k子过程子过程)。其决策函数。其决策函数序列称为序列称为k子过程策略，简称子策略，记为子过程策略，简称子策略，记为Pk,n 即：即：Pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第22页，共90页允许策略集合用允许策略集合用P表示。从允许策略集合中找出达到最优效表示。从允许策略集合中找出达到最优效果的策略称为最优策略。果的策略称为最优策略。在上图中，用在上图中，用P1,5=A，B1，C2，D2，E1，F是一个策略，是一个策略，P3,5=C2，D2，E1，F 是是P1,5的的一个子策略。一个子策略。5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第23页，共90页状态转移方程状态转移方程 动态规划中本阶段的状态往往是上一阶段状态和动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。如果给定了第上一阶段的决策结果。如果给定了第k段的状态段的状态sk，则第则第k+1段的状态段的状态sk+1 也就完全确定。也就完全确定。状态转移方程：由状态转移方程：由k段到段到k十十l段的状态转移规律段的状态转移规律,sk+1=Tk(sk,uk)。例例4中，状态转移方程为：中，状态转移方程为：sk+1=uk(sk)5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第24页，共90页指标函数及最优指标函数指标函数及最优指标函数在多阶段决策过程最优化问题中，用来衡量所在多阶段决策过程最优化问题中，用来衡量所实现过程的优劣的数量指标，称为指标函数；实现过程的优劣的数量指标，称为指标函数；它是一个定义在全过程和所有后部子过程上的它是一个定义在全过程和所有后部子过程上的确定的数量函数，常用确定的数量函数，常用Vk,n表示即：表示即：Vk,n=Vk,n（sk,sk+1,sn）指标函数指标函数Vk,n的最优值，称为相应的最优指标的最优值，称为相应的最优指标函数，记为函数，记为fk(sk)。5.2.1 5.2.1 动态规划的基本概念动态规划的基本概念现在学习的是第25页，共90页5.25.2动态规划的基本概念和基本原理动态规划的基本概念和基本原理5.1.2.5.1.2.动态规划的基本原理动态规划的基本原理 BellmanBellman最优化原理最优化原理作为整个过程的最优策略具有这作为整个过程的最优策略具有这样的性质：即无论过去的状态和决样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最态而言，余下的诸决策必须构成最优策略。优策略。现在学习的是第26页，共90页结合例结合例4 4最短最短路线问题介绍动态规路线问题介绍动态规划的基本思想。从过划的基本思想。从过程的最后一段开始，程的最后一段开始，用逆序递推方法求解，用逆序递推方法求解，逐步求各段各点到终逐步求各段各点到终点厂的最短路线，最点厂的最短路线，最后求得后求得A A点到点到F F点的最点的最短路线。短路线。5.1.2.动态规划的基本原理动态规划的基本原理现在学习的是第27页，共90页o 第一步，从第一步，从s5开始，状态变量开始，状态变量s5可取两种可取两种状态状态E1，E2，它们，它们到到F点的路长分别为点的路长分别为第二步，第二步，k4，状态变量，状态变量s5可取三个值可取三个值D1，D2，D3，这是经过，这是经过一个中途点到达终点一个中途点到达终点F的两级决策问题，从的两级决策问题，从D1到到F只有两条路只有两条路线，需加以比较，取其中最短的，即：线，需加以比较，取其中最短的，即：现在学习的是第28页，共90页现在学习的是第29页，共90页图7-2现在学习的是第30页，共90页动态规划方法的基本思想：动态规划方法的基本思想：(1)(1)将多阶段决策过程将多阶段决策过程划分阶段划分阶段，恰当地选取，恰当地选取状态变量、状态变量、决策变量决策变量及定义及定义最优指标函数最优指标函数，从而把问题化成一族同，从而把问题化成一族同类型的子问题，然后逐个求解。类型的子问题，然后逐个求解。(2)(2)求解时从求解时从边界条件边界条件开始，逆开始，逆(或顺或顺)过程行进方向，逐段过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，出的子问题的最优结果，最后一个子问题的最优解，就最后一个子问题的最优解，就是整个问题的最优解是整个问题的最优解。(3)(3)动态规划方法是既把当前一段动态规划方法是既把当前一段与未来各段分开与未来各段分开，又把当，又把当前效益前效益和未来效益结合和未来效益结合起来考虑的一种最优化方法，因起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。优选择一般是不同的。5.1.2.动态规划的基本原理动态规划的基本原理现在学习的是第31页，共90页o动态规划的基本方程是递推逐段求解的根据，一般动态规划的基本方程是递推逐段求解的根据，一般的动态规划基本方程可以表为：的动态规划基本方程可以表为：Bellman Bellman最优化原理：作为整个过程的最优策略具有这样的最优化原理：作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。的状态而言，余下的诸决策必须构成最优策略。5.1.2.动态规划的基本原理动态规划的基本原理现在学习的是第32页，共90页o动态规划的基本解题步骤如下：动态规划的基本解题步骤如下：第一步：划分阶段；第一步：划分阶段；第二步：确定状态变量及其取值范围；第二步：确定状态变量及其取值范围；1)1)代表性。代表性。2)2)可知性。可知性。3)3)无后效性。无后效性。第三步：确定决策变量及其取值范围；第三步：确定决策变量及其取值范围；第四步：建立状态转移方程；第四步：建立状态转移方程；第五步：确定指标函数第五步：确定指标函数第六步：建立动态规划基本方程，然后从第六步：建立动态规划基本方程，然后从k kn n开始，逐开始，逐段向前推移，直到求出段向前推移，直到求出f f1 1(s(s1 1)时，就得到了整个过程的时，就得到了整个过程的最优解，包括最优策略和相应的最优指标函数值。最优解，包括最优策略和相应的最优指标函数值。5.1.2.动态规划的基本原理动态规划的基本原理现在学习的是第33页，共90页5.35.3动态规划模型的建立与求解动态规划模型的建立与求解o资源分配问题资源分配问题 例例5 5 某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目j(jj(j1 1，2 2，3)3)的投资额为的投资额为x xi i时，其收益分别为时，其收益分别为g g1 1(x(x1 1)4x4x1 1，g g2 2(x(x2 2)9x9x2 2，g g3 3(x(x3 3)2x2x3 32 2，问应如何分配投资数，问应如何分配投资数额才能使总收益最大额才能使总收益最大?5.3.1动态规划模型的建立动态规划模型的建立现在学习的是第34页，共90页 这是一个与时间无明显关系的静态最优化问题，可列出其这是一个与时间无明显关系的静态最优化问题，可列出其静态模型：静态模型：求求x x1 1，x x2 2，x x2 2：，使：，使5.3.1动态规划模型的建立动态规划模型的建立现在学习的是第35页，共90页o用动态规划方法求解：用动态规划方法求解：n阶段阶段k：k=1,2,3n状态变量状态变量s sk k：第：第k段可以投资于第段可以投资于第k项到第项到第3个项目个项目的资金数。的资金数。n决策变量决策变量x xk k：决定给第：决定给第k个项目投资的资金数。个项目投资的资金数。n状态转移方程：状态转移方程：s sk+1k+1 s sk k-x xk k。n指标函数：指标函数：n最优指标函数人最优指标函数人f fk k(s sk k)：当可投资金数为：当可投资金数为s sk k时，投时，投资第资第k3项所得的最大收益数项所得的最大收益数n基本方程：基本方程：5.3.1动态规划模型的建立动态规划模型的建立现在学习的是第36页，共90页 例例6 船舶总公司拟将船舶总公司拟将5万元资金投放到下属万元资金投放到下属A、B、C三个船三个船厂，各船厂在获得资金后的收益如表厂，各船厂在获得资金后的收益如表5-1所示。试用动态所示。试用动态规划方法求使总收益最大的投资分配方案。规划方法求使总收益最大的投资分配方案。012345A035789B046899C0137910投投资资额额收益收益船厂船厂表表5-15.3.1动态规划模型的建立动态规划模型的建立现在学习的是第37页，共90页解：解：阶段阶段k：k=1,2,3n状态变量状态变量s sk k：第：第k段可以投资于第段可以投资于第k项到第项到第3个项目个项目的资金数。的资金数。n决策变量决策变量xk:为第为第k阶段分配给第阶段分配给第k个船厂的资金数。显个船厂的资金数。显然然:状态转移方程：状态转移方程：5.3.1动态规划模型的建立动态规划模型的建立现在学习的是第38页，共90页指标函数：阶段指标函数指标函数：阶段指标函数g gk k(s sk k)如表如表5-1所示所示最优指标函数人最优指标函数人f fk k(s sk k)：当可投资金数为：当可投资金数为s sk k时，投资第时，投资第k3项所得的最大收益数项所得的最大收益数基本方程：基本方程：用逆序法由最后一阶段向前推进计算。用逆序法由最后一阶段向前推进计算。5.3.1动态规划模型的建立动态规划模型的建立现在学习的是第39页，共90页K=3时：时：阶段阶段k=300000111012330237703499045101005现在学习的是第40页，共90页阶段阶段k=20000001000+1=1f3(1)=1144+0=4f3(0)=012000+3=3f3(2)=3145f3(1)=1266f3(0)=023007f3(3)=7147f3(2)=3267f3(1)=1388f3(0)=034009f3(4)=91411f3(3)=71269f3(2)=3389f3(1)=1499f3(0)=050010f3(5)=101413f3(4)=912613f3(3)=723811f3(2)=34910f3(1)=1599f3(0)=0现在学习的是第41页，共90页阶段阶段f1（x1）k=1500131313141112513837136481245990最优策略最优策略(对船厂对船厂A、B、C的资金分配序列的资金分配序列)是：是：分给船厂分给船厂A 1万元，分给船厂万元，分给船厂B 1万元，分给船厂万元，分给船厂C 3万元最大收益是万元最大收益是14万元。万元。由上述计算结果可知由上述计算结果可知:最大收益是：最大收益是：现在学习的是第42页，共90页o例例4 4的顺序解法：的顺序解法：5.3.2.逆序法与顺序法逆序法与顺序法现在学习的是第43页，共90页o从从k k0 0开始，开始，是边界条件是边界条件ok k1 1时，时，定义有：定义有：ok k2 2时，时，定义有：定义有：现在学习的是第44页，共90页 类似有：类似有：现在学习的是第45页，共90页2.2.动态规划模型的求解：动态规划模型的求解：1)1)离散变量的分段穷举算法离散变量的分段穷举算法 动态规划模型中的动态规划模型中的状态变量状态变量与与决策变量决策变量若被限定只能若被限定只能取离散值，则可采用分段穷举法。用分段穷举法求最优指取离散值，则可采用分段穷举法。用分段穷举法求最优指标函数值时，要正确确定标函数值时，要正确确定每段状态变量取值范围每段状态变量取值范围及允许及允许决决策集合策集合的范围。的范围。2)2)连续变量的解法连续变量的解法 当动态规划模型中当动态规划模型中状态变量状态变量与与决策变量决策变量为连续变量，为连续变量，就要根据方程的具体情况灵活选取求解方法，如经典解析就要根据方程的具体情况灵活选取求解方法，如经典解析方法、线性规划方法、非线性规划法或其它数值计算方法方法、线性规划方法、非线性规划法或其它数值计算方法等。可用逆序解法和顺序解法来求解。等。可用逆序解法和顺序解法来求解。3)3)连续变量的离散化解法连续变量的离散化解法 5.3.2.逆序法与顺序法逆序法与顺序法现在学习的是第46页，共90页解：解：阶段阶段k=1,2,3;状态变量状态变量s sk k 为第为第k段可以投资于第段可以投资于第k项到第项到第3个项目的资金个项目的资金数；数；决策变量决策变量x xk k 决定给第决定给第k个项目投资的资金数；个项目投资的资金数；状态转移方程状态转移方程：s sk+1k+1 s sk k-x xk k；最优指标函数最优指标函数f fk k(s sk k)表示当可投资金数为表示当可投资金数为s sk k时，投资第时，投资第k到到第第3项所得的最大收益数；项所得的最大收益数；f f1 1(s s1 1)为所求的总收益；为所求的总收益；递推方程递推方程：例例5 5 某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目j(jj(j1 1，2 2，3)3)的投资额为的投资额为x xi i时，时，其收益分别为其收益分别为g g1 1(x(x1 1)4x4x1 1，g g2 2(x(x2 2)9x9x2 2，g g3 3(x(x3 3)2x2x3 32 2，问应如何分配投资，问应如何分配投资数额才能使总收益最大数额才能使总收益最大?(a)用逆序解法解例用逆序解法解例5现在学习的是第47页，共90页k3时，k2时，现在学习的是第48页，共90页k1时，现在学习的是第49页，共90页现在学习的是第50页，共90页阶段划分和决策变量设置同逆序法；阶段划分和决策变量设置同逆序法；状态变量状态变量sk+1 表示可用于第表示可用于第1个到第个到第k个项目投资的资金数个项目投资的资金数:s410，s3 s4 x3，s2 s3 x2，s1 s2 x2;状态转移方程：状态转移方程：sk sk+1-xk；最优指标函数人；最优指标函数人fk(sk+1)表示第表示第k阶段投资金数为阶段投资金数为sk+1时，投资第时，投资第1到第到第k项所得的最大收益数；项所得的最大收益数；递推方程：递推方程：(b)用顺序解法解例用顺序解法解例5现在学习的是第51页，共90页现在学习的是第52页，共90页当k=3时现在学习的是第53页，共90页3)3)连续变量的离散化解法连续变量的离散化解法投资分配问题的一般静态模型为：投资分配问题的一般静态模型为：动态规划模型，其基本方程为：动态规划模型，其基本方程为：5.3.2.逆序法与顺序法逆序法与顺序法现在学习的是第54页，共90页 由于由于s sk k与与x xk k都是连续变量，当各阶段指标都是连续变量，当各阶段指标g gk k(x(xk k)没有特殊性质没有特殊性质而而较为复杂时，要求出较为复杂时，要求出f fk k(s(sk k)会比较困难，这时常常把连续变量会比较困难，这时常常把连续变量离散化求其数值解。具体做法如下：离散化求其数值解。具体做法如下：01 a(m )2 q 012qmq s sk k，x xk k p (a)(a)把把a a分成分成m m份，每份份，每份 大小。大小。S Sk k的取值范围为：的取值范围为：00，2 2,m,m ，的大小可依据问题所要求的精度以及计算机的容的大小可依据问题所要求的精度以及计算机的容量来定。量来定。(b)(b)决策变量决策变量x xk k也在离散点也在离散点0 0，2 2，m m 上取值，相上取值，相应的指标函数应的指标函数f fk k(s(sk k)就被就被定义在这些离散值上，于是定义在这些离散值上，于是:5.3.2.逆序法与顺序法逆序法与顺序法现在学习的是第55页，共90页(c)(c)按逆序（或顺序）方法，逐步递推求出按逆序（或顺序）方法，逐步递推求出f fn n(s(sn n),),，f f1 1(s(s1 1)，最，最后求出最优资金分配方案。后求出最优资金分配方案。解解:令令 2，将区间，将区间0，l0分割成分割成0，2，4，6，8，10六个点，六个点，即状态变量即状态变量sk集合为集合为0，2，4，6，8，10；允许决策集合为；允许决策集合为0 xk sk，xk与与sk均在分割点上取值。均在分割点上取值。例例5其中q s sk k，x xk k p 递推方程就变为了：递推方程就变为了：现在学习的是第56页，共90页 计算结果表明，最优决策为：计算结果表明，最优决策为：x1*0，x2*0，x3*10，最大收益为，最大收益为f1(10)200，与例，与例5结论完全相同。结论完全相同。式中式中x3与与s3的集合均为：的集合均为：0，2，4，6,8，10。计算结果见表计算结果见表71。当当k k3 3时，时，现在学习的是第57页，共90页o表7-1阶段skxkvkvkn=vk+fk+1fkPkn*3002x32=0000228882443232324667272726881281281288101020020020010现在学习的是第58页，共90页o表7-2阶段阶段s sk kx xk kv vk kv vknkn=v=vk k+f+fk+1k+1f fk kP Pkn kn*2009x2=000020002-022x9=1818+0184000+32=324-022x9=1818+8=2644x9=3636+0=36366000+72=72720-622x9=1818+32=5044x9=3636+8=4465454+0=54810现在学习的是第59页，共90页阶段阶段s sk kx xk kv vk kv vknkn=v=vk k+f+fk+1k+1f fk kP Pkn kn*28000+128=1281280-822x9=1818+72=9044x9=3636+32=6865454+8=6287272+0=7210000+200=2002000-1022x9=1818+1282=14644x9=3636+72=10865454+32=8687272+8=80109090+0=90o表7-2现在学习的是第60页，共90页o表7-3阶段阶段s sk kx xk kv vk kv vknkn=v=vk k+f+fk+1k+1f fk kP Pkn kn*11004x1=0 0+200=2002000-0-10288+128=13644x4=1624+36=6062454+32=8683232+18=50104040+0=40现在学习的是第61页，共90页5.45.4动态规划模型的应用动态规划模型的应用5.4.1背包问题（装载问题）背包问题（装载问题）一位旅行者携带背包去登山，已知他所能承受的背包重量限一位旅行者携带背包去登山，已知他所能承受的背包重量限度为度为a千克，现有千克，现有n种物品可供他选择装入背包，第种物品可供他选择装入背包，第i种物品的种物品的单件重量为单件重量为ai千克，其价值千克，其价值(可以是表明本物品对登山的重要性的数可以是表明本物品对登山的重要性的数量指标量指标)是携带件数是携带件数xi的函数的函数ci(xi)(i=1,2,.,n),问旅行者应如问旅行者应如何选择携带各种物品的件数，以使总价值最大？何选择携带各种物品的件数，以使总价值最大？静态数学模型：静态数学模型：现在学习的是第62页，共90页5.45.4动态规划模型的应用动态规划模型的应用n状态转移方程：状态转移方程：n允许决策集合：允许决策集合：最优指标函数最优指标函数：基本方程基本方程：动态规划顺序法：动态规划顺序法：阶段阶段k：(k=1,2,n)按装入物品排序按装入物品排序状态变量状态变量s sk k：第：第k段开始时剩余的空间。段开始时剩余的空间。决策变量决策变量xk:装入第装入第k件物品的件数。件物品的件数。现在学习的是第63页，共90页5.4动态规划模型的应用动态规划模型的应用n允许决策集合：允许决策集合：最优指标函数最优指标函数：基本方程基本方程：动态规划逆序法：动态规划逆序法：阶段阶段k：(k=1,2,n)按装入物品排序按装入物品排序状态变量状态变量s sk k：第：第k段开始时剩余的空间。段开始时剩余的空间。决策变量决策变量xk:装入第装入第k件物品的件数。件物品的件数。n状态转移方程：状态转移方程：现在学习的是第64页，共90页5.45.4动态规划模型的应用动态规划模型的应用 例例7 今有三种货物需要装船，各种货物的重量与运输利润关今有三种货物需要装船，各种货物的重量与运输利润关系如图系如图5-7所示。船的最大装载能力为所示。船的最大装载能力为w6(t)，问应如，问应如何装载才能使总利润最大何装载才能使总利润最大?货物种类货物种类(i)货物质量货物质量(Wi)(t)利润利润(vi)(千元）千元）12823133418o动态规划逆序法：动态规划逆序法：n阶段阶段k：(k=1,2,3)按装入物品排序按装入物品排序n状态变量状态变量s sk k：第：第k段开始时剩余的空间段开始时剩余的空间(可装载第可装载第k种至第种至第n种的载货量。种的载货量。n决策变量决策变量xk:装入第装入第k件货物的数量。件货物的数量。现在学习的是第65页，共90页5.45.4动态规划模型的应用动态规划模型的应用n状态转移方程：状态转移方程：n指标函数：阶段指标即为第指标函数：阶段指标即为第k阶段装载阶段装载xk件货物时件货物时所创的利润所创的利润vkxk。基本方程：基本方程：现在学习的是第66页，共90页5.45.4动态规划模型的应用动态规划模型的应用K=3时：现在学习的是第67页，共90页K=2时：现在学习的是第68页，共90页K=1时：现在学习的是第69页，共90页o 如果已知某企业所生产产品的生产费用、存贮费用和如果已知某企业所生产产品的生产费用、存贮费用和市场的需要量，在其生产能力和存贮能力许可的前提下，市场的需要量，在其生产能力和存贮能力许可的前提下，正确确定各个时期的生产量，使既完成交货计划，又使正确确定各个时期的生产量，使既完成交货计划，又使总支出最少，这就是生产与存贮问题。总支出最少，这就是生产与存贮问题。5.45.4动态规划模型的应用动态规划模型的应用5.4.2 生产存贮问题生产存贮问题（库存问题）（库存问题）例例8 某船厂根据合同，从当年起连续某船厂根据合同，从当年起连续4年年末要为客户提供规年年末要为客户提供规格型号相同的大型客货船，每年的交船数及生产每艘船的生产格型号相同的大型客货船，每年的交船数及生产每艘船的生产费用如表费用如表55所示。所示。现在学习的是第70页，共90页解：动态规划逆序法：解：动态规划逆序法：n阶段阶段k：(k=1,2,3,4)n状态变量状态变量s sk k：第：第k阶段初贮存阶段初贮存(积压积压)的船数。的船数。5.45.4动态规划模型的应用动态规划模型的应用该厂的生产能力为每年该厂的生产能力为每年6艘船。在进行生产的年度，船厂还要支出经常费艘船。在进行生产的年度，船厂还要支出经常费用用60万元。若造出的船当年不交货，则每艘船每积压一年造成的积压损万元。若造出的船当年不交货，则每艘船每积压一年造成的积压损失费为失费为40万元。假定开始时及第四年年未交贷后均无积压船只，问船厂万元。假定开始时及第四年年未交贷后均无积压船只，问船厂应如何安排这四年的生产计划，使所花的总费用为最低应如何安排这四年的生产计划，使所花的总费用为最低?决策变量决策变量xk:为第为第k阶段生产的船数。阶段生产的船数。现