运筹学 动态规划 运筹学..

Presentation on theme: "运筹学 动态规划 运筹学.."— Presentation transcript:

1 运筹学 动态规划 运筹学.

2 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例

3 1.多阶段决策过程的最优化 多阶段决策过程特点: 一、多阶段决策问题 (Multi-Stage decision process) 状态
x1 阶段1 T1 决策u1 x2 决策u2 阶段2 T2 x3 ... xk 决策uk 阶段k Tk xk+1 xn 决策un 阶段n Tn xn+1

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

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

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

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

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

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

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

11 1.多阶段决策过程的最优化 图5-11 运输网络图示

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

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

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

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

16 1.多阶段决策过程的最优化 具体说，此问题先从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 。

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

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

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

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

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

22 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} ；

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

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

25 2.动态规划的基本概念 （五）状态转移方程 系统在阶段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)无关。系统状态的这种转移，用数学公式描述即有： (5-1)

26 2.动态规划的基本概念 通常称式(5-1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。 (六) 指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。例如：图5—1的指标就是运费。

27 2.动态规划的基本概念 (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)的函数，严格说来，应表示为:

28 2.动态规划的基本概念 不过实际应用中往往表示为Rk(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关，过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数gk(sk,uk)累积形成的，适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式．对于部子过程的指标函数可以表示为： 式中，表示某种运算，可以是加、减、乘、除、开方等。 (5-2)

29 2.动态规划的基本概念 多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即: (5-3)
有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如： (5-4) 总之，具体问题的目标函数表达形式需要视具体问题而定。

30 2.动态规划的基本概念 (七) 最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即
为pk*(sk) ；而构成该子策赂的各段决策称为该 过程上的最优决策，记为 ；有 简记为

31 2.动态规划的基本概念 特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例只有唯一始点v1即s1取值唯一,故f1(s1)=18就是例的最优值，而 就是例的最优策略。 但若取值不唯一,则问题的最优值记为f0有 最优策略即为s1=s1*状态下的最优策略： 我们把最优策略和最优值统称为问题的最 优解。

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

33 2.动态规划的基本概念 式中“OPT”表示最优化，视具体问题取max或min。
上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列 ，使之既满足式(5-5)给出的全部约束条件，又使式(5-5)所示的目标函数取得极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线

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

35 2.动态规划的基本原理 下面给出标号法的一般步骤：
1.从最后一段标起，该段各状态(即各始点)到终点的距离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终点。 2.向前递推，给前一阶段的各个状态标号。每个状态上方方格内的数字表示该状态到终点的最短距离。即为该状态到该阶段已标号的各终点的段长，再分别加上对应终点上方的数字而取其最小者。将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来，表示出各刚标号的点到终点的最短路线。

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

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

38 2.动态规划的基本原理 第一步：先考虑第四阶段，即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 。

39 2.动态规划的基本原理 (2)从B2出发也有两种决策:B2→C1,B2→C2同理, 有f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}＝min(9+5，8+87)＝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。

40 2.动态规划的基本原理 (3)从A3出发也有两种决策:A3→B1,A3→B2 此时
f2(A2)=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,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路线为A2→B1→C1→E ，且u3(A2)＝B1 。 那么,从S到E共有三条最短路线： 此时,u1(S)＝A1题 和 此时,u1(S)＝A3 ，最短距离为21。

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

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

43 2.动态规划的基本原理 2．最优化原理 （贝尔曼最优化原理）
作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为： 则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为

44 2.动态规划的基本原理 如第一节所述，基于上述原理，提出了一
种逆序递推法；这里可以指出，该法的关键在于给出一种递推关系。一般把这种递推关系称为动态规划的函数基本方程。 3.函数基本方程 在例中，用标号法求解最短路线的计 算公式可以概括写成： (5-6) 其中， 在这里表示从状态sk到由决策uk(sk)所决定的状态sk+1之间的距离,是边界条件，表示全过程到第四阶段终点结束。

45 2.动态规划的基本原理 一般地，对于n个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第k阶段和第k+1阶段间的递推公式可表示如下： (1)当过程指标函数为下列“和”的形式时， 相应的函数基本方程为 （5—7）

46 2.动态规划的基本原理 (2) 当过程指标函数为下列“积”的形式时, 相应的函数基本方程为 （5—8） 可以看出，和、积函数的基本方程中边界
条件(即 的取值)是不同的。

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

48 3.动态规划方法的基本步骤 1．应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。 2．正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：

49 3.动态规划方法的基本步骤 (1)要能够正确地描述受控过程的变化特征。
(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。 (3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数．而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。

50 3.动态规划方法的基本步骤 3．正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。 4. 能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk ,uk)

51 3.动态规划方法的基本步骤 5．根据题意,正确地构造出目标与变量的函数关系——目标函数，目标函数应满足下列性质：
(1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk ,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数。 (2)要满足递推关系，即 (3)函数 对其变元Rk+1来说要严格单调。

52 3.动态规划方法的基本步骤 6．写出动态规划函数基本方程 例如常见的指标函数是取各段指标和的形式
其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ：

53 3.动态规划方法的基本步骤 二．动态规划方法的基本步骤
为进一步说明动态规划模型建立的基本方法及其求解过程,下面通过实际例子用上述方法具体给出求解动态规划方法的基本步骤： 例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。

54 3.动态规划方法的基本步骤 假设某厂开始有x=1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。 解：首先构造这个问题的动态规划模型。 1．变量设置 (1)设阶段变量k表示年度，因此，阶段总数n=5。 (2)状态变量sk表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时的完好机床数量。

55 3.动态规划方法的基本步骤 (3)决策变量uk，表示第k年度中分配于高负荷下生产的机床台数。于是sk- uk便为该年度中分配于低负荷下生产的机床台数． 这里sk与uk均取连续变量，当它们有非整数数值时．可以这样理解：如sk＝0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.4时，就表示一台机床在 k年度只有4/10的时间于高负荷下工作． 2．状态转移方程为 k=1，2，…,6

56 3.动态规划方法的基本步骤 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,5

57 3.动态规划方法的基本步骤 因此，当u4*=s4时，有最大值f4(s4)=13.6s4 6.边界条件为
下面采用逆序递推计算法,从第5年度开始递推计算。 k=5时有 显然，当u5*=s5时，f5(s5)有最大值，相应的有f5(s5)=8s5 k=4时有 , = 因此，当u4*=s4时，有最大值f4(s4)=13.6s4

58 3.动态规划方法的基本步骤 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) =

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

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

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

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

63 3.动态规划方法的基本步骤 k=3时有 可知,当u3*=0时,f3(s3)有最大值f4(s4)=24.5s3-7500. k=2时有
+ =

64 3.动态规划方法的基本步骤 k=1时有 只有取u1*=0时,f1(s1)有最大值，即 f1(s1)=29.4s1-7500 。

65 3.动态规划方法的基本步骤 （台） （台） （台） （台） （台） （台） 因此，u5*=4.5s5-2500=425(台)，这就是说第5年里还有204台投入低负荷下生产，否则不能保证s6=0.7u5+0.9(u5-s5)=500(台)。 在上述最优决策下，5年里所得最高产量为： f1(s1)＝29.4s1-7500= ＝21900(个)。 可见，附加了终端约束条件以后，其最高产量f1(s1)比终端自由时要低一些。

66 3.动态规划方法的基本步骤 例5.4：一个线路网络图，从A到E要修建一条石油管道，必须 在B、C、D处设立加压站。各边上的数为长度，现需要找一条路使总长度最短。 B3 B2 B1 C3 C2 C1 D3 D2 D1 E A 4 5 6 3 7 2 10 9 8

67 3.动态规划方法的基本步骤 解: 可分成4个阶段：
解: 可分成4个阶段： A到B、B到C、C到D、D到E； 每个阶段 k 的起点称为状态Sk ； 从 k 阶段的起点出发可以做一选择，即决定到下一阶段的哪个节点,称为决策Xk ；可见,Sk+1 是由 Sk 和Xk 所决定的。

68 3.动态规划方法的基本步骤 那么，从A出发经过4个阶段：A到B、B到C、C到D、D到E，逐次作出决策，构成从A到E 的一条路线，记为 u 。
即 u = S1 X1 S2 X2 S3 X3 S4 X4 S5 其中 S1 = A ，S5 = E 记 d 为两个相邻节点之间的长度， 如 d（A，B 3）= 3 。

69 3.动态规划方法的基本步骤 ① 记 fk(Sk)为从Sk到E的最短长度,称为从Sk到E的距离。
那么，f1(A)是从A到E的最短距离，即最优策略的值。

70 3.动态规划方法的基本步骤 （1）逆序法：从E到A。
② 最短路问题的特点：如果从A到E的最优策略经过某节点，那么这个策略的从该节点到E的一段，必定是该节点到E的所有线路中 Sk最短的一条，即这一段的长度为 fk（Sk）。 （1）逆序法：从E到A。 （2）顺序法：对节点Sk，从A到Sk 所有线路中，最短的一条的长度记为 φk（S k），例如φ1（A）= 0，称为问题的边界条件。

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

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

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

74 4.动态规划方法应用举例 1.动态规划的四大要素 ① 状态变量及其可能集合 xk  Xk ② 决策变量及其允许集合 uk  Uk
③ 状态转移方程 xk+1= Tk (xk ,uk ) ④ 阶段效应 rk ( xk , uk )

75 4.动态规划方法应用举例 返回 2. 动态规划基本方程 fn+1(xn+1) = 0 (边界条件)
fk(xk) = opt u{rk ( xk , uk ) + fk+1(xk+1) } k = n,…,1 返回

76 求 最 短 路 径

77 求 最 短 路 径 例5.5

78 求 最 短 路 径 将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。 将决策定义为到达下一站所选择的 路径，例如目前的状态是x2=B3，这时 决策允许集合包含三个决策，它们是 D2(x2)=D2(B3)={B3C1,B3C2,B3C3}

79 最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为 f5(x5)=f5(E)=0 其含义是从E到E的最短路径为0。
求 最 短 路 径 最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为 f5(x5)=f5(E)=0 其含义是从E到E的最短路径为0。 第四阶段的递推方程为 :

80 其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。
求 最 短 路 径 其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。 由此得到f4(x4)的表达式。由于这是 一个离散的函数，取值用列表表示：

81 求 最 短 路 径 第三阶段的递推方程为：

82 求 最 短 路 径 由此得到f3(x3)的表达式：

83 求 最 短 路 径

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

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

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

87 资 源 分 配 问 题

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

89 资 源 分 配 问 题 阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资；
决策允许集合：0≤dk≤xk 状态转移方程：xk+1=xk-dk 阶段指标：vk(xk ,dk)见表中所示； 递推方程：fk(xk)=max{vk(xk ,dk)+fk+1(xk+1)} 终端条件：f4(x4)=0

90 k=4，f4(x4)=0 k=3，0≤d3≤x3，x4=x3-d3
资 源 分 配 问 题 k=4，f4(x4)=0 k=3，0≤d3≤x3，x4=x3-d3

91 资 源 分 配 问 题 k=2，0≤d2≤x2，x3=x2-d2

92 资 源 分 配 问 题 k=1，0≤d1≤x1，x2=x1-d1

93 背 包 问 题

94 背 包 问 题

95 则 Max z= c1x1+c2x2+…+cnxn s.t. w1x1+w2x2+…+wnxn≤W x1,x2,…,xn为正整数
背 包 问 题 则 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种物品的件数；

96 背 包 问 题 Dk(xk)={dk|0 dkxk/wk，dk为整数}； fk(xk)=max{ckdk+fk+1(xk+1)}
背 包 问 题 4. 决策允许集合： Dk(xk)={dk|0 dkxk/wk，dk为整数}； 5. 状态转移方程：xk+1=xk-wkdk 6. 阶段指标：vk=ckdk 7. 递推方程 fk(xk)=max{ckdk+fk+1(xk+1)} =max{ckdk+fk+1(xk-wkdk)} 8. 终端条件：fn+1(xn+1)=0

97 背 包 问 题 例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5 用动态规划求解 f4(x4)=0 对于k=3

98

99

100

101

102 机器负荷分配问题

103

104 机器负荷分配问题 构造动态规划模型如下： 阶段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

105 机器负荷分配问题 递推方程：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)]} dkxk

106 机器负荷分配问题 f5(x5)=max{8d5+5(x5-d5)+f6(x6)} 0d5x =max{3d5+5x5}=8x5, d5*=x5 0d5x5 f4(x4)=max{8d4+5(x4-d4)+f5(x5)} 0d4x =max{8d4+5(x4-d4)+8x5} 0d4x =max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]} 0d4x =max{1.4d4+12.3x4}=13.7x4, d4*=x4 0d4x4

107 机器负荷分配问题 f3(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.28d x3}=17.52x3, d3*=x3 0d3x3

108 机器负荷分配问题 f2(x2)=max{8d2+5(x2-d2)+f3(x3)} 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.504d x2}=20.77x2,d2*= d2x2

109 机器负荷分配问题 f1(x1)=max{8d1+5(x1-d1)+f2(x2)} 0d1x =max{8d1+5(x1-d1)+20.77x2} d1x =max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]} 0d1x =max{-0.05d x1}=23.69x1,d1*= d1x1

110 机器负荷分配问题 由此可以得到： f1(x1)=23.69x1, d1*=0 f2(x2)=20.77x2, d2*=0
f3(x3)=17.52x3, d3*=x3 f4(x4)=13.60x4, d4*=x4 f5(x5)=8x d5*=x5 用x1=1000代入，得到五年最大产量为 f1(x1)=f1(1000)=23690

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

112 机器负荷分配问题 在这个例子中，状态变量的终端值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满足:

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

114 生 产 库 存 问 题

115 例5.9：一个工厂生产某种产品,1- 7月份生产成本和产品需求量的变化情 况如下表：
生 产 库 存 问 题 例5.9：一个工厂生产某种产品, 月份生产成本和产品需求量的变化情 况如下表：

116 生 产 库 存 问 题 阶段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 }； 阶段指标：vk(xk ,dk)=ckdk； 终端条件：f8(x8)=0, x8=0；

117 生 产 库 存 问 题 递推方程：fk(xk)=min{vk(xk ,dk)+fk+1(xk+1)} dkDk(xk) =min{ckdk+fk+1(xk-rk+dk)} dkDk(xk) 对于k=7 因为 x8=0 有 d7=0 递推方程为 f7(x7)=min{c7d7+f8(x8)}= d7=0

118 生 产 库 存 问 题 对于k=6 因为 d7=0，所以 x7=r7=4 而 x6-r6+d6=x7=4 因此有 d6=x7+r6-x6=4+7-x6=11-x6 也是唯一的决策。因此递推方程为： f6(x6)=min{c6d6+f7(x7)} d6=11-x6 =10d6=10(11-x6)=110-10x6

119 生 产 库 存 问 题 对于k=5 f5(x5)=min{c5d5+f6(x6)} d5D5(x5)
=min{20d x6} d5D5(x5) =min{20d (x5-r5+d5)} d5D5(x5) =min{20d (x5-2+d5)} =min{10d5-10x5+130} D5(x5) ={d5| d50, r6x5-r5+d5H } ={d5|d50, r6+r5-x5d5H+r5-x5} ={d5| d50, 9-x5d511-x5}

120 生 产 库 存 问 题 因为x5H=9，因此9-x50，决策允许集合可以简化为 D5(x5)={d5| 9-x5d511-x5} 递推方程成为 f5(x5)=min{10d5-10x5+130} x5d511-x5 =10(9-x5)-10x =220-20x d5*=9-x5

121 生 产 库 存 问 题 对于k=4 f4(x4)=min{c4d4+f5(x5)} d4D4(x4) =min{17d x5} d4D4(x4) =min{17d (x4-r4+d4)} d4D4(x4) =min{17d (x4-3+d4)} d4D4(x4) =min{-3d4-20x4+280} d4D4(x4)

122 生 产 库 存 问 题 由于 在f4(x4)的表达式中d4的系数是-3， 因此d4在决策允许集合中应取集合中的 最大值，即d4=12-x4 由此 f4(x4)=-3(12-x4)-20x4+280 =-17x4+244 D4(x4)={d4| d40, r5x4-r4+d4H} ={d4| d40, r5+r4-x4d4H+r4-x4} ={d4| d40, 5-x4d412-x4} ={d4| max[0,5-x4]d412-x4}

123 生 产 库 存 问 题 对于k=3 f3(x3)=min {c3d3+f4(x4)} d3D3(x3) =min {13d x4} d3D3(x3) =min {13d (x3-r3+d3)} d3D3(x3) =min {-4d3-17x3+329} d3D3(x3) D3(x3)={d3| d30,r4x3-r3+d3H} ={d3| d30,r4+r3-x3d3H+r3-x3} ={d3| d30,8-x3d314-x3} ={d3| max[0,8-x3]d314-x3} 由此 f3(x3)=-4(14-x3)-17x =-13x3+273, d3*=14-x3

124 生 产 库 存 问 题 对于k=2 f2(x2)=min{c2d2+f3(x3)} d2D2(x2) =min{18d x3} d2D2(x2) =min{18d (x2-r2+d2)} d2D2(x2) =min{18d (x2-8+d2)} d2D2(x2) =min{5d2-13x2+377} d2D2(x2) D2(x2)={d2|d20,r3x2-r2+d2H} ={d2|d20,r3+r2-x2d2H+r2-x2} ={d2|d20,13-x2d217-x2}

125 生 产 库 存 问 题 因为 13-x2>0 所以 d2(x2)={d2|13-x2d217-x2} 由此 f2(x2)=5(13-x2)-13x =-18x2+442, d2*=13-x2

126 生 产 库 存 问 题 对于k=1 f1(x1)=min{c1d1+f2(x2)} d1D1(x1) =min{11d x2} d1D1(x1) =min{11d (x1-r1+d1)} d1D1(x1) =min{11d (x1-0+d1)} d1D1(x1) =min{-7d1-18x1+442} d1D1(x1) D1(x1)={d1|d10,r2x1-r1+d1H} ={d1|d10,r2+r1-x1d1H+r1-x1} ={d1|d10,8-x1d19-x1}

127 生 产 库 存 问 题 根据题意 x1=2 所以 D1(x1)={d1| 6d17} 由此 d1=7 f1(x1)=-7d1-18x =-7×7－18×2＋442 =357 将以上结果总结成下表：

128 设 备 更 新 问 题

129 设 备 更 新 问 题 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，

130

131 设 备 更 新 问 题

132 设 备 更 新 问 题 例5.10：设具体数据如下：

133

134

135

136

137

138

139

140

141 97

142 由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。
设 备 更 新 问 题 由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。 这两个决策是