运筹学.pptx
《运筹学.pptx》由会员分享,可在线阅读,更多相关《运筹学.pptx(89页珍藏版)》请在咨信网上搜索。
1、本章内容|多阶段决策过程的最优化|动态规划的基本概念和基本原理|动态规划模型的建立与求解|动态规划在经济管理中的应用|马氏决策规划简介美国数学家贝尔曼(Richard.Bellman)创始时间上个世纪50年代创始人|是运筹学的一个主要分支|是解决多阶段决策过程的最优化的一种方法多阶段决策过程:资源分配问题生产计划与库存问题投资问题装载问题排序问题生产过程的最优控制等多阶段决策过程的最优化的目标:达到整个活动过程的总体效果最优主要用于解决:最优路径问题动态规划模型分类离散确定型离散随机型连续确定型连续随机型多阶段决策问题(Multi-Stage decision process)状态 x1阶段1
2、T1决策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+11 1多多阶段阶段决策决策过程过程的最的最优化优化1.多阶段决策过程的最优化 动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。1 1多多阶段阶段决策决策过程过程的最的最优化优化2.多阶段决策问题举例 属于多阶段决策类的问题很多,例如:1)1)工厂生产过程工厂生
3、产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。1 1多多阶段阶段决策决策过程过程的最的最优化优化|例1:某厂与用户签订了如表所示的交货合同,表中数字为月底的交货量。该厂的生产能力为每月400件,该厂仓库的存货能力为300件。已知每百件货物的生产费用为10000元。在进行生产的月份,工厂还要支付经常费4000元。仓库保管费为每百件货物每月1000元。假设开始时及6月底交货后无存货。月份123456交货量(百件)1253211 1多多阶段阶段决策决策过程过程的最的最优化优化 2)2)设设备备
4、更更新新问问题题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费因此就需要综合权衡决定设备的使用年限,使总的经济效益最好。例2:下表给出了某单位的预测数据,现决定考虑到1998年(n=5),试作5年内的设备更新计划1 1多多阶段阶段决策决策过程过程的最的最优化优化产品年代机龄收入额维护费新设备购置费旧设备折价19931234518161614148899105020151052
5、1994012342221201816668810503025201510199501232725242256895231262115199601229262455652332820199701302845553530199803246040 3)3)连连续续生生产产过过程程的的控控制制问问题题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。1 1多多阶段阶段决策决策过程过程的最的最优化优化 以上所举问题的发展过程都与时间因素有关,因此在这类多阶段决策问题中,阶
6、段的划分常取时间区段来表示,并且各个阶段上的决策往往也与时间因素有关,这就使它具有了“动态”的含义,所以把处理这类动态问题的方法称为动态规划方法。不过,实际中尚有许多不包含时间因素的一类“静态”决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题,应用动态规划方法加以解决。1 1多多阶段阶段决策决策过程过程的最的最优化优化 4 4)资资源源分分配配问问题题:便属于这类静态问题。如:某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决
7、策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题(后后面面我我们们将将详细讨论这个问题详细讨论这个问题)。1 1多多阶段阶段决策决策过程过程的最的最优化优化|例3:某工厂生产A、B、C三种产品,都使用某种原材料,现有原材料4吨。江不同数量的这种原料分配给各种产品时产生的收益如表所示,试确定使总收益最大的分配法。ABC01230101720061718081111 5 5)运运输输网网络络问问题题:如图7-1所示的运输网络,点间连线上的数字表示两地距离(也可是运费、时间等),要求从A至F的最短路线。这种运输网络问题也是静态决策问题。但是,按照网络中点的分布,可
8、以把它分为5个阶段,而作为多阶段决策问题来研究。1 1多多阶段阶段决策决策过程过程的最的最优化优化1 1多多阶段阶段决策决策过程过程的最的最优化优化本章内容|多阶段决策过程的最优化|动态规划的基本概念和基本原理|动态规划模型的建立与求解|动态规划在经济管理中的应用|马氏决策规划简介 一、动态规划的基本概念一、动态规划的基本概念 使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义:2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 (一一)阶段和阶段变量阶段和阶段变量 为了便于求解和
9、表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段。一个阶段,就是需要作出一个决策的子问题,通常,阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量,一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目,图71所示的最短路问题就是一个四阶段决策过程。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 (二二)状状态态、状状态态变变量量和和可可能能状状态态集集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量,称为状态。反映状态变化的量叫做状态变量
10、。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后,每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段k的初始状态记作sk,终止状态记为sk+1。但为了清楚起见,通常定义阶段的状态即指其初始状态。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 2可能状态集 一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示,skSk,可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定在图71所示的最短路问题中,第一阶段
11、状态为A,状态变量s1的状态集合S1=A;第二阶段则有两个状态:B1,B2,状态变量s2的状态集合S2=B1,B2;第三阶段有四个状态:C1,C2,C3,C4状态变量s3的状态集合S3=C1,C2,C3,C4;第四阶段则有三个状态:D1,D,D3,状态变量s4的状态集合S4=C1,C2,C3 ;第五阶段则有两个状态E1,E2状态变量s5的状态集合S5=E1,E2,2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 (三)决策、决策变量和允许决策集合(三)决策、决策变量和允许决策集合 所谓决策,就是确定系统过程发展的方案。决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状
12、态作出的选择。用以描述决策变化的量称之决策变量和状态变量一样,决策变量可以用一个数,一组数或一向量来描述,也可以是状态变量的函数,记以uk=uk(sk),表示于阶段k状态sk时的决策变量。决策变量的取值往往也有一定的允许范围,称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示,uk(sk)Uk(sk)允许决策集合实际是决策的约束条件。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 (四)策略和允许策略集合(四)策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分,全过程策略是指具有n个阶段的全部过程,由依次进行的n个阶段决策 构 成
13、 的 决 策 序 列,简 称 策 略,表 示 为p1,nu1,u2,un。从k阶段到第n阶段,依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,nuk,uk+1,un,显然当k=1时的k部子策略就是全过程策略。在实际问题中,由于在各个阶段可供选择的决策有许多个,因此,它们的不同组合就构成了许多可供选择的决策序列(策略),由它们组成的集合,称之允许策略集合,记作P1,n,从允许策略集中,找出具有最优效果的策略称为最优策略。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 (五)状态转移方程(五)状态转移方程 系统在阶段k处于状态sk,执行决策uk(sk)的结果是系统状态的转移
14、,即系统由阶段k的初始状态sk转移到终止状态sk+1,或者说,系统由k阶段的状态sk转移到了阶段k+1的状态sk+1,多阶段决策过程的发展就是用阶段状态的相继演变来描述的。对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定,与系统过去的状 态 s1,s2,sk-1及 其 决 策 u1(s1),u2(s2)uk-1(sk-1)无关。系统状态的这种转移,用数学公式描述即有:(7-1)2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 通常称式(7-1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式,
15、但是它们的状态转移,还是有一定规律可循的。(六六)指标函数指标函数 用来衡量策略或子策略或决策的效果的某种数量指标,就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题,指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用,等等。例如:图71的指标就是运费。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理(1)阶段指标函数(也称阶段效应)。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标,则它就是第k段指标函数,简记为gk。图7-1的gk值就是从状态sk到状态sk+1的距离。譬如,gk(A,B1)=4,即A到B1的
16、距离为3。(2)过程指标函数(也称目标函数)。用Rk(sk,uk)表示第k子过程的指标函数。如图7-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时,从sk点到终点F的距离。由此可见,Rk(sk,uk)不仅跟当前状态sk有关,还跟该子过程策略pk(sk)有关,因此它是sk和pk(sk)的函数,严格说来,应表示为:2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 不 过 实 际 应 用 中 往 往 表 示 为Rk(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关,过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标,它是由各阶段的阶
17、段指标函数gk(sk,uk)累积形成的,适于用动态规划求解的问题的过程指标函数(即目标函数),必须具有关于阶段指标的可分离形式对于部子过程的指标函数可以表示为:式中,表示某种运算,可以是加、减、乘、除、开方等。(7-2)2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即:(7-3)有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,如:(7-4)总之,具体问题的目标函数表达形式需要视具体问题而定。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 (七七)最优解最优解 用fk(sk)表示第k子过
18、程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数;式中“OPT”表示最优化,视具体问题取max或min。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 最优化原理(贝尔曼最优化原理)作为一个全过程的最优策略具有这样的性质:对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,余下的诸决策必构成一个最优子策略。该原理的具体解释是,若某一全过程最优策略为:则对上述策略中所隐含的任一状态而言,第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中,即为2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 二二.动态规划求解的多
19、阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。因此,问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 例例4 4:为了说明动态规划的基本思想方法和特点,下面以图
20、7-1所示为例讨论的求最短路问题的方法。第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出最优方案。这里从A到F的路程可以分为5个阶段。第一段的走法有两种,第二段的走法有三种,第三四段的走法 各 两 种,第 五 段 走 法 一 种,因 此 共 有2322124条可能的路线,分别算出各条路线的距离,最后进行比较,可知最优路线。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 显然,当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,而且其中包含着许多重复计算 第二种方法即所谓“局部最优路径”法,是说某人从k出发,
21、他并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是AB1C1D1E1F,全程长度是18;显然,这种方法的结果常是错误的2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是,首先将问题划分为5个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程,动态规划方法总是从过程的最后阶段开始考虑,然后逆着实际过程发展的顺序,逐段向前递推计算直至始点。
22、2动动态规态规划的划的基本基本概念概念和基和基本原本原理理 具体说,此问题先从F开始,因为F是终点。再无后继过程,故可以接着考虑第5阶段上所有可能状态E1,E2的最优后续过程。因为从E1,E2到F的路线是唯一的,所以E1,E2的最优决策和最优后继过程就是到F,它们的最短距离分别是4和3。接着考虑阶段4上可能的状态D1,D2,D3 到F的最优决策和最优后继过程在状态D1上,到E1是3,到E2是5,综合考虑后继过程整体最优,取最优决策是到E1,最优后继过程是D1E1F,最短距离是7。同理,状态D2的最优决策是至E2;D3的最优决策是到E1。2动动态规态规划的划的基本基本概念概念和基和基本原本原理理
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 胡运权
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。