运筹学第5章.ppt
《运筹学第5章.ppt》由会员分享,可在线阅读,更多相关《运筹学第5章.ppt(146页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、运筹学课件运筹学课件第五章第五章动态规划动态规划制作:北京理工大学制作:北京理工大学 吴祈宗等吴祈宗等1第五章 动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点2一、多阶段决策问题(Multi-Stage decision process)多阶段决策过程特点多阶段决策过程特点:状态状态 x x1 1阶段阶段1 1T T1 1决策决策u u1 1状态状态 x x2 2决策决策u u2 2阶段阶段2 2T T2 2状态状态 x x3 3.状态状态 x xk k决策决策u uk k阶段阶段k kT Tk k状态状态 x xk k+1+1
2、.状态状态 x xn n决策决策u un n阶段阶段n nTnTn状态状态 x xn n+1+11.1.多阶段决策过程的最优化多阶段决策过程的最优化31.1.多阶段决策过程的最优化多阶段决策过程的最优化 动动态态规规划划方方法法与与“时时间间”关关系系很很密密切切,随随着着时时间间过过程程的的发发展展而而决决定定各各时时段段的的决决策策,产产生生一一个个决决策策序序列列,这这就就是是“动动态态”的的意意思思。然然而而它它也也可可以以处处理理与与时时间间无无关关的的静静态态问问题题,只只要要在在问问题题中中人人为为地地引引入入“时时段段”因因素素,就就可可以以将将其其转转化化为为一一个个多多阶阶
3、段段决决策策问问题题。在本章中将介绍这种处理方法。在本章中将介绍这种处理方法。41.1.多阶段决策过程的最优化多阶段决策过程的最优化 二、多阶段决策问题举例二、多阶段决策问题举例 属属于于多多阶阶段段决决策策类类的的问问题题很很多多,例如:例如:1)1)工工厂厂生生产产过过程程:由由于于市市场场需需求求是是一一随随着着时时间间而而变变化化的的因因素素,因因此此,为为了了取取得得全全年年最最佳佳经经济济效效益益,就就要要在在全全年年的的生生产产过过程程中中,逐逐月月或或者者逐逐季季度度地地根根据据库库存存和和需需求求情情况况决决定生产计划安排。定生产计划安排。51.1.多阶段决策过程的最优化多阶
4、段决策过程的最优化 2)2)设设备备更更新新问问题题:一一般般企企业业用用于于生生产产活活动动的的设设备备,刚刚买买来来时时故故障障少少,经经济济效效益益高高,即即使使进进行行转转让让,处处理理价价值值也也高高,随随着着使使用用年年限限的的增增加加,就就会会逐逐渐渐变变为为故故障障多多,维维修修费费用用增增加加,可可正正常常使使用用的的工工时时减减少少,加加工工质质量量下下降降,经经济济效效益益差差,并并且且,使使用用的的年年限限越越长长、处处理理价价值值也也越越低低,自自然然,如如果果卖卖去去旧旧的的买买新新的的,还还需需要要付付出出更更新新费费因因此此就就需需要要综综合合权权衡衡决决定定设
5、设备备的的使使用用年年限限,使总的经济效益最好。使总的经济效益最好。61.1.多阶段决策过程的最优化多阶段决策过程的最优化 3)3)连连续续生生产产过过程程的的控控制制问问题题:一一般般化化工工生生产产过过程程中中,常常包包含含一一系系列列完完成成生生产产过过程程的的设设备备,前前一一工工序序设设备备的的输输出出则则是是后后一一工工序序设设备备的的输输入入,因因此此,应应该该如如何何根根据据各各工工序序的的运运行行工工况况,控控制制生生产产过过程程中中各各设设备备的的输输入入和和输输出出,以以使总产量最大。使总产量最大。71.1.多阶段决策过程的最优化多阶段决策过程的最优化许许多多问问题题的的
6、发发展展过过程程都都与与时时间间因因素素有有关关。在在这这类类多多阶阶段段决决策策问问题题中中,阶阶段段的的划划分分常常取取时时间间区区段段来来表表示示,并并且且各各个个阶阶段段上上的的决决策策往往往往也也与与时时间间因因素素有有关关。这这就就使使它它具具有有了了“动动态态”的的含含义义,所所以以把把处处理理这类动态问题的方法称为动态规划方法。这类动态问题的方法称为动态规划方法。实实际际中中尚尚有有许许多多不不包包含含时时间间因因素素的的一一类类“静静态态”决决策策问问题题,就就其其本本质质而而言言是是一一次次决决策策问问题题,是是非非动动态态决决策策问问题题,但但是是也也可可以以人人为为地地
7、引引入入阶阶段段的的概概念念当当作作多多阶阶段段决决策策问问题题,应应用用动动态态规规划划方方法法加加以以解解决。决。81.1.多阶段决策过程的最优化多阶段决策过程的最优化 4 4)资资源源分分配配问问题题:资资源源分分配配问问题题便便属属于于这这类类静静态态问问题题。如如:某某工工业业部部门门或或公公司司,拟拟对对其其所所属属企企业业进进行行稀稀缺缺资资源源分分配配,为为此此需需要要制制定定出出收收益益最最大大的的资资源源分分配配方方案案。这这种种问问题题原原本本要要求求一一次次确确定定出出对对各各企企业业的的资资源源分分配配量量,它它与与时时间间因因素素无无关关,不不属属动动态态决决策策,
8、但但是是,我我们们可可以以人人为为地地规规定定一一个个资资源源分分配配的的阶阶段段和和顺顺序序,从从而而使使其其变变成成一一个个多多阶阶段段决决策策问问题题(后后面面我我们将详细讨论这个问题们将详细讨论这个问题)。91.1.多阶段决策过程的最优化多阶段决策过程的最优化 5)运运输输网网络络问问题题:如如图图5-1所所示示的的运运输输网网络络,点点间间连连线线上上的的数数字字表表示示两两地地距距离离(也也可可是是运运费费、时时间间等等),要要求求从从fk(sk)至至v10的最短路线。的最短路线。这这种种运运输输网网络络问问题题也也是是静静态态决决策策问问题题。但但是是,按按照照网网络络中中点点的
9、的分分布布,可可以以把把它它分分为为4个个阶阶段段,而而作作为为多多阶阶段决策段决策问题来研究。问题来研究。101.1.多阶段决策过程的最优化多阶段决策过程的最优化三三、动动态态规规划划求求解解的的多多阶阶段段决决策策问问题题的的特点特点通通常常多多阶阶段段决决策策过过程程的的发发展展是是通通过过状状态的一系列变换来实现的。态的一系列变换来实现的。一一般般情情况况下下,系系统统在在某某个个阶阶段段的的状状态态转转移移除除与与本本阶阶段段的的状状态态和和决决策策有有关关外外,还还可可能能与与系系统统过过去去经经历历的的状状态态和决策有关。和决策有关。适适合合于于用用动动态态规规划划方方法法求求解
10、解的的只只是是一一类类特特殊殊的的多多阶阶段段决决策策问问题题,即即具具有有“无后效性无后效性”的多阶段决策过程的多阶段决策过程。111.1.多阶段决策过程的最优化多阶段决策过程的最优化w无后效性(又称马尔柯夫性)无后效性(又称马尔柯夫性)是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。121.1.多阶段决策过程的最优化多阶段决策过程的最优化 四、动态规划方法导引四、动态规划方法导引 为了说明动态规划的基本思想方法和特点,下面以图5-1所示为例讨论的求最短路问题的方法 131.1.多阶段决策过程的最优化多阶段决策过程的最优化 图5
11、-11 运输网络图示 返回141.1.多阶段决策过程的最优化多阶段决策过程的最优化w一般有三种思路求解一般有三种思路求解 全全枚枚举举法法或或穷穷举举法法:它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果,再再对对它它们们一一一一进行比较,求出最优方案。进行比较,求出最优方案。可可以以计计算算:从从v v1 1到到v v1010的的路路程程可可以以分分为为4 4个个阶阶段段。第第一一段段走走法法有有3 3种种,第第二二、三三两两段段走走法法各各 有有 2 2种种,第第 四四 段段 走走 法法 仅仅 1 1种种,共共 有有3 32 22 21 11212条
12、条可可能能的的路路线线,分分别别算算出出各各条条路路线线的的距距离离,最最后后进进行行比比较较,可可知知最最优优路路线线是是v v1 1 v v3 3 v v7 7 v v9 9 v v10 10,最最短短距距离离是是1818用用穷穷举举法法求求最最优优路路线线的的计计算算工工作作量量将将会会十十分庞大,而且其中包含着许多重复计算分庞大,而且其中包含着许多重复计算151.1.多阶段决策过程的最优化多阶段决策过程的最优化 局部最优路径法:某人从k点出发,并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是v1 v3 v5 v8
13、v10,全程长度是20;显然,这种方法的结果常是错误的161.1.多阶段决策过程的最优化多阶段决策过程的最优化 动态规划方法:动态规划方法寻求该最短路问题的基本思想是,首先将问题划分为4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到(如图)171.1.多阶段决策过程的最优化多阶段决策过程的最优化图1 运输网络动态规划方法求解图示跳过过程跳过过程181.1.多阶段决策过程的最优化多阶段决策过程的最优化 具体说,此问题先从v10开始,因为v10是终点。再无后继过程,故可以接着考虑第4阶段上所有可能状态v8,v9的最
14、优后续过程因为从v8,v9 到v10的路线是唯一的,所以v8,v9 的最优决策和最优后继过程就是到v10,它们的最短距离分别是5和3。接着考虑阶段3上可能的状态v5,v6,v7,到v10的最优决策和最优后继过程在状态V5上,虽然到v8是8,到v9是9,但是综合考虑后继过程整体最优,取最优决策是到v9,最优后继过程是v5v9 v10,最短距离是12同理,状态v6的最优决策是至v8;v7的最优决策是到v9。191.1.多阶段决策过程的最优化多阶段决策过程的最优化 同样,当阶段3上所有可能状态的最优后继过程都已求得后,便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程,如v2的最优决策是到v
15、5,最优路线是v2v5v9v10,最短距离是15依此类推,最后可以得到从初始状态v1的最优决策是到v3最优路线是v1v3v7v9v10,全程的最短距离是18。图51中粗实线表示各点到的最优路线,每点上方括号内的数字表示该点到终点的最短路距离。201.1.多阶段决策过程的最优化多阶段决策过程的最优化 小小 结结w全枚举法虽可找出最优方案,但不是个好算法,w局部最优法则完全是个错误方法,w只有动态规划方法属较科学有效的算法21 2.2.动态规划的基本概念动态规划的基本概念 一、动态规划的基本概念一、动态规划的基本概念 使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,同时也为了
16、今后叙述和讨论方便,这里需要对动态规划的下述一些基本术语进一步加以说明和定义:22 2.2.动态规划的基本概念动态规划的基本概念 (一一)阶段和阶段变量阶段和阶段变量 为为了了便便于于求求解解和和表表示示决决策策及及过过程程的的发发展展顺顺序序,而而把把所所给给问问题题恰恰当当地地划划分分为为若若干干个个相相互互联联系系又又有有区区别别的的子子问问题题,称称之之为为多多段段决决策策问问题题的的阶阶段段。通通常常,阶阶段段是是按按决决策策进进行行的的时时间间或或空空间间上上先先后后顺顺序序划划分分的的。用用以以描描述述阶阶段段的的变变量量叫叫作作阶阶段段变变量量,一一般般以以k表表示示阶阶段段变
17、变量量阶阶段段数数等等于于多多段段决决策策过程从开始到结束所需作出决策的数目。过程从开始到结束所需作出决策的数目。232.2.动态规划的基本概念动态规划的基本概念 (二)状态、状态变量和可能状态集(二)状态、状态变量和可能状态集 1.1.状状态态与与状状态态变变量量:描描述述事事物物(或或系系统统)在在某某特特定定的的时时间间与与空空间间域域中中所所处处位位置置及及运运动动特特征征的的量量,称称为为状状态态。反反映映状状态态变变化化的的量量叫叫做做状状态态变变量量。状状态态变变量量包包含含在在给给定定的的阶阶段段上上确确定定全全部部允允许许决决策策所所需需要要的的信信息息。每每个个阶阶段段的的
18、状状态态可可分分为为初初始始状状态态和和终终止止状状态态,或或称称输输入入状状态态和和输输出出状状态态,阶阶段段k的的初初始始状状态态记记作作sk,终终止止状状态态记记为为sk+1。通常定义阶段的状态即指其初始状态。通常定义阶段的状态即指其初始状态。24 2.2.动态规划的基本概念动态规划的基本概念 2 2可能状态集可能状态集 一一般般状状态态变变量量的的取取值值有有一一定定的的范范围围或或允允许许集集合合,称称为为可可能能状状态态集集,或或可可达达状状态态集集。可可能能状状态态集集实实际际上上是是关关于于状状态态的的约约束束条条件件。通通常常可可能能状状态态集集用用相相应应阶阶段段状状态态s
19、 sk k的的大大写写字字母母S Sk k表表示示,s sk k S Sk k,可可能能状状态态集集可可以以是是一一离离散散取取值值的的集集合合,也也可可以以为为一一连连续续的的取取值值区区间,视具体问题而定间,视具体问题而定25 (三三)决决策策、决决策策变变量量和和允允许许决决策策集合集合 决决策策的的实实质质是是关关于于状状态态的的选选择择,是是决决策策者者从从给给定定阶阶段段状状态态出出发发对对下下一一阶阶段状态作出的选择。段状态作出的选择。用用以以描描述述决决策策变变化化的的量量称称之之决决策策变变量量。决决策策变变量量的的值值可可以以用用数数,向向量量、其其它它量量,也也可可以以是
20、是状状态态变变量量的的函函数数,记记以以u uk k=u uk k(s sk k),表表示示于于阶阶段段k k状状态态s sk k时时的的决策变量。决策变量。2.2.动态规划的基本概念动态规划的基本概念262.2.动态规划的基本概念动态规划的基本概念 决决策策变变量量的的取取值值往往往往也也有有一一定定的的允允许许范范围围,称称之之允允许许决决策策集集合合。决决策策变变量量u uk k(s sk k)的的允允许许决决策策集用集用U Uk k(s sk k)表示表示,u uk k(s sk k)U Uk k(s sk k)允允许许决决策策集集合合实实际际是是决决策策的的约束条件。约束条件。27
21、(四)策略和允许策略集合(四)策略和允许策略集合 策策略略(Policy)也也叫叫决决策策序序列列策策略略有有全全过过程程策策略略和和k部部子子策策略略之之分分,全全过过程程策策略略是是指指由由依依次次进进行行的的n个个阶阶段段决决策策构构成成的的决决策策序序列列,简简称称策策略略,表表示示为为p1,nu1,u2,un。从从k阶阶段段到到第第n阶阶段段,依依次次进进行行的的阶阶段段决决策策构构成成的的决决策策 序序 列列 称称 为为 k部部 子子 策策 略略,表表 示示 为为pk,nuk,uk+1,un,显显然然当当k=1时时的的k部子策略就是全过程策略。部子策略就是全过程策略。2.2.动态规
22、划的基本概念动态规划的基本概念28 2.2.动态规划的基本概念动态规划的基本概念w在实际问题中,由于在各个阶在实际问题中,由于在各个阶段可供选择的决策有许多个,段可供选择的决策有许多个,因此,它们的不同组合就构成因此,它们的不同组合就构成了许多可供选择的决策序列了许多可供选择的决策序列(策略策略),由它们组成的集合,由它们组成的集合,称之称之允许策略集合允许策略集合,记作,记作P1,n,从允许策略集中,找出具有从允许策略集中,找出具有最优效果的策略称为最优效果的策略称为最优策略最优策略。29 (五)状态转移方程(五)状态转移方程 系系统统在在阶阶段段k处处于于状状态态sk,执执行行决决策策uk
23、(sk)的的结结果果是是系系统统状状态态的的转转移移,即即系系统统由由阶阶段段k的的初初始状态始状态sk转移到终止状态转移到终止状态sk+1。2.2.动态规划的基本概念动态规划的基本概念302.2.动态规划的基本概念动态规划的基本概念 对对于于具具有有无无后后效效性性的的多多阶阶段段决决策策过过程程,系系统统由由阶阶段段k到到阶阶段段k+1的的状状态态转转移移完完全全由由阶阶段段k的的状状态态sk和和决决策策 uk(sk)所所确确定定,与与系系统统过过去去的的状状态态 s1,s2,sk-1及及其其决决策策u1(s1),u2(s2),uk-1(sk-1)无关无关。31 系系统统状状态态的的这这种
24、种转转移移,用用数数学学公式描述即有:公式描述即有:(5(51)1)通通常常称称上上式式(5-1)(5-1)为为多多阶阶段段决决策策过过程程的的状状态态转转移移方方程程。有有些些问问题题的的状状态态转转移移方方程程不不一一定定存存在在数数学学表表达达式式,但但是是它它们们的的状状态态转转移移,还还是是有有一一定定规规律可循的。律可循的。2.2.动态规划的基本概念动态规划的基本概念32 2.2.动态规划的基本概念动态规划的基本概念 (六六)指标函数指标函数 用用来来衡衡量量策策略略或或子子策策略略或或决决策策的的效效果果的的某某种种数数量量指指标标,就就称称为为指指标标函函数数。它它是是定定义义
25、在在全全过过程程或或各各子子过过程程或或各各阶阶段段上上的的确确定定数数量量函函数数。对对不不同同问问题题,指指标标函函数数可可以以是是诸诸如如费费用用、成成本本、产产值值、利利润润、产产量量、耗耗量量、距距离离、时时间间、效用,等等。效用,等等。33 1)阶段指标函数(阶段效应)阶段指标函数(阶段效应)用用gk(sk,uk)表表示示第第k段段处处于于sk状状态态且且所所作作决决策策为为uk(sk)时时的的指指标标,则则它它就就是是第第k段段指指标标函函数数,简记为简记为gk 2.2.动态规划的基本概念动态规划的基本概念34 (2)(2)过程指标函数(目标函数)过程指标函数(目标函数)用用Rk
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学
限制150内