最优化技术基础.pptx

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