运筹学基础及应用(第五版)_(第10章排队论).ppt

运筹学OPERATIONS RESEARCH Little 公式 其中 ?是单位时间内到达的平均顾客数； ?是单位时间内可以服务完的平均顾客数。 系统中平均顾客数 = 单位时间内到达的平均顾客数×平均逗留时间 又 如果求得Pn ,则 即可得到。 另外 1-P0 是系统的忙期概率。 排队论研究的基本问题： 通过研究主要数量指标在瞬时或平稳状态下的概率分布及数字特征，了解系统运行的基本特征。 统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中，系统是否达到平稳状态的检验；顾客相继到达时间间隔相互独立性的检验，服务时间的分布及有关参数的确定等。 排队研究的基本问题： 系统优化问题：又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优的或最合理的状态。包括：最优设计问题和最优运营问题。 §2 输入与服务时间的分布 一、最简单流 1、定义; 在时长为 t 的时间段内，有k个顾客到达的概率 服从poisson分布： t时段内平均到达顾客数； 单位时段内平均到达顾客数 2、最简单流的性质 （1）平稳性：在一定时间间隔内，有k个顾客到达的概率只与时长有关，与起始时刻无关； （2）无后效性：[a,a+t]时段内有k个顾客到达的概率与a时刻之前的客流无关； （3）普通性：在足够小的时段内有2个或个以上顾客到来的概率为零。 说明：1、最简单流的性质可以简化有关计算； 2、假设所研究的问题都是最简单流，或近似最简单流 二、最简单流的有关计算 1、单位时间内到达的顾客数 2、 内没有顾客到达的概率 3、 恰有一个顾客到达的概率 4、若顾客到达~ poisson分布，则相继到达间隔时间 ~ 负指数分布 三、服务时间 设服务时间~ 负指数分布 1、单位时间内服务完毕，离去的顾客数 2、 内没有顾客离去的概率 3、 恰有一个顾客离去的概率 4、若干负指数分布的最小值也是负指数分 说明： 服务机构中有s个并联服务台，各台~ 负指数分布，则整个服务时间~ 负指数分布。 第*页 生灭过程 第*页 2、t时刻有n-1个顾客， 时刻系统中有n个顾客的概率为 1、t时刻有n个顾客， 时刻系统中仍有n个顾客的概率为 时刻系统中有n个顾客的概率 3、t时刻有n+1个顾客， 时刻系统中有n个顾客的概率为 4、t时刻为n,n-1,n+1个顾客之外的情况， 时刻系统中有n个顾客的概率为 第*页 于是 特别的，n=0时 第*页 移项求极限，得差分微分方程 时,平稳状态 §4 最简单的排队模型 一、M/M/1/ ? 模型 ： 顾客相继到达时间服从参数为?的负指数分布； 服务时间服从参数为?的负指数分布； 服务台数为1； 系统的空间为无限，允许永远排队。 1、队长的分布 记 Pn=p{N=n} , n=0,1,2…. 为系统达到平衡状态后队长的概率分布， 则 ?n=?； ?n= ?， ? = ?/?1， 有 Pn= (1-?)?n, n=0,1,2…. 2、几个数量指标 平均队长： L= ?n Pn= ? n (1-?)?n= ?/ (1-?) = ?/(?- ?) 平均排队长： Lq= ?(n-1) Pn= ?2/ (1-?) = ?2/ ?(?- ?) 平均逗留时间： W=E(T)= 1/(?- ?) （little公式) 平均等待时间： Wq= ?/ ?(?- ?) 例3：考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达2列；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平衡状态下系统中列车的平均数；每一列车的平均逗留时间；等待编组的列车平 均数。如果列车因站中2股道均被占用而停在站外或前方站时，每列车每小时费用为a元，求每天由于列车在站外等待而造成的损失。 解：本例可看成一个M/M/1/?排队问题，其中? =2， ? =3，?=?/?=2/31 系统中列车的平均数 L= ?/ (1-?)=(2/3)