远程运筹学动态规划

1、5.1 多阶段决策过程的最优化多阶段决策过程的最优化5.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理5.3 动态规划方法的基本步骤动态规划方法的基本步骤5.4 动态规划应用举例动态规划应用举例5.15.1多阶段决策过程的最优化多阶段决策过程的最优化一、多阶段决策问题一、多阶段决策问题 动态规划是把多阶段决策问题作为动态规划是把多阶段决策问题作为研究对象。所谓多阶段决策问题，是指这研究对象。所谓多阶段决策问题，是指这样一类活动过程，即根据问题本身的特点，样一类活动过程，即根据问题本身的特点，可以将其求解的全过程划分为若干个相互可以将其求解的全过程划分为若干个相互联系的阶段联系的阶

2、段( (即将问题划分为许多个相互即将问题划分为许多个相互联系的子问题联系的子问题) )，在它的每一阶段都需要，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。后再转移到下一个阶段。往往前一个阶段的决策要影响到后一个阶往往前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。人们把这段的决策，从而影响整个过程。人们把这样的决策过程称做多阶段决策过程样的决策过程称做多阶段决策过程(Multi-Stagedecision process)。各个阶段所确定的各个阶段所确定的决策就构成了一个决策就构成了一个决策序列，称为一个策决策序

3、列，称为一个策略。略。一般来说，由于每一阶段可供选择的一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。就会有许多可供选择的策略。若对应于一个策略，可以由一个量化的指若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效标来确定这个策略所对应的活动过程的效果，那么，不同的策略就有各自的效果。果，那么，不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其

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

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

6、阶段决策问题举例二、多阶段决策问题举例属于多阶段决策类的问题很多，例如属于多阶段决策类的问题很多，例如： 工厂生产过程：由于市场需求是工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。求情况决定生产计划安排。 设备更新问题：一般企业用于生设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使高

7、，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效合权衡决定设备的使用年限，使总的经济效益最好。益最好。 例例 3 3 连续生产过程的控制问题：一般连续生产过程的控制问题：一般化工生产过程中，常包含一

8、系列完成生产过化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大和输出，以使总产量最大。 以上所举问题的发展过程都与时间因素以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就段上的决策往往也与时

9、间因素有关，这就使它具有了使它具有了“动态动态”的含义，所以把处理的含义，所以把处理这类动态问题的方法称为动态规划方法。这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的不过，实际中尚有许多不包含时间因素的一类一类“静态静态”决策问题，就其本质而言是决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。决策问题，应用动态规划方法加以解决。 资源分配问题：便属于这类静态资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟

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

11、1所示的所示的运输网络，点间连线上的数字表示两地距运输网络，点间连线上的数字表示两地距离离( (也可是运费、时间等也可是运费、时间等) )，要求从，要求从f fk k( (s sk k) )至至v v1010的最短路线。的最短路线。 这种运输网络问题也是静态决策问这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把题。但是，按照网络中点的分布，可以把它分为它分为4 4个阶段，而作为多阶段决策问题来个阶段，而作为多阶段决策问题来研究。研究。 v2 5 5 6 14 10 9 3 8 8 7 7 8 8 6 5 6 11 7 9 5 v1 v3 v4 v6 v5 v7 v9 v8 v

12、10 1234图图5-15-1 运输网络图示运输网络图示（10）（14）（16）（15）（17）（22）（22）（21）（27）三、动态规划求解的多阶段决策问题的特点三、动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法的求解就比

13、较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有求解的只是一类特殊的多阶段决策问题，即具有“无后效性无后效性”的多阶段决策过程。所谓无后效性，的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策系统以前经历的状态和决策( (历史历史) )无关。无关。多阶段决策过程特点多阶段决策过程特点: :状态状态 x x1 1阶段阶段1 1T T1 1决策决策u u1 1状态状态 x x2 2决策决

14、策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要点：要点：阶段，状态，决策，状态转移方程，阶段，状态，决策，状态转移方程， k k - - 后部子过程后部子过程四、动态规划方法导引四、动态规划方法导引 例例5.15.1：为了说明动态规划的基本思想方：为了说明动态规划的基本思想方法和特点，下面以图法和特点，下面以图5-15-1所示为例讨论的求最所示为例讨论的求最短路问题的方法。短路问题的

15、方法。 它的它的基本思想是列举出所有可能发生的方案和结果，基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里再对它们一一进行比较，求出最优方案。这里从从v v1 1到到v v1010的路程可以分为的路程可以分为4 4个阶段。第一段的个阶段。第一段的走法有三种，第二三两段的走法各有两种，第走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有四段的走法仅一种，因此共有3 32 22 21 11212条可能的路线，分别算出各条路线的距离，最条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是后进行比较，可知最优路线是v v1 1 v v2

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

17、2 v v5 5 v v9 9 v v1010 ，全程长度是，全程长度是3030；显然，这；显然，这种方法的结果常是错误的种方法的结果常是错误的 动态规划动态规划方法寻求该最短路问题的基本思想是，首先方法寻求该最短路问题的基本思想是，首先将问题划分为将问题划分为4 4个阶段，每次的选择总是综个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。下，全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过为了找出所有可能状态的最优后继过程

18、，动态规划方法总是从过程的最后阶段开程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。段向前递推计算直至始点。具体说，此问题先从具体说，此问题先从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 的

19、最优决策和最优后继过程就是到的最优决策和最优后继过程就是到v v1010 ，它，它们的最短距离分别是们的最短距离分别是1010和和1414。 接着考虑阶段接着考虑阶段3 3上可能的状态上可能的状态v v5 5 , ,v v6 6 , , v v7 7 , , 到到v v1010的最优决策和最优后继过程在状的最优决策和最优后继过程在状态态V V5 5上，虽然到上，虽然到v v8 8是是6 6，到，到v v9 9是是5 5，但是综，但是综综合考虑后继过程整体最优，取最优决策是综合考虑后继过程整体最优，取最优决策是到到v v8 8, ,最优后继过程是最优后继过程是v v5 5v v8 8 v v10

20、 10 ，最短距，最短距离是离是1616同理，状态同理，状态v v6 6的最优决策是至的最优决策是至v v8 8 ；v v7 7的最优决策是到的最优决策是到v v9 9 。 同样，当阶段同样，当阶段3 3上所有可能状态的最优上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段后继过程都已求得后，便可以开始考虑阶段2 2上所有可能状态的最优决策和最优后继过上所有可能状态的最优决策和最优后继过程，如程，如v v2 2的最优决策是到的最优决策是到v v5 5, ,最优路线是最优路线是v v2 2v v5 5v v8 8v v10 10 ，最短距离是，最短距离是2222依此类推，依此类推，最后可

21、以得到从初始状态最后可以得到从初始状态v v1 1的最优决策是到的最优决策是到v v2 2最优路线是最优路线是v v1 1v v2 2v v5 5v v8 8v v10 10 ，全程的，全程的最短距离是最短距离是2727。图。图5151中粗实线表示各点到中粗实线表示各点到的最优路线，每点上圆括号内的数字表示该的最优路线，每点上圆括号内的数字表示该点到终点的最短路距离。点到终点的最短路距离。综上所述可见，综上所述可见，全枚举法虽可找出最优方案，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的误方法，只有动

22、态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算了所有

23、中间非最优的方案组合，从而使计算工作量比穷举法大为减少。工作量比穷举法大为减少。 动态规划是解决多阶段最优决策的方法动态规划是解决多阶段最优决策的方法, 由美国数学家贝尔曼由美国数学家贝尔曼(R. Bellman) 于于 1951年首先提出年首先提出; 1957年贝尔曼发表动态规划方面的第一部年贝尔曼发表动态规划方面的第一部专著专著“动态规划动态规划”, 标志着运筹学的一标志着运筹学的一 个个新分支的创立。新分支的创立。 动态规划将复杂的多阶段决策问题分解为动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题一系列简单的、离散的单阶段决策问题, 采用顺序求解方法采用顺序求解方

24、法, 通过解一系列小问题通过解一系列小问题达到求解整个问题目的达到求解整个问题目的; 动态规划的各个决策阶段不但要考虑本阶动态规划的各个决策阶段不但要考虑本阶段的决策目标段的决策目标, 还要兼顾整个决策过程的还要兼顾整个决策过程的整体目标整体目标, 从而实现整体最优决策从而实现整体最优决策. 离散确定型离散确定型 离散随机型离散随机型 连续确定型连续确定型 连续随机型连续随机型 动态规划没有准确的数学表达式和定义动态规划没有准确的数学表达式和定义精确的算法精确的算法, 它强调具体问题具体分析它强调具体问题具体分析, 依赖分析者的经验和技巧。依赖分析者的经验和技巧。 与运筹学其他方法有很好的互补

25、关系与运筹学其他方法有很好的互补关系, 尤尤其在处理非线性、离散性问题时有其独其在处理非线性、离散性问题时有其独到的特点。到的特点。 动态规划在工程技术动态规划在工程技术, 企业管理企业管理, 军事部军事部门有广泛的应用门有广泛的应用; 可解决资源分配可解决资源分配, 生产生产调度调度, 库存管理库存管理, 路径优化路径优化, 设备更新设备更新, 投投资规划资规划, 排序问题和生产过程的最优控制排序问题和生产过程的最优控制等问题等问题拾火柴游戏拾火柴游戏: 桌子上放桌子上放30根火柴根火柴, 每人一次每人一次可拾起可拾起13根根, 谁拾起最后一根火柴谁输谁拾起最后一根火柴谁输, 如果你先选择如

26、果你先选择, 如何保证你能赢得游戏？如何保证你能赢得游戏？2925211713951使用动态规划方法求解决策问题首先要将使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式问题改造成符合动态规划求解要求的形式, ,要涉及以下概念要涉及以下概念: :(1)(1)阶段阶段(2)(2)状态状态(3)(3)决策与策略决策与策略 (4)(4)状态转移状态转移(5)(5)指标函数指标函数把一个复杂决策问题按时间或空间特征分把一个复杂决策问题按时间或空间特征分解为若干解为若干(n)个相互联系的阶段个相互联系的阶段(stage), 以便按顺序求解以便按顺序求解;阶段一般用下标阶段一般用下标

27、 k 表示表示;每阶段有若干状态每阶段有若干状态(state), 表示某一阶段表示某一阶段决策面临的条件决策面临的条件, k 阶段的状态特征可用阶段的状态特征可用状态变量状态变量 sk 或或 xk描述描述;状态有起始、中间、最终状态之分，每一状态有起始、中间、最终状态之分，每一阶段的全部状态构成该阶段的状态集合阶段的全部状态构成该阶段的状态集合Sk，并有，并有sk Sk或或xk Sk。每一阶段都要做出决策，表示从某一阶每一阶段都要做出决策，表示从某一阶段的某一状态出发进行的选择段的某一状态出发进行的选择;在在 k 阶段阶段 sk 状态的决策由决策变量状态的决策由决策变量uk(sk) 描述描述,

28、 其取值范围由允许决策集合其取值范围由允许决策集合Dk(sk) 表示表示, 即即: uk(sk) Dk(sk)。序列决策构成策略序列决策构成策略, 只含部分决策的序列只含部分决策的序列称为子策略称为子策略, 记为记为 pk(sk):pk(sk)=uk(sk), uk+1(sk+1), . , un-1(sn-1)状态转移确定从一个状态到另一个状态的状态转移确定从一个状态到另一个状态的转移过程转移过程, 由状态转移方程描述由状态转移方程描述: sk+1 = T (sk, uk);状态转移方程在大多数情况下可以由数学状态转移方程在大多数情况下可以由数学公式表达公式表达, 如如: sk+1 = sk

29、 + uk；Vk(sk)= k(sk,uk, sk+1,uk+1, ., sn-1,un-1, sn) = k(vk(sk, uk), vk+1(sk+1, uk+1), ., vn) = k (sk, uk, Vk+1(sk+1, uk+1) = k (vk(sk, uk), Vk+1(sk+1, uk+1)最优损益函数为最优损益函数为: fk(sk) = opt Vk(sk) nkiiiikusvV),( ; nkiiiikusvV),( 阶段 k阶段 k+1Vk = k(vk(sk, uk), vk+1(sk+1, uk+1), ., vn-1(sn-1, un-1)sk+1 =T(sk

30、,uk)vk(sk+1, uk+1)vk(sk, uk)sk+2uk+1skuk 用动态规划求解最短路问题用动态规划求解最短路问题25861410913887788656117951346579810阶段阶段: 可分为可分为5个阶段个阶段, k = 1, ., 5。 状态状态: 可用城市编号可用城市编号, S1=1, S2=2, 3, 4, S3=5, 6, 7, S4=8, 9, S5=10 决策决策: 决策变量也可用城市编号决策变量也可用城市编号; 状态转移方程状态转移方程: sk+1= uk; 损益递推函数损益递推函数:)()(111kkijDjDikksfcminsfkk k = 4f

31、4 (8) = 10, f4 (9) = 14 k = 3f3(5)=min6+f4(8)=16*, 8+f4(9)=22=16 f3(6)=min5+f4(8)=15*, 9+f4(9)=23=15 f3(7)=min8+f4(8)=18, 3+f4(9)=17*=17 k = 2 f2(2) = min6+ f3(5), 8+ f3(6), 11+ f3(7) = min22*, 23, 28 = 22f2(3) = min6+f3(5), 8+f3(6), 7+ f3(7) = min22*, 23, 24 = 22 f2(4) = min5+f3(5), 7+f3(6), 8+f3(7

32、) = min21*, 22, 25 = 21 k = 1 f1(1) = min5+f2(2), 9+f2(3), 7+f2(4) = min27*, 31, 28 = 27 最短路是：最短路是：1 2 5 8 10对有对有 7 个阶段个阶段, 每个阶段有每个阶段有 5 种状态的最种状态的最短路径问题短路径问题, 用穷举法计算要进行用穷举法计算要进行 56 = 15625 次加法和次加法和 3124 次比较次比较, 而动态规划而动态规划只需只需105次加法和次加法和 84 次比较次比较, 计算效率分计算效率分别提高近别提高近150和和40倍倍. 状态变量状态变量 sk 表示第表示第 k 阶段

33、可用资源的数量阶段可用资源的数量, 要满要满足足sk c; 决策变量决策变量 xk表示表示 k 阶段使用的资源量阶段使用的资源量;则有则有: : s1= c, s2= s1- x1, s3= s2 - x2 状态转移方程为状态转移方程为: sk+1 = sk - xk。 递推函数为递推函数为: )()()(110kkksxkksfxpmaxsfkk由由 f2 / x2 = 2x2 s2 - 3x22 = 0 可解得最优解为：可解得最优解为：x2*= (2/3)s2 , f2(s2) = (4/27) s23)()()()(322220222203220332202222222222= xsxm

34、axxsxmaxsxmaxsfxmaxsfsxsxsxsxk = 2:3333 33sxmaxsfsx)(由由 f1 / x1 = (4/27)(s1 - x1)3 -3x1 (s1 - x1)2 = (4/27)( s1 - x1)2(s1 - 4x1) = 0最优解为最优解为: x1*= (1/4)s1, f1(s1) = (1/64)s14由初始条件由初始条件s1 = c可得可得:x1*= c/4 , x2*= c/2 , x3*= c/4 , f1(c) = c4/64)()()(31127410221011 1111xsxmaxsfxmaxsfsxsx 例例 2 的损益函数的损益函数

35、是普通的多项式是普通的多项式, 可以用可以用解析法求的最优解解析法求的最优解, 计算比较简单计算比较简单, 如果损如果损益函数的形式比较复杂益函数的形式比较复杂, 无法用解析方法无法用解析方法求解求解, 可以将连续变量离散化后可以将连续变量离散化后, 用穷举的用穷举的方法求解。方法求解。 对任何阶段对任何阶段 k, 有有sk+1= T (sk, uk), sk+1仅取仅取决于当前状态决于当前状态sk和当前决策和当前决策uk, 与与 k 阶段阶段前的状态和决策无关前的状态和决策无关, 也即也即, k 阶段以后的阶段以后的发展不受该阶段以前状态的影响发展不受该阶段以前状态的影响, 过去的过去的历史

36、只能通过当前状态来影响今后的发历史只能通过当前状态来影响今后的发展。展。 整个过程的最优策略应具有这样的性质整个过程的最优策略应具有这样的性质: 无无论过去的状态和决策如何论过去的状态和决策如何, 对前面的决策所对前面的决策所形成的状态而言形成的状态而言, 后续的诸决策必须构成最后续的诸决策必须构成最优策略；优策略； 上一条成立的条件是损益递推函数严格单上一条成立的条件是损益递推函数严格单调。调。1. 将问题按时间或空间划分为满足递推关系将问题按时间或空间划分为满足递推关系的若干阶段的若干阶段, 对非时序问题可人为地引入对非时序问题可人为地引入“时段时段”概念概念;2. 正确选择状态变量正确选

37、择状态变量 sk, 满足满足:可知性可知性: 正确描述动态过程演变正确描述动态过程演变, 可直接或可直接或间接确定状态变量的值间接确定状态变量的值;无后效性无后效性: 后面的决策与前面的决策无关后面的决策与前面的决策无关;3. 确定决策变量确定决策变量uk(或或xk)以及允许决策集合以及允许决策集合Dk;4. 写出状态转移方程写出状态转移方程 sk+1 = T (sk , dk);5. 写出损益函数的递推关系写出损益函数的递推关系, 应满足应满足:a) 是定义在所有阶段上的数量函数；是定义在所有阶段上的数量函数；b) 具有可分离性，并满足递推关系；具有可分离性，并满足递推关系；c) 损益函数应

38、严格单调。损益函数应严格单调。 可以解决线性可以解决线性, 非线性非线性, 整数规划无法有整数规划无法有效求解的复杂问题效求解的复杂问题; 容易找到全局最优解容易找到全局最优解; 可以得到一组解可以得到一组解; 没有标准的模型可供应用没有标准的模型可供应用, 构模依赖于个人构模依赖于个人的经验和技巧的经验和技巧; 状态变量需满足无后效性状态变量需满足无后效性, 有较大的局限性有较大的局限性; 动态规划的维数灾难限制了对规模较大问题动态规划的维数灾难限制了对规模较大问题的求解效率的求解效率;1. 资源配置问题资源配置问题2. 生产与库存问题生产与库存问题3. 复合系统工作可靠性问题复合系统工作可

39、靠性问题4. 二维背包问题二维背包问题5. 设备更新问题设备更新问题6. 货郎担问题货郎担问题如何将有限的资源分配给若干种生产活如何将有限的资源分配给若干种生产活动，并使资源利用的收益最大是经济活动，并使资源利用的收益最大是经济活动中常见的问题，动态规划可以求解一动中常见的问题，动态规划可以求解一些线性规划无法解决的资源配置问题。些线性规划无法解决的资源配置问题。一般的资源分配问题可以描述为如下的规一般的资源分配问题可以描述为如下的规划问题：划问题：某工厂有某工厂有4台设备要投到三种生产线上，台设备要投到三种生产线上，投到不同生产线的预期收入的函数关系如投到不同生产线的预期收入的函数关系如下：

40、下： g1(x1) = 7x1+2 (x10); g1(x1) = 0 (x1= 0) g2(x2) = 3x2+7 (x20); g2(x2) = 0 (x2= 0) g3(x3) = 4x3+5 (x30); g3(x3) = 0 (x3= 0)设备如何分配可使工厂的收益最大？设备如何分配可使工厂的收益最大？1. 阶段阶段与生产线相联系与生产线相联系, 阶段阶段 k 只考虑分配到只考虑分配到生产线生产线 k 的设备台数的设备台数;2. 状态变量状态变量 sk 表示表示 k 生产线可分配的设备数生产线可分配的设备数;3. 决策变量决策变量 xk 表示决定在表示决定在 k 生产线上使用的生产线

41、上使用的设备数设备数;4. 状态转移方程状态转移方程: sk+1 = sk - xk;5. 损益函数损益函数: fk(sk)=max gk(xk)+fk+1(sk+1)g2( x2 ) + f3 ( s3 )S2 x201234f2(s2)x2*00*0010+910+0*10120+13 10+9* 13+019130+17 10+13* 13+916+023140+21 10+17* 13+13 16+919+0271k = 1:g1(x1) = 7x1 + 2 s2 = s1 - x1g1( x1 ) + f2 ( s2 )s1 x101234f1(s1) x1*40+279+23 16

42、+19* 23+10 30+0352因此得到：因此得到：x1 = 2 , x2 = 1 , x3 = 1例例5.4 某公司有资金某公司有资金10万元，若投资于项目万元，若投资于项目 i ( i =1 , 2 , 3 ) 的投资额为的投资额为 xi 时，其收益分别为时，其收益分别为g1(x1)=4x1 ， g2(x2)=9x2 ， g3(x3)=2x32，问应如何，问应如何分配投资数额才能使总收益最大？分配投资数额才能使总收益最大？解：解：静态数学模型为：静态数学模型为： max z = 4x1+ 9x2+ 2x32 s. t . x1+ x2+ x3 = 10 x1，x2， x3 0动态规划模

43、型：动态规划模型： 阶段变量阶段变量k ：( k = 1 , 2 , 3 ) 状态变量状态变量 sk ：第：第 k 段可以投资于第段可以投资于第 k 项到第项到第3个个 项目的资金数。项目的资金数。 决策变量决策变量xk : 给第给第 k 个项目的资金数。个项目的资金数。 状态转移方程：状态转移方程： s k+1 = sk xk 。 最优值函数最优值函数 fk(sk)：当可投资数为：当可投资数为sk 时，投资第时，投资第 k 3 项所得的最大收益数。项所得的最大收益数。 基本方程：基本方程： 0)()1 ,2,3(,)()(max)(44110sfksfxgsfkkkksxkkkk当当 k =

44、 3 时有：时有： 232303322max)(33sxsfsx 当当 k = 2 时有：时有： )(9max)(33202222sfxsfsx 232029max22sxsx 22220)(29max22xsxsx 令令2222222)(29),(xsxxsh 由由0)1)(492222 xsdxdh解得解得,4922 sx042222 dxhd所以所以4922 sx是极小点。是极小点。极大值只可能在极大值只可能在 0，s2 的端点处取得：的端点处取得：22222229)(2)(ssfssf 或或当当29,922222 sss解解得得.0,92,29*22222 xsss此此时时时时当当.,

45、92,292*22222sxsss 此此时时时时当当当当 k = 1 时有：时有： )(4max)(22101111sfxsfsx 时时当当2229)(ssf 994max)10(11110011xsxfx 111100959max1sxsx 但此时但此时矛盾矛盾与与29,29100102112 sxss舍去舍去时时当当22222)(ssf 24max)10(211110011）（xsxfx 令令2111111)(24),(xsxxsh 由由10)1)(44111111 sxxsdxdh而而042112 dxhd，所以，所以111 sx是极小点。是极小点。比较比较 0 , 10 两个端点：两个

46、端点：200)10(,011 fx时时40)10(,1011 fx时时0*1 x所以，由状态转移方程顺推，所以，由状态转移方程顺推，10010*112 xss因为：因为：292 s，所以，所以10010,0*223*2 xssx因此因此103*3 sx最优投资方案为全部投资于第最优投资方案为全部投资于第3个项目，可得最个项目，可得最大收益大收益200万元。万元。 离散的时间段内如何安排生产与库存。离散的时间段内如何安排生产与库存。 生产成本为生产成本为: C(xt) = k + cxt (xt 0) 或或 C(xt) = 0 (xt = 0), k为开工所需费用为开工所需费用, c 是是变动成

47、本变动成本, xt为为 t 期的生产数量期的生产数量; 库存成本为：库存成本为：H(yt) = hyt, h为单位库存成为单位库存成本，本，yt为为 t 期期初库存数量。期期初库存数量。 假定假定k = 250, c = 2, h = 1, y1 = 0, T = 5, 需需求数据如下表求数据如下表, 如何安排生产才能使总成本如何安排生产才能使总成本最小最小? 阶段阶段可按周期可按周期 t 划分划分, t = 1, 2, 3, 4, 5 每周期期初的库存量为该阶段的状态每周期期初的库存量为该阶段的状态, 状状态变量态变量 st 表示表示 t 周期期初库存；周期期初库存； 决策变量决策变量 xt

48、 表示表示 t 期的生产数量期的生产数量; 状态转移方程为状态转移方程为: st+1 = st + xt - dtft(st) = min Ct(xt) + Ht(st) + ft+1(st+1) 以库存表示系统状态会大大增加系统状态以库存表示系统状态会大大增加系统状态数量数量, 然而然而, 上述问题的最优决策必须使每上述问题的最优决策必须使每一阶段库存或者为零一阶段库存或者为零, 或者为后续一或几或者为后续一或几个周期需求之和。个周期需求之和。 t= 5:f5(0) = k+cx5+hs5 = 250+2 270+1 0 = 790 (x5= 270) f5(270) = k+cx5+hs5

49、 = 0+2 0+1 270 = 270 (x5= 0) t = 4: f4( 0 ) = min 250+2 140+ f5(0), 250+2 410+ f5(270)= min 1320*, 1340 = 1320 (x4= 140)f4(140) = 1 140+ f5(0) = 140 + 790 = 930 (x4= 0) f4(410) = 1 410+ f5(270) = 410 + 270 = 680 (x4= 0) t = 3:f3(0) = min 250+2 360+f5(0), 250+2 500 + f4(140), 250+2 770+ f4(410) = min

50、 2290, 2180*, 2470 = 2180 (x3= 500)f3(360)=1 360+f4(0)=360+1320=1680 (x3=0)f3(500)=1 500+f4(140)=500+930=1430 (x3= 0)f3(770)=1 770+f4(410) = 770+680 = 1450 (x3= 0)t = 2:f2(0)=min 250+2 220+f3(0),250+2 580+f3(360), 250+2 720+f3(500), 250+2 990+ f3(770) = min2870*,3090,3120,3680=2870(x2=220)f2(220)=1

51、220+f3(0) = 220+2180 = 2400 (x2= 0)f2(580)=1 580+f3(360)=580+1680=2260 (x2= 0)f3(720)=1 720+f3(500)=720+1430=2150 (x2= 0)t = 1:f1(0)=min 250+2 280+f2(0),250+2 500+f2(220),250+2 860+ f2(580), 250+2 1000+ f2(720) =min3800,3650*,4290,4400=3650 (x1= 500)最优解为：最优解为： x1= 500, x2= 0, x3= 500, x4= 0, x5= 270

52、简单判断方法：只要固定费用大于后面发生的简单判断方法：只要固定费用大于后面发生的库存费用，就值得一次生产满足一或几个周期库存费用，就值得一次生产满足一或几个周期的需求。的需求。 为保证设备可靠运行为保证设备可靠运行, 一些关键部件往往一些关键部件往往由多个器件并联运行由多个器件并联运行, 如果器件如果器件 i 的失效概的失效概率为率为 pi, 则则 xi 个器件并联工作的可靠性为个器件并联工作的可靠性为(1 - pixi), 假定每个器件的采购费用为假定每个器件的采购费用为 ci, 在在满足总采购费用不超过预算限制满足总采购费用不超过预算限制 C 的前提的前提下下, 使设备可靠性最高的规划问题

53、可以描使设备可靠性最高的规划问题可以描述为述为:max: z = )1(1 nixiips.t. niiicxc1该问题为整数非线性规划，可以用动态规该问题为整数非线性规划，可以用动态规划求解，设关键器件数划求解，设关键器件数n = 3，总费用为，总费用为120万元。器件的单价与可靠性如下表：万元。器件的单价与可靠性如下表：器件号器件号i 单价单价(万元万元) 失效概率失效概率pi阶段与器件挂钩，第阶段与器件挂钩，第 i 阶段仅考虑器件阶段仅考虑器件 i 的的采购数量采购数量;si 表示表示 i 阶段可使用的采购费用阶段可使用的采购费用;xi 表示表示 i 阶段决定购买阶段决定购买 i 器件的

54、数量；器件的数量；状态转移方程状态转移方程: si+1 = si - ci xi；递推损益函数递推损益函数:fi(si) = max ( 1 - pixi ) fi+1(si+1)。i = 1f1(120) = max1 x1 3 0.9f2(90), 0.99f2(60), 0.999f2(30) = max 0.9 0.84*, 0.99 0.4, 0.999 0 = 0.756i = 2f2(90) = max 0.8f3(75) , 0.96f3(60) , 0.992f3(45) , 0.9984f3(30) = max 0.8 0.875 , 0.96 0.875* , 0.992 0.75 , 0.998