数学建模动态规划

《数学建模动态规划》由会员分享，可在线阅读，更多相关《数学建模动态规划（101页珍藏版）》请在金锄头文库上搜索。

1、第九章第九章 动态规划动态规划 1 多阶段决策过程最优化多阶段决策过程最优化 2 动态规划基本概念动态规划基本概念 3 动态规划基本原理动态规划基本原理 4 动态规划的应用动态规划的应用1 11.1.多阶段决策过程的最优化多阶段决策过程的最优化 一、多阶段决策问题一、多阶段决策问题l l动动态态规规划划是是把把多多阶阶段段决决策策问问题题作作为为研研究究对对象。象。l l多多阶阶段段决决策策问问题题：根根根根据据据据问问问问题题题题本本本本身身身身的的的的特特特特点点点点，可可可可以以以以将将将将其其其其求求求求解解解解的的的的全全全全过过过过程程程程划划划划分分分分为为为为若若若若干干干干个

2、个个个相相相相互互互互联联联联系系系系的的的的阶阶阶阶段段段段( ( ( (即即即即将将将将问问问问题题题题划划划划分分分分为为为为许许许许多多多多个个个个相相相相互互互互联联联联系系系系的的的的子子子子问问问问题题题题) ) ) )，在在在在它它它它的的的的每每每每一一一一阶阶阶阶段段段段都都都都需需需需要要要要作作作作出出出出决决决决策策策策，并并并并且且且且在在在在一一一一个个个个阶阶阶阶段段段段的决策确定以后再转移到下一个阶段。的决策确定以后再转移到下一个阶段。的决策确定以后再转移到下一个阶段。的决策确定以后再转移到下一个阶段。2 21.1.多阶段决策过程的最优化多阶段决策过程的最优化

3、多阶段决策过程多阶段决策过程(Multi-(Multi-StagedecisionStagedecision process)process)： 前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。3 31.1.多阶段决策过程的最优化多阶段决策过程的最优化最优策略：最优策略：若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把

4、一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。4 41.1.多阶段决策过程的最优化多阶段决策过程的最优化 多多阶阶段段决决策策过过程程最最优优化化的的目目标标是是要要达达到到整整个个活活动动过过程程的的总总体体效效果果最最优优。由由于于各各段段决决策策间间有有机机地地联联系系着着，本本段段决决策策的的执执行行将将影影响响到到下下一一段段的的决决策策，以以至至于于影影响响总总体体效效果果，所所以以决决策策者者在在每每段段决决策策时时不不应应仅仅考考虑虑本本阶阶段段最最优优，还还应应考考虑虑对对最最终终目目标标的的影影响响，从从而而作作出出对对全全局局来来讲讲是是最

5、最优优的的决决策策。动动态态规规划划就就是是符符合合这这种种要求的一种决策方法。要求的一种决策方法。5 51.1.多阶段决策过程的最优化多阶段决策过程的最优化图1 运输网络图示6 6多阶段决策过程特点多阶段决策过程特点: :要点：要点：阶段，状态，决策，状态转阶段，状态，决策，状态转移方程，移方程，k k- -后部子过程后部子过程状态状态 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.状态状态

6、 x xn n决策决策u un n阶段阶段n nTnTn状态状态 x xn n+1+11.1.多阶段决策过程的最优化多阶段决策过程的最优化7 71.1.多阶段决策过程的最优化多阶段决策过程的最优化四、动态规划方法导引四、动态规划方法导引四、动态规划方法导引四、动态规划方法导引例例例例1 1 1 1：为为了了说说明明动动态态规规划划的的基基本本思思想想方方法法和和特特点点，下下面面以图以图1 1所示为例讨论的求最短路问题的方法。所示为例讨论的求最短路问题的方法。 第第第第一一一一种种种种方方方方法法法法称称做做全全枚枚举举法法或或穷穷举举法法。它它的的基基本本思思想想是是列列举举出出所所有有可可

7、能能发发生生的的方方案案和和结结果果，再再对对它它们们一一一一进进行行比比较较，求求出出最最优优方方案案。这这里里从从v v1 1到到v v1010的的路路程程可可以以分分为为4 4个个阶阶段段。第第一一段段的的走走法法有有三三种种，第第二二三三两两段段的的走走法法各各有有两两种种，第第四四段段的的走走法法仅仅一一种种，因因此此共共有有3 3 2 2 2 2 1 11212条条可可能能的的路路线线，分分别别算算出出各各条条路路线线的的距距离离，最最后后进进行行比比较较，可可知知最最优优路路线线是是v v1 1 v v3 3 v v7 7 v v9 9 v v1010 , ,最短距离是最短距离是

8、18188 81.1.多阶段决策过程的最优化多阶段决策过程的最优化 显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第第二二种种方方法法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1 1 v3 v5 v8 v10 ，全程长度是20；显然，这种方法的结果常是错误的9 91.1.多阶段决策过程的最优化多阶段决策过程的最优化 第第三三种种方方法法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4

9、个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。10101.1.多阶段决策过程的最优化多阶段决策过程的最优化结论：结论：结论：结论：l l全枚举法虽可找出最优方案，但不是个好算法；全枚举法虽可找出最优方案，但不是个好算法；全枚举法虽可找出最优方案，但不是个好算法；全枚举法虽可找出最优方案，但不是个好算法；l l局部最优法则完全是个错误方法；局部最优法则完全是个错误方法；局部最优法

10、则完全是个错误方法；局部最优法则完全是个错误方法；l l动动动动态态态态规规规规划划划划方方方方法法法法属属属属较较较较科科科科学学学学有有有有效效效效的的的的算算算算法法法法：它它的的基基本本思思想想是是，把把一一个个比比较较复复杂杂的的问问题题分分解解为为一一系系列列同同类类型型的的更更易易求求解解的的子子问问题题，便便于于应应用用计计算算机机。整整个个求求解解过过程程分分为为两两个个阶阶段段，先先按按整整体体最最优优的的思思想想逆逆序序地地求求出出各各个个子子问问题题中中所所有有可可能能状状态态的的最最优优决决策策与与最最优优路路线线值值，然然后后再再顺顺序序地地求求出出整整个个问问题题

11、的的最最优优策策略略和和最最优优路路线线。计计算算过过程程中中，系系统统地地删删去去了了所所有有中中间间非非最最优优的的方方案案组组合合，从从而而使计算工作量比穷举法大为减少。使计算工作量比穷举法大为减少。1111 2.2.动态规划的基本概念动态规划的基本概念 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义： 1212 2.2.动态规划的基本概念动态规划的基本概念 ( (一一) ) 阶段和阶段变量阶段和阶段变量 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互

12、联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目。1313 2.2.动态规划的基本概念动态规划的基本概念 （二）状态、状态变量和可能状态集（二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初

13、始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。14142.2.动态规划的基本概念动态规划的基本概念 2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定1515 （三）决策、决策变量和允许决策集合三）决策、决策变量和允许决策集合三）决策、决策变量和允许决策集合三）决策、决策变量和允许决策集合 所所

14、谓谓决决策策，就就是是确确定定系系统统过过程程发发展展的的方方案案。决决策策的的实实质质是是关关于于状状态态的的选选择择，是是决决策策者者从从给给定定阶阶段段状态出发对下一阶段状态作出的选择。状态出发对下一阶段状态作出的选择。 用用以以描描述述决决策策变变化化的的量量称称之之决决策策变变量量和和状状态态变变量量一一样样，决决策策变变量量可可以以用用一一个个数数，一一组组数数或或一一向向量量来来描描述述，也也可可以以是是状状态态变变量量的的函函数数，记记以以u uk k= = u uk k( (s sk k) )，表示于阶段表示于阶段k k状态状态s sk k时时的决策变量。的决策变量。 决决策

15、策变变量量的的取取值值往往往往也也有有一一定定的的允允许许范范围围，称称之之允允许许决决策策集集合合。决决策策变变量量u uk k( (s sk k) )的的允允许许决决策策集集用用U Uk k( (s sk k) )表表示示, , u uk k( (s sk k) ) U Uk k( (s sk k) )允允许许决决策策集集合合实实际际是是决决策策的约束条件。的约束条件。 2.2.动态规划的基本概念动态规划的基本概念1616 （四）、策略和允许策略集合（四）、策略和允许策略集合（四）、策略和允许策略集合（四）、策略和允许策略集合 策策略略(Policy)(Policy)也也叫叫决决策策序序列

16、列策策略略有有全全过过程程策策略略和和k k部部子子策策略略之之分分，全全过过程程策策略略是是指指具具有有n n个个阶阶段段的的全全部部过过程程，由由依依次次进进行行的的n n个个阶阶段段决决策策构构成成的的决决策策序序列列，简简称称策策略略，表表示示为为p p1,1,n n u u1 1, ,u u2 2, , , ,u un n 。从从k k阶阶段段到到第第n n阶阶段段，依依次次进进行行的的阶阶段段决决策策构构成成的的决决策策序序列列称称为为k k部部子子策策略略, ,表表示示为为p pk,nk,n u uk k, ,u uk k+1+1, , , ,u un n ，显显然然当当k k=

17、1=1时的时的k k部子策略就是全过程策略。部子策略就是全过程策略。 在在实实际际问问题题中中，由由于于在在各各个个阶阶段段可可供供选选择择的的决决策策有有许许多多个个，因因此此，它它们们的的不不同同组组合合就就构构成成了了许许多多可可供供选选择择的的决决策策序序列列( (策策略略) )，由由它它们们组组成成的的集集合合，称称之之允允许许策策略略集集合合，记记作作P P1,1,n n ，从从允允许许策策略略集集中中，找找出出具有最优效果的策略称为最优策略。具有最优效果的策略称为最优策略。2.2.动态规划的基本概念动态规划的基本概念1717 （五）状态转移方程（五）状态转移方程（五）状态转移方程

18、（五）状态转移方程 系系统统在在阶阶段段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 ，多多阶阶段段决决策策过过程程的的发展就是用阶段状态的相继演变来描述的。发展就是用阶段状态的相继演变来描述的。 对对于于具具有有无无后后效效性性的的多多阶阶段段决决策策过过程程,

19、,系系统统由由阶阶段段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) )无无关关。系系统统状状态态的这种转移，用数学公式描述即有：的这种转移，用数学公式描述即有：2.2.动态规划的基本概念动态规划的基本概念(1)1818 通常称式(1)为多阶

20、段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。 ( (六六) ) 指标函数指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。 2.2.动态规划的基本概念动态规划的基本概念1919 (1)阶段指标函数（也称阶段效应）。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk 。 (2)过程指标函数（也称目标函数）。

21、用Rk(sk,uk)表示第k子过程的指标函数。如图5-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见，Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:2.2.动态规划的基本概念动态规划的基本概念2020 不不过过实实际际应应用用中中往往往往表表示示为为R Rk k( (s sk k, ,u uk k) )或或R Rk k( (s sk k) )。还还跟跟第第k k子子过过程程上上各各段段指指标标函函数数有有关关，过过程程指指标标函函数数R Rk k( (s s

22、k k) )通通常常是是描描述述所所实实现现的的全全过过程程或或k k后后部部子子过过程程效效果果优优劣劣的的数数量量指指标标，它它是是由由各各阶阶段段的的阶阶段段指指标标函函数数g gk k( (s sk k, ,u uk k) )累累积积形形成成的的，适适于于用用动动态态规规划划求求解解的的问问题题的的过过程程指指标标函函数数（即即目目标标函函数数），必必须须具具有有关关于于阶阶段段指指标标的的可可分分离离形形式式对对于于部部子子过过程程的的指指标标函函数数可可以以表表示示为：为： 式式中中，表表示示某某种种运运算算，可可以以是是加加、减减、乘乘、除除、开开方等。方等。2.2.动态规划的基

23、本概念动态规划的基本概念 (2)2121 多多阶阶段段决决策策问问题题中中，常常见见的的目目标标函函数数形形式式之之一一是取各阶段效应之和的形式，即是取各阶段效应之和的形式，即: : (3) (3) 有有些些问问题题，如如系系统统可可靠靠性性问问题题，其其目目标标函函数数是是取各阶段效应的连乘积形式，如：取各阶段效应的连乘积形式，如： (4)(4) 总总之之，具具体体问问题题的的目目标标函函数数表表达达形形式式需需要要视视具具体问题而定。体问题而定。2.2.动态规划的基本概念动态规划的基本概念2222 ( ( ( (七七七七) ) ) ) 最优解最优解最优解最优解 用用f fk k( (s s

24、k k) )表示第表示第k k子过程指标函数子过程指标函数 在状态在状态s sk k下下的最优值的最优值, ,即即 称称f fk k( (s sk k) )为第为第k k子过程上的最优指标函数；与它子过程上的最优指标函数；与它相应的子策略称为相应的子策略称为s sk k状态下的最优子策略，记状态下的最优子策略，记为为p pk k* *( (s sk k) ) ；而构成该子策赂的各段决策称为该而构成该子策赂的各段决策称为该过程上的最优决策，记为过程上的最优决策，记为 有有 简记简记为为2.2.动态规划的基本概念动态规划的基本概念2323 特别当特别当k k=1=1且且s s1 1取值唯一时，取值

25、唯一时，f f1 1( (s s1 1) )就是问题的最就是问题的最优值，优值，而而p p1 1* *就是最优策略。如例只有唯一始点就是最优策略。如例只有唯一始点v v1 1即即s s1 1取值唯一取值唯一, ,故故f f1 1( (s s1 1)=18)=18就是例的最优值，而就是例的最优值，而 就是例的最优策略。就是例的最优策略。 但若取值不唯一但若取值不唯一, ,则问题的最优值记为则问题的最优值记为f f0 0有有 最优策略即为最优策略即为s s1 1= =s s1 1* *状态下的最优策略：状态下的最优策略： 我们把最优策略和最优值统称为问题的最我们把最优策略和最优值统称为问题的最 优

26、解。优解。2.2.动态规划的基本概念动态规划的基本概念2424 按上述定义，所谓最优决策按上述定义，所谓最优决策 是指它们在全过是指它们在全过程上整体最优程上整体最优( (即所构成的全过程策略为最优即所构成的全过程策略为最优) )，而不一定，而不一定在各阶段上单独最优。在各阶段上单独最优。 ( ( ( (八八八八) ) ) ) 多阶段决策问题的数学模型多阶段决策问题的数学模型多阶段决策问题的数学模型多阶段决策问题的数学模型 综综上上所所述述，适适于于应应用用动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决决策策问问题题，亦亦即即具具有有无无后后效效性性的的多多阶阶段段决决策策问问题题

27、的的数数学学模模型呈以下形式型呈以下形式: :2.2.动态规划的基本概念动态规划的基本概念（5）2525 式中“OPTOPT”表示最优化，视具体问题取max或min。 上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列 ，使之既满足式(5)给出的全部约束条件，又使式(5)所示的目标函数取得极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线2.2.动态规划的基本概念动态规划的基本概念2626最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优

28、子策略。该原理的具体解释是，若某一全过程最优策略为： 动态规划的基本原理动态规划的基本原理 则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为27273.3.动态规划方法的基本步骤动态规划方法的基本步骤 1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。 2正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量

29、必须具备以下三个特征：28283.3.动态规划方法的基本步骤动态规划方法的基本步骤 (1)(1)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。 (2)(2)要要满满足足无无后后效效性性。即即如如果果在在某某个个阶阶段段状状态态已已经经给给定定，那那么么在在该该阶阶段段以以后后，过过程程的的发发展展不不受受前前面面各各段段状状态态的的影影响响，如如果果所所选选的的变变量量不不具具备备无无后后效效性性，就就不不能能作作为为状状态态变变量量来来构构造造动动态态规规划划的的模型。模型。 (3)(3)要要满满足足可可知知性性。即即所所规规定定的的各各段段状状态态变变量量的的值值

30、，可可以以直直接接或或间间接接地地测测算算得得到到。一一般般在在动动态态规规划划模模型型中中，状状态态变变量量大大都都选选取取那那种种可可以以进进行行累累计计的的量量。此此外外，在在与与静静态态规规划划模模型型的的对对应应关关系系上上，通通常常根根据据经经验验，线线性性与与非非线线性性规规划划中中约约束束条条件件的的个个数数，相相当当于于动动态态规规划划中中状状态态变变量量s sk k的的维维数数而而前前者者约约束束条条件件所所表表示示的的内内容容，常常就就是是状状态态变变量量s sk k所代表的内容。所代表的内容。29293.3.动态规划方法的基本步骤动态规划方法的基本步骤 3 3正正确确地

31、地定定义义决决策策变变量量及及各各阶阶段段的的允允许许决决策策集集合合U Uk k( (s sk k) )，根根据据经经验验，一一般般将将问问题题中中待待求求的的量量，选选作作动动态态规规划划模模型型中中的的决决策策变变量量。或或者者在在把把静静态态规规划划模模型型( (如如线线性性与与非非线线性性规规划划) )转转换换为为动动态态规规划划模模型型时时，常常取取前前者者的的变变量量x xj j为为后后者的决策变量者的决策变量u uk k。 4. 4. 能能够够正正确确地地写写出出状状态态转转移移方方程程，至至少少要要能能正正确确反反映映状状态态转转移移规规律律。如如果果给给定定第第k k阶阶段

32、段状状态态变变量量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) )30303.3.动态规划方法的基本步骤动态规划方法的基本步骤 5 5根根据据题题意意, ,正正确确地地构构造造出出目目标标与与变变量量的的函函数数关关系系目目标标函函数数，目目标标函函数数应应满满足足下下列列性质：性质： (1)(1)可可分分性性，即即对对于于所所有有k k后后部部子子过过程程，其其目目 标标

33、 函函 数数 仅仅 取取 决决 于于 状状 态态s sk k及及 其其 以以 后后 的的 决决 策策 u uk k , ,u uk k+1+1,u un n, ,就就是是说说它它是是定定义义在在全全过过程程和和所所有后部子过程上的数量函数。有后部子过程上的数量函数。 (2)(2)要满足递推关系，即要满足递推关系，即 (3)(3)函函数数 对对其其变变元元R Rk k+1+1来来说说要要严严格格单调。单调。3131 6写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ：3.3.动态规划方法的基本步骤动态规划方法

34、的基本步骤3232求 最 短 路 径3535 求 最 短 路 径例5.53636 将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。 将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)=B3C1,B3C2,B3C3求 最 短 路 径3737最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为: :求 最 短 路 径3838其中*表示最优值

35、，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。 由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：求 最 短 路 径3939第三阶段的递推方程为：求 最 短 路 径4040由此得到f3(x3)的表达式：求 最 短 路 径4141求 最 短 路 径4242由此得到f2(x2)的表达式：求 最 短 路 径4343第一阶段的递推方程为：求 最 短 路 径4444由此得到f1(x1)的表达式求 最 短 路 径4545资资 源源 分分 配配 问问 题题4646 例5.6: 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关

36、。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题47471.1.阶段k：每投资一个项目作为一个阶段；2.2.状态变量xk：投资第k个项目前的资金数；3.3.决策变量dk：第k个项目的投资；4.4.决策允许集合：0dkxk5.5.状态转移方程：xk+1=xk-dk6.6.阶段指标：vk(xk ,dk)见表中所示；7.7.递推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)8.8.终端条件：f4(x4)=0资资 源源 分分 配配 问问 题题4848k=4，f4(x4)=0k=3，

37、0d3x3，x4=x3-d3资资 源源 分分 配配 问问 题题4949k=2，0d2x2，x3=x2-d2资资 源源 分分 配配 问问 题题5050k=1，0d1x1，x2=x1-d1资资 源源 分分 配配 问问 题题5151背 包 问 题5252背 包 问 题5353则 Max z=c1x1+c2x2+cnxn s.t. w1x1+w2x2+wnxnW x1,x2,xn为正整数1.1.阶 段k： 第k次 装 载 第k种 物 品（k=1,2,n）2.2.状态变量sk：第k次装载时背包还可以装载的重量；3.3.决策变量dk：第k次装载第k种物品的件数；背 包 问 题54544. 4. 决策允许集

38、合：Dk(xk)=dk|0 dksk/wk，dk为整数；5. 5. 状态转移方程：sk+1=sk-wkdk6 6. 阶段指标：vk=ckdk7 7. 递推方程 fk(sk)=maxckdk+fk+1(sk+1) =maxckdk+fk+1(sk-wkdk)8. 8. 终端条件：fn+1(sn+1)=0背 包 问 题5555 例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5用动态规划求解 f4(s4)=0 对于k=3背 包 问 题56565757585859596060 机器负荷分配问题机器负荷分配问题61616262 构造动态规划模型如下：

39、 阶段阶段k k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，依次类推；k=6表示第五年末（即第六年初）。 状态变量状态变量x xk k：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数。 决策变量决策变量d dk k：第k年投入高负荷运行的机器数； 状态转移方程状态转移方程：xk+1=0.7dk+0.9(xk-dk) 决策允许集合决策允许集合：Dk(xk)=dk|0dkxk 阶段指标阶段指标：vk(xk ,dk)=8dk+5(xk-dk) 终端条件终端条件：f6(x6)=0 机器负荷分配问题机器负荷分配问题6363递推方程

40、：fk(xk)=maxvk(xk,dk)+fk+1(xk+1) d dk k D Dk k( (x xk k) )= max8max8d dk k+5(+5(x xk k- - d dk k)+)+f fk k+1+10.70.7d dk k+0.9(+0.9(x xk k- -d dk k) ) 0 0 d dk k x xk k 机器负荷分配问题机器负荷分配问题6464f5(x5)=max8d5+5(x5-d5)+f6(x6) 0 0 d d5 5 x x5 5 =max3d5+5x5=8x5, d5*=x5 0 0 d d5 5 x x5 5f4(x4)=max8d4+5(x4-d4)+

41、f5(x5) 0 0 d d4 4 x x4 4 =max8d4+5(x4-d4)+8x5 0 0 d d4 4 x x4 4 =max8d4+5(x4-d4)+80.7d4+0.9(x4-d4) 0 0 d d4 4 x x4 4 =max1.4d4+12.3x4=13.7x4, d4*=x4 0 0 d d4 4 x x4 4 机器负荷分配问题机器负荷分配问题6565f3(x3)=max8d3+5(x3-d3)+f4(x4) 0 0 d d3 3 x x3 3=max8d3+5(x3-d3)+13.7x4 0 0 d d3 3 x x3 3=max8d3+5(x3-d3)+13.70.7d

42、3+0.9(x3-d3) 0 0 d d3 3 x x3 3=max0.28d3+17.24x3=17.52x3, d3*=x3 0 0 d d3 3 x x3 3 机器负荷分配问题机器负荷分配问题6666f2(x2)=max8d2+5(x2-d2)+f3(x3) 0 0 d d2 2 x x2 2 =max8d2+5(x2-d2)+17.52x3 0 0 d d2 2 x x2 2 =max8max8d d2 2+5(+5(x x2 2- -d d2 2)+17.520.7)+17.520.7d d2 2+0.9(+0.9(x x2 2- -d d2 2) 0 0 d d2 2 x x2 2

43、 =max-0.504d2+20.77x2=20.77x2,d2*=0 0 0 d d2 2 x x2 2 机器负荷分配问题机器负荷分配问题6767f1(x1)=max8d1+5(x1-d1)+f2(x2) 0 0 d d1 1 x x1 1 =max8d1+5(x1-d1)+20.77x2 0 0 d d1 1 x x1 1 =max8max8d d1 1+5(+5(x x1 1- -d d1 1)+20.770.7)+20.770.7d d1 1+0.9(+0.9(x x1 1- -d d1 1) 0 0 d d1 1 x x1 1 =max-0.05d1+23.69x1=23.69x1,

44、d1*=0 0 0 d d1 1 x x1 1 机器负荷分配问题机器负荷分配问题6868由此可以得到：l lf1(x1)=23.69x1,d1*=0l lf2(x2)=20.77x2,d2*=0l lf3(x3)=17.52x3,d3*=x3l lf4(x4)=13.60x4,d4*=x4l lf5(x5)=8x5 d5*=x5用x1=1000代入，得到五年最大产量为l lf1(x1)=f1(1000)=23690 机器负荷分配问题机器负荷分配问题6969每年投入高负荷运行的机器数以每年初完好的机器数为：l lx1=1000l ld1*=0, x2=0.7d1+0.9(x1-d1)=900l

45、ld2*=0, x3=0.7d2+0.9(x2-d2)=810l ld3*=x3=810, x4=0.7d3+0.9(x3-d3)=567l ld4*=x4=567, x5=0.7d4+0.9(x4-d4)=397l ld5*=x5=397, x6=0.7d5+0.9(x5-d5)=278 机器负荷分配问题机器负荷分配问题7070 在这个例子中，状态变量的终端值x6是未加约束的，如果要求在第五年末（即第六年初）完好的机器数不少于500台，这时决策变量d5的决策允许集合将成为：D5(x5)=d5|0.7d5+0.9(x5-d5)500, d50即 0.9x5-0.2d5500d50 或 0d54

46、.5x5-2500 容易想象，这时的最大产量将比x6是自由的情况下小。l l 这个例子可以推广到一般情况。设高负荷生产时机器的完好率为k1，单台产量为p1；低负荷完好率为k2，单台产量为p2。若有t满足: 机器负荷分配问题机器负荷分配问题7171则从1t-1年，年初将全部完好机器投入低负荷运行，从tn年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。 机器负荷分配问题机器负荷分配问题7272生生 产产 库库 存存 问问 题题7373 例例5.95.9：一个工厂生产某种产品,1- 7月份生产成本和产品需求量的变化情 况如下表：生生 产产 库库 存存 问问 题题7474l l阶

47、段k：月份，k=1,2,7,8；l l状态变量xk：第k个月初（发货以前）的库存量；l l决策变量dk：第k个月的生产量；l l状态转移方程：xk+1=xk-rk+dk；l l决策允许集合：l lDk(xk)=dk | dk0, rk+1xk+1H =dk | dk0, rk+1xk-rk+dkH ；l l阶段指标：vk(xk ,dk)=ckdk；l l终端条件：f8(x8)=0,x8=0；生生 产产 库库 存存 问问 题题7575递推方程：fk(xk)=minvk(xk ,dk)+fk+1(xk+1) d dk k D Dk k(x(xk k) ) =minckdk+fk+1(xk-rk+d

48、k) d dk k D Dk k( (x xk k) )l l对于k=7l l因为 x8=0l l有 d7=0l l递推方程为l lf7(x7)=minc7d7+f8(x8)=0 d7=0生生 产产 库库 存存 问问 题题7676对于k=6因为d7=0，所以x7=r7=4而x6-r6+d6=x7=4因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=minc6d6+f7(x7) d d6 6=11-=11-x x6 6=10d6=10(11-x6)=110-10x6生生 产产 库库 存存 问问 题题7777对于对于对于对于k k k k=5=5=

49、5=5f f f f5 5 5 5( ( ( (x x x x5 5 5 5)=min)=min)=min)=minc c c c5 5 5 5d d d d5 5 5 5+ + + +f f f f6 6 6 6( ( ( (x x x x6 6 6 6) ) ) ) d d d d5 5 5 5 D D D D5 5 5 5( ( ( (x x x x5 5 5 5) ) ) ) =min20 =min20 =min20 =min20d d d d5 5 5 5+110-10+110-10+110-10+110-10x x x x6 6 6 6 d d d d5 5 5 5 D D D D

50、5 5 5 5( ( ( (x x x x5 5 5 5) ) ) ) =min20 =min20 =min20 =min20d d d d5 5 5 5+110-10(+110-10(+110-10(+110-10(x x x x5 5 5 5- - - -r r r r5 5 5 5+ + + +d d d d5 5 5 5) d d d d5 5 5 5 D D D D5 5 5 5( ( ( (x x x x5 5 5 5) ) ) ) =min20 =min20 =min20 =min20d d d d5 5 5 5+110-10(+110-10(+110-10(+110-10(x

51、x x x5 5 5 5-2+-2+-2+-2+d d d d5 5 5 5) d d d d5 5 5 5 D D D D5 5 5 5( ( ( (x x x x5 5 5 5) ) ) ) =min10 =min10 =min10 =min10d d d d5 5 5 5-10-10-10-10x x x x5 5 5 5+130+130+130+130 d d d d5 5 5 5 D D D D5 5 5 5( ( ( (x x x x5 5 5 5) ) ) )D D D D5 5 5 5( ( ( (x x x x5 5 5 5) =) =) =) =d d d d5 5 5 5

52、| | | | d d d d5 5 5 5 0, 0, 0, 0, r r r r6 6 6 6 x x x x5 5 5 5- - - -r r r r5 5 5 5+ + + +d d d d5 5 5 5 H H H H = = = =d d d d5 5 5 5| | | |d d d d5 5 5 5 0, 0, 0, 0, r r r r6 6 6 6+ + + +r r r r5 5 5 5- - - -x x x x5 5 5 5 d d d d5 5 5 5 H H H H+ + + +r r r r5 5 5 5- - - -x x x x5 5 5 5 = = = =d

53、 d d d5 5 5 5| | | | d d d d5 5 5 5 0, 9-0, 9-0, 9-0, 9-x x x x5 5 5 5 d d d d5 5 5 5 11-11-11-11-x x x x5 5 5 5 生生 产产 库库 存存 问问 题题7878因为x5H=9，因此9-x50，决策允许集合可以简化为 D5(x5)=d5| 9-x5d511-x5递推方程成为f5(x5)=min10d5-10x5+130 9- 9-x x5 5 d d5 5 11-11-x x5 5 =10(9-x5)-10x5+130 =220-20x5 d5*=9-x5生生 产产 库库 存存 问问 题题

54、7979对于k=4f4(x4)=minc4d4+f5(x5) d d4 4 D D4 4( (x x4 4) ) =min17d4+220-20x5 d d4 4 D D4 4( (x x4 4) ) =min17d4+220-20(x4-r4+d4) d d4 4 D D4 4( (x x4 4) ) =min17d4+220-20(x4-3+d4) d d4 4 D D4 4( (x x4 4) ) =min-3d4-20x4+280 d d4 4 D D4 4( (x x4 4) ) 生生 产产 库库 存存 问问 题题8080D4(x4)=d4| d40, r5x4-r4+d4H=d4|

55、 d40, r5+r4-x4d4H+r4-x4=d4| d40, 5-x4d412-x4=d4| max0,5-x4d412-x4 由于 在f4(x4)的表达式中d4的系数是-3， 因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20x4+280 =-17x4+244生生 产产 库库 存存 问问 题题8181对于k=3f3(x3)=min c3d3+f4(x4)d3D3(x3)=min 13d3+244-17x4 d3D3(x3) =min 13d3+244-17(x3-r3+d3) d d3 3 D D3 3( (x x3 3) ) =m

56、in -4d3-17x3+329 d3D3(x3) D3(x3)=d3| d30,r4x3-r3+d3H=d3| d30,r4+r3-x3d3H+r3-x3=d3| d30,8-x3d314-x3=d3| max0,8-x3d314-x3由此 f3(x3)=-4(14-x3)-17x3+329 =-13x3+273, d3*=14-x3生生 产产 库库 存存 问问 题题8282对于k=2f2(x2)=minc2d2+f3(x3) d2D2(x2) =min18d2+273-13x3 d2D2(x2) =min18d2+273-13(x2-r2+d2) d d2 2 D D2 2( (x x2

57、2) ) =min18d2+273-13(x2-8+d2) d d2 2 D D2 2( (x x2 2) ) =min5d2-13x2+377 d2D2(x2) D2(x2)=d2|d20,r3x2-r2+d2H =d2|d20,r3+r2-x2d2H+r2-x2 =d2|d20,13-x2d217-x2生生 产产 库库 存存 问问 题题8383因为 13-x20所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2生生 产产 库库 存存 问问 题题8484对于k=1f1(x1)=minc1d1+f

58、2(x2) d1D1(x1) =min11d1+442-18x2 d1D1(x1) =min11d1+442-18(x1-r1+d1) d d1 1 D D1 1( (x x1 1) ) =min11d1+442-18(x1-0+d1) d d1 1 D D1 1( (x x1 1) ) =min-7d1-18x1+442 d d1 1 D D1 1( (x x1 1) ) D D1 1( (x x1 1)=)=d d1 1| |d d1 1 0,0,r r2 2 x x1 1- -r r1 1+ +d d1 1 H H = =d d1 1| |d d1 1 0,0,r r2 2+ +r r1

59、 1- -x x1 1 d d1 1 H H+ +r r1 1- -x x1 1 = =d d1 1| |d d1 1 0,8-0,8-x x1 1 d d1 1 9-9-x x1 1 生生 产产 库库 存存 问问 题题8585根据题意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357将以上结果总结成下表：生生 产产 库库 存存 问问 题题8686设设 备备 更更 新新 问问 题题8787 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，设设 备备 更更 新新 问问 题题88888989设设 备备 更更 新新 问问 题题9090例5.10：设具体数据如下：设设 备备 更更 新新 问问 题题9191929293939494959596969797989899999797100100 由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。 这两个决策是 设设 备备 更更 新新 问问 题题101101