运筹学课件-动态规划

1第四章动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点2一、多阶段决策问题 (Multi-Stagedecisionprocess)多阶段决策过程特点:状态

x1阶段1T1决策u1状态

x2决策u2阶段2T2状态

x3...状态

xk决策uk阶段kTk状态

xk+1...状态

xn决策un阶段nTn状态

xn+11.多阶段决策过程的最优化31.多阶段决策过程的最优化

动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。41.多阶段决策过程的最优化

二、多阶段决策问题举例属于多阶段决策类的问题很多，例如：

1)工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。51.多阶段决策过程的最优化

2)设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。61.多阶段决策过程的最优化

3)连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。71.多阶段决策过程的最优化

以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。81.多阶段决策过程的最优化

4）资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。91.多阶段决策过程的最优化

5）运输网络问题：如图5-1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从fk(sk)至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。101.多阶段决策过程的最优化图5-1运输网络图示111.多阶段决策过程的最优化

三、动态规划求解的多阶段决策问题的特点

通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。121.多阶段决策过程的最优化

四、动态规划方法导引例5.1：为了说明动态规划的基本思想方法和特点，下面以图5-1所示为例讨论的求最短路问题的方法。第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有3×2×2×1＝12条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1→v3→

v7→

v9→v10

,最短距离是18．131.多阶段决策过程的最优化

显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1→v3→v5→

v8→

v10

，全程长度是20；显然，这种方法的结果常是错误的．141.多阶段决策过程的最优化

第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。151.多阶段决策过程的最优化

具体说，此问题先从v10开始，因为v10是终点。再无后继过程，故可以接着考虑第4阶段上所有可能状态v8,v9的最优后续过程．因为从v8,v9

到v10的路线是唯一的，所以v8,v9

的最优决策和最优后继过程就是到v10

，它们的最短距离分别是5和3。接着考虑阶段3上可能的状态v5,v6,v7,到v10的最优决策和最优后继过程．在状态V5上，虽然到v8是8，到v9是9，但是综合考虑后继过程整体最优，取最优决策是到v9,最优后继过程是v5→v9→v10，最短距离是12．同理，状态v6的最优决策是至v8

；v7的最优决策是到v9

。161.多阶段决策过程的最优化

同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程，如v2的最优决策是到v5,最优路线是v2→v5→v9→v10，最短距离是15…依此类推，最后可以得到从初始状态v1的最优决策是到v3最优路线是v1→v3→v7→v9→v10，全程的最短距离是18。图5—1中粗实线表示各点到的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。171.多阶段决策过程的最优化

综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。18

2.动态规划的基本概念

一、动态规划的基本概念

使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义：

(一)阶段和阶段变量

为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量．阶段数等于多段决策过程从开始到结束所需作出决策的数目，图5—1所示的最短路问题就是一个四阶段决策过程。19

2.动态规划的基本概念

（二）状态、状态变量和可能状态集

1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。20

2.动态规划的基本概念

2．可能状态集一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，sk∈Sk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定．在图5—1所示的最短路问题中，第一阶段状态为v1，状态变量s1的状态集合S1={v1}；第二阶段则有三个状态：v2,v3,v4

,状态变量s2的状态集合S2={v2,v3,v4}

；第三阶段也有三个状态:v5,v6,v7

，状态变量s3的状态集合S3={v5,v6,v7}

；第四阶段则有二个状态：v8,v9,状态变量s4的状态集合S4={v8,v9}

；21

（三）决策、决策变量和允许决策集合所谓决策，就是确定系统过程发展的方案。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，也可以是状态变量的函数，记以uk=uk(sk)，表示于阶段k状态sk时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示,uk(sk)∈Uk(sk)允许决策集合实际是决策的约束条件。

2.动态规划的基本概念

22

（四）、策略和允许策略集合策略(Policy)也叫决策序列．策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,n{u1,u2,…,un}。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,n{uk,uk+1,…,un}，显然当k=1时的k部子策略就是全过程策略。在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n

，从允许策略集中，找出具有最优效果的策略称为最优策略。

2.动态规划的基本概念

23

（五）状态转移方程系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1

，或者说，系统由k阶段的状态sk转移到了阶段k+1的状态sk+1

，多阶段决策过程的发展就是用阶段状态的相继演变来描述的。对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2,…,sk-1及其决策u1(s1),u2(s2)…uk-1(sk-1)无关。系统状态的这种转移，用数学公式描述即有：

2.动态规划的基本概念

(5-1)通常称式(5-1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。24

(六)指标函数用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。例如：图5—1的指标就是运费。

2.动态规划的基本概念

25

(1)阶段指标函数（也称阶段效应）。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk

。图5-1的gk值就是从状态sk到状态sk+1的距离。譬如，gk(v2,v5)=3,即v2到v5的距离为3。

(2)过程指标函数（也称目标函数）。用Rk(sk,uk)表示第k子过程的指标函数。如图5-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见，Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:

2.动态规划的基本概念

26

不过实际应用中往往表示为Rk(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关，过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数gk(sk,uk)累积形成的，适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式．对于k后部子过程的指标函数可以表示为：式中，

表示某种运算，可以是加、减、乘、除、开方等。

2.动态规划的基本概念

(5-2)27

多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:

(5-3)

有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：

(5-4)

总之，具体问题的目标函数表达形式需要视具体问题而定。

2.动态规划的基本概念

28

(七)最优解用fk(sk)表示第k子过程指标函数在状态sk下的最优值,即

称fk(sk)为第k子过程上的最优指标函数；与它相应的子策略称为sk状态下的最优子策略，记为pk*(sk)；而构成该子策赂的各段决策称为该过程上的最优决策，记为；有

简记为

2.动态规划的基本概念

29

特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例只有唯一始点v1即s1取值唯一,故f1(s1)=18就是例1的最优值，而就是例1的最优策略。但若取值不唯一,则问题的最优值记为f0有

最优策略即为s1=s1*状态下的最优策略：

我们把最优策略和最优值统称为问题的最优解。

2.动态规划的基本概念30

按上述定义，所谓最优决策是指它们在全过程上整体最优(即所构成的全过程策略为最优)，而不一定在各阶段上单独最优。

(八)多阶段决策问题的数学模型综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:

2.动态规划的基本概念

（5-5）31

式中“OPT”表示最优化，视具体问题取max或min。

上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列，使之既满足式(5-5)给出的全部约束条件，又使式(5-5)所示的目标函数取得极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线

2.动态规划的基本概念32

二、动态规划的最优化原理与基本方程

1．标号法为进一步阐明动态规划方法的基本思路，我们介绍一种只适用于例这类最优路线问题的特殊解法——标号法。标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。通常标号法采取“逆序求解”的方法来寻找问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。

2.动态规划的基本原理

33

下面给出标号法的一般步骤：

1.从最后一段标起，该段各状态(即各始点)到终点的距离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终点。

2.向前递推，给前一阶段的各个状态标号。每个状态上方方格内的数字表示该状态到终点的最短距离。即为该状态到该阶段已标号的各终点的段长，再分别加上对应终点上方的数字而取其最小者。将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来，表示出各刚标号的点到终点的最短路线。

2.动态规划的基本原理34

3.逐次向前递推，直到将第一阶段的状态(即起点)也标号，起点方格内的数字就是起点到终点的最短距离，从起点开始连接终点的粗箭线就是最短路线。用标号法来求解下例例5.2：网络图5—2表示某城市的局部道路分布图。一货运汽车从S出发，最终到达目的地E。其中Ai(i＝1，2，3),Bj(j＝1，2)和Ck(k＝1，2)是可供汽车选择的途经站点，各点连线上的数字表示两个站点问的距离。问此汽车应走哪条路线，使所经过的路程距离最短?

2.动态规划的基本原理35

2.动态规划的基本原理图5-2某城市的局部道路分布图36

第一步：先考虑第四阶段，即k=4，该阶段共有两个状态：C1、C2，设f4(C1)和f4(C2)分别表示C1、C2到E的最短距离，显然有f4(C1)=5和f4(C2)=8，边界条件f5(E)=0。第二步：即k=3,该阶段共有两个状态:B1,

B2

(1)从B1出发有两种决策:B1→C1，B1→C2

。记d3(B1,C1)表示B1到C1的距离,即,这里的每一种决策的阶段指标函数就是距离，所以，B1→C1的阶段指标函数为d3(B1,C1)＝6，B1→C2的阶段指标函数为d3(B1,C2)＝5。因此有,

f3(B1)＝min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}＝min(6＋5，5＋8)＝11。那么，从出发到E的最短路线是B1→C1→E，对应的决策u3(B1)=C1

。

2.动态规划的基本原理37

(2)从B2出发也有两种决策:B2→C1,B2→C2同理,有f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}＝min(9+5，8+8)＝14，那么，从B2出发到E的最短路线是B2→C1→E，且u3(B2)=C1。

第三步：即k＝2,该阶段共有三个状态:Al,A2,A3(1)从Al出发有两种决策：A1→B1,A1→B2。则

f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}＝min{6＋11，5＋14}＝17，即A1到E的最短路线为A1→B1→C1→E，且u3(A1)＝B1

。

(2)从A2出发也有两种决策:A2→B1,A2→B2。此时，f2(A2)＝min{d2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路线为A2→B1→C1→E，且u3(A2)＝B1。

2.动态规划的基本原理38

(3)从A3出发也有两种决策:A3→B1,A3→B2

此时

f2(A3)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)}＝min{7+11，4+14}＝18，即A3到E的最短路线为A3→B1→C1→E

，对应的u2(A3)＝B2

。第四步：即k＝1，该阶段只有一个状态S,从S出发有三种决策:S→A1,S→A2,S→A3,那么,f1(S)=min{d1(S,A1)+f2(A1),d2(S,A2)+f2(A2)，d3(S,A3)+f2(A3)}＝min{4+17，3+19,3+18}＝21，那么,从S到E共有三条最短路线：

此时,u1(S)＝A1,u1(S)＝A3

，最短距离为21。

2.动态规划的基本原理39

结果如图5-3所示。每个状态上方的方格内的数字表示该状态到E的最短距离，首尾相连的粗箭线构成每一状态到E的最短路线。因此，标号法不但给出起点到终点的最短路线和最短距离，同时也给出每一状态到终点的最短路线及其最短距离。如,A1到E的最短路线是,最短矩离是17

图见下页

2.动态规划的基本原理40

2.动态规划的基本原理图5-3某城市局部道路求最短路径的过程41

2．最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：

2.动态规划的基本原理

则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为42

如第一节所述，基于上述原理，提出了一种逆序递推法；这里可以指出，该法的关键在于给出一种递推关系。一般把这种递推关系称为动态规划的函数基本方程。

3.函数基本方程在上例中，用标号法求解最短路线的计算公式可以概写成：(5-6)

其中在这里表示从状态sk到由决策uk(sk)所决定的状态sk+1之间的距离,是边界条件，表示全过程到第四阶段终点结束。

2.动态规划的基本原理43

一般地，对于n个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第k阶段和第k+1阶段间的递推公式可表示如下：

(1)当过程指标函数为下列“和”的形式时，

相应的函数基本方程为

（5—7）

2.动态规划的基本原理44

(2)当过程指标函数为下列“积”的形式时,

相应的函数基本方程为

（5—8）可以看出，和、积函数的基本方程中边界条件(即的取值)是不同的。

2.动态规划的基本原理453.动态规划方法的基本步骤

标号法仅适用于求解象最短路线问题那样可以用网络图表示的多阶段决策问题。但不少多阶段决策问题不能用网络图表示。此时,应该用函数基本方程来递推求解.一般来说,要用函数基本方程逆推求解,首先要有效地建立动态规划模型,然后再递推求解,最后得出结论.然而,要把一个实际问题用动态规划方法来求解,还必须首先根据问题的要求。把它构造成动态规划模型,这是非常重要的一步。正确地建立一个动态规划模型,往往问题也就解决了一大半,而一个正确的动态规划模型,应该满足哪些条件呢?463.动态规划方法的基本步骤

1．应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。

2．正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：473.动态规划方法的基本步骤

(1)要能够正确地描述受控过程的变化特征。

(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。

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

3．正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。

4.能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk

,uk)493.动态规划方法的基本步骤

5．根据题意,正确地构造出目标与变量的函数关系——目标函数，目标函数应满足下列性质：

(1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策uk

,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数。

(2)要满足递推关系，即

(3)函数对其变元Rk+1来说要严格单调。50

6．写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式

其中表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：3.动态规划方法的基本步骤51

二：动态规划问题求解的一般步骤

逆序求条件最优目标函数顺序求最优策略、最优路线和最优目标函数值。具体过程描述如下:1.逆序地求出条件最优目标函数值集合和条件最优决策集

k=n时，动态规划基本方程是

因为是η段决策过程，不存在η+1阶段，是阶段η的终止状态，也是整个n段决策过程的最终状态。在阶段n之后不再作出决策，因而也不会再发生阶段效应。因此

52这是一个已知的条件，称为动态规划基本方程的边界条件，于是

k=η时的动态规划基本方程成为

上式表明，阶段n相应于状态的后部子过程的最优决策，就是使阶段n的阶段效应为最优的决策，其条件最优目标函数值就是阶段n处于时执行该最优决策的阶段效应，即需要注意的是，和中的是阶段n的初始状态，又是阶段n-1的终止状态，因此它的取值要由阶段n-1的状态和决策确定，它们的值在计算和

时还是未知的。53因此，这里必须就阶段n的所有可能状态

，计算和，即求出第η阶段的条件最优目标函数值集合和条件最优决策集合

由于此时所有的已经求出，故可以根据就阶段n-1的每个可能状态求关于

的条件最优决策54可以象上面一样就阶段1的各个可能状态

求出第一阶段的条件最优决策集合和条件最优目标函数值集合

及相应的条件最优目标函数值552.顺序地求最优决策序列

这一阶段的工作是顺着决策进行的次序进行的，即从阶段1开始，依次进行。

当阶段1的初始状态Xl是唯一确定时(称为始端固定问题)，上面求得的阶段1的条件最优集合也有唯一确定的元素和。按定义是从阶段1的状态起执行最优策

略时的条件最优目标函数值，由于是唯一确定的，因而也就是

整个过程的最优目标函数值，即

相应地，阶段1的条件最优决策

就是阶段1的关于整个

过程的最优决策，即

56当阶段1的初始状态不是唯一的时候，

式中

是

的状态可能集，是中使整个过程取得最优

目标函数值

的初始状态，即整个多段决策过程的最优初始状

态(始端固定问题可以解释为)。阶段1的最优决策是

根据阶段1的最优初始状态

和最优决策，按状态转

移方程可求得阶段2的最优初始状态，进而从阶

段2的条件最优集合中又可找到关于

的最优决策

57余可类推，直至阶段η。其时已知于是即可求出和如下

整个求解过程可如下描述，即所求多段决策过程的最优目标函数是

最优策略或最优决策序列是最优路线或最优状态序列是58

二．动态规划方法的应用举例为进一步说明动态规划模型建立的基本方法及其求解过程,下面通过实际例子用上述方法具体给出求解动态规划方法的基本步骤：例5.3:有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为g,与年初投入生产的机床数量u1的关系为g=g(u1)=8u1,这时,年终机床完好台数将为au1,(a为机床完好率，0<a<1,设a=0.7).在低负荷下生产时,产品的年产量为h,和投入生产的机床数量u2的关系为h=h(u2)=5u2,相应的机床完好率为b(0<b<1,设b=0.9),一般情况下a<b。3.动态规划方法的基本步骤59

假设某厂开始有x=1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。

解：首先构造这个问题的动态规划模型。

1．变量设置

(1)设阶段变量k表示年度，因此，阶段总数n=5。

(2)状态变量sk表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时的完好机床数量。3.动态规划方法的基本步骤60

(3)决策变量uk，表示第k年度中分配于高负荷下生产的机床台数。于是sk-uk便为该年度中分配于低负荷下生产的机床台数．这里sk与uk均取连续变量，当它们有非整数数值时．可以这样理解：如sk＝0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.4时，就表示一台机床在

k年度只有4/10的时间于高负荷下工作．

2．状态转移方程为

k=1，2，…,63.动态规划方法的基本步骤61

3．允许决策集合,在第k段为

4．目标函数。设gk(sk,uk)为第k年度的产量，则gk(sk,uk)=8uk+5(sk-uk),因此，目标函数为k＝1,2,．．．,5

5．条件最优目标函数递推方程。令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系：

k=1,2,3,4,53.动态规划方法的基本步骤62

6.边界条件为下面采用逆序递推计算法,从第5年度开始递推计算。

k=5时有显然，当u5*=s5时，f5(s5)有最大值，相应的有f5(s5)=8s5

k=4时有

3.动态规划方法的基本步骤

,=

=

因此，当u4*=s4时，有最大值f4(s4)=13.6s463

k=3时有

可见，当u3*=s3时，f3(s3)有最大值f3(s3)=17.55s3.

k=2时有

=+=此时，当取u2*=0时有最大值，即f2(s2)=20.8s2，其中s2=0.7u1+0.9(s1-u1)3.动态规划方法的基本步骤

=64

k=1时有

+

=

当取u1*=0时,f1(s1)有最大值，即f1(s1)=23.7s1,因为s1=1000,故f1(s1)=23700个产品．按照上述计算顺序寻踪得到下述计算结果：3.动态规划方法的基本步骤65

上面所讨论的最优决策过程是所谓始端状态s1固定，终端状态s6自由．如果终端也附加上一定的约束条件，那么计算结果将会与之有所差别．例如，若规定在第五个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？3.动态规划方法的基本步骤66

解：由状态转移方程有得

显而易见，由于固定了终端的状态s6，第五年的决策变量U5的允许决策集合U5(s5)也有了约束，上式说明U5(s5)已退化为一个点，即第五年投入高负荷下生产的机床数只能由式U5=4.5s5-2500作出一种决策，故3.动态规划方法的基本步骤＝50067

当k=5时有

当k=4时有

显然，只有取u4*=0，f4(s4)有最大值，即f4(s4)=21.7s4-7500。同理类推3.动态规划方法的基本步骤=

=

=

=68k=3时有

可知,当u3*=0时,f3(s3)有最大值f4(s4)=24.5s3-7500.k=2时有此时,当u2*=0时有最大值,即f2(s2)=27.1s2-75003.动态规划方法的基本步骤

=

=

=

=

+

69

k=1时有

只有取u1*=0时,f1(s1)有最大值，即

f1(s1)=29.4s1-7500。由此可见，为了使下一个五年计划开始的一年有完好的机床500台，其最优策略应该为：在前4年中，都应该把全部机床投人低负荷下生产，在第5年，只能把部分完好机投入高负荷下生产。根据最优策赂，从始端向终端递推计算出各年的状态，即算出每年年初的完好机床台数，因为s1＝1000台，于是有3.动态规划方法的基本步骤==70

因此，u5*=4.5s5-2500=425(台)，这就是说第5年里还有204台投入低负荷下生产，否则不能保证s6=0.7u5+0.9(u5-s5)=500(台)。在上述最优决策下，5年里所得最高产量为：

f1(s1)＝29.4s1-7500=29400-7500＝21900(个)。可见，附加了终端约束条件以后，其最高产量f1(s1)比终端自由时要低一些。3.动态规划方法的基本步骤（台）（台）（台）（台）（台）（台）71

例5.4：一个线路网络图，从A到E要修建一条石油管道，必须在B、C、D处设立加压站。各边上的数为长度，现需要找一条路使总长度最短。B3B2B1C3C2C1D3D2D1EA4563434547426571097863.动态规划方法的基本步骤72

解:可分成4个阶段：

A到B、B到C、C到D、D到E；每个阶段k

的起点称为状态Sk

；从k

阶段的起点出发可以做一选择，即决定到下一阶段的哪个节点,称为决策Xk

；可见,Sk+1是由Sk

和Xk

所决定的。3.动态规划方法的基本步骤73

那么，从A出发经过4个阶段：A到B、B到C、C到D、D到E，逐次作出决策，构成从A到E

的一条路线，记为u

。

即

u=S1X1

S2X2

S3X3S4X4S5

其中S1=A

，S5=E

记d

为两个相邻节点之间的长度，如d（A，B

3）=3。3.动态规划方法的基本步骤74

①

记fk(Sk)为从Sk到E的最短长度,称为从Sk到E的距离。

那么，f1(A)是从A到E的最短距离，即最优策略的值。3.动态规划方法的基本步骤75

②最短路问题的特点：如果从A到E的最优策略经过某节点，那么这个策略的从该节点到E的一段，必定是该节点到E的所有线路中Sk最短的一条，即这一段的长度为fk（Sk）。（1）逆序法：从E到A。（2）顺序法：对节点Sk，从A到Sk

所有线路中，最短的一条的长度记为φk（Sk），例如φ1（A）=0，称为问题的边界条件。3.动态规划方法的基本步骤76

动态规划模型建立后，对基本方程分段求解，不像线性规划或非线性规划那样有固定的解法，必须根据具体问题的特点，结合数学技巧灵活求解，如动态规划模型中的状态变量与决策变量若被限定只能取离散值，则可采用离散变量的分段穷举法。当动态规划模型中状态变量与决策变量为连续变量，就要根据方程的具体情况灵活选取连续变量的求解方法。如经典解析方法、线性规划方法、非线性规划法或其它数值计算方法等。还有连续变量的离散化解法和高维问题的降维法及疏密格子点法等等。3.动态规划方法的基本步骤77

学习方法建议：第一步先看问题，充分理解问题的条件、情况及求解目标。第二步结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”——这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。4.动态规划方法应用举例78

第三步动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。第四步把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。第五步对照自己的求解，分析成败。4.动态规划方法应用举例79

1.动态规划的四大要素

①状态变量及其可能集合xk

Xk②决策变量及其允许集合uk

Uk

③状态转移方程

xk+1=Tk

(xk,uk

)④阶段效应rk

(xk,uk

)

4.动态规划方法应用举例80

2.动态规划基本方程

fn+1(xn+1)=0(边界条件)

fk(xk)=opt

u{rk

(xk,uk

)+fk+1(xk+1)}

k=n,…,14.动态规划方法应用举例81求最短路径

82

求最短路径1：定步数问题例4.183

将问题分成四个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。

将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)={B3

C1,B3

C2,B3

C3}求最短路径

84

最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为

f5(x5)=f5(E)=0

其含义是从E到E的最短路径为0。

第四阶段的递推方程为 : 求最短路径

85

其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。

由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：求最短路径

86第三阶段的递推方程为：

求最短路径

87由此得到f3(x3)的表达式：

求最短路径

88求最短路径

89由此得到f2(x2)的表达式：求最短路径

90第一阶段的递推方程为：求最短路径

91由此得到f1(x1)的表达式求最短路径

922.不定步数问题

不定步数问题是指从起点到终点的路线所经过的步数不完全相同的工程路线问题。现举例说明动态规划解决此类问题的方法。

例4-2今有一最短路问题如图4-8所示，其中符号含义与例

4-1中的相同，求由s到t的最短距离和最短路线。

93解从图中可知，从s到t的路线中有步数为三步的，如从s到a，c到t，也有5步的，如s到b，a，c，d再到t。因此，该问题属于不定步数问题。对于这种问题，由于无法划分阶段，因而不能严格按例4-1中的求解方法来加以求解，然而，若用r(i，j)表示从

节点i到节点j的距离，用f(i)表示i节点到t节点的最短距离，则根据动态规划原理，应该有:

其中j的取值范围是所有从i可以一步到达的节点。94在一定的条件下，依据此递推关系就可以逐一求解f()在各点上的值(由t往前倒退)。

同时，这一关系给出了函数f()的一个函数方程，其求解也可以通过迭代的方法来实现。

迭代可以针对f()来进行，称为函数迭代法，也可以针对策略{u(i)}(i=s，a，b，c，d)来进行，称为策略迭代法，现分别讨论如下。95(1)用函数迭代法求解

函数迭代法步骤:①先选定一初始函数

②然后用递推关系求如下:这里可以看出，为从i点出发走k步到t的最短距离。96可以证明，若对于某个k，有，对所有节点i成立，则即为条件最优目标函数。

则为s到t的最短距离。

按函数迭代法把本例数据代入得

97上述计算可以继续下去，其结果整理如表4-498

isabCdt

240

84240

1284240

1284240

表4-4函数迭代法计算结果表可见各点到t的最短距离如表中,从计算过程可以逆序找出最短路线，例如，s到t的最短路线是先经过b，见计算的过程而b到t的最短路线长为4，是经过C到t的。见计算的过程，即s→b→c→t。99(2)用策略迭代法求解

策略迭代法步骤:（1）给每个点i选择一个下一步到达的点，

i=s，α，b，

c，d取k=O100代入本例数据计算如下：101102103104105策略迭代法的中间结果汇总如表4-5所示:

表4-5策略选代法结果表

a18b12b

a

d9C8Cbd8C4CCt2t2tdt4t4tt0

0

106资源分配问题107

例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。

资源分配问题108阶段k：每投资一个项目作为一个阶段；状态变量xk：投资第k个项目前的资金数；决策变量uk：第k个项目的投资；决策允许集合：0≤uk≤xk状态转移方程：xk+1=xk-uk阶段指标：vk(xk

,uk)见表中所示；递推方程：fk(xk)=max{vk(xk

,uk)+fk+1(xk+1)}终端条件：f4(x4)=0资源分配问题109k=4，f4(x4)=0

k=3，0≤u3≤x3，x4=x3-u3

资源分配问题110k=2，0≤u2≤x2，x3=x2-u2资源分配问题111k=1，0≤u1≤x1，x2=x1-u1资源分配问题112背包问题113背包问题114则Max

z= c1x1+c2x2+…+cnxn

s.t.w1x1+w2x2+…+wnxn≤W

x1,x2,…,xn为正整数

阶段k：第k次装载第k种物品（k=1,2,…,n）状态变量xk：第k次装载时背包还可以装载的重量；决策变量dk：第k次装载第k种物品的件数；背包问题1154.决策允许集合： Dk(xk)={dk|0

dk

xk/wk，dk为整数}；5.状态转移方程：xk+1=xk-wkdk6.阶段指标：vk=ckdk7.递推方程

fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}8.终端条件：fn+1(xn+1)=0背包问题116

例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5

用动态规划求解f4(x4)=0

对于k=3背包问题117118119120121

机器负荷分配问题122123

构造动态规划模型如下：

阶段k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，…，依次类推；k=6表示第五年末（即第六年初）。

状态变量xk：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数。

决策变量dk：第k年投入高负荷运行的机器数；

状态转移方程：xk+1=0.7dk+0.9(xk-dk)

决策允许集合：Dk(xk)={dk|0

dk

xk}

阶段指标：vk(xk

,dk)=8dk+5(xk-dk)

终端条件：f6(x6)=0

机器负荷分配问题124递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}

dk

Dk(xk)

=max{8dk+5(xk-dk)+fk+1[0.7dk+0.9(xk-dk)]}

0

dk

xk

机器负荷分配问题125f5(x5)=max{8d5+5(x5-d5)+f6(x6)}

0

d5

x5

=max{3d5+5x5}=8x5, d5*=x5

0

d5

x5

f4(x4)=max{8d4+5(x4-d4)+f5(x5)}

0

d4

x4

=max{8d4+5(x4-d4)+8x5}

0

d4

x4

=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}

0

d4

x4

=max{1.4d4+12.3x4}=13.7x4, d4*=x4

0

d4

x4

机器负荷分配问题126f3(x3)=max{8d3+5(x3-d3)+f4(x4)}

0

d3

x3

=max{8d3+5(x3-d3)+13.7x4}

0

d3

x3

=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}

0

d3

x3

=max{0.28d3+17.24x3}=17.52x3, d3*=x3

0

d3

x3

机器负荷分配问题127f2(x2)=max{8d2+5(x2-d2)+f3(x3)}

0

d2

x2

=max{8d2+5(x2-d2)+17.52x3}

0

d2

x2

=max{8d2+5(x2-d2)+17.52[0.7d2+0.9(x2-d2)]}

0

d2

x2

=max{-0.504d2+20.77x2}=20.77x2,d2*=0

0

d2

x2

机器负荷分配问题128f1(x1)=max{8d1+5(x1-d1)+f2(x2)}

0

d1

x1

=max{8d1+5(x1-d1)+20.77x2}

0

d1

x1

=max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]}

0

d1

x1

=max{-0.05d1+23.69x1}=23.69x1,d1*=0

0

d1

x1

机器负荷分配问题129由此可以得到：f1(x1)=23.69x1, d1*=0f2(x2)=20.77x2, d2*=0f3(x3)=17.52x3, d3*=x3f4(x4)=13.60x4, d4*=x4f5(x5)=8x5

d5*=x5用x1=1000代入，得到五年最大产量为f1(x1)=f1(1000)=23690

机器负荷分配问题130每年投入高负荷运行的机器数以每年初完好的机器数为：x1=1000d1*=0,x2=0.7d1+0.9(x1-d1)=900d2*=0,x3=0.7d2+0.9(x2-d2)=810d3*=x3=810,x4=0.7d3+0.9(x3-d3)=567d4*=x4=567,x5=0.7d4+0.9(x4-d4)=397d5*=x5=397,x6=0.7d5+0.9(x5-d5)=278

机器负荷分配问题131

在这个例子中，状态变量的终端值x6是未加约束的，如果要求在第五年末（即第六年初）完好的机器数不少于500台，这时决策变量d5的决策允许集合将成为：

D5(x5)={d5|0.7d5+0.9(x5-d5)

500,d5

0}

即0.9x5-0.2d5

500

d5

0或0

d5

4.5x5-2500

容易想象，这时的最大产量将比x6是自由的情况下小。这个例子可以推广到一般情况。设高负荷生产时机器的完好率为k1，单台产量为p1；低负荷完好率为k2，单台产量为p2。若有t满足:

机器负荷分配问题132则从1—t-1年，年初将全部完好机器投入低负荷运行，从t—n年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。

机器负荷分配问题133生产库存问题134

例5.9：一个工厂生产某种产品,1-

7月份生产成本和产品需求量的变化情

况如下表：

生产库存问题135阶段k：月份，k=1,2,…,7,8；状态变量xk：第k个月初（发货以前）的库存量；决策变量dk：第k个月的生产量；状态转移方程：xk+1=xk-rk+dk；决策允许集合：Dk(xk)={dk

|dk

0,rk+1

xk+1

H} ={dk

|dk

0,rk+1

xk-rk+dk

H}；阶