运筹学-动态规划(一)(名校讲义).ppt

《运筹学-动态规划(一)(名校讲义).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第十七、十八讲动态规划（一）§1引言§2动态规划的计算方法——递推方式§1引言（1）动态规划是运筹学的重要分支之一，它是解决多阶段决策过程最优化的一种方法。该法是由美国数学家贝尔曼（R.Bellman）等人在二十世纪50年代首先提出的。R.Bellman于1957年发表的“动态规划”一书是动态规划方面的第一本著作。目前，动态规划已成功地用于解决资源分配、货物装运、设备更新、生产计划以及复合系统可靠性等许多问题。§1引言（2）一、动态规划求解问题的思路某旅客需从①号站到达⑩号站，试指出一条最短路径。交通状况如图3-1

2、所示。[解]一种习惯求解法是首先计算所有可能路线的距离，然后经比较选出一条最短路线，这称为显枚举或穷举法，当维数增大时，该法计算量将急剧增大，从而变得不可行。动态规划是采用递推方式使计算量大减，现简介其思路。108976543211644236136176619103710988,96129109895468444108108第5阶段第4阶段第3阶段第2阶段第1阶段图3-1最优旅行路线问题图3-1中，圆圈内数字表示旅行可能通过的站号（状态号）；共分5个阶段；箭头表示旅行路线，箭头旁边数字表示距离。§1引言（3）令x

3、表示状态(站)号；fi(x)表示从第i阶段x状态到达终点的最短距离；di(x)表示从第i阶段x状态到达终点取最短路线时应到达的下一个状态（站）号。1）假设旅客已到达第4阶段的⑧⑨状态(i)若已到达状态⑧，则只一条路可到达⑩故f4(8)=8d4(8)=10(ii)若已到达状态⑨，同理得f4(9)=4，d4(9)=10。§1引言（4）2）假设旅客已到达第3阶段的⑤⑥⑦状态(i)若已到达状态⑤，有2条路可选：⑤→⑧及⑤→⑨此时应检查这两种选择中能达到的最短距离，即，比较下述i)及ii）并找出最小值。i)从⑤到⑧的距离与⑧

4、到终点的最短距离和ii）从⑤到⑨的距离与⑨到终点的最短距离和。这两个值分别为4+f4(8)=12和8+f4(9)=12，两种费用相等，故得f3(5)=12d3(5)=8或9§1引言（5）（ii）若已到达状态⑥，同理可得f3(6)=min=min=10对应d3(6)=9(iii)若已到达状态⑦，同样得f3(7)=min=8d3(7)=9按照同样方法，可算出旅客已到第2阶段和第1阶段的结果。§1引言（6）把上述计算结果全部标在图3-1上的状态点附近。其中，圆圈上方数字表示该状态点的最短距离，圆圈下方数字表示该状态点的最

5、优决策。最后，根据计算结果，可找出从①到⑩的最短路线为①→④→⑥→⑨→⑩。§1引言（7）二、最优化原理最优化原理可阐述如下：“一个最优策略具有这样的性质：不论初始状态和初始决策如何，相对于第1个决策所形成的状态来说，余下决策必定构成一个最优策略”。如图3-2中，若路线I和II是A到C的最优路线，则根据最优化原理，路线II必是从B到C的最优路线。AⅠCBII’图3-2II§1引言（8）三、动态规划中的主要名词术语1．阶段（Stage）：把问题分成几个相互联系的有顺序的几个环节，通常用k表示。2．状态（State）：表

6、示某阶段的出发位置或状态值，通常用x表示。3．决策（Decision）：从某阶段的1个状态演变到下一阶段某状态的选择，通常用d或u表示。§1引言（8）三、动态规划中的主要名词术语4．策略（Policy）：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略，通常用P表示。5．目标函数（或费用函数）：在优化过程中，衡量实现过程的优劣的准则，通常用f或J表示。§2动态规划的计算方法——递推方式（1）根据动态规划所求解问题的不同情况可采用后向（逆序）动态规划和前向（顺序）动态规划两种。一、后向动态规划

7、法已知：目标函数J=＝min约束条件（状态转移方程）x(k+1)=g[x(k)，u(k)，k]则，递推公式为§2动态规划的计算方法——递推方式（2）起步：其中，I（x，k）——从k阶段x状态出发采取最优策略到达过程终点所获得的最优目标值；L（x，u，k）——k阶段x状态采取决策u所获得的本段目标函数值，又称直接项；U——决策变量u的集合。§2动态规划的计算方法——递推方式（3）[例3-2]供电系统的投资规划问题某工厂为满足用电需求增加量，计划在1980年，1985年及1990年投资兴建发电站。电站有500MW和10

8、00MW两种，每年最多兴建一座电站，其投资额示如表3-1，下列表内金额全折合到1980年标准。表3-1兴建电站投资表（单位：106元）投资额年份容量198019851990500MW1000MW1.00.50.251.60.80.4§2动态规划的计算方法——递推方式（4）电站投资兴建后5年发电。工厂各年需新增加的累积电功率示如表3-2。表3-2工厂各年需新增