运筹学讲义6

合工大考研第六讲排队论顾客源顾客源排队结构排队结构排队规则服务规则服务规则服务机构服务机构离去离去顾客到来顾客到来排队系统顾客源排队规则服务机构顾客总体数顾客到达方式顾客流的概率分布损失制等待制混合制服务台数量及构成服务方式服务时间单个、成批确定型、随机型5种结构FCFSLCFSSIROPR有限、无限(m)一个一个、成批确定型、随机型顾客到达输入过程占有空间队列具体、抽象；容量(N)有限、无限单列、多列(c)；互相转移；中途退出独立、不独立平稳、不平稳服务时间的分布平稳、非平稳服务员数量没有、一个或多个X/Y/ZX处填写表示相继到达间隔时间的分布;Y处填写表示服务时间的分布;Z处填写并列的服务台的数目c.c=1单服务台，c1多服务合工大考研台表示相继到达间隔时间和服务时间的各种分布的符号:M—负指数分布D—确定型Ek—k阶爱尔朗分布GI—一般相互独立的时间间隔的分布G—一般服务时间的分布X/Y/Z/A/B/CA处填写系统容量限制N；N=c损失制，N=∞等待制系统，Nc混合制系统B处填写顾客源数m（有限、无限）；C处填写服务规则（FCFS/LCFS/SIRO/PR）。约定：FCFSZYX/////如略去后三项，即指1、平均到达率(λ)：单位时间内平均到达的顾客数。平均到达间隔(1/λ)2、平均服务率(μ)：单位时间内平均服务的顾客数。平均服务时间(1/μ)3、队长(Ls)：排队系统中顾客的平均数。4、队列长(Lq)：指系统中排队等候服务的顾客数。Ls=Lq+正被服务的顾客数5、逗留时间(Ws)：指一个顾客在系统中的停留时间。6、等待时间(Wq)：指一个顾客在系统中排队等待的时间。合工大考研Ws=Wq+服务时间7、系统的状态：描述系统中的顾客数损失制、服务台个数c系统容量N系统容量无限0,1,2,...,N0,1,2,...0,1,2,...,c8、系统的状态概率[Pn(t)]：指t时刻、系统状态为n的概率9、稳定状态（统计平衡状态）：limPn(t)→PnPn=P{N=n}稳态系统中有n个顾客概率P1稳态系统中有1个顾客概率P0稳态所有服务台全部空闲概率模型Pn(t)的计算（在时刻t系统中有n个顾客的概率）×O×O离去到达nnnn××OOnn+1n-1n(A)(B)(C)(D)在时刻t+Δt顾客数在区间（t,t+Δt）在时刻t顾客数情况×O×O离去到达nnnn××OOnn+1n-1n(A)(B)(C)(D)在时刻t+Δt顾客数在区间（t,t+Δt）在时刻t顾客数情况λΔtμΔtλΔtPn(t)Pn(t)Pn+1(t)Pn-1(t)1-λΔt1-λΔtμΔt1-μΔt1-μΔtPn(t+Δt)=Pn(t)(1-λΔt)(1-μΔt)+Pn+1(t)(1-λΔt)μΔt++Pn-1(t)λΔt(1-μΔt)+Pn(t)λΔtμΔtn≥1整理得：Pn(t+Δt)=Pn(t)(1-λΔt-μΔt)+Pn+1(t)μΔt+Pn-1(t)λΔt+o(Δt)合工大考研[Pn(t+Δt)-Pn(t)]/Δt=λPn-1(t)+μPn+1(t)-(λ+μ)Pn(t)令Δt0dPn(t)/dt=λPn-1(t)+μPn+1(t)–(λ+μ)Pn(t)(n≥1)(1)考虑P0(t)的情况：×OO离去到达000××O010(A)(B)(C)在时刻t+Δt顾客数在区间（t,t+Δt）在时刻t顾客数情况×OO离去到达000××O010(A)(B)(C)在时刻t+Δt顾客数在区间（t,t+Δt）在时刻t顾客数情况μΔtP0(t)P1(t)1-λΔt1-λΔt1P0(t)λΔtμΔtP0(t+Δt)=P0(t)(1-λΔt)+P1(t)(1-λΔt)μΔt+P0(t)λΔtμΔt令Δt0dP0(t)/dt=-λP0(t)+μP1(t)（2）令dPn(t)/dt=0，由(1)和(2)得到-λP0+μP1=0(3)λPn-1+μPn+1-(λ+μ)Pn=0(4)-λP0+μP1=0(3)λPn-1+μPn+1-(λ+μ)Pn=0(4)1PP0由(3)式得1PP0由(3)式得,012nnPPn（），，，0通过求解可得,012nnPPn（），，，0通过求解可得令n=1，由(4)式得220PP（）200001nnPPPP1（令）2001111P()P合工大考研01(1),1nnPPn011nnPPP忙n-1λμn0λμ1λμn+1…...…...λP0=μP1λPn-1+μPn+1=(λ+μ)Pn对状态0对状态n(n≥1)系统状态转移速度图（1）系统中平均顾客数（Ls）012300123SnnLnPPPPP23(1)(23)SS232342323S23(1)1/11/sL记230(1)1(1)2(1)3(1)（2）队列中等待的平均顾客数（Lq）1231012(1)qnnLPPPnP合工大考研011(1)nnssnnnPPLPL（3）顾客逗留时间的期望值（Ws）李泰勒（Little）证明了在很宽的条件下，排队系统数量指标之间有以下的关系式：Ws=Ls/λe11sW（4）队列中顾客等待时间（Wq）李泰勒证明了在很宽的条件下，排队系统数量指标之间有以下的关系式111qqseLWW1,111/0nρρPρPnn合工大考研(1)队长（Ls）指在系统中的顾客数(2)排队长（Lq）指系统中排队等候服务的顾客数Lq=Ls-正被服务的顾客数sLλμλρρLLsq(3)逗留时间（Ws）指一个顾客在系统中的停留时间(4)等待时间（Wq）指一个顾客在系统中排队等待的时间Wq=Ws-服务时间λμWEWs1][λμρμWWsq1（5）顾客在系统中逗留的时间W（随机变量），在M/M/1情形下，它服从参数为的负指数分布，即()()()()()1()()()1()()()1分布函数密度函数顾客在系统中逗留时间超过的概率是顾客在系统中逗留时间不超过的概率是（12年，第二题，15分）某修理店只有一个修理工，来修理合工大考研的顾客到达过程为泊松流，平均4人/小时；修理时间服从负指数分布，平均每人服务时间为6分钟。请计算：1）修理店空闲的概率；2）店内恰有3个顾客的概率；3）在店内的平均顾客数；4）每位顾客在店内的平均逗留时间；5）等待服务的平均顾客数；6）每位顾客平均等待服务的时间；7）必须在店内消耗10分钟以上的概率。解：由已知条件知4/10/人小时，人小时，因此40.410=0P10.6=33P(1)0.0384=42L1043s111W1046s0.444L10415q0.41W10415s1）修理店空闲的概率2）店内恰有3个顾客的概率3）在店内的平均顾客数4）每位顾客在店内的平均逗留时间5）等待服务的平均顾客数6）每位顾客平均等待服务的时间7）必须在店内消耗10分钟以上的概率()11P(W)6wee（08年，第五题，15分）顾客按泊松分布到达某单人理发店，平均间隔20分钟。理发时间为负指数分布，平均每人15分钟。合工大考研设该系统符合M/M/1模型，求：a）顾客不必等待的概率；b）顾客在店内平均等待时间；c）若顾客在店内耗时超过1.25小时，则雇人帮忙，问平均到达率达到多少以上需雇人帮忙。解：由已知条件知3/4/人小时，人小时，因此30.754=a）顾客不必等待的概率0P10.25=；b）顾客在店内平均等待时间q0.75W0.7543==小时；c）若顾客在店内耗时超过1.25小时，即sW1.25，因此111.25,3.24==，平均到达率达到32/.人小时以上需雇人帮忙。M/M/1/N/∞模型（混合制系统）假定系统最大容量为N，单服务台情形排队等待的顾客最多为N-1n-1λμn0λμ1λμn+1…...…...N-1λμNn-1λμn0λμ1λμn+1…...…...N-1λμNN+1个状态合工大考研10111()nnnNNPPPPPPP10111()nnnNNPPPPPPPPn的计算2000001NNnnPPPPP1PP0,10nnPPnN（）通过求解可得,10nnPPnN（）通过求解可得2011NP()10111N()Pn1nNNnNPP0111111解得：NNnNnNnP1s101L,111（）(1)队长NNnNnNnP1s101L,111（）(1)队长NnsonnPLPq1L11（）（）(2)队列长NnsonnPLPq1L11（）（）(2)队列长有效到达率λe=λ(1-PN)系统不满时顾客以λ的速度进入系统合工大考研1W1qqqseNLLWP（）(4)顾客等待时间1W1qqqseNLLWP（）(4)顾客等待时间0W1ssseLLP（）(3)顾客逗留时间λe=μ(1-P0)顾客源为有限的情形（M/M/1/∞/m）(m-n+1)λmλ(m-n)λλn-1μn0μ1μn+1…...…...m-1μmn-1μn0μ1μn+1…...…...m-1μm机器故障问题：设共有m台机器，机器故障停机表示到达，待修机器形成队列，修理工是服务员。10111(1)[()],11nnnmmPmPPmnPmnPnmPPM/M/c规定各服务台工作相互独立且平均分配服务率相同，即μ1=μ2=…=μc=μ整个服务机构的平均服务率为cμ,(n≥c)nμ,(nc)规定各服务台工作相互独立且平均分配服务率相同，即μ1=μ2=…=μc=μ整个服务机构的平均服务率为cμ,(n≥c)nμ,(nc)n-1nμn0μ1(n+1)μn+1…...…...n-1cμnn≤cncλλλλn-1nμn0μ1(n+1)μn+1…...…...n-1cμnn≤cncλλλλ合工大考研()(c)101111(1)(),1(),nnnnnnPPnPPnPnccPPcPn