研究生入學(xué)考試上海交大運(yùn)籌學(xué)期末考試考研復(fù)習(xí)珍貴PPT資料適合全國高?？佳泻推谀┛荚?排隊(duì)論P(yáng)PT學(xué)習(xí)教案

1、會計(jì)學(xué)1 研究生入學(xué)考試上海交大運(yùn)籌學(xué)期末考研究生入學(xué)考試上海交大運(yùn)籌學(xué)期末考 試考研復(fù)習(xí)珍貴試考研復(fù)習(xí)珍貴PPT資料適合全國高校資料適合全國高校 考研和期末考試考研和期末考試9排隊(duì)論排隊(duì)論 排隊(duì)系統(tǒng)的組成和特征 盡管排隊(duì)系統(tǒng)是多種多樣的，但從決定排隊(duì)系統(tǒng)進(jìn) 程的因素來看，它有三個基本的組成部分，這就是輸入 過程、排隊(duì)規(guī)則及服務(wù)機(jī)構(gòu)。 1)輸入過程：描述顧客來源以及顧客到達(dá)排隊(duì)系統(tǒng)的規(guī) 律。包括： 顧客源中顧客的數(shù)量是有限還是無限； 顧客到達(dá)的方式是單個到達(dá)還是成批到達(dá)； 顧客相繼到達(dá)的間隔時間分布是確定型的還是隨機(jī) 型的，分布參數(shù)是什么，是否獨(dú)立，是否平穩(wěn)。 第1頁/共63頁 2)排隊(duì)規(guī)則：

2、描述顧客排隊(duì)等待的隊(duì)列和接受服務(wù)的次 序。包括： 即時制還是等待制； 等待制下隊(duì)列的情況（是單列還是多列，顧客能不 能中途退出，多列時各列間的顧客能不能相互轉(zhuǎn)移）； 等待制下顧客接受服務(wù)的次序（先到先服務(wù)，后到 先服務(wù)，隨機(jī)服務(wù)，有優(yōu)先權(quán)的服務(wù)）。 3)服務(wù)機(jī)構(gòu)：描述服務(wù)臺(員)的機(jī)構(gòu)形式和工作情況。 包括： 服務(wù)臺（員）的數(shù)目和排列情況； 服務(wù)臺（員）的服務(wù)方式； 服務(wù)時間是確定型的還是隨機(jī)型的，分布參數(shù)是什 么，是否獨(dú)立，是否平穩(wěn)。 第2頁/共63頁 排隊(duì)模型的分類 D.G.Kendall在1953年提出了一個分類方法，按照 系統(tǒng)的三個最主要的、影響最大的三個特征要素進(jìn)行 分類，它們是：顧

3、客相繼到達(dá)的間隔時間分布、服務(wù) 時間的分布、并列的服務(wù)臺個數(shù)。按照這三個特征要 素分類的排隊(duì)系統(tǒng)，用符號（稱為Kendall記號）表示 為 X/Y/Z 其中X處填寫顧客相繼到達(dá)的間隔時間分布，Y處填寫 服務(wù)時間的分布，Z處填寫并列的服務(wù)臺個數(shù)。 例如M/M/1，表示顧客相繼到達(dá)的間隔時間為負(fù)指 數(shù)分布、服務(wù)時間為負(fù)指數(shù)分布、單服務(wù)臺的模型。 第3頁/共63頁 后來，在1971年關(guān)于排隊(duì)論符號標(biāo)準(zhǔn)化的會議上 決定，將Kendall符號擴(kuò)充為： X/Y/Z/A/B/C 其中前三項(xiàng)意義不變。 A處填寫系統(tǒng)容量限制; B處填寫顧客源中的顧客數(shù)目; C處填寫服務(wù)規(guī)則（如先到先服務(wù)FCFS，后到先 服務(wù)L

4、CFS）。 約定，如略去后三項(xiàng)，即指X/Y/Z/FCFS的 情形。 后面我們只討論先到先服務(wù)FCFS的情形，所以略 去第六項(xiàng)。 第4頁/共63頁 排隊(duì)系統(tǒng)的求解 對于一個排隊(duì)系統(tǒng)，運(yùn)行狀況的好壞既涉及到顧 客的利益，又涉及到服務(wù)機(jī)構(gòu)的利益，還有社會效果 好壞的問題。為了研究排隊(duì)系統(tǒng)運(yùn)行的效率、估計(jì)服 務(wù)質(zhì)量、研究設(shè)計(jì)改進(jìn)措施，必須確定一些基本指標(biāo) ，用以判斷系統(tǒng)運(yùn)行狀況的優(yōu)劣。下面介紹幾種常用 的指標(biāo)。 1)隊(duì)長：把系統(tǒng)中的顧客數(shù)稱為隊(duì)長，它的期望值記 作Ls。而把系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)稱為排隊(duì)長 （隊(duì)列長），它的期望值記作Lq。顯然有 隊(duì)長排隊(duì)長正被服務(wù)的顧客數(shù)。 第5頁/共63頁 2)

5、逗留時間：一個顧客從到達(dá)排隊(duì)系統(tǒng)到服務(wù)完 畢離去的總停留時間稱為逗留時間，它的期望值記 作Ws。 一個顧客在系統(tǒng)中排隊(duì)等待的時間稱為等待時 間，它的期望值記作Wq。顯然有 逗留時間等待時間服務(wù)時間。 3)瞬態(tài)和穩(wěn)態(tài) 把系統(tǒng)中的顧客數(shù)稱為系統(tǒng)的狀態(tài)。考慮在t時刻 系統(tǒng)的狀態(tài)為n的概率，它是隨時刻t而變化的，用 Pn(t)表示，稱為系統(tǒng)的瞬態(tài)。求瞬態(tài)解是很不容易的 ，一般即使求出也很難利用，因此我們常用它的極限 lim Pn(t)Pn t 稱為穩(wěn)態(tài)或稱統(tǒng)計(jì)平衡狀態(tài)的解。 第6頁/共63頁 n =系統(tǒng)有n個顧客時的平均到達(dá)率（單位時 間平均到達(dá)的顧客人數(shù)即是平均到達(dá)率） n =系統(tǒng)有n個顧客時的平均

6、離開率 =對任何n都是常數(shù)的平均到達(dá)率. =對任何n都是常數(shù)的平均離開率. 1/ =期望到達(dá)間隔時間 1/ =期望服務(wù)時間 =服務(wù)強(qiáng)度， 或稱使用因子, /(s) 第7頁/共63頁 q L q W 平均隊(duì)長 平均等待隊(duì)長 平均等待時間 平均逗留時間 s L s W 第8頁/共63頁 1 qs WW ss WL qq WL 公式Little qs LL 將前兩式帶入后式得將前兩式帶入后式得 第9頁/共63頁 0 n ns nPL又因?yàn)橛忠驗(yàn)?1 )( sn nq PsnL 所以，只需要求出Pn即可。 第10頁/共63頁 幾個主要概率分布 一、POISSON分布 設(shè)N(t)表示在時間區(qū)間t0,t0

7、+t)內(nèi)到達(dá)的顧客數(shù)，是隨機(jī)變 量。當(dāng)N(t)滿足下列三個條件時，我們說顧客的到達(dá)符合 Poisson分布。這三個條件是： (1)平穩(wěn)性 在時間區(qū)間t0,t0+t)內(nèi)到達(dá)的顧客數(shù)N(t)，只 與區(qū)間長度t有關(guān)而與時間起點(diǎn)t0無關(guān)。 (2)無后效性 在時間區(qū)間t0,t0+t)內(nèi)到達(dá)的顧客數(shù)N(t)， 與t0以前到達(dá)的顧客數(shù)獨(dú)立。 (3)普通性 在充分短的時間區(qū)間t內(nèi)，到達(dá)兩個或兩個 以上顧客的概率極小，可以忽略不計(jì)，即 Pn(t)o(t) n=2 第11頁/共63頁 在上述三個條件下可以推出 (t)n Pn(t) e-t n=0,1,2, n! 其中表示單位時間平均到達(dá)的顧客數(shù)，即為到 達(dá)率。

8、不難算出，N(t)的數(shù)學(xué)期望和方差分別是： EN(t)t VarN(t)t 第12頁/共63頁 二、負(fù)指數(shù)分布 隨機(jī)變量T的概率密度若是 e-t t0 fT(t) 0 t0 則稱T服從負(fù)指數(shù)分布，它的分布函數(shù)是 1-e-t t0 FT(t) 0 t0 T的數(shù)學(xué)期望和方差分別為： ET1/， Var(T)1/2 負(fù)指數(shù)分布具有下列性質(zhì)： (1)無記憶性或馬爾柯夫性，即 PTt+s / TsPTt (2)當(dāng)顧客到達(dá)符合Poisson分布時，顧客相繼到達(dá) 的間隔時間T必服從負(fù)指數(shù)分布。 第13頁/共63頁 對于Poisson分布，表示單位時間平均到達(dá) 的顧客數(shù)，所以1/表示顧客相繼到達(dá)的平均間 隔時

9、間，而這正和ET的意義相符。 服務(wù)時間符合負(fù)指數(shù)分布時，設(shè)它的概率密 度函數(shù)和分布函數(shù)分別為 fv(t)e-t； Fv(t)1-e-t (t0) 其中表示單位時間能夠服務(wù)完的顧客數(shù)，為服 務(wù)率；而1/表示一個顧客的平均服務(wù)時間，正 是v的期望值。 第14頁/共63頁 密度函數(shù) 0for t0 0 )( tfore tf t T 均值 1 )(TE 方差 2 1 )( TVar 設(shè)隨機(jī)變量 T 分布函數(shù) t etTP 1)( fT(t) t 1 )(TE 第15頁/共63頁 )()0(ttTtPtTP fT(t) tt t fT(t) 是一個嚴(yán)格下降函數(shù) 第16頁/共63頁 )()/(tTPtT

10、ttTP無后效性 )( )( ) ( )( ) ( )/( )( )( tTPe e ee e e tTP ttTP tTP tTandttTP tTttTP t t tt t tt 不管多長時間(t)已經(jīng)過去， 逗留時間的概率分布與下 一個事件的相同. 第17頁/共63頁 t n n etUP TTTMinU ).( 21 21 )( ),.,.( 幾個獨(dú)立的指數(shù)分布的隨 機(jī)變量的最小有一個指數(shù) 分布 幾個獨(dú)立的指數(shù)分布的隨 機(jī)變量的和還是一個指數(shù) 分?jǐn)?shù)的隨機(jī)變量 T (1 +2 +3) T1(1) T1(2) T1(3) min 第18頁/共63頁 指數(shù)分布 0tfor 0 0 )( tf

11、ore tf t T 1 )( TE ! )( )( n et ntXP tn Poisson分布 ttXE )( 服務(wù)時間的概率在t時間內(nèi)已經(jīng)服務(wù)n個顧 客的概率 1/: 平均服務(wù)時間 平均服務(wù)率= 第19頁/共63頁 排隊(duì)系統(tǒng)的狀態(tài)n隨時間變化的過程稱為生滅過程， 設(shè)平均到達(dá)率為n,平均服務(wù)率為n,負(fù)指數(shù)分布排隊(duì)系統(tǒng) （M/M/1/）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示 ： 穩(wěn)態(tài)概率方程如下： 0P0=1P1 n-1Pn-1+n+1Pn+1=nPn+nPn 01 n-1n n+1. 0 1 n-2 n-1 n 1 2 n-1 n n+1 . 生滅過程 第20頁/共63頁 0 1 0 1 PP

12、 0 12 01 1 2 1 0011 2 1 2 1 2 )( 1 PPPPPP 0 123 012 2 3 2 1122 3 2 3 2 3 )( 1 PPPPPP 0 123 0121 1 1 22111 1 )( 1 PPPPPP n n n n n nnnn n n n n n 第21頁/共63頁 1, 0 123 0121 CC n n n 若令若令 0 PCP nn 則則 1 0 0 0 因?yàn)橐驗(yàn)?n n n n PCP 0 0 1 所以所以 n n C P 由前面的推導(dǎo)，可以求出另外的那些量的值。 第22頁/共63頁 最簡單的排隊(duì)系統(tǒng)的模型 最簡單的排隊(duì)系統(tǒng)：是指輸入為最簡單流

13、，服務(wù)時間 為負(fù)指數(shù)分布的排隊(duì)服務(wù)系統(tǒng) 并且，此處我們假設(shè)：服務(wù)規(guī)則為：先到先服務(wù)；在 多個服務(wù)站的情況，假設(shè)顧客排成一個單一的隊(duì)伍。 第23頁/共63頁 假定： 1. 平均到達(dá)率為常數(shù)（對所有的n,有n = ） 2. 服務(wù)機(jī)構(gòu)的平均服務(wù)率也是常數(shù) 單個服務(wù)站時，有n = ， 多個服務(wù)站時，若設(shè)S為并聯(lián)的服務(wù)站個數(shù)，則有 ,.)1,( ),.,2 , 1( SSnS Snn n 3. 1 S 即服務(wù)機(jī)構(gòu)總的服務(wù)效率應(yīng)高于顧客的平均到達(dá) 率 保證系統(tǒng)最終能進(jìn)入穩(wěn)定狀態(tài)。 這樣就可以把生滅過程的結(jié)論拿來用！ 一、顧客源無限、隊(duì)長不受限制的排隊(duì)模型 第24頁/共63頁 01 n-1n n+1. 穩(wěn)態(tài)

14、概率方程如下： P0=P1 Pn-1+Pn+1=Pn+Pn 設(shè)=/1，考慮到Pn=1，解得 P0=1- Pn=(1-) n , n1 這里的稱為服務(wù)強(qiáng)度，也稱話務(wù)強(qiáng)度，它刻劃了服務(wù)機(jī)構(gòu)的 繁忙程度，所以又稱服務(wù)機(jī)構(gòu)的利用率。 此時的排隊(duì)系統(tǒng)(M/M/1/）的生滅過程可用下面 的狀態(tài)轉(zhuǎn)移圖表示： 1、S1時，即M/M/1模型 第25頁/共63頁 服務(wù)系統(tǒng)的其他各項(xiàng)運(yùn)行指標(biāo)計(jì)算如下 ： 平均隊(duì)長： 平均排隊(duì)長： 1 ) 1 1 ()1()()1( )()1()1( 0 000 d d d d d d nnPL n n n n n n n ns )( 2 sq LL 第26頁/共63頁 平均逗留時間

15、: 平均等待時間: 1 s s L W )( q q L W 第27頁/共63頁 再計(jì)算（1）顧客在系統(tǒng)中停留時間超過t的概率？ 假定一個顧客來到系統(tǒng)時，系統(tǒng)中已有n個人，則該 顧客在系統(tǒng)中的停留時間應(yīng)該是系統(tǒng)對前n個顧客的 服務(wù)時間加上對他的服務(wù)時間。 設(shè)T1，T2，Tn表示前n個顧客的服務(wù)時間，Tn+1 表示對該顧客的服務(wù)時間。 令Sn+1=T1+T2+Tn+Tn+1,則 ,)( ! )( 1 tn n et n Sf t tn n dtet n tSP 0 1 )( ! 此時是愛爾朗分布 第28頁/共63頁 顧客在系統(tǒng)中停留時間小于t的概率（Ws平均逗留時間） 顧客在系統(tǒng)中停留時間超過t

16、的概率 t t tn n n n nnS edtet n tSPPtWP )1( 0 0 0 1 1)( ! )1( t SS etWPtWP )1( 1 第29頁/共63頁 （2）已經(jīng)有人等待的情況下還要等待多久？ 1 )(1 )0E( 0 P W WW q qq 第30頁/共63頁 第31頁/共63頁 2、有S個并聯(lián)服務(wù)站時， )( , !)( )/( )!()( )( ).)( ),.,2 , 1( , ! )/( 11 0121 123 0121 Sn SSSS Sn n C Sn n SSn n SSn n n n n n ,.)1,( ),.,2 , 1( SSnS Snn n 因

17、為此時有 所以 第32頁/共63頁 1 1 ! )/( ! )/( 1 )( ! )/( ! )/( 1 1 0 1 0 0 S n Sn S nSn Sn Sn S Sn SSn P )( , ! )/( ),.,1 , 0( , ! )/( 0 0 SnP SS SnP n P Sn S n n 第33頁/共63頁 因?yàn)樵诙鄠€服務(wù)站的情況下， S 并令n-S=j,則有 2 0 0 00 0 0 0 )1( ! )/( ) 1 1 ( ! )/( )( ! )/( ! )/( )( S P d d P Sd d P S P S jjPPSnL S j S j S Snj j S j jSnq

18、 平均排隊(duì)長： 其他參數(shù)如：平均隊(duì)長Ls，平均逗留時間Ws，平均等待時 間Wq，都可以通過Little公式求出。 第34頁/共63頁 例：某廠有大量同一型號的車床，當(dāng)該種車床損壞 后或送機(jī)修車間或由機(jī)修車間派人來修理。已知該 種車床損壞率服從泊松分布，平均每天2臺。又機(jī)修 車間對每臺損壞車床的修理時間為負(fù)指數(shù)分布的隨 機(jī)變量，平均每臺的修理時間為 天。但 是一個 與機(jī)修人員編制及維修設(shè)備配備好壞（即與機(jī)修車 間每年開支費(fèi)用K）有關(guān)的函數(shù)。已知 /1 )1900( ,001. 01 . 0)(元 KKK 又已知機(jī)器損壞后，每臺每天的生產(chǎn)損失為400元， 試決定使該廠生產(chǎn)最經(jīng)濟(jì)的K及 第35頁/共

19、63頁 解：問題包含兩個費(fèi)用：機(jī)器損壞造成的生產(chǎn)損失 S1機(jī)修車間的開支S2，要使整個系統(tǒng)最經(jīng)濟(jì)就是S S1S2最小。以下以一個月為期計(jì)算 S1正在修理和待修機(jī)器數(shù)每臺每天的生產(chǎn)損失 每個月的工作日數(shù) ) 9 . 1001. 0 2 (8800) 001. 01 . 0 (8800 )(880022400 KK LS 12 2 KS 第36頁/共63頁 ) 9 . 1001. 0 2 (8800 12 K K S 0 )9 . 1001. 0( 6 .17 12 1 2 KdK dS 2580,65.17,16430 2 .211)9 . 1001. 0( 2 SK K 第37頁/共63頁 例

20、：病人到達(dá)只有一個醫(yī)生的醫(yī)院門診部的時間平 均每20分鐘一個，設(shè)對每個病人的診治時間平均為 15分鐘，又知道以上兩種時間均為負(fù)指數(shù)的概率分 布。若該門診部希望到達(dá)的病人90%以上能在候診 室找到座位，則該醫(yī)院最少應(yīng)該設(shè)置多少座位？ 解：設(shè)候診室有座位C個，再加上診治中的病人的座 位共有C1個。按照題目要求，該醫(yī)院門診部內(nèi)病 人總數(shù)不多于C1個的概率為0.90,即 6 9 . 01)1( 9 . 0 2 1 0 1 0 1 0 C P P C C n n C n n C n n 第38頁/共63頁 二、顧客源無限、隊(duì)長受限制的排隊(duì)模型 當(dāng)系統(tǒng)的容量有限制(為M)時，設(shè)顧客的平均到達(dá) 率仍為常數(shù)，

21、但由于系統(tǒng)中已有M個顧客時，新到的顧 客將自動離去，所以有 )( 0 )1,.,1 , 0( Mn Mn n 1、 S1時 )( 0 ),.,1( )/( n Mn Mn C n n 所以有 第39頁/共63頁 )1( 1 1 1 1 0 n 0 M M n P )1,( 1 1 1 MnP n M n )1( 1 )1( 1 nP 1 1 0 M MM n nS M L 其他指標(biāo)的計(jì)算： 先計(jì)算有效輸入率eff 由于在隊(duì)長受限的情況下，當(dāng)達(dá)到顧客數(shù)n大于或等 于M時，新來顧客會自動離去。因此雖然顧客以平 均為的速度來到服務(wù)系統(tǒng)，但由于一部分的顧客離 去，真正進(jìn)入系統(tǒng)的的顧客的輸入率是小于的。

22、 第40頁/共63頁 )1( 0 P eff eff s s eff q q eff Sq L W L W LL 由于系統(tǒng)中的平均排隊(duì)的顧客數(shù)總是等于系統(tǒng)中的 平均顧客數(shù)平均正在接受服務(wù)的顧客數(shù)，即： )1()1( 0 1 PLPnLL S M n n eff Sq 第41頁/共63頁 對于隊(duì)長受限制的排隊(duì)模型，當(dāng)系統(tǒng)中有M個 顧客時，新到顧客會自動離開，故不一定要求 時，有當(dāng)1, 1 ),.2 , 1( 00 MnPPP n n )1( )1/(1. 0 MPP M )1( 2 0 M nPL M n nS 第42頁/共63頁 2、 S個并聯(lián)服務(wù)站時 對于隊(duì)長受限制的排隊(duì)模型，當(dāng)系統(tǒng)中有M個

23、顧客 時，新到顧客會自動離開，故當(dāng)n1時 01 S+1 N (N-1) (N-S+1) (N-S) 2 S S S .N N-1.S S-1 第51頁/共63頁 由上圖中知道，S1時，有 ),.,1( )( 0 ),.,1 , 0( ,)( Nn Nn NnnN n n S1時，有 ,.)1,( ),.,1( )( 0 ),.,1 , 0( ,)( SSnS Snn Nn NnnN n n 由于當(dāng)n=N時， n=0,所以系統(tǒng)最終一定能達(dá)到穩(wěn)定狀 態(tài)，所以可用求解穩(wěn)定狀態(tài)的方法進(jìn)行處理。 第52頁/共63頁 S1時 )( 0 ),.,1( )/( )!( ! Nn Nn nN N C n n )

24、,.,1( )/( )!( ! )/( )!( ! 1 0 N 0n 0 NnP nN N P nN N P n n n )1( )( )!( ! )1()1( 0 0 1 0 1 PLnPL P nN N nPnL q N n nS N n n N n nq 第53頁/共63頁 由于顧客輸入率n隨系統(tǒng)狀態(tài)而變化，因此平均 輸入率可按照下式計(jì)算： )()( 00 s N n n n nn LNPnNP 且有 q q s s L W L W , 第54頁/共63頁 S1時， )( 0 ),.,1,( )/( !)!( ! ),.,1( )/( !)!( ! Nn NSSn SSnN N Sn n

25、nN N C n Sn n n N 1Sn -1S 0n N Sn 0 0 0 )( )/( !)!( ! )/( )!( ! 1 )( , 0 ),.,( ,)/( !)!( ! ),.,0( ,)/( !)!( ! nq n Sn n n Sn n n PSnL SSnN N nN N P Nn NSnP SSnN N SnP nnN N P 第55頁/共63頁 例：設(shè)有一名工人負(fù)責(zé)照管6臺自動機(jī)床。當(dāng)機(jī)床需 要加料、發(fā)生故障或刀具磨損時就自動停車，等待 工人照管。設(shè)平均每臺機(jī)床兩次停車的時間間隔為1 小時，又設(shè)每臺機(jī)床停車時，需要工人平均照管的 時間為0.1小時。以上兩項(xiàng)時間均服從負(fù)指數(shù)分布， 試計(jì)算該系統(tǒng)的各項(xiàng)指標(biāo)。 解： 6, 1 . 0 N 00 1 1 6 . 0) 1 . 0 ( )!16 ( ! 6 PPP ) 62 ( ,) 1 . 0 ( )!6 ( ! 6 0 nP n P n n 數(shù)據(jù)見下表 第56頁/共63頁 n 等待照管的等待照管的 機(jī)床數(shù)機(jī)床數(shù)n-1 Pn/P0Pn(n-1)PnnPn 0010.484500 100.60.290700.2907 210.30.14540.14540.2908 320.120.0582