數(shù)學(xué)建模排隊論模型PPT學(xué)習(xí)教案

1、數(shù)學(xué)建模排隊論模型數(shù)學(xué)建模排隊論模型排隊論模型排隊論模型 一、排隊論的基本概念一、排隊論的基本概念 二、單通道等待制排隊問題二、單通道等待制排隊問題 （MM1排隊系統(tǒng)）排隊系統(tǒng)）三、多通道等待制排隊問題三、多通道等待制排隊問題 （MMc排隊系統(tǒng)）排隊系統(tǒng)） 第1頁/共48頁一、排隊論的基本概念一、排隊論的基本概念（一）排隊過程（一）排隊過程 1.1.排隊系統(tǒng)排隊系統(tǒng) “排隊排隊”是指在服務(wù)機(jī)構(gòu)處要求服務(wù)對象的一個是指在服務(wù)機(jī)構(gòu)處要求服務(wù)對象的一個等待隊列，而等待隊列，而“排隊論排隊論”則是研究各種排隊現(xiàn)象的則是研究各種排隊現(xiàn)象的理論。理論。 到來 服服務(wù)務(wù)規(guī)規(guī)則則 服服 離離去去 顧顧客客源源

2、 排排隊隊機(jī)機(jī)構(gòu)構(gòu) 務(wù)務(wù) 機(jī)機(jī) 構(gòu)構(gòu) 排排隊隊系系統(tǒng)統(tǒng) 第2頁/共48頁 在排隊論中，我們把要求服務(wù)的對象稱為在排隊論中，我們把要求服務(wù)的對象稱為“顧客顧客”，而將從事服務(wù)的機(jī)構(gòu)或人稱為，而將從事服務(wù)的機(jī)構(gòu)或人稱為“服務(wù)服務(wù)臺臺”。 在顧客到達(dá)服務(wù)臺時，可能立即得到服在顧客到達(dá)服務(wù)臺時，可能立即得到服務(wù)，也可能要等待到可以利用服務(wù)臺的時候為止。務(wù)，也可能要等待到可以利用服務(wù)臺的時候為止。第3頁/共48頁 排隊系統(tǒng)隊列除了有形的還有無形的排隊系統(tǒng)隊列除了有形的還有無形的。 排隊系統(tǒng)中的排隊系統(tǒng)中的“顧客顧客”與與“服務(wù)臺服務(wù)臺”這兩個名這兩個名詞可以從不同的角度去理解。詞可以從不同的角度去理解。

3、排隊系統(tǒng)排隊系統(tǒng)顧客顧客服務(wù)臺服務(wù)臺上、下班的工人乘公共汽車上、下班的工人乘公共汽車工人工人公共汽車公共汽車病人到醫(yī)院看病病人到醫(yī)院看病病人病人醫(yī)生醫(yī)生高炮擊退敵機(jī)高炮擊退敵機(jī)敵機(jī)敵機(jī)高炮高炮機(jī)器發(fā)生故障需要維修機(jī)器發(fā)生故障需要維修機(jī)器機(jī)器修理工修理工第4頁/共48頁 在上述顧客在上述顧客- -服務(wù)臺組成的排隊系統(tǒng)中，顧客到服務(wù)臺組成的排隊系統(tǒng)中，顧客到來的時刻與服務(wù)臺進(jìn)行服務(wù)的時間一般來說是隨不來的時刻與服務(wù)臺進(jìn)行服務(wù)的時間一般來說是隨不同的時機(jī)與條件而變化的，往往預(yù)先無法確定。因同的時機(jī)與條件而變化的，往往預(yù)先無法確定。因此，系統(tǒng)的狀態(tài)是隨機(jī)的，故而排隊論也稱此，系統(tǒng)的狀態(tài)是隨機(jī)的，故而排

4、隊論也稱隨機(jī)服隨機(jī)服務(wù)系統(tǒng)務(wù)系統(tǒng)。第5頁/共48頁 各式各樣的排隊現(xiàn)象呈現(xiàn)的基本特征：排隊系統(tǒng)各式各樣的排隊現(xiàn)象呈現(xiàn)的基本特征：排隊系統(tǒng)由輸入過程、排隊規(guī)則及服務(wù)機(jī)構(gòu)三部分組成。由輸入過程、排隊規(guī)則及服務(wù)機(jī)構(gòu)三部分組成。(1)(1)輸入過程輸入過程 輸入過程就是顧客按怎樣的規(guī)律到達(dá)，它首先應(yīng)輸入過程就是顧客按怎樣的規(guī)律到達(dá)，它首先應(yīng)包括顧客總體數(shù)，是有限的還是無限的；其次應(yīng)說明包括顧客總體數(shù)，是有限的還是無限的；其次應(yīng)說明顧客到達(dá)的方式，是成批到達(dá)顧客到達(dá)的方式，是成批到達(dá)( (每批數(shù)量是隨機(jī)的還每批數(shù)量是隨機(jī)的還是確定性的是確定性的) )還是單個到達(dá)；最后應(yīng)說明相繼到達(dá)的還是單個到達(dá)；最后應(yīng)

5、說明相繼到達(dá)的顧客顧客( (或批或單個或批或單個) )之間的時間間隔的分布是什么。之間的時間間隔的分布是什么。 2.2.排隊系統(tǒng)的組成和特征排隊系統(tǒng)的組成和特征第6頁/共48頁 排隊規(guī)則是指到達(dá)的顧客以怎樣的規(guī)則接受服務(wù)。排隊規(guī)則是指到達(dá)的顧客以怎樣的規(guī)則接受服務(wù)。 1 1）損失制：）損失制：顧客到達(dá)，服務(wù)臺不空立即離去，顧客到達(dá)，服務(wù)臺不空立即離去，另求服務(wù)。另求服務(wù)。 2 2）等待制：）等待制：顧客到達(dá)，排隊等待。對等待制服顧客到達(dá)，排隊等待。對等待制服務(wù)可分為：先到先服務(wù)，后到先服務(wù)，優(yōu)先服務(wù)，隨務(wù)可分為：先到先服務(wù)，后到先服務(wù)，優(yōu)先服務(wù)，隨機(jī)服務(wù)，成批服務(wù)等。機(jī)服務(wù)，成批服務(wù)等。 3

6、3）混合制：）混合制：在現(xiàn)實生活中，很多服務(wù)系統(tǒng)介于在現(xiàn)實生活中，很多服務(wù)系統(tǒng)介于損失制和等待制之間，當(dāng)顧客到達(dá)時，服務(wù)臺不空就損失制和等待制之間，當(dāng)顧客到達(dá)時，服務(wù)臺不空就排隊，若排隊的位置已滿就離去。排隊，若排隊的位置已滿就離去。 (2)(2)排隊規(guī)則排隊規(guī)則第7頁/共48頁 服務(wù)機(jī)構(gòu)主要指服務(wù)臺的數(shù)目，多個服務(wù)服務(wù)機(jī)構(gòu)主要指服務(wù)臺的數(shù)目，多個服務(wù)臺進(jìn)行服務(wù)時，服務(wù)方式是并聯(lián)還是串聯(lián)；服臺進(jìn)行服務(wù)時，服務(wù)方式是并聯(lián)還是串聯(lián)；服務(wù)時間服從什么分布等。務(wù)時間服從什么分布等。 (3)(3)服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)第8頁/共48頁 1.1.排隊模型的分類排隊模型的分類 D.G.KendallD.G.Ken

7、dall引進(jìn)了排隊模型分類符號，現(xiàn)已廣引進(jìn)了排隊模型分類符號，現(xiàn)已廣泛采用，這里僅針對并列的服務(wù)臺。泛采用，這里僅針對并列的服務(wù)臺。 記記X X：顧客到達(dá)的時間間隔分布；顧客到達(dá)的時間間隔分布；Y Y：服務(wù)時間的服務(wù)時間的分布；分布；Z Z：服務(wù)臺數(shù)。則排隊模型：服務(wù)臺數(shù)。則排隊模型：X XY YZ Z。 常用的記號：常用的記號：M M負(fù)指數(shù)分布；負(fù)指數(shù)分布；D D確定型；確定型；EkEkk k階愛爾朗（階愛爾朗（ErlangErlang）分布；分布；GIGI一般相互獨(dú)立的隨一般相互獨(dú)立的隨機(jī)分布，機(jī)分布，G G一般隨機(jī)分布。這里主要討論一般隨機(jī)分布。這里主要討論M MM M1 1，M MM

8、MC C。（二）排隊模型的分類及數(shù)量指標(biāo)（二）排隊模型的分類及數(shù)量指標(biāo)第9頁/共48頁 (1)(1)隊長隊長 隊長是指系統(tǒng)中的顧客數(shù)隊長是指系統(tǒng)中的顧客數(shù)( (包括排隊等候和正包括排隊等候和正在接受服務(wù)的顧客數(shù)在接受服務(wù)的顧客數(shù)) )；等待隊長是指系統(tǒng)中等待；等待隊長是指系統(tǒng)中等待服務(wù)的顧客數(shù)。無論是隊長還是等待隊長，都是顧服務(wù)的顧客數(shù)。無論是隊長還是等待隊長，都是顧客和服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指標(biāo)，特別是對系統(tǒng)設(shè)客和服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指標(biāo)，特別是對系統(tǒng)設(shè)計者來說，尤為重要，因為它涉及到系統(tǒng)等待空間計者來說，尤為重要，因為它涉及到系統(tǒng)等待空間的大小。的大小。2.2.排隊模型的數(shù)量指標(biāo)排隊模型的數(shù)

9、量指標(biāo)第10頁/共48頁 逗留時間是指一顧客從進(jìn)入系統(tǒng)起一直到接受逗留時間是指一顧客從進(jìn)入系統(tǒng)起一直到接受服務(wù)后離開系統(tǒng)為止所花費(fèi)的時間；等待時間是指服務(wù)后離開系統(tǒng)為止所花費(fèi)的時間；等待時間是指一顧客從進(jìn)入系統(tǒng)起到接受服務(wù)時所花費(fèi)的時間。一顧客從進(jìn)入系統(tǒng)起到接受服務(wù)時所花費(fèi)的時間。顯然，一個顧客的逗留時間等于其等待時間與接受顯然，一個顧客的逗留時間等于其等待時間與接受服務(wù)的時間之和。逗留時間與等待時間對顧客來說服務(wù)的時間之和。逗留時間與等待時間對顧客來說是最關(guān)心的，因為每個顧客都希望自己用于排隊等是最關(guān)心的，因為每個顧客都希望自己用于排隊等待的時間愈短愈好。待的時間愈短愈好。 (2)(2)逗留

10、時間逗留時間第11頁/共48頁 忙期是指從顧客到達(dá)空閑服務(wù)機(jī)構(gòu)起到服務(wù)機(jī)構(gòu)忙期是指從顧客到達(dá)空閑服務(wù)機(jī)構(gòu)起到服務(wù)機(jī)構(gòu)再次為空閑為止的這段時間，即服務(wù)機(jī)構(gòu)連續(xù)繁忙再次為空閑為止的這段時間，即服務(wù)機(jī)構(gòu)連續(xù)繁忙的時間長度。這是服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指標(biāo)，因的時間長度。這是服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指標(biāo)，因為它直接關(guān)系到服務(wù)員的工作強(qiáng)度，與忙期相對應(yīng)為它直接關(guān)系到服務(wù)員的工作強(qiáng)度，與忙期相對應(yīng)的是閑期，即為服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時間長度。的是閑期，即為服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時間長度。顯然，在排隊系統(tǒng)中，忙期與閑期是交錯出現(xiàn)的。顯然，在排隊系統(tǒng)中，忙期與閑期是交錯出現(xiàn)的。 (3)(3)忙期忙期第12頁/共48頁

11、1.1.最簡單流與最簡單流與PoissonPoisson過程過程 記隨機(jī)過程記隨機(jī)過程x x（t t）：）：t0t0為時間為時間0 0，t t內(nèi)流內(nèi)流( (事件事件) )發(fā)生的次數(shù)，例如對于隨機(jī)到來某電話發(fā)生的次數(shù)，例如對于隨機(jī)到來某電話交換臺的呼叫，以交換臺的呼叫，以x x（t t）表示該交換臺在表示該交換臺在0 0，t t這段時間內(nèi)收到呼叫的次數(shù)；若是服務(wù)機(jī)構(gòu)，可以這段時間內(nèi)收到呼叫的次數(shù)；若是服務(wù)機(jī)構(gòu)，可以用用x x（t t）表示該機(jī)構(gòu)在表示該機(jī)構(gòu)在0 0，t t時間內(nèi)來到的顧客時間內(nèi)來到的顧客數(shù)數(shù)。（三）（三）PoissonPoisson流與指數(shù)分布流與指數(shù)分布第13頁/共48頁最簡單

12、流應(yīng)最簡單流應(yīng) 具有以下特征稱具有以下特征稱0: )(ttx(1)(1)流具有平衡性流具有平衡性 對任何對任何 和和 , , 的分布只取決于的分布只取決于 而與而與 無關(guān)。無關(guān)。(2)(2)流具有無后效性流具有無后效性對互不交接的時間區(qū)間序列對互不交接的時間區(qū)間序列 ， 是一組相互獨(dú)立的隨機(jī)變量。是一組相互獨(dú)立的隨機(jī)變量。(3)(3)流具有普通性流具有普通性即在即在 時間內(nèi)，事件發(fā)生多于時間內(nèi)，事件發(fā)生多于1 1次的概率為次的概率為 。 0anttt210)1 ()()(niaxtaxinttt,21a)1 (,nibaii)()(iiaxbx01)()(Prlimtaxtaxtt)( to

13、第14頁/共48頁定理定理1 1設(shè)設(shè) 是最簡單流，則對任何是最簡單流，則對任何 和和都有都有 我們把滿足這一分布規(guī)律的隨機(jī)過程我們把滿足這一分布規(guī)律的隨機(jī)過程稱為稱為PoissonPoisson過程，最簡單流亦稱過程，最簡單流亦稱PoissonPoisson流，特別取流，特別取 得得故參數(shù)故參數(shù)表示單位時間內(nèi)事件發(fā)生次數(shù)的平均數(shù)表示單位時間內(nèi)事件發(fā)生次數(shù)的平均數(shù)。0: )(ttx0a0t), 2 , 1 , 0(!)()()(Prkekkkaxtaxtk0: )(ttx), 2 , 1 , 0(!)()(Prkekkktxtk0attxE)(第15頁/共48頁2.2.PoissonPoisso

14、n流的發(fā)生時間間隔分布流的發(fā)生時間間隔分布 當(dāng)流當(dāng)流( (過程過程) ) 構(gòu)成構(gòu)成PoissonPoisson過程時，就過程時，就稱 為稱 為 P o i s s o nP o i s s o n 流 。 設(shè) 流 發(fā) 生 的 時 刻 依 次流 。 設(shè) 流 發(fā) 生 的 時 刻 依 次為為 , ,，發(fā)生的時間間隔記為發(fā)生的時間間隔記為 ，其中其中 。定理定理2 2 事件流事件流 為為PoissonPoisson流的充要條件是流的充要條件是 的流發(fā)生時間間隔的流發(fā)生時間間隔 相互獨(dú)立，且服相互獨(dú)立，且服從相同的負(fù)指數(shù)分布，即從相同的負(fù)指數(shù)分布，即0: )(ttxnttt,21), 2 , 1(1nt

15、tnnn00t0: )(ttx0: )(ttx n0001Prttettn第16頁/共48頁3.3.負(fù)指數(shù)分布的負(fù)指數(shù)分布的MarkovMarkov特性特性定理定理3 3設(shè)設(shè)T T為連續(xù)型隨機(jī)變量，且為連續(xù)型隨機(jī)變量，且T0T0，那么，那么，T T服從服從負(fù)指數(shù)分布的充要條件是：對任何負(fù)指數(shù)分布的充要條件是：對任何 ，都有，都有上式可改寫為：對任何上式可改寫為：對任何 ，都有，都有 如果把如果把T T解釋為壽命，上式表明：如果已知年齡解釋為壽命，上式表明：如果已知年齡大于大于 歲，則再活歲，則再活x x年的概率與以前的年的概率與以前的 ( (年年) )無關(guān)，無關(guān)，所以有時又風(fēng)趣地稱指數(shù)分布是所

16、以有時又風(fēng)趣地稱指數(shù)分布是“永遠(yuǎn)年輕永遠(yuǎn)年輕”。 上面兩式表明連續(xù)型隨機(jī)變量上面兩式表明連續(xù)型隨機(jī)變量T T的的MarkovMarkov特性當(dāng)特性當(dāng)且僅當(dāng)非負(fù)隨機(jī)變量服從負(fù)指數(shù)分布時才具有。且僅當(dāng)非負(fù)隨機(jī)變量服從負(fù)指數(shù)分布時才具有。001tt0101PrPrttTtTtTxTtTxtTPrPr0000t0t0t第17頁/共48頁例例1 1 設(shè)某一服務(wù)系統(tǒng)的輸入流是設(shè)某一服務(wù)系統(tǒng)的輸入流是PoissonPoisson流，平均流，平均每每3 3分鐘進(jìn)入分鐘進(jìn)入5 5名顧客，試計算：名顧客，試計算：(1)12(1)12分鐘內(nèi)進(jìn)入分鐘內(nèi)進(jìn)入1515名顧客的概率；名顧客的概率；(2)(2)輸入時間間隔大

17、于輸入時間間隔大于1 1分鐘的概率。分鐘的概率。解解(1)(1)由于由于 ，在在0 0，t t內(nèi)進(jìn)入內(nèi)進(jìn)入k k名顧客的概名顧客的概率率 于是于是1212分鐘內(nèi)進(jìn)入分鐘內(nèi)進(jìn)入1515名顧客的概率名顧客的概率35), 2 , 1 , 0(!)()(Prkekkktxtk0516. 0)1235(!15115)12(Pr123515ex第18頁/共48頁(2)(2)由于輸入時間間隔由于輸入時間間隔服從參數(shù)為服從參數(shù)為的指數(shù)分布的指數(shù)分布則所求概率為則所求概率為0001Prttettn1888. 01Pr35en第19頁/共48頁 對于單通道等待制排隊問題主要討論輸入過對于單通道等待制排隊問題主要討

18、論輸入過程為程為PoissonPoisson流，服務(wù)時間服從負(fù)指數(shù)分布，單服流，服務(wù)時間服從負(fù)指數(shù)分布，單服務(wù)臺的情形，即務(wù)臺的情形，即M MM M1 1排隊系統(tǒng)。排隊系統(tǒng)。（一）標(biāo)準(zhǔn)模型（一）標(biāo)準(zhǔn)模型 即為即為M MM M1 1排隊系統(tǒng)。所謂標(biāo)準(zhǔn)模型，排隊系統(tǒng)。所謂標(biāo)準(zhǔn)模型，就是顧客的輸入流是參數(shù)為就是顧客的輸入流是參數(shù)為的的PoissonPoisson流，每個流，每個顧客的服務(wù)時間是相互獨(dú)立的且服從參數(shù)為顧客的服務(wù)時間是相互獨(dú)立的且服從參數(shù)為的的負(fù)指數(shù)分布，單個服務(wù)臺且系統(tǒng)的容量無限負(fù)指數(shù)分布，單個服務(wù)臺且系統(tǒng)的容量無限( (排隊排隊模型分類第四個表示系統(tǒng)中允許的最大顧客數(shù)模型分類第四個表

19、示系統(tǒng)中允許的最大顧客數(shù)) )。二、單通道等待制排隊問題二、單通道等待制排隊問題 （MMMM1 1排隊系統(tǒng)）排隊系統(tǒng)）第20頁/共48頁1.1.系統(tǒng)的系統(tǒng)的MarkovMarkov特性特性 考慮隨機(jī)過程考慮隨機(jī)過程 ，其中其中 為時刻為時刻 時時排隊系統(tǒng)中的顧客數(shù)。排隊系統(tǒng)中的顧客數(shù)。 對于任何對于任何 條件概率條件概率由于輸入為由于輸入為PoissonPoisson流，服務(wù)時間服從負(fù)指數(shù)分布，流，服務(wù)時間服從負(fù)指數(shù)分布，則無論則無論 在在 處取何值，上式條件概率僅依處取何值，上式條件概率僅依賴于賴于 的值和區(qū)間的值和區(qū)間 的長度的長度 ，即即0: )(ttx)(txtnttt21011221

20、1)(,)(,)()(Prnnnnitxitxitxitx)(txnttt,21)(1ntx),(1nntt1nntt11112211)()(Pr)(,)(,)()(Prnnnnnnnnitxitxitxitxitxitx第21頁/共48頁 直觀地說，如果知道現(xiàn)在時刻直觀地說，如果知道現(xiàn)在時刻 時系統(tǒng)的顧時系統(tǒng)的顧客數(shù)狀況，那么從概率意義上來說，將來時刻客數(shù)狀況，那么從概率意義上來說，將來時刻 時時系統(tǒng)的顧客數(shù)狀況，與過去時刻系統(tǒng)的顧客數(shù)狀況，與過去時刻 時顧時顧客數(shù)的狀況無關(guān)。這個特性就是隨機(jī)過程客數(shù)的狀況無關(guān)。這個特性就是隨機(jī)過程的的MarkovMarkov特性。特性。 我們把系統(tǒng)在某一時

21、刻的顧客數(shù)看做系統(tǒng)在這我們把系統(tǒng)在某一時刻的顧客數(shù)看做系統(tǒng)在這個時刻的狀態(tài)。根據(jù)系統(tǒng)狀態(tài)個時刻的狀態(tài)。根據(jù)系統(tǒng)狀態(tài) 的的MarkovMarkov特性，特性，容易研究在時間區(qū)間容易研究在時間區(qū)間 內(nèi)系統(tǒng)狀態(tài)的轉(zhuǎn)移概內(nèi)系統(tǒng)狀態(tài)的轉(zhuǎn)移概率，為研究系統(tǒng)在任一時刻的狀態(tài)分布提供工具率，為研究系統(tǒng)在任一時刻的狀態(tài)分布提供工具。1ntnt221,nttt0: )(ttx)(tx),(ttt第22頁/共48頁 記時刻記時刻t t系統(tǒng)處于狀態(tài)系統(tǒng)處于狀態(tài)n n的概率的概率利用利用M MM M1 1對輸入與服務(wù)時間分布的假設(shè)，在時對輸入與服務(wù)時間分布的假設(shè)，在時間區(qū)間間區(qū)間 內(nèi)，新進(jìn)入或離開顧客個數(shù)有以下結(jié)果：內(nèi)

22、，新進(jìn)入或離開顧客個數(shù)有以下結(jié)果： 內(nèi)沒有顧客進(jìn)入內(nèi)沒有顧客進(jìn)入 內(nèi)新進(jìn)入一名顧客內(nèi)新進(jìn)入一名顧客 內(nèi)多于一名顧客進(jìn)入內(nèi)多于一名顧客進(jìn)入 內(nèi)沒有顧客離開內(nèi)沒有顧客離開 內(nèi)有一名顧客離開內(nèi)有一名顧客離開 內(nèi)多于一名顧客離開內(nèi)多于一名顧客離開2.2.排隊系統(tǒng)的穩(wěn)態(tài)解排隊系統(tǒng)的穩(wěn)態(tài)解ntxtPn)(Pr)(),(ttt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt第23頁/共48頁 當(dāng)當(dāng) 時有時有導(dǎo)出導(dǎo)出 滿足的微分方程組滿足的微分方程組)(tpn)()1 ()()1)(

23、)(100totttpttpttp)()()()()(1000tottpttptpttp0t)()()(100tptptp第24頁/共48頁故故 滿足的微分方程組滿足的微分方程組)()()1)(1)()()(11tottptttpttpttpnnnn)()()()()(11tptptptpnnnn對對1n)()()(, 2 , 1)()()()()(10011tptptpntptptptpnnnn)(tpn第25頁/共48頁 對于系統(tǒng)的穩(wěn)定狀態(tài)情形，對于系統(tǒng)的穩(wěn)定狀態(tài)情形， 與與t t無關(guān)，無關(guān)，故故 ，記記 ，從而有從而有對于上述差分方程，利用歸納法不難求得對于上述差分方程，利用歸納法不難求

24、得)(tpn0)( tpn)(tppnn0, 2 , 10)(1011ppnpppnnn0)(ppnn第26頁/共48頁 記記 為排隊系統(tǒng)的來往強(qiáng)度，當(dāng)為排隊系統(tǒng)的來往強(qiáng)度，當(dāng) 時，由時，由 可得可得 由于由于 構(gòu)成概率分布，則構(gòu)成概率分布，則 ，從而級數(shù)從而級數(shù) 必須收斂，故有必須收斂，故有 。 np01nnp0)(nn1101nnp, 2 , 1 , 0)1 (npnn第27頁/共48頁MMMM1 1系統(tǒng)的數(shù)量指標(biāo)系統(tǒng)的數(shù)量指標(biāo) (1)(1)穩(wěn)定狀態(tài)下系統(tǒng)中顧客數(shù)的數(shù)學(xué)期望的定義穩(wěn)定狀態(tài)下系統(tǒng)中顧客數(shù)的數(shù)學(xué)期望的定義為為被稱為系統(tǒng)中顧客的平均數(shù)，簡稱被稱為系統(tǒng)中顧客的平均數(shù)，簡稱平均隊長平

25、均隊長。 0nnnpL1)(1(1000nnnnnnnnpL1)1(2000nnnnnnqpnppnL 穩(wěn)定狀態(tài)下系統(tǒng)中等待服務(wù)顧客數(shù)的數(shù)學(xué)期望，穩(wěn)定狀態(tài)下系統(tǒng)中等待服務(wù)顧客數(shù)的數(shù)學(xué)期望，簡稱平均簡稱平均等待隊長等待隊長。第28頁/共48頁 (2)(2)顧客在系統(tǒng)中的顧客在系統(tǒng)中的平均逗留時間平均逗留時間則顧客在系統(tǒng)中的則顧客在系統(tǒng)中的平均等待時間平均等待時間 可以證明，顧客在系統(tǒng)中逗留時間服從參數(shù)為可以證明，顧客在系統(tǒng)中逗留時間服從參數(shù)為-的負(fù)指數(shù)分布。的負(fù)指數(shù)分布。1)(11q第29頁/共48頁 與與 是衡量排隊系統(tǒng)質(zhì)量的很重要的效是衡量排隊系統(tǒng)質(zhì)量的很重要的效率度量，它們之間有著有趣的聯(lián)

26、系：率度量，它們之間有著有趣的聯(lián)系：上式稱為上式稱為LittleLittle公式。公式。 對對M MM M1 1排隊系統(tǒng)，它有著明顯的直觀排隊系統(tǒng)，它有著明顯的直觀意義：從平均意義來說，意義：從平均意義來說， 表明系統(tǒng)中的顧客表明系統(tǒng)中的顧客數(shù)，等于一個顧客在系統(tǒng)時間內(nèi)來到的新的顧客數(shù)；數(shù)，等于一個顧客在系統(tǒng)時間內(nèi)來到的新的顧客數(shù)； 表明系統(tǒng)中處于等待狀態(tài)的顧客數(shù)，等于表明系統(tǒng)中處于等待狀態(tài)的顧客數(shù)，等于一個顧客的等待時間內(nèi)來到的新顧客數(shù)。一個顧客的等待時間內(nèi)來到的新顧客數(shù)。 LittleLittle公式公式qqLLLqqLqLL,q,第30頁/共48頁(3)(3)穩(wěn)定狀態(tài)下穩(wěn)定狀態(tài)下忙期忙期

27、的數(shù)學(xué)期望的數(shù)學(xué)期望由此可見，一個忙期中所服務(wù)顧客的平均數(shù)為由此可見，一個忙期中所服務(wù)顧客的平均數(shù)為1)(TE忙忙11)(TE第31頁/共48頁 例例2 2（病人候診問題）某單位醫(yī)院的一個科室有（病人候診問題）某單位醫(yī)院的一個科室有一位醫(yī)生值班，經(jīng)長期觀察，每小時平均有一位醫(yī)生值班，經(jīng)長期觀察，每小時平均有4 4個病人，個病人，醫(yī)生每小時平均可診斷醫(yī)生每小時平均可診斷5 5人，病人的到來服從人，病人的到來服從PoissonPoisson流，診病時間服從負(fù)指數(shù)分布，試分析該科流，診病時間服從負(fù)指數(shù)分布，試分析該科室的工作狀況，如要求室的工作狀況，如要求99%99%以上的病人有座，該科室以上的病人

28、有座，該科室至少設(shè)多少座位至少設(shè)多少座位? ?如果該單位每天如果該單位每天2424小時上班，病人小時上班，病人因看病因看病1 1小時而耽誤工作單位要損失小時而耽誤工作單位要損失3030元，這樣單位元，這樣單位平均損失多少元平均損失多少元? ?如果該科室提高看病速度，每小時如果該科室提高看病速度，每小時平均可診平均可診6 6人，單位每天可減少損失多少人，單位每天可減少損失多少? ?可減少多可減少多少座位少座位? ?第32頁/共48頁 解：解： 由題意可知，由題意可知， 則則該科室平均有病人數(shù)該科室平均有病人數(shù) ( (人人) )該科室平均等待的病人數(shù)該科室平均等待的病人數(shù) （人人) )看一次病平均

29、所需的時間看一次病平均所需的時間 （小時（小時) )看一次病平均所需的等待時間看一次病平均所需的等待時間 ( (小小時時) )醫(yī)生的忙期醫(yī)生的忙期 ( (小時小時) )一個忙期中平均看病人數(shù)一個忙期中平均看病人數(shù) (人)8 . 054, 5, 4, 2 , 1 , 08 . 02 . 0)1 (npnnn2.3)1(2qL1L4)1(L8 .0qqL忙忙1)(1)(TE5)()(TE第33頁/共48頁 為了滿足為了滿足99%99%以上的病人有座，設(shè)科室應(yīng)設(shè)以上的病人有座，設(shè)科室應(yīng)設(shè)m m個座個座位，即：位，即：P P醫(yī)務(wù)室病人數(shù)醫(yī)務(wù)室病人數(shù)m m0.990.99 故該設(shè)故該設(shè)2020個座位。個

30、座位。 該單位該單位2424小時上班，平均每天有小時上班，平均每天有4 424249696人看人看病，看病所占的總時間為病，看病所占的總時間為1 196969696小時，所以因看小時，所以因看病平均每天損失病平均每天損失303096962 880(2 880(元元) )。mnmnmnnp01099. 01)1 (201)ln01. 0(lnm第34頁/共48頁 若醫(yī)生診病速度提高到每小時若醫(yī)生診病速度提高到每小時6 6人，即人，即6 6、 2 23 3，類似于上面的計算，有以下結(jié)果：類似于上面的計算，有以下結(jié)果： （人），人）， （人）人） ( (小時小時) )， （小時小時) )這樣單位每天

31、損失：這樣單位每天損失：30300.50.596961 4401 440（元），（元），比原來減少比原來減少1 4401 440元，此時只需座位：元，此時只需座位： 即即1111個座位，比原來減少個座位，比原來減少9 9個座位個座位。342qLL315 . 0q111)32ln01. 0(lnm第35頁/共48頁（二）系統(tǒng)容量有限的模型（二）系統(tǒng)容量有限的模型 即為即為M MM M1 1N N排隊系統(tǒng)?？紤]排隊系統(tǒng)的容排隊系統(tǒng)?？紤]排隊系統(tǒng)的容量為量為N N，即若系統(tǒng)已有即若系統(tǒng)已有N N個顧客，則再來新顧客即被個顧客，則再來新顧客即被拒絕進(jìn)入系統(tǒng)。對于拒絕進(jìn)入系統(tǒng)。對于n nN N，與與M

32、MM M1 1相類似，相類似， ，有有ntxtPn)(Pr)()()()(1, 2 , 1)()()()()(10011tptptpNntptptptpnnnn對于對于n nN N，)()1)()()(1tottpttpttpNNN)()()(1tptptpNNN第36頁/共48頁 即即 滿足微分方程滿足微分方程 在穩(wěn)態(tài)情況下，在穩(wěn)態(tài)情況下， ， ，則則)(tPn)()()()()()(1, 2 , 1)()()()()(110011tptptptptptpNntptptptpNNNnnnn0)( tpn)(tppnn001, 2 , 10)(11011NNnnnppppNnppp第37頁/共

33、48頁 則則 由由 ，可得可得0ppnnNnnp01Nnnp00111)1 (1111NnnNp11)1 (11110NNp第38頁/共48頁系統(tǒng)的各項指標(biāo)系統(tǒng)的各項指標(biāo)11) 1(112110NNnNnNNpnL111112) 1(110NNnNnqNNNNpnL第39頁/共48頁 由于有容量的限制，顧客實際進(jìn)入系統(tǒng)的速率不由于有容量的限制，顧客實際進(jìn)入系統(tǒng)的速率不是是，而是而是 ( (有效到達(dá)率有效到達(dá)率) )，因而，因而LittleLittle公式成立：公式成立：1)1 (1121)1 (NNNNNpL1)1 (121)1 (NNNqqNNpL)1 (,NeepqeqeLL第40頁/共48頁三、多通道等待制排隊問題三、多通道等待制排隊問題 （MMMMc c排隊系統(tǒng)）排隊系統(tǒng)） 多通道就是多服務(wù)臺，這里主要討論多通道就是多服務(wù)臺，這里主要討論M M