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

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

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

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

4、隊(duì)論也稱隨機(jī)服隨機(jī)服務(wù)系統(tǒng)務(wù)系統(tǒng)。第5頁(yè)/共48頁(yè) 各式各樣的排隊(duì)現(xiàn)象呈現(xiàn)的基本特征：排隊(duì)系統(tǒng)各式各樣的排隊(duì)現(xiàn)象呈現(xiàn)的基本特征：排隊(duì)系統(tǒng)由輸入過程、排隊(duì)規(guī)則及服務(wù)機(jī)構(gòu)三部分組成。由輸入過程、排隊(duì)規(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ī)的還是確定性的是確定性的) )還是單個(gè)到達(dá)；最后應(yīng)說明相繼到達(dá)的還是單個(gè)到達(dá)；最后應(yīng)

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

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

7、dall引進(jìn)了排隊(duì)模型分類符號(hào)，現(xiàn)已廣引進(jìn)了排隊(duì)模型分類符號(hào)，現(xiàn)已廣泛采用，這里僅針對(duì)并列的服務(wù)臺(tái)。泛采用，這里僅針對(duì)并列的服務(wù)臺(tái)。 記記X X：顧客到達(dá)的時(shí)間間隔分布；顧客到達(dá)的時(shí)間間隔分布；Y Y：服務(wù)時(shí)間的服務(wù)時(shí)間的分布；分布；Z Z：服務(wù)臺(tái)數(shù)。則排隊(duì)模型：服務(wù)臺(tái)數(shù)。則排隊(duì)模型：X XY YZ Z。 常用的記號(hào)：常用的記號(hào)：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。（二）排隊(duì)模型的分類及數(shù)量指標(biāo)（二）排隊(duì)模型的分類及數(shù)量指標(biāo)第9頁(yè)/共48頁(yè) (1)(1)隊(duì)長(zhǎng)隊(duì)長(zhǎng) 隊(duì)長(zhǎng)是指系統(tǒng)中的顧客數(shù)隊(duì)長(zhǎng)是指系統(tǒng)中的顧客數(shù)( (包括排隊(duì)等候和正包括排隊(duì)等候和正在接受服務(wù)的顧客數(shù)在接受服務(wù)的顧客數(shù)) )；等待隊(duì)長(zhǎng)是指系統(tǒng)中等待；等待隊(duì)長(zhǎng)是指系統(tǒng)中等待服務(wù)的顧客數(shù)。無論是隊(duì)長(zhǎng)還是等待隊(duì)長(zhǎng)，都是顧服務(wù)的顧客數(shù)。無論是隊(duì)長(zhǎng)還是等待隊(duì)長(zhǎng)，都是顧客和服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指標(biāo)，特別是對(duì)系統(tǒng)設(shè)客和服務(wù)機(jī)構(gòu)最關(guān)心的數(shù)量指標(biāo)，特別是對(duì)系統(tǒng)設(shè)計(jì)者來說，尤為重要，因?yàn)樗婕暗较到y(tǒng)等待空間計(jì)者來說，尤為重要，因?yàn)樗婕暗较到y(tǒng)等待空間的大小。的大小。2.2.排隊(duì)模型的數(shù)量指標(biāo)排隊(duì)模型的數(shù)

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

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

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

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

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

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

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

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

17、于輸入時(shí)間間隔大于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頁(yè)/共48頁(yè)(2)(2)由于輸入時(shí)間間隔由于輸入時(shí)間間隔服從參數(shù)為服從參數(shù)為的指數(shù)分布的指數(shù)分布則所求概率為則所求概率為0001Prttettn1888. 01Pr35en第19頁(yè)/共48頁(yè) 對(duì)于單通道等待制排隊(duì)問題主要討論輸入過對(duì)于單通道等待制排隊(duì)問題主要討

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

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

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

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

22、，新進(jìn)入或離開顧客個(gè)數(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.排隊(duì)系統(tǒng)的穩(wěn)態(tài)解排隊(duì)系統(tǒng)的穩(wěn)態(tài)解ntxtPn)(Pr)(),(ttt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt第23頁(yè)/共48頁(yè) 當(dāng)當(dāng) 時(shí)有時(shí)有導(dǎo)出導(dǎo)出 滿足的微分方程組滿足的微分方程組)(tpn)()1 ()()1)(

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

24、得)(tpn0)( tpn)(tppnn0, 2 , 10)(1011ppnpppnnn0)(ppnn第26頁(yè)/共48頁(yè) 記記 為排隊(duì)系統(tǒng)的來往強(qiáng)度，當(dāng)為排隊(duì)系統(tǒng)的來往強(qiáng)度，當(dāng) 時(shí)，由時(shí)，由 可得可得 由于由于 構(gòu)成概率分布，則構(gòu)成概率分布，則 ，從而級(jí)數(shù)從而級(jí)數(shù) 必須收斂，故有必須收斂，故有 。 np01nnp0)(nn1101nnp, 2 , 1 , 0)1 (npnn第27頁(yè)/共48頁(yè)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ù)，簡(jiǎn)稱被稱為系統(tǒng)中顧客的平均數(shù)，簡(jiǎn)稱平均隊(duì)長(zhǎng)平

25、均隊(duì)長(zhǎng)。 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é)期望，簡(jiǎn)稱平均簡(jiǎn)稱平均等待隊(duì)長(zhǎng)等待隊(duì)長(zhǎng)。第28頁(yè)/共48頁(yè) (2)(2)顧客在系統(tǒng)中的顧客在系統(tǒng)中的平均逗留時(shí)間平均逗留時(shí)間則顧客在系統(tǒng)中的則顧客在系統(tǒng)中的平均等待時(shí)間平均等待時(shí)間 可以證明，顧客在系統(tǒng)中逗留時(shí)間服從參數(shù)為可以證明，顧客在系統(tǒng)中逗留時(shí)間服從參數(shù)為-的負(fù)指數(shù)分布。的負(fù)指數(shù)分布。1)(11q第29頁(yè)/共48頁(yè) 與與 是衡量排隊(duì)系統(tǒng)質(zhì)量的很重要的效是衡量排隊(duì)系統(tǒng)質(zhì)量的很重要的效率度量，它們之間有著有趣的聯(lián)

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

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

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

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

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

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

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

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