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

《运筹学课件动态规划精.ppt》由会员分享，可在线阅读，更多相关《运筹学课件动态规划精.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学课件动态规划2023/2/24运筹学课件第1页，本讲稿共68页2023/2/24运筹学课件 动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它可以指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个

2、策略，列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。使各阶段的效益的总和达到最优。8.1 多阶段决策问题与动态规划多阶段决策问题与动态规划第2页，本讲稿共68页2023/2/24运筹学课件安全过河问题安全过河问题古代有3位商人各自带了一个仆人外出来到了一个渡口,渡口只有一条小船每次只能乘2人,仆人私下约定只要岸上的仆人人数超过商人人数,就可杀人越货.但是过河的决策由商人制定.问商人如何安全的渡过河去?第3页，本讲稿共68页2023/2/24运筹学课件第4页，本讲稿共68页2023/2/24运筹学课件一、多阶段决策问题1.时间阶段的例子（机器负荷问题）某厂有1000台

3、机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。123 4 5S1=1000 x1x2x5x4x3s5v1v2v3v4v5s2s3s48.1 多阶段决策问题与动态规划多阶段决策问题与动态规划第5页，本讲稿共68页2023/2/24运筹学课件2.空间阶段的例子（最短路问题）如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。AEB1B2B3C1C2C3D1D229531225156468101312111410阶段1 阶段2 阶段3 阶段4第6页，本讲稿共68页2

4、023/2/24运筹学课件动态规划解决问题的基本特征1.动态规划一般解决最值（最优，最大，最小，最长）问题；2.动态规划解决的问题一般是离散的，可以分解（划分阶段）的；3.动态规划解决的问题必须包含最优子结构，即可以由（n1）的最优推导出n的最优第7页，本讲稿共68页2023/2/24运筹学课件动态规划模型的分类：动态规划模型的分类：以以“时间时间”角度可分成：角度可分成：离散型离散型和连续型。和连续型。从信息确定与否可分成：从信息确定与否可分成：确定型确定型和随机型。和随机型。从目标函数的个数可分成：从目标函数的个数可分成：单目标单目标型和多目标型。型和多目标型。第8页，本讲稿共68页202

5、3/2/24运筹学课件1.基本概念阶段（StageStage）分步求解的过程，用阶段变量k表示，k=1，n状态（StateState）每阶段初每阶段初可能的情形或位置，用状态变量Sk表示。按状态的取值是离散或连续，将动态规划问题分为 离散型和连续型。决策（Decision Decision）每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量xk表示。状态转移由Sk转变为Sk+1的规律，记Sk+1=T(Sk，xk)。策略（PolicyPolicy）由各阶段决策组成的序列，记P1n=x1，xn，称Pkn=xk，xn为阶段k至n的后部子策略。8.28.2基本概念与方程基本概念与方

6、程第9页，本讲稿共68页2023/2/24运筹学课件决策显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。KSkSk+1XkVk第10页，本讲稿共68页2023/2/24运筹学课件过河:决策向量xk(I,J)初始状态s1是T(3,3)结束状态sn是 T(0,0)可达状态有哪些?(3,J)(2,2)(1,1)(0,J)0321123AJII 表示留在左岸的商人人数J 表示留在左岸的仆人人数第11页，本讲稿共68页2023/2/24运筹学课件阶段指标每阶段选定决策xk后所产生的效益，记 vk=vk(Sk，xk)。指标函数各阶

7、段的总效益，记相应于Pkn的指标函数 为vkn=vkn(Sk，Pkn)。其中最优的称最优 指标函数，记 fk=fk（Sk）=opt vkn。问题：动态规划的最优解和最优值各是什么？最优解：最优策略P1n，最优值：最优指标f1。第12页，本讲稿共68页2023/2/24运筹学课件多阶段决策过程多阶段决策过程 d1 d2 dNs1 s2 s3 sN sN+1 1 2 N V1 V2 VN N 阶段决策系统示意图第13页，本讲稿共68页2023/2/24运筹学课件2.基本原理与基本方程（1）基本原理以最短路为例说明第14页，本讲稿共68页2023/2/24运筹学课件（2）基本方程根据最优性原理，可建

8、立从后向前逆推求解的递推公式基本方程：通常动态规划问题的最优值函数满足递推关系式.。边界条件第15页，本讲稿共68页2023/2/24运筹学课件 动态规划求解的一般步骤：-确定过程的分段，构造状态变量；-设置决策变量，写出状态转移；-列出阶段指标和指标函数；-写出基本方程，由此逐段递推求解。KSkSk+1XkVk8.3 动态规划的求解方法动态规划的求解方法第16页，本讲稿共68页2023/2/24运筹学课件例1 用动态规划方法求解前面的最短路问题。AEB1B2B3C1C2C3D1D2295312251564681013121114101.离散型离散型求解方法求解方法第17页，本讲稿共68页20

9、23/2/24运筹学课件 标号法求解标号法求解在每个节点上标出从该节点到终点终点的最短距离AEB1B2B3C1C2C3D1D229531225156468101312111410始端终端0528712201419191234逆序解法第18页，本讲稿共68页2023/2/24运筹学课件AEB1B2B3C1C2C3D1D229531225156468101312111410请在每个节点上标出从该节点到始点始点的最短距离顺序解法第19页，本讲稿共68页2023/2/24运筹学课件解：设阶段k=1，2，3，4依次表示4个阶段选路的过程；状态sk表示k阶段初可能处的位置；决策xk表示k阶段初可能选择的路

10、；阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数 vk4=表示k至4阶段的总路长；用表格方式求解用表格方式求解逆推第20页，本讲稿共68页2023/2/24运筹学课件AEB1B2B3C1C2C3D1D2295312251564681013121114104k Sk xk vk vkn=vk+fk+1 fk3C1C2C38712C1D1EC2D2EC3D2E第21页，本讲稿共68页2023/2/24运筹学课件k Sk xk vk vkn=vk+fk+1 fkAEB1B2B3C1C2C3D1D2295312251564681013121114102B1B2B320B1C1D1E14B2C

11、1D1E19B3C2D2E第22页，本讲稿共68页2023/2/24运筹学课件k Sk xk vk vkn=vk+fk+1 fkAEB1B2B3C1C2C3D1D2295312251564681013121114101A19AB2C1D1EP*14=AB2C1D1Ef1=19（最短路）（最短距）第23页，本讲稿共68页2023/2/24运筹学课件作业作业:用表格方式法求解用表格方式法求解8.2,并给出阶段并给出阶段,状态变量状态变量,决决策变量策变量.状态转移方程和指标函数状态转移方程和指标函数;最优值函数最优值函数第24页，本讲稿共68页2023/2/24运筹学课件第25页，本讲稿共68页2

12、023/2/24运筹学课件2.连续型（用公式递推求解）例2 用动态规划方法求解前面的机器负荷问题。某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。123 4 5S1=1000 x1x2x5x4x3s5v1v2v3v4v5s2s3s4第26页，本讲稿共68页2023/2/24运筹学课件阶段指标vk=8xk+5(sk-xk)表示第k年的产量；指标函数vkn=表示第k至5年的总产量；解：设阶段k=1，5表示第k年安排机器的过程；状态sk表

13、示第k年初的完好机器台数；决策xk表示第k年投入高负荷的机器台数；则投入低负荷的台数为sk-xk；状态转移sk+1=0.7xk+0.9(sk-xk)；第27页，本讲稿共68页2023/2/24运筹学课件f5(S5)是关于x5的单调增函数 x5*=S5 f5(S5)=8S5第28页，本讲稿共68页2023/2/24运筹学课件5年的最大总产量为23.721000=23720。第29页，本讲稿共68页2023/2/24运筹学课件逆推解法的特点:123 4 5 S1x1x2x5x4x3s5v1v2v3v4v5s2s3s4始端已知终端边界值取0或11.已知初始状态s12.最优值函数fk(sk)表示第k阶

14、段的初始状态为sk,从k阶段到n阶段的最优值.该问题的最优值f1(s1)3.边界条件是fn+1=0或者14.递推关系是 fk(sk)=opt(vk+fk+1)第30页，本讲稿共68页2023/2/24运筹学课件第四节 动态规划应用举例 本节将通过动态规划的四种应用类型静态规划问题的动态规划求解、资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。第31页，本讲稿共68页2023/2/24运筹学课件123 S1x1x2x3v1v2v3s2s3s4三阶段决策问题状态变量Sk:s1,s2,s3,s4决策变量为xi:x1,x2,x3例子例子:一、静态规划问题的动态规划求

15、解一、静态规划问题的动态规划求解第32页，本讲稿共68页2023/2/24运筹学课件123 S1x1x2x3v1v2v3s2s3s44假定s1=4,用逆推法可分析每个阶段的状态转移:第3阶段:s3=x3第2阶段:s2=x2+s3第1阶段:s1=x1+s2递推方程:每个阶段上决策变量的取值范围?第33页，本讲稿共68页2023/2/24运筹学课件第34页，本讲稿共68页2023/2/24运筹学课件第35页，本讲稿共68页2023/2/24运筹学课件123 S1x1x2x3v1v2v3s2s3s4k123sk431x*k121fk441第36页，本讲稿共68页2023/2/24运筹学课件123 S

16、1x1x2x3v1v2v3s2s3s44假定s4=4,用顺推法可分析每个阶段的状态转移:第1阶段:s2=x1第2阶段:s3=x2+s2第3阶段:s4=x3+s3递推方程:每个阶段上决策变量的取值范围?已知终止状态sn+1怎么求解动态规划?第37页，本讲稿共68页2023/2/24运筹学课件k123sk-+1134x*k121fk144第38页，本讲稿共68页2023/2/24运筹学课件二、资源分配问题二、资源分配问题1.问题的一般提法 设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？2.数学规划模型模型的特点变量

17、分离。第39页，本讲稿共68页2023/2/24运筹学课件3.用动态规划方法求解阶段k状态sk决策xk=1,n表示把资源分配给第k种产品的过程；表示在给第k种产品分配之前还剩有的资源量；表示分配给第k种产品的资源量；状态转移sk+1=sk-xk；阶段指标vk指标函数vkn 12S1=ax1x2g1(x1)g2(x2)nxnsngn(xn)s2s3.第40页，本讲稿共68页2023/2/24运筹学课件例例3 3 某公司拟将某种高效设备某公司拟将某种高效设备5 5台分配给所属甲、台分配给所属甲、乙、丙乙、丙3 3厂。各厂获此设备后可产生的效益如下表。厂。各厂获此设备后可产生的效益如下表。问应如何分

18、配，可使所产生的总效益最大？问应如何分配，可使所产生的总效益最大？效益厂设备台数甲 乙 丙0 0 0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12第41页，本讲稿共68页2023/2/24运筹学课件解：阶段k状态sk决策xk=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；表示在第k阶段初还剩有的可分台数；表示第k阶段分配的设备台数；状态转移sk+1=sk-xk；阶段指标vk指标函数vk3 问题：本问题是属于离散型还是属于连续型？怎样解？离散型，用表格的方式求解。第42页，本讲稿共68页2023/2/24运筹学课件效益厂设备台数甲 乙 丙0 0

19、0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12k Sk xk vk vk+fk+1 fk3012345012345 0 4 6111212 0+0 4+0 6+011+012+012+0 0 4 6111212012345第43页，本讲稿共68页2023/2/24运筹学课件k Sk xk vk vk+fk+1 fk0123452 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+010 2-0 0 0 0+11 1 5 5+6 2 10 10+4 3 11 11+014 2-1

20、 0 0 0+12 1 5 5+11 2 10 10+6 3 11 11+4 4 11 11+016 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+021 2-3第44页，本讲稿共68页2023/2/24运筹学课件k Sk xk vk vk+fk+1 fk15012345 0 3 7 912130+21 3+167+149+1012+513+021 0-2-3 2-2-1最优策略：P*13 为0-2-3或2-2-1，即分给甲厂0台、分给乙厂2台、分给丙厂3台，或分给甲厂2台、分给乙厂2台、分给丙厂1台。最优值：

21、f1=21。可见，最优解可以是不唯一的，但最优值是唯一的。第45页，本讲稿共68页2023/2/24运筹学课件资源分配问题的应用很广泛，例如：1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？第46页，本讲稿共68页2023/2/24运筹学课件其中,ci(xi)表示携带数量为xi的价值函数;Wi表示第i种物品的单件重量1n2s1x1x2xnSn+1s2

22、v1=c1(x1)vn=cn(xn)v2=c2(x2)sn第47页，本讲稿共68页2023/2/24运筹学课件三、复合系统工作可靠性问题三、复合系统工作可靠性问题1.问题的一般提法 设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？串接:12第48页，本讲稿共68页2023/2/24运筹学课件2.数学规划模型模型的特点变量分离。3.用动态规划方法求解12S1=Wx1x2p1(x1)p2(x2)nxnsnpn(xn)

23、s2s3.第49页，本讲稿共68页2023/2/24运筹学课件阶段k状态sk决策xk=1,n表示安排第k个部件备用件的过程；表示在给第k个部件安排之前还剩有的容许重量；表示第k个部件上安排的备用件数量；状态转移sk+1=sk-wkxk；阶段指标vk指标函数vkn 第50页，本讲稿共68页2023/2/24运筹学课件可靠性问题的应用很广泛，例如：1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？2.已知x1+x2+xn=c，求z=x1x

24、2xn的最大值。第51页，本讲稿共68页2023/2/24运筹学课件四、设备更新问题四、设备更新问题例4 某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的决定。假设第k年中，rk(tk)表示车龄为tk的车使用一年的收入，uk(tk)表示车龄为tk的车使用一年的维修费用，ck(tk)表示车龄为tk的车更新成新车的费用。现公司需制定一个10年计划，以决定如何安排使10年的总收入最大。12S1=？x1x2 10 x10s10v1v2v10s2问题：状态和决策怎样设置？决策是更新与否，可用0-1变量表示；状态可设为车龄。第52页，本讲稿共68页2023/2/24运筹学课件阶段k状

25、态sk决策xk=1,10表示第k年的决策过程；=tk表示第k年的车龄；状态转移tk+1=tk +1(1-xk)阶段指标vk指标函数vkn=rktk -uktk -ck(tk)(1-xk)(1-xk)xk第53页，本讲稿共68页2023/2/24运筹学课件四、其他随机型问题举例例5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。据技术分析估计，每个瓷瓶出炉后的合格率为0.5，各瓶合格与否相互独立（即一炉如装有n个瓷瓶，那么出炉后都不合的概率为0.5n）。制造一个瓷瓶的原料费为100元，烧一炉的费用为300元。现因厂中条件限制最多只能烧3炉，每炉最多装4个瓷瓶。若3炉的瓷瓶无1个合格，则因不能履行

26、合同而被罚款1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。第54页，本讲稿共68页2023/2/24运筹学课件作业作业:9.1 9.11第55页，本讲稿共68页2023/2/24运筹学课件采采购购与与销销售售 某商店在未来的4个月里,准备用它的一个仓库来专门经销某种商品,仓库最大容量能贮存这种商品1000单位.假定该商店每月只能出卖仓库现有的货,当商店在某月购货时,下月初才能到货.预测该商品未来四个月的买卖价格如表7-12所示,假定商店在1月开始经销时,仓库贮有该商品500单位.试问若不计库存费用,该商店应如何制定1月至4月的订购与销售计划,使预期获

27、利最大。1281317 10911151234销售单价购买单价月份 k第56页，本讲稿共68页2023/2/24运筹学课件KSkSk+1XkVkYk题目给出的约束条件题目给出的约束条件第57页，本讲稿共68页2023/2/24运筹学课件n建立动态规划模型建立动态规划模型阶段k:按月份划分为4个阶段，K1，2，3，4 ：第K月定购的货物数量状态转移方程：状态变量 :第K月初时仓库中的存货量（含上月订货）决策变量 ：第K月卖出的货物数量最优指标函数 ：第K月初存货量为 时，从第K月到4月末所获得最大利润。第58页，本讲稿共68页2023/2/24运筹学课件则有逆序递推关系式(基本方程)为：n建立动

28、态规划模型建立动态规划模型第59页，本讲稿共68页2023/2/24运筹学课件当 K4 时显然，决策应取 ，最大值：n动态规划模型求解动态规划模型求解第60页，本讲稿共68页2023/2/24运筹学课件当 K3 时n动态规划模型求解动态规划模型求解第61页，本讲稿共68页2023/2/24运筹学课件这个阶段需求解一个线性规划问题：因为只有两个变量 ，可以用图解法，也可以用单纯形法，求解得到：时有最大值n动态规划模型求解动态规划模型求解第62页，本讲稿共68页2023/2/24运筹学课件当 K2 时n动态规划模型求解动态规划模型求解第63页，本讲稿共68页2023/2/24运筹学课件求解线性规划

29、问题：得：n动态规划模型求解动态规划模型求解第64页，本讲稿共68页2023/2/24运筹学课件当 K1 时因为所以n动态规划模型求解动态规划模型求解第65页，本讲稿共68页2023/2/24运筹学课件解线性规划问题：得决策:n动态规划模型求解动态规划模型求解第66页，本讲稿共68页2023/2/24运筹学课件最优策略见下表，最大利润为16000 月份期前存货售出量购进量 1 500 500 0 2 0 0 1000 3 1000 1000 1000 4 1000 1000 0n动态规划模型求解结果动态规划模型求解结果第67页，本讲稿共68页2023/2/24运筹学课件第68页，本讲稿共68页