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