运筹学教程七随机服务理论概述素材.pptx

1第七章第七章 随机服务理论概述随机服务理论概述确定型只是随机现象的特例确定型只是随机现象的特例27.1 随机服务系统随机服务系统系统的输入与输出是随机变量系统的输入与输出是随机变量A.k.Erlang 于于19091920年发表了一系列根据话务量计年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础算电话机键配置的方法，为随机服务理论奠定了基础又称为又称为排队论排队论(Queuing Theory)或或拥塞理论拥塞理论(Congestion Theory)3 与服务系统性能相关的特性与服务系统性能相关的特性服务系统存在来自两个矛盾方面的要求服务系统存在来自两个矛盾方面的要求顾客希望服务质量好，如排队等待时间短，损失率低顾客希望服务质量好，如排队等待时间短，损失率低系统运营方希望设备利用率高系统运营方希望设备利用率高给用户一个经济上能够承受的满意的质量给用户一个经济上能够承受的满意的质量哪些系统特性会影响系统的性能？哪些系统特性会影响系统的性能？服务机构的组织方式与服务方式服务机构的组织方式与服务方式顾客的输入过程和服务时间分布顾客的输入过程和服务时间分布系统采用的服务规则系统采用的服务规则 7.1.1 服务机构的组织方式与服务方式服务机构的组织方式与服务方式单台制和多台制单台制和多台制并联服务并联服务串联服务串联服务串并联服务、网络服务串并联服务、网络服务全利用度、部分利用度全利用度、部分利用度4 与服务系统性能相关的特性与服务系统性能相关的特性 7.1.2 输入过程和服务时间输入过程和服务时间顾客单个到达或成批到达顾客单个到达或成批到达顾客到达时间间隔的分布和服务时间的分布顾客到达时间间隔的分布和服务时间的分布顾客源是有限的还是无限的顾客源是有限的还是无限的 7.1.3 服务规则服务规则损失制损失制等待制等待制：先到先服务先到先服务(FIFO)，后到先服务，随机服务，优，后到先服务，随机服务，优先权服务先权服务混合制混合制逐个到达，成批服务；成批到达，逐个服务逐个到达，成批服务；成批到达，逐个服务57.2 随机服务过程随机服务过程单台服务系统、等待制、先到先服务单台服务系统、等待制、先到先服务顾客在系统中的总时长：逗留时间顾客在系统中的总时长：逗留时间=等待时长等待时长+服务时长服务时长等待时长与顾客到达率和服务时长有关等待时长与顾客到达率和服务时长有关6当服务台连续不断服务时，有如下关系：当服务台连续不断服务时，有如下关系：wi+1+i+1=wi+hiwi+hi 表示了累计的未完成的服务时长，一般地有表示了累计的未完成的服务时长，一般地有 忙期和忙时忙期和忙时 系统系统连续不断服务的时期称为忙期。而系连续不断服务的时期称为忙期。而系统最繁忙的一个小时称为忙时。统最繁忙的一个小时称为忙时。排队系统的指标及其关系排队系统的指标及其关系 1）Wq、Wd 分别是顾客的分别是顾客的平均排队等待时间和平均逗留时间平均排队等待时间和平均逗留时间2）Lq、Ld分别是分别是系统平均排队的顾客数和系统的平均顾客数系统平均排队的顾客数和系统的平均顾客数3）h 是顾客的是顾客的平均服务时长，平均服务时长，是顾客的是顾客的平均到达率。平均到达率。4）Ln 是同时接受服务的平均顾客数是同时接受服务的平均顾客数(即即平均服务台占用数平均服务台占用数)5）Ld=Wd=(Wq+h)=Lq+Ln ，Lq=Wq，Ln=h77.3 服务时间与间隔时间服务时间与间隔时间 7.3.1 概述概述顾客的服务时间由于多种原因具有不确定性，最好的描述顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也具有一定方法就是概率分布；同样顾客到达的间隔时间也具有一定的概率分布的概率分布服务时间和到达间隔时间服从什么分布？可以先通过统计服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验得到经验分布，然后再做理论假设和检验经验分布一般采用直方图来表示，如下图经验分布一般采用直方图来表示，如下图8若统计区间分得越细，样本越多，则经验分布的轮廓越接若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线近曲线一般服务时间和间隔时间都是非负的连续实变量，令一般服务时间和间隔时间都是非负的连续实变量，令 h 代代表服务时间，表服务时间，代表间隔时间，代表间隔时间，t 为给定的时间，则它们的为给定的时间，则它们的概率分布函数分别表示为概率分布函数分别表示为F(t)=Ph t F(t)=P t它们的概率密度函数为它们的概率密度函数为f(t)=F(t)，具有性质：，具有性质：f(t)0，f(t)dt=1服务时间落在区间服务时间落在区间(a,c)的概率为的概率为服务时间落在区间服务时间落在区间(t,t+t)的概率为的概率为 Pt 1 个服务台终结的概率为个服务台终结的概率为 o(t)，称为，称为普通性普通性 137.4 输入过程输入过程即顾客到达的分布，可用相继到达顾客的间隔时间描述，即顾客到达的分布可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述也可以用单位时间内到达的顾客数描述间隔时间服从定长分布间隔时间服从定长分布单位时间内到达的顾客数服从单位时间内到达的顾客数服从波松分布波松分布(法国数学家法国数学家Poisson,1837)间隔时间服从爱尔兰分布间隔时间服从爱尔兰分布一般独立同分布一般独立同分布 7.4.1 波松输入过程及其特点波松输入过程及其特点(0,t)时间内到达时间内到达 k 个顾客的个数服从波松分布，若个顾客的个数服从波松分布，若 为为到达率到达率电话呼叫的到达，商店的顾客到达，十字路口的汽车流，电话呼叫的到达，商店的顾客到达，十字路口的汽车流，港口到达的船只，机场到达的飞机等港口到达的船只，机场到达的飞机等14 7.4.1 波松输入过程及其特点波松输入过程及其特点(1)平稳性平稳性：顾客到达数只与时间区间长度有关：顾客到达数只与时间区间长度有关(2)无后效性无后效性：不相交的时间区间内所到达的顾客数是独立的：不相交的时间区间内所到达的顾客数是独立的(3)普通性普通性：在：在 t 时间内到达一个顾客的概率为时间内到达一个顾客的概率为 t+o(t)，到，到达两个或两个以上顾客的概率为达两个或两个以上顾客的概率为 o(t)；即两个顾客不可能同；即两个顾客不可能同时到达时到达(4)有限性：在有限的时间区间内，到达的顾客数是有限的。有限性：在有限的时间区间内，到达的顾客数是有限的。波松过程具有波松过程具有可迭加性可迭加性即独立的波松分布变量的和仍为波松分布即独立的波松分布变量的和仍为波松分布15 7.4.1 波松输入过程及其特点波松输入过程及其特点波松过程的到达间隔时间为负指数分布波松过程的到达间隔时间为负指数分布令令 代表间隔时间，则概率代表间隔时间，则概率 P t代表时间区间代表时间区间(0,t)内没有顾客来的概率；由波松分布可知内没有顾客来的概率；由波松分布可知P0(t)=P t=et故间隔时间故间隔时间 的分布为的分布为 P t=1 et7.4.2 马尔科夫链马尔科夫链马尔科夫链马尔科夫链(Markov Chain)又简称又简称马氏链马氏链，是一种，是一种离散事件离散事件随机过程。用数学式表达为随机过程。用数学式表达为PXn+1=xn+1|X1=x1,X2=x2,.,Xn=xn=PXn+1=xn+1|Xn=xnXn+1的状态只与的状态只与 Xn的状态有关，与的状态有关，与 Xn 前的状态无关，前的状态无关，具有具有无记忆性无记忆性，或，或无后效性无后效性，又称，又称马氏性马氏性状态转移是一步一步发生的，一步状态转移概率状态转移是一步一步发生的，一步状态转移概率Pij(t)=PXn+1=j|Xn=i16 例例 7.4.2 一售货员出售两种商品一售货员出售两种商品A和和B，每日工作，每日工作 8 小时。购买每种小时。购买每种商品的顾客到达过程为波松分布，到达率分别为商品的顾客到达过程为波松分布，到达率分别为 A=8人人/日，日，B=16人人/日，试求：日，试求：(1)1小时内来到顾客总数为小时内来到顾客总数为 3 人的概率；人的概率；(2)三个顾客全是购买三个顾客全是购买B类商品的概率。类商品的概率。解解：(1)总到达率为总到达率为 A+B=24人人/日，日，1 小时小时=1/8 日，故日，故(2)3 个顾客全是购买个顾客全是购买 B 类商品的概率为类商品的概率为177.5 生灭过程生灭过程一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭亡，人口的增减，生物种群的灭种现象等亡，人口的增减，生物种群的灭种现象等采用马氏链采用马氏链令令 N(t)代表系统在时刻代表系统在时刻 t 的状态，下一瞬间的状态，下一瞬间 t+t 系统的系统的状态只能转移到相邻状态，或维持不变，如图所示状态只能转移到相邻状态，或维持不变，如图所示三种转移是不相容的，三者必居其一三种转移是不相容的，三者必居其一只有具有无记忆性和普通性的过程只有具有无记忆性和普通性的过程(分布分布)才适用马氏链才适用马氏链令令 Pj(t)=PN(t)=j代表系统在时刻代表系统在时刻 t 处于状态处于状态 j 的概率的概率18 生灭过程的马氏链生灭过程的马氏链根据马氏链，应用全概率公式，有状态转移概率方程根据马氏链，应用全概率公式，有状态转移概率方程另有两个边界方程另有两个边界方程19 生灭方程的推导过程生灭方程的推导过程将上述三个差分方程化为微分方程将上述三个差分方程化为微分方程上述三个方程是动态方程，当系统处于稳态时，系统处于上述三个方程是动态方程，当系统处于稳态时，系统处于统计平衡状态，即状态概率不随时间变化，从而状态概率统计平衡状态，即状态概率不随时间变化，从而状态概率导数为导数为 0；令上三个方程左侧为；令上三个方程左侧为 0，得稳态方程组，得稳态方程组20 生灭过程稳态解生灭过程稳态解方程方程(1),(2),(3)与稳态状态转移图一一对应；递归解如下：与稳态状态转移图一一对应递归解如下：21 满足生灭过程的条件满足生灭过程的条件系统的输入过程和服务过程具有平稳、无记忆性和普通性系统的输入过程和服务过程具有平稳、无记忆性和普通性服务台是独立的、相同的、并联的服务台是独立的、相同的、并联的波松输入过程和负指数服务时长就具有这些性质波松输入过程和负指数服务时长就具有这些性质可以用马氏链来描述系统的状态转移可以用马氏链来描述系统的状态转移这种系统称为这种系统称为生灭服务系统生灭服务系统，一般用，一般用 M/M/n 表示，又表示，又称为称为标准服务系统标准服务系统；标准服务系统的形式很多，但都是基于生灭方程，关键标准服务系统的形式很多，但都是基于生灭方程，关键是找出是找出 j,j 的不同表达式，将它们代入的不同表达式，将它们代入生灭方程生灭方程标准服务系统的表示法：标准服务系统的表示法：(X/Y/Z:A/B/C)，X 表示输入过程，表示输入过程，Y 表示服务过程，表示服务过程，Z 表示并联服务台的个数，表示并联服务台的个数，A 表示顾客源，表示顾客源，B 表示系统容量，表示系统容量，C 表示服务规则表示服务规则(M/M/n:/m/FIFO)表示波松输入，负指数服务时长，表示波松输入，负指数服务时长，n 个并联服务台，顾客源无穷，系统容量为个并联服务台，顾客源无穷，系统容量为 m,m n，先到先服务先到先服务D 定长分布；定长分布；Ek k阶爱尔兰分布；阶爱尔兰分布；G 一般独立分布一般独立分布人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。管理与人文学院管理与人文学院 忻展红忻展红 1999，4