运筹学第三版第六章_动态规划课件.ppt

第八章动态规划,教学内容：动态规划问题实例动态规划的基本概念与原理动态规划应用举例,引言,动态规划是解决多阶段决策过程最优化的一种方法。该方法是由美国数学家贝尔曼（R.E.Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了DynamicProgramming一书，是动态规划领域中的第一本著作。,第一节动态规划问题及实例,动态规划是解决多阶段决策问题的一种方法，是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。动态规划模型的分类：以“时间”角度可分成：离散型和连续型。从信息确定与否可分成：确定型和随机型。从目标函数的个数可分成：单目标型和多目标型。,第一节动态规划问题及实例,一、多阶段决策过程多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策过程也称为序贯决策过程。这种问题就称为多阶段决策问题。,二、多阶段决策问题的特点过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。,第一节动态规划问题及实例,三、具体实例1、最短路线问题,给定一个线路网络，,要从A向F铺设一条输油管道，各点间连,线上的数字表示距离，问应选择什么路线，可使总距离最短？,第一节动态规划问题及实例,2、生产与存储问题：,某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。,第一节动态规划问题及实例,3、投资决策问题,某公司现有资金Q亿元，在今后5年内考虑给A、B、C、D四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第五年末拥有资金的本利总额最大。,第一节动态规划问题及实例,4、设备更新问题,企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。,现在某企业要决定一台设备未来8年的更新计划，已预测到第j年购买设备的价格为Kj，Gj为设备经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费用(j=1,28)，问应在哪年更新设备可使总费用最小。,第二节动态规划的基本概念与原理,动态规划的基本概念阶段；状态；决策和策略；状态转移方程；指标函数。,第二节动态规划的基本概念与原理,一。基本概念,阶段：是指问题需要做出决策的步数。阶段总数常记为n，相应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变量，k=1,2,n.k即可以是顺序编号也可以是逆序编号，常用顺序编号。,状态：各阶段开始时的客观条件，第k阶段的状态常用状态变量表示，状态变量取值的集合成为状态集合，用表示。,例如，案例1中，,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第1阶段,第2阶段,第3阶段,第4阶段,第5阶段,状态1,状态2,状态3,状态4,状态5,状态6,决策：是指从某阶段的某个状态出发，在若干个不同方案中,做出的选择。表示决策的变量，称为决策变量，用表示。表示第k阶段当状态处于sk时的决策变量。,例如：表示走到C阶段,当处于C2路口时，下一步奔D1.,时的允许决策集合记为，例如：,决策变量允许的取值范围称为允许决策集合，第k阶段状态为,状态转移方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用,表示。,策略：一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略。简称子策略，记为。即,当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记为：,在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。,指标函数：分阶段指标函数和过程指标函数。阶段指标函数,是指第k阶段从状态出发，采取决策时的效益，用,表示。而过程指标函数是从第k阶段的某状态出发，,采取子策略,效益之和：,最优指标函数：表示从第k阶段状态为时采用最佳策略,到过程终止时的最佳效益。记为,时所得到的阶段,其中opt可根据具体情况取max或min。,基本方程：此为逐段递推求和的依据，一般为：,式中opt可根据题意取max或min.,例如，案例1的基本方程为：,最优性原理：最优策略的子策略必为最优。不管过去的状态,和决策如何，从眼下直到最后的诸决策必构成最优子策略。,动态规划的优点：,可把一个N维优化问题化成N个一维优化问题求解。函数方程中附加某些约束条件，可使求解更加容易。求得最优解以后，可得所有子问题的最优解。,动态规划的缺点：,“一个”问题，“一个”模型，“一个”求解方法。且求解技巧要求比较高，没有统一处理方法。状态变量维数不能太高，一般要求小于6。,第三节动态规划应用举例,例1最短路线问题,基本思想：如果起点A经过B1,C1,D1,E1而到终点F，则由C1出发经D1,E1到F点这条子路线，是从C1到F的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推。,状态变量：各路线的位置,决策变量：第k阶段当状态处于时，决定下一个状态的位置,状态转移方程：上一阶段到下一阶段的转移规则,指标函数：从状态出发，采取决策时的路程距离,最优指标函数：第k阶段状态为时且采用最佳走线策略，使从k位置及以后的路线最短。,逆序递推方程：,（1）k=5时，状态,它们到F点的距离即为,最短路。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（2）k=4时，状态,它们到F点需经过中途,点E，需一一分析从E到F的最短路：先说从D1到F的最短路,有两种选择：经过E1,E2,比较最短。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,这说明由D1到F的最短距离为7，其路径为,相应的决策为：,这说明由D2到F的最短距离为5，其路径为,相应的决策为：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即D3到F的最短距离为5，其路径为,相应的决策为：,（3）k=3时，状态,这说明由C1到F的最短距离为12，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即由C2到F的最短距离为10，相应的决策为,即由C3到F的最短距离为8，相应的决策为,即由C4到F的最短距离为9，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（4）k=2时，状态,这说明由B1到F的最短距离为13，相应的决策为,即由B2到F的最短距离为15，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（1）k=1时，只有一个状态点A,则,即由A到F的最短距离为17，相应的决策为,所以最优路线为：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,再按计算顺序反推可得最优决策序列：,顺序递推方程：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,例1：,1阶段,2阶段,3阶段,4阶段,5阶段,行走方向,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,K=1时,注意到：,所以,K=2时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,K=3时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,类似地，可算出：,最优策略：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,最短路径：,最短路长：,注：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使用。,例2资源分配问题（离散型）,例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？,表1利润增长额,（百元）,解：把对四个工厂的投资依次看成4个阶段的决策过程，,确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：,状态变量：可用于第k,k+1,n个工厂的投资额。,决策变量：第k阶段对第k个工厂的投资额。,允许决策集：,状态转移方程：,其中,阶段指标函数：第k阶段投资元时所产生的利润。（见上表）,最优指标函数：第k阶段状态为且采取最佳投资策略，从第k个工厂以及以后的最大总利润。,逆序法基本递推方程：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1利润增长额,（百元）,解：（1）k=4时,考虑：若到最后一个，第4个工厂投资时，还有资金，若投资于第4个工厂的资金为，则最大利润为,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1利润增长额,（百元）,（注意到此时=0）,自然问：现在还有多少钱？即=？,=0，100，200，300，400，500，600都有可能。,下面分情况讨论：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1利润增长额,（百元）,时，,时，,其他种情况类似讨论，我们把所有的结果汇总成一个表2。,表1利润增长额,（百元）,表2k=4时决策表,表1利润增长额,（百元）,（2）k=3时到第三个工厂投资时，可利用的资金还有，,若向第三个工厂投资（万元），则自此即以后最大利润为：,表1利润增长额,（百元）,同样问：=？，即现在还有多少钱？它是允许决策集上界。,同理,仅举一例：,表1利润增长额,（百元）,表2k=4时决策表,表1利润增长额,（百元）,所有情况讨论结果汇总成下表：,表3k=3时决策表,（3）k=2时,仅举一例：,表1利润增长额,（百元）,表3k=3时决策表,关于的其它取值情况及相应的最优决策列于下表,表4k=2时决策表,（4）k=1时，此时,表1利润增长额,（百元）,表4k=2时决策表,汇一表格：,表5k=1时决策表,此时对应最大值134的有三个值：,所对应的最优策略分别为：,时，由状态转移方程,知：,所对应的,表4k=2时决策表,对应的,再由状态转移方程,对应的,表3k=3时决策表,所对应的,再由状态转移方程,对应的,表2k=4时决策表,对应的,从而得一最优策略,同理还有另外三个最优策略:,所有解总利润最大增长额为,（百元）,加上刚才一组,资源分配问题（连续型）：设备负荷分配问题。,例3:某公司有500辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆，在两种不同的负荷下运输的卡车数量，使在5年内的总利润最大？,解：这是一个以时间为特征的多阶段决策问题。,阶段：将5年运输计划看成5个阶段的决策问题。k=1,2,3,4,5,状态变量：第k阶段初完好卡车数量，其中,决策变量：表示第k阶段分配给超负荷运输的卡车数量。,显然，分配给低负荷的卡车数为,注：这里视，为连续变量。若=0.6表示有一辆卡车在第k年度有60的时间处于完好状态。=0.7表示有一辆卡车在第k年度有70时间在超负荷运输等等。,状态转移方程：,阶段指标函数：表示第k年度利润。,最优指标函数：第k年度初完好车辆数为时，采用最优策略到第5年末所产生的最大利润。,逆序递推式为：,1）k=5时,（注意到此时=0）,此时,2）k=4时,同理，只有当,时，函数,才能达到极大值。故有,3）k=3时,不难得到,4）k=2时,可见，只有当,时，函数,才能达到,极大值。故有,5）k=1时,同理，只有当,时，函数,才能达到,极大值。故有,（万元）,所对应的最优策略分别为：,时，由状态转移方程,由,得,再由,得,第一年初：500辆车全部用于低负荷运输。第二年初：还有450辆完好的车，也全部用于低负荷运输。第三年初：还有405辆完好的车，全部用于超负荷运输。第四年初：还有238.5辆完好的车，全部用于超负荷运输。第五年初：还有198.45辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余138.15辆完好的车。,实现最大利润,（亿元）,思考：某公司有1000辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆在两种不同的负荷下运输的卡车数量，使在第5年年末剩余的完好卡车数量为500台，并且使在5年内的总利润最大？,第1年,第2年,第3年,第4年,投x1辆超负荷车,状态,状态,状态,投x2辆超负荷车,投x3辆超负荷车,投x4辆超负荷车,第5年,投x4辆超负荷车,状态,状态,第1年,第2年,第3年,第4年,投x1辆超负荷车,状态,状态,状态,投x2辆超负荷车,投x3辆超负荷车,投x4辆超负荷车,第5年,投x4辆超负荷车,状态,状态,逆序递推式为：,第1年,第2年,第3年,第4年,投x1辆超负荷车,状态,状态,状态,投x2辆超负荷车,投x3辆超负荷车,投x4辆超负荷车,第5年,投x4辆超负荷车,状态,状态,1）k=5时,（注意到此时=0）,第5节背包问题,一般的提法为：一旅行者携带背包去登山。已知他所能承受的背包重量的极限为a(千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为(千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量的函数（i=1，2，n）.问旅行者应如何选择携带物品的件数，以使总价值最大？,此模型解决的是运输工具包括卫星的最优装载问题。,其数学模型为：,设为第i种物品装入的件数，则背包问题可归结为如下,形式的整数规划模型：,下面从一个例子来分析动态规划建模。,例4有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表7-4所示。,应如何装载可使总价值最大？,表7-4,设第种货物装载的件数为,则问题可表为：,阶段k:将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分3个阶段，即k=1,2,3.,状态变量：在第k段开始时，背包中允许装入前k种物品的总重量。,决策变量：装入第k种物品的件数。,状态转移方程：,最优指标函数：在背包中允许装入物品的总重量不超过kg时，采取最优策略只装前k种物品时的最大使用价值,由此可得动态规划的顺序递推方程为：,货物1,货物2,货物3,K=1时,货物1,货物2,货物3,K=1时,注意到：,例如：,时，,其它计算结果见表7-5：,表7-5,货物1,货物2,货物3,K=2时,其中,例如：,时，,表7-5,其它计算结果见表7-6：,表7-6,货物1,货物2,货物3,K=3时,表7-6,从,再由状态转移方程,表7-6,货物1,货物2,货物3,再由状态转移方程,表7-5,最大装载价值为,总结：今后解背包问题应先从k=3入手：,k=3时,下面应有重点地从k=2中求解三个最优函数值：,K=2时,所以从第一阶段应有重点地求以下四个数：,K=1时,由此逐一逆推代回上式：,由此逐一逆推代回上式：,由此逐一逆推代回上式：,最后,最优策略：,再由状态转移方程,再由状态转移方程,最大装载价值为,思考：用动态规划方法求解：,解：我们用背包问题顺序解的思路：人为的划分三个阶段：k=1,2,3阶段指标函数及其他分配情况如下图：,1,2,3,动态规划的顺序递推方程为：,1,2,3,1,2,3,最优决策为,所对应的最优解为,例（二维背包）有一辆最大货运量为13t、最大容量为10件的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？,解：设装载第i种货物的件数为（i=1,2,3），则问题可表述为,1,2,3,关于件数的约束:,关于重量的约束:,基本方程式：,1,2,3,问题就是求：,1,2,3,1,2,3,同理可求得,所以最优决策方案为：,最优装载价值为：,例5货郎担问题,货郎担问题也叫推销商问题（travelingsalesmanproblem）,其一般提法为：有n个城市，用1，2，n表示，城i,j之间的距离为，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短？,1,2,3,6,4,5,7,8,9,10,11,12,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,一。动态规划解,阶段变量k：按所经过的城市个数划分阶段k,k=1,2,n-1.,状态变量：设第k阶段到达城市i时途中所经过的k个城市,集合为S，则,其中,1,2,3,6,4,5,7,8,9,10,11,12,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,例如：，表示推销商从城1出发途径城市2,3,4到达城市5时，须先途经城市2,4到达城市3，再奔城市5。,决策变量：第k阶段到达城市i的最短路线上邻接i的前一,个城市。,1,2,3,6,4,5,7,8,9,10,11,12,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,阶段指标函数:设从城市1出发，第k-1阶段到达到城市j,则城市j与下一阶段（第k阶段）的目的地城市i之间的距离为,最优指标函数：从城市1出发，经过S中k个城市,到,达城市i的最短距离.,1,2,3,6,4,5,7,8,9,10,11,12,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,则动态规划的顺序递推关系为:,最后算出,即为全程的最短距离,同时可得最优策略,即最优行走路线.,例1已知4个城市间距离如表1，求从城市1出发，经其他城市一次且仅一次最终回到城市1的最短路与距离。,解：由边界条件知：,当k=1时，从城市1出发，经过1个城市到达城市i的最短距离为：,即从城市1出发，途经1个城市奔城2，应先到4，再到2。,即从城市1出发，途经1个城市奔城3，应先到4，再到3。,即从城市1出发，途经1个城市奔城4，应先到2，再到4。,当k=2时，从城市1出发，途经2个城市到达城市i的最短距离为,即从城市1出发，途经2个城市3，4奔城2，应先到4，再到2。,即从城市1出发，途经2个城市2，4奔城3，应先到4，再到3。,即从城市1出发，途经2个城市2，3奔城4，应先到2，再到4。,当k=3时，从城市1出发，途经3个城市到达城市1的最短距离,货郎担的最短路线是12431。,逆推回去,行走距离为23。,第七讲：设备更新问题企业中经常会遇到一台设备应该使用多少年更新最合算的问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费