運(yùn)籌學(xué)教案_排隊論1

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

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

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

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

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

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

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

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

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

10、間隔分布和服務(wù)時間分布( (可實測可實測) )。 2. 2. 研究研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。狀態(tài)概率用系統(tǒng)中顧客數(shù)。狀態(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)一般很快都能達(dá)到，但實際中達(dá)不能達(dá)到，但實際中達(dá)不到穩(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.根據(jù)排隊系統(tǒng)對應(yīng)的理論模型根據(jù)排隊系統(tǒng)對應(yīng)的理論模型求出用以判斷系統(tǒng)求出用以判斷系統(tǒng)運(yùn)行優(yōu)劣的基本數(shù)量指標(biāo)的概率分布或特征數(shù)。運(yùn)行優(yōu)劣的基本數(shù)量指標(biāo)的概率分布或特征數(shù)。 數(shù)量指標(biāo)主要包括數(shù)量指標(biāo)主要包括: : (1)(1)平均隊長（平均隊長（L Ls s）: :系統(tǒng)中的顧客數(shù)。系統(tǒng)中的顧客數(shù)。 平均隊列長（平均隊列長（L Lq q）: :系統(tǒng)中排隊等待服務(wù)的顧客數(shù)。系統(tǒng)中排隊等待服務(wù)的顧客數(shù)。 系統(tǒng)中顧客

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

14、是衡量服務(wù)機(jī)構(gòu)效率的指標(biāo)，忙期關(guān)系到工作強(qiáng)度）數(shù)都是衡量服務(wù)機(jī)構(gòu)效率的指標(biāo)，忙期關(guān)系到工作強(qiáng)度） 4. .排隊系統(tǒng)指標(biāo)優(yōu)化排隊系統(tǒng)指標(biāo)優(yōu)化 含優(yōu)化設(shè)計與優(yōu)化運(yùn)營。含優(yōu)化設(shè)計與優(yōu)化運(yùn)營。 問題問題1 1 系統(tǒng)中顧客數(shù)系統(tǒng)中顧客數(shù)= =平均隊列長（平均隊列長（L Lq q）+1+1？ 12 排隊系統(tǒng)的組成與特征排隊系統(tǒng)的組成與特征 排隊系統(tǒng)的模型分類排隊系統(tǒng)的模型分類 顧客到達(dá)間隔時間和服務(wù)時間的經(jīng)驗分布與顧客到達(dá)間隔時間和服務(wù)時間的經(jīng)驗分布與理論分布理論分布 穩(wěn)態(tài)概率穩(wěn)態(tài)概率P Pn n的計算的計算 標(biāo)準(zhǔn)的標(biāo)準(zhǔ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 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的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)容量有限制的多服務(wù)臺模型系統(tǒng)容量有限制的多服務(wù)臺模型(M/M/C/N/) 顧客源為有限的顧客源為有限的多服務(wù)臺模型多服務(wù)臺模型(M/M/C/M)(M/M/C/M) 一般服務(wù)時間的（一般服務(wù)時間的（M/G/1M/G/1）模型）模型 Pollaczek-Khintchine(P-K) 公式公式定長服務(wù)時間定長服務(wù)時間 M/D/1M/

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

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

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

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

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

21、t以前所處的狀以前所處的狀態(tài)無態(tài)無關(guān)。關(guān)。 平穩(wěn)性：平穩(wěn)性：即對于足夠小的即對于足夠小的tt，有：，有：)()(tttttP ，1普阿松流具有如下特性：普阿松流具有如下特性： 在在t,t+tt,t+t內(nèi)有一個顧客到達(dá)的概率與內(nèi)有一個顧客到達(dá)的概率與t t無關(guān)無關(guān), ,而與而與tt成正比。成正比。19 普通性：普通性：對充分小的對充分小的t,t,在時間區(qū)間（在時間區(qū)間（t,t+tt）內(nèi)有內(nèi)有2 2個或個或2 2個以上顧客到達(dá)的概率是一高階無窮小個以上顧客到達(dá)的概率是一高階無窮小. . 由此知，在由此知，在(t，t+t)t)區(qū)間內(nèi)沒有顧客到達(dá)的概率為：區(qū)間內(nèi)沒有顧客到達(dá)的概率為：)(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 是常數(shù)，它是常數(shù)，它表示單位時間到達(dá)的顧客數(shù)，稱表示單位時間到達(dá)的顧客數(shù)，稱為概率強(qiáng)度。為概率強(qiáng)度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=1 在上述假設(shè)下，在上述假設(shè)下，t t時刻系統(tǒng)中有時刻系統(tǒng)中有n n個顧客的概率個顧客的概率p pn(tn(t) )： 20)()()(1tPtPdttdPnnn0)0(nP (1)(1)()(00tPdttdP1)0(0P (2)(2) 當(dāng)當(dāng)n=0時

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

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

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

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

27、以往統(tǒng)計資料往統(tǒng)計資料, ,在運(yùn)輸過程中易碎物品按普阿松流發(fā)在運(yùn)輸過程中易碎物品按普阿松流發(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 對排隊模型，在給定輸入和服務(wù)條件下，主要對排隊模型，

29、在給定輸入和服務(wù)條件下，主要研究系統(tǒng)的下述運(yùn)行指標(biāo)：研究系統(tǒng)的下述運(yùn)行指標(biāo)： (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)的運(yùn)行特征。它決定了系統(tǒng)的運(yùn)行特征。 已知顧客到達(dá)服從參數(shù)為已知顧客到達(dá)服從參數(shù)為的泊松過程，服務(wù)時的泊松過程，服務(wù)時間服從參數(shù)為間服從參數(shù)為的負(fù)指數(shù)分布?，F(xiàn)仍然通過研究區(qū)間的負(fù)指數(shù)分布?，F(xiàn)仍然通過研究區(qū)間 t，t+tt）的變化來求解。在時刻）的變化來求解。在時刻t+tt，系統(tǒng)中有，系統(tǒng)中有n n個顧客不外乎有下列四種情況（個顧客不外乎有下列四種情況（ t，t+tt）內(nèi)到達(dá)）內(nèi)到達(dá)或離開或離開2 2個以上個以上沒列入）。沒列入）。 ？ 29區(qū)區(qū)間間( (t t, , t+t t) ) 情情況況 時時刻刻t t的的顧顧客客 到到達(dá)達(dá) 離離去去 時時刻刻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)應(yīng)應(yīng)是這四項之和，則有：是這四項之和，則有：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，得關(guān)于，得關(guān)于P Pn n(t)(t)的微分差分方程：的微分差分方程：)()()()()(11tPtPtPdttdPnnnn (1) 當(dāng)當(dāng)n=0時，只有表中的（時，只有表中的（A）、（）、（B）兩種情況，）兩種情況，因為在較小的因為在較小的tt內(nèi)不可能發(fā)生（內(nèi)不可能發(fā)生（D D）（到達(dá)

33、后即離）（到達(dá)后即離去），若發(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)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖： 由（由（4）得：）得：001PPP 其中其中服務(wù)強(qiáng)度服務(wù)強(qiáng)度 將其代入（將其代入（3）式并令）式并令n=1,2,(也可從狀態(tài)轉(zhuǎn)移也可從狀態(tài)轉(zhuǎn)移圖中看出狀態(tài)平衡方程圖中看出狀態(tài)平衡方程)得：得： 關(guān)于關(guān)于Pn的差的差分方程分方程 n-1n-1 n n n+1n+1 2 2 0 0 1 1 穩(wěn)態(tài)時，穩(wěn)態(tài)

34、時， 它 對 時它 對 時間的導(dǎo)數(shù)為間的導(dǎo)數(shù)為0，所以由，所以由(1)、(2)兩式得：兩式得： Pn(t)與時間無關(guān)與時間無關(guān), 可以寫成可以寫成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 以此類推以此類推，當(dāng)，當(dāng)n=n時，時，00)(PPPnnn (5)(5)1 10 nnP 以及概率性質(zhì)知：以及概率性質(zhì)知：111000 PPnn (數(shù)列的極限為數(shù)列的極限為 ) 11 10Pnn)(P 1 (6)(6) 否則排隊無限遠(yuǎn)否則排隊無限遠(yuǎn) 系統(tǒng)系統(tǒng)穩(wěn)態(tài)穩(wěn)態(tài)概率概率系統(tǒng)的運(yùn)行指標(biāo)系統(tǒng)的運(yùn)行指標(biāo)34 (1) 系統(tǒng)中的隊長系統(tǒng)中的隊長Ls（平均隊長）（平均隊長） nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n (01) 1 Ls 即即: