运筹学二动态规划幻灯片.ppt

《运筹学二动态规划幻灯片.ppt》由会员分享，可在线阅读，更多相关《运筹学二动态规划幻灯片.ppt（122页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学二动态规划运筹学二动态规划第1页，共122页，编辑于2022年，星期三动态规划动态规划n 动动态态规规划划是是运运筹筹学学的的一一个个分分支支，它它是是解解决决多多阶阶段段决决策策问问题题的的一一种种数数学学方方法法。大大约约产产生生于于上上个个世世纪纪50年年代代，已已广广泛泛的的应应用用于于工工程程技技术术、工工农农业业生生产产以以及及军军事事等等部部门门，并并获获得得了了显显著著的的效效果果，尤尤其其是是在在企企业业管管理理决策方面。决策方面。第2页，共122页，编辑于2022年，星期三动态规划 在在企企业业管管理理方方面面，动动态态规规划划可可以以用用来来解解决决最最优优路路径径

2、问问题题、资资源源分分配配问问题题、生生产产调调度度问问题题、库库存存问问题题、装装载载问问题题、排排序序问问题题、设设备备更更新新问问题题、生生产产过过程程最最优优控控制制等等问问题题，是是现现代代企企业业管管理理中中一一种种重要的决策方法。重要的决策方法。第3页，共122页，编辑于2022年，星期三主要内容主要内容n动态规划（动态规划（1）n 动态规划基本原理与方法动态规划基本原理与方法n动态规划（动态规划（2）n 动态规划应用举例动态规划应用举例第4页，共122页，编辑于2022年，星期三运筹学（二）运筹学（二）动态规划（动态规划（1）动态规划基本原理与方法动态规划基本原理与方法第5页，

3、共122页，编辑于2022年，星期三主要内容主要内容n 1.多阶段决策过程及实例多阶段决策过程及实例n 2.动态规划基本概念动态规划基本概念n 3.动态规划基本原理动态规划基本原理 4.动态规划与其它方法的比较动态规划与其它方法的比较 5.动态规划的理论基础动态规划的理论基础n 6.动态规划的具体解法动态规划的具体解法第6页，共122页，编辑于2022年，星期三1.1.多阶段决策过程与实例多阶段决策过程与实例n 在在生生产产实实践践和和科科学学实实验验中中，存存在在这这样样一一类类活活动动过过程程：其其过过程程分分为为若若干干个个互互相相联联系系的的阶阶段段，在在每每一一个个阶阶段段都都需需要

4、要作作出出决决策策，目目的的是是使使整整个个过过程程达达到到最最好好的的活动效果。活动效果。第7页，共122页，编辑于2022年，星期三示例示例1n 例例1 1 最最短短路路线线问问题题给给定定一一个个线线路路网网络络，两两点点之之间间连连线线上上的的数数字字表表示示两两点点间间的的距距离离(或或费费用用)，试试求求一一条条由由A到到G的的铺铺管管线线路路，使使总总距距离离为为最最短短(或或总总费费用用最小最小)。第8页，共122页，编辑于2022年，星期三n最短路线问题示意图最短路线问题示意图第9页，共122页，编辑于2022年，星期三最短路线问题示意图最短路线问题示意图第10页，共122页

5、，编辑于2022年，星期三n 在在最最短短线线路路问问题题中中，各各个个阶阶段段决决策策的的选选取取不不是是任任意意确确定定的的，它它既既依依赖赖于于当当前前所所处处的的位位置置（或或状状态态），又又影影响响以以后后的的决决策策（或或发发展展）。当当各各个个阶阶段段决决策策确确定定后后，就就组组成成了了一一个个决决策策序序列列，因因而而也也就就决定了整个过程的一条活动路线。决定了整个过程的一条活动路线。第11页，共122页，编辑于2022年，星期三示例示例2n 例例2 机机器器负负荷荷分分配配问问题题某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高

6、负负荷荷下下进进行行生生产产时时，产产品品的的年年产产量量g和和投投入入生生产产的的机机器器数数量量u1的的关关系系为为n g=g(u1)n这这时时，机机器器的的年年完完好好率率为为a，即即如如果果年年初初投投入入高高负负荷荷状状态态生生产产的的完完好好机机器器数数量量为为u，到到年年终终时时完完好好的的机机器就为器就为au，其中，其中0a1；第12页，共122页，编辑于2022年，星期三n 在在低低负负荷荷下下生生产产时时，产产品品的的年年产产量量h和投入生产的机器数量和投入生产的机器数量u2的关系为的关系为n h=h(u2)n相应的机器年完好率为相应的机器年完好率为b，其中，其中0b1。第

7、13页，共122页，编辑于2022年，星期三n 假假定定开开始始生生产产时时，完完好好的的机机器器数数量量为为s1。要要求求制制定定一一个个五五年年计计划划，在在每每年年开开始始时时，决决定定如如何何重重新新分分配配完完好好的的机机器器在在两两种种不不同同的的负负荷荷下下生生产产的的数数量量，使使在在五五年年内内产产品的总产量达到最高。品的总产量达到最高。第14页，共122页，编辑于2022年，星期三n多阶段决策过程示意图多阶段决策过程示意图第15页，共122页，编辑于2022年，星期三n 从从决决策策的的角角度度来来看看，上上述述前前后后关关联联具具有有链链状状结结构构的的多多阶阶段段过过程

8、程就就称称为为多多阶阶段段决决策策过过程程，也也称称序序贯贯决决策策过过程程。这这种种问题就称为多阶段决策问题。问题就称为多阶段决策问题。第16页，共122页，编辑于2022年，星期三n 在在多多阶阶段段决决策策问问题题中中，各各个个阶阶段段采采取取的的决决策策，一一般般来来说说与与时时间间有有关关，决决策策依依赖赖于于当当前前的的状状态态，又又随随即即引引起起状状态态的的转转移移，一一个个决决策策序序列列就就是是在在变变化化的的状状态态中产生出来的中产生出来的，故有，故有“动态动态”的含义。的含义。第17页，共122页，编辑于2022年，星期三n 但但是是，一一些些与与时时间间没没有有关关系

9、系的的静静态态规规划划（如如线线性性规规划划、非非线线性性规规划划等等）问问题题，只只要要人人为为地地引引进进“时时间间”因因素素，也也可可以以把把它它视视为为多多阶阶段段决决策策问问题题，用用动动态态规划的方法去处理。规划的方法去处理。第18页，共122页，编辑于2022年，星期三2.动态规划基本概念动态规划基本概念 下下面面结结合合最最短短路路线线问问题题，对对动动态态规规划划所涉及到的基本概念进行说明。所涉及到的基本概念进行说明。第19页，共122页，编辑于2022年，星期三 在在最最短短路路线线问问题题中中，从从A点点到到G点点可可以以分分为为6个个阶阶段段，是是一一个个6阶阶段段的的

10、多多阶阶段段决决策策问问题题。其其目目的的是是：在在各各个个阶阶段段上上选选择择一一个个恰恰当当的的决决策策，使使得得由由这这些些决决策策组组成成的的一一个个决决策策序序列列所所决决定定的的一一条条路路线线是是总总路路程程最最短的一条。短的一条。第20页，共122页，编辑于2022年，星期三最短路线问题示意图最短路线问题示意图第21页，共122页，编辑于2022年，星期三 动动态态规规划划问问题题涉涉及及到到的的基基本本概概念念主主要要有有：阶阶段段、状状态态、决决策策、策策略略、状状态态转转移移方程方程和和指标函数指标函数（以及（以及最优值函数最优值函数）。）。第22页，共122页，编辑于2

11、022年，星期三阶段阶段 1）阶段阶段 将将所所给给问问题题的的过过程程，恰恰当当地地分分为为若若干干个个相相互互联系的阶段，以便能按一定的次序去求解。联系的阶段，以便能按一定的次序去求解。描描述述阶阶段段的的变变量量称称为为阶阶段段变变量量，常常用用k表示。表示。第23页，共122页，编辑于2022年，星期三阶段阶段 阶阶段段的的划划分分，一一般般是是根根据据时时间间和和空空间间的的自自然然特特征征来来划划分分，但但要要便便于于把把问问题题的的过过程程能能转转化化为为多多阶阶段段决决策策的的过过程程。如如例例1可可分分为为6个个阶阶段段来来求求解解，k分分别别等等于于1、2、3、4、5、6。

12、第24页，共122页，编辑于2022年，星期三阶段阶段最短路线问题中最短路线问题中“阶段阶段”的示意图的示意图第25页，共122页，编辑于2022年，星期三状态状态 2）状态状态 状状态态表表示示每每个个阶阶段段开开始始所所处处的的自自然然状状况况或或客客观观条条件件，它它描描述述了了研研究究问问题题过过程程的的状状况况，又又称不可控因素。称不可控因素。第26页，共122页，编辑于2022年，星期三状态状态 在在例例1中中，状状态态就就是是某某阶阶段段的的出出发发位位置置。它它既既是是该该阶阶段段某某支支路路的的起起点点，又又是是前前一阶段某支路的终点。一阶段某支路的终点。第27页，共122页

13、，编辑于2022年，星期三状态状态 最短路线问题中最短路线问题中“状态状态”的示意图的示意图第28页，共122页，编辑于2022年，星期三状态状态 通通常常一一个个阶阶段段有有若若干干个个状状态态，第第一一阶阶段段有有一一个个状状态态就就是是点点A，第第二二阶阶段段有有两两个个状状态态，即即点点集集B1，B2，第第k阶阶段段的的状状态就是第态就是第k阶段所有始点的集合。阶段所有始点的集合。第29页，共122页，编辑于2022年，星期三状态状态 描描述述过过程程状状态态的的变变量量称称为为状状态态变变量量。它它可可用用一一个个数数、一一组组数数或或一一向向量量(多多维维情情形形)来描述。来描述。

14、第30页，共122页，编辑于2022年，星期三状态状态 常常用用sk表表示示第第k阶阶段段的的状状态态变变量量。如如在在例例1中中第第三三阶阶段段有有四四个个状状态态，则则状状态态变变量量sk可可取取四四个个值值，即即C1、C2、C3、C4。点点集集合合C1，C2，C3，C4就就称称为为第第三三阶阶段段的可达状态集合。记为的可达状态集合。记为 S3C1，C2，C3，C4第31页，共122页，编辑于2022年，星期三最短路线问题中最短路线问题中“状态集合状态集合”的示意图的示意图第32页，共122页，编辑于2022年，星期三状态状态 有有时时为为了了方方便便起起见见，将将该该阶阶段段的的状状态态

15、编上号码编上号码1，2，这时也可记，这时也可记 S31，2，3，4 第第k阶段的可达状态集合就记为阶段的可达状态集合就记为Sk。第33页，共122页，编辑于2022年，星期三 在在例例1中中，当当某某阶阶段段的的始始点点给给定定后后，虽虽然然会会影影响响后后面面各各阶阶段段的的行行进进路路线线和和整整个个路路线线的的长长短短，而而后后面面各各阶阶段段路路线线的的发发展展不不受这点以前各阶段决策的影响受这点以前各阶段决策的影响。第34页，共122页，编辑于2022年，星期三状态无后效性示意图状态无后效性示意图第35页，共122页，编辑于2022年，星期三马尔科夫性马尔科夫性 这里，状态应具有如下

16、性质：这里，状态应具有如下性质：如果某如果某阶段状态给定后，则在这阶段以后过程的阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。发展不受这阶段以前各阶段状态的影响。换句话说，过程的过去历史只能通过当前换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态的状态去影响它未来的发展，当前的状态是以往历史的一个总结。是以往历史的一个总结。这个性质称为无这个性质称为无后效性后效性(即即马尔科夫性马尔科夫性)。第36页，共122页，编辑于2022年，星期三决策决策 3）决策决策 决策表示当过程处于决策表示当过程处于某一阶段的某个某一阶段的某个状态状态时，可以时，

17、可以作出不同的决定作出不同的决定(或选择或选择)，从而确定下一阶段的状态，这种决定称为从而确定下一阶段的状态，这种决定称为决策。在最优控制中也称为控制。决策。在最优控制中也称为控制。第37页，共122页，编辑于2022年，星期三决策决策 描描述述决决策策的的变变量量，称称为为决决策策变变量量。它它可可用用一一个个数数、一一组组数数或或一一向向量量来来描描述述。常常用用uk(sk)表表示示第第k阶阶段段当当状状态态处处于于sk时时的的决决策变量。它是状态变量的函数。策变量。它是状态变量的函数。第38页，共122页，编辑于2022年，星期三决策决策 在在实实际际问问题题中中，决决策策变变量量的的取

18、取值值往往往往限限制制在在某某一一范范围围之之内内，此此范范围围称称为为允允许许决决策策集集合合。常常用用Dk(sk)表表示示第第k阶阶段段从从状状态态sk出发的允许决策集合，显然出发的允许决策集合，显然,uk(sk)Dk(sk)。第39页，共122页，编辑于2022年，星期三决策决策 如在例如在例1第二第二阶阶段中，若从状段中，若从状态态B1出出发发，就可作出三种不同的决策，其允，就可作出三种不同的决策，其允许许决决策集合策集合D2(B1)C1，C2，C3，若，若选选取取的点的点为为C2，则则C2是状是状态态B1在决策在决策u2(B1)作作用下的一个新的状用下的一个新的状态态，记记作作 u2

19、(B1)=C2。第40页，共122页，编辑于2022年，星期三决策决策 最短路线问题中最短路线问题中“决策决策”的示意图的示意图第41页，共122页，编辑于2022年，星期三策略策略 4）策略策略 策策略略是是一一个个按按顺顺序序排排列列的的决决策策组组成成的的集合。集合。由由过过程程的的第第k阶阶段段开开始始到到终终止止状状态态为为止止的过程，称为问题的后部子过程。的过程，称为问题的后部子过程。第42页，共122页，编辑于2022年，星期三最短路线问题最短路线问题“子过程子过程”的示意图的示意图第43页，共122页，编辑于2022年，星期三策略策略 由由每每段段的的决决策策按按顺顺序序排排列

20、列组组成成的的决决策策函函数数序序列列 称称为为k子子过过程程策略，简称子策略，记为策略，简称子策略，记为 ，即，即第44页，共122页，编辑于2022年，星期三策略策略 当当k=1时时，此此决决策策函函数数序序列列称称为为全全过过程程的一个策略，简称策略，记为的一个策略，简称策略，记为 ，即，即第45页，共122页，编辑于2022年，星期三策略策略 在在实实际际问问题题中中，可可供供选选择择的的策策略略有有一一定定的的范范围围，此此范范围围称称为为允允许许策策略略集集合合，用用P表表示示。从从允允许许策策略略集集合合中中找找出出达达到到最最优优效果的策略称为最优策略。效果的策略称为最优策略。

21、第46页，共122页，编辑于2022年，星期三状态转移方程状态转移方程 5）状态转移方程状态转移方程 状状态态转转移移方方程程是是确确定定活活动动过过程程如如何何由由一一个个状状态态演演变变到到另另一一个个状状态态。若若给给定定第第k阶阶段段状状态态变变量量的的值值，如如果果该该段段的的决决策策变变量量uk一一经经确确定定，第第k+1阶阶段段的的状状态态变变量量sk+1的的值值也也就就完完全全确确定定，即即sk+1的的值值随随sk和和uk的的值值变化而变化。变化而变化。第47页，共122页，编辑于2022年，星期三状态转移方程状态转移方程 这种确定的对应关系，记为这种确定的对应关系，记为 上上

22、式式描描述述了了由由k阶阶段段到到k+1阶阶段段的的阶阶段段的的状状态态转转移移规规律律，称称为为状状态态转转移移方方程程。Tk称称为为状状态态转移函数。转移函数。第48页，共122页，编辑于2022年，星期三状态转移方程状态转移方程 如例如例1中，状态转移方程为中，状态转移方程为第49页，共122页，编辑于2022年，星期三指标函数和最优值函数指标函数和最优值函数 6）指标函数和最优值函数指标函数和最优值函数 用用来来衡衡量量所所实实现现过过程程优优劣劣的的一一种种数数量量指标指标，称为指标函数。，称为指标函数。指指标标函函数数是是定定义义在在全全过过程程和和所所有有后后部部子过程子过程上的

23、确定的数量函数。上的确定的数量函数。第50页，共122页，编辑于2022年，星期三最短路线问题最短路线问题“指标函数指标函数”的示意图的示意图第51页，共122页，编辑于2022年，星期三指标函数指标函数 常用常用Vk,n表示，即表示，即第52页，共122页，编辑于2022年，星期三 指指标标函函数数的的最最优优值值，称称为为最最优优值值函函数数，记记为为 它它表表示示从从第第k阶阶段段的的状状态态sk开开始始到到第第n阶阶段段的的终终止止状状态态的的过过程程，采采取取最最优优策策略略所所得得到到的的指指标标函函数数值值，即即最优值函数最优值函数 “opt”是最优化是最优化(optimizat

24、ion)的缩写，可的缩写，可根据题意而取根据题意而取min或或max。第53页，共122页，编辑于2022年，星期三最短路线问题最短路线问题“最优值函数最优值函数”的示意图的示意图第54页，共122页，编辑于2022年，星期三n 当当应应用用动动态态规规划划进进行行求求解解的的多多阶阶段段决决策策问问题题时时，其其指指标标函函数数应应具具有有可可分分离离性性，并并满满足足递递推推关关系系，即即Vk,n可可以以表表示示为为sk、uk、Vk+1,n的函数，记为的函数，记为指标函数的性质指标函数的性质 在实际问题中很多指标函数都满足这个性质。在实际问题中很多指标函数都满足这个性质。第55页，共122

25、页，编辑于2022年，星期三其中其中 表示第表示第j阶段的阶段指标，这时上式可阶段的阶段指标，这时上式可写成写成常见的指标函数形式常见的指标函数形式 (1)过过程程和和它它的的任任一一子子过过程程的的指指标标是是它它所所包包含含的各阶段的指标的和。即的各阶段的指标的和。即第56页，共122页，编辑于2022年，星期三常见的指标函数形式常见的指标函数形式 (2)过过程程和和它它的的任任一一子子过过程程的的指指标标是是它它所所包包含含的的各阶段指标的乘积，即各阶段指标的乘积，即这时就可写成这时就可写成第57页，共122页，编辑于2022年，星期三3.动态规划基本原理动态规划基本原理 下下面面结结合

26、合最最短短路路线线问问题题，介介绍绍动动态态规规划方法的基本思想。划方法的基本思想。第58页，共122页，编辑于2022年，星期三最短路线问题求解思路最短路线问题求解思路最短路线问题求解示意图最短路线问题求解示意图第59页，共122页，编辑于2022年，星期三 最最短短路路线线有有一一个个重重要要特特性性：如如果果由由起起点点A经经过过P点点和和H点点而而到到达达终终点点G是是一一条条最最短短路路线线，则则由由点点P出出发发经经过过H点点到到达达终终点点G的的这这条条子子路路线线，对对于于从从点点P出出发发到到达达终终点点的的所所有有可可能能选选择择的的不不同同路路线线来来说说，必必定定也是最

27、短路线。也是最短路线。第60页，共122页，编辑于2022年，星期三 例例如如，在在最最短短路路线线问问题题中中，若若找找到到了了AB1C2D1E2F2G是是由由A到到G的的最最短短路路线线，则则D1E2F2G应应该该是是由由D1出出发发到到G点点的的所所有有可可能能选选择择的的不不同同路路线中的最短路线。线中的最短路线。第61页，共122页，编辑于2022年，星期三 根根据据最最短短路路线线这这一一特特性性，寻寻找找最最短短路路线线的的方方法法，就就是是从从最最后后一一段段开开始始，用用由由后后向向前前逐逐步步递递推推的的方方法法，求求出出各各点点到到G点点的的最最短短路路线线，最最后后求求

28、得得由由A点点到到G点点的的最最短短路线。路线。第62页，共122页，编辑于2022年，星期三 所所以以，动动态态规规划划的的方方法法是是：从从终终点点逐逐段段向向始始点点方方向向寻寻找找最最短短路路线线的的一一种种方方法法逆推解法逆推解法。动态规划方法示意图动态规划方法示意图第63页，共122页，编辑于2022年，星期三最短路线问题动态规划求解示意图最短路线问题动态规划求解示意图第64页，共122页，编辑于2022年，星期三 为为了了找找出出最最短短路路线线，再再按按计计算算的的顺顺序序反反推推之之，可求出最优决策函数序列，即可求出最优决策函数序列，即找出相应的最短路线为找出相应的最短路线为

29、第65页，共122页，编辑于2022年，星期三 从从上上面面的的计计算算过过程程中中可可以以看看出出：在在求求解解的的各各个个阶阶段段，利利用用了了k阶阶段段与与k+1阶阶段段之之间间的的递推关系：递推关系：第66页，共122页，编辑于2022年，星期三 一一般般情情况况，k阶阶段段与与k+1阶阶段段的的递递推推关关系系式式可写成：可写成：边界条件为第67页，共122页，编辑于2022年，星期三 递递推推关关系系式式(1-1)称称为为动动态态规规划划的的基基本本方程方程。第68页，共122页，编辑于2022年，星期三动态规划方法基本思想动态规划方法基本思想n 在在将将问问题题的的过过程程分分成

30、成几几个个相相互互联联系系的的阶阶段段，并并恰恰当当地地选选取取状状态态变变量量和和决决策策变变量量及及定定义义最最优优值值函函数数的的基基础础上上，把把一一个个大大问问题题化化成成一一族族同同类类型型的的子子问问题题，然然后后逐逐个求解。个求解。第69页，共122页，编辑于2022年，星期三动态规划方法基本思想动态规划方法基本思想n 即即根根据据基基本本方方程程，从从边边界界条条件件开开始始，逐逐段段递递推推寻寻优优，在在每每一一个个子子问问题题的的求求解解中中，均均利利用用了了它它前前面面的的子子问问题题的的最最优优化化结结果果，依依次次进进行行，最最后后一一个个子子问问题题所所得得的的最

31、优解，就是整个问题的最优解。最优解，就是整个问题的最优解。第70页，共122页，编辑于2022年，星期三建立动态规划模型的五个要点建立动态规划模型的五个要点 (1)将问题的过程划分成恰当的阶段；将问题的过程划分成恰当的阶段；(2)正正确确选选择择状状态态变变量量sk，使使它它既既能能描描述述过过程的演变，又要满足无后效性；程的演变，又要满足无后效性；(3)确确定定决决策策变变量量uk及及每每阶阶段段的的允允许许决决策策集集合合Dk(sk)；(4)正确写出状态转移方程；正确写出状态转移方程；第71页，共122页，编辑于2022年，星期三建立动态规划模型的五个要点建立动态规划模型的五个要点 (5)

32、正正确确写写出出指指标标函函数数Vk,n的的关关系系，它它应应满足下面三个性质：满足下面三个性质：是是定定义义在在全全过过程程和和所所有有后后部部子子过过程程上上的数量函数；的数量函数；第72页，共122页，编辑于2022年，星期三 要要具具有有可可分分离离性性，并并满满足足递递推推关关系系,即即 函函数数 对对于于变变量量Vk+1,n要严格单调。要严格单调。建立动态规划模型的五个要点建立动态规划模型的五个要点第73页，共122页，编辑于2022年，星期三其中其中 表示第表示第j j段的指标。它显然是段的指标。它显然是满足指标函数三个性质的。满足指标函数三个性质的。考察动态规划基本方程考察动态

33、规划基本方程 设指标函数是取各阶段指标的和的形式，即设指标函数是取各阶段指标的和的形式，即。第74页，共122页，编辑于2022年，星期三上式可写成上式可写成 当当初初始始状状态态和和过过程程的的策策略略给给定定时时，指指标标函函数数也也就就确确定定了了。因因此此，指指标标函函数数是是初初始始状状态态和和策略的函数。可记为策略的函数。可记为。第75页，共122页，编辑于2022年，星期三其子策略其子策略 可看成是由决策可看成是由决策 和和子策略子策略 组合而成，即 上面递推关系又可写成上面递推关系又可写成第76页，共122页，编辑于2022年，星期三 用用p*k,n(sk)表表示示初初始始状状

34、态态为为sk的的后后部部子子过过程程所有子策略中的最优子策略，则最优值函数为所有子策略中的最优子策略，则最优值函数为 第77页，共122页，编辑于2022年，星期三由于由于同时同时第78页，共122页，编辑于2022年，星期三4.动态规划与其它方法的比较动态规划与其它方法的比较 1）与穷举法的比较与穷举法的比较 2）与静态规划的比较与静态规划的比较第79页，共122页，编辑于2022年，星期三与穷举法相比有以下优点与穷举法相比有以下优点 (1)减减少少了了计计算算量量。计计算算例例1若若用用穷穷举举法法，就就要要对对48条条路路线线进进行行比比较较，运运算算在在计计算算机机上上进进行行时时，比

35、比较较运运算算要要进进行行47次次；求求各各条条路路线线的的距距 离离，即即 使使 用用 逐逐 段段 累累 加加 方方 法法，也也 要要 进进 行行6+12+24+48+48138次加法运算次加法运算。第80页，共122页，编辑于2022年，星期三与穷举法相比有以下优点与穷举法相比有以下优点 用用动动态态规规划划方方法法来来计计算算，比比较较运运算算(从从k=5段段开开始始向向前前算算)共共进进行行3+3+4+4+115次次。每每次次比比较较运运算算相相应应有有两两次次加加法法运运算算，再再去去掉掉中中间间重重复复两两次次(即即B1C1，B2C4各各多多算算了了一一次次)，实实际际只只有有28

36、次次加加法法运运算算。可可见见，动动态态规规划划方方法法比比穷穷举举法法减减少少了了计计算算量量。而而且且随随着着段段数数的增加，计算量将大大地减少。的增加，计算量将大大地减少。第81页，共122页，编辑于2022年，星期三与穷举法相比有以下优点与穷举法相比有以下优点 (2)丰丰富富了了计计算算结结果果。在在上上述述解解法法中中，我我们们得得到到的的不不仅仅仅仅是是由由A点点出出发发到到G点点的的最最短短路路线线及及相相应应的的最最短短距距离离，而而且且得得到到了了从从所所有有各各中中间间点点出出发发到到G点点的的最最短短路路线线及及相相应应的的距距离离。这这就就是是说说，求求出出的的不不是是

37、一一个个最最优优策策略略，而而是是一族的最优策略。一族的最优策略。第82页，共122页，编辑于2022年，星期三与静态规划的比较与静态规划的比较l相同点相同点 动动态态规规划划、线线性性规规划划和和非非线线性性规规划划都都属属于于数数学学规规划划范范围围，研研究究对对象象本本质质上上都都是是求求极极值值问问题题，都是利用迭代法去逐步求解。，都是利用迭代法去逐步求解。第83页，共122页，编辑于2022年，星期三l不同点不同点 1）线线性性规规划划和和非非线线性性规规划划研研究究的的问问题题通通常常与与时时间间无无关关，故故又又称称为为静静态态规规划划。线线性性规规划划迭迭代代中中的的每每一一步

38、步是是就就问问题题的的整整体体加加以以改改善的。善的。第84页，共122页，编辑于2022年，星期三l不同点不同点 2）动动态态规规划划研研究究的的问问题题与与时时间间有有关关，研研究究具具有有多多阶阶段段决决策策过过程程的的一一类类问问题题，将将问问题题的的整整体体按按时时间间或或空空间间的的特特征征分分成成若若干干个个前前后后衔衔接接的的时时空空阶阶段段，把把多多阶阶段段决决策策问问题题表表示示为为前前后后有有关关联联的的一一系系列列单单阶阶段段决决策策问问题题，然然后后逐逐个个加加以以解解决，从而求出整个问题的最优决策序列。决，从而求出整个问题的最优决策序列。第85页，共122页，编辑于

39、2022年，星期三l不同点不同点 3）动动态态规规划划对对于于某某些些静静态态问问题题，也也可可以以人人为为地地引引入入时时间间因因素素，把把它它看看作作是是按按阶阶段段进进行行的的一一个个动动态态规规划划问问题题，这这就就使使得得动动态态规规划划成成为为求求解解某某些些线线性性、非非线线性性规规划划的的有有效效方方法。法。第86页，共122页，编辑于2022年，星期三5.动态规划的理论基础动态规划的理论基础 动态规划的理论基础是什么？动态规划的理论基础是什么？第87页，共122页，编辑于2022年，星期三动态规划的最优性原理动态规划的最优性原理 动动态态规规划划的的最最优优性性原原理理：“作

40、作为为整整个个过过程程的的最最优优策策略略具具有有这这样样的的性性质质：即即无无论论过过去去的的状状态态和和决决策策如如何何，对对前前面面的的决决策策所所形形成成的的状状态态而而言言，余余下下的的诸诸决决策策必必须须构构成成最最优优策策略略。”简简言言之之，一一个个最最优优策策略略的的子子策策略略总总是是最最优优的的。第88页，共122页，编辑于2022年，星期三 动动态态规规划划的的最最优优性性定定理理：对对于于阶阶段段数数为为n的的多多阶阶段段决决策策过过程程，为为最最优优策策略略的的充充要要条条件件是是对对任任意意一一个个k(0kn-1)，有，有动态规划的动态规划的最优性定理最优性定理第

41、89页，共122页，编辑于2022年，星期三动态规划的动态规划的最优性定理最优性定理第90页，共122页，编辑于2022年，星期三 上上式式中中，它它是是由由给给定定的的初初始始状状态态s0和和子子策策略略P0,k-1所所确确定定的的k阶阶段段状状态态。当当V是是效效益益函函数数时时，opt取取max；当当V是是损损失失函数时，函数时，opt取取min。动态规划的动态规划的最优性定理最优性定理第91页，共122页，编辑于2022年，星期三6.动态规划的具体解法动态规划的具体解法n 在在应应用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题时，有两种具体的求解方法：时，有两种具体的求解方法

42、：n 1）逆推解法；逆推解法；n 2）顺）顺推解法；推解法；n 3）算例）算例第92页，共122页，编辑于2022年，星期三动态规划逆推解法的基本方程动态规划逆推解法的基本方程动态规划逆推解法的基本方程为动态规划逆推解法的基本方程为：边界条件为边界条件为式中式中第93页，共122页，编辑于2022年，星期三 其其求求解解过过程程为为：根根据据边边界界条条件件，从从k=n开开始始，由由后后向向前前逆逆推推，从从而而逐逐步步可可求求得得各各段段的的最最优优决决策策和和相相应应的的最最优优值值，最最后后求求出出 时时，就得到整个问题的最优解。就得到整个问题的最优解。求解过程求解过程第94页，共122

43、页，编辑于2022年，星期三算例算例例例3 用逆推解法求解下面用逆推解法求解下面问题问题第95页，共122页，编辑于2022年，星期三算例算例解解:按按问问题题的的变变量量个个数数划划分分阶阶段段，把把它它看看作作为为一个三阶段决策问题。一个三阶段决策问题。设设状状态态变变量量为为s1，s2，s3和和s4，并并记记s1=c；取取问问题题中中的的变变量量x1，x2和和x3为为决决策策变变量量；各各阶阶段段指指标标函函数数按按乘乘积积方方式式结结合合。令令最最优优值值函函数数fk(sk)表表示示为为第第k阶阶段段的的初初始始状状态态为为sk，从从k阶阶段段到到3阶阶段段所得到的最大值。所得到的最大

44、值。第96页，共122页，编辑于2022年，星期三算例算例设设则有则有第97页，共122页，编辑于2022年，星期三及最优解及最优解算例算例 用逆推解法，从后向前依次有用逆推解法，从后向前依次有第98页，共122页，编辑于2022年，星期三由由 可得可得算例算例(舍去舍去)第99页，共122页，编辑于2022年，星期三所以，所以，为极大值点。此时为极大值点。此时算例算例由于由于第100页，共122页，编辑于2022年，星期三算例算例仿前分析，可得仿前分析，可得第101页，共122页，编辑于2022年，星期三算例算例由于已知由于已知 根根据据计计算算的的顺顺序序反反推推算算，可可得得各各阶阶段段

45、的的最优决策和最优值。最优决策和最优值。第102页，共122页，编辑于2022年，星期三算例算例即即由由可得可得第103页，共122页，编辑于2022年，星期三算例算例可得可得由由第104页，共122页，编辑于2022年，星期三算例算例因此得到最优解为因此得到最优解为最大值为最大值为第105页，共122页，编辑于2022年，星期三动态规划顺推解法的基本方程动态规划顺推解法的基本方程动态规划顺推解法的基本方程为动态规划顺推解法的基本方程为：边界条件为边界条件为式中式中第106页，共122页，编辑于2022年，星期三 其其求求解解过过程程为为：根根据据边边界界条条件件，从从k=1开开始始，由由前前

46、向向后后顺顺推推，逐逐步步求求得得各各段段的的最最优优决决策策和和相相应应的的最最优优值值，最最后后求求出出 ，就就得得到到整个问题的最优解。整个问题的最优解。求解过程求解过程第107页，共122页，编辑于2022年，星期三 例4 将例将例3用顺推解法解之。用顺推解法解之。解解：设设s4=c,令令最最优优值值函函数数 表表示示第第k阶阶段段末末的的状状态态为为sk+1，从从1阶阶段段到到k阶阶段段的的最最大大值值。设设算例算例则有则有第108页，共122页，编辑于2022年，星期三算例算例用顺推解法，从前向后依次有用顺推解法，从前向后依次有及最优解及最优解第109页，共122页，编辑于2022

47、年，星期三算例算例最优解最优解最优解最优解第110页，共122页，编辑于2022年，星期三由于已知由于已知 ，故易得到最优解为，故易得到最优解为算例算例最大值为最大值为第111页，共122页，编辑于2022年，星期三逆推解法与顺推解法的取舍逆推解法与顺推解法的取舍l关键：动态规划递推关系式的构建关键：动态规划递推关系式的构建l逆逆推推形形式式，当当初初始始状状态态给给定定时时，用用逆逆推推比比较较方便方便l顺顺推推形形式式，当当终终止止状状态态给给定定时时，用用顺顺推推比比较方便较方便第112页，共122页，编辑于2022年，星期三算例算例例例5 用动态规划方法解以下问题。用动态规划方法解以下

48、问题。第113页，共122页，编辑于2022年，星期三解解：按按问问题题中中变变量量的的个个数数分分为为三三个个阶阶段段。设设状状态态变变量量为为 ，并并记记 ；取取 为为各各阶阶段段的的决决策策变变量量；各各阶阶段段指指标标函函数数按按加加法法方方式式结结合合。最最优优值值函函数数 表表示示第第k阶阶段段的的结结束束状状态态为为sk，从，从1阶段至阶段至k阶段的最大值。阶段的最大值。算例算例第114页，共122页，编辑于2022年，星期三算例算例设设则有则有第115页，共122页，编辑于2022年，星期三算例算例用顺推方法，从前向后依次有用顺推方法，从前向后依次有第116页，共122页，编辑

49、于2022年，星期三 因因该该点点不不在在允允许许决决策策集集合合内内，故故无无须须判判别别。因因而而 的的最最大大值值必必在在两两个个端端点点上上选选取。取。算例算例由由解得解得第117页，共122页，编辑于2022年，星期三 因因此此，的的最最大大值值点点在在 处处，故故得得到到 及相应的最优解及相应的最优解 。算例算例由于由于第118页，共122页，编辑于2022年，星期三算例算例由由 ，解得，解得第119页，共122页，编辑于2022年，星期三 由由于于 ，故故该该点点为为极极小小值值点点。而而算例算例故故 的最大值点在的最大值点在 处，处，所以得所以得及相应的最优解及相应的最优解第120页，共122页，编辑于2022年，星期三 由由于于s3 9，故故s3=9时时，才才能能达达到到最最大大值值。所所以以 为为最最大大值值。再再根根据据计计算算的的顺序反推算可求得最优解为顺序反推算可求得最优解为算例算例最大值为最大值为第121页，共122页，编辑于2022年，星期三课后作业安排课后作业安排n第八章习题第八章习题:8.2，8.3，8.4(2)，8.5(3,6).第122页，共122页，编辑于2022年，星期三