《运筹学期末复习》PPT课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《《运筹学期末复习》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《运筹学期末复习》PPT课件.ppt(159页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1运筹学总复习运筹学总复习2第八章第八章排队论排队论3s 系统中系统中并联服务台的数目并联服务台的数目;平均到达率平均到达率(单位时间到达的顾客数);(单位时间到达的顾客数);1/平均到达间隔平均到达间隔(相继到达顾客的平均间隔(相继到达顾客的平均间隔时间)。时间)。平均服务率平均服务率(单位时间服务的顾客数);(单位时间服务的顾客数);1/平均服务时间平均服务时间(为顾客服务的平均时间)。(为顾客服务的平均时间)。服务强度服务强度,即每个服务台单位时间内的,即每个服务台单位时间内的平均服务时间;平均服务时间;一般有一般有 s ;稳态排队系统的参数稳态排队系统的参数4 Pn=PN=n:稳稳态态
2、系系统统任任一一时时刻刻状状态态为为n(系统中(系统中恰好有恰好有n个顾客个顾客)的概率;)的概率;特特别别当当n=0时时,Pn即即P0,为为稳稳态态系系统统所有服务台全部空闲的概率。所有服务台全部空闲的概率。稳态下系统的基本数量指标稳态下系统的基本数量指标5到到达达的的顾顾客客不不一一定定全全部部进进入入系系统统接接受受服服务务,设设系系统统中中有有n个个顾顾客客时时,每每单单位位时时间间进进入入系系统统的的顾顾客客平平均均数数为为 n,每每单单位位时时间间离离开开系系统统的的顾顾客平均数为客平均数为 n。我们引入:。我们引入:e 有有效效平平均均到到达达率率,即即每每单单位位时时间间实实际
3、际进进入入系系统统的的平平均均顾顾客客数数(期期望值),望值),e=npn对等待制的排队系统,有对等待制的排队系统,有 e 6平均有效离去率平均有效离去率:e=n pn 从平稳系统中均值的意义看,容易理解从平稳系统中均值的意义看,容易理解应有应有平均有效离去率等于平均有效平均有效离去率等于平均有效到达率到达率,即,即 e=e7L,Lq,e,W,Wq 之间的关系:之间的关系:L=eW,Lq=e Wq几何解释:稳态时,一个顾客,进入系几何解释:稳态时,一个顾客,进入系统后,每单位时间平均到达统后,每单位时间平均到达 e e顾客。顾客。eeeee进入时刻进入时刻离开时刻离开时刻总时间总时间W队长队长
4、L由时间段内由时间段内W个个 e组成的组成的L=eW5)Little公式公式8同理:同理:Lq=eWq又又W=Wq+(1/)-W与与Wq只相差一段平均服务时间只相差一段平均服务时间1/L=Lq+(e/)5)Little公式公式以上公式对一般泊松输入以上公式对一般泊松输入指数排指数排队模型成立。队模型成立。9对于平均队长和平均队列长,可用下列公对于平均队长和平均队列长,可用下列公式计算式计算 因此,只要知道因此,只要知道 ,则,则 或或 就可由以上两公式求得,从而再由上面四就可由以上两公式求得,从而再由上面四公式就能求得四项主要工作指标。公式就能求得四项主要工作指标。10排队论求解的主要数量指标
5、排队论求解的主要数量指标P0、Pn、L、Lq、W、Wq11单服务台无限源系统单服务台无限源系统M/M/1/FCFSM/M/1/N/FCFS12M/M/1/FCFS系统系统:参数参数,问题的一般提法:泊松输入泊松输入/负指数分布负指数分布/单服务台单服务台/系统无系统无限制限制/顾客源无限制顾客源无限制求解:(1)系统状态系统状态P0、Pn (2)系统运行指标:系统运行指标:L、Lq、W、Wq13M/M/1/FCFS排队系统模型的主要指标排队系统模型的主要指标1、系统中无顾客的概率:、系统中无顾客的概率:P0=1 2、系统中有、系统中有n个顾客的概率:个顾客的概率:Pn=n.(1)3、系统中的平
6、均顾客数:、系统中的平均顾客数:L=/(1)4、顾客在系统中的平均逗留时间:、顾客在系统中的平均逗留时间:W=L/5、顾客花在排队上的平均等待时间:、顾客花在排队上的平均等待时间:Wq=W-1/u6、平均排队的顾客数:、平均排队的顾客数:Lq=Wq141 1、例子例子 P216P216 某医院急诊室同时只能诊治某医院急诊室同时只能诊治1 1个病人,个病人,诊治时间服从指数分布,每个病人平均需诊治时间服从指数分布,每个病人平均需要要1515分钟。病人按泊松分布到达,平均每分钟。病人按泊松分布到达,平均每小时到达小时到达3 3人。求该排队系统的主要数量指人。求该排队系统的主要数量指标。标。15由题
7、意知:该题是由题意知:该题是M/M/1/FCFS排队系统排队系统(人小人小时时),60154(人小人小时时)故服务强度为故服务强度为其中,其中,p0是急是急诊诊室空室空闲闲的概率,也是病人不必的概率,也是病人不必等待立即就能就等待立即就能就诊诊的概率。的概率。16此模型的平均有效到达率,即是到达率此模型的平均有效到达率,即是到达率 病人在急病人在急诊诊室内外平均逗留室内外平均逗留时间时间:病人平均等候病人平均等候时间时间:(小小时时)45(分分钟钟)急诊室内外的病人平均数:急诊室内外的病人平均数:(人)(人)(小时)(小时)急急诊诊室外排室外排队队等待的病人平均数:等待的病人平均数:(人人)1
8、72、某医院手术室只能同时诊治一个病人,病某医院手术室只能同时诊治一个病人,病人到达服从泊松分布,每小时病人平均到达率人到达服从泊松分布,每小时病人平均到达率为为2.1(人人/小时小时)。每次手术平均时间。每次手术平均时间0.4(小时小时/人人),服从负指数分布求:,服从负指数分布求:(1)病房中病人的平均数病房中病人的平均数(L);(2)排队等待手术病人的平均数排队等待手术病人的平均数(Lq);(3)病人在病房中平均逗留时间病人在病房中平均逗留时间(W)(4)病人排队等待时间病人排队等待时间(Wq)。18193、某医院急诊室每小时到达一个病人,输入为最简某医院急诊室每小时到达一个病人,输入为
9、最简单流,急诊室仅有一名医生,病人接受紧急护理平单流,急诊室仅有一名医生,病人接受紧急护理平均需均需20分钟,服务时间为负指数分布,试求:分钟,服务时间为负指数分布,试求:(1)稳态情况下:稳态情况下:a)没有病人的概率;没有病人的概率;b)有两个有两个病人的概率;病人的概率;c)急诊室里病人的平均数;急诊室里病人的平均数;d)排队中病排队中病人的平均数;人的平均数;e)病人在急诊室中的平均时间病人在急诊室中的平均时间(2)为了保证病人急诊所花费的平均时间少于)为了保证病人急诊所花费的平均时间少于25分钟,那么平均紧急护理时间必须降至多少分钟分钟,那么平均紧急护理时间必须降至多少分钟?2021
10、22第七章第七章 动态规划动态规划23动态规划的基本概念动态规划的基本概念1 1)阶段和阶段变量阶段和阶段变量 阶阶段段是是按按决决策策进进行行的的时时间间或或空空间间上上先先后后顺顺序序划划分分的的。用用以以描描述述阶阶段段的的变变量量叫叫作作阶阶段段变变量量,一一般般以以k表表示示阶阶段段变变量量阶阶段段数数等等于于多多阶阶段段决决策策过过程程从从开开始始到到结结束所需作出决策的数目。束所需作出决策的数目。242 2)状态、状态变量和可能状态集状态、状态变量和可能状态集 描描述述事事物物(或或系系统统)在在某某特特定定的的时时间间与与空空间间域域中中所所处处位位置置及及运运动动特特征征的的
11、量量,称称为为状状态态。反反映映状状态态变变化化的量叫做的量叫做状态变量状态变量。25 每每个个阶阶段段的的状状态态可可分分为为初初始始状状态态和和终终止止状状态态,或或称称输输入入状状态态和和输输出出状状态态,阶阶段段k的的初初始始状状态态记记作作sk,终终止止状状态态记记为为sk+1。通通常常定义阶段的状态即指其初始状态定义阶段的状态即指其初始状态。26 一一般般状状态态变变量量的的取取值值有有一一定定的的范范围围或或允允许许集集合合,称称为为可可能能状状态态集集,可可能能状状态态集集用用相相应应阶阶段段状状态态sk的的大大写写字字母母Sk表表示示,sk Sk,可可能能状状态态集集可可以以
12、是是一一离离散散取取值值的的集集合合,也也可可以以为为一一连连续续的的取值区间,视具体问题而定取值区间,视具体问题而定273)决策、决策变量和允许决策集合决策、决策变量和允许决策集合 决决策策的的实实质质是是关关于于状状态态的的选选择择,是是决决策策者者从从给给定定阶阶段段状状态态出出发发对对下下一阶段状态作出的选择。一阶段状态作出的选择。28 用以描述决策变化的量称之用以描述决策变化的量称之决策决策变量变量。决策变量的值可以用数,向。决策变量的值可以用数,向量、其它量,也可以是状态变量的量、其它量,也可以是状态变量的函数函数.记记uk=uk(sk),表示于阶段,表示于阶段k 状态为状态为sk
13、 时的决策变量。时的决策变量。29 决决策策变变量量的的取取值值往往往往也也有有一一定定的的允允许许范范围围,称称之之允允许许决决策策集集合合。决决策策变量变量uk(sk)的允许决策集用的允许决策集用Uk(sk)表示表示,uk(sk)Uk(sk)允允许许决决策策集集合合实实际际是是决决策策的的约约束束条条件。件。304)策略和允许策略集合策略和允许策略集合策策略略(Policy)也也叫叫决决策策序序列列策策略略有有全全过过程程策策略略和和k部部子子策策略略之之分分,全全过过程程策策略略是是指指由由依依次次进进行行的的n个个阶阶段段决决策策构构成成的的决决策策序序列列,简简称称策策略略,表表示为
14、示为p1,nu1,u2,un。31 从从k 阶阶段段到到第第n 阶阶段段,依依次次进进行行的的阶阶段段决决策策构构成成的的决决策策序序列列称称为为k 部部子子策策略略,表表示示为为pk,nuk,uk+1,un,显显然然当当k=1时时的的k 部部子子策策略略就就是是全全过程策略过程策略。32 在实际问题中,由于在各个阶在实际问题中,由于在各个阶段可供选择的决策有许多个,因此,段可供选择的决策有许多个,因此,它们的不同组合就构成了许多可供选它们的不同组合就构成了许多可供选择的决策序列择的决策序列(策略策略),由它们组成的,由它们组成的集合,称之集合,称之允许策略集合允许策略集合,记作,记作P1,n
15、,从允许策略集中,找出具有最优效,从允许策略集中,找出具有最优效果的策略称为果的策略称为最优策略最优策略。335)状态转移方程状态转移方程 系系统统在在阶阶段段k处处于于状状态态sk,执执行行决决策策uk(sk)的的结结果果是是系系统统状状态态的的转转移移,即即系系统统由由阶阶段段k的的初初始始状状态态sk转转移移到到终止状态终止状态sk+1。34 系系统统状状态态的的这这种种转转移移,用用数数学学公式描述即有:公式描述即有:通通常常称称上上式式为为多多阶阶段段决决策策过过程程的的状状态态转转移移方方程程。有有些些问问题题的的状状态态转转移移方方程程不不一一定定存存在在数数学学表表达达式式,但
16、但是是它它们们的的状状态态转转移移,还是有一定规律可循的。还是有一定规律可循的。356)6)指标函数指标函数 用用来来衡衡量量策策略略或或子子策策略略或或决决策策的的效效果果的的某某种种数数量量指指标标,就就称称为为指指标标函函数数。它它是是定定义义在在全全过过程程或或各各子子过过程程或或各各阶阶段段上上的的确确定定数数量量函函数数。对对不不同同问问题题,指指标标函函数数可可以以是是诸诸如如费费用用、成成本本、产产值值、利利润润、产产量量、耗耗量量、距距离离、时时间间、效效用等等。用等等。36阶段指标函数(阶段效应)阶段指标函数(阶段效应)用用gk(sk,uk)表表示示第第k段段处处于于sk状
17、状态态且且所所作作决决策策为为uk(sk)时时的的指指标标,则则它就是第它就是第k段指标函数,简记为段指标函数,简记为gk37过程指标函数(目标函数)过程指标函数(目标函数)用用Rk(sk,uk)表表示示k子子过过程程的的指指标标函函数数。Rk(sk,uk)不不仅仅跟跟当当前前状状态态sk有有关关,还还跟跟该该子子过过程程策策略略pk(sk)有有关关,因因此此它它是是sk和和pk(sk)的的函函数数,严严格格说说来来,应表示为,应表示为:387)最优解最优解用用 fk(sk)表表 示示 第第 k子子 过过 程程 指指 标标 函函 数数,在状态,在状态sk下的最优值下的最优值,即即称称fk(sk
18、)为为第第k子子过过程程上上的的最最优优指指标函数;标函数;39相相应应的的子子策策略略称称为为sk状状态态下下的的最最优优子子策策略略,记记为为pk*(sk);而而构构成成该该子子策策赂赂的的各各段段决决策策称为该过程上的称为该过程上的最优决策最优决策,记为,记为有有 简记为简记为40特别,特别,当当k=1且且s1取值唯一时,取值唯一时,f1(s1)就是问题的最优值,而就是问题的最优值,而p1*就是最就是最优策略。优策略。41 最最优优策策略略即即为为s1=s1*状状态态下下的的最最优优策略:策略:我我们们把把最最优优策策略略和和最最优优值值统统称称为为问问题的最优解。题的最优解。428)8
19、)多阶段决策问题的数学模型多阶段决策问题的数学模型 适适于于动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决决策策问问题题,即即具具有有无无后后效效性性的的多多阶阶段段决决策策问问题题的的数数学模型学模型:43常用求最小的加法计算公式常用求最小的加法计算公式:(边界条件)(边界条件)阶段指标阶段指标44动态规划方法的基本步骤动态规划方法的基本步骤用用函函数数基基本本方方程程逆逆推推求求解解是是常常用用的的方方法法:首首先先要要有有效效地地建建立立动动态态规规划划模模型型,然然后后再再递递推推求求解解基基本本方方程程,最最后后回溯求得最优策略回溯求得最优策略。合合理理、有有效效地地建建
20、立立一一个个动动态态规规划划模模型型,是解决问题的关键。是解决问题的关键。45(一)动态规划建模要点(一)动态规划建模要点 将将实实际际问问题题恰恰当当地地分分割割成成n个个子子问题问题(n个阶段个阶段)通通常常是是根根据据时时间间或或空空间间而而划划分分,或或者者在在经经由由静静态态的的数数学学规规划划模模型型转转换换为为动动态态规规划划模模型型时时,常常取取静静态态规规划划中变量的个数中变量的个数n。46动态规划建模要点动态规划建模要点 正确地定义状态变量正确地定义状态变量sk,使它既能正确,使它既能正确地描述过程的状态,又能满足无后效性地描述过程的状态,又能满足无后效性。在动态规划模型中
21、,一般状态变量要选在动态规划模型中,一般状态变量要选取那种取那种可以进行累计的量可以进行累计的量。47动态规划建模要点动态规划建模要点 正正确确地地定定义义决决策策变变量量及及各各阶阶段段的的允许决策集合允许决策集合Uk(sk)。一一般般将将问问题题中中待待求求的的量量选选作作动动态态规划模型中的决策变量。规划模型中的决策变量。48动态规划建模要点动态规划建模要点 正确地写出状态转移方程正确地写出状态转移方程 要要能能正正确确反反映映状状态态转转移移规规律律。如如果果给给定定第第k阶阶段段状状态态变变量量sk 的的值值,则则该该段段的的决决策策变变量量uk 一一经经确确定定,第第k+1段段的的
22、状状态态变变量量sk+1的的值值也也就就完完全全确定,即有确定,即有 sk+1=Tk(sk,uk)49动态规划建模要点动态规划建模要点 正确地写出目标函数正确地写出目标函数 目目标标函函数数由由递递推推关关系系构构成成,因因此此,它应满足下列性质:它应满足下列性质:函数可分性:函数可分性:阶段指标相对独立阶段指标相对独立;要满足递推关系;要满足递推关系;过程函数严格单调。过程函数严格单调。50动态规划基本方程动态规划基本方程fn+1(sn+1)=0(边界条件边界条件)fk(sk)=optugk(sk,uk)+fk+1(sk+1)k=n,n-1,151(二)逆序求解动态规划基本方程(二)逆序求解
23、动态规划基本方程 常见三种情况:一种是对于常见三种情况:一种是对于特殊的网络求最优特殊的网络求最优路径路径,可以直接在网络图上,直观地使用,可以直接在网络图上,直观地使用标号标号法法(见下一节)求解;(见下一节)求解;对于对于离散型离散型的动态规划问题,常使用的动态规划问题,常使用列表格列表格(递推方程)(递推方程)的方法求解。的方法求解。当阶段指标与递推公式可表示为解析显函数时,当阶段指标与递推公式可表示为解析显函数时,对于规模较大,特别是对于规模较大,特别是连续型连续型的动态规划问题,的动态规划问题,常直接常直接使用函数求优使用函数求优的方法。的方法。52(三)回溯求得最优策略(三)回溯求
24、得最优策略 从从k=1k=1开始,逐步向后归纳出开始,逐步向后归纳出前一环节各步所选择的决策,得到前一环节各步所选择的决策,得到决策序列,即最优策略。决策序列,即最优策略。531 1、例子例子 P176P176用用递推方程递推方程求解最短路径问题求解最短路径问题54(一)建模(一)建模如图划分成如图划分成5个阶段;个阶段;状态变量状态变量sk表示第表示第k阶段开始的位置;阶段开始的位置;决决策策变变量量uk定定义义为为到到达达下下一一站站所所选选择择的的路路径;径;状态转移:决策确定了下一阶段的状态;状态转移:决策确定了下一阶段的状态;阶段指标:图中线段上所标的数值;阶段指标:图中线段上所标的
25、数值;55最优指标函数最优指标函数fk(sk):表示从目前状态到表示从目前状态到E的最短路径。的最短路径。终端条件为终端条件为f5(s5)=f5(E)=0其其含含义义是是从从E到到E的的最最短短路路径径为为0。56(二)逆推求解(二)逆推求解第第4阶段的递推方程为阶段的递推方程为从从f5(s5)到到f4(s4)的递推过程用下表表示的递推过程用下表表示 s4U4(s4)s5g4(s4,u4)g4(s4,u4)+f5(s5)f4(s4)最最优优决策决策u4*C1C1EE55+0=5*5C1EC2C2EE88+0=8*8C2E57第第3阶段的递推方程为:阶段的递推方程为:从从f4(s4)到到f3(s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学期末复习 运筹学 期末 复习 PPT 课件
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内