远程运筹学5动态

《远程运筹学5动态》由会员分享，可在线阅读，更多相关《远程运筹学5动态（112页珍藏版）》请在金锄头文库上搜索。

1、主要内容主要内容:5.15.1多阶段决策过程的最优化多阶段决策过程的最优化多阶段决策过程的最优化多阶段决策过程的最优化 5.2 5.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划的基本概念和基本原理5.3 5.3 动态规划方法的基本步骤动态规划方法的基本步骤动态规划方法的基本步骤动态规划方法的基本步骤 5.4 5.4 动态规划应用举例动态规划应用举例动态规划应用举例动态规划应用举例第第 五五 章章 动动 态态 规规 划划5.15.1多阶段决策过程的最优化多阶段决策过程的最优化 动态规划是解决多阶段最优决策的方法动态规划是解决多阶段最优决策的方法

2、, 由美国数学家贝尔曼由美国数学家贝尔曼(R. Bellman) 于于 1951年首先提出年首先提出;1957年贝尔曼发表动态规划方面的第一部年贝尔曼发表动态规划方面的第一部专著专著“动态规划动态规划”, 标志着运筹学的一标志着运筹学的一 个个新分支的创立。新分支的创立。例例 5 .1 求解最短路问题求解最短路问题 动态规划将复杂的多阶段决策问题分解为动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题一系列简单的、离散的单阶段决策问题, 采用顺序求解方法采用顺序求解方法, 通过解一系列小问题通过解一系列小问题达到求解整个问题目的达到求解整个问题目的;动态规划的各个决策阶段不

3、但要考虑本阶动态规划的各个决策阶段不但要考虑本阶段的决策目标段的决策目标, 还要兼顾整个决策过程的还要兼顾整个决策过程的整体目标整体目标, 从而实现整体最优决策从而实现整体最优决策.动态规划的分类动态规划的分类:离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型动态规划的特点动态规划的特点:动态规划没有准确的数学表达式和定义动态规划没有准确的数学表达式和定义精确的算法精确的算法, 它强调具体问题具体分析它强调具体问题具体分析, 依赖分析者的经验和技巧。依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系与运筹学其他方法有很好的互补关系, 尤尤其在处理非线性、离

4、散性问题时有其独其在处理非线性、离散性问题时有其独到的特点。到的特点。 通通常常多多阶阶段段决决策策过过程程的的发发展展是是通通过过状状态态的的一一系系列列变变换换来来实实现现的的。一一般般情情况况下下，系系统统在在某某个个阶阶段段的的状状态态转转移移除除与与本本阶阶段段的的状状态态和和决决策策有有关关外外，还还可可能能与与系系统统过过去去经经历历的的状状态态和和决决策策有有关关。因因此此，问问题题的的求求解解就就比比较较困困难难复复杂杂。而而适适合合于于用用动动态态规规划划方方法法求求解解的的只只是是一一类类特特殊殊的的多多阶阶段段决决策策问问题题，即即具具有有“无无后后效效性性”的的多多阶

5、阶段段决决策策过过程程。所所谓谓无无后后效效性性，又又称称马马尔柯夫性，是指系统从某个阶段往后的发展，尔柯夫性，是指系统从某个阶段往后的发展，仅仅由由本本阶阶段段所所处处的的状状态态及及其其往往后后的的决决策策所所决决定定，与与系系统统以以前前经经历历的的状状态态和和决决策策( (历历史史) )无无关。关。具具有有无无后后效效性性的的多多阶阶段段决决策策过过程程的的特特点点是是系系统统过过去去的的历历史史，只只能能通通过过现现阶阶段段的的状状态态去去影影响响系系统统的的未未来来，当当前前的的状状态态就就是是后后过过程程发发展展的初始条件。的初始条件。动态规划的应用动态规划的应用动态规划在工程技

6、术动态规划在工程技术, 企业管理企业管理, 军事部军事部门有广泛的应用门有广泛的应用; 可解决资源分配可解决资源分配, 生产生产调度调度, 库存管理库存管理, 路径优化路径优化, 设备更新设备更新, 投资规划投资规划, 排序问题和生产过程的最优控排序问题和生产过程的最优控制等问题制等问题;拾火柴游戏拾火柴游戏: 桌子上放桌子上放30根火柴根火柴, 每人一每人一次可拾起次可拾起13根根, 谁拾起最后一根火柴谁谁拾起最后一根火柴谁输输, 如果你先选择如果你先选择, 如何保证你能赢得游如何保证你能赢得游戏？戏？2925211713951动态规划与倒推求解动态规划与倒推求解:使用动态规划方法求解决策问

7、题首先要将使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式问题改造成符合动态规划求解要求的形式, ,要涉及以下概念要涉及以下概念: :(1)(1)阶段阶段(2)(2)状态状态(3)(3)决策与策略决策与策略 (4) (4)状态转移状态转移(5)(5)指标函数指标函数5.2 5.2 动态规划的基本概念和基本思想动态规划的基本概念和基本思想一、基本概念一、基本概念 (1) 划分阶段划分阶段 把一个复杂决策问题按时间或空间特把一个复杂决策问题按时间或空间特征分解为若干征分解为若干(n)(n)个相互联系的阶段个相互联系的阶段(stage), (stage), 以便按顺序求解以便

8、按顺序求解; ; 阶段变量描述当前所处的阶段位置，一阶段变量描述当前所处的阶段位置，一般用下标般用下标 k k 表示表示; ;每阶段有若干状态每阶段有若干状态(state), 表示某一阶段决策表示某一阶段决策面临的条件或所处位置及运动特征的量面临的条件或所处位置及运动特征的量,称为称为状态。反映状态变化的量叫作状态变量。状态。反映状态变化的量叫作状态变量。 k 阶段的状态特征可用状态变量阶段的状态特征可用状态变量 sk 或或 xk描述描述;状态有起始、中间、最终状态之分，每一阶段状态有起始、中间、最终状态之分，每一阶段的全部状态构成该阶段的状态集合的全部状态构成该阶段的状态集合Sk，并有，并有

9、sk Sk或或xk Sk。每个阶段的状态可分为初始状。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，态和终止状态，或称输入状态和输出状态，阶段的初始状态记作阶段的初始状态记作sk ，终止状态记为，终止状态记为sk+1 (2) 确定状态确定状态 (3) (3) 决策、决策变量决策、决策变量 所谓决策就是确定系统过程发展的方案，所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选给定阶段状态出发对下一阶段状态作出的选择。择。 用以描述决策变化的量称之决策变量，用以描述决策变化的量称之

10、决策变量，和状态变量一样，决策变量可以用一个数，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述也可以是状态变量一组数或一向量来描述也可以是状态变量的函数，记以的函数，记以 ，表示于，表示于 k 阶段状阶段状态态 sk 时的决策变量时的决策变量 决策变量的取值往往也有一定的容许范围，决策变量的取值往往也有一定的容许范围，称之允许决策集合决策变量称之允许决策集合决策变量 uk(sk)的允许的允许决策集用决策集用 UK(SK)表示，表示， uk(sk) UK(SK) , 允允许决策集合实际是决策的约束条件。许决策集合实际是决策的约束条件。 (4)(4)策略和允许策略集合策略和允许策略集合

11、 策略策略(Policy)也叫决策序列策略有全过程也叫决策序列策略有全过程策略和策略和 k 部子策略之分，全过程策略是指具部子策略之分，全过程策略是指具有有n 个阶段的全部过程，由依次进行的个阶段的全部过程，由依次进行的 n 个个阶段决策构成的决策序列，简称策略，表示阶段决策构成的决策序列，简称策略，表示为为 。从。从 k 阶段到第阶段到第 n 阶段，阶段，依次进行的阶段决策构成的决策序列称为依次进行的阶段决策构成的决策序列称为 k 部子策略部子策略,表示为表示为 ，显然，显然当当 k=1时的时的 k 部子策略就是全过程策略。部子策略就是全过程策略。 (5) 状态转移方程状态转移方程 状态转移

12、确定从一个状态到另一个状态的转状态转移确定从一个状态到另一个状态的转移过程移过程, 由状态转移方程描述由状态转移方程描述: sk+1 = T (sk, uk); 状态转移方程在大多数情况下可以由数学公状态转移方程在大多数情况下可以由数学公式表达式表达, 如如: sk+1 = sk + uk；(6) 指标函数指标函数 用来衡量策略或子策略或决策的效果的用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费函数。对不同问题，指标函

13、数可以是诸如费用、成本、产值、利润、产量、耗量、距离、用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。时间、效用，等等。 用用gk(sk , uk)表示第表示第 k 段处于状态段处于状态 sk且且所作决策为所作决策为 uk 时的指标，则它就是第时的指标，则它就是第 k 段指标函数，简记为段指标函数，简记为gk 。 用用R RK K(s(sk k , u , uk k) )表示第表示第k k子过程的指标函数。子过程的指标函数。表示处于第表示处于第 k k 段段 s sk k 状态且所作决策为状态且所作决策为u uk k时，从时，从 s sk k 点到终点的距离。由此可见，点到终点的距离

14、。由此可见， R RK K(s(sk k , u , uk k) )不仅跟当前状态不仅跟当前状态 s sk k 有关，还跟有关，还跟（2 2）过程指标函数）过程指标函数（也称目标函数）（也称目标函数）（1）阶段指标函数）阶段指标函数（也称阶段效应）（也称阶段效应）还跟该子过程策略还跟该子过程策略 pk(sk) 有关有关,严格说来，严格说来，应表示为应表示为 Rk(sk , pk(sk) 。它是由各阶段的。它是由各阶段的阶段指标函数阶段指标函数 gk(sk , uk)累积形成的，对于累积形成的，对于 k 部子过程的指标函数可以表示为：部子过程的指标函数可以表示为： 式式中中 ，表表示示某某种种运

15、运算算，可可以以是是加加、减减、乘、除、开方等乘、除、开方等 多阶段决策问题中，常见的目标函数形式多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即之一是取各阶段效应之和的形式，即: 有些问题，如系统可靠性问题，其目标函有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，数是取各阶段效应的连乘积形式， (7) 最优解最优解 用用 fk(sk) 表示第表示第 k 子过程指标函数子过程指标函数Rk(sk , pk(sk)在状态在状态 sk 下的最优值，即下的最优值，即: 称称 fk(sk) 为第为第 k 子过程上的最优指标函数；子过程上的最优指标函数；与它相应的子策

16、略与它相应的子策略 pk(sk) 称为状态称为状态 sk 下的最下的最优子策略，记为优子策略，记为 pk*(sk) 例例 5 .2 用动态规划求解最短路问题用动态规划求解最短路问题 最短路的求解最短路的求解: 阶段阶段: 可分为可分为5个阶段个阶段, k = 1, ., 5。 状态状态: 可用城市编号可用城市编号, S1=1, S2=2, 3, 4, S3=5, 6, 7, S4=8, 9, S5=10 决策决策: 决策变量也可用城市编号决策变量也可用城市编号; 状态转移方程状态转移方程: sk+1= uk; 损益递推函数损益递推函数: k = 4f4 (8) = 10, f4 (9) = 1

17、4 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 = 22 f2(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) = min21*, 22, 25 =

18、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倍倍.动态规划的无后效性原则动态规划的无后效性原则对任何阶段对任何阶段

19、 k, 有有sk+1= T (sk, uk), sk+1仅仅取决于当前状态取决于当前状态sk和当前决策和当前决策uk, 与与 k 阶阶段前的状态和决策无关段前的状态和决策无关, 也即也即, k 阶段以阶段以后的发展不受该阶段以前状态的影响后的发展不受该阶段以前状态的影响, 过过去的历史只能通过当前状态来影响今后去的历史只能通过当前状态来影响今后的发展。的发展。整个过程的最优策略应具有这样的性质整个过程的最优策略应具有这样的性质: 无论过去的状态和决策如何无论过去的状态和决策如何, 对前面的决策对前面的决策所形成的状态而言所形成的状态而言, 后续的诸决策必须构成后续的诸决策必须构成最优策略；最优

20、策略；上一条成立的条件是损益递推函数严格单上一条成立的条件是损益递推函数严格单调。调。二、动态规划的最优性原理二、动态规划的最优性原理在在例例5.1中中，用用标标号号法法求求解解最最短短路路线线的的计计算算公公式可以概括写成：式可以概括写成： 其其中中，gk 在在这这里里表表示示从从状状态态 sk 到到由由决决策策 uk 所所决决定定的的状状态态 sk+1 之之间间的的距距离离。f5(s5)=0 是是边边界条件，表示全过程到第四阶段终点结束。界条件，表示全过程到第四阶段终点结束。 一般地，对于一般地，对于 n 个阶段的决策过程，假设个阶段的决策过程，假设只考虑指标函数是只考虑指标函数是“和和”

21、与与“积积”的形式，的形式，第第 k 阶段和第阶段和第 k+1 阶段间的递推公式可表示阶段间的递推公式可表示如下：如下： 当过程指标函数为下列当过程指标函数为下列“和和”的形式时的形式时 相应的函数基本方程为相应的函数基本方程为 : : 当过程指标函数为下列当过程指标函数为下列“积积”的形式时的形式时相应的函数基本方程为相应的函数基本方程为 :5.3 5.3 动态规划方法的基本步骤动态规划方法的基本步骤1. 将问题按时间或空间划分为满足递推关系的将问题按时间或空间划分为满足递推关系的若干阶段若干阶段, 对非时序问题可人为地引入对非时序问题可人为地引入“时时段段”概念概念;2. 正确选择状态变量

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

23、系；具有可分离性，并满足递推关系；c) 损益函数应严格单调。损益函数应严格单调。例例5.3 有有某某种种机机床床，可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产，在在高高负负荷荷下下生生产产时时，产产品品的的年年产产量量为为 g ，与与年年初初投投入入生生产产的的机机床床数数量量 u1 的的关关系系为为 g=g(u1)=8u1 ，这这时时，年年终终机机床床完完好好台台数数将将为为，au1 ( a为为机机床床完完好好率率， 0 a 1 ，设设 a=0.7 )。在在低低负负荷荷下下生生产产时时，产产品品的的年年产产量量为为 h ，和和投投入入生生产产的的机机床床数数量量的的关

24、关系系为为 h=h(u2)=5u2 ，相相应应的的机机床床完完好好率率为为 b ( 0b2 ，设设 b= 0.9 )，一一般般情况下情况下 ( a b )。 假设某厂开始有假设某厂开始有 x1=1000 台完好的机床，现台完好的机床，现要制定一个五年生产计划，问每年开始时如要制定一个五年生产计划，问每年开始时如何重新分配完好的机床在两种不同的负荷下何重新分配完好的机床在两种不同的负荷下生产的数量，以使在生产的数量，以使在5年内产品的总产量为年内产品的总产量为最高。最高。 解：解：首先构造这个问题的动态规划模型。首先构造这个问题的动态规划模型。1分分阶阶段段：设设阶阶段段变变量量 k 表表示示年

25、年度度，因因此此，阶段总数阶段总数 n = 5 。2. 状状态态变变量量：用用 sk 表表示示第第 k 年年度度初初拥拥有有的的完完好好机机床床台台数数，同同时时也也是是第第 k-1 年年度度末末时时的完好机床数量。的完好机床数量。3. 决策变量：决策变量：用用 uk 表示第表示第 k 年度中分配年度中分配于高负荷下生产的机床台数。于是于高负荷下生产的机床台数。于是 sk-uk 便为该年度中分配于低负荷下生产的机床便为该年度中分配于低负荷下生产的机床台数。台数。 4状态转移方程为：状态转移方程为：决策变量的取值：决策变量的取值：在第在第 k 段为段为 6条件最优目标函数递推方程条件最优目标函数

26、递推方程令令 fk(sk ) 表表示示由由第第 k 年年的的状状态态 sk 出出发发，采采取取最最优优分分配配方方案案到到第第5年年度度结结束束这这段段时时间间的的产产品品产量，根据最优化原理有以下递推关系产量，根据最优化原理有以下递推关系:下下面面采采用用逆逆序序递递推推计计算算法法,从从第第5年年度度开开始始递递推计算推计算K=5 时有时有显显然然，当当 u5*=s5 时时，f5(s5) 有有最最大大值值，相相应应的有的有 f5(s5) = 8s5 。K=4 K=4 时有：时有： 因此，当因此，当 u4*= s4 时，有最大值时，有最大值 f4(s4)=13.6s4K=3 =3 时有：时有

27、：可可见见，当当 u3*= s3 时时，有有最最大大值值 f3(s3) =17.55s3 。K=2 =2 时有：时有： 此此 时时 ， 当当 u2*= 0 时时 有有 最最 大大 值值 ， 即即 f2(s2)=20.8s2,其中其中 s2=0.7u1+0.9(s1-u1)K=1 =1 时有：时有：当当 u1*= 0 时时, 有最大值，即有最大值，即 f1(s1)=23.7s1 , 因为因为 s1=1000 , 故故 f1(s1)=23700 个产品。个产品。 按照上述计算顺序寻踪得到下述计算结果：按照上述计算顺序寻踪得到下述计算结果： 上面所讨论的最优决策过程是所谓始端上面所讨论的最优决策过程

28、是所谓始端状态固定，终端状态自由如果终端也附加状态固定，终端状态自由如果终端也附加上一定的约束条件，那么计算结果将会与之上一定的约束条件，那么计算结果将会与之有所差别例如，若规定在第五个年度结束有所差别例如，若规定在第五个年度结束时，完好的机床数量为时，完好的机床数量为500台台(上面只有上面只有278台台)，问应该如何安排五年的生产，使之在，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？满足这一终端要求的情况下产量最高？ 解：解：由状态转移方程由状态转移方程有有由此式得由此式得当当 k=5 时有时有当当 k=4 时有时有显显 然然 ， 只只 有有 取取 u4*=0 , 有

29、有 最最 大大 值值 f4(s4)=21.4s4-7500当当 k=3 时有时有:显显然然，只只有有取取 u3*=0 , f3(s3) 有有最最大大值值 f3(s3)=24.5s3-7500 。当当 k=2 时有时有:显显然然，只只有有取取 u2*=0 , f2(s2) 有有最最大大值值 f2(s2)=27.1s2-7500 。当当 k=1 时有时有:显显然然，只只有有取取 u1*=0 , f1(s1) 有有最最大大值值 f1(s1)=29.4s1-7500 。 例例5.4 某某公公司司拥拥有有资资金金 10 万万元元，若若投投资资于于项项目目 i (i1，2，3) 的的投投资资额额为为 xi

30、 时时，其其收收益益分分别别为为 g1(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32 ,问应如何分配投资数额才能使总收益最大问应如何分配投资数额才能使总收益最大? 这这是是一一个个与与时时间间无无明明显显关关系系的的静静态态最最优优化化问题，可列出其静态模型为：问题，可列出其静态模型为：求求 x1 , x2 , x3 的值使的值使满足满足 我们可以人为地赋予它我们可以人为地赋予它“时段时段”的概念，的概念，用动态规划方法求解用动态规划方法求解 解：解：（解法（解法1）首先用逆序构造动态规划模型。首先用逆序构造动态规划模型。1分分阶阶段段：设设阶阶段段变变量量 k 表表示

31、示依依次次对对第第 k 个个项目投资，因此，阶段总数项目投资，因此，阶段总数 n = 3。( k = 1 , 2 , 3 )2. 状状态态变变量量：用用 sk 表表示示已已经经对对第第 1 至至 第第 k-1 个个项项目目投投资资后后的的剩剩余余资资金金；即即第第 k 段段初初拥拥有有的的可可以以分分配配给给第第 k 到到第第3个个项项目目的的资金额资金额 （单位：万元）（单位：万元） 。3. 决策变量：决策变量：用用 xk 表示对第表示对第 k 个项目投个项目投资资 的资金数量（单位：万元）。的资金数量（单位：万元）。决策变量的取值：决策变量的取值： 0 xk sk 4状态转移方程为：状态转

32、移方程为：6. 基本方程为：基本方程为： 最优指标函数最优指标函数 fk(sk) 表示第表示第 k 阶段，初阶段，初始状态为始状态为 sk 时，从第时，从第 k 到第到第 3 个项目所获个项目所获最大收益最大收益 当当 k=3 时：时：当当 k=2 时：时：极大值只可能在极大值只可能在 0 ，s2 端点取得，端点取得，当当 k=1 时：时：矛盾，所以舍去矛盾，所以舍去 sk 0); 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)设备如何分配可

33、使工厂的收益最大？设备如何分配可使工厂的收益最大？分析：分析：1. 阶段阶段与生产线相联系与生产线相联系, 阶段阶段 k 只考虑分配到只考虑分配到生产线生产线 k 的设备台数的设备台数;2. 状态变量状态变量 sk 表示表示 k 生产线可分配的设备数生产线可分配的设备数;3. 决策变量决策变量 xk 表示决定在表示决定在 k 生产线上使用的生产线上使用的设备数设备数;4. 状态转移方程状态转移方程: sk+1 = sk - xk;5. 损益函数损益函数: fk(sk)=max gk(xk)+fk+1(sk+1)s3 f3(s3) x3*0 f3(0) = maxx3=0 0 = 0 01 f3

34、(1) = maxx3 1 4x3+5 = 9 12 f3(2) = maxx3 2 4x3+5 = 13 23 f3(3) = maxx3 3 4x3+5 = 17 34 f3(4) = maxx3 4 4x3+5 = 21 4求解：求解：k = 3: g3(x3) = 4x3 + 5 k k = 2: = 2: g g2 2( (x x2 2) = 3) = 3x x2 2 + 7 + 7 s s3 3 = = s s2 2 - - x x2 2k = 1:g1(x1) = 7x1 + 2 s2 = s1 - x1因此得到：因此得到：x1 = 2 , x2 = 1 , x3 = 1离散的时

35、间段内如何安排生产与库存。离散的时间段内如何安排生产与库存。生产成本为生产成本为: C(xt) = k + cxt (xt 0) 或或 C(xt) = 0 (xt = 0), k为开工所需费用为开工所需费用, c 是是变动成本变动成本, xt为为 t 期的生产数量期的生产数量;库存成本为：库存成本为：H(yt) = hyt, h为单位库存为单位库存成本，成本，yt为为 t 期期初库存数量。期期初库存数量。2. 生产与库存问题生产与库存问题例例: 假定假定k = 250, c = 2, h = 1, y1 = 0, T = 5, 需需求数据如下表求数据如下表, 如何安排生产才能使总成本如何安排生

36、产才能使总成本最小最小? t 1 2 3 4 5需求需求(dt)220280360140270分析分析:阶段阶段可按周期可按周期 t 划分划分, t = 1, 2, 3, 4, 5每周期期初的库存量为该阶段的状态每周期期初的库存量为该阶段的状态, 状状态变量态变量 st 表示表示 t 周期期初库存；周期期初库存；决策变量决策变量 xt 表示表示 t 期的生产数量期的生产数量;状态转移方程为状态转移方程为: st+1 = st + xt - dt递推函数递推函数:ft(st) = min Ct(xt) + Ht(st) + ft+1(st+1)以库存表示系统状态会大大增加系统状态以库存表示系统状

37、态会大大增加系统状态数量数量, 然而然而, 上述问题的最优决策必须使上述问题的最优决策必须使每一阶段库存或者为零每一阶段库存或者为零, 或者为后续一或或者为后续一或几个周期需求之和。几个周期需求之和。 t= 5:f5(0) = k+cx5+hs5 = 250+2 270+1 0 = 790 (x5= 270) f5(270) = k+cx5+hs5 = 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(14

38、0) = 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 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)=

39、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 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 =

40、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简单判断方法：只要固定费用大于后面发生的简单判断方法：只要固定费用大于后面发生的库存费用，就值得一次生产满足一或几个周期库存费用，就值得一次生产满足一或几个周期的需求。的需求。3. 复合系统的工作可靠性问题复合系统的工作可靠性问题例例: 为保证设备可

41、靠运行为保证设备可靠运行, 一些关键部件往一些关键部件往往由多个器件并联运行往由多个器件并联运行, 如果器件如果器件 i 的失的失效概率为效概率为 pi, 则则 xi 个器件并联工作的可靠个器件并联工作的可靠性为性为(1 - pixi), 假定每个器件的采购费用假定每个器件的采购费用为为 ci, 在满足总采购费用不超过预算限制在满足总采购费用不超过预算限制 C 的前提下的前提下, 使设备可靠性最高的规划问使设备可靠性最高的规划问题可以描述为题可以描述为:该问题为整数非线性规划，可以用动态规该问题为整数非线性规划，可以用动态规划求解，设关键器件数划求解，设关键器件数n = 3，总费用为，总费用为

42、120万元。器件的单价与可靠性如下表：万元。器件的单价与可靠性如下表： 1300.1 2150.2 3200.5器件号器件号i 单价单价(万元万元) 失效概率失效概率pi分析：分析：阶段与器件挂钩，第阶段与器件挂钩，第 i 阶段仅考虑器件阶段仅考虑器件 i 的的采购数量采购数量;si 表示表示 i 阶段可使用的采购费用阶段可使用的采购费用;xi 表示表示 i 阶段决定购买阶段决定购买 i 器件的数量；器件的数量；状态转移方程状态转移方程: si+1 = si - ci xi；递推损益函数递推损益函数:fi(si) = max ( 1 - pixi ) fi+1(si+1)。i = 1f1(12

43、0) = 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.9984 0.5 = 0.84 f2(60) = max 0.8f3(45), 0.96f3(30) = max 0.8 0.75*, 0.96 0.5 = 0.6f2(30) =

44、max 0.8f3(15), 0 f3(30) = 0 f3(75) = 0.875, f3(60) = 0.875, f3(45) = 0.75, f3(30) = 0.5, 因此因此, 最优解为最优解为: x1 = 1, x2 = 2, x3 = 34 二维背包问题二维背包问题当背包问题中有两个限制条件时当背包问题中有两个限制条件时(如重量和如重量和体积限制体积限制), 所形成的问题为所形成的问题为 二维背包问题二维背包问题, 问题的一般形式为问题的一般形式为:max z = i ci xi s.t. i ai xi b xi 0 且为整数且为整数例例: 卡车的最大运货重量为卡车的最大运货

45、重量为 12 吨吨, 容积为容积为 10 立方米立方米, 现有现有A , B 两种货物两种货物, 重量分别重量分别为为 3 吨和吨和 4 吨吨, 体积分别为体积分别为 1 和和 5 立方米立方米, 运费分别为运费分别为 2 和和 3 元元, 如何装载使所得运如何装载使所得运费最大。费最大。 由资源条件可知最多可装载由资源条件可知最多可装载 4 件件 A 或或 2 件件 B。分析分析:阶段可按货物种类划分阶段可按货物种类划分, k = 1, 2每阶段剩余的载货能力每阶段剩余的载货能力(重量与容积重量与容积)为该为该阶段的状态阶段的状态, 状态变量状态变量 sk = (s1k, s2k);决策变量

46、决策变量 xk 表示表示 k 阶段资源的占用量阶段资源的占用量;状态转移方程状态转移方程: sk+1= sk-akxk , ak=(a1k, a2k)损益函数为损益函数为: fk(sk)=maxckxk+fk+1(sk+1)k = 2f2(12, 10) = maxx2=0,1,2f1(12,10), 3+ f1(8, 5), 6+f2(4, 0) = max 8, 3+4, 6+0 = 8k = 1f1(12,10) = maxx1 4 2x1 = 8f1( 8, 5) = maxx1 2 2x1 = 4f1( 4, 0) = 0动态规划的维数增加时动态规划的维数增加时, 求解的复杂程度求解

47、的复杂程度也会增加。如果状态变量的维数为也会增加。如果状态变量的维数为 m, 离离散的决策变量有散的决策变量有 n 个取值个取值, 则在每个阶段则在每个阶段需要存储需要存储 nm 个数据个数据, 这就是所谓的维数灾这就是所谓的维数灾难。难。5 设备更新问题设备更新问题设备在使用全过程中会遭受磨损设备在使用全过程中会遭受磨损, 使用一使用一段时间后就要维修段时间后就要维修, 而且使用的时间越长而且使用的时间越长, 维修费用越高维修费用越高, 设备使用多少时间在经济设备使用多少时间在经济上最合算上最合算, 就是设备更新问题。就是设备更新问题。例例: 某设备的年效益和年均维修费用如下表某设备的年效益

48、和年均维修费用如下表, 如何在未来的如何在未来的5年内进行更新决策。年内进行更新决策。使用年限使用年限 0 1 2 3 4效益效益 r 5 4.5 4 3.75 3 维修费维修费u 0.5 1 1.5 2 2.5更新费更新费c 0.5 1.5 2.2 2.5 3分析：分析：分析：分析：阶段阶段阶段阶段 k = k = 1, 2, 3, 4, 5;1, 2, 3, 4, 5;s sk k 表示表示表示表示 k k 年初设备已使用的年限年初设备已使用的年限年初设备已使用的年限年初设备已使用的年限; ;x xk k 为为为为 k k 年初决定设备是继续使用还是更新的决年初决定设备是继续使用还是更新的

49、决年初决定设备是继续使用还是更新的决年初决定设备是继续使用还是更新的决策变量策变量策变量策变量: : x xk k = = 1 1表示继续使用表示继续使用表示继续使用表示继续使用, , x xk k = = 0 0表示更新表示更新表示更新表示更新; ;状态转移方程状态转移方程状态转移方程状态转移方程: : s sk k+1+1 = = s sk kx xk k + 1;+ 1;损益函数损益函数:vk(sk) = r(skxk) - u(skxk) - c(sk)(1-xk ) r(0) - u(0) - c(sk) (xk= 0) vk(sk) = r(sk) - u(sk ) (xk= 1)

50、递推函数递推函数:fk(sk) = maxvk(sk) + fi+1(si+1)k = 5 状态变量状态变量 s5 可取可取 1, 2, 3, 4f5(1) = maxx1=0,1r(0) - u(0) - c(1), r(1) - u(1)= max 5-0.5-1.5, 4.5-1= 3.5 (x5*=1)f5(2)=max5-0.5-2.2, 4-1.5= 2.5 (x5*=1)f5(3)=max, 3.75-2= 2 (x5*=0)f5(4)=max5-0.5-3, 3-2.5 = 1.5 (x5*=0) k k = = 4 4状态变量状态变量状态变量状态变量 s s4 4 可取可取可

51、取可取 1, 2, 3 1, 2, 3 f f4 4(1) = (1) = maxmax r r(0)-(0)-u u(0)-(0)-c c(1)+(1)+f f5 5(1), (1), r r(1)-(1)-u u(1)+ (1)+ f f5 5(2)(2) = = max max 5-0.5-1.5+3.55-0.5-1.5+3.5, 4.5-1+2.5, 4.5-1+2.5 = 6.5 ( = 6.5 (x x4 4* = 0) * = 0) f f4 4(2) = (2) = max max 5-0.5-2.2+3.55-0.5-2.2+3.5, 4-1.5+2, 4-1.5+2 =

52、5.8 ( = 5.8 (x x4 4* = 0) * = 0) f f4 4(3) = (3) = max max 5-0.5-2.5+3.55-0.5-2.5+3.5, 3.75-2+1.5 , 3.75-2+1.5 = 5.5 ( = 5.5 (x x4 4* = 0) * = 0) k = 3状态变量状态变量 s3 可取可取 1, 2, f3(1) = maxr(0) - u(0) - c(1) + f4(1), r(1) - u(1) + f4(2) = max 5-0.5-1.5+6.5, 4.5-1+5.8 = 9.5 (x3* = 0) f3(2) = max 5-0.5-2.

53、2+6.5, 4-1.5+5.5 = 8.8 (x3* = 0) k = k = 2 2状态变量状态变量状态变量状态变量 s s2 2 可取可取可取可取 1, 1, f f2 2(1) = (1) = maxmax r r(0) - (0) - u u(0) - (0) - c c(1) + (1) + f f3 3(1), (1), r r(1) - (1) - u u(1) + (1) + f f3 3(2)(2) = = max max 5-0.5-1.5+9.55-0.5-1.5+9.5, 4.5-1+8.8, 4.5-1+8.8 = 12.5 ( = 12.5 (x x2 2* =

54、0) * = 0) k = k = 1 1时状态变量时状态变量时状态变量时状态变量 s s1 1 只能取只能取只能取只能取 0 0 f f1 1(0) = (0) = maxmax r r(0) - (0) - u u(0) - (0) - c c(0) + (0) + f f2 2(1), (1), r r(0) - (0) - u u(0) + (0) + f f2 2(1)(1) = = maxmax5-0.5-0.5+12.5, 5-0.5-0.5+12.5, 5-0.5+12.55-0.5+12.5 = 17 ( = 17 (x x1 1* = 1) * = 1) 最优策略为最优策略

55、为:k =12345 不更新不更新 更新更新 更新更新 更新更新 不更新不更新一货郎从某城市出发要经过一货郎从某城市出发要经过 n 个城市个城市, 每每个城市都要经过且只能经过一次个城市都要经过且只能经过一次, 最后还最后还要回到原先出发的城市要回到原先出发的城市, 问应如何选择旅问应如何选择旅行路线可使总行程最短。行路线可使总行程最短。 6 货郎担问题货郎担问题例例: 已知已知4个城市间的距离如下表所示，求个城市间的距离如下表所示，求经过所有城市的最短的旅行路线。经过所有城市的最短的旅行路线。 城市城市 1 2 3 41 0 6 7 92 8 0 9 73 5 8 0 84 6 5 5 0分

56、析分析:与最短路径问题不同与最短路径问题不同, 由于后面所走的路由于后面所走的路径与前面所经过的城市相关径与前面所经过的城市相关, 状态变量不容状态变量不容易满足无后效性原则易满足无后效性原则;阶段数与要旅行的城市数相关阶段数与要旅行的城市数相关;可以将货郎担问题转化为一个最短路问题可以将货郎担问题转化为一个最短路问题, 但存在维数灾难。但存在维数灾难。1234342423143423267997885585759865685814101313141617211923如果要旅行的城市个数为如果要旅行的城市个数为 n , 则最短路等价问题中则最短路等价问题中某一阶段出现的最多节点数是某一阶段出现的最多节点数是 (n - 1)!上例中的上例中的 n = 4, 则每阶段最多会有则每阶段最多会有: (4-1)! = 3*2*1 = 6如果有如果有10个城市个城市, 会有会有362880个节点。个节点。教科书上介绍的方法与上述方法等价。教科书上介绍的方法与上述方法等价。