资源描述
数学建模简明教程国家精品课程国家精品课程第六章第六章 排队论排队论 一、一、问题引入与分析问题引入与分析 二、排队论的基本概念二、排队论的基本概念 三、三、几类排队论模型几类排队论模型 四、模型的建立与求解四、模型的建立与求解 目录下页返回上页结束1.2001年全国数学竞赛的年全国数学竞赛的B题题“公交车调度公交车调度”某条公交线路上行方向共某条公交线路上行方向共1414站，下行方向共站，下行方向共 1313站站.公交公司配给该线路同一型号的大客车，每公交公司配给该线路同一型号的大客车，每辆标准载客辆标准载客100100人，据统计客车在该线路上运行的人，据统计客车在该线路上运行的平均速度为平均速度为2020公里公里/小时小时.运营调度要求，乘客候车运营调度要求，乘客候车时间一般不要超过时间一般不要超过1010分钟，早高峰一般不要超过分钟，早高峰一般不要超过是这样的：是这样的：一、问题引入与分析一、问题引入与分析目录下页返回上页结束5 5分钟，车辆满载率不应超过分钟，车辆满载率不应超过120%120%，一般也不要，一般也不要低于低于50%.试根据这些材料和要求，为该线路设计一个试根据这些材料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案便于操作的全天（工作日）的公交车调度方案包括两个起点站的发车时刻表；一共需要多少包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等公交公司双方的利益；等等.目录下页返回上页结束2.问题分析：问题分析：目录下页返回上页结束对于第一个问题，关于公交车的调度方案，对于第一个问题，关于公交车的调度方案，可以利用各种的不同的方法，比如多目标规划，可以利用各种的不同的方法，比如多目标规划，去求得在一定原则下的最优方案，得到一个满足去求得在一定原则下的最优方案，得到一个满足实际情况的分配方案，但要建立具体的明确、完实际情况的分配方案，但要建立具体的明确、完整的数学模型，以及求解模型的方法，如何采集整的数学模型，以及求解模型的方法，如何采集运营数据是关键的运营数据是关键的.在实际中，公交车具有随机在实际中，公交车具有随机性，特别是顾客的到来是随机的，是无法精确预性，特别是顾客的到来是随机的，是无法精确预目录下页返回上页结束测的，这就决定了公交车的数量并不是完全确定测的，这就决定了公交车的数量并不是完全确定的固定不变的，而是随着不同时段顾客的多少而的固定不变的，而是随着不同时段顾客的多少而变化变化.因此顾客和公交车之间存在随机因素因此顾客和公交车之间存在随机因素.很明显，顾客和公交车是一个服务和被服务很明显，顾客和公交车是一个服务和被服务的关系的关系.如果公交车数量过多，也就是已有的资如果公交车数量过多，也就是已有的资源大于需求，虽然公交车的数量能够满足顾客源大于需求，虽然公交车的数量能够满足顾客需求，减少了顾客排队等待的时间，公交车提供需求，减少了顾客排队等待的时间，公交车提供的服务使顾客的满意度很高，却会造成公交车公的服务使顾客的满意度很高，却会造成公交车公目录下页返回上页结束司的浪费，比如某一时段某一线路所发公交车上没司的浪费，比如某一时段某一线路所发公交车上没有顾客或很少的顾客，个别时段个别线路如此，公有顾客或很少的顾客，个别时段个别线路如此，公交车公司也许可以接受，但长时间的空跑或入不敷交车公司也许可以接受，但长时间的空跑或入不敷出，最终会使公交车公司不堪重负，甚至倒闭；另出，最终会使公交车公司不堪重负，甚至倒闭；另一方面，如果公交车数量较少，很多顾客得不到服一方面，如果公交车数量较少，很多顾客得不到服务，或者很多顾客花了很长的时间去排队等候，造务，或者很多顾客花了很长的时间去排队等候，造成顾客的不满意度提高，这样公交车公司会失去顾客成顾客的不满意度提高，这样公交车公司会失去顾客.如何考虑随机因素，设计合理方案，建立数学模如何考虑随机因素，设计合理方案，建立数学模型，一方面提供服务的服务机构即公交公司的线型，一方面提供服务的服务机构即公交公司的线路设计合理，能够赢得顾客，获得利益；另一方路设计合理，能够赢得顾客，获得利益；另一方面被服务的顾客能够在被服务的过程中，排队等面被服务的顾客能够在被服务的过程中，排队等候的时间最短，这都是上述问题要解决的，也是候的时间最短，这都是上述问题要解决的，也是排队论的主要研究内容排队论的主要研究内容.目录下页返回上页结束二、排队论的基本知识二、排队论的基本知识目录下页返回上页结束2.排队系统描述排队系统描述3.基本组成部分基本组成部分4.数量指标数量指标5.排队模型的记号排队模型的记号1.背景介绍背景介绍1.背景介绍背景介绍 排队论是研究排队现象的理论和应用的学科，是排队论是研究排队现象的理论和应用的学科，是专门研究由于随机因素影响而产生的拥挤现象的科学专门研究由于随机因素影响而产生的拥挤现象的科学.2020世纪初丹麦数学家、电气工程师爱尔朗把概率论应世纪初丹麦数学家、电气工程师爱尔朗把概率论应用于电话通话问题，从而开创了这门应用数学科学用于电话通话问题，从而开创了这门应用数学科学.2020世纪世纪3030年代中期，费勒引进了生灭过程，排队论年代中期，费勒引进了生灭过程，排队论才被数学界承认为一门重要的学科才被数学界承认为一门重要的学科.20.20世纪世纪4040年代排年代排对论在运筹学这个新领域中成了一个重要的部分对论在运筹学这个新领域中成了一个重要的部分.20.20世纪世纪5050年代初肯德尔对排对论作了系统的研究，他用年代初肯德尔对排对论作了系统的研究，他用目录下页返回上页结束马尔科夫链方法研究排队论，使排队论得到进一步发马尔科夫链方法研究排队论，使排队论得到进一步发展展.20.20世纪世纪6060年代起排队论研究的课题日趋复杂，很年代起排队论研究的课题日趋复杂，很多问题很难求得精确解，因此开始了近似方法的研究多问题很难求得精确解，因此开始了近似方法的研究.排队论应用范围很广，它适用于一切服务系统排队论应用范围很广，它适用于一切服务系统.尤尤其在通信系统、交通系统、计算机存储系统和生产管理其在通信系统、交通系统、计算机存储系统和生产管理系统等方面应用的最多系统等方面应用的最多.排队是日常生活和工作中常见的现象排队是日常生活和工作中常见的现象.例如等公共例如等公共汽车排队，到商店购物排队，交款排队，到医院看病汽车排队，到商店购物排队，交款排队，到医院看病目录下页返回上页结束等待排队，买火车票排队，托运行李排队，取货排队，等待排队，买火车票排队，托运行李排队，取货排队，这是人的排队这是人的排队.还有另一种排队，例如文件等待打印或还有另一种排队，例如文件等待打印或发送，报告等首长批示，路口红红灯下的汽车、自行车发送，报告等首长批示，路口红红灯下的汽车、自行车等待通过路口，这是物或设备排队等待通过路口，这是物或设备排队.总之，凡是具有公共服务性质的事业和工作，凡总之，凡是具有公共服务性质的事业和工作，凡是出现拥挤现象的领域，都是排队论的用武之地是出现拥挤现象的领域，都是排队论的用武之地.目录下页返回上页结束2.排队系统描述排队系统描述 排队系统又称为随机服务系统，是研究服务排队系统又称为随机服务系统，是研究服务 请求服务的人或者物请求服务的人或者物顾客；顾客；排队系统的共同特征：排队系统的共同特征：顾客到达系统的时刻是随机的，为每一位顾客顾客到达系统的时刻是随机的，为每一位顾客 有为顾客服务的人或者物，即服务员或服务台；有为顾客服务的人或者物，即服务员或服务台；目录下页返回上页结束过程和拥挤现象的随机模型过程和拥挤现象的随机模型.提供服务的时间是随机的，因而整个排队系统提供服务的时间是随机的，因而整个排队系统的状态也是随机的的状态也是随机的.排队系统的几种形式排队系统的几种形式：目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束基本排队过程基本排队过程：从图从图6666可知，每个顾客由顾客源按一定方式可知，每个顾客由顾客源按一定方式目录下页返回上页结束到达服务系统，首先加入队列排队等待接受服务，到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开务，获得服务的顾客立即离开.排队论所要研究解决的问题：排队论所要研究解决的问题：面对拥挤现象，人们通常的做法是增加服务设施面对拥挤现象，人们通常的做法是增加服务设施但是增加的数量越多，人力、物力的支出就越大，甚但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响待的时间就会很长，这样对顾客会带来不良影响.如如何做到既保证一定的服务质量指标，又使服务设施费何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是随机服务系统理论用大小这对矛盾，就是随机服务系统理论排队论排队论所要研究解决的问题。所要研究解决的问题。目录下页返回上页结束3.排队系统的基本组成部分排队系统的基本组成部分排队系统是由输入过程、排对规则和服务机构组成排队系统是由输入过程、排对规则和服务机构组成.(1).输入过程输入过程 指要求服务的顾客是按怎样的规律指要求服务的顾客是按怎样的规律(i)顾客总体数顾客总体数.又称顾客源、输入源又称顾客源、输入源.这是指顾客这是指顾客(ii)顾客到达方式顾客到达方式.这是描述顾客是怎样来到系这是描述顾客是怎样来到系统统目录下页返回上页结束到达排队系统的过程，有时也把它称为顾客流到达排队系统的过程，有时也把它称为顾客流.一一般可以从般可以从3 3个方面来描述个方面来描述个输入过程个输入过程.的来源的来源.顾客源可以是有限的，也可以是无限的顾客源可以是有限的，也可以是无限的.的，是单个到达，还是成批到达的，是单个到达，还是成批到达.(iii)顾客流的概率分布顾客流的概率分布.或称相继顾客到达的时间或称相继顾客到达的时间(2).排对规则排对规则 指服务台从队列中选取顾客进行指服务台从队列中选取顾客进行(i)损失制损失制 指如果顾客到达排队系统时，所有指如果顾客到达排队系统时，所有目录下页返回上页结束间隔的分布间隔的分布.这是求解排队系统有关运行指标问这是求解排队系统有关运行指标问题题时，首先需要确定的指标时，首先需要确定的指标.顾客流的概率分布一般顾客流的概率分布一般有定长分布、二项分布、泊松流有定长分布、二项分布、泊松流(最简单流最简单流)、爱尔、爱尔朗分布等若干种朗分布等若干种.服务的顺序服务的顺序.一般可以分为损失制、等待制和混一般可以分为损失制、等待制和混合制等合制等3 3大类大类.服务台都被先到的顾客占用，那么他们就自动服务台都被先到的顾客占用，那么他们就自动离开系统永不再来离开系统永不再来.(ii)等待制等待制 指当顾客来到系统时，所有服务台指当顾客来到系统时，所有服务台a.先到先服务先到先服务 按顾客到达的先后顺序对顾客按顾客到达的先后顺序对顾客b.先到后服务先到后服务c.随机服务随机服务 即当服务台空闲时，不按照排队即当服务台空闲时，不按照排队d.优先权服务优先权服务目录下页返回上页结束都不空，顾客加入排队行列等待服务都不空，顾客加入排队行列等待服务.等待制中，等待制中，服务台在选择顾客进行服务时常有如下四种规则：服务台在选择顾客进行服务时常有如下四种规则：进行服务进行服务.序列而随意指定某个顾客接受服务序列而随意指定某个顾客接受服务.(iii)混合制混合制 这是等待制与损失制相结合的一种服这是等待制与损失制相结合的一种服a.队长有限队长有限.当排队等待服务的顾客人数超当排队等待服务的顾客人数超b.等待时间有限等待时间有限.即顾客在系统中的等待时即顾客在系统中的等待时c.逗留时间逗留时间(等待时间与服务时间之和等待时间与服务时间之和)有限有限.目录下页返回上页结束务规则，一般是指允许排队，但又不允许队列无限务规则，一般是指允许排队，但又不允许队列无限长下去长下去.具体说来，大致有三种：具体说来，大致有三种：过规定数量时，后来的顾客就自动离去，另过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的求服务，即系统的等待空间是有限的.间不超过某一给定的长度间不超过某一给定的长度T T，当等待时间超，当等待时间超过过T T时，顾客将自动离去，并不再回来时，顾客将自动离去，并不再回来.(3).服务机构服务机构 (i)服务台数量及构成形式服务台数量及构成形式.从数量上说，服务台有单从数量上说，服务台有单(ii)服务方式服务方式.这是指在某一时刻接受服务的顾客数，这是指在某一时刻接受服务的顾客数，(iii)服务时间的分布服务时间的分布.在多数情况下，对每一个顾客的在多数情况下，对每一个顾客的目录下页返回上页结束服务台和多服务台之分服务台和多服务台之分.从构成形式上看，服务台有：从构成形式上看，服务台有：单队一单队一-单服务台式；单服务台式；单队一单队一-多服务台并联多服务台并联式；式；多队一多队一-多服务台并联式；多服务台并联式；单队一单队一-多服多服务台串联式；务台串联式；单队一单队一-多服务台并串联混合式，多服务台并串联混合式，以及多队多服务台并串联混合式等等以及多队多服务台并串联混合式等等.它有单个服务和成批服务两种它有单个服务和成批服务两种.服务时间是一随机变量服务时间是一随机变量.4.排队系统的主要数量指标排队系统的主要数量指标 排队论主要研究系统的性态，即与排队有关排队论主要研究系统的性态，即与排队有关(1).排队系统主要数量指标排队系统主要数量指标等待时间、等待时间、忙期、忙期、队长队长.目录下页返回上页结束的数量指标的概率规律性；系统的优化问题；统的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型计推断，根据资料合理建立模型.目的是正确设目的是正确设计和有效运行各个服务系统，使之发挥最佳效益计和有效运行各个服务系统，使之发挥最佳效益.所以必须确定判断系统运行优劣的基本数量指标所以必须确定判断系统运行优劣的基本数量指标.(i).等待时间等待时间 从顾客到达时刻起到他开始接受服务止这从顾客到达时刻起到他开始接受服务止这(ii).忙期忙期 忙期是指从顾客到达空闲着的服务机构起，到忙期是指从顾客到达空闲着的服务机构起，到(iii).队长队长 队长是指系统中的顾客数队长是指系统中的顾客数(排队等待的顾客数与排队等待的顾客数与目录下页返回上页结束段时间称为等待时间段时间称为等待时间.等待时间是个随机变量等待时间是个随机变量.从顾客从顾客到达时刻起到他接受服务完成止这段时间称为逗留时到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量间，也是随机变量.服务机构再次成为空闲止的这段时间，即服务机构连续忙服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间的时间.这是个随机变量，是服务员最为关心的指标，因这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度为它关系到服务员的服务强度.与忙期相对的是闲期与忙期相对的是闲期,即即服务机构连续保持空闲的时间服务机构连续保持空闲的时间.在排队系统中，忙期和闲在排队系统中，忙期和闲期总是交替出现的期总是交替出现的.正在接受服务的顾客数之和正在接受服务的顾客数之和)；排队长是指系统中正在排队；排队长是指系统中正在排队等待服务的顾客数等待服务的顾客数.队长和排队长一般都是随机变量队长和排队长一般都是随机变量.(2).数量指标的常用记号数量指标的常用记号(i).主要数量指标主要数量指标WW平均逗留时间，即平均逗留时间，即(在任意时刻在任意时刻)进入进入目录下页返回上页结束所有顾客数的期望值；所有顾客数的期望值；等待服务的顾客数的期望值；等待服务的顾客数的期望值；稳态系统的顾客逗留时间的期望值；稳态系统的顾客逗留时间的期望值；稳态系统的顾客等待时间的期望值稳态系统的顾客等待时间的期望值.L-L-平均队长，平均队长，即稳态系统任一时刻的即稳态系统任一时刻的qW平均等待时间，即平均等待时间，即(在任意时刻在任意时刻)进入进入qW 平均等待队长，即稳态系统任一时刻平均等待队长，即稳态系统任一时刻qL(ii).其它常用数量指标其它常用数量指标s 系统中并联服务台的数目系统中并联服务台的数目；N 稳态系统任一时刻的状态（即系统中稳态系统任一时刻的状态（即系统中U 任一顾客在稳态系统中的逗留时间；任一顾客在稳态系统中的逗留时间；Q 任一顾客在稳态系统中的等待时间；任一顾客在稳态系统中的等待时间；目录下页返回上页结束所有顾客数）；所有顾客数）；平均到达率；平均到达率；平均到达间隔；平均到达间隔；1 平均服务率；平均服务率；平均服务时间；平均服务时间；1 有服务台全部空闲的概率；有服务台全部空闲的概率；目录下页返回上页结束繁忙程度的重要尺度繁忙程度的重要尺度.服务强度，即每个服务台单位时间内的平服务强度，即每个服务台单位时间内的平均服务时间，一般有均服务时间，一般有 ，这是衡量排队系统，这是衡量排队系统 s:稳态系统任意时刻状态为稳态系统任意时刻状态为n n的概率；的概率；nPP Nn特别当特别当n=0n=0时时(系统中顾客数为系统中顾客数为0)0)，即稳态系统所即稳态系统所0P 5.排队系统的描述符号排队系统的描述符号 描述符号：描述符号：X/Y/Z/A/B/CX/Y/Z/A/B/CXX顾客相继到达的间隔时间的分布顾客相继到达的间隔时间的分布 ；常用下；常用下MM表示到达的过程为泊松过程或负指数分布；表示到达的过程为泊松过程或负指数分布；DD表示定长输入；表示定长输入；GG表示一般相互独立的随机分布表示一般相互独立的随机分布.YY服务时间的分布；所用符号与表示顾客服务时间的分布；所用符号与表示顾客目录下页返回上页结束列符号：列符号：到达间隔时间分布相同到达间隔时间分布相同.表示表示K K阶爱尔朗分布；阶爱尔朗分布；kEZZ服务台个数服务台个数 ；“1”1”表示单个服务台，表示单个服务台，“s”(s1)s”(s1)A A系统容量限制系统容量限制(默认为默认为)；如系统有；如系统有K K个等待位子，则个等待位子，则B B顾客源数目（默认为顾客源数目（默认为）；分有限与无限两种，）；分有限与无限两种，表表C C服务规则；服务规则；常用下列符号：常用下列符号：FCFSFCFS：表示先到先服务的排队规则；：表示先到先服务的排队规则；LCFSLCFS：表示后到先服务的排队规则；：表示后到先服务的排队规则；PRPR：表示优先权服务的排队规则表示优先权服务的排队规则。目录下页返回上页结束表示多个服务台表示多个服务台.0K0K1)s(s1)个服务台；系个服务台；系统等待空间容量无限统等待空间容量无限(等待制等待制)；顾客源无限，采；顾客源无限，采用先到先服务规则用先到先服务规则.中的前中的前3 3个符号个符号.例如，某排队问题为例如，某排队问题为M MM MS S.无限；顾客源无限，先到先服务，单个服务的等无限；顾客源无限，先到先服务，单个服务的等待制系统待制系统.三、几类排队论模型三、几类排队论模型1.M/M/S M/M/S 模型模型2.GI/M/n GI/M/n 模型模型目录下页返回上页结束1.M/M/s M/M/s排队模型排队模型 M/M/sM/M/s排队模型是指排队模型是指s s个服务员的排队系统，个服务员的排队系统，顾客到来间隔时间是独立同分布的；顾客到来间隔时间是独立同分布的；服务时间也是独立同分布的；服务时间也是独立同分布的；并且独立于输入过程；并且独立于输入过程；排队规则是等待制；排队规则是等待制；目录下页返回上页结束含假定：含假定：顾客到来间隔时间服从参数为顾客到来间隔时间服从参数为 的指数分布，的指数分布，服务时间服从参数为服务时间服从参数为 的负指数分布，且有隐的负指数分布，且有隐 按排队论的基本构成特征，来求解该排队模型按排队论的基本构成特征，来求解该排队模型(1).基本构成基本构成(i)顾客到达规律顾客到达规律()(),0,1,2!kttP X tkekk 目录下页返回上页结束的主要数量指标：的主要数量指标：平均到达率平均到达率.表示在表示在 时间到达的顾客数，称为排队系统的输入过程时间到达的顾客数，称为排队系统的输入过程.()Xt(,)t tt 其平均值为其平均值为 ，即单位时间内到达的顾客数为，即单位时间内到达的顾客数为 ，并称为，并称为t它服从参数为它服从参数为 的泊松分布，即的泊松分布，即：t(ii)服务时间服务时间目录下页返回上页结束服务率服务率 .表示顾客到达间隔时间序列，其表示顾客到达间隔时间序列，其1|nnnnss 中中 表示第表示第n个顾客的到来时刻个顾客的到来时刻.n 可以证明可以证明：服从参数服从参数 为的泊松分布的充为的泊松分布的充()X tt负指数分布负指数分布.要条件是到要条件是到达间隔时间序列达间隔时间序列 独立同分布且服从独立同分布且服从ns记记Z Z为服务时间，为服务时间，Z Z服从参数为服从参数为 的负指数分布的负指数分布：01()00tteP Ztt 则则 ，即为每个顾客平均服务时间为，即为每个顾客平均服务时间为 ，从，从1EZ 1 而单位时间内被服务的顾客的平均数为而单位时间内被服务的顾客的平均数为 ，称为平均，称为平均 (iii)排队规则排队规则按顾客的到达的先后顺序服务，即先到先服务按顾客的到达的先后顺序服务，即先到先服务.满足以上三个条件的模型在排队论中记为模型满足以上三个条件的模型在排队论中记为模型(2).数量特征数量特征(只讨论只讨论s=1s=1情形情形)(i)平均队长平均队长 稳态下系统内等待服务的顾客数，其数学期稳态下系统内等待服务的顾客数，其数学期目录下页返回上页结束望称为平均等待队长，即望称为平均等待队长，即M/M/s模模型，其中型，其中s s为服务员的个数为服务员的个数.1L(其中其中称为服务强度称为服务强度.).)21qL (1)(ii)平均逗留时间和平均等待时间平均逗留时间和平均等待时间平均逗留时间为平均逗留时间为平均等待时间为平均等待时间为则公式则公式称为称为LittleLittle公式公式.目录下页返回上页结束1LW 11()qW LW qqLW qLL1qWW(3).M/M/s M/M/s 排队模型排队模型(i)当当s=2s=2时时 服务强度服务强度平均队长平均队长平均等待时间平均等待时间 (ii)当当s s是任意的是任意的服务强度服务强度平均队长平均队长平均等待时间平均等待时间 目录下页返回上页结束212222221L 22222(1)LW s 02()!(1)sssLsps ssLW 其中其中为所有服务员均空闲的概率为所有服务员均空闲的概率.1100()()!(1)sksksspks 例例1.某医院急诊室同时只能诊治一个病人，诊治时间某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要服从指数分布，每个病人平均需要1515分钟。病人按泊分钟。病人按泊松分布到达，平均每小时到达松分布到达，平均每小时到达3 3人。试对此排队系统人。试对此排队系统进行分析进行分析.解解对此排队系统分析如下：对此排队系统分析如下：先确定参数值：这是单服务系统有，先确定参数值：这是单服务系统有，目录下页返回上页结束=3=3人人/h/h=60/15=60/15 人人/h=4/h=4人人/h/h故服务强度为：故服务强度为：计算稳态概率：计算稳态概率：010.75PP 目录下页返回上页结束0.750110.750.25P 计算系统主要工作指标计算系统主要工作指标3343L 人人人人30.752.25qLLP 人人人人11160min43Whh10.750.7545minqWWPhh 目录下页返回上页结束 15-12=3min15-12=3min目录下页返回上页结束由于由于112W 代入代入 解得：解得：3 5 平均服务时间为：平均服务时间为：1112min5h (1)1(1)0.9P NxP Nx 目录下页返回上页结束(1)0.1P Nx (1)120.1xx 上式两边取对数上式两边取对数目录下页返回上页结束(2)loglog0.1x 因为因为故故1 log0.1128loglog0.75x 所以所以6x 解解 这相当于增加了一个服务台，故有这相当于增加了一个服务台，故有:S S30.75,0.37524 120(0.75)1510.750.452!(10.375)2.211P 目录下页返回上页结束2s 3 4 人人/h/h人人/h/h22(0.75)0.375550.270.1211112!(10.375)qL 人人人人(0.120.75)0.87qLL 人人人人0.870.2917.4min3LWh 0.120.042.4min3qqLWh 病人必须等候的概率病人必须等候的概率,即系统状态即系统状态N2N2的概率：的概率：2(0.75)5(2)0.202!(10.375)11P N 目录下页返回上页结束表表6-1 6-1 两个系统的比较两个系统的比较目录下页返回上页结束2.GI/M/n GI/M/n排队模型排队模型满足下述三个条件的随机服务系统称为满足下述三个条件的随机服务系统称为GI/M/nGI/M/n排队模型排队模型(1).GI/M/sGI/M/s系统的构成系统的构成b.服务系统由服务系统由n n个并联的服务台所组成个并联的服务台所组成.c.各顾客的服务时间之间是相互独立同分布的，服各顾客的服务时间之间是相互独立同分布的，服目录下页返回上页结束是相互独立同分布的随机变量是相互独立同分布的随机变量.务时间与到达间隔时间相互独立务时间与到达间隔时间相互独立,且服务时间的分且服务时间的分a.顾客到达时刻的间隔顾客到达时刻的间隔10(0,1,2;0)nnn 布服从参数为布服从参数为 的负指数分布的负指数分布 .(2).数量特征数量特征存在且与初始条件无关，其表达式为：存在且与初始条件无关，其表达式为：(i)队长队长目录下页返回上页结束定理定理6.1 设设 为第为第m m个乘客到达时系统的队长，当个乘客到达时系统的队长，当mq时，队长的分布极限时，队长的分布极限 1nlim()mjmP qjK K1(1),0,1,1,1,nrjrrjjj nrUjnjjn n 其中其中 为方程为方程的唯一解，而的唯一解，而(1)A n 目录下页返回上页结束1(1),0,1,1(1)(1)knrrkkk rnnkkUKCrnCnk 11(1)11(1)(1)knkkknnkkKCnk 011,1,2,1()kikiilCCknAl a.该系统的平稳分布下的平均队长为该系统的平稳分布下的平均队长为b.系统的平均队长为系统的平均队长为c.系统服务台平均占有数系统服务台平均占有数目录下页返回上页结束1121(1)(1)(1)jnjnE qjKU 其中其中11101nnn 2(1)KE qw E lE qE qw (ii)等待时间等待时间存在且与初始条件无关，其表达式为存在且与初始条件无关，其表达式为 目录下页返回上页结束令第令第m m个顾客的等待时间为个顾客的等待时间为 ，其分布为，其分布为mw()()mmP wxWx 定理定理6.2 对对GI/M/nGI/M/n系统，当系统，当 时，队长的分布极限时，队长的分布极限1nlim()()mmWxW x (1)()1,01n xKeW xx 其中其中 都与定理都与定理(6.1)(6.1)中的一致中的一致.,K 定理定理6.3 在在GI/M/n系统中，设各顾客服务的时间相互独系统中，设各顾客服务的时间相互独在平衡状态下，顾客到达是不需要等待的概率为在平衡状态下，顾客到达是不需要等待的概率为平均等待时间为平均等待时间为目录下页返回上页结束等待的时间内，每台服务设施的输出过程（即服务完成等待的时间内，每台服务设施的输出过程（即服务完成(0)11KW 20()(1)KWxdW xn 离开服务机构的顾客）是一个以离开服务机构的顾客）是一个以 为强度的泊松过程为强度的泊松过程.立且具有公共的以立且具有公共的以 为参数的负指数分布，则在该顾客为参数的负指数分布，则在该顾客四、模型建立与求解四、模型建立与求解目录下页返回上页结束1.问题分析问题分析 2.基本假设基本假设3.模型的建立与求解模型的建立与求解 1.问题分析问题分析 将公交车的运行看作是提供服务，即服务机构；将公交车的运行看作是提供服务，即服务机构；将乘客看作顾客，乘客乘坐公交车看作是接受公交将乘客看作顾客，乘客乘坐公交车看作是接受公交的服务的服务.公交车运行中乘客的数目描述了系统的状公交车运行中乘客的数目描述了系统的状 态，随着时间的变化，一些乘客得到服务后离去，态，随着时间的变化，一些乘客得到服务后离去，又有一些新的顾客到来，在人数较多时就要排队等又有一些新的顾客到来，在人数较多时就要排队等目录下页返回上页结束服务系统，这里拟用排队论来解决该问题服务系统，这里拟用排队论来解决该问题.按排队按排队论的要求，将公交车看作服务机构，乘客看作顾客论的要求，将公交车看作服务机构，乘客看作顾客.候，而且，顾客到来的时间具有随机性，对顾客的候，而且，顾客到来的时间具有随机性，对顾客的服务时间也有随机性，所以公交车运行系统是一个服务时间也有随机性，所以公交车运行系统是一个随时间变化的随机动态系统，可以看作一个随机随时间变化的随机动态系统，可以看作一个随机目录下页返回上页结束 2.基本假设基本假设(i).某站旅客到达为泊松过程某站旅客到达为泊松过程(ii).公交车对每批乘客服务时间为相互独立的负公交车对每批乘客服务时间为相互独立的负目录下页返回上页结束指数分布，指数分布，每批服务时间是指公交车从起始站出每批服务时间是指公交车从起始站出 乘客到达时间间隔服从参数为乘客到达时间间隔服从参数为 的的k k阶爱尔兰分布：阶爱尔兰分布：发再返回起始站所需的时间为发再返回起始站所需的时间为 .RTt110()10!00kitmmitetP tit 目录下页返回上页结束服从参数服从参数 为的负指数分布为的负指数分布.RTt与与 的关系为的关系为：RTt其中其中 表示运行一个程序的平均时间表示运行一个程序的平均时间.RTt11RTRTE tT3.模型的建立与求解模型的建立与求解 k阶爱尔朗分布的概率密度为：阶爱尔朗分布的概率密度为：到达间隔的期望值到达间隔的期望值目录下页返回上页结束1()()(1)!kt ta tAek 0()()(),()0tkAsedA tres ss 10()mmkE tdA t 公交车服务系统的服务强度为公交车服务系统的服务强度为：以平均等待队长衡量乘客的满意度，系统以平均等待队长衡量乘客的满意度，系统 以乘客的等待时间在非高峰期不超过以乘客的等待时间在非高峰期不超过10分分目录下页返回上页结束服务台的平均占有数衡量公交车公司的利益作服务台的平均占有数衡量公交车公司的利益作为规划模型的目标为规划模型的目标；钟，高峰期不超过钟，高峰期不超过5分钟，以及车容量在区间分钟，以及车容量在区间(50,120)作为约束条件，建立随机规划模型作为约束条件，建立随机规划模型:1tRTmmE vTE nk 约束条件为约束条件为：对上述模型求解即可得到公交车调度的一个对上述模型求解即可得到公交车调度的一个目录下页返回上页结束完整方案完整方案.至此，利用排队论来建立调度问题的至此，利用排队论来建立调度问题的一个明确、完整的随机规划数学模型，可以利用一个明确、完整的随机规划数学模型，可以利用一般规划模型的求解方法进行求解一般规划模型的求解方法进行求解.2min min(1)E lE qE qwkE qw 20(50,120)()5(10)(1)KKWxdW xorn 再见目录下页返回上页结束
展开阅读全文