運籌學教案_排隊論1

1、1 排隊論（排隊論（queuing),也稱隨機服務系統(tǒng)理論，是也稱隨機服務系統(tǒng)理論，是運籌學的一個主要分支。運籌學的一個主要分支。 1909年，丹麥哥本哈根電子公司電話工程師年，丹麥哥本哈根電子公司電話工程師A. K. Erlang的開創(chuàng)性論文的開創(chuàng)性論文“概率論和電話通訊理論概率論和電話通訊理論”標志此理論的誕生。排隊論的發(fā)展最早是與電話，標志此理論的誕生。排隊論的發(fā)展最早是與電話，通信中的問題相聯(lián)系的，并到現(xiàn)在是排隊論的傳統(tǒng)通信中的問題相聯(lián)系的，并到現(xiàn)在是排隊論的傳統(tǒng)的應用領域。近年來在計算機通訊網絡系統(tǒng)的應用領域。近年來在計算機通訊網絡系統(tǒng)、交通、交通運輸、醫(yī)療衛(wèi)生系統(tǒng)、庫存管理、作戰(zhàn)指

2、揮等各領運輸、醫(yī)療衛(wèi)生系統(tǒng)、庫存管理、作戰(zhàn)指揮等各領域中均得到應用。域中均得到應用。2排隊結構服務機構顧客源顧客到達排隊規(guī)則服務規(guī)則離去圖1 排 隊系統(tǒng)示意圖 排隊系統(tǒng)一般有三個基本組成部分：排隊系統(tǒng)一般有三個基本組成部分：1.1.輸輸入過程；入過程；2.2.排隊規(guī)則；排隊規(guī)則；3.3.服務機構?，F(xiàn)分別說服務機構。現(xiàn)分別說明：明：3 輸入即為顧客的到達，可有下列情況：輸入即為顧客的到達，可有下列情況： 1）顧客源可能是有限的，也可能是無限的。顧客源可能是有限的，也可能是無限的。 2）顧客是成批到達或是單個到達。顧客是成批到達或是單個到達。 3）顧客到達的間隔時間可能是隨機的或確定的。顧客到達的

3、間隔時間可能是隨機的或確定的。 4）顧客到達可能是相互獨立的或關聯(lián)的。所謂顧客到達可能是相互獨立的或關聯(lián)的。所謂獨立就是以前顧客的到達對以后顧客的到達無影響。獨立就是以前顧客的到達對以后顧客的到達無影響。 5）輸入過程可以是平穩(wěn)的（輸入過程可以是平穩(wěn)的（stationarystationary）或說）或說是對時間齊次的（是對時間齊次的（Homogeneous in timeHomogeneous in time），也可以），也可以是非平穩(wěn)的。輸入過程是平穩(wěn)的是指顧客相繼到達是非平穩(wěn)的。輸入過程是平穩(wěn)的是指顧客相繼到達的間隔時間分布和參數（均值、方差）與時間無關；的間隔時間分布和參數（均值、方差

4、）與時間無關；非平穩(wěn)的則是與時間相關，非平穩(wěn)的處理比較困難。非平穩(wěn)的則是與時間相關，非平穩(wěn)的處理比較困難。 4 1）顧客到達后接受服務分為即時制（損失制）顧客到達后接受服務分為即時制（損失制）和等待制。即時制不形成隊列，而對于等待制將和等待制。即時制不形成隊列，而對于等待制將會形成隊列，顧客可以按下規(guī)則接收服務：會形成隊列，顧客可以按下規(guī)則接收服務： （1 1）先到先服務先到先服務 FCFS FCFS （2 2）后到先服務）后到先服務 LCFS LCFS （3 3）隨機服務）隨機服務RAND RAND （4 4）有優(yōu)先權服務）有優(yōu)先權服務 PRPR。 2）從隊列的空間可分為有容量限制和無容量從

5、隊列的空間可分為有容量限制和無容量限制。限制。 3 3）從隊列數可分為單列和多列。）從隊列數可分為單列和多列。5 1 1）服務機構可以是單服務員和多服務員服務，）服務機構可以是單服務員和多服務員服務，這種服務形式與隊列規(guī)則聯(lián)合后形成了多種不同隊這種服務形式與隊列規(guī)則聯(lián)合后形成了多種不同隊列，不同形式的排隊服務機構，如：列，不同形式的排隊服務機構，如：112n. . .12n。單隊單服務臺多隊多服務臺（并列)單隊多服務臺（并列）12n.12312單隊多服務臺（串列）混合形式6 上述特征中最主要的、影響最大的是：上述特征中最主要的、影響最大的是：顧客相繼到達的間隔時間分布顧客相繼到達的間隔時間分布

6、服務時間的分布服務時間的分布服務臺數服務臺數 D.G.KendallD.G.Kendall，19531953提出了分類法，稱為提出了分類法，稱為KendallKendall記號記號( (適用于并列服務臺適用于并列服務臺) )即：即：X/Y/Z:A/B/CX/Y/Z:A/B/C 2)2)服務方式分為單個顧客服務和成批顧客服務。服務方式分為單個顧客服務和成批顧客服務。 3)3)服務時間分為確定型和隨機型。服務時間分為確定型和隨機型。 4)4)服務時間的分布在這里我們假定是平穩(wěn)的。服務時間的分布在這里我們假定是平穩(wěn)的。7 式中：式中：X顧客相繼到達間隔時間分布。顧客相繼到達間隔時間分布。 M負指數分

7、布負指數分布Markov，D確定型分布確定型分布Deterministic， EkK階愛爾朗分布階愛爾朗分布Erlang， GI 一般相互獨立隨一般相互獨立隨機分布機分布(General Independent)， G 一般隨機分布。一般隨機分布。Y填寫服務時間分布（與上同）填寫服務時間分布（與上同）Z填寫并列的服務臺數填寫并列的服務臺數A排隊系統(tǒng)的最大容量排隊系統(tǒng)的最大容量B顧客源數量顧客源數量 C排隊規(guī)則排隊規(guī)則 如如 即為顧客到達為泊松過即為顧客到達為泊松過程，服務時間為負指數分布，單臺，無限容量，無程，服務時間為負指數分布，單臺，無限容量，無限源，先到先服務的排隊系統(tǒng)模型。限源，先到先

8、服務的排隊系統(tǒng)模型。8 1.1.排隊系統(tǒng)的統(tǒng)計推斷排隊系統(tǒng)的統(tǒng)計推斷: :即通過對排隊系統(tǒng)主即通過對排隊系統(tǒng)主要參數的統(tǒng)計推斷和對排隊系統(tǒng)的結構分析，判要參數的統(tǒng)計推斷和對排隊系統(tǒng)的結構分析，判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根據排隊理論進行研究。據排隊理論進行研究。 2.2.系統(tǒng)性態(tài)問題系統(tǒng)性態(tài)問題: :即研究各種排隊系統(tǒng)的概率即研究各種排隊系統(tǒng)的概率規(guī)律性，主要研究隊長分布、等待時間分布和忙規(guī)律性，主要研究隊長分布、等待時間分布和忙期分布等統(tǒng)計指標期分布等統(tǒng)計指標, ,包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。 3.3.最優(yōu)化問題

9、：即包括最優(yōu)設計最優(yōu)化問題：即包括最優(yōu)設計( (靜態(tài)優(yōu)化靜態(tài)優(yōu)化) )，最優(yōu)運營（動態(tài)優(yōu)化）。最優(yōu)運營（動態(tài)優(yōu)化）。 9 求解一般排隊系統(tǒng)問題的目的主要是通過求解一般排隊系統(tǒng)問題的目的主要是通過研究排隊系統(tǒng)運行的效率指標，估計服務質研究排隊系統(tǒng)運行的效率指標，估計服務質量，確定系統(tǒng)的合理結構和系統(tǒng)參數的合理量，確定系統(tǒng)的合理結構和系統(tǒng)參數的合理值，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建值，以便實現(xiàn)對現(xiàn)有系統(tǒng)合理改進和對新建系統(tǒng)的最優(yōu)設計等。系統(tǒng)的最優(yōu)設計等。 排隊問題的一般步驟：排隊問題的一般步驟： 1. 1. 確定或擬合確定或擬合排隊系統(tǒng)顧客到達的時間排隊系統(tǒng)顧客到達的時間間隔分布和服務時間分布

10、間隔分布和服務時間分布( (可實測可實測) )。 2. 2. 研究研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數。狀態(tài)概率用系統(tǒng)中顧客數。狀態(tài)概率用P Pn n(t)(t)表示表示, ,即在即在t t時刻系統(tǒng)中有時刻系統(tǒng)中有n n個顧客的概率，也稱瞬態(tài)概率。個顧客的概率，也稱瞬態(tài)概率。10 求解狀態(tài)概率求解狀態(tài)概率P Pn n(t)(t)方法是建立含方法是建立含P Pn n(t)(t)的微分差的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也于瞬態(tài)解一般求出確定值比較困難，

11、即便求得一般也很難使用。因此我們常常使用它的極限很難使用。因此我們常常使用它的極限( (如果存在的如果存在的話話) )：nttnp)(plim 穩(wěn)態(tài)的物理意義見右圖，穩(wěn)態(tài)的物理意義見右圖，系統(tǒng)的穩(wěn)態(tài)一般很快都系統(tǒng)的穩(wěn)態(tài)一般很快都能達到，但實際中達不能達到，但實際中達不到穩(wěn)態(tài)的現(xiàn)象也存在。到穩(wěn)態(tài)的現(xiàn)象也存在。值得注意的是求穩(wěn)態(tài)概值得注意的是求穩(wěn)態(tài)概率率P Pn n并不一定求并不一定求t的的極限極限,而只需求而只需求P Pn n(t)=0 (t)=0 即可。即可。 過渡狀態(tài) 穩(wěn)定狀態(tài) pn t 圖3 排隊系統(tǒng)狀態(tài)變化示意圖 稱為穩(wěn)態(tài)稱為穩(wěn)態(tài)( (steady state)steady state)

12、解，解，或稱統(tǒng)計平衡狀態(tài)或稱統(tǒng)計平衡狀態(tài) ( (Statistical Equilibrium State)Statistical Equilibrium State)的解的解。11 3.3.根據排隊系統(tǒng)對應的理論模型根據排隊系統(tǒng)對應的理論模型求出用以判斷系統(tǒng)求出用以判斷系統(tǒng)運行優(yōu)劣的基本數量指標的概率分布或特征數。運行優(yōu)劣的基本數量指標的概率分布或特征數。 數量指標主要包括數量指標主要包括: : (1)(1)平均隊長（平均隊長（L Ls s）: :系統(tǒng)中的顧客數。系統(tǒng)中的顧客數。 平均隊列長（平均隊列長（L Lq q）: :系統(tǒng)中排隊等待服務的顧客數。系統(tǒng)中排隊等待服務的顧客數。 系統(tǒng)中顧客

13、數系統(tǒng)中顧客數L Ls s = =系統(tǒng)中排隊等待服務的顧客數系統(tǒng)中排隊等待服務的顧客數L Lq q + +正被正被服務的顧客數服務的顧客數c c (2)(2)平均逗留時間平均逗留時間(Ws)(Ws): :指一個顧客在系統(tǒng)中的停留時間。指一個顧客在系統(tǒng)中的停留時間。 平均等待時間平均等待時間(Wq(Wq) ): :指一個顧客在系統(tǒng)中排隊等待的時間。指一個顧客在系統(tǒng)中排隊等待的時間。 (3)(3)忙期忙期：指從顧客到達空閑服務機構起到服務機構再次為：指從顧客到達空閑服務機構起到服務機構再次為空閑這段時間長度。（忙期和一個忙期中平均完成服務顧客空閑這段時間長度。（忙期和一個忙期中平均完成服務顧客數都

14、是衡量服務機構效率的指標，忙期關系到工作強度）數都是衡量服務機構效率的指標，忙期關系到工作強度） 4. .排隊系統(tǒng)指標優(yōu)化排隊系統(tǒng)指標優(yōu)化 含優(yōu)化設計與優(yōu)化運營。含優(yōu)化設計與優(yōu)化運營。 問題問題1 1 系統(tǒng)中顧客數系統(tǒng)中顧客數= =平均隊列長（平均隊列長（L Lq q）+1+1？ 12 排隊系統(tǒng)的組成與特征排隊系統(tǒng)的組成與特征 排隊系統(tǒng)的模型分類排隊系統(tǒng)的模型分類 顧客到達間隔時間和服務時間的經驗分布與顧客到達間隔時間和服務時間的經驗分布與理論分布理論分布 穩(wěn)態(tài)概率穩(wěn)態(tài)概率P Pn n的計算的計算 標準的標準的M/M/1M/M/1模型模型( (M/M/1:/FCFS)/FCFS) 系統(tǒng)容量有限

15、制的系統(tǒng)容量有限制的模型模型M/M/1:N/FCFS/FCFS 顧客源有限模型顧客源有限模型M/M/1/M/M/ FCFSFCFS 標準的標準的M/M/CM/M/C模型模型M/M/C:/FCFS/FCFS13 M/M/C型系統(tǒng)和型系統(tǒng)和C個個M/M/1型系統(tǒng)型系統(tǒng) 系統(tǒng)容量有限制的多服務臺模型系統(tǒng)容量有限制的多服務臺模型(M/M/C/N/) 顧客源為有限的顧客源為有限的多服務臺模型多服務臺模型(M/M/C/M)(M/M/C/M) 一般服務時間的（一般服務時間的（M/G/1M/G/1）模型）模型 Pollaczek-Khintchine(P-K) 公式公式定長服務時間定長服務時間 M/D/1M/

16、D/1模型模型 愛爾朗服務時間愛爾朗服務時間M/Ek/1模型模型 排隊系統(tǒng)優(yōu)化排隊系統(tǒng)優(yōu)化 M/M/1 模型中的最優(yōu)服務率模型中的最優(yōu)服務率u 標準的標準的M/M/1Model 系統(tǒng)容量為系統(tǒng)容量為N的情形的情形 M/M/C模型中最優(yōu)服務臺數模型中最優(yōu)服務臺數C14 一個排隊系統(tǒng)的最主要特征參數是一個排隊系統(tǒng)的最主要特征參數是顧客的到達間隔時間分布與服務時間分顧客的到達間隔時間分布與服務時間分布。要研究到達間隔時間分布與服務時布。要研究到達間隔時間分布與服務時間分布需要首先根據現(xiàn)存系統(tǒng)原始資料間分布需要首先根據現(xiàn)存系統(tǒng)原始資料統(tǒng)計出它們的統(tǒng)計出它們的經驗分布經驗分布（見（見P315P31531

17、9319），），然后與理論分布然后與理論分布擬合擬合，若能照應，我們，若能照應，我們就可以得出上述的分布情況。就可以得出上述的分布情況。15 經驗分布是對排隊系統(tǒng)的某些時間參數根據經驗分布是對排隊系統(tǒng)的某些時間參數根據經驗數據進行統(tǒng)計分析，并依據統(tǒng)計分析結果假經驗數據進行統(tǒng)計分析，并依據統(tǒng)計分析結果假設其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法設其統(tǒng)計樣本的總體分布，選擇合適的檢驗方法進行檢驗，當通過檢驗時，我們認為時間參數的進行檢驗，當通過檢驗時，我們認為時間參數的經驗數據服從該假設分布。經驗數據服從該假設分布。 分布的擬合檢驗一般采用分布的擬合檢驗一般采用 2檢驗。由數理統(tǒng)檢驗。由數理統(tǒng)計的

18、知識我們知：若樣本量計的知識我們知：若樣本量n充分大充分大(n50)，則則當假設當假設H0為真時，統(tǒng)計量總是近似地服從自由度為真時，統(tǒng)計量總是近似地服從自由度為為k-r-1的的 2分布，其中分布，其中k為分組數，為分組數，r為檢驗分為檢驗分布中被估計的參數個數。布中被估計的參數個數。16tnnenttP !)( 式中式中為常數為常數(0)0)，稱，稱X X服從參數為服從參數為的泊松分布，的泊松分布，若在上式中引入時間參數若在上式中引入時間參數t t，即令，即令tt代替代替，則有：，則有： 在概率論中，我們曾學過泊松分布，設隨機變在概率論中，我們曾學過泊松分布，設隨機變量為量為X，則有：，則有：

19、!nenxPn n=0,1,2, （1） 與時間有關的隨機變量的概率與時間有關的隨機變量的概率，是一個，是一個隨機過程隨機過程，即即泊松過程泊松過程。 t0，n=0,1,2, （2）17)()(,1221ntNtNPttPn （t2t1，n0） 若設若設N(t)N(t)表示在時間區(qū)間表示在時間區(qū)間0,t)0,t)內到達的顧客數內到達的顧客數(t0),P(t0),Pn n(t(t1 1,t,t2 2) )表示在時間區(qū)間表示在時間區(qū)間tt1 1,t,t2 2)(t)(t2 2tt1 1) )內有內有n(0)n(0)個顧客到達的概率。即：個顧客到達的概率。即： 在一定的假設條件下在一定的假設條件下

20、顧客的到達過程就是顧客的到達過程就是一個泊松過程。一個泊松過程。 當當P Pn n(t(t1 1,t,t2 2) )符合下述三個條件時，顧客到達過程符合下述三個條件時，顧客到達過程就是泊松過程就是泊松過程( (顧客到達形成普阿松流顧客到達形成普阿松流) )。18 無后效性：無后效性：各區(qū)間的到達相互獨立各區(qū)間的到達相互獨立, ,即即MarkovMarkov性。性。. . . . . . . t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是說過程在也就是說過程在t+tt+t所處的狀態(tài)與所處的狀態(tài)與t

21、t以前所處的狀以前所處的狀態(tài)無態(tài)無關。關。 平穩(wěn)性：平穩(wěn)性：即對于足夠小的即對于足夠小的tt，有：，有：)()(tttttP ，1普阿松流具有如下特性：普阿松流具有如下特性： 在在t,t+tt,t+t內有一個顧客到達的概率與內有一個顧客到達的概率與t t無關無關, ,而與而與tt成正比。成正比。19 普通性：普通性：對充分小的對充分小的t,t,在時間區(qū)間（在時間區(qū)間（t,t+tt）內有內有2 2個或個或2 2個以上顧客到達的概率是一高階無窮小個以上顧客到達的概率是一高階無窮小. . 由此知，在由此知，在(t，t+t)t)區(qū)間內沒有顧客到達的概率為：區(qū)間內沒有顧客到達的概率為：)(1),(0to

22、ttttP 令令t1 1=0,t=0,t2 2=t,=t,則則P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t) 0 0 是常數，它是常數，它表示單位時間到達的顧客數，稱表示單位時間到達的顧客數，稱為概率強度。為概率強度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=1 在上述假設下，在上述假設下，t t時刻系統(tǒng)中有時刻系統(tǒng)中有n n個顧客的概率個顧客的概率p pn(tn(t) )： 20)()()(1tPtPdttdPnnn0)0(nP (1)(1)()(00tPdttdP1)0(0P (2)(2) 當當n=0時

23、，則時，則 te)t(P 0 (3)(3) （沒有顧客到達的概率）（沒有顧客到達的概率） （n n個顧客到達的概率）個顧客到達的概率）tnnenttP !)()( （4 4） 瞬態(tài)方瞬態(tài)方程程 （1 1）、（）、（2 2）兩式求導并令導數為）兩式求導并令導數為0 0，得穩(wěn)態(tài)概率：，得穩(wěn)態(tài)概率：21 級數級數.!nx.!xxenx 212 tkke!k)t( 0!)()()(11ntnetnPtNEnntnn )!1()(11 nttennt 令令k=n-1，則：，則：!)()(0kttetNEkkt tetetNEtt )(ttar )(N(V 同理方差為：同理方差為： 顧客到達過程是一個顧客

24、到達過程是一個泊松過程泊松過程( (泊松流泊松流) )。 期望期望22 表示單位時間內顧客平均到達數。表示單位時間內顧客平均到達數。 1/表示顧客到達的平均間隔時間。表示顧客到達的平均間隔時間。對顧客的服務時間對顧客的服務時間 ：系統(tǒng)處于忙期時系統(tǒng)處于忙期時兩顧客相繼離兩顧客相繼離開系統(tǒng)的時間間隔開系統(tǒng)的時間間隔，一般地也服從負指數分布，一般地也服從負指數分布， 1TE21 TVar 接受服務，然后離開接受服務，然后離開服務時間的分布：服務時間的分布： 可以證明可以證明當輸入過程是泊松流時，兩顧客相繼到當輸入過程是泊松流時，兩顧客相繼到達的時間間隔達的時間間隔T T獨立且服從負指數分布。（等價

25、）獨立且服從負指數分布。（等價）tetF 1)(tetf )( ，則，則23其中：其中：表示單位時間內能被服務的顧客數，即平均表示單位時間內能被服務的顧客數，即平均 服務率。服務率。 1/1/表示一個顧客的平均服務時間。表示一個顧客的平均服務時間。 設設v v1 1, v, v2 2，, v, vk k是是k k個獨立的隨機變量，服從相同個獨立的隨機變量，服從相同參數參數 k k 的負指數分布，那么：的負指數分布，那么：tetF 1)(tetf )( ，則，則 令令 ，則，則稱為服務強度稱為服務強度。kT 2124 串聯(lián)的串聯(lián)的k k個服務臺個服務臺，每臺服務時間相互獨立，服，每臺服務時間相互

26、獨立，服從相同的負指數分布（參數從相同的負指數分布（參數k k ），那么一顧客走完），那么一顧客走完k k個服務臺總共所需要服務時間就服從上述的個服務臺總共所需要服務時間就服從上述的k k階階ErlangErlang分布。分布。011 te)!k()kt(k)t (ftkkk 則稱則稱T服從服從k階階愛爾朗分布。其特征值為：愛爾朗分布。其特征值為： 1TE21 kTVar ,其概率密度是其概率密度是1/ k1/ k表示一個顧客的一個服務臺的平均服務時間。表示一個顧客的一個服務臺的平均服務時間。25 例例: :有易碎物品有易碎物品500500件件, ,由甲地運往乙地由甲地運往乙地, ,根據以根據

27、以往統(tǒng)計資料往統(tǒng)計資料, ,在運輸過程中易碎物品按普阿松流發(fā)在運輸過程中易碎物品按普阿松流發(fā)生破碎生破碎, ,其破損率為其破損率為0.002,0.002,現(xiàn)求現(xiàn)求:1.:1.破碎破碎3 3件物品的件物品的概率概率;2.;2.破碎少于破碎少于3 3件的概率和多于件的概率和多于3 3件的概率件的概率;3.;3.至少有一件破損的概率至少有一件破損的概率. . 解解: : =0.002500=1 1 1破碎破碎3 3件物品的概率為件物品的概率為: : P(k=3)=( P(k=3)=( 3 3/3/3！)e)e- - =(1=(13 3/3/3！)e)e-1-1=0.0613=0.0613 即物品破碎

28、即物品破碎3 3件的概率為件的概率為6.136.13 2. 2.破碎物品少于破碎物品少于3 3件的概率件的概率: :26 破碎物品少于破碎物品少于3 3件的概率為件的概率為91.9791.97 破碎物品多于破碎物品多于3 3件的概率為件的概率為: : 02. 098. 01!1330 kkekp 3.3.至少有一件破碎的概率為至少有一件破碎的概率為 PkPk 1=1-(11=1-(1k k/k!)e/k!)e- - =1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.632 9197. 021112120 eeknp27 對排隊模型，在給定輸入和服務條件下，主要對排隊模型，

29、在給定輸入和服務條件下，主要研究系統(tǒng)的下述運行指標：研究系統(tǒng)的下述運行指標： (1)(1)系統(tǒng)的系統(tǒng)的平均隊長平均隊長LsLs( (期望值期望值) )和和平均隊列長平均隊列長LqLq( (期望值期望值) )； (2)(2)系統(tǒng)中系統(tǒng)中顧客平均逗留時間顧客平均逗留時間WsWs與隊列中與隊列中平均等平均等待時間待時間WqWq； 本節(jié)只研究本節(jié)只研究M/M/1M/M/1模型，下面分三種情況討論：模型，下面分三種情況討論：28 系統(tǒng)中有系統(tǒng)中有n n個顧客個顧客M/M/1:/FCFS/FCFS模型模型 在任意時刻在任意時刻t t，狀態(tài)為，狀態(tài)為n n的概率的概率P Pn n(t(t) )（瞬態(tài)概率），

30、（瞬態(tài)概率），它決定了系統(tǒng)的運行特征。它決定了系統(tǒng)的運行特征。 已知顧客到達服從參數為已知顧客到達服從參數為的泊松過程，服務時的泊松過程，服務時間服從參數為間服從參數為的負指數分布?，F(xiàn)仍然通過研究區(qū)間的負指數分布。現(xiàn)仍然通過研究區(qū)間 t，t+tt）的變化來求解。在時刻）的變化來求解。在時刻t+tt，系統(tǒng)中有，系統(tǒng)中有n n個顧客不外乎有下列四種情況（個顧客不外乎有下列四種情況（ t，t+tt）內到達）內到達或離開或離開2 2個以上個以上沒列入）。沒列入）。 ？ 29區(qū)區(qū)間間( (t t, , t+t t) ) 情情況況 時時刻刻t t的的顧顧客客 到到達達 離離去去 時時刻刻t+t t的的顧顧

31、客客 ( (t t, , t+t t) )的的概概率率 0 0, , t+t t 的的概概率率 A n n 1-t+O(t) 1-t+O(t) Pn(1-t+O(t) （1-t+O(t)） B n+1 n 1-t+O(t) t+O(t) Pn+1(1-t+O(t) （t+O(t)） C n-1 n t+O(t) 1-t+O(t) Pn-1(t+O(t) （1-t+O(t)） D n n t+O(t) t+O(t) Pn(t+O(t) （t+O(t)） 由于這四種情況是互不相容的，所以由于這四種情況是互不相容的，所以Pn(t+t)t)應應是這四項之和，則有：是這四項之和，則有：tttPtttPt

32、ttPttPnnnn)1)()()1)(1)()(1)()1 ()(1tOtttPn 所有的高階無所有的高階無窮小合并窮小合并30) t(Ot) t (Pt) t (P) tt)(t (Pnnn 111t) t(O) t (P)() t (P) t (Pt) t (P) tt (Pnnnnn 11 令令t0t0，得關于，得關于P Pn n(t)(t)的微分差分方程：的微分差分方程：)()()()()(11tPtPtPdttdPnnnn (1) 當當n=0時，只有表中的（時，只有表中的（A）、（）、（B）兩種情況，）兩種情況，因為在較小的因為在較小的tt內不可能發(fā)生（內不可能發(fā)生（D D）（到達

33、后即離）（到達后即離去），若發(fā)生可將去），若發(fā)生可將tt取小即可。取小即可。)t()t)(t (P)t)(t (P)tt (P 11100 ) t (P) t (Pdt) t (dP100 (2)(2)生生滅滅過過程程瞬瞬態(tài)態(tài)解解31 由此可得該排隊系統(tǒng)的由此可得該排隊系統(tǒng)的狀態(tài)轉移圖狀態(tài)轉移圖： 由（由（4）得：）得：001PPP 其中其中服務強度服務強度 將其代入（將其代入（3）式并令）式并令n=1,2,(也可從狀態(tài)轉移也可從狀態(tài)轉移圖中看出狀態(tài)平衡方程圖中看出狀態(tài)平衡方程)得：得： 關于關于Pn的差的差分方程分方程 n-1n-1 n n n+1n+1 2 2 0 0 1 1 穩(wěn)態(tài)時，穩(wěn)態(tài)

34、時， 它 對 時它 對 時間的導數為間的導數為0，所以由，所以由(1)、(2)兩式得：兩式得： Pn(t)與時間無關與時間無關, 可以寫成可以寫成Pn,011 nnnP)(PP010 PP (3)(3) (4)(4)320120 P)(PP n=1n=10020 P)(PP 0202021PP)(P)(P n=2n=20231 P)(PP00230 P)(PP 0303022231PP)(P)(P 33 以此類推以此類推，當，當n=n時，時，00)(PPPnnn (5)(5)1 10 nnP 以及概率性質知：以及概率性質知：111000 PPnn (數列的極限為數列的極限為 ) 11 10Pnn)(P 1 (6)(6) 否則排隊無限遠否則排隊無限遠 系統(tǒng)系統(tǒng)穩(wěn)態(tài)穩(wěn)態(tài)概率概率系統(tǒng)的運行指標系統(tǒng)的運行指標34 (1) 系統(tǒng)中的隊長系統(tǒng)中的隊長Ls（平均隊長）（平均隊長） nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n (01) 1 Ls 即即: