排隊論講義ppt課件

1、排隊論排隊論1；.一、概率論及隨機過程回顧n隨機變量隨機變量離散型隨機變量n概率分布和概率分布圖概率分布和概率分布圖n數(shù)學期望和方差數(shù)學期望和方差n常見離散型隨機變量的概率分布常見離散型隨機變量的概率分布A二點分布二點分布?A二項式分布二項式分布?APoisson分布分布?1.1、隨機變量與概率分布2；.一、概率論及隨機過程復習n隨機變量隨機變量離散型隨機變量n概率分布和概率分布圖概率分布和概率分布圖n數(shù)學期望和方差數(shù)學期望和方差n常見離散型隨機變量的概率分布常見離散型隨機變量的概率分布A二點分布二點分布?A二項式分布二項式分布?APoisson分布分布?3；.n隨機變量隨機變量連續(xù)型隨機變量

2、連續(xù)型隨機變量n概率密度函數(shù)概率密度函數(shù)n概率分布函數(shù)概率分布函數(shù)n數(shù)學期望和方差數(shù)學期望和方差n常見連續(xù)型隨機變量的概率分布常見連續(xù)型隨機變量的概率分布A均勻分布均勻分布A指數(shù)分布？指數(shù)分布？A正態(tài)正態(tài)分布？分布？Ak階愛爾朗分布？階愛爾朗分布？一、隨機變量與概率分布2/1)(,/1)()0(0,00,)(XDXExxexax 隨機變量隨機變量X X為時間間隔，如顧客到達的為時間間隔，如顧客到達的時間間隔、電話呼叫的時間、產(chǎn)品的壽命等。時間間隔、電話呼叫的時間、產(chǎn)品的壽命等。密度函數(shù)密度函數(shù)4；.? 愛爾朗分布211)(,1)(0,)!1()()(kTDTEtekktktbktkkkXXX,

3、21k 為為k k個相互獨立的隨機變量；個相互獨立的隨機變量；服從相同參數(shù)服從相同參數(shù) 的負指數(shù)分布；的負指數(shù)分布；kXXXT21設設 ，則，則T T的密度函數(shù)為的密度函數(shù)為 如如k k個服務臺串聯(lián)（個服務臺串聯(lián)（k k個服務階段），個服務階段），一個顧客接受一個顧客接受k k個服務共需的服務時間個服務共需的服務時間T T，T T 愛爾朗分布。愛爾朗分布。5；.1.2 隨機過程的有關概念n隨機過程隨機過程(Random process)的定義的定義),(TttX 設設 ，是一族隨機變量，是一族隨機變量，T T是一個實數(shù)集，對是一個實數(shù)集，對 是一個是一個隨機變量，則稱隨機變量，則稱 為隨機過程

4、。為隨機過程。)(,tXTt),(TttXTt T T：參數(shù)集合參數(shù)集合 當當T=0,1,T=0,1,n,n, 時，稱為隨機序列時，稱為隨機序列 ：隨機過程的一個狀態(tài)：隨機過程的一個狀態(tài) 狀態(tài)空間狀態(tài)空間E=X(t)E=X(t)全體可能取值，全體可能取值， ktX)(6；.n隨機過程的基本類型隨機過程的基本類型二階矩過程二階矩過程平穩(wěn)過程平穩(wěn)過程平穩(wěn)獨立增量過程平穩(wěn)獨立增量過程常見隨機過程常見隨機過程A馬爾可夫過程？馬爾可夫過程？APoisson過程？過程？A生滅過程？生滅過程？1.2 隨機過程的有關概念7；.n定義： 若滿足如下性質(zhì)： 對任意非負整數(shù) ，只要就有 則稱 具有馬爾可夫性，或無后

5、效性。馬爾可夫性，或無后效性。馬爾可夫過程 馬爾可夫鏈離散離散,.2 , 1 , 0),(nnXttttr.21)()()(,.,)(,)()(2211rrrritXjtXPitXitXitXjtXP0)(,.,)(,)(2211rritXitXitXP)(nX1t2trt1rtt過去過去現(xiàn)在現(xiàn)在將來將來 “ “將來將來”的情況與的情況與“過去過去”無關，無關，只是通過只是通過“現(xiàn)在現(xiàn)在”與與“過去過去”發(fā)生聯(lián)系，若發(fā)生聯(lián)系，若“現(xiàn)在現(xiàn)在”已知，已知，“將來將來”與與“過去過去”無關。無關。)(nX8；.n時齊的馬氏鏈時齊的馬氏鏈：馬氏鏈 若滿足： 則稱 為時齊馬爾可夫鏈時齊馬爾可夫鏈)(mP

6、iXjXPijnmn,.2 , 1 , 0),(nnX,.2 , 1 , 0),(nnX)(mPij 系統(tǒng)由狀態(tài)系統(tǒng)由狀態(tài)i i經(jīng)過經(jīng)過m m 個時間間隔個時間間隔（或或m m 步）轉(zhuǎn)移到狀態(tài)步）轉(zhuǎn)移到狀態(tài)j j 的轉(zhuǎn)移概率的轉(zhuǎn)移概率9；.Poisson過程n定義：設 為時間 內(nèi)到達系統(tǒng)的顧客數(shù)，若滿足下面三個條件：n獨立性：在任意兩個不相交的區(qū)間內(nèi)顧客到 達的情況相互獨立；n平穩(wěn)性：在 內(nèi)有一個顧客到達的 概率為n普通性：在 內(nèi)多于一個顧客到達 的率為 。則稱 為Poisson過程。)(tNt ,00),(ttNttt , );( tt)( tttt , （1 1）只與區(qū)間長度與）只與區(qū)間長

7、度與 起點無關。起點無關。（2 2）單位時間內(nèi)一個）單位時間內(nèi)一個 顧客到達的概率顧客到達的概率 為為 。10；.Poisson過程與過程與Poisson分布分布定理定理1 1：設：設 為時間為時間 內(nèi)到達系統(tǒng)的顧客數(shù)內(nèi)到達系統(tǒng)的顧客數(shù) 則則 為為PoissonPoisson過程的充要條件是過程的充要條件是)(tNt ,00),(ttN,.2 , 1!)()(nentntNPtn數(shù)理統(tǒng)計方法數(shù)理統(tǒng)計方法容易初步判斷容易初步判斷: :期望期望= =標準差標準差ttNDttNE)(,)(11；.Poisson過程與負指數(shù)分布過程與負指數(shù)分布tTPsTstTP定理定理2 2：設：設 為時間為時間 內(nèi)

8、到達系統(tǒng)的顧客數(shù)內(nèi)到達系統(tǒng)的顧客數(shù) 則則 為參數(shù)為為參數(shù)為 的的PoissonPoisson過程的過程的 充要條件是相繼到達的時間間隔充要條件是相繼到達的時間間隔T T服從相互服從相互 獨立的參數(shù)為獨立的參數(shù)為 的負指數(shù)分布。的負指數(shù)分布。)(tNt ,00),(ttN0, 00,)(ttetatT負指數(shù)分布的性質(zhì)負指數(shù)分布的性質(zhì): 2/1)(,/1tNDTE馬爾可夫性馬爾可夫性，或無后效，或無后效性性12；.nPoisson過程與Poisson分布的關系：定理定理1 1：設：設 為時間為時間 內(nèi)到達系統(tǒng)的顧客數(shù)內(nèi)到達系統(tǒng)的顧客數(shù) 則則 為為PoissonPoisson過程的充要條件是過程的充

9、要條件是)(tNt ,00),(ttN,.2 , 1!)()(nentntNPtn定理定理2 2：設：設 為時間為時間 內(nèi)到達系統(tǒng)的顧客數(shù)內(nèi)到達系統(tǒng)的顧客數(shù) 則則 為參數(shù)為為參數(shù)為 的的PoissonPoisson過程的過程的 充要條件是相繼到達的時間間隔充要條件是相繼到達的時間間隔T T服從相互服從相互 獨立的參數(shù)為獨立的參數(shù)為 的負指數(shù)分布。的負指數(shù)分布。)(tNt ,00),(ttN0, 00,)(ttetatT對于對于PoissonPoisson流：流： 單位時間平均到達的顧客數(shù)單位時間平均到達的顧客數(shù) 顧客相繼到達的平均間隔時間顧客相繼到達的平均間隔時間/113；.n定義：設定義：設

10、 為一個隨機過程，若為一個隨機過程，若N(t)N(t)的概率分布具有以下性的概率分布具有以下性質(zhì)：質(zhì)： (1) (1)假設假設N(t)=nN(t)=n，則從時刻到下一個顧客到達時刻止的時間服從參數(shù)為則從時刻到下一個顧客到達時刻止的時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； (2) (2)假設假設N(t)=nN(t)=n，則從時刻到下一個顧客離開時刻止的時間服從參數(shù)為則從時刻到下一個顧客離開時刻止的時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； (3) (3)同一時刻是只有一個同一時刻是只有一個 顧客到達或離去。顧客到達或離去。 則稱則稱 為一個生滅過程。為一個生滅過程。 0),(ttN0),(

11、ttNnn生滅生滅過程過程14；.1 10 001nn-1n+11nnn1n平穩(wěn)生滅過程系統(tǒng)狀態(tài)平穩(wěn)生滅過程系統(tǒng)狀態(tài)n n平衡方程：平衡方程：“流入流入= =流出流出”nnnnnnnppppp)(011111100系統(tǒng)達到平穩(wěn)狀態(tài)時：系統(tǒng)達到平穩(wěn)狀態(tài)時：.)2 , 1 , 0(),(ntppnn)(tN的分布的分布.)2 , 1 , 0(,)()(nntNPtpn15；.系統(tǒng)達到平穩(wěn)狀態(tài)時：系統(tǒng)達到平穩(wěn)狀態(tài)時：100110210111.,.2 , 1,nnnnnnnnnnnCppCnpCp其中其中nnnnnnnppppp)(011111100平衡方程：平衡方程： 當當 時才有意義時才有意義1n

12、nC.)2 , 1 , 0(,)()(nntNPtppnn16；.二、排隊論的基本知識17；.排隊論研究的內(nèi)容排隊論研究的內(nèi)容n性態(tài)問題: 排隊系統(tǒng)的概率規(guī)律, 如隊長分布, 等待時間分布等.n最優(yōu)化問題: 排隊系統(tǒng)的最優(yōu)設計.n統(tǒng)計推斷: 判定排隊系統(tǒng)的類型.18；.顧客源顧客源2.1、排隊排隊模型模型排隊系統(tǒng)排隊系統(tǒng)排隊排隊結(jié)構(gòu)結(jié)構(gòu)服務服務機構(gòu)機構(gòu)排隊規(guī)則服務規(guī)則服務規(guī)則接受接受服務服務后離去后離去19；.服務服務機構(gòu)機構(gòu)服務服務臺臺( (a) a) 一個一個隊列、單服務隊列、單服務臺臺（階段階段）20；.服務臺服務臺1服務臺服務臺2( (b) b) 一個一個隊列、隊列、s s個服務階段個

13、服務階段服務服務機構(gòu)機構(gòu)21；.服務臺服務臺1服務臺服務臺2服務服務機構(gòu)機構(gòu)( (c c) ) 一個一個隊列、隊列、s s個服務臺個服務臺 一個服務階段一個服務階段22；.服務臺服務臺3服務臺服務臺4服務臺服務臺1服務臺服務臺2服務服務機構(gòu)機構(gòu)( (d d) ) s s個個隊列、隊列、s s個服務階段個服務階段23；.服務臺服務臺3服務臺服務臺4服務臺服務臺1服務臺服務臺2: 124: 243: 3214服務服務機構(gòu)機構(gòu)( (e e) )混合混合型型24；.排隊排隊結(jié)構(gòu)結(jié)構(gòu)服務服務臺臺( (f f) ) 一個一個隊列隊列服務服務臺臺( (g g) ) s s個個隊列隊列25；. n輸入過程輸入

14、過程n顧客總體顧客總體:有限有限,無限無限.n顧客到達方式顧客到達方式:單個單個,成批成批.n顧客到達間隔時間顧客到達間隔時間: 確定的、確定的、 隨機的隨機的.n顧客到達的獨立性顧客到達的獨立性: 獨立獨立,不獨立不獨立. n輸入過程的平穩(wěn)性輸入過程的平穩(wěn)性: 與時間無關與時間無關(平穩(wěn)的平穩(wěn)的), 與時間有關與時間有關(非平穩(wěn)的非平穩(wěn)的).2.22.2、 排隊系統(tǒng)的組成和特征排隊系統(tǒng)的組成和特征26；.n顧客到達時間間隔的分布顧客到達時間間隔的分布:：第：第n n個顧客與第個顧客與第n-1n-1個顧客到達的時間間隔；個顧客到達的時間間隔；nXnT：第：第n n個顧客到達的時刻；個顧客到達的

15、時刻；設設nTTT100, 2, 1,1nTTXnnn令令1T2TnT1nT1nT0TnX27；.n顧客到達時間間隔的分布顧客到達時間間隔的分布:假定假定 是獨立同分布，分布函數(shù)為是獨立同分布，分布函數(shù)為 ，排隊論中常用的有兩種：排隊論中常用的有兩種：nX)(tAnX（2 2）最簡流（即）最簡流（即PoissonPoisson流）（流）（M M）：）： 顧客到達時間間隔顧客到達時間間隔 為獨立的，為獨立的， 服從負指數(shù)分布，其密度函數(shù)為服從負指數(shù)分布，其密度函數(shù)為（1 1）定長分布（）定長分布（D D）：）：顧客到達時間間隔為確定的。顧客到達時間間隔為確定的。000)(ttetat因為負指數(shù)分

16、布因為負指數(shù)分布具有無后效性具有無后效性（即（即Markov性）性）28；. n排隊及排隊規(guī)則排隊及排隊規(guī)則n即時制即時制(損失制損失制)n等待制等待制n先到先服務先到先服務: FCFSn后到先服務后到先服務: LCFSn隨機服務隨機服務n優(yōu)先權服務：優(yōu)先權服務：PSn隊容量隊容量: 有限有限, 無限無限; 有形有形, 無形無形.n隊列數(shù)目隊列數(shù)目: 單列單列, 多列多列.29；. n 服務機構(gòu)服務機構(gòu)n服務員數(shù)量服務員數(shù)量: 無無, 單個單個, 多個多個.n隊列與服務臺的組合隊列與服務臺的組合n服務方式服務方式: 單個顧客單個顧客, 成批顧客成批顧客.n服務時間服務時間: 確定的確定的, 隨

17、機的隨機的. 服務時間和到達間隔時間至少一個是隨服務時間和到達間隔時間至少一個是隨機的機的.n服務時間分布是平穩(wěn)的服務時間分布是平穩(wěn)的.30；.n服務時間分布服務時間分布: 設某服務臺的服務時間為設某服務臺的服務時間為V V，其密度函數(shù)為其密度函數(shù)為b b（t t），），常見的分布有：常見的分布有：（1 1）定長分布（）定長分布（D D）：）：每個顧客接受服務的時間每個顧客接受服務的時間 是一個確定的常數(shù)。是一個確定的常數(shù)。（2 2）負指數(shù)分布（）負指數(shù)分布（M M）：）：每個顧客接受服務時間每個顧客接受服務時間 相互獨立，具有相互的負指數(shù)分布：相互獨立，具有相互的負指數(shù)分布： 其中其中 ，為

18、一常數(shù)。，為一常數(shù)。000)(ttetbt0- - 單位時間平均服務完成的顧客數(shù)單位時間平均服務完成的顧客數(shù)1/1/ - - 每個顧客的平均服務時間每個顧客的平均服務時間31；.n服務時間分布服務時間分布:（3 3）k k階愛爾朗（階愛爾朗（ErlangErlang）分布：每個顧客接受服務分布：每個顧客接受服務 時間服從時間服從k k階愛爾朗分布，其密度函數(shù)為：階愛爾朗分布，其密度函數(shù)為：tkkektkktb)!1()()(132；. n符號表示符號表示: X/Y/ZnX - 客到達間隔時間分布客到達間隔時間分布nY - 服務時間分布服務時間分布nZ - 服務臺個數(shù)服務臺個數(shù)nX, Y 可以是

19、可以是:nM - M - 負指數(shù)分布負指數(shù)分布nD - D - 確定性的確定性的nE Ek k - k - k階階ErlangErlang分布分布nGI - GI - 一般相互獨立的到達時間間隔分布一般相互獨立的到達時間間隔分布nG - G - 一般一般( (General)General)時間分布時間分布排隊系統(tǒng)的分類排隊系統(tǒng)的分類33；. n擴展符號表示擴展符號表示: X/Y/Z/A/B/CnA - 系統(tǒng)容量系統(tǒng)容量nB - 顧客源中顧客的數(shù)量顧客源中顧客的數(shù)量nC - 服務規(guī)則服務規(guī)則: FCFS, LCFS, 等等等等.n若省略后三項，即是指下面的情形：若省略后三項，即是指下面的情形：

20、 X/Y/Z/ / /FCFS 例：M/M/s/K表示？34；. 已知: 顧客到達間隔時間分布, 服務時間分布. 求:n隊長隊長: Ls - 系統(tǒng)中的顧客數(shù)系統(tǒng)中的顧客數(shù). 排隊長排隊長(隊列長隊列長): Lq - 隊列中的顧客數(shù)隊列中的顧客數(shù). Ls = Lq + 正在接受服務的顧客數(shù)正在接受服務的顧客數(shù)n逗留時間逗留時間: W S- 顧客在系統(tǒng)中的停留時間顧客在系統(tǒng)中的停留時間 等待時間等待時間: Wq - 顧客在隊列中的等待時間顧客在隊列中的等待時間. WS = Wq + 服務時間服務時間n忙期忙期, 損失率損失率, 服務強度服務強度.排隊問題的求解排隊問題的求解35；.三三. .單服務

21、臺負指數(shù)分布單服務臺負指數(shù)分布排隊系統(tǒng)分析排隊系統(tǒng)分析 3.1 3.1 M/M/1M/M/1模型模型3.2 3.2 M/M/1/N/ M/M/1/N/ 模型模型( (即系統(tǒng)的容量有限即系統(tǒng)的容量有限) )3.3 3.3 M/M/1/ /m M/M/1/ /m 模型（即顧客源為有限）模型（即顧客源為有限）36；.顧客源顧客源排隊系統(tǒng)排隊系統(tǒng)排隊排隊結(jié)構(gòu)結(jié)構(gòu)服務服務機構(gòu)機構(gòu)排隊規(guī)則服務規(guī)則服務規(guī)則接受接受服務服務后離去后離去 3.1 3.1 M/M/1M/M/1模型模型無限無限輸入過程服從輸入過程服從參數(shù)為參數(shù)為 的的PoissonPoisson過程過程單隊單隊隊長無限隊長無限先到先服務先到先服務

22、服務時間服從服務時間服從參數(shù)為參數(shù)為 的的負指數(shù)分布負指數(shù)分布37；. 求解：求解：np: :系統(tǒng)達到平穩(wěn)后，系統(tǒng)有系統(tǒng)達到平穩(wěn)后，系統(tǒng)有n n個顧客的概率。個顧客的概率。1n 0)(0n 01110nnnPPPPP平衡方程：平衡方程：1n )1(1 0nnPP1 :令，且當，且當時時01102101.,.2, 1,ppCnpCpnnnnnnnnn其中其中38；.n關于 的幾點說明：) 1 (/1/1(2)01(3)p顧客平均到達率顧客平均到達率顧客平均服務率顧客平均服務率一個顧客服務時間一個顧客服務時間一個顧客到達時間一個顧客到達時間服務強度服務強度, 1) 4(即顧客的顧客平均到達率即顧客

23、的顧客平均到達率小于顧客平均服務率時，小于顧客平均服務率時，系統(tǒng)才能達到統(tǒng)計平穩(wěn)。系統(tǒng)才能達到統(tǒng)計平穩(wěn)。系統(tǒng)中至少有系統(tǒng)中至少有一個顧客的概一個顧客的概率；率；服務臺處于忙服務臺處于忙的狀態(tài)的概率；的狀態(tài)的概率；反映系統(tǒng)繁忙反映系統(tǒng)繁忙程度程度39；. 計算有關指標計算有關指標101.)2(.)32()1 ( 3232321n0nsnnsLnnPLn隊長隊長40；.n隊列長隊列長 1)1 () 1( 201n10nssnnnnqLPLPnPPnL 計算有關指標計算有關指標41；. n逗留時間逗留時間: : 可以證明可以證明, Ws服從參數(shù)為服從參數(shù)為-的負指數(shù)分布的負指數(shù)分布. 則則:n等待時

24、間等待時間1 sW1 sqWW服務WWWsq 計算有關指標計算有關指標42；.計算有關指標計算有關指標nLittle公式（相互關系）qsqsqqssLLWWWLWL 1 小小結(jié)結(jié)1 sWqW qLsL平均服務平均服務時間時間平均在忙的服務平均在忙的服務臺數(shù)臺數(shù)/正在接受正在接受服務的顧客數(shù)服務的顧客數(shù)有效到達率有效到達率43；.n平均忙期 B , 忙期出現(xiàn)的概率n平均閑期 I , 閑期出現(xiàn)的概率 (1-)n忙期 B : 閑期 I = : (1-)n平均閑期 I = 1 / 閑期的分布與顧客到達時間閑期的分布與顧客到達時間間隔的相同間隔的相同-服從參數(shù)為服從參數(shù)為 的負指數(shù)分布的負指數(shù)分布計算有

25、關指標計算有關指標n忙期與閑期忙期與閑期 WHY?1-P0= 44；.n平均忙期平均忙期 B , 忙期出現(xiàn)的概率忙期出現(xiàn)的概率 n平均閑期平均閑期 I , 閑期出現(xiàn)的概率閑期出現(xiàn)的概率 (1- )n忙期忙期 B : 閑期閑期 I = : (1- )n平均閑期平均閑期 I = 1 / n平均忙期平均忙期 B = ( / (1- ) / = 1/( - )計算有關指標計算有關指標n忙期與閑期忙期與閑期 與逗留時間與逗留時間WsWs相同相同!?45；.例：某醫(yī)院手術室每小時就診病人數(shù)和手術例：某醫(yī)院手術室每小時就診病人數(shù)和手術 時間的記錄如下：時間的記錄如下：到達的病人數(shù)到達的病人數(shù) 出現(xiàn)次數(shù)出現(xiàn)次

26、數(shù) n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上以上 1 合計合計 100完成手術時間完成手術時間 出現(xiàn)次數(shù)出現(xiàn)次數(shù) r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上以上 0 合計合計 10046；.n解：到達的病人數(shù) 出現(xiàn)次數(shù) n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合計 100每小時病人平均到達率每小時病人平均到達率1.2100nnu（人（人/小時）小時）每次手術平均時間每次手術平均時間4.0100rrv（小時（小時/人）人）每小

27、時完成手術人數(shù)每小時完成手術人數(shù)（平均服務率）（平均服務率）5.24.01（人（人/小時）小時）?,47；.n解：到達的病人數(shù) 出現(xiàn)次數(shù) n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合計 100每小時病人平均到達率每小時病人平均到達率1.2100nnu（人（人/小時）小時）每次手術平均時間每次手術平均時間4.0100rrv（小時（小時/人）人）每小時完成手術人數(shù)每小時完成手術人數(shù)（平均服務率）（平均服務率）5.24.01（人（人/小時）小時）完成手術時間完成手術時間 出現(xiàn)次數(shù)出現(xiàn)次數(shù) r vr 0.00.2 38 0.20.4 25 0.40.6 17 0

28、.60.8 9 0.81.0 6 1.01.2 5 1.2 以上以上 0 合計合計 1005 . 2, 1 . 248；.解：5 . 2, 1 . 21 sWqW 41. 425. 55 . 21 . 2sqLL25. 51 . 25 . 21 . 2sL49；.3.2 3.2 系統(tǒng)容量有限制的情形系統(tǒng)容量有限制的情形 ( (M/M/1/N/FCFSM/M/1/N/FCFS）n狀態(tài)轉(zhuǎn)移圖n狀態(tài)轉(zhuǎn)移方程 Nn 1-Nn )(0n 11101NNnnnPPPPPPPN-1N50；.求排隊系統(tǒng)顧客數(shù)的分布狀況求排隊系統(tǒng)顧客數(shù)的分布狀況01102101.,.2, 1,ppCnpCpnnnnnnnnn其

29、中其中 1 1 .,.2 , 1,002000110210pppppCwherenpCpNNnnnnnnnnnnn51；. N1,2,.,n 11 11110nNnNPP1) 1 (20NP求排隊系統(tǒng)顧客數(shù)的分布狀況求排隊系統(tǒng)顧客數(shù)的分布狀況52；. n隊長隊長n隊列長隊列長 1101)1(1NNNnnsNnPL)1()1(00PLPnLsNnnq計算有關指標計算有關指標53；. n逗留時間逗留時間 n等待時間等待時間111Little1 100）（）（公式根據(jù)）（）或（有效到達率：NqsesseNePLPLLWPP1sqWW計算有關指標計算有關指標系統(tǒng)已滿顧客不能到達的系統(tǒng)已滿顧客不能到達的

30、概率概率-損失率損失率/10eP ）服務強度：（54；. 有有6個椅子接待人們排隊，超過個椅子接待人們排隊，超過6人顧客就離開，平均到達率人顧客就離開，平均到達率3人人/小時，理發(fā)需時平均小時，理發(fā)需時平均15分鐘。分鐘。7為系統(tǒng)中的最大顧客數(shù)。為系統(tǒng)中的最大顧客數(shù)。舉例：單人理發(fā)館排隊問題55；. n 顧客到達就能理發(fā)的概率顧客到達就能理發(fā)的概率 -相當于理發(fā)店內(nèi)沒有顧客相當于理發(fā)店內(nèi)沒有顧客n等待顧客數(shù)的期望值等待顧客數(shù)的期望值2778. 0)4/3(14/3111810NP39. 1)2778. 01 (11. 2)1 (11. 2)4/3(1)4/3(84/314/31) 1(1088

31、11PLLNLsqNNs56；. n 求有效到達率求有效到達率 n顧客在理發(fā)館內(nèi)逗留的期望時間顧客在理發(fā)館內(nèi)逗留的期望時間8 .4373. 089. 2/11. 2/essLW小時小時分鐘分鐘89. 2)2778. 01 (41 10eeNePP）（）或（人人/小時小時57；. n可能的顧客中有百分之幾不等待就離開可能的顧客中有百分之幾不等待就離開 -求系統(tǒng)中有求系統(tǒng)中有7 7個顧客的概率個顧客的概率%7 . 3)4/3(14/31)43()/(1/1)(87877P58；. 設：設：m ：為顧客總體數(shù)，為顧客總體數(shù)， ： 每個顧客的到達率，每個顧客的到達率， m - Ls ：系統(tǒng)外顧客的平均

32、數(shù)，：系統(tǒng)外顧客的平均數(shù)， e = （ m - Ls）：）：為系統(tǒng)有效到達率。為系統(tǒng)有效到達率。3.3 3.3 顧客源有限制的情形顧客源有限制的情形 ( (M/M/1/m/FCFSM/M/1/m/FCFS）含義與上節(jié)不同含義與上節(jié)不同對對顧客而言，而不是對顧客而言，而不是對系統(tǒng)系統(tǒng)m對系統(tǒng)而言對系統(tǒng)而言,有一個有一個顧客到達的概率顧客到達的概率59；.狀狀態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)移移圖圖01mn-1n(m-n+1) (m-n)n+1. . . . .m-1m. . .(m-1) 260；.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 mn 1-mn )() 1(0n 11101mmnnnPPPnmPnmPPmP11mnnPF注意

33、到注意到 ，61；. 求解狀態(tài)轉(zhuǎn)移方程得求解狀態(tài)轉(zhuǎn)移方程得m1,2,.,n )()!(!)()!(!1010PnmmPimmPnnimi有效到達率有效到達率)(seLm ）（01 Pe求解顧客數(shù)概率分布求解顧客數(shù)概率分布62；. n等待時間等待時間n正常運轉(zhuǎn)的平均設備臺數(shù)正常運轉(zhuǎn)的平均設備臺數(shù)1sqWW)1(0PLms計算有關指標計算有關指標63；. n隊長隊長n隊列長隊列長n逗留時間逗留時間)1(0PmLs)1(0PLLsq1)1(0PmWs計算有關指標計算有關指標例：P343#例764；.四四. 多服務臺負指數(shù)分布排隊系統(tǒng)分析多服務臺負指數(shù)分布排隊系統(tǒng)分析65；.規(guī)規(guī)定：定：n各服務臺工作

34、是相互獨立的，且平均服務率相同，均為各服務臺工作是相互獨立的，且平均服務率相同，均為 。n整個服務機構(gòu)的平均服務率為：整個服務機構(gòu)的平均服務率為： c c ( (當當n n c ) c )， n n ( (當當n c );n c );n記記 = = / / , , s s= = / /c c = = /c /c 為服務系統(tǒng)的平均利用率為服務系統(tǒng)的平均利用率 當當 / / c c 1 1時，不會排成無限隊列。時，不會排成無限隊列。66；. 1 2 c.系統(tǒng)人數(shù)系統(tǒng)人數(shù)n n人人67；. 1 2 c.系統(tǒng)人數(shù)系統(tǒng)人數(shù)n n人人n = c68；. 1 2 c.系統(tǒng)人數(shù)系統(tǒng)人數(shù)n n人人 69；.狀狀

35、態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)移移圖圖01n-1nn(n+1)n+1. . . . .22n-1nccn+1. . . . .n = c 70；.n狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 n )(cn 1 )() 1(0n 111101cPcPPcPnPPnPPnnnnnn71；.解差分方程，求得狀態(tài)概率為解差分方程，求得狀態(tài)概率為 )(!1)(!1)(11!1)(!1001100cnPcccnPnPckPncnnnckck72；. n顧客等候的概率顧客等候的概率 )(!1)( !1010cnPcccnPnPnnnn0)1( !)(PcPcnPsccnn n平均正接受服務的顧客數(shù)平均正接受服務的顧客數(shù)=正忙的服務臺數(shù)正忙的服務臺

36、數(shù)cnncnnPcnPc10qsLL解釋解釋?73；. )(!1)( !1010cnPcccnPnPnnnn n隊長隊長n隊列長隊列長n逗留時間及等待時間逗留時間及等待時間qqsLLL021)1( !)()(PcPcnLssccnnqssqqLWLW ;唯一唯一74；. 某售票所有三個窗口，某售票所有三個窗口，顧客到達服從顧客到達服從Poisson過程，到達過程，到達 = 0.9 人人/分鐘，服務分鐘，服務 =0.4人人/分鐘。設顧客到達后依分鐘。設顧客到達后依次排成一隊向空閑的窗次排成一隊向空閑的窗口購票，如圖口購票，如圖 a. 圖圖 a 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口

37、3 =0.4 = 0.975；.圖圖 a 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 = 0.3 = 0.3 = 0.3 = 0.9圖圖 b 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 = 0.976；.n屬于M/M/c型系統(tǒng) c =3, =/ =2.25, s = /c =2.25/3 1,符合要求.整個售票所空閑概率整個售票所空閑概率平均隊長平均隊長95. 370. 10748. 0)4/1 ( ! 34/3)25. 2(23qsqLLL0748. 03/25. 211! 325. 2!25. 212030nnnp77；.平均等待時間和逗留時間平

38、均等待時間和逗留時間分鐘分鐘39.44.0/189.1/189.19.0/70.1qsqqWWLW57.00748.04/1!3)25.2()3(3nP顧客到達后必須等待概率顧客到達后必須等待概率78；. 以上例說明以上例說明, ,設顧客到達后在每設顧客到達后在每個窗口前各排一隊個窗口前各排一隊( (其它條件不變其它條件不變),),共三隊共三隊, ,每隊平均到達率為每隊平均到達率為: :3 . 03/9 . 0321 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 = 0.3 = 0.3 = 0.3 = 0.9圖圖 b79；.結(jié)果比較結(jié)果比較80；.n狀態(tài)圖是多服務臺和容量有

39、限的綜合狀態(tài)圖是多服務臺和容量有限的綜合n平衡方程平衡方程你會嗎你會嗎? ?Nncccnnnnnn 0 N 01N,0,1,2, 81；.1 ) 1(! 1 )1 ( !)1 (! ! 0 !1101101000ccncnccnccNccncnnnncNcncnpNncpcccnpnpn求系統(tǒng)有求系統(tǒng)有n位顧客的概率分布位顧客的概率分布82；.n求系統(tǒng)的指標求系統(tǒng)的指標)1 (Nep有效到達率有效到達率)1 ( 10NNcnncnnppcnpc平均被占用的服務臺平均被占用的服務臺83；.n求系統(tǒng)的指標求系統(tǒng)的指標1 , )(seqqessqsNcnnqWLWLWcLLpcnL84；.85；.86；.n設系統(tǒng)的平均到達率為設系統(tǒng)的