第六讲动态规划上.ppt

《第六讲动态规划上.ppt》由会员分享，可在线阅读，更多相关《第六讲动态规划上.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六讲动态规划上现在学习的是第1页，共47页第一节第一节多阶段决策过程的最优化多阶段决策过程的最优化 美国数学家贝尔曼美国数学家贝尔曼(R.Bellman)50R.Bellman)50年代执年代执教于普林斯顿和斯坦福大学，后进入兰德教于普林斯顿和斯坦福大学，后进入兰德（RandRand）研究所。研究所。19571957年发表年发表“Dynamic Dynamic ProgrammingProgramming”一书，标识动态规划的正式诞生。一书，标识动态规划的正式诞生。现在学习的是第2页，共47页最短路问题最短路问题给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），给定一个交通网络图

2、如下，其中两点之间的数字表示距离（或花费），试求从试求从A A点到点到G G点的最短距离（总费用最小）点的最短距离（总费用最小）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456现在学习的是第3页，共47页2 2、每个阶段都要进行、每个阶段都要进行决策决策,目的是使整个过程的决策达到目的是使整个过程的决策达到最优效果。最优效果。多阶段决策问题：多阶段决策问题：1 1、在多阶段决策过程中、在多阶段决策过程中,系统的动态过程可以按照时间进程分系统的动态过程可以按照时间进程分为为状态状态相互相互联系联系而又相互而又相互

3、区别区别的各个的各个阶段阶段；现在学习的是第4页，共47页12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策现在学习的是第5页，共47页多阶段决策问题的典型例子多阶段决策问题的典型例子现在学习的是第6页，共47页 给定一个线路网络图，要从给定一个线路网络图，要从A A地向地向F F地铺设一条输油管道，各点间地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短连线上的数字表示距离，问应选择什么路线，可使总距离最短?现在学习的是第7页，共47页资源分配问题资源分配问题 例例.某某公公司司拟拟将将某某种种设设备备5 5台台，分分配配给给所所属属的的甲甲、乙乙、

4、丙丙三三个个工工厂厂。各各工工厂厂获获得得此此设设备备后后，预预测测可可创创造造的的利利润润如如下下表表所所示示，问问这这5 5台台设设备备应应如如何何分配给这分配给这3 3个工厂，使得所创造的总利润为最大？个工厂，使得所创造的总利润为最大？工厂 盈利设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12现在学习的是第8页，共47页机器负荷分配问题机器负荷分配问题 某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产品的年产量

5、产品的年产量g g和投入生产的机器数量和投入生产的机器数量u u1 1的关系为的关系为g g=g g(u u1 1)这时，机器的年完好率为这时，机器的年完好率为a a，即如果年初完好机器的数量为即如果年初完好机器的数量为u u，到年终完好的到年终完好的机器就为机器就为auau,0,0a a11。在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h h和投入生产的机器数量和投入生产的机器数量u u2 2的关系为的关系为 h h=h h(u u2 2)假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s s1 1。要求制定一个五年计划，在每年开始时要求制定一个五年计划，在每年开

6、始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。产品的总产量达到最高。相应的机器年完好率相应的机器年完好率b b,0,0b b11。现在学习的是第9页，共47页设备更新问题设备更新问题 企企业业在在使使用用设设备备时时都都要要考考虑虑设设备备的的更更新新问问题题，因因为为设设备备越越陈陈旧旧所所需需的的维维修修费费用用越越多多，但但购购买买新新设设备备则则要要一一次次性性支支出出较较大大的的费费用用。现现某某企企业业要要决决定定一一台台设设备备未未来来8 8年年的的更更新新计计划划

7、，已已预预测测了了第第j j年年购购买买设设备备的的价价格格为为K Kj j，设设G Gj j为为设设备备经经过过j j年年后后的的残残值值，C Cj j为为设设备备连连续续使使用用j-1j-1年年后后在在第第j j年年的的维维修修费费(j j1 1，2 2，8)8)，问问应应在在哪哪些些年年更更新新设设备备可使总费用最小。可使总费用最小。这这是是一一个个8 8阶阶段段决决策策问问题题，每每年年年年初初要要作作出出决决策策，是是继继续续使使用用旧旧设设备备，还是购买新设备。还是购买新设备。现在学习的是第10页，共47页第二节第二节动态规划的基本概念和基本原理动态规划的基本概念和基本原理 一、动

8、态规划的基本概念一、动态规划的基本概念使使用用动动态态规规划划方方法法解解决决多多阶阶段段决决策策问问题题，首首先先要要将将实实际际问问题题写写成成动动态态规规划划模模型型，此此时时要要用用到到以以下下概概念：念：(1)阶段；阶段；(2)状态；状态；(3)决策和策略；决策和策略；(4)状态转移；状态转移；(5)指标函数指标函数。现在学习的是第11页，共47页要便于把问题的过程转化为多阶段决策的过程。要便于把问题的过程转化为多阶段决策的过程。1.阶段、阶段变量阶段、阶段变量 把所给问题的过程，适当地分为若干个相互联系把所给问题的过程，适当地分为若干个相互联系的的阶段阶段，以便按次序去求每阶段的解

9、以便按次序去求每阶段的解;描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量，常用常用k k表示表示；阶段的划分，一般是阶段的划分，一般是按时间和空间按时间和空间的的自然特征自然特征（年、月、年、月、路段路段）来划分）来划分 ；现在学习的是第12页，共47页 例例中，从中，从A A到到F F可以分成从可以分成从A A到到B (BB (B有两种选择有两种选择B B1 1,B,B2 2)，从从B B到到C (CC (C有四种选择有四种选择C C1 1，C C2 2，C C3 3，C C4 4)，从从C C到到D (DD (D有三种选择有三种选择D D1 1，D D2 2 ,D,D3 3)，从从D

10、 D到到E (EE (E有两种选择有两种选择E E1 1，E E2 2)，再从再从E E到到F F五个阶段。五个阶段。k k1 1，2 2，3 3，4 4，5 5。现在学习的是第13页，共47页 状态变量的取值有一定的允许集合或范围，此集合称状态变量的取值有一定的允许集合或范围，此集合称为为状态允许集合，状态允许集合，用用S Sk k表示。表示。2.2.状态、状态变量状态、状态变量 每个阶段开始所处的自然状态或客观条件。通常一个每个阶段开始所处的自然状态或客观条件。通常一个阶段有若干个状态。阶段有若干个状态。描述过程状态的变量称为描述过程状态的变量称为状态变量状态变量，常用常用s sk k（一

11、个数、一个数、一组数、一个向量一组数、一个向量）表示第表示第k k阶段的状态。阶段的状态。现在学习的是第14页，共47页 在例在例5中，第一阶段状态为中，第一阶段状态为A，第二阶段则有二个状态：第二阶段则有二个状态：Bl，B2。状状态变量态变量s1的集合的集合 ，后面各段的状态集合分别是：，后面各段的状态集合分别是：现在学习的是第15页，共47页 动态规划中的状态应具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发动态规划中的状态应具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。也就是说，当前的状态是过去历史的一个完整总结，展不受这段以前各段状态的影

12、响。也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展，这称为过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性无后效性。如果所选定如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。例例 5 5 中中，当当某某段段的的初初始始状状态态已已选选定定某某个个点点时时，从从这这个个点点以以后后的的铺铺管管路路线线只只与与该该点点有有关关，不受以前的铺管路线影响，所以满足状态的无后效性。不受以前的铺管路线影响，所以满足状态的无后效性。现在学习的是第16页，共47页 在

13、实际问题中决策变量的取值往往在某一范围之内，此范围称为在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集允许决策集合合。常用常用 D Dk k(s sk k)表示第表示第 k k 阶段从状态阶段从状态s sk k出发的允许出发的允许决策集合决策集合，显然有显然有 决策变量是状态变量的函数。决策变量是状态变量的函数。3.决策、决策变量决策、决策变量 过程的某一阶段、过程的某一阶段、某个状态某个状态,可以做出不同的决定可以做出不同的决定(选择选择),),决定下一阶段的状态，决定下一阶段的状态，这种决定称为这种决定称为决策决策。uk(sk)Dk(sk)描述决策的变量，称为描述决策的变

14、量，称为决策变量决策变量。常用常用 表示第表示第 k k 阶段当状态阶段当状态为为s sk k 时的决策变量。时的决策变量。现在学习的是第17页，共47页 在在例例5 5中，从第二阶段的状态中，从第二阶段的状态B B1 1出发，可选择下一段的出发，可选择下一段的C C1 1，C C2 2，C C3 3，即其允许决策集即其允许决策集 合为：合为：我们决定选择我们决定选择C3，则可表为：则可表为：uk(sk)Dk(sk)现在学习的是第18页，共47页由由每每段段的的决决策策按按顺顺序序排排列列组组成成的的决决策策函函数数序序列列称称为为k子子过过程程策策略略，简简称称子子策策略略，记为记为pk,n

15、(sk)，即即 当当k=1时，此决策函数序列成为全过程的一个策略，简称时，此决策函数序列成为全过程的一个策略，简称策略策略，记为记为p1,n(s1)即：即：4.策略策略按顺序排列的按顺序排列的决策决策组成的集合；组成的集合；可供选择的策略有一定范围，此范围称为可供选择的策略有一定范围，此范围称为允许策略集合允许策略集合，用用表示。从表示。从允许策略集合中找出达到最优效果的策略称为允许策略集合中找出达到最优效果的策略称为最优策略最优策略。由第由第kn(终止状态终止状态)为止的过程，称为问题的为止的过程，称为问题的后部子过程后部子过程（k 子过程）子过程）现在学习的是第19页，共47页 费用、成本

16、、利润、路长等费用、成本、利润、路长等 。用。用 V Vk k,n n 表示之。表示之。5.指标函数和最优值函数指标函数和最优值函数 用于衡量所选定策略优劣的数量指标称为用于衡量所选定策略优劣的数量指标称为指标函数指标函数；它是定义在全过程或它是定义在全过程或所有所有后部后部子过程上确定的数量函数。子过程上确定的数量函数。一个一个n n段决策过程，从段决策过程，从l l到到n n叫作问题的叫作问题的原过程原过程，对于任意一个给定的对于任意一个给定的k(1kn)k(1kn)，从第从第k k段到第段到第n n段的过程称为原过程的一个段的过程称为原过程的一个后部子过程后部子过程。表示在第表示在第k

17、k段，状态为段，状态为s sk k采用策略采用策略 ，后部子过程的指标函数，后部子过程的指标函数值。值。表示初始状态为表示初始状态为s1采用策略采用策略 时原过程的指标函数值，时原过程的指标函数值，而而现在学习的是第20页，共47页 最优指标函数最优指标函数记为记为 ，它表示从第，它表示从第 k段状态段状态 sk采用最优策略采用最优策略 到过程终止时的最佳效益值。到过程终止时的最佳效益值。与与 间的关系为：间的关系为：opt全称全称optimum，表示最优化，根据具体问题分别表为表示最优化，根据具体问题分别表为max或或min。当当k1时，时，就是从初始状态就是从初始状态 s1到全过程结束的整

18、体最优函数。到全过程结束的整体最优函数。在在例例5中中，指指标标函函数数是是距距离离。如如第第2阶阶段段，状状态态为为B1时时，表表示示从从B1到到F的的距距离离，而而则则表表示示从从B1到到F的的最最短短距距离离。本本问问题题的的总总目目标标是是求求，即从，即从A到终点到终点F的最短距离的最短距离。现在学习的是第21页，共47页二、动态规划的基本思想与基本原理二、动态规划的基本思想与基本原理 下面结合例下面结合例5最短路线问题介绍动态规划的最短路线问题介绍动态规划的基本思想。基本思想。现在学习的是第22页，共47页 为了求出最短路线，一种简单的方法，可以求出所有从为了求出最短路线，一种简单的

19、方法，可以求出所有从A A至至F F的的可能铺设的路长并加以比较。不难知道从可能铺设的路长并加以比较。不难知道从A A至至F F共有共有2424条不同路径，条不同路径，要求出最短路线需要做要求出最短路线需要做2323次比较运算，这种方法称次比较运算，这种方法称穷举法穷举法。当问题的段数很多、各段的状态也很多时，穷举法的计算量当问题的段数很多、各段的状态也很多时，穷举法的计算量会大大增加，甚至使得求优成为不可能。下面介绍动态规划方会大大增加，甚至使得求优成为不可能。下面介绍动态规划方法。注意本方法是从过程的法。注意本方法是从过程的最后一段开始最后一段开始，用，用逆序递推逆序递推方法求解，方法求解

20、，逐步求出各段各点到终点逐步求出各段各点到终点F F的最短路线，最后求得的最短路线，最后求得A A点到点到F F点的最短路点的最短路线。线。现在学习的是第23页，共47页 用用 表表示示由由状状态态sk点点出出发发，采采用用决决策策uk到到达达下下一一阶阶段段sk+1点点时时的两点距离。的两点距离。第一步第一步，从从k5开始，状态变量开始，状态变量s5可取两种状态可取两种状态E1，E2，它们到它们到F点的路长分点的路长分别为别为4，3。即：即：第第二二步步，k4，状状态态变变量量s4可可取取三三个个值值D1，D2，D3，这这是是经经过过一一个个中中途途点点到到达达终终点点F的的两两级决策问题，

21、从级决策问题，从D1到到F有两条路线，需加以比较，取其中最短的，即：有两条路线，需加以比较，取其中最短的，即：现在学习的是第24页，共47页由由D D1 1到终点到终点F F最短距离为最短距离为7 7，其路径为，其路径为D D1 1EE1 1FF。相应决策为相应决策为 即即D2到终点最短距离为到终点最短距离为5，其路径为，其路径为D2E2F。相应决策为相应决策为即即D3到终点最短距离为到终点最短距离为5，其路径为，其路径为D3E1F。相应决策为相应决策为现在学习的是第25页，共47页类似的，可算得：类似的，可算得：k=3时，有时，有k=2时，有时，有k=1时，则时，则现在学习的是第26页，共4

22、7页所以最优路线为：所以最优路线为：即从即从A A到到F F的最短距离为的最短距离为1717。本段决策为。本段决策为 再按计算顺序反推可得最优决策序列再按计算顺序反推可得最优决策序列 即即现在学习的是第27页，共47页 这这种种递递推推关关系系称称为为动动态态规规划划的的基基本本方方程程，(7.3(7.3b)b)式式称称为为边边界界条件条件。从从例例5 5的的计计算算过过程程中中可可以以看看出出，在在求求解解的的各各阶阶段段，都都利利用用了了第第k k段段和和第第k+1k+1段的如下关系：段的如下关系：现在学习的是第28页，共47页 上上述述最最短短路路线线的的计计算算过过程程也也可可用用图图

23、直直观观表表示示出出来来，如如图图7 7-2-2，每每个个结结点点上上方方的的括括号号内内的的数数，表表示示该该点点到到终终点点F F的的最最短短距距离离。连连结结各各点点到到F F点的线表示最短路径。这种在图上直接计算的方法叫点的线表示最短路径。这种在图上直接计算的方法叫标号法标号法。现在学习的是第29页，共47页第三节第三节动态规划模型的建立与求解动态规划模型的建立与求解 一、动态规划模型的建立一、动态规划模型的建立 建建立立动动态态规规划划的的模模型型，就就是是分分析析问问题题并并建建立立问问题题的的动动态态规规划划基本方程基本方程。应应用用动动态态规规划划方方法法的的关关键键在在于于:

24、识识别别问问题题的的多多阶阶段段特特征征，将将问问题题分分解解成成为为可可用用递递推推关关系系式式联联系系起起来来的的若若干干子子问问题题，而而正正确确建建立立基基本本递递推推关关系系方方程程的的关关键键又又在在于于正正确确选选择择状状态态变变量量，保保证各阶段的状态变量具有递推的状态转移关系。证各阶段的状态变量具有递推的状态转移关系。现在学习的是第30页，共47页 下面以资源分配问题为例介绍动态规划下面以资源分配问题为例介绍动态规划的建模条件及解法。资源分配问题是动态规的建模条件及解法。资源分配问题是动态规划的典型应用之一，资源可以是资金、原材划的典型应用之一，资源可以是资金、原材料、设备、

25、劳力等，资源分配就是将料、设备、劳力等，资源分配就是将一定数一定数量量的一种或几种资源恰当地分配给若干使用者，的一种或几种资源恰当地分配给若干使用者，以以获取最大效益。获取最大效益。现在学习的是第31页，共47页资源分配问题资源分配问题例例.某公司拟将某种设备某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如下表所示，问这厂。各工厂获得此设备后，预测可创造的利润如下表所示，问这5台设备应如何分配给这台设备应如何分配给这3个工厂，使得所创造的总利润为最大？个工厂，使得所创造的总利润为最大？工厂 盈利设备台数 甲 厂 乙

26、厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12现在学习的是第32页，共47页解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。厂。设设sk=分配给第分配给第k个厂至第个厂至第3个厂的设备台数（个厂的设备台数（k=1、2、3）xk=分配给第分配给第k个设备台数。个设备台数。已知已知s1=5,并有并有现在学习的是第33页，共47页第三阶段第三阶段:显然将台设备都分配给第显然将台设备都分配给第3工厂时，工厂时，也就是时，第也就是时，第3阶段的指标值

27、（即第阶段的指标值（即第3厂的盈利）厂的盈利）为最大，即为最大，即由于第由于第3阶段是最后的阶段，故有阶段是最后的阶段，故有其中可取值为其中可取值为0,1,2,3,4,5。其数值计算见表。其数值计算见表。现在学习的是第34页，共47页01234 5 000014 412662311113412124512125现在学习的是第35页，共47页其中表示取其中表示取3子过程上最优指标值时的子过程上最优指标值时的决策，例如在表决策，例如在表可知当可知当=4时，有有时，有有此时，即当时，此时取此时，即当时，此时取（把（把4台设备分配给第台设备分配给第3厂）是最优决策，此时阶段指标值厂）是最优决策，此时阶

28、段指标值（盈利）为（盈利）为12，最优，最优3子过程最优指标值也为子过程最优指标值也为12。第二阶段：第二阶段：当把台设备分配给第当把台设备分配给第2工厂和第工厂和第3工工厂时，则对每个值，有一种最优分配方案，使最大盈利厂时，则对每个值，有一种最优分配方案，使最大盈利即最优即最优2子过程最优指标函数值为子过程最优指标函数值为现在学习的是第36页，共47页因为上式也可写成其数值计算如表所示。0123450 00104 51206 54 1023011 56 110 1424012 114110 161,25012 512 116114 110212现在学习的是第37页，共47页 其中在的这一行里

29、，当时，这里从表105中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表106查即可知=11。同样可知当时，可知 ;当时，；当时，；当时，；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的 上面加一横以示区别，也可知这时的最优决策为1或2。现在学习的是第38页，共47页第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表 然后按计算表格的顺序推算，可知最优分配方案有两个：1.由于，根据，查表107可知，再由 ，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据 ，查表可 0

30、123455 316 9+10 12+5 13+0 21 0,2现在学习的是第39页，共47页知，再由 ,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。现在学习的是第40页，共47页问如何分配投资数额才能使总效益最大问如何分配投资数额才能使总效益最大?例：例：某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目i(i=1,2,3)i(i=1,2,3)的投资额为的投资额为x xi i时，其效益分别为时，其效益分别为 现在学习的是第41页，共47页解：解：可列出静态规划问题的模型如下可列出静态规划问题的模型如下现在学习的是第42页，共47页

31、 1.1.分阶段：分阶段：分三个阶段，即分三个阶段，即 k=1k=1，2 2，3 3。将投资项目排序，将投资项目排序，首先考虑对项目首先考虑对项目1 1投资投资，然后然后考虑对项目考虑对项目2 2投资投资，最后考虑对项目最后考虑对项目3 3投资投资,即把问题即把问题划分为划分为3 3个阶段个阶段，每个阶段只决定对一个项目应投资每个阶段只决定对一个项目应投资的金额。这样问题转化为一个的金额。这样问题转化为一个3 3段决策过程。段决策过程。现在学习的是第43页，共47页2.2.确定决策变量：确定决策变量：通常可以取静态规划中的变通常可以取静态规划中的变量为决策变量。量为决策变量。即设即设 决策变量

32、决策变量 ：决定给第：决定给第k k个项目投资的资金数。个项目投资的资金数。现在学习的是第44页，共47页3.3.确定状态变量：确定状态变量：状态变量与决策变量有密切关系，状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。状态变量一般为累计量或随递推过程变化的量。可可以以把把每每阶阶段段可可供供使使用用的的资资金金定定为为状状态态变变量量 ，初初始始状状态态 。为为分分配配于于第第一一种种项项目目的的资资金金数数，则则当当第第一一阶段阶段(k k1)1)时，有时，有现在学习的是第45页，共47页状态转移方程状态转移方程:指标函数：指标函数：状态变量状态变量 ：第：第k k段可以投资于第段可以投资于第k k项到第项到第3 3个项目的资金数。个项目的资金数。现在学习的是第46页，共47页 基本方程：基本方程：最优指标函数：最优指标函数：f fk k(s(sk k)当可投资金数为当可投资金数为 时，投资时，投资第第k k至第至第3 3项项所得的最大收益数。所得的最大收益数。现在学习的是第47页，共47页