《最优化技术基础精选PPT.ppt》由会员分享，可在线阅读，更多相关《最优化技术基础精选PPT.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于最优化技术基础关于最优化技术基础第1页，讲稿共27张，创作于星期二最优策略：对应于一个策略，可以由一个量化的指标来确定这个策略对应的效果，不同的策略有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。多阶段决策过程最优化的目标是要达到整个活动过程的总体效多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者在每段决策到下一段的决策，以至于影响总体效果，所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影
2、响，从而作时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。决策方法。应指出，动态规划不象线性规划那样有一个标准的数学表达应指出，动态规划不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处式和明确定义的一组规则，而必须对具体问题进行具体分析处理，除了要对基本概念和方法正确理解外，应以丰富的想象力理，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。去建立模型，用创造性的技巧去求解。第2页，讲稿共
3、27张，创作于星期二(2)(2)多阶段决策问题举例多阶段决策问题举例 a)a)a)a)工工工工厂厂厂厂生生生生产产产产过过过过程程程程:为为了了取取得得全全年年最最佳佳经经济济效效益益，在在全全年年的的生生产产过过程程中中，根根据据市市场场需需求求，逐逐月月或或者者逐逐季季度度地地根根据据库库存存和和需需求求情情况况决定生产计划安排。决定生产计划安排。b)b)b)b)设设设设备备备备更更更更新新新新问问问问题题题题:需需要要综综合合权权衡衡决决定定设设备备的的使使用用年年限限，使使总总的的经经济济效效益最好益最好 c)c)c)c)连连连连续续续续生生生生产产产产过过过过程程程程的的的的控控控控
4、制制制制问问问问题题题题:一一般般化化工工生生产产过过程程中中，常常包包含含一一系系列列完完成成生生产产过过程程的的设设备备，前前一一工工序序设设备备的的输输出出则则是是后后一一工工序序设设备备的的输输入入，因因此此，应应该该如如何何根根据据各各工工序序的的运运行行工工况况，控控制制生生产产过程中各设备的输入和输出，以使总产量最大。过程中各设备的输入和输出，以使总产量最大。以上问题的发展过程都与时间因素有关，因此阶段的以上问题的发展过程都与时间因素有关，因此阶段的以上问题的发展过程都与时间因素有关，因此阶段的以上问题的发展过程都与时间因素有关，因此阶段的划分常取时间区段来表示，并且各个阶段上的
5、决策往往也划分常取时间区段来表示，并且各个阶段上的决策往往也划分常取时间区段来表示，并且各个阶段上的决策往往也划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就是与时间因素有关，这就是与时间因素有关，这就是与时间因素有关，这就是“动态动态动态动态”的含义，所以把处理这类的含义，所以把处理这类的含义，所以把处理这类的含义，所以把处理这类问题的方法称为动态规划方法。问题的方法称为动态规划方法。问题的方法称为动态规划方法。问题的方法称为动态规划方法。第3页，讲稿共27张，创作于星期二 d d d d）资资资资源源源源分分分分配配配配问问问问题题题题:某某工工业业部部门门拟拟对对其
6、其所所属属企企业业进进行行稀稀缺缺资资源源分分配配，为为此此需需要要制制定定出出收收益益最最大大的的资资源源分分配配方方案案。这这种种问问题题与与时时间间因因素素无无关关，不不属属动动态态决决策策，但但我我们们可可以以人人为为地地规规定定一一个个资资源源分分配配的的阶阶段段和和顺顺序序，从从而而使使其其变变成成一一个多阶段决策问题。个多阶段决策问题。e e e e）运运运运输输输输网网网网络络络络问问问问题题题题:运运输输网网络络连连线线上上的的数数字字表表示示两两地地距距离离(也也可可以以是是运运费费、时时间间等等)，要要求求从从A A 至至E E的的最最短短路路线线。这这种种运运输输网网络
7、络问问题题也也是是静静态态决决策策问问题题。但但是是，按按照照网网络络中中点点的的分分布布，可可以把它分为以把它分为几几个阶段，而作为多阶段决策问题来研究。个阶段，而作为多阶段决策问题来研究。第4页，讲稿共27张，创作于星期二 (3)(3)(3)(3)动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通通通通常常常常多多多多阶阶阶阶段段段段决决决决策策策策过过过过程程程程的的的的发发发发展展展展是是是是通通通通过过过过状状状状态态态态的的的的一一一一系系系系列列列列变变变变换换换换来来来来实实实实现现现现的
8、的的的。一一一一般般般般情情情情况况况况下下下下，系系系系统统统统在在在在某某某某个个个个阶阶阶阶段段段段的的的的状状状状态态态态转转转转移移移移除除除除与与与与本本本本阶阶阶阶段段段段的的的的状状状状态态态态和和和和决决决决策策策策有有有有关关关关外外外外，还还还还可可可可能能能能与与与与系系系系统统统统过过过过去去去去经经经经历历历历的的的的状状状状态态态态和和和和决决决决策策策策有有有有关关关关。因因因因此此此此，问题的求解就比较困难复杂。问题的求解就比较困难复杂。问题的求解就比较困难复杂。问题的求解就比较困难复杂。适适适适合合合合于于于于用用用用动动动动态态态态规规规规划划划划方方方方
9、法法法法求求求求解解解解的的的的只只只只是是是是一一一一类类类类特特特特殊殊殊殊的的的的多多多多阶阶阶阶段段段段决决决决策策策策问问问问题题题题，即即即即具具具具有有有有“无无无无后后后后效效效效性性性性”(马马马马尔尔尔尔柯柯柯柯夫夫夫夫性性性性)的的的的多多多多阶阶阶阶段段段段决决决决策策策策过过过过程程程程。所所所所谓谓谓谓无无无无后后后后效效效效性性性性，是是是是指指指指系系系系统统统统从从从从某某某某个个个个阶阶阶阶段段段段往往往往后后后后的的的的发发发发展展展展，仅仅仅仅由由由由本本本本阶阶阶阶段段段段所所所所处处处处的的的的状状状状态态态态及及及及其其其其往往往往后后后后的的的的
10、决决决决策策策策所所所所决决决决定定定定，与与与与系系系系统统统统以以以以前前前前经经经经历历历历的的的的状状状状态态态态和和和和决决决决策策策策(历历历历史史史史)无无无无关关关关。多多多多阶阶阶阶段段段段决决决决策策策策过过过过程程程程特特特特点点点点:状态状态 x x1 1阶段阶段1 1T T1 1决策决策u u1 1状态状态 x x2 2决策决策u u2 2阶段阶段2 2T T2 2状态状态 x x3 3.状态状态 x xk k决策决策u uk k阶段阶段k kT Tk k状态状态 x xk k+1+1.状态状态 x xn n决策决策u un n阶段阶段n nTnTn状态状态 x xn
11、 n+1+1第5页，讲稿共27张，创作于星期二(4)(4)动态规划方法导引动态规划方法导引例例1 1 1 1：为为了了说说明明动动态态规规划划的的基基本本方方法法和和特特点点，以以上上面面运输网络图为例运输网络图为例,讨论求最短路问题的方法。讨论求最短路问题的方法。讨论求最短路问题的方法。讨论求最短路问题的方法。第第一一种种方方法法枚枚举举法法.它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果，再再一一一一比比较较，求求出出最最优优方方案案。这这里里从从A A到到E E的的路路程程可可以以分分为为5 5个个阶阶段段。各各阶阶段段走走法法:第第1 1段段有
12、有3 3种种，第第2 2段段各各有有3 3种种，第第3 3段段各各有有2 2种种，第第4 4段段各各1 1种种，因因此此共共有有332133211818条条可可能能的的路路线线，分分别别算算出出各各条条路路线线的的距距离离进进行行比比较较，可可知知最最优优路路线线是是A A B B2 2 C C1 1 DD1 1 E E,最短距离是最短距离是1919 显显然然，如如果果组组成成网网络络的的节节点点很很多多时时，用用穷穷举举法法求求最最优优路路线线的的计计算算量量将将会会十十分分庞庞大大，其其中中包包含含许许多多重重复复计计算算枚枚枚枚举举举举法法法法虽虽虽虽可找出最优方案，但不是个好算法可找出
13、最优方案，但不是个好算法可找出最优方案，但不是个好算法可找出最优方案，但不是个好算法第6页，讲稿共27张，创作于星期二 第第第第二二二二种种种种方方方方法法法法:“:“:“:“局局局局部部部部最最最最优优优优路路路路径径径径”法法法法.说说某某人人从从某某站站出出发发，他他选选择择“逢逢近近便便走走”的的决决策策，以以为为只只要要“局局部部最最优优”,就就会会达达到到”“整整体体最最优优”，所所取取决决策策必必是是A A B B3 3 C C3 3 DD1 1 E E,但但全全程程长长度度是是2525；显显然然，这这种种方方法法的的结结果果常常是是错错误误的的局局局局部部部部最最最最优优优优法
14、则是错误方法法则是错误方法法则是错误方法法则是错误方法.第第第第三三三三种种种种方方方方法法法法动动动动态态态态规规规规划划划划方方方方法法法法.首首先先将将问问题题划划分分为为5 5个个阶阶段段，每每次次的的选选择择总总是是综综合合后后继继过过程程的的一一并并最最优优进进行行考考虑虑，在在各各段段所所有有可可能能状状态态的的最最优优后后继继过过程程都都已已求求得得的的情情况况下下，全全程程的的最最优优路路线线便便也也随随之之得得到到。动动态态规规划划方方法法总总是是从从过过程程的的最最后后阶阶段段开开始始考考虑虑，然然后后逆逆着着实实际际过过程程发发展展的的顺顺序序，逐逐段段向向前前递递递递
15、推推推推计计计计算算算算直至始点。直至始点。动动动动态态态态规规规规划划划划方方方方法法法法属属属属较较较较科科科科学学学学有有有有效效效效的的的的算算算算法法法法，计计算算过过程程中中，系系统统地地删删去去了了所所有有中中间间非非最最优优的的方方案案组组合合，从从而而使使计计算算量量比比枚枚枚枚举举举举法法法法大为减少。大为减少。第7页，讲稿共27张，创作于星期二 2.动态规划的基本概念 使使用用动动态态规规划划方方法法解解决决多多阶阶段段决决策策问问题题，首首先先要要将将实实际际问问题题写写成成动动态态规规划划模模型型，需需要要对对动动态态规规划划的的一一些些基基本本术术语语加加以说明和定
16、义：以说明和定义：1.1.1.1.阶段阶段阶段阶段 为为了了便便于于求求解解和和表表示示决决策策及及过过程程的的发发展展顺顺序序，而而把把所所给给问问题题恰恰当当地地划划分分为为若若干干个个相相互互联联系系又又有有区区别别的的子子问问题题，称称之之为为多多段段决决策策问问题题的的阶阶段段。一一个个阶阶段段，就就是是需需要要作作出出一一个个决决策策的的子子问问题题，通通常常，阶阶段段是是按按决决策策进进行行的的时时间间或或空空间间上上先后顺序划分的。先后顺序划分的。2.2.2.2.状态和状态变量状态和状态变量状态和状态变量状态和状态变量 用用以以描描述述系系统统在在某某特特定定的的时时间间与与空
17、空间间域域中中所所处处位位置置及及运运动动特特征征的的量量，称称为为状状态态。每每个个阶阶段段的的状状态态可可分分为为初初始始状状态态和和终终止止状状态态，阶阶段段k k的的初初始始状状态态记记作作s sk k，终终止止状状态态记记为为s sk+1k+1。但但通通通通常常常常定定定定义义义义阶阶阶阶段段段段的的的的状状状状态态态态即即即即指指指指其其其其初初初初始始始始状状状状态态态态，故故阶阶段段k k的终止状态的终止状态s sk+1k+1为为阶段阶段k+1k+1的初始状态的初始状态。描描述述过过程程k k的的状状态态变变量量称称为为状状态态变变量量s sk k ，其其取取值值范范围围称称为
18、为可可能状态集能状态集S Sk k,即即s sk kS Sk k。第8页，讲稿共27张，创作于星期二 3.3.决策和决策变量决策和决策变量决策和决策变量决策和决策变量 决决策策是是状状态态的的选选择择，是是决决策策者者从从给给定定阶阶段段状状态态出出发发对对下下一一阶阶段段状态作出的选择。状态作出的选择。描描述述决决策策变变化化的的量量称称之之决决策策变变量量，和和状状态态变变量量一一样样，决决策策变变量量可可以以用用一一个个数数或或一一向向量量来来描描述述，也也可可以以是是状状态态变变量量的的函函数数，记记以以u uk k=u uk k(s sk k)，表示阶段，表示阶段k k状态状态s s
19、k k时的决策变量。时的决策变量。决决策策变变量量的的取取值值也也有有一一定定的的允允许许范范围围，称称之之允允许许决决策策集集合合U Uk k(s sk k),),u uk k(s sk k)U Uk k(s sk k)。4.4.策略策略策略策略 全全过过程程策策略略(Policy)(Policy)是是依依次次进进行行的的全全部部n n个个阶阶段段决决策策构构成成的的决决策策序序列列，表表示示为为p p1,1,n n u u1 1,u u2 2,u un n;从从k k阶阶段段到到第第n n阶阶段段，依依次次构构成成的的决决策策序序列列称称为为k k k k部部部部子子子子策策策策略略略略,
20、表表示示为为p pk,nk,n u uk k,u uk k+1+1,u un n ，显显然然当当k k=1=1时的时的k k部子策略就是全过程策略。部子策略就是全过程策略。在在实实际际问问题题中中，由由于于在在各各个个阶阶段段可可供供选选择择的的决决策策有有许许多多个个，因因此此，它它们们的的不不同同组组合合就就构构成成了了许许多多可可供供选选择择的的决决策策序序列列(策策略略)，它它们们组组成成”允允许许策策略略集集”，记记作作P P1,1,n n ，从从中中找找出出具具有有最最优优效效果果的的策策略略称称为为最最优优策策略。略。第9页，讲稿共27张，创作于星期二 5.5.5.5.状态转移方
21、程状态转移方程状态转移方程状态转移方程 系系统统在在阶阶段段k k处处于于状状态态s sk k，执执行行决决策策u uk k(s(sk k)的的结结果果是是系系统统状状态态的的转转移移，即即系系统统由由阶阶段段k k的的初初始始状状态态s sk k转转移移到到终终止止状状态态s sk k+1+1，或或者者说由说由k k阶段的状态阶段的状态s sk k转移到了转移到了k k+1+1阶段的状态阶段的状态s sk k+1+1。对对于于具具有有无无后后效效性性的的多多阶阶段段决决策策过过程程,系系统统由由阶阶段段k k到到阶阶段段k k+1+1的的状状态态转转移移完完全全由由阶阶段段k k的的状状态态
22、s sk k和和决决策策u uk k(s(sk k)所所确确定定，与与系系统统过过去去的的状状态态s s1 1,s s2 2,s sk k-1-1及及其其决决策策u u1 1(s s1 1),),u u2 2(s s2 2)u uk k-1-1(s sk k-1-1)无无关关。系统状态的这种转移，用数学公式描述即有：系统状态的这种转移，用数学公式描述即有：(1)式式式式(1)(1)称为多阶段决策过程的称为多阶段决策过程的称为多阶段决策过程的称为多阶段决策过程的状态转移方程状态转移方程状态转移方程状态转移方程。有些问题的状态转移方。有些问题的状态转移方。有些问题的状态转移方。有些问题的状态转移方
23、程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。的。的。的。第10页，讲稿共27张，创作于星期二6.6.指标函数和最优解指标函数和最优解指标函数和最优解指标函数和最优解 指标函数是用来衡量策略效果的某种数量指标。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用等等。(1)(1)阶段指标函数:用g gk k(sk,u,uk)表示第k k段段处处于于s sk状态且
24、所作决策为u uk k(s sk k)时时的的指指标标，它它就就是是第第k k段指标函数，简记为g gk。(2)过程指标函数（也称目标函数）:用Rk(s sk k,uk)表示第k k子子过过程程的的指指标标函函数数。如如运运运运输输输输网网网网络络络络图图的的Rk k(s sk k,u uk)表示处于第k k段s sk状态且所作决策为u uk时时，从从sk点点到到终终点点E的距离。由此可见，R Rk k(sk k,u uk k)不仅跟当前状态sk k有有关关，还还跟跟该该子子过过程程策策略略p pk k(sk k)有有关关，因因此此它它是是sk和pk k(sk k)的函数，应表示为:第11页，
25、讲稿共27张，创作于星期二 用f fk(sk)表示第表示第k k子过程指标函数子过程指标函数 在状态在状态s sk k下的最优值下的最优值,即 与它相应的子策略称为s sk状态下的最优子策略，简简记为:特别当k k=1=1且且s1 1取值唯一时，f1(s s1 1)就是问题的最优值，而p p1*就是最优策略。就是最优策略。我们把最优策略和最优值统称为问题的最优解。第12页，讲稿共27张，创作于星期二7.7.多阶段决策问题的数学模型多阶段决策问题的数学模型多阶段决策问题的数学模型多阶段决策问题的数学模型 综综上上所所述述，适适于于应应用用动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决
26、决策策问问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:（5）模型说明对于给定的多阶段决策过程，求取一个最优策略模型说明对于给定的多阶段决策过程，求取一个最优策略(决策序决策序列列 )，使之既满足全部约束条件，又使目标函数取，使之既满足全部约束条件，又使目标函数取得极值，同时，执行该最优策略时，过程状态演变序列即最优路得极值，同时，执行该最优策略时，过程状态演变序列即最优路线线 ,按上述定义，所谓最优决策是指它们按上述定义，所谓最优决策是指它们在全过程上整体最优在全过程上整体最优第13页，讲稿共27张，创作于星期二8.8.最优
27、化原理最优化原理 （贝尔曼最优化原理）（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对对于于最最优优策策略略过过程程中中的的任任意意状状态态而而言言，无无论论其其过过去去的的状状态态和和决决策策如如何何，余余下下的的诸诸决决策策必必构构成成一一个个最最优优子子策策略略。该原理的具体解释是，若某一全过程最优策略为：则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为第14页，讲稿共27张，创作于星期二贝尔曼最优化原理概念贝尔曼最优化原理概念:如图如图,如果已经给出从点如果已经给出从点A到点到点C的的最优轨迹，那么从任一中
28、间点最优轨迹，那么从任一中间点B到点到点C的部分轨迹必须是从的部分轨迹必须是从B到到C的最优轨迹。的最优轨迹。设给出路线设给出路线-是从是从A到到C的最优路线，根据贝尔曼原的最优路线，根据贝尔曼原理，则路线理，则路线 是从是从B到到C的最优路线。的最优路线。证证:用反证法用反证法,假设某条其它假设某条其它路线，例如路线，例如 是从是从B到到C的最的最优路线，那么，路线优路线，那么，路线I-比路比路线线I-有更小的费用。但这有更小的费用。但这与与I-是从是从A到到C最优路线的前最优路线的前提相矛盾，因此提相矛盾，因此必是从必是从B到到C的最优路线的最优路线贝尔曼阐述贝尔曼阐述:“一个最优策略有这
29、样的特性，不论初始状态和初始决策如一个最优策略有这样的特性，不论初始状态和初始决策如何，相对于第一个决策所形成的状态来说，余下的决策必定构成一个最优何，相对于第一个决策所形成的状态来说，余下的决策必定构成一个最优策略策略”。第15页，讲稿共27张，创作于星期二(1)(1)应应应应将将将将实实实实际际际际问问问问题题题题恰恰恰恰当当当当地地地地分分分分割割割割成成成成n个个个个子子子子问问问问题题题题(n个个个个阶阶阶阶段段段段)。通通通通常常常常是是是是根据时间或空间而划分的。根据时间或空间而划分的。根据时间或空间而划分的。根据时间或空间而划分的。(2)(2)正正正正确确确确地地地地定定定定义
30、义义义状状状状态态态态变变变变量量量量sk，使使使使它它它它既既既既能能能能正正正正确确确确地地地地描描描描述述述述过过过过程程程程的的的的状状状状态态态态，又又又又能能能能满满满满足足足足无无无无后后后后效效效效性性性性动动动动态态态态规规规规划划划划中中中中的的的的状状状状态态态态变变变变量量量量必必必必须须须须具具具具备备备备以以以以下下下下三个特征：三个特征：三个特征：三个特征：a)a)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。b)b)b)b)要要要要满满满满足足足足无无无无后后后后效
31、效效效性性性性。即即即即如如如如果果果果在在在在某某某某个个个个阶阶阶阶段段段段状状状状态态态态已已已已经经经经给给给给定定定定，那那那那么么么么在在在在该该该该阶阶阶阶段段段段以以以以后后后后，过过过过程程程程的的的的发发发发展展展展不不不不受受受受前前前前面面面面各各各各段段段段状状状状态态态态的的的的影影影影响响响响，如如如如果果果果所所所所选选选选的的的的变变变变量量量量不不不不具具具具备备备备无无无无后后后后效效效效性性性性，就就就就不不不不能能能能作作作作为为为为状状状状态态态态变变变变量量量量来来来来构造动态规划的模型。构造动态规划的模型。构造动态规划的模型。构造动态规划的模型。
32、c)c)要要满满足足可可知知性性。即即所所规规定定的的各各段段状状态态变变量量的的值值，可以直接或间接地测算得到。可以直接或间接地测算得到。3.动态规划方法的基本步骤第16页，讲稿共27张，创作于星期二(3)正正正正确确确确地地地地定定定定义义义义决决决决策策策策变变变变量量量量及及及及各各各各阶阶阶阶段段段段的的的的允允允允许许许许决决决决策策策策集集集集合合合合Uk(s(sk).).根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如如线线性性与与非非线线性性规规划划)转转换换为为动动态态规规划划模模型型时时，常常取取前前者者的的变变量量x x x xj
33、j j j为为后后者者的决策变量的决策变量u uk k k k。(4)(4)能能够够正正确确地地写写出出状状态态转转移移方方程程。如果给定第k阶段状态变量sk的的值值，则则该该段段的的决决策策变变量量u uk一经确定，第k k+1段段的的状状态态变变量量s sk+1+1的值也就完全确定，即有sk k+1+1=Tk k(s sk,u uk)(5)(5)正正正正确确确确地地地地构构构构造造造造出出出出目目目目标标标标函函函函数数数数.例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然满足递推关系：第17页，讲稿共27张，创作于星期二求最短路径4.动态规划方法应用举例第18页，
34、讲稿共27张，创作于星期二 将将问问题题分分成成五五个个阶阶段段，第第k k k k阶阶段段到到达达的的具具体体地地点点用用状状态态变变量量x xk k表表示示，例例如如：x x2 2 2 2=B=B3 3表表示示第第二二阶阶段段到到达达位位置置B B3 3 3 3，等等。这里状态变量取字符值而不是数值。，等等。这里状态变量取字符值而不是数值。，等等。这里状态变量取字符值而不是数值。，等等。这里状态变量取字符值而不是数值。将将将将决决决决策策策策定定定定义义义义为为为为到到到到达达达达下下下下一一一一站站站站所所所所选选选选择择择择的的的的路路路路径径径径，例例例例如如如如目目目目前前前前的的
35、的的状状状状态是态是态是态是x x x x2 2 2 2=B=B3 3 3 3，这时决策允许集合包含三个决策，它们是，这时决策允许集合包含三个决策，它们是，这时决策允许集合包含三个决策，它们是，这时决策允许集合包含三个决策，它们是 D D2 2(x x2 2)=)=D D2 2(B B3 3)=)=B B3 3C C1 1,B B3 3C C2 2,B B3 3C C3 3 最优指标函数最优指标函数最优指标函数最优指标函数f f f fk k(x(x(x(xk k)表示从目前状态到表示从目前状态到E E的最短路径。的最短路径。的最短路径。的最短路径。终端条件为终端条件为 f f5 5(x(x5
36、 5)=f)=f5 5(E)=0(E)=0其含义是从其含义是从E E E E到到E E E E的最短路径为的最短路径为0 0 0 0。第19页，讲稿共27张，创作于星期二从从f f5 5(x(x5 5)到到f f4 4(x(x4 4)的递推过程用下表表示：的递推过程用下表表示：第四阶段的递推方程为：第四阶段的递推方程为：在上表中，在上表中，在上表中，在上表中，*表示最优值，由于决策允许集合表示最优值，由于决策允许集合表示最优值，由于决策允许集合表示最优值，由于决策允许集合D4 4(x4 4)中的决中的决策是唯一的，因此这个值就是最优值。策是唯一的，因此这个值就是最优值。第20页，讲稿共27张，
37、创作于星期二 由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：f4(x4)的表达式的表达式D15D1Ex4f4(x4)最优决策 d4*D22D2E第21页，讲稿共27张，创作于星期二从从f f4 4(x(x4 4)到到f f3 3(x(x3 3)的递推过程用表格表示如下：的递推过程用表格表示如下：第三阶段的递推方程为：第三阶段的递推方程为：第22页，讲稿共27张，创作于星期二由此得到由此得到由此得到由此得到f f3 3 3 3(x x x x3 3)的表达式的表达式的表达式的表达式,取值用列表表示取值用列表表示：第23页，讲稿共27张，创作于星期二第二阶段的递推方程为：第
38、二阶段的递推方程为：从从f f3 3(x x3 3)到到f f2 2(x x2 2)的递推过程用表格表示如下：的递推过程用表格表示如下：第24页，讲稿共27张，创作于星期二由此得到由此得到f f f f2 2 2 2(x x2 2 2 2)的表达式的表达式,取值用列表表示取值用列表表示取值用列表表示取值用列表表示：x x2 2f f2 2(x(x2 2)最优决策最优决策d d2 2*B B1 12020B B1 1C C1 1B B2 21414B B2 2C C1 1B B3 31919B B3 3C C2 2第25页，讲稿共27张，创作于星期二从从f f2 2(x x2 2)到到f f1 1(x x1 1)的递推过程用表格表示如下：的递推过程用表格表示如下：第一阶段的递推方程为：第一阶段的递推方程为：第26页，讲稿共27张，创作于星期二12.04.2023感感谢谢大大家家观观看看第27页，讲稿共27张，创作于星期二