《OR动态规划》PPT课件.ppt

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

1、求A到E的最短距离！BACBDBCDEC412312312322164728386756110637 514第九章第九章 动态规划动态规划 李李 娜娜 2009.92009.9o动态规划是解决多阶段决策过程最优化问题动态规划是解决多阶段决策过程最优化问题的一种方法的一种方法变换成变换成单阶段单阶段问题。问题。o根据时间参量分为：离散变量和连续变量根据时间参量分为：离散变量和连续变量o根据决策过程演变分为：确定性和随机性的根据决策过程演变分为：确定性和随机性的o动态规划可分为：离散确定性、离散随机性、动态规划可分为：离散确定性、离散随机性、连续确定性、连续随机性四种。连续确定性、连续随机性四种。

2、9.19.1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例BACBDBCDEC412312312322164728386756110637 51求最短路径！求最短路径！4用穷举法的计算量用穷举法的计算量:如果从如果从A到到E的站点有的站点有k个，除个，除A、E之外每站有之外每站有3个位置则个位置则总共有总共有3k-12条路径；条路径；计算各路径长度总共要进行计算各路径长度总共要进行(k+1)3k-12次加法以及次加法以及3k-12-1次比较。随着次比较。随着 k 的值增加时，需要进行的加法和比较的的值增加时，需要进行的加法和比较的次数将迅速增加；次数将迅速增加；例如当例如当 k=20

3、时，加法次数为时，加法次数为 4.25508339662271015 次，次，比较比较 1.37260754729771014 次。次。若用若用1亿次亿次/秒的计算机计算需要约秒的计算机计算需要约508天。天。逆序解法：逆序解法：讨论：讨论：1、以以上上求求从从A到到E的的最最短短路路径径问问题题，可可以以转转化化为为四四个个性性质质完完全全相相同同，但但规规模模较较小小的的子子问问题题，即即分分别别从从Di、Ci、Bi、A到到E的的最最短短路路径径问问题。题。第4阶段：D1E，1条路，10，D2E，1条路，6，不一定谁入选最终的最优C1C2C3D1D2E830075001600106阶段阶段

4、4本阶段始本阶段始点点(状态状态)本阶段各终点本阶段各终点(决策决策)到到 E 的的最短距最短距离离本阶段最优本阶段最优终点终点(最优决策最优决策)ED11010ED266E确定每个Dk到达终点E的最短路的长度最短路的长度：10，6 该最短路线的下一步：E，E第3阶段：C1D1、D2，2 条路，8，6 C2D1、D2，2 条路，7，5 C3D1、D2，2 条路，1，6阶段阶段3状态状态决策决策到到 E 的的最短距离最短距离最优最优决策决策D1D2C18+10=186+6=1212D2C27+10=175+6=1111D2C31+10=116 +6=1211D1确定每个Cj 到达终点E的最短路的

5、长度最短路的长度：12，11，11 该最短路线的下一步：D2，D2，D1如果从C1出发，经过D2到达终点最优如果从C2出发，经过D2到达终点最优如果从C3出发，经过D1到达终点最优第2阶段：BiCj，3条路阶段阶段2状态状态决策决策到到 E 的的最短距离最短距离最优最优决策决策C1C2C3B12+12=141+11=126+11=1712C2B24+12=167+11=182+11=1313C3B34+12=168+11=193+11=1414C3B47+12=195+11=161+11=1212C3确定每个Bi 到达终点E的最短路的长度最短路的长度：12,13,14,12 该最短路线的下一步

6、：C2，C3，C3，C3第1阶段：AB1、B2、B3、B4，4条路，4，3，3，2阶段阶段1状态状态决策决策到到 E 的的最短距离最短距离最优最优决策决策B1B2B3B4A4+12=16 3+13=16 3+14=17 2+12=1414B4确定 A 到达终点E的最短路的长度最短路的长度：14 该最短路线的下一步：B4所以，从AE的最短路线是：A B4 C3 D1 E，最短路长度，14逆序标号法：141213141211111210 60BACBDBCDEC41231231232216472838675611063751顺序标号法：BACBDBCDEC412312312322164728386

7、756110637510433235649149.2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理o一、基本概念：一、基本概念：o 1、阶段、阶段k：表示决策顺序的离散的量，阶段可以按表示决策顺序的离散的量，阶段可以按时间或空间划分。时间或空间划分。o 例题：按照空间划分的例题：按照空间划分的A-B；B-C；C-D；D-Eo 2、状态状态sk：能确定地表示决策过程当前特征的量。能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。的，也可以是离散的。o 1阶段阶段 Ao 2阶段阶段Bi

8、,i=1,2,3,4 所以所以S2=B1，B2，B3，B4 o3、决策、决策xk：从某一状态向下一状态过渡时所从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为做的选择。决策是所在状态的函数，记为xk(sk)。oX2（B1）=C1 or C2 or C3o 决策允许集合决策允许集合Dk(sk)：在状态在状态sk下，允许采下，允许采取决策的全体。取决策的全体。o4、策略、策略Pk,n(sk)：从第从第k阶段开始到最后第阶段开始到最后第n阶段的决策序列，称阶段的决策序列，称k子策略。子策略。P1,n(s1)即即为全过程策略。为全过程策略。o5、状态转移方程、状态转移方程 sk+1=T

9、k(sk,xk)：某一某一状态以及该状态下的决策，与下一状态之状态以及该状态下的决策，与下一状态之间的函数关系。间的函数关系。o6、阶段指标函数、阶段指标函数rk(sk,xk)：从状态从状态sk出发，选择决策出发，选择决策xk所产生的第所产生的第k阶段指标。阶段指标。二、基本方程：二、基本方程：o最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Rk,n的最优值，即上式中上式中“opt”表示表示“max”或或“min”终端条件：为了使以上的递推方程有递推的起点，必须要设定最终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态优指标的终

10、端条件，一般最后一个状态n+1下最优指标下最优指标 fn+1(sn+1)=0。三、最优化原理三、最优化原理o作为整个过程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质：o 不管在此最优策略上的某个状态以前的状态不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，必定构成最优子策略。就是说，最优策略最优策略的的任任意子策略意子策略都是都是最优最优的。的。9.3 动态规划的应用动态规划的应用o资源分配问题资源分配问题 例例2.某公司拟将某种设备某公司拟将某种设备5台，分配给所属的甲、乙、丙三个

11、工厂。各工厂台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表获得此设备后，预测可创造的利润如表10-5所示，问这所示，问这5台设备应如何分台设备应如何分配给这配给这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分给三个工厂？分给三个工厂？-看成三阶段问题！求利润最大化！看成三阶段问题！求利润最大化！A5B4B3B5D0C5C4C3C2C1B2B1B0C0下脚标表

12、示剩余台下脚标表示剩余台数！脚标之差表示数！脚标之差表示分出去的台数！分出去的台数！037912130510111111将问题按工厂分为三个阶段，甲、乙、丙三将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为个厂分别编号为1、2、3厂。厂。设sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。xk=分配给第k个厂的设备台数。已知s1=5,根据 和 的定义可以得知：从第三阶段开始计算 第三阶段:显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即 由于第3阶段是最后的阶段，故有 其中可取值为0,1,2,3,4,5。其数值计算见表106。01234 50

13、0001 4412 6623 11 1134 121245 12125 其中表示取其中表示取3子过程上最优指标值时的子过程上最优指标值时的决策，例如在表决策，例如在表10-6中可知当中可知当=4时，有有时，有有此时，即当时，此时取此时，即当时，此时取（把（把4台设备分配给第台设备分配给第3厂）是最优决策，此时阶段指标值厂）是最优决策，此时阶段指标值（盈利）为（盈利）为12，最优，最优3子过程最优指标值也为子过程最优指标值也为12。第二阶段：第二阶段：当把台设备分配给第当把台设备分配给第2工厂和第工厂和第3工工厂时，则对每个值，有一种最优分配方案，使最大盈利厂时，则对每个值，有一种最优分配方案，

14、使最大盈利即最优即最优2子过程最优指标函数值为子过程最优指标函数值为 0123450 00104 51206 54 1023011 56 110 1424012 114110 161,25012 512 116114 110212因为 上式也可写成 其数值计算如表107所示。其中在的这一行里，当时，这里从表105中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表106查即可知=11。同样可知当时，可知 ;当时，；当时，；当时，；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的 上面加一横以示区别，也可知这时的最优决策为1或2。第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表108 表10-8 然后按计算表格的顺序推算，可知最优分配方案有两个：1.由于，根据，查表107可知，再由 ，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据 ，查表107可 0123455 316 9+10 12+5 13+0 21 0,2知，再由 ,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。作业：oP225（1、4）oTHE END