15《运筹学》(第四版)连续动态规划.pdf

莫莫 莉莉 水电与数字化工程学院 第三章第三章 动态规划动态规划(Dynamic Programming) 主讲人：莫主讲人：莫 莉莉 moli 2015 年年 6 月月 莫莫 莉莉 水电与数字化工程学院 温温故故 引例引例 动态规划基本概念动态规划基本概念 离散动态规划离散动态规划 知知新新 引例引例 动态规划优劣动态规划优劣 经营管理中的应用经营管理中的应用 多种应用多种应用 前节回顾前节回顾 莫莫 莉莉 水电与数字化工程学院 前节回顾前节回顾 动态规划所解决的问题：动态规划所解决的问题：多阶段问题多阶段问题 动态规划的动态规划的核心核心: 动态规划的动态规划的优优缺点缺点: 在于将问题公式化，也可以说在于将问题公式化，也可以说 ，动态规划是将多阶段决策问，动态规划是将多阶段决策问 题进行公式化的一种技术。题进行公式化的一种技术。 适用范围广，模型算法一体化，方便编程。适用范围广，模型算法一体化，方便编程。 由于没有统一的标准模型，使得动态规划的应用由于没有统一的标准模型，使得动态规划的应用 难度增加难度增加 。 莫莫 莉莉 水电与数字化工程学院 前节回顾前节回顾 动态规划根据多阶段决策过程的时间参量类动态规划根据多阶段决策过程的时间参量类 型可以分为型可以分为离散型决策过程离散型决策过程和和连续型决策过程；连续型决策过程； 根据决策过程的演变性态又可以分为根据决策过程的演变性态又可以分为确定型决策确定型决策 过程过程和和随机型过程。随机型过程。组合起来有下列类型：组合起来有下列类型： 离散确定型、离散随机型、连续确定型、连离散确定型、离散随机型、连续确定型、连 续随机型续随机型。本章主要介绍。本章主要介绍离散确定型决策过程离散确定型决策过程。 莫莫 莉莉 水电与数字化工程学院 前节回顾前节回顾 例. (最短路径问题) 下图表示从起点A到终点E之间各点的距离。 求A到E的最短路径。 BA CB D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 48 3 8 6 7 5 6 1 10 6 3 7 51 B4 莫莫 莉莉 水电与数字化工程学院 前节回顾前节回顾 用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位 置则总共有3k条路径； 计算各路径长度总共要进行3k-1 次比较。随着 k 的值增加时，需要进行的加法和比较的 次数将迅速增加； 例如当 k=20时，加法次数为 4.25508339662271015 次，比较 1.37260754729771014次。若用1亿次/秒的计 算机计算需要约508天。 莫莫 莉莉 水电与数字化工程学院 前节回顾前节回顾 状态(每阶段初始的出发点) 最短路问题中，各个节点就是状态 生产库存问题中，库存量是状态 物资分配问题中，剩余的物资量是状态 控制变量(决策变量) 最短路问题中，走哪条路 生产库存问题中，各阶段的产品生产量 物资分配问题中，分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推，所以阶段的编号也是逆向的 当然也可以正向递推 基本概念基本概念 莫莫 莉莉 水电与数字化工程学院 作业作业 序号序号课后作业课后作业页码页码、题、题号号备注备注 第第1次作业次作业 P44-1.1(1),1.3,1.4 P45-1.6(1)(2) 图图解法，基解，解法，基解，单纯形单纯形法法 大大M法法 第第2次作业次作业 P74-2.3(1)(2),2.7 P75-2.8 对偶对偶问题，问题，对偶对偶问题性问题性质质求最优解求最优解 对偶单纯形对偶单纯形法法 第第3次作业次作业 P187-7.3,7.4,7.5 P187-7.7,7.13 判判定定凸凸规划，规划，斐波那契斐波那契法，法，0.618法法 最最速速下下降降法，法，共轭梯共轭梯度法度法 第第4次作业次作业 P188-7.13(3),7.17 P189-7.21,7.23 P211-8.2,8.3 变变尺尺度法，度法，Kuhn-Tucker条件条件 SUMT外点外点法，法，SUMT内点内点法法 最最短路短路线线 参照公共邮箱的电子版教材中的页码参照公共邮箱的电子版教材中的页码，完成第完成第3次次、第第4次作次作 业业，于于2015年年6月月17日完成日完成。 莫莫 莉莉 水电与数字化工程学院 温温故故 引例引例 动态规划基本概念动态规划基本概念 离散动态规划离散动态规划 知知新新 引例引例 动态规划优劣动态规划优劣 经营管理中的应用经营管理中的应用 多种应用多种应用 前节回顾前节回顾 莫莫 莉莉 水电与数字化工程学院 第三章第三章 动态规划动态规划 基本概念介绍基本概念介绍1 1 离散动态规划离散动态规划2 2 连续动态规划连续动态规划3 3 在水库调度中的应用在水库调度中的应用4 4 莫莫 莉莉 水电与数字化工程学院 2.1 2.1 引例引例 例例某警卫部门共有某警卫部门共有12支巡逻队，负责支巡逻队，负责4个要害部位个要害部位 的警卫巡逻。对每个部位可分别派出的警卫巡逻。对每个部位可分别派出24支巡逻队，并且派出支巡逻队，并且派出 巡逻队数的不同，各部位预期在一段时期内可能造成的损失有巡逻队数的不同，各部位预期在一段时期内可能造成的损失有 差别，具体数字见下表。问该警卫部门应往各部位分别派多少差别，具体数字见下表。问该警卫部门应往各部位分别派多少 巡逻队，使总的预期损失为最小。巡逻队，使总的预期损失为最小。 DCBA, 部位部位 预期损失预期损失 巡逻队数巡逻队数 A B C D 2 3 4 18 38 24 34 14 35 22 31 10 31 21 25 莫莫 莉莉 水电与数字化工程学院 2.1 2.1 引例引例 部位部位 预期损失预期损失 巡逻队数巡逻队数 A B C D 2 3 4 18 38 24 34 14 35 22 31 10 31 21 25 解：解： 阶段数阶段数：把：把12支巡逻队往各部支巡逻队往各部 位派遣看成依次分四个阶段位派遣看成依次分四个阶段。 状态变量状态变量：xk表示每个阶段初表示每个阶段初 拥有的可派遣的巡逻队数拥有的可派遣的巡逻队数。 决策变量决策变量：uk表示对各部位派出的巡逻队数表示对各部位派出的巡逻队数，各阶段允许的决策各阶段允许的决策 集合为：集合为： 状态转移方程状态转移方程：xk 1 xkuk ) 4 , 3 , 2 , 1(,42)(kuuxU kkkk 若用若用表示表示 阶段派出的巡逻队数为阶段派出的巡逻队数为时时，该阶段的部位的预该阶段的部位的预 期损失值期损失值， ),( kkk uxvk k u 莫莫 莉莉 水电与数字化工程学院 2.1 2.1 引例引例 设用设用表示表示 阶段状态为阶段状态为 ，以此出发采用最优子策略到过以此出发采用最优子策略到过 程结束时的预期损失值程结束时的预期损失值，则有则有: )( kk xf k k x )(),(min)( 11 )( kkkkk xUu kk xfuxvxf kkk 采用后向算法采用后向算法，先考虑给先考虑给部位派巡逻队部位派巡逻队，则上式可写为：则上式可写为：D4k ),(min)( 444 )( 44 444 uxvxf xUu )(),(min)( 55444 )( 44 444 xfuxvxf xUu 0)( 55 xf 莫莫 莉莉 水电与数字化工程学院 2.1 2.1 引例引例 u4 x4 v4(x4, u4) f 4 (x4)u4* 234 2 3 4 5 6 34 34 34 34 34 31 31 31 31 25 25 25 34 31 25 25 25 2 3 4 4 4 因因，又，又 的可能值为的可能值为 ，故由已知数据，可得，故由已知数据，可得 下表的结果。下表的结果。 4 , 3 , 2)( 44 xU 4 x 62 4 x 部位部位 预期损失预期损失 巡逻队数巡逻队数 A B C D 2 3 4 18 38 24 34 14 35 22 31 10 31 21 25 ),(min)( 444 )( 44 444 uxvxf xUu 再联合考虑对再联合考虑对、 两个部位派巡逻队两个部位派巡逻队，即即。这时有这时有CD3k )(),(min)( 44333 )( 33 333 xfuxvxf xUu 因有因有，又又，故可得到下表的计算结果故可得到下表的计算结果。 4 , 3 , 2)( 33 xU84 3 x u3 x3 v3(x3, u3) + f 4 (x3-u3) f 3 (x3)u3* 234 4 5 6 7 8 24+34 24+31 24+25 24+25 24+25 22+34 22+31 22+25 22+25 21+34 21+31 21+25 58 55 49 47 46 2 2 2 3 4 莫莫 莉莉 水电与数字化工程学院 2.1 2.1 引例引例 下面考虑对下面考虑对、 、 三个部位派巡逻队三个部位派巡逻队，即即，这时有这时有BC D 2k )(),(min)( 33222 )( 22 222 xfuxvxf xUu 同样有同样有，又又，故可得到下表的计算结果故可得到下表的计算结果。4 , 3 , 2)( 22 xU108 2 x u2 x2 v2(x2, u2)+f 3 (x2-u2) f 2 (x2) u2* 234 8 9 10 3849 3847 3846 3555 3549 3547 3158 3155 3149 87 84 80 2 3 4 234 4 5 6 7 8 24+34 24+31 24+25 24+25 24+25 22+34 22+31 22+25 22+25 21+34 21+31 21+25 58 55 49 47 46 2 2 2 3 4 部位部位 预期损失预期损失 巡逻队数巡逻队数 A B C D 2 3 4 18 38 24 34 14 35 22 31 10 31 21 25 3 u 3 x )(),( 334333 uxfuxv )( 33 xf 3 u 莫莫 莉莉 水电与数字化工程学院 2.1 2.1 引例引例 )(),(min)( 22111 )( 11 111 xfuxvxf xUu 最后考虑对最后考虑对四个部位四个部位 派巡逻队派巡逻队，即即，有有 DCBA, 1k 因因，又又， 计算得右表计算得右表。 12 1 x4 , 3 , 2)( 11 xU u1 x1 v1(x1, u1)+f 2 (x1-u1) f 1 (x1)u1* 234 1218+8014+8410+87974 部位部位 预期损失预期损失 巡逻队数巡逻队数 A B C D 2 3 4 18 38 24 34 14 35 22 31 10 31 21 25 u2 x2 v2(x2, u2)+f 3 (x2-u2) f 2 (x2) u2* 234 8 9 10 3849 3847 3846 3555 3549 3547 3158 3155 3149 87 84 80 2 3 4 莫莫 莉莉 水电与数字化工程学院 2.1 2.1 引例引例 因此因此，故，故，4 1 u8412 2 x 所以所以，因而，因而，2 2 u628 3 x 再由前面表知再由前面表知，推算得，推算得2 3 u 426 4 x 234 2 3 4 5 6 34 34 34 34 34 31 31 31 31 25 25 25 34 31 25 25 25 2 3 4 4 4 234 4 5 6 7 8 24+34 24+31 24+25 24+25 24+25 22+34 22+31 22+25 22+25 21+34 21+31 21+25 58 55 49 47 46 2 2 2 3 4 234 8 9 10 3849 3847 3846 3555 3549 3547 3158 3155 3149 87 84 80 2 3 4 234 1218+8014+8410+87974 )( 44 xf 4 u 4 x ),( 444 uxv 4 u 3 u 3 x )(),( 334333 uxfuxv )( 33 xf 3 u 2 u 2 x )(),( 223222 uxfuxv )( 22 xf 2 u 1 x 1 u )(),( 112111 uxfuxv )( 11 xf 1 u 因此该警卫部门的派巡逻队的因此该警卫部门的派巡逻队的 最优策略为：最优策略为： 部位支，部位支， 部位支，部位支， 部位支，部位支， 部位部位 支，总预期损失为支，总预期损失为97单位。单位。 AB CD 莫莫 莉莉 水电与数字化工程学院 2.2 2.2 动态规划的特点动态规划的特点 动态规划与静态规划的关系动态规划与静态规划的关系 动态规划与静态规划动态规划与静态规划（线性与非线性规划等线性与非线性规划等）研究的对象本质上研究的对象本质上 都是在若干约束条件下的函数极值问题都是在若干约束条件下的函数极值问题，两种规划在很多情况下两种规划在很多情况下 原则上可以相互转换原则上可以相互转换。 1动态规划可以看作求决策动态规划可以看作求决策使指标函数使指标函数 达到最优达到最优(最大或最小最大或最小)的极值问题的极值问题，状态转移方程状态转移方程、端点条件端点条件 以及允许状态集以及允许状态集、允许决策集等是约束条件允许决策集等是约束条件，原则上可以用非原则上可以用非 线性规划方法求解线性规划方法求解。 n uuu, 21 ),( 2111nn xxuxV 2 一些静态规划只要适当引入阶段变量、状态、决策等就可以一些静态规划只要适当引入阶段变量、状态、决策等就可以 用动态规划方法求解。用动态规划方法求解。 莫莫 莉莉 水电与数字化工程学院 2.2 2.2 动态规划的特点动态规划的特点 动态规划的优越性动态规划的优越性 与静态规划相比与静态规划相比，动态规划的优越性在于：动态规划的优越性在于： （1）能够得到全局最优解。由于约束条件确定的约束集合往往）能够得到全局最优解。由于约束条件确定的约束集合往往 很复杂，即使指标函数较简单，用非线性规划方法也很难求出很复杂，即使指标函数较简单，用非线性规划方法也很难求出 全局最优解，而动态规划方法把全过程化为一系列结构相似的全局最优解，而动态规划方法把全过程化为一系列结构相似的 子问题，每个子问题的变量个数大大减少，约束集合也简单得子问题，每个子问题的变量个数大大减少，约束集合也简单得 多，易于得到全局最优解。特别是对于约束集合、状态转移和多，易于得到全局最优解。特别是对于约束集合、状态转移和 指标函数不能用分析形式给出的优化问题，可以对每个子过程指标函数不能用分析形式给出的优化问题，可以对每个子过程 用枚举法求解，而约束条件越多，决策的搜索范围越小，求解用枚举法求解，而约束条件越多，决策的搜索范围越小，求解 也越容易。对于这类问题，动态规划通常是求全局最优解的唯也越容易。对于这类问题，动态规划通常是求全局最优解的唯 一方法。一方法。 莫莫 莉莉 水电与数字化工程学院 2.2 2.2 动态规划的特点动态规划的特点 可以得到一族最优解。与非线性规划只能得到全过程的一个可以得到一族最优解。与非线性规划只能得到全过程的一个 最优解不同，动态规划得到的是全过程最优解不同，动态规划得到的是全过程及所有后部子过程的及所有后部子过程的 各个状态的一族最优解各个状态的一族最优解。有些实际的问题需要这样的解族，。有些实际的问题需要这样的解族， 即使不需要，它们在分析最优策略和最优值对于状态的稳定即使不需要，它们在分析最优策略和最优值对于状态的稳定 性时也是很有用的。当最优策略由于某种原因不能实现时，性时也是很有用的。当最优策略由于某种原因不能实现时， 这样的解族可以用来寻找次优策略。这样的解族可以用来寻找次优策略。 能够利用经验提高求解效率能够利用经验提高求解效率。如果实际问题本身就是动态的如果实际问题本身就是动态的， 由于动态规划方法反映了过程逐段演变的前后联系和动态特由于动态规划方法反映了过程逐段演变的前后联系和动态特 征征，在计算中可以利用实际知识和经验提高求解效率在计算中可以利用实际知识和经验提高求解效率。如在如在 策略迭代法中策略迭代法中，实际经验能够帮助寻找较好的初始策略实际经验能够帮助寻找较好的初始策略，提提 高收敛速度高收敛速度。 莫莫 莉莉 水电与数字化工程学院 2.2 2.2 动态规划的特点动态规划的特点 （2）用数值方法求解时存在维数灾用数值方法求解时存在维数灾。若一维状态变量有若一维状态变量有 个取个取 值值，那么对于那么对于 维问题维问题，状态状态就有就有个值个值，对于每个对于每个 状态值都要计算状态值都要计算、存储函数存储函数，对于对于 稍大稍大（即使即使 ）的实际问题的计算往往是不现实的的实际问题的计算往往是不现实的。目前还没有克服维目前还没有克服维 数灾的有效的一般方法数灾的有效的一般方法。 m n k x n m )( kk xfn 3n 动态规划的缺点：动态规划的缺点： （1）没有统一的标准模型，也没有构造模型的通用方法，甚至还）没有统一的标准模型，也没有构造模型的通用方法，甚至还 没有判断一个问题能否构造动态规划的准则。这样就只能对没有判断一个问题能否构造动态规划的准则。这样就只能对 每类问题进行具体分析，构造具体的模型。对于较复杂的问每类问题进行具体分析，构造具体的模型。对于较复杂的问 题在选择状态、决策、确定状态转移规律等方面需要丰富的题在选择状态、决策、确定状态转移规律等方面需要丰富的 想象力和灵活的技巧性，这就带来了应用上的局限性。想象力和灵活的技巧性，这就带来了应用上的局限性。 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 1、资源分配问题 设有某种原料，总数量为a，用于生产n种产品，若分 配数量ui用于生产第i种产品，其收益g(ui)。问应如何分配 原料，才能使生产n种产品的总收入最大？ 设状态变量xk表示分配用于生产第k种产品至第n种产 品的原料数量。 决策变量uk表示分配给生产第k种产品的原料数。 状态转移方程为xk+1=xk-uk 允许决策集合为Uk(xk)=uk0ukxk 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 令最优值函数表示以数量为xk的原料分配给第k种产 品至第n种产品所得到的最大总收入。 )( kk xf 则动态规划的递推关系式为： 0)( , 2 , 1),()(max)( 11 1 nn kkkkkkk xf nkuxfugxf 允许决策集合为Uk(xk)=uk0ukxk 状态转移方程为xk+1=xk-uk 决策变量uk表示分配给生产第k种产品的原料数。 设状态变量xk表示分配用于生产第k种产品至第n种产 品的原料数量。 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 例 某公司拟将5台设备分配给所需的甲、乙、丙三个工厂， 各工厂获得设备后获利润见下表。问：这5台设备如何分配给 各工厂，才能使公司得到的利润最大。 工厂工厂 获利获利 设备台数设备台数 甲甲乙乙丙丙 0000 1354 27106 391111 4121112 5131112 单位：万元 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 解：将问题按工厂分为三个阶段，甲、乙、丙三个 工厂分别编号为1、2、3。 设xk表示为分配给第k个工厂至第3个工厂的设备台数 uk表示为分配给第k个工厂的设备台数，则 xk+1=xk-uk 为状态转移方程。 Pk(uk)表示为uk台设备分配到第k个工厂所获利润值。 fk(xk)表示为xk台设备分配给第k个工厂至第3个工厂 时所得到的最大利润值。则有递推关系式为 0)( 0 1 , 2 , 3),()(max)( 44 1 xf xu kuxfuPxf kk kkkkkkk 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 0)( 0 1 , 2 , 3),()(max)( 44 1 xf xu kuxfuPxf kk kkkkkkk 第三阶段：设将x3台设备（x3=0,1,2,3,4,5）全部分配 给工厂丙时，最大获利值为 )(max)( 3333 33 uPxf xu u3 x3 P3(u3) f3(x3) u3* 012345 0 1 2 3 4 5 000 144 266 31111 41212 51212 工厂工厂 获利获利 设备台数设备台数 甲甲乙乙丙丙 0000 1354 27106 391111 4121112 5131112 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 第二阶段：最大获利值为 )()(max)( 2232222 2 uxfuPxf u u2 x2 P2(u2)+f3(x2-u2)f2(x2) u2* 012345 0 1 2 3 4 5 000 0+45+0 51 0+65+410+0 102 0+11 5+610+411+0142 0+12 0+12 5+11 10+611+4 11+0161,2 5+12 10+11 11+6 11+4 11+0 212 工厂工厂 获利获利 设备台数设备台数 甲甲乙乙丙丙 0000 1354 27106 391111 4121112 5131112 u3 x3 P3(u3) f3(x3)u3* 012345 0 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 1 2 3 4 5 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 第一阶段：最优获利值为)5()(max)5( 12111 ufuPf 其中x1=5，u1=0,1,2,3,4,5。 u2 x2 P2(u2)+f3(x2-u2)f2(x2) u2* 012345 0 1 2 3 4 5 000 0+45+0 51 0+65+410+0 102 0+11 5+610+411+0142 0+12 0+12 5+11 10+611+4 11+0161,2 5+12 10+11 11+6 11+4 11+0 212 u1 x1 P1(u1)+f2(5-u1) f1(5)u1* 012345 5 0+213+167+149+1012+513+0210,2 工厂工厂 获利获利 设备台数设备台数 甲甲乙乙丙丙 0000 1354 27106 391111 4121112 5131112 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 u1 x1 P1(u1)+f2(5-u1) f1(5)u1* 012345 50+213+167+149+1012+513+0210,2 然后按计算表格的顺序反推算，可知最优分配方案有两个： （1）由于u1*=0，根据x2=x1 u1*=5 0=5，查表3 知u2*=2；由于x3=x2 u2*=52= 3，故u3*=x3=3。 即甲厂分配0台，乙厂分配2台，丙厂分配3台。 u2 x2 P2(u2)+f3(x2-u2)f2(x2) u2* 012345 0 1 2 3 4 5 000 0+45+0 51 0+65+410+0 102 0+11 5+610+411+0142 0+12 0+12 5+11 10+611+4 11+0161,2 5+12 10+11 11+6 11+4 11+0 212 u3 x3 P3(u3) f3(x3)u3* 012345 0 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 1 2 3 4 5 莫莫 莉莉 水电与数字化工程学院 2.3 2.3 在经营管理中的应用在经营管理中的应用 u1 x1 P1(u1)+f2(5-u1) f1(5)u1* 012345 50+213+167+149+1012+513+0210,2 u2 x2 P2(u2)+f3(x2-u2)f2(x2) u2* 012345 0 1 2 3 4 5 000 0+45+0 51 0+65+410+0 102 0+11 5+610+411+0142 0+12 0+12 5+11 10+611+4 11+0161,2 5+12 10+11 11+6 11+4 11+0 212 u3 x3 P3(u3) f3(x3)u3* 012345 0 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 1 2 3 4 5 （2）由于u1*=2，根据x2=x1u1*=52= 3，查表3知 u2*=2，由于x3=x2 u2*=3 2=1，故u3*=x3=1。 即甲厂分配2台，乙厂分配2台，丙厂分配1台。 上述两个分配方案得的总获利均为21万元。 莫莫 莉莉 水电与数字化工程学院 第三章第三章 动态规划动态规划 基本概念介绍基本概念介绍1 1 离散动态规划离散动态规划2 2 连续动态规划连续动态规划3 3 在水库调度中的应用在水库调度中的应用4 4 莫莫 莉莉 水电与数字化工程学院 3.1 3.1 连续动态规划的概念连续动态规划的概念 在资源分配问题中，还有一种要考虑资源回收 利用的问题，这里决策变量为连续值，故称为资源 连续分配问题。 这类问题可叙述如下： 设某种资源数量为x1，可投入A和B两种生产， 第一年投入A种生产的数量为u1，则余下的投入B种 生产的数量为x1-u1，收入为g(u1)+h(x1-u1)，其中 g(u)和h(u)为已知函数，且g(0)=h(0)=0。年终时两 种资源还可以回收，再投入A、B两种生产。 设年回收率分别为0a1和0b1，则在第一 年生产后，回收的资源量合计为x2=au1+b(x1-u1)。 莫莫 莉莉 水电与数字化工程学院 3.1 3.1 连续动态规划的概念连续动态规划的概念 设年回收率分别为0a1和0b1，则在第一 年生产后，回收的资源量合计为x2=au1+b(x1-u1)。 第二年再将资源数量x2中的u2和x2-u2分别再 投入A、B两种生产，则第二年又可得到收入为 g(u2)+h(x2-u2)。如此继续进行n年，应当如何决 定每年投入A生产的资源数量u1,u2, ,un，才能 使总的收入最大。 莫莫 莉莉 水电与数字化工程学院 3.2 3.2 例题例题 例 . 机器负荷分配问题 某厂新购某种新机床125台，据估计，这种机床 5年后将被其它设备所代替。此类机床如在高负荷状 态下工作，每台年创利润10万元，年损坏率为1/2； 如在低负荷状态下工作，每台年创利润6万元，年损 坏率为1/5。问应如何安排这些车床的生产负荷，才 能使5年内获得最大的利润？ 解：很自然想到将问题划分为5个阶段，每一年为 一个阶段。 莫莫 莉莉 水电与数字化工程学院 3.2 3.2 例题例题 状态变量xk表示第k年年初的完好机床台数。决 策变量uk表示第k年安排高负荷状态下工作的机床台 数，则低负荷状态下工作的机床台数为xk-uk台， 则状态转移方程为 1 1143 11() 25510 kkkkkk xuxuxu 第k年可得利润为 10uk+6(xk-uk)=4uk+6xk 最优值函数fk(xk)表示由资源xk出发，从第k年开 始到第5年结束时机床所创造利润的最大值，因而 有递推关系式： 莫莫 莉莉 水电与数字化工程学院 3.2 3.2 例题例题 最优值函数fk(xk)表示由资源xk出发，从第k年开始到 第5年结束时机床所创造利润的最大值，因而有递 推关系式： 1 , 2 , 3 , 4 , 5),(64max)( 0)( 11 0 66 kxfxuxf xf kkkk xu kk kk 当k=5时，有)64(max)( 55 0