《数据、模型与决策_(第二版)》第六章：动态规划

第六章 动态规划,第六章 动态规划,数据、模型与决策 (第二版),学习目标,动态规划是解决多阶段决策过程最优化问题的一种方法。 明确什么是多阶段的决策问题；理解动态规划的基本思想和基本方程；理解动态规划的最优性原理和最优性定理。 掌握动态规划在资源分配问题、生产和存贮问题、采购问题中的应用，并学会使用动态规划方法分析和解决实际的问题。,第六章 动态规划,数据、模型与决策 (第二版),第六章 动态规划,动态规划（Dynamic Programming，简称DP）是运筹学的重要分支之一，它是一种研究多阶段决策问题的最优化理论和方法。大约产生于50年代。1951年美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变为一系列互相联系单阶段问题，然后逐个加以解决。 动态规划的方法，在工程技术中、企业管理、工农业生产及军事等部门都有广泛的应用，并且获得了显著的效果。 动态规划模型的分类，根据多阶段决策过程的时间变量是离散的还是连续的变量，过程分为离散决策过程和连续决策过程。,第六章 动态规划,数据、模型与决策 (第二版),第六章 动态规划,6.1 动态规划的基本概念和基本方程 6.2 动态规划应用举例,第六章 动态规划,数据、模型与决策 (第二版),6.1 动态规划的基本概念和基本方程,6.1.1 多阶段决策 6.1.2 动态规划的基本概念 6.1.3 动态规划的基本方程 6.1.4 动态规划的基本思想归纳 6.1.5 动态规划的最优性原理和最优性定理,第六章 动态规划,数据、模型与决策 (第二版),6.1.1 多阶段决策,多阶段决策问题：把一个问题可看作一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程。,第六章 动态规划,数据、模型与决策 (第二版),最短路问题,下图是一个线路网络图，代表待定的输油管可行路线，A，B，C代表经过的三个地区，每个地区都有若干个转运点，构成许多不同的输油路线，转运点间的数字表示点间距离，问应选择那些路线，使总路线最短？,第六章 动态规划,数据、模型与决策 (第二版),6.1.2 动态规划的基本概念,阶段 状态 决策 策略 状态转移方程 指标函数和最优值函数,第六章 动态规划,数据、模型与决策 (第二版),6.1.3动态规划的基本方程,动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 当k=4时，由D1到终点E只有一条路线，故f4（D1）=4， 同理，f4（D2）=3。 当k=3时，出发点有C1，C2 ，C3三个。若从C1出发，则有两个选择，一是至D1，一是至D2，则 f3（C1）=min =min =7 其相应的决策为u3（C1）= D1，这说明，由C1至终点E的最短距离为7，其最短路线是C1 D1 E。 同理，从C2和C3出发，则有 f3（C2）=6 其相应的决策为u3（C2）= D2 f3（C3）=10 其相应的决策为u3（C3）= D1,第六章 动态规划,数据、模型与决策 (第二版),当k=2时，有 f2（B1）=12 u2（B1）= C2 f2（B2）=11 u2（B2）= C2 f2（B3）=9 u2（B2）= C2 当k=1时，出发点只有一个A点，则有 f1（A）=15 u1（A）= B1 于是，我们找到从起点A到终点E点的最短距离为15。 为了找出最短路线，再按计算的顺序反推之，可求出最优决策函数序列u k，即由u1（A）= B1，u2（B1）= C2，u3（C2）= D2，u4（D2）= E组成一个最优策略。因而，找出相应的最短路线为A B1 C2 D2 E。,第六章 动态规划,数据、模型与决策 (第二版),第六章 动态规划,数据、模型与决策 (第二版),一般情况下，k阶段与k+1阶段的递推关系可写为 （6-1） k=n，n-1， ，1 边界条件为 f n+1（sn+1）=0 这种递推关系式（x.1）称为动态规划的基本方程。,第六章 动态规划,数据、模型与决策 (第二版),6.1.4 动态规划方法的基本思想归纳,（1）动态方法关键在于正确的归纳出基本的递推关系式和恰当的边界条件（即基本方程）。要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后的一个子问题所得到的最优解，就是整个问题的最优解。 （2）在多阶段决策过程中，动态规划方法是既将当前一阶段和未来各阶段分开，又将当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。 （3）在求整个问题的最优策略时，由于初始状态是已知的，而每阶段的决策都是该阶段状态的函数，故最优决策所进过的各阶段状态便可逐次变换得到，从而确定了最优路线。,第六章 动态规划,数据、模型与决策 (第二版),步骤： （1）将系统分为恰当的阶段，并编号； （2）确定状态变量sk，状态集合Sk； （3）确定决策变量dk（sk），以及允许决策的集合Dk（Sk）； （4）建立状态转移方程Sk+1=Tk（Sk，uk）; （5）建立指标函数Vk，n的关系。,第六章 动态规划,数据、模型与决策 (第二版),6.1.5动态规划的最优性原理和最优性定理,动态规划的最优性定理： 设阶段数为n的多阶段决策过程，其阶段编号为k=0，1， ，n-1。允许策略 是最优决策的重要条件，对任一个k，0kn-1和 有 式中， ， ，当是由给定的初始状态so和子策略 所确定的k段状态。当V是效益函数时，opt取max；当V是损失函数时，opt取min（证明省略）。,第六章 动态规划,数据、模型与决策 (第二版),推论 若允许策略 是最优策略，则对任意的k，0kn-1，它的子策略 对于 为起点的k到n-1子过程来说，必是最优策略（注意：k段状态 是由s0和 所决定的）。,第六章 动态规划,数据、模型与决策 (第二版),第六章 动态规划,6.1 动态规划的基本概念和基本方程 6.2 动态规划应用举例,第六章 动态规划,数据、模型与决策 (第二版),6.2动态规划应用举例,6.2.1 资源分配问题 6.2.2 生产与存贮问题 6.2.3 采购问题 6.2.4 复合系统工作可靠性问题 6.2.5 背包问题 6.2.6 货郎担问题,第六章 动态规划,数据、模型与决策 (第二版),6.2.1 资源分配问题,资源分配问题是一种或若干种有限资源（如原材料、电力、资金与设备等）合理的分配给若干使用者，以使总体上达到最优效果。,第六章 动态规划,数据、模型与决策 (第二版),某企业集团购置了三台设备，分配给所属的甲、乙、丙三个工厂使用。由于各工厂外部环境及内部条件有差异，在获得这些设备后所得盈利也各有不同，如图表所示。问：该集团如何考虑，才能使分配给各工厂后，国家所得的利益最大？,第六章 动态规划,数据、模型与决策 (第二版),sk表示分配给第k个工厂至第n个工厂的设备台数。 xk分配给第k个工厂的设备台数。 则 为分配给第k+1个工厂至第n个工厂的设备台数。 表示为xk 台设备分配到第k个工厂所得的盈利值。 表示为sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。,第六章 动态规划,数据、模型与决策 (第二版),第三阶段,第六章 动态规划,数据、模型与决策 (第二版),第二阶段：,第六章 动态规划,数据、模型与决策 (第二版),第一阶段：,从而，可以得到如下解： =0， =0， =3或者 =0， =2， =1。,第六章 动态规划,数据、模型与决策 (第二版),6.2.2 生产与存储问题,某厂根据市场预测，确定今后四个月该厂的一种主要产品每月需求量如表6-6所示。已知每月生产固定费用为3000元，但若当月不生产则为0；产品成本为1000元/件；每个月末未售出的产品，每单位存贮费500元；每个月最大生产能力为6万件；若第1个月初无库存产品，第4个月末也不留库存，则该厂应怎样安排生产，才能使今后4个月的总费用最小？,第六章 动态规划,数据、模型与决策 (第二版),第六章 动态规划,数据、模型与决策 (第二版),令 k=1，2，3，4表示今后4个月的序号。 设：vk=第k月末的库存量； xk=第k月的产量。 令以dk表示第k月的需求量，则： vk=vk-1+xk-dk 第k月内的生产成本为：,第六章 动态规划,数据、模型与决策 (第二版),hk（vk）表示第k月结束时有库存量vk所需的存贮费用hk（vk）=0.5vk 则由题意得第k月的成本总费用为： 其中,第六章 动态规划,数据、模型与决策 (第二版),6.2.3 采购问题,某厂必须在今后的5周之内购买一批原材料，根据过去的资料统计，未来5周之内的浮动价格和概率如表6-7所示。问，应该在哪一周以什么价格购入，才能使其采购原材料的价格最低？,第六章 动态规划,数据、模型与决策 (第二版),Sk为状态变量，表示第k周的原料实际价格。 为决策变量，当 =1时，采购；当 =0时，表示第k周等待。 表示第k周决定等待，而在以后采取最优决策时采购价格的期望值。 fk(sk) 表示第k周的价格为 时，从第k周到第5周采取最优策略所得的最小期望值。 所以，我们得到逆推关系式为：,第六章 动态规划,数据、模型与决策 (第二版),其中 并且得出最优决策为,第六章 动态规划,数据、模型与决策 (第二版),6.2.4 复合系统工作可靠性问题,设某种机器的工作系统有n个部件串联组成，只要有一个部件失灵，整个系统就不能工 作。为提高整个系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并且设计了备用元件自动投入装置。显然，备用元件越多，整个系统正常工作的可靠性越大。但备用设备多了，整个系统的成本、重量、体积均相应加大，工作精度也降低，因此，最优化问题是在考虑上述限制条件下，应如何选择各部件的备用元件数，使整个系统的工作可靠性最大。,第六章 动态规划,数据、模型与决策 (第二版),设部件 i（i=1，2，n）上装有ui个备用件时，它正常工作的概率为 ，因此，整个系统正常工作的可靠性，可用它正常工作的概率衡量，即,第六章 动态规划,数据、模型与决策 (第二版),设装一个部件i备用元件费用为 ，总量为 ，要求整个系统所装备用元件的总费用不超过c，总重量不超过w，则这个问题有两个约束条件，它的静态规划模型为： max s.t 且为整数，i=1，2，3，n,第六章 动态规划,数据、模型与决策 (第二版),整机可靠性的动态规划基本方程为：,第六章 动态规划,数据、模型与决策 (第二版),某厂设计一种电子设备，由三种元件D1、D2、D3组成，已知这三种元件的价格和可靠性如表6-8所示。要求在设计中所能使用元件的费用不超过105元，试问应如何设计使设备的可靠性达到最大（不考虑重量的限制）。,第六章 动态规划,数据、模型与决策 (第二版),6.2.5 背包问题,某运输个体户有一辆能载重10吨的货车。现在有3种物品需要从甲城运至乙城，这3种货物的单位重量和每件的运输利润如表6-9所示，现在问：应该怎么选择物品（几件）才能使装载的利润最大？,第六章 动态规划,数据、模型与决策 (第二版),决策变量 表示第k种物品的装入件数； 表示第k种物品的单位运输利润； 状态变量 表示装入第1种物品至第k种物品的总重量； 表示装入第k种物品的重量。 则状态转移方程为：,第六章 动态规划,数据、模型与决策 (第二版),最优函数 是指当总重量不超过 吨时，货车可以装载的从第1种到第k种物品的最大利润，即：,第六章 动态规划,数据、模型与决策 (第二版),6.2.6 货郎担问题,一个推销员需要去n个城市推销产品，从某城出发，经过其他n-1个城市一次且仅仅一次，再返回原出发城市，试问如何选择行程路线，使总路程最短？,第六章 动态规划,数据、模型与决策 (第二版),设S表示从 到 中间所有可能经过的城市集合，S实际上是包含除 、 两个点之外其余点的集合，但S中的点个数要随阶段数改变。 状态变量（i，s） ：表示从 出发，经过S集合中所有点依次到达最后 。 决策：表示为由一个城市走到另一城市。 表示从 经k个城市的S集合到 城市的最短路线上邻接 的前一个城市。 最优指标函数 fk（i，S）：表示从 出发经由k个城市的S集合到 的最短路线。,第六章 动态规划,数据、模型与决策 (第二版),动态规划的顺序梯推关系为,第六章 动态规划,数据、模型与决策 (第二版),已知四个城市间