资源描述：
《第七章 运筹学 动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章动态规划多阶段的决策问题最优化原理与动态规划基本方程离散确定型动态规划模型的求解连续确定型动态规划模型的求解一般数学规划模型的动态规划求解法背包问题教学目的与要求:使学生学会利用多阶段问题的决策思想处理一些简单的实际问题,并会用WinQSB求解动态规划.重点与难点:重点是离散型资源分配问题;难点是动态规划建模和求解方法.教学方法:从多阶段最短路引入基本概念和数学模型,再讲解离散型DP和连续型DP.思考题,讨论题,作业:本章习题.参考资料:见前言.学时分配:6学时.前言:动态规划是最优化的一个分支,它是解决多阶段决策过程最优化的一种方法.
2、动态规划的创始人是美国数学家贝尔曼(R.Bellman).它在四十年代后期和五十年代初期在美国兰德公司工作,针对一些多阶段决策问题提出了解决这类问题的最优化原理,并在1957年出版了动态规划的第一本书《Dynamicprogramming》.在企业管理方面,动态规划可以解决库存问题,资源分配问题,设备更新问题,运输问题,生产过程最优控制问题.它的弱点是,根据最优化原理建立的动态规划基本方程,尚无统一的解法,而要根据其数学结构灵活处理;此外,变量个数不能太多,否则计算量太大,这称为维数问题.第一节多阶段决策问题及实例所谓多阶段决策问题,是指一个
3、大问题可以划分为若干个阶段,每个阶段形成一个子问题,各个阶段是互相联系的,每个阶段都要作出决策,并且一个阶段的决策确定以后会影响下一阶段的决策,从而影响整个过程的活动路线.各个阶段所确定的决策构成一个决策序列,称为一个策略,对于不同的策略其效果不同(效果可以用数量来衡量).多阶段决策问题就是选择一个最优策略,使在给定的标准下达到最好的效果.典型例题:例1多阶段网络的最短路2511214106104131112396581052C1C3D1AB1B3B2D2EC2状态1状态2状态3状态4终点例题特点:⒈阶段:如图的阶段,分为四段;⒉状态:顶点;
4、⒊决策:选弧;⒋转移:从一个顶点走到另一个顶点;⒌目标:路长最短.例2资源分配问题设有数量x的某种资源,将它投入两种生产A,B.若以y投入生产A,剩下的x-y投入生产B,则收入函数为g(y)+h(x-y),如果生产后可以回收再生产,其回收率分别为0≤a,b≤1,则在第一阶段生产后回收的总资源为再将投入生产A,B,若以分别投入生产A,B则又可得收入因此两阶段的总收入为如果上面的过程进行了n个阶段,而且我们希望选择使n个阶段的总收入最大,问题变为例题特点:⒈阶段:年(月)⒉状态:资金数⒊决策:分配给A的资金数⒋转移:⒌效益:n个阶段的总收入最大第
5、二节最优化原理与动态规划基本方程一.动态规划的基本概念⒈阶段(stage):是指一个问题需要作出决策的步骤,用k表示阶段数,k称为阶段变量.通常以时间作为阶段变量.⒉状态(state):状态表示在任一阶段所处的位置,通常一个阶段有若干个状态,描述过程状态的变量称为状态变量,第k阶段的状态变量用表示.状态变量取值的全体称为状态空间或状态集合.在例1中各阶段的状态变量集合如下:第一阶段状态变量第二阶段状态变量第三阶段状态变量第四阶段状态变量终点E注意:状态变量是动态规划中最关键的一个参数,它既反映前面各阶段决策的结局,又是本阶段作出决策的出发点,
6、状态是动态规划问题各阶段信息的传递点和结合点.⒊决策(decision):决策是指某阶段状态给定后,从该阶段演变到下一阶段某状态的选择.决策变量表示第k阶段状态为时对方案的选择.表示k阶段状态为时决策允许的取值集合.例如:例1中⒋策略(policy)和子策略(subpolicy):动态规划问题各阶段决策组成的序列总体称为一个策略.是n个阶段DP的一个策略.⒌状态转移律:从的某一状态值出发,当决策变量的取值决定后,下一阶段状态变量的取值也随之确定.这种从上一阶段的某一状态值到下一阶段某一状态值的转移规律称为状态转变移律.可表示为⒍指标函数(in
7、dexfunction):指标函数是用来衡量实现过程优劣的一种数量指标.它是从状态出发至过程最终,当采取某种策略时,按预定标准得到的效益值,这个值既与有关,又与以后所选取的策略有关,它是两者的函数,称为过程指标函数,记为特别地,仅第k阶段的指标函数,可记为最优指标函数:是指对某一确定状态选取最优策略后得到的指标函数值,也就是对应某一最优子策略的某种效益度量,这个度量值可以是成本,产量,距离等等.对应于从状态出发的最优子策略的效益值记为其中optimization是最优化的意思,在具体问题中,可以是最小化(min)也可以是最大化(max).二.
8、最优化原理与动态规划基本方程贝尔曼(R.Bellman)最优化原理:作为整个过程的最优策略具有这样的性质,无论过去的状态和决策如何,对先前决策所形成的状态而言,余下
