运筹学课件--动态规划.ppt

2019/6/28,运筹学课件,动态规划,8.1 多阶段决策问题与动态规划 8.2 动态规划的基本概念 8.3 动态规划的步骤 8.4 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 不确定性采购问题 4 排序问题,2019/6/28,运筹学课件,动态规划所研究的对象是多阶段决策问题。 所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。,8.1 多阶段决策问题与动态规划,2019/6/28,运筹学课件,安全过河问题,古代有3位商人各自带了一个仆人外出来到了一个渡口, 渡口只有一条小船每次只能乘2人,仆人私下约定只要岸上的仆人人数超过商人人数,就可杀人越货.但是过河的决策由商人制定. 问商人如何安全的渡过河去?,2019/6/28,运筹学课件,2019/6/28,运筹学课件,一、多阶段决策问题 1. 时间阶段的例子（机器负荷问题） 某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。,8.1 多阶段决策问题与动态规划,2019/6/28,运筹学课件,2. 空间阶段的例子（最短路问题） 如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。,2019/6/28,运筹学课件,动态规划,解决问题的基本特征,1. 动态规划一般解决最值（最优，最大，最小，最长）问题；,2. 动态规划解决的问题一般是离散的，可以分解（划分阶段）的；,3. 动态规划解决的问题必须包含最优子结构，即可以由（n1）的最优推导出n的最优,2019/6/28,运筹学课件,动态规划模型的分类： 以“时间”角度可分成： 离散型和连续型。 从信息确定与否可分成： 确定型和随机型。 从目标函数的个数可分成： 单目标型和多目标型。,2019/6/28,运筹学课件,1.基本概念,阶段（Stage）分步求解的过程，用阶段变量k表示，k=1，n,状态（State）每阶段初可能的情形或位置，用状态变量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为 离散型和连续型。,决策（ Decision ）每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量xk表示。,状态转移由Sk转变为Sk+1的规律，记Sk+1=T(Sk， xk)。,策略（ Policy）由各阶段决策组成的序列，记P1n=x1， xn， 称Pkn=xk， xn为阶段k至n的后部子策略。,8.2基本概念与方程,2019/6/28,运筹学课件,当前状态,以前状态,决策,显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。,K,Sk,Sk+1,Xk,Vk,2019/6/28,运筹学课件,过河:决策向量xk(I,J) 初始状态s1是T(3,3) 结束状态sn是 T(0,0) 可达状态有哪些?(3,J) (2,2) (1,1) (0,J),0,3,2,1,1,2,3,A,J,I,I 表示留在左岸的商人人数 J 表示留在左岸的仆人人数,2019/6/28,运筹学课件,阶段指标每阶段选定决策xk后所产生的效益，记 vk= vk(Sk， xk)。,指标函数各阶段的总效益，记相应于Pkn的指标函数 为vkn= vkn(Sk， Pkn )。其中最优的称最优 指标函数，记 fk = fk（ Sk ）=opt vkn。,问题：动态规划的最优解和最优值各是什么？,最优解：最优策略P1n ， 最优值：最优指标f1。,2019/6/28,运筹学课件,多阶段决策过程,2019/6/28,运筹学课件,2.基本原理与基本方程,（1）基本原理,以最短路为例说明,2019/6/28,运筹学课件,（2）基本方程,根据最优性原理，可建立从后向前逆推求解的递推公式基本方程：,通常动态规划问题的最优值函数满足递推关系式.。,边界条件,2019/6/28,运筹学课件,动态规划求解的一般步骤： - 确定过程的分段，构造状态变量； - 设置决策变量，写出状态转移； - 列出阶段指标和指标函数； - 写出基本方程，由此逐段递推求解。,K,Sk,Sk+1,Xk,Vk,8.3 动态规划的求解方法,2019/6/28,运筹学课件,例1 用动态规划方法求解前面的最短路问题。,1. 离散型,求解方法,2019/6/28,运筹学课件,标号法求解 在每个节点上标出从该节点到终点的最短距离,始端,终端,0,5,2,8,7,12,20,14,19,19,1,2,3,4,逆序解法,2019/6/28,运筹学课件,请在每个节点上标出从该节点到始点的最短距离,顺序解法,2019/6/28,运筹学课件,解：设阶段k=1，2，3，4依次表示4个阶段选路的过程；,状态sk表示k阶段初可能处的位置；,决策xk表示k阶段初可能选择的路；,阶段指标vk表示k阶段与所选择的路段相应的路长；,指标函数 vk4 = 表示k至4阶段的总路长；,用表格方式求解,逆推,2019/6/28,运筹学课件,4,3,8,7,12,C1D1E,C2D2E,C3D2E,2019/6/28,运筹学课件,2,2019/6/28,运筹学课件,1,A,19,AB2C1D1E,f1 = 19,（最短路） （最短距）,2019/6/28,运筹学课件,作业: 用表格方式法求解8.2,并给出阶段,状态变量,决策变量.状态转移方程和指标函数;最优值函数,2019/6/28,运筹学课件,2019/6/28,运筹学课件,2. 连续型（用公式递推求解）,例2 用动态规划方法求解前面的机器负荷问题。 某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。,2019/6/28,运筹学课件,阶段指标vk=8xk+5(sk-xk)表示第k年的产量； 指标函数vkn= 表示第k至5年的总产量；,解：设阶段k=1，5表示第k年安排机器的过程； 状态sk表示第k年初的完好机器台数； 决策xk表示第k年投入高负荷的机器台数；则投入低负荷的台数为sk-xk ； 状态转移sk+1=0.7xk+0.9(sk-xk)；,2019/6/28,运筹学课件,f5 (S5 )是关于x5的单调增函数 x5 *=S5 f5 (S5 )= 8S5,2019/6/28,运筹学课件,5年的最大总产量为23 .721000=23720。,2019/6/28,运筹学课件,逆推解法的特点:,始端已知,终端边界值取0或1,1.已知初始状态s1 2.最优值函数fk(sk)表示第k阶段的初始状态为sk,从k阶段到n阶段的最优值. 该问题的最优值f1(s1) 3.边界条件是fn+1=0或者1 4.递推关系是 fk(sk)=opt(vk+fk+1),2019/6/28,运筹学课件,第四节 动态规划应用举例 本节将通过动态规划的四种应用 类型静态规划问题的动态规划求解、资源分配问题、复合系统可 靠性问题、设备更新问题，进一步介 绍动态规划的特点和处理方法。,2019/6/28,运筹学课件,三阶段决策问题,状态变量Sk: s1,s2,s3,s4 决策变量为xi:x1,x2,x3,例子:,一、静态规划问题的动态规划求解,2019/6/28,运筹学课件,4,假定s1=4,用逆推法可分析每个阶段的状态转移: 第3阶段: s3=x3 第2阶段: s2=x2+s3 第1阶段: s1=x1+s2,递推方程:,每个阶段上决策变量的取值范围?,2019/6/28,运筹学课件,2019/6/28,运筹学课件,2019/6/28,运筹学课件,2019/6/28,运筹学课件,4,假定s4=4,用顺推法可分析每个阶段的状态转移: 第1阶段: s2=x1 第2阶段: s3=x2+s2 第3阶段: s4=x3+s3,递推方程:,每个阶段上决策变量的取值范围?,已知终止状态sn+1怎么求解动态规划?,2019/6/28,运筹学课件,2019/6/28,运筹学课件,二、资源分配问题,1. 问题的一般提法 设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？,2. 数学规划模型,模型的特点 变量分离。,2019/6/28,运筹学课件,3.用动态规划方法求解,阶段k 状态sk 决策xk,=1,n表示把资源分配给第k种产品的过程； 表示在给第k种产品分配之前还剩有的资源量； 表示分配给第k种产品的资源量；,状态转移sk+1,= sk- xk ；,阶段指标vk 指标函数vkn,2019/6/28,运筹学课件,例3 某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？,2019/6/28,运筹学课件,解：,阶段k 状态sk 决策xk,=1,2,3依次表示把设备分配给甲、乙、丙厂的过程； 表示在第k阶段初还剩有的可分台数； 表示第k阶段分配的设备台数；,状态转移sk+1,= sk- xk ；,阶段指标vk 指标函数vk3,问题：本问题是属于离散型还是属于连续型？怎样解？,离散型，用表格的方式求解。,2019/6/28,运筹学课件,3,012345,012345,0 4 6 111212,0+0 4+0 6+0 11+0 12+0 12+0,0 4 6 111212,012345,2019/6/28,运筹学课件,2,0 0 0+0 0 0-0,0 0 0+4 1 5 5+0,5 1-0,0 0 0+6 1 5 5+4 2 10 10+0,10 2-0,0 0 0+11 1 5 5+6 2 10 10+4 3 11 11+0,14 2-1,0 0 0+12 1 5 5+11 2 10 10+6 3 11 11+4 4 11 11+0,16 1-3 2-2,0 0 0+12 1 5 5+12 2 10 10+11 3 11 11+6 4 11 11+4 5 11 11+0,21 2-3,2019/6/28,运筹学课件,1,5,21 0-2-3 2-2-1,最优策略：P*13 为0-2-3或2-2-1， 即分给甲厂0台、分给乙厂2台、分给丙厂3台， 或分给甲厂2台、分给乙厂2台、分给丙厂1台。,最优值： f1=21。,可见，最优解可以是不唯一的，但最优值是唯一的。,2019/6/28,运筹学课件,资源分配问题的应用很广泛，例如： 1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？ 2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？,2019/6/28,运筹学课件,其中,ci(xi)表示携带数量为xi的价值函数; Wi表示第i种物品的单件重量,2019/6/28,运筹学课件,三、复合系统工作可靠性问题,1. 问题的一般提法 设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？,串接:,2019/6/28,运筹学课件,2. 数学规划模型,模型的特点 变量分离。,3.用动态规划方法求解,2019/6/28,运筹学课件,阶段k 状态sk 决策xk,=1,n表示安排第k个部件备用件的过程； 表示在给第k个部件安排之前还剩有的容许重量； 表示第k个部件上安排的备用件数量；,状态转移sk+1,= sk- wkxk ；,阶段指标vk 指标函数vkn,2019/6/28,运筹学课件,可靠性问题的应用很广泛，例如： 1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？ 2.已知x1+x2+xn=c，求z=x1x2xn的最大值。,2019/6/28,运筹学课件,四、设备更新问题,例4 某运输公司购进一批卡车投入运营，公司每年初需 对卡车作出更新或继续使用的决定。假设第k年中，rk(tk) 表示车龄为tk的车使用一年的收入，uk(tk)表示车龄为tk的 车使用一年的维修费用，ck(tk)表示车龄为tk的车更新成新 车的费用。现公司需制定一个10年计划，以决定如何安排 使10年的总收入最大。,问题：状态和决策怎样设置？, 决策是更新与否，可用0-1变量表示；状态可设为车龄。,2019/6/28,运筹学课件,阶段k 状态sk 决策xk,= 1,10表示第k年的决策过程； = tk表示第k年的车龄；,状态转移tk+1,= tk +1,(1-xk),阶段指标vk 指标函数vkn,= rktk - uktk - ck(tk),xk,2019/6/28,运筹学课件,四、其他随机型问题举例,例5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。 据技术分析估计，每个瓷瓶出炉后的合格率为0.5，各瓶合格 与否相互独立（即一炉如装有n个瓷瓶，那么出炉后都不合 的概率为0.5n）。制造一个瓷瓶的原料费为100元，烧一炉的 费用为300元。现因厂中条件限制最多只能烧3炉，每炉最多 装4个瓷瓶。若3炉的瓷瓶无1个合格，则因不能履行合同而 被罚款1600元。试用动态规划方法确定一种生产方案（即每 炉该装几个瓷瓶），使总的期望成本为最小。,2019/6/28,运筹学课件,作业: 9.1 9.11,2019/6/28,运筹学课件,采购与 销售,某商店在未来的4个月里,准备用它的一个仓库来专门经销某种商品,仓库最大容量能贮存这种商品1000单位.假定该商店每月只能出卖仓库现有的货,当商店在某月购货时,下月初才能到货.预测该商品未来四个月的