高级运筹学第5章new

1、运筹学东北财经大学信息工程学院肖文峰E-mail:Tel:运运 筹筹 学学 1.运筹学思想与运筹学建模 2.基本概念和基本理论 3.线性规划 4.非线性规划 5.动态规划 6.整数规划 7.网络计划 8.智能优化计算简介 第五章 动态规划本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例 动态规划是运筹学的重要分支之一，它是解动态规划是运筹学的重要分支之一，它是解决多阶段决策过程最优化的一种方法。决多阶段决策过程最优化的一种方法。该法是由美国数学家贝尔曼（该法是由美国数学家贝尔曼（R. Bellman）等

2、人 在 二 十 世 纪等 人 在 二 十 世 纪 5 0 年 代 首 先 提 出 的 。年 代 首 先 提 出 的 。R.Bellman于于1957年发表的年发表的“动态规划动态规划”一一书是动态规划方面的第一本著作。书是动态规划方面的第一本著作。目前，动态规划已成功地用于解决资源分配、目前，动态规划已成功地用于解决资源分配、货物装运、设备更新、生产计划以及复合系货物装运、设备更新、生产计划以及复合系统可靠性等许多问题。统可靠性等许多问题。一、多阶段决策问题(Multi-Stage decision process)多阶段决策过程特点:状态状态 x x1 1阶段阶段1 1T T1 1决策决策u

3、 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+11.多阶段决策过程的最优化多阶段决策过程的最优化1.多阶段决策过程的最优化多阶段决策过程的最优化 动态规划方法与动态规划方法与“时间时间”关系很关系很密切，随着时间过程的发展而决定各密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这时段的决策，产生一个决策序列，这就是就是“动态动态”的意思

4、。然而它也可以的意思。然而它也可以处理与时间无关的静态问题，只要在处理与时间无关的静态问题，只要在问题中人为地引入问题中人为地引入“时段时段”因素，就因素，就可以将其转化为一个多阶段决策问题。可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。在本章中将介绍这种处理方法。1.多阶段决策过程的最优化多阶段决策过程的最优化 二、多阶段决策问题举例 属于多阶段决策类的问题很多，例属于多阶段决策类的问题很多，例如：如： 1)工厂生产过程：由于市场需求是一随：由于市场需求是一随着时间而变化的因素，因此，为了取得着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产全年最佳经济效益

5、，就要在全年的生产过程中，逐月或者逐季度地根据库存和过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。需求情况决定生产计划安排。1.多阶段决策过程的最优化多阶段决策过程的最优化 2)设备更新问题：一般企业用于生产活一般企业用于生产活动的设备，刚买来时故障少，经济效益高，动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、降，经济效益差，

6、并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最衡决定设备的使用年限，使总的经济效益最好。好。1.多阶段决策过程的最优化多阶段决策过程的最优化 3)连续生产过程的控制问题：一般：一般化工生产过程中，常包含一系列完化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行因此，应该如何根据各工序的运行状况，控制生产过程

7、中各设备的输状况，控制生产过程中各设备的输入和输出，以使总产量最大。入和输出，以使总产量最大。1.多阶段决策过程的最优化多阶段决策过程的最优化许多问题的发展过程都与时间因素有关。许多问题的发展过程都与时间因素有关。在这类多阶段决策问题中，在这类多阶段决策问题中，阶段的划分阶段的划分常取时间区段常取时间区段来表示，并且各个阶段上来表示，并且各个阶段上的决策往往也与时间因素有关。这就使的决策往往也与时间因素有关。这就使它具有了它具有了“动态动态”的含义，所以把处理的含义，所以把处理这类动态问题的方法称为动态规划方法。这类动态问题的方法称为动态规划方法。实际中尚有许多不包含时间因素的一类实际中尚有许

8、多不包含时间因素的一类“静态静态”决策问题，就其本质而言是一决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是次决策问题，是非动态决策问题，但是也可以也可以人为地引入阶段的概念人为地引入阶段的概念当作多阶当作多阶段决策问题，应用动态规划方法加以解段决策问题，应用动态规划方法加以解决决。1.多阶段决策过程的最优化多阶段决策过程的最优化 4）资源分配问题：便属于这类静态便属于这类静态问题。如：某工业部门或公司，拟对其问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种制定出收益最大的资源分配方案。这种问题

9、原本要求一次确定出对各企业的资问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题成一个多阶段决策问题( (后面我们将详细后面我们将详细讨论这个问题讨论这个问题) )。1.多阶段决策过程的最优化多阶段决策过程的最优化 5）运输网络问题：如：如图图7 71 1所示的运输网络，点间连线上的数所示的运输网络，点间连线上的数字表示两地距离字表示两地距离( (也可是运费、时也可是运费、时间等间等) )

10、，要求从，要求从f fk k( (s sk k) )至至v v1010的最短路的最短路线。线。 这种运输网络问题也是静态决策这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，问题。但是，按照网络中点的分布，可以把它分为可以把它分为4 4个阶段，而作为多个阶段，而作为多阶段决策问题来研究。阶段决策问题来研究。 1.多阶段决策过程的最优化多阶段决策过程的最优化三、动态规划求解的多阶段决策问题的特点通常多阶段决策过程的发展是通过状通常多阶段决策过程的发展是通过状态的一系列变换来实现的。态的一系列变换来实现的。 一般情况下，系统在某个阶段的状态一般情况下，系统在某个阶段的状态转移除与本阶段的

11、状态和决策有关外，转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策还可能与系统过去经历的状态和决策有关。有关。适合于用动态规划方法求解的只是一适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即类特殊的多阶段决策问题，即具有具有“无后效性无后效性”的多阶段决策过程的多阶段决策过程。1.多阶段决策过程的最优化多阶段决策过程的最优化无后效性无后效性（又称马尔柯夫性）（又称马尔柯夫性） 指系统从某个阶段往后的发展，指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往仅由本阶段所处的状态及其往后的决策所决定，与系统以前后的决策所决定，与系统以前经历的状态和决策经历的状态和决策

12、( (历史历史) )无关。无关。1.多阶段决策过程的最优化多阶段决策过程的最优化 四、动态规划方法导引 为了说明动态规划的基为了说明动态规划的基本思想方法和特点，下本思想方法和特点，下面以图面以图7 71 1所示为例讨所示为例讨论的求最短路问题的方论的求最短路问题的方法法 1 1.多阶段决策过程的最优化多阶段决策过程的最优化 图711 运输网络图示 返回1.多阶段决策过程的最优化多阶段决策过程的最优化一般有三种思路求解 全枚举法或穷举法：全枚举法或穷举法：它的基本思想是列举出所它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进有可能发生的方案和结果，再对它们一一进行比较，求出最优方案

13、。行比较，求出最优方案。 可以计算：从可以计算：从v v1 1到到v v1010的路程可以分为的路程可以分为4 4个阶个阶段。第一段走法有段。第一段走法有3 3种，第二、三两段走法各种，第二、三两段走法各有有2 2种，第四段走法仅种，第四段走法仅1 1种，共有种，共有3 32 22 21 11212条可能的路线，分别算出各条路线的距条可能的路线，分别算出各条路线的距离，最后进行比较，可知离，最后进行比较，可知最优路线是最优路线是v v1 1 v v3 3 v v7 7 v v9 9 v v10 10 , ,最短距离是最短距离是1818用穷举法求用穷举法求最优路线的计算工作量将会十分庞大，而且最

14、优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算其中包含着许多重复计算1.多阶段决策过程的最优化多阶段决策过程的最优化 局部最优路径法：局部最优路径法：某人从某人从k k点出点出发，并不顾及全线是否最短，发，并不顾及全线是否最短，只是选择当前最短途径，只是选择当前最短途径，“逢逢近便走近便走”，错误地以为局部最错误地以为局部最优会致整体最优优会致整体最优，在这种想法，在这种想法指导下，所取决策必是指导下，所取决策必是v v1 1 v v3 3 v v5 5 v v8 8 v v1010 ，全程长度是，全程长度是2020；显然，这种方法的结果常；显然，这种方法的结果常是错误的是错误的1

15、.多阶段决策过程的最优化多阶段决策过程的最优化 动态规划方法：动态规划方法：动态规划方法寻动态规划方法寻求该最短路问题的基本思想是，求该最短路问题的基本思想是，首先将问题划分为首先将问题划分为4 4个阶段，每个阶段，每次的选择总是综合后继过程的一次的选择总是综合后继过程的一并最优进行考虑，在各段所有可并最优进行考虑，在各段所有可能状态的最优后继过程都已求得能状态的最优后继过程都已求得的情况下，全程的最优路线便也的情况下，全程的最优路线便也随之得到（如图）随之得到（如图）1.多阶段决策过程的最优化多阶段决策过程的最优化图1 运输网络动态规划方法求解图示跳过过程跳过过程1.多阶段决策过程的最优化多

16、阶段决策过程的最优化 具体说，此问题先从具体说，此问题先从v v1010开始，因为开始，因为v v1010是终点。是终点。再无后继过程，故可以接着考虑第再无后继过程，故可以接着考虑第4 4阶段上所阶段上所有可能状态有可能状态v v8 8 , ,v v9 9的最优后续过程因为从的最优后续过程因为从v v8 8 , ,v v9 9 到到v v1010的路线是唯一的，所以的路线是唯一的，所以v v8 8 , ,v v9 9 的最的最优决策和最优后继过程就是到优决策和最优后继过程就是到v v1010 ，它们的最，它们的最短距离分别是短距离分别是5 5和和3 3。 接着考虑阶段接着考虑阶段3 3上可能的

17、状态上可能的状态v v5 5 , ,v v6 6 , , v v7 7 , , 到到v v1010的最优决策和最优后继过程在状态的最优决策和最优后继过程在状态V V5 5上，虽上，虽然到然到v v8 8是是8 8，到，到v v9 9是是9 9，但是综合考虑后继过程，但是综合考虑后继过程整体最优，取最优决策是到整体最优，取最优决策是到v v9 9, ,最优后继过程最优后继过程是是v v5 5v v9 9 v v10 10 ，最短距离是，最短距离是1212同理，状态同理，状态v v6 6的最优决策是至的最优决策是至v v8 8 ；v v7 7的最优决策是到的最优决策是到v v9 9 。1.多阶段决

18、策过程的最优化多阶段决策过程的最优化 同样，当阶段同样，当阶段3 3上所有可能状态的最上所有可能状态的最优后继过程都已求得后，便可以开始考虑优后继过程都已求得后，便可以开始考虑阶段阶段2 2上所有可能状态的最优决策和最优上所有可能状态的最优决策和最优后继过程，如后继过程，如v v2 2的最优决策是到的最优决策是到v v5 5, ,最优路最优路线是线是v v2 2v v5 5v v9 9v v10 10 ，最短距离是，最短距离是1515依此依此类推，最后可以得到从初始状态类推，最后可以得到从初始状态v v1 1的最优的最优决策是到决策是到v v3 3最优路线是最优路线是v v1 1v v3 3v

19、 v7 7v v9 9v v10 10 ，全程的最短距离是全程的最短距离是1818。图。图7 71 1中粗实线表中粗实线表示各点到的最优路线，每点上方括号内的示各点到的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。数字表示该点到终点的最短路距离。1.多阶段决策过程的最优化多阶段决策过程的最优化 小 结全枚举法虽可找出最优方案，全枚举法虽可找出最优方案，但不是个好算法，但不是个好算法，局部最优法则完全是个错误局部最优法则完全是个错误方法，方法，只有只有动态规划方法属较科学动态规划方法属较科学有效的算法有效的算法 2.动态规划的基本概念动态规划的基本概念 一、动态规划的基本概念 使用动

20、态规划方法解决多阶段决使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说的下述一些基本术语进一步加以说明和定义：明和定义： 2.动态规划的基本概念动态规划的基本概念 (一) 阶段和阶段变量 为了便于求解和表示决策及过程的发展为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段相互联系又有区别的子问题，称之为多段决策问题的

21、决策问题的阶段阶段。一个阶段，就是需要作。一个阶段，就是需要作出一个决策的子问题，通常，出一个决策的子问题，通常，阶段是按决阶段是按决策进行的时间或空间上先后顺序划分的策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作用以描述阶段的变量叫作阶段变量阶段变量，一般，一般以以k k表示阶段变量阶段数等于多段决策表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目。过程从开始到结束所需作出决策的数目。 2.动态规划的基本概念动态规划的基本概念 （二）状态、状态变量和可能状态集 1. 1.状态与状态变量状态与状态变量。用以描述事物。用以描述事物( (或系统或系统) )在在某特定的时

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

23、即指其初始状态。见，通常定义阶段的状态即指其初始状态。 2.动态规划的基本概念动态规划的基本概念 2可能状态集 一般状态变量的取值有一定的范围或一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相态的约束条件。通常可能状态集用相应应阶段状态阶段状态s sk k的大写字母的大写字母Sk表示，表示，skSk，可能状态集可以是一离散取值的集合，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体也可以为一连续的取值区间，视具体问题而定问题而定 （三

24、）决策、决策变量和允许决策集合 决策决策的实质是关于状态的选择，是决策者的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的从给定阶段状态出发对下一阶段状态作出的选择。选择。 用以描述决策变化的量称之用以描述决策变化的量称之决策变量。决策变量。决决策变量的值可以用数，向量、其它量，也可策变量的值可以用数，向量、其它量，也可以是状态变量的函数，记以以是状态变量的函数，记以uk= uk(sk)，表示，表示于阶段于阶段k k状态状态s sk k时的决策变量。时的决策变量。 决策变量的取值往往也有一定的允许范围，决策变量的取值往往也有一定的允许范围，称之称之允许决策集合允许决策集合。

25、决策变量。决策变量uk(sk)的允许决策集用Uk(sk)表示, uk(sk) Uk(sk)允许决策集允许决策集合实际是决策的约束条件。合实际是决策的约束条件。 2.动态规划的基本概念动态规划的基本概念 （四）、策略和允许策略集合 策略策略(Policy)(Policy)也叫决策序列策略也叫决策序列策略有有全过程策略全过程策略和和k k部子策略部子策略之分，全之分，全过程策略是指由依次进行的过程策略是指由依次进行的n n个阶段个阶段决策构成的决策序列，简称策略，决策构成的决策序列，简称策略，表示为表示为p1,nu1,u2,un。从。从k k阶段到阶段到第第n n阶段，依次进行的阶段决策构成阶段，

26、依次进行的阶段决策构成的决策序列称为的决策序列称为k k部子策略部子策略, ,表示为表示为pk,nuk,uk+1,un ，显然当，显然当k k=1=1时的时的k k部子策略就是全过程策略。部子策略就是全过程策略。 2.动态规划的基本概念动态规划的基本概念2.动态规划的基本概念动态规划的基本概念在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n ，从允许策略集中，找出具有最优效果的策略称为最优策略。 （五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移

27、，即系统由阶段k的初始状态sk转移到终止状态sk+1 。 对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2, ,sk-1及其决策u1(s1), u2(s2)uk-1(sk-1)无关。 2.动态规划的基本概念动态规划的基本概念 系统状态的这种转移，用数学公式描述即有： (7- (7-1 1） 通常称上式通常称上式(7-1)(7-1)为多阶段决策过程为多阶段决策过程的状态转移方程。有些问题的状态的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，转移方程不一定存在数学表达式，但是它们的状态转移，还

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

29、(2)过程指标函数（也称目标函数）。过程指标函数（也称目标函数）。 用Rk(sk,uk)表示第k子过程的指标函数。 Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为: 2.动态规划的基本概念动态规划的基本概念)(,(kkkkspsR实际应用中可表示为实际应用中可表示为R Rk k( (s sk k, ,u uk k) )或或R Rk k( (s sk k) ) 过程指标函数过程指标函数R Rk k( (s sk k) )通常是描述所实现的全过程通常是描述所实现的全过程或或k k后部子过程效果优劣的数量指标，它是由各

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

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

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

33、nnkkkksususuLnksusususpnnkkkkkk, 2 , 1),(,),(),()(11LLnkuuupnkkk, 2 , 1,1LL 特别当特别当k k=1=1且且s s1 1取值唯一时，取值唯一时，f f1 1( (s s1 1) )就是问题就是问题的最优值，而的最优值，而p p1 1* * 就是最优策略。就是最优策略。 但若取但若取值不唯一值不唯一, ,则问题的最优值记为则问题的最优值记为f f0 0有有 最优策略即为最优策略即为s s1 1=s s1 1* *状态下的最优策略：状态下的最优策略： 我们把最优策略和最优值统称为问题的最我们把最优策略和最优值统称为问题的最优

34、解。优解。 2.动态规划的基本概念动态规划的基本概念)()(11111011ssfsfoptfSs,),()(211111nuususspL), 2 , 1(nkukL 2.动态规划的基本概念动态规划的基本概念(八) 多阶段决策问题的数学模型 综上所述，适于应用动态规划方法综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型无后效性的多阶段决策问题的数学模型呈以下形式呈以下形式: :nkUuSsusTstsusususRRoptfkkkkkkkknnuun, 2 , 1),(. .),(122111LL(7-5）

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

36、,21nuuuL,121nnssssL 二、动态规划的最优化原理与基本方程1标号法( (只适用于一类最优路线问题的只适用于一类最优路线问题的特殊解法）特殊解法） 标号法是借助网络图通过分段标号来求标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。出最优路线的一种简便、直观的方法。通常标号法采取通常标号法采取“逆序求解逆序求解”的方法来的方法来寻找问题的最优解，即从最后阶段开始，寻找问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得逐次向阶段数小的方向推算，最终求得全局最优解。全局最优解。 2.动态规划的基本原理动态规划的基本原理标号法的一般步骤：标号法的一般步

37、骤： （1 1）. .给最后一段给最后一段标号标号，该段各状态，该段各状态( (即各始点即各始点) )到终点的距离用数字分别到终点的距离用数字分别标在各点上方的方格内，并标在各点上方的方格内，并用粗箭用粗箭线连接各点和终点线连接各点和终点。 （2 2）. .向前递推，给前一阶段的各个向前递推，给前一阶段的各个状态状态标号标号。每个状态上方方格内的。每个状态上方方格内的数字表示该状态到终点的最短距离。数字表示该状态到终点的最短距离。将刚标号的点沿着最短距离所对应将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来的已标号的点用粗箭线连接起来，表示出各刚标号的点到终点的最短表示出各刚标号的点

38、到终点的最短路线路线。 2.动态规划的基本原理动态规划的基本原理（3 3）. .逐次向前递推，直到将第逐次向前递推，直到将第一阶段的状态一阶段的状态( (即起点即起点) )标号标号，起，起点方格内的数字就是起点到终点方格内的数字就是起点到终点的点的最短距离最短距离，从，从起点开始连起点开始连接终点的粗箭线接终点的粗箭线就是就是最短路线最短路线。 2.动态规划的基本原理动态规划的基本原理2.动态规划的基本原理动态规划的基本原理 例例7 7.2.2：网络图网络图7 72 2表示某城表示某城市的局部道路分布图。一货运市的局部道路分布图。一货运汽车从汽车从S S出发，最终到达目的地出发，最终到达目的地

39、E E。其中。其中A Ai i( (i i1 1，2 2，3),3),B Bj j( (j j1 1，2)2)和和C Ck k( (k k1 1，2)2)是可供汽车选是可供汽车选择的途经站点，各点连线上的择的途经站点，各点连线上的数字表示两个站点问的距离。数字表示两个站点问的距离。问此汽车应走哪条路线，使所问此汽车应走哪条路线，使所经过的路程距离最短经过的路程距离最短? ? 2.动态规划的基本原理动态规划的基本原理图72 某城市的局部道路分布图 058111417191821 2.动态规划的基本原理动态规划的基本原理图73某城市局部道路求最短路径的过程 结果如图结果如图7 73 3所示。从所示

40、。从S S到到E E最短距离为最短距离为2121共有三条最短路线：共有三条最短路线： (1)(1) (2) (2) (3) (3) 标号法不但给出起点到终点的最短路标号法不但给出起点到终点的最短路线和最短距离，同时也线和最短距离，同时也 给出每一状态到终点的最短给出每一状态到终点的最短 路线及其最短距离。路线及其最短距离。 2.动态规划的基本原理动态规划的基本原理ECBAS111ECBAS113ECBAS1232 2最优化原理最优化原理 （贝尔曼最优化（贝尔曼最优化原理）原理） 作为一个全过程的最优策略具作为一个全过程的最优策略具有这样的性质：有这样的性质：对于最优策略对于最优策略过程中的任意

41、状态而言，无论过程中的任意状态而言，无论其过去的状态和决策如何，余其过去的状态和决策如何，余下的诸决策必构成一个最优子下的诸决策必构成一个最优子策略。策略。 2.动态规划的基本原理动态规划的基本原理2.动态规划的基本原理动态规划的基本原理 该原理的具体解释是，若某一全过程最优策略为： 则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为)(),(,),(),()(221111nnkksususususp LL)(,),(),()(11nnkkkkkksusususp L 3.函数基本方程 基于这个原理，提出了一种逆序递推法；该法的关键

42、在于给出一种递推关系。一般把这种递推关系称为动态规划的函数基本方程。对于求最小的加法的计算公式为： 2.动态规划的基本原理动态规划的基本原理 1 ,2 , 1,),()(,(min)(0)(111)(11LnnksufsusgsfsfkkkkkkksUukknnkkk（边界条件）（边界条件）阶段指标阶段指标一般地，(1)当过程指标函数为“和”的形式 时，相应的函数基本方程为 2.动态规划的基本原理动态规划的基本原理)(,()()(kkkksPpkkspsRoptsfkKk),(nkiiiiusgopt121011111,),()(,()()(LnnksufsusgoptsfsfkkkkkkkU

43、ukknnkk (2) 当过程指标函数为“积”的形式时， 相应的函数基本方程为 可以看出，和、积函数的基本方程中边界 条件(即 的取值)是不同的。 2.动态规划的基本原理动态规划的基本原理)(,()()(kkkksPpkkspsRoptsfkKknkiiiiusgopt),(121111111,)()(,()()(LnnksufsusgoptsfsfkkkkkkkUukknnkk)(11nnsf3.动态规划方法的基本步骤动态规划方法的基本步骤用函数基本方程逆推求解是常用的用函数基本方程逆推求解是常用的方法：方法： 首先要有效地首先要有效地建立动态规划模型建立动态规划模型, ,然后再然后再递推求

44、解递推求解, ,最后最后得出结论得出结论. .正确地建立一个动态规划模型正确地建立一个动态规划模型, ,是解是解决问题的关键。决问题的关键。正确的动态规划模型正确的动态规划模型, ,应该满足下列应该满足下列条件：条件：3.动态规划方法的基本步骤动态规划方法的基本步骤（1）应将实际问题恰当地分割成n个子问题(n个阶段) 通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n。 3.动态规划方法的基本步骤动态规划方法的基本步骤（2）正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性 动态规划中的状态与一般控制系统中和通常所说的

45、状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：3.动态规划方法的基本步骤动态规划方法的基本步骤要能够正确地描述受控过程的变化特征。要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。 3.动态规划方法的基本步骤动态规划方法的基本步骤要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。 一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。 在解静态规划模型时，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数约束条件所表

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

47、步骤动态规划方法的基本步骤（5）正确地写出目标函数，目标函数应满足下列性质：可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk ,uk+1 , ,un 就是说它是定义在全过程和所有后部子过程上的数量函数。 3.动态规划方法的基本步骤动态规划方法的基本步骤要满足递推关系，即函数 对其变元Rk+1来说要严格单调。),(,),(,111111nkkkkknkkkknkssRussususRLL ),(,111nkkkkkssRusL 写出动态规划函数基本方程写出动态规划函数基本方程3.动态规划方法的基本步骤动态规划方法的基本步骤121011111,),()(,()()(L

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

49、放到一边，看书中的求解方法，要充分理解教材中的论述。 第五步 对照自己的求解，分析成败。 4.动态规划方法应用举例动态规划方法应用举例 1. 1.动态规划的四大要素动态规划的四大要素 状态变量及其可能集合状态变量及其可能集合 x xk k X Xk k 决策变量及其允许集合决策变量及其允许集合 u uk k U Uk k 状态转移方程状态转移方程 x xk k+1+1= = T Tk k ( (x xk k , ,u uk k ) ) 阶段效应阶段效应 r rk k ( ( x xk k , , u uk k ) ) 4.动态规划方法应用举例动态规划方法应用举例 2. 动态规划基本方程 fn+

50、1(xn+1) = 0 (边界条件) fk(xk) = opt urk ( xk , uk ) + fk+1(xk+1) k = n , n-1, , 1返回返回4.动态规划方法应用举例动态规划方法应用举例动态规划是一种方法，而不是算法。即对复杂问题需加以分析才能应用动态规划的迭代算法进行求解，而且其中具有很大技巧性。动态规划目前已广泛用于旅行路径问题、资源分配问题、生产计划问题、设备更新问题、排序问题及复合系统可靠性问题等等。求求 最最 短短 路路 径径BACBDBCDEC212312312511214106104131211396581052 阶段1 阶段2 阶段3 阶段4 阶段5 求求

51、最最 短短 路路 径径例7.5 将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。 将决策定义为到达下一站所选择的将决策定义为到达下一站所选择的路径，例如目前的状态是路径，例如目前的状态是x x2 2=B B3 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 求求 最最 短短 路路 径径最优指标函数fk(xk)表示

52、从目前状态到E的最短路径。终端条件为f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为第四阶段的递推方程为: :fxvxdfxdDx4444455444()min(,)()()从 f5(x5)到 f4(x4)的递推过程用下表表示： x4D4(x4) x5v4(x4,d4) v4(x4,d4)+f5(x5) f4(x4) 最优决策 d4*D1D1E E55+0=5*5D1ED2D2E E22+0=2*2D2E求求 最最 短短 路路 径径其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。 由此得到由此得到f f4 4( (

53、x x4 4) )的表达式。由于这是的表达式。由于这是一个离散的函数，取值用列表表示：一个离散的函数，取值用列表表示：f4(x4) 的表达式 x4 f4(x4) 最优决策 d4* D1 5 D1E D2 2 D2E 求求 最最 短短 路路 径径第三阶段的递推方程为：第三阶段的递推方程为：从 f4(x4)到 f3(x3)的递推过程用表格表示如下： x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) 最优决策d3* C1 C1畗D1 C1畗D2 D1 D2 3 9 3+5=8* 9+2=11 8 C1畗D1 C2 C2畗D1 C2畗D2 D1 D2 6 5

54、 6+5=11 5+2=7* 7 C2畗D2 C3 C3畗D1 C3畗D2 D1 D2 8 10 8+5=13 10+2=12* 12 C3畗D2 )(),(min)(44333)(33333xfdxvxfxDd 求求 最最 短短 路路 径径由此得到f3(x3)的表达式：x3 f3(x3) 最 优 决 策d3* C1 8 C1D1 C2 7 C2D2 C3 12 C3D2 第二阶段的递推方程为： )(),(min)(33222)(22222xfdxvxfxDd从f3(x3)到f2(x2)的递推过程用表格表示如下： 求求 最最 短短 路路 径径x2 D2(x2) x3 v2(x2,d2) v2(

55、x2,d2)+f3(x3) f2(x2) 最优决策 d2* B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20* 14+7=21 10+12=22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+8=14* 10+7=17 4+12=16 14 B2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+7=19* 11+12=23 19 B3C2 求求 最最 短短 路路 径径由此得到f2(x2)的表达式：x2 f2(x2) 最优决策d2* B1 20 B1畗C1 B2 14

56、 B2畗C1 B3 19 B3畗C2 求求 最最 短短 路路 径径第一阶段的递推方程为：)(),(min)(22111)(11111xfdxvxfxDd 从f2(x2)到f1(x1)的递推过程用表格表示如下： x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x2) f1(x1) 最优决策 d1* A A B1 A B2 AB3 B1 B2 B3 2 5 1 2+20=22 5+14=19* 1+19=20 19 A B 2 求求 最最 短短 路路 径径由此得到f1(x1)的表达式x1 f1(x1) 最优决策 d1* A 19 A B2 从表达式f1(x1)可以看出，从A

57、到E 的最短路径长度为 19 。由f1(x1)向 f4(x4)回朔，得到最短路径为： A 畗 B2 畗 C1畗 D1畗 E求求 最最 短短 路路 径径资资 源源 分分 配配 问问 题题 例7.6: 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表： 项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨4 万元51 万吨55 万吨58 万吨求对三个项目的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题1.

58、1.阶段阶段k k：每投资一个项目作为一个阶段；：每投资一个项目作为一个阶段；2.2.状态变量状态变量x xk k：投资第：投资第k k个项目前的资金个项目前的资金数；数；3.3.决策变量决策变量d dk k：第：第k k个项目的投资；个项目的投资；4.4.决策允许集合：决策允许集合：00d dk kx xk k5.5.状态转移方程：状态转移方程：x xk k+1+1= =x xk k- -d dk k6.6.阶段指标：阶段指标：v vk k( (x xk k , ,d dk k) )见表中所示；见表中所示；7.7.递推方程：递推方程：f fk k( (x xk k)=)=maxmaxv vk

59、 k( (x xk k , ,d dk k)+)+f fk k+1+1( (x xk k+1+1)8.8.终端条件：终端条件：f f4 4( (x x4 4)=0)=0资资 源源 分分 配配 问问 题题k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=112203030+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=01

60、31111+0=11223030+0=30314545+0=454405858+0=58*584资资 源源 分分 配配 问问 题题k=2，0d2x2，x3=x2-d2x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=0000100+11=111101313+0=13*1310200+30=30*111313+11=242202929+0=293000300+45=45*121313+30=43212929+11=403304343+0=434500400+58=58131313+45=58222929+30=59*314343+11=544