最优化技术基础课件.ppt

《最优化技术基础课件.ppt》由会员分享，可在线阅读，更多相关《最优化技术基础课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于最优化技术基础关于最优化技术基础第1页，此课件共27页哦最优策略：对应于一个策略，可以由一个量化的指标来确定这个策略对应的效果，不同的策略有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者在每段决策时不应仅考虑本阶段最优，以至于影响总体效果，所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑

2、对最终目标的影响，从而作出对全局来讲是最优的决策。动态还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。规划就是符合这种要求的一种决策方法。应指出，动态规划不象线性规划那样有一个标准的数学表达式和应指出，动态规划不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理，除了明确定义的一组规则，而必须对具体问题进行具体分析处理，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。用创造性的技巧去求解。第2页，此课件共27页哦

3、(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)动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通通通通常常常常多多多多阶阶阶阶段段段段决决决决策策策策过过过过程程程程的的的的发发发发展展展展是是是是通通通通过过过过状状状状态态态态的的的的一一一一系系系系列列列列变变变变换换换换来来来来实实实实现现现现的的的的。一一一一般般般般情情情情况况况况下下下下，系系系系统统统统在在在在某某某某个个个个阶阶阶阶段段段段的的的的状状状

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 n+1+1第5页，此课件共27页哦(4)(4)动态规划方法导引动态规划方法导引例例例例1 1 1 1：为为了了说说明明

11、动动态态规规划划的的基基本本方方法法和和特特点点，以以上上面面运输网络图为例运输网络图为例,讨论求最短路问题的方法。讨论求最短路问题的方法。第第一一种种方方法法枚枚举举法法.它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果，再再一一一一比比较较，求求出出最最优优方方案案。这这里里从从A A到到E E的的路路程程可可以以分分为为5 5个个阶阶段段。各各阶阶段段走走法法:第第1 1段段有有3 3种种，第第2 2段段各各有有3 3种种，第第3 3段段各各有有2 2种种，第第4 4段段各各1 1种种，因因此此共共有有332133211818条条可可能能的的路路线

12、线，分分别别算算出出各各条条路路线线的的距距离离进进行行比比较较，可可知知最最优优路路线线是是A A B B2 2 C C1 1 DD1 1 E E,最短距离是最短距离是1919 显显然然，如如果果组组成成网网络络的的节节点点很很多多时时，用用穷穷举举法法求求最最优优路路线线的的计计算算量量将将会会十十分分庞庞大大，其其中中包包含含许许多多重重复复计计算算枚枚枚枚举举举举法法法法虽虽虽虽可可可可找找找找出最优方案，但不是个好算法出最优方案，但不是个好算法出最优方案，但不是个好算法出最优方案，但不是个好算法第6页，此课件共27页哦 第第第第二二二二种种种种方方方方法法法法:“:“:“:“局局局局

13、部部部部最最最最优优优优路路路路径径径径”法法法法.说说某某人人从从某某站站出出发发，他他选选择择“逢逢近近便便走走”的的决决策策，以以为为只只要要“局局部部最最优优”,就就会会达达到到”“整整体体最最优优”，所所取取决决策策必必是是A A B B3 3 C C3 3 DD1 1 E E,但但全全程程长长度度是是2525；显显然然，这这种种方方法法的的结结果果常常是是错错误误的的局局局局部部部部最最最最优优优优法则是错误方法法则是错误方法法则是错误方法法则是错误方法.第第第第三三三三种种种种方方方方法法法法动动动动态态态态规规规规划划划划方方方方法法法法.首首先先将将问问题题划划分分为为5 5

14、个个阶阶段段，每每次次的的选选择择总总是是综综合合后后继继过过程程的的一一并并最最优优进进行行考考虑虑，在在各各段段所所有有可可能能状状态态的的最最优优后后继继过过程程都都已已求求得得的的情情况况下下，全全程程的的最最优优路路线线便便也也随随之之得得到到。动动态态规规划划方方法法总总是是从从过过程程的的最最后后阶阶段段开开始始考考虑虑，然后逆着实际过程发展的顺序，逐段向前然后逆着实际过程发展的顺序，逐段向前递推计算递推计算递推计算递推计算直至始点。直至始点。动动动动态态态态规规规规划划划划方方方方法法法法属属属属较较较较科科科科学学学学有有有有效效效效的的的的算算算算法法法法，计计算算过过程程

15、中中，系系统统地地删删去去了了所所有有中中间间非非最最优优的的方方案案组组合合，从从而而使使计计算算量量比比枚枚枚枚举举举举法法法法大为减少。大为减少。第7页，此课件共27页哦 2.动态规划的基本概念 使使用用动动态态规规划划方方法法解解决决多多阶阶段段决决策策问问题题，首首先先要要将将实实际际问问题题写写成成动动态态规规划划模模型型，需需要要对对动动态态规规划划的的一一些些基基本本术术语加以说明和定义：语加以说明和定义：1.1.1.1.阶段阶段阶段阶段 为为了了便便于于求求解解和和表表示示决决策策及及过过程程的的发发展展顺顺序序，而而把把所所给给问问题题恰恰当当地地划划分分为为若若干干个个相

16、相互互联联系系又又有有区区别别的的子子问问题题，称称之之为为多多段段决决策策问问题题的的阶阶段段。一一个个阶阶段段，就就是是需需要要作作出出一一个个决决策策的的子子问问题题，通通常常，阶阶段段是是按按决决策策进进行行的的时时间间或或空空间间上上先先后后顺顺序序划分的。划分的。2.2.2.2.状态和状态变量状态和状态变量状态和状态变量状态和状态变量 用用以以描描述述系系统统在在某某特特定定的的时时间间与与空空间间域域中中所所处处位位置置及及运运动动特特征征的的量量，称称为为状状态态。每每个个阶阶段段的的状状态态可可分分为为初初始始状状态态和和终终止止状状态态，阶阶段段k k的的初初始始状状态态记

17、记作作s sk k，终终止止状状态态记记为为s sk+1k+1。但但通通通通常常常常定定定定义义义义阶阶阶阶段段段段的的的的状状状状态态态态即即即即指指指指其其其其初初初初始始始始状状状状态态态态，故故阶阶段段k k的的终终止止状状态态s sk+1k+1为为阶段阶段k+1k+1的初始状态的初始状态。描描述述过过程程k k的的状状态态变变量量称称为为状状态态变变量量s sk k ，其其取取值值范范围围称称为为可能状态集可能状态集S Sk k,即即s sk kS Sk k。第8页，此课件共27页哦 3.3.决策和决策变量决策和决策变量决策和决策变量决策和决策变量 决决策策是是状状态态的的选选择择，

18、是是决决策策者者从从给给定定阶阶段段状状态态出出发发对对下下一一阶阶段段状态作出的选择。状态作出的选择。描描述述决决策策变变化化的的量量称称之之决决策策变变量量，和和状状态态变变量量一一样样，决决策策变变量量可可以以用用一一个个数数或或一一向向量量来来描描述述，也也可可以以是是状状态态变变量量的的函函数数，记记以以u uk k=u uk k(s sk k)，表示阶段，表示阶段k k状态状态s sk k时的决策变量。时的决策变量。决决策策变变量量的的取取值值也也有有一一定定的的允允许许范范围围，称称之之允允许许决决策策集集合合U Uk k(s sk k),),u uk k(s sk k)U Uk

19、 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部部部部子子子子策策策策略略略略,表表示示为为p pk,nk,n u uk k,u uk k+1+1,u un n ，显显然然当当k k=1=1时的时的k k部子策略就是全过程策略。部子策略就是全过程策略。在在实实际际问问题题中中，由由

20、于于在在各各个个阶阶段段可可供供选选择择的的决决策策有有许许多多个个，因因此此，它它们们的的不不同同组组合合就就构构成成了了许许多多可可供供选选择择的的决决策策序序列列(策策略略)，它它们们组组成成”允允许许策策略略集集”，记记作作P P1,1,n n ，从从中中找找出出具具有有最最优优效效果的策略称为最优策略。果的策略称为最优策略。第9页，此课件共27页哦 5.5.5.5.状态转移方程状态转移方程状态转移方程状态转移方程 系系统统在在阶阶段段k k处处于于状状态态s sk k，执执行行决决策策u uk k(s(sk k)的的结结果果是是系系统统状状态态的的转转移移，即即系系统统由由阶阶段段k

21、 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的的状状态态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

22、 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 k,u,uk)表示第k k段处于sk k状态且所作决策为u uk(sk k)时的指标，它就是第k k段段指指标标函函数数，简简记记为为gk。(2)(2)过过程程指指标标函函数数（也也

24、称称目目标标函函数数）:用用Rk(sk k,uk k)表示第k子过程的指标函数。如运运运运输输输输网网网网络络络络图图的的Rk k(sk,uk k)表示处于第k k段段sk k状状态态且且所所作作决决策策为为uk k时时，从从sk k点点到到终终点点E的距离。由此可见，Rk(sk k,uk)不仅跟当前状态sk有有关关，还还跟跟该该子子过过程程策策略略p pk k(s sk)有有关关，因因此此它它是是sk k和和pk(s sk)的的函函数数，应应表表示示为为:第11页，此课件共27页哦 用fk(s sk)表示第表示第k k子过程指标函数子过程指标函数 在状态s sk k下的最优值,即 与它相应的

25、子策略称为与它相应的子策略称为sk k状态下的最优子策略，简记为记为:特特别别当当k=1=1且且s s1取值唯一时，f1(s1 1)就就是是问问题题的的最最优优值值，而而p1*就是最优策略。我们把最优策略和最优值统称为问题的最优解。我们把最优策略和最优值统称为问题的最优解。第12页，此课件共27页哦7.7.多阶段决策问题的数学模型多阶段决策问题的数学模型多阶段决策问题的数学模型多阶段决策问题的数学模型 综综上上所所述述，适适于于应应用用动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决决策策问问题题，亦亦即即具有无后效性的多阶段决策问题的数学模型呈以下形式具有无后效性的多阶段决策问题的

26、数学模型呈以下形式:（5）模型说明对于给定的多阶段决策过程，求取一个最优策略模型说明对于给定的多阶段决策过程，求取一个最优策略(决策序决策序列列 )，使之既满足全部约束条件，又使目标函数，使之既满足全部约束条件，又使目标函数取得极值，同时，执行该最优策略时，过程状态演变序列即最优取得极值，同时，执行该最优策略时，过程状态演变序列即最优路线路线 ,按上述定义，所谓最优决策是指它按上述定义，所谓最优决策是指它们在全过程上整体最优们在全过程上整体最优第13页，此课件共27页哦8.8.最优化原理最优化原理最优化原理最优化原理 （贝尔曼最优化原理）（贝尔曼最优化原理）（贝尔曼最优化原理）（贝尔曼最优化原

27、理）作为一个全过程的最优策略具有这样的性质：对对于于最最优优策策略略过过程程中中的的任任意意状状态态而而言言，无无论论其其过过去去的的状状态态和和决决策策如如何何，余余下下的的诸诸决决策策必必构构成成一一个个最最优优子子策策略略。该原理的具体解释是，若某一全过程最优策略为：则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为第14页，此课件共27页哦贝尔曼最优化原理概念贝尔曼最优化原理概念:如图如图,如果已经给出从点如果已经给出从点A到点到点C的的最优轨迹，那么从任一中间点最优轨迹，那么从任一中间点B到点到点C的部分轨迹必须是从的部

28、分轨迹必须是从B到到C的最的最优轨迹。优轨迹。设给出路线设给出路线-是从是从A到到C的最优路线，根据贝尔曼原理，的最优路线，根据贝尔曼原理，则路线则路线 是从是从B到到C的最优路线。的最优路线。证证:用反证法用反证法,假设某条其假设某条其它路线，例如它路线，例如 是从是从B到到C的最优路线，那么，路线的最优路线，那么，路线I-比路线比路线I-有更小的费用。有更小的费用。但这与但这与I-是从是从A到到C最优路最优路线的前提相矛盾，因此线的前提相矛盾，因此必必是从是从B到到C的最优路线的最优路线贝尔曼阐述贝尔曼阐述:“一个最优策略有这样的特性，不论初始状态和初始决策一个最优策略有这样的特性，不论初

29、始状态和初始决策如何，相对于第一个决策所形成的状态来说，余下的决策必定构成一个如何，相对于第一个决策所形成的状态来说，余下的决策必定构成一个最优策略最优策略”。第15页，此课件共27页哦(1)(1)应应应应将将将将实实实实际际际际问问问问题题题题恰恰恰恰当当当当地地地地分分分分割割割割成成成成n n个个个个子子子子问问问问题题题题(n个个个个阶阶阶阶段段段段)。通通通通常常常常是是是是根据时间或空间而划分的。根据时间或空间而划分的。根据时间或空间而划分的。根据时间或空间而划分的。(2)正正正正确确确确地地地地定定定定义义义义状状状状态态态态变变变变量量量量s sk k，使使它它既既能能正正确确

30、地地描描述述过过程程的的状状态态，又又能能满满足足无无后后效效性性动动动动态态态态规规规规划划划划中中中中的的的的状状状状态态态态变变变变量量量量必必必必须须须须具具具具备备备备以下三个特征：以下三个特征：以下三个特征：以下三个特征：a)a)a)a)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。b)b)要要要要满满满满足足足足无无无无后后后后效效效效性性性性。即即即即如如如如果果果果在在在在某某某某个个个个阶阶阶阶段段段段状状状状态态态态已已已已经经经经给给给给定定定定，那那那那么么么么在在在在该

31、该该该阶阶阶阶段段段段以以以以后后后后，过过过过程程程程的的的的发发发发展展展展不不不不受受受受前前前前面面面面各各各各段段段段状状状状态态态态的的的的影影影影响响响响，如如如如果果果果所所所所选选选选的的的的变变变变量量量量不不不不具具具具备备备备无无无无后后后后效效效效性性性性，就就就就不不不不能能能能作作作作为为为为状状状状态态态态变变变变量量量量来来来来构造动态规划的模型。构造动态规划的模型。构造动态规划的模型。构造动态规划的模型。c)c)c)c)要要满满足足可可知知性性。即即所所规规定定的的各各段段状状态态变变量量的的值值，可以直接或间接地测算得到。可以直接或间接地测算得到。3.动态

32、规划方法的基本步骤第16页，此课件共27页哦(3)(3)正正确确地地定定义义决决策策变变量量及及各各阶阶段段的的允允许许决决策策集集合合U Uk k(sk k).根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量x x x xj j j j为后者的决策变量为后者的决策变量u u u uk k k k。(4)(4)能能能能够够够够正正正正确确确确地地地地写写写写出出出出状状状状态态态态转转转转移移移移方方方方程程程程。如果给定第k k阶段状态变量s sk k的值，则该段的决策变量u uk k一一经经确确定定

33、，第第k k+1段的状态变量sk k+1的值也就完全确定，即有的值也就完全确定，即有sk+1+1=Tk(s sk k,uk)(5)(5)正正确确地地构构造造出出目目标标函函数数.例例如如常常见见的的指指标标函函数数是是取取各各段段指标和的形式指标和的形式 其中 表示第i i阶阶段段的的指指标标，它它显显然然满满足足递递推关系：推关系：第17页，此课件共27页哦求最短路径4.动态规划方法应用举例第18页，此课件共27页哦 将将将将问问问问题题题题分分分分成成成成五五五五个个个个阶阶阶阶段段段段，第第第第k k阶阶段段到到达达的的具具体体地地点点用用状状态态变变量量x x x xk k k k表表

34、表表示示示示，例例例例如如如如：x x2 2 2 2=B=B3 3表表示示第第二二阶阶段段到到达达位位置置B B3 3，等等。这里状态变量取字符值而不是数值。，等等。这里状态变量取字符值而不是数值。将将将将决决决决策策策策定定定定义义义义为为为为到到到到达达达达下下下下一一一一站站站站所所所所选选选选择择择择的的的的路路路路径径径径，例例例例如如如如目目目目前前前前的的的的状状状状态是态是态是态是x x2 2 2 2=B=B3 3 3 3，这时决策允许集合包含三个决策，它们是，这时决策允许集合包含三个决策，它们是，这时决策允许集合包含三个决策，它们是，这时决策允许集合包含三个决策，它们是 D

35、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 E E的最短路径。的最短路径。终端条件为终端条件为终端条件为终端条件为 f f5 5(x(x5 5)=f)=f5 5(E)=0(E)=0其含义是从其含义是从E E E E到到到到E E E E的最短路径为的最短路径为0 0。第19页，此课件共27页哦从从f f5 5(x(x5 5)到到f f4 4(x(x4 4)的递推过程用

36、下表表示：的递推过程用下表表示：第四阶段的递推方程为：第四阶段的递推方程为：在上表中，在上表中，在上表中，在上表中，*表示最优值，由于决策允许集合表示最优值，由于决策允许集合表示最优值，由于决策允许集合表示最优值，由于决策允许集合D4(x4 4)中的决中的决中的决中的决策是唯一的，因此这个值就是最优值。策是唯一的，因此这个值就是最优值。策是唯一的，因此这个值就是最优值。策是唯一的，因此这个值就是最优值。第20页，此课件共27页哦 由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：f4(x4)的表达式的表达式D15D1Ex4f4(x4)最优决策 d4*D22D2E第21页，此

37、课件共27页哦从从f f4 4(x(x4 4)到到f f3 3(x(x3 3)的递推过程用表格表示如下：的递推过程用表格表示如下：第三阶段的递推方程为：第三阶段的递推方程为：第22页，此课件共27页哦由此得到由此得到由此得到由此得到f f f f3 3 3 3(x x x x3 3)的表达式的表达式,取值用列表表示取值用列表表示取值用列表表示取值用列表表示：第23页，此课件共27页哦第二阶段的递推方程为：第二阶段的递推方程为：从从f f3 3(x x3 3)到到f f2 2(x x2 2)的递推过程用表格表示如下：的递推过程用表格表示如下：第24页，此课件共27页哦由此得到由此得到f f f f2 2(x x x x2 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页哦14.10.2022感感谢谢大大家家观观看看第27页，此课件共27页哦