排隊論PPT學(xué)習(xí)課件學(xué)習(xí)教案

1、會計學(xué)1排隊排隊(pi du)論論PPT學(xué)習(xí)課件學(xué)習(xí)課件第一頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案2大綱要求：掌握排隊論的基本概念、常見(chn jin)的到達時間間隔分布和服務(wù)時間分布特性，生滅過程及穩(wěn)態(tài)概率。單服務(wù)臺負指數(shù)分布排隊模型；多服務(wù)臺負指數(shù)排隊模型；排隊系統(tǒng)設(shè)計的最優(yōu)化重點：掌握M/M/1模型及其應(yīng)用難點：到達流的穩(wěn)態(tài)概率和系統(tǒng)狀態(tài)轉(zhuǎn)移概率及其優(yōu)化服務(wù)設(shè)計自學(xué)：M/G/1模型第1頁/共72頁第二頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案3第2頁/共72頁第三頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(

2、dinz)教案4到達的顧客要求的服務(wù)服務(wù)機構(gòu)機械壞了 修理 修理工人修理工人 領(lǐng)取配件 管理員病人 就診 醫(yī)生打電話 通話 交換臺文件 打印(d yn) 打印(d yn)機飛機降落 降落 跑道指揮機構(gòu)顧客 就餐 服務(wù)員汽車 路口 紅綠燈第3頁/共72頁第四頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案5排隊結(jié)構(gòu)服務(wù)機構(gòu)顧客源顧客到達排隊規(guī)則服務(wù)規(guī)則離去圖1 排 隊系統(tǒng)示意圖第4頁/共72頁第五頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案6第5頁/共72頁第六頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案7第

3、6頁/共72頁第七頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案8112n. . .12n。單隊單服務(wù)臺多隊多服務(wù)臺（并列)單隊多服務(wù)臺（并列）12n.12312單隊多服務(wù)臺（串列）混合形式第7頁/共72頁第八頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案9 2)服務(wù)方式分為單個顧客服務(wù)和成批顧客服務(wù)。服務(wù)方式分為單個顧客服務(wù)和成批顧客服務(wù)。 3)服務(wù)時間分為確定服務(wù)時間分為確定(qudng)型型(定常時間）和隨機型。定常時間）和隨機型。 4)服務(wù)時間的分布在這里我們假定是平穩(wěn)的。服務(wù)時間的分布在這里我們假定是平穩(wěn)的。 我們研究的問題是：

4、輸入是服從(fcng)某種分布，顧客的到達是相互獨立到達的平穩(wěn)過程；各列間不能相互轉(zhuǎn)移、中途不能退出；單個單個地服務(wù)方式，服務(wù)服從(fcng)某種分布， FCFS。第8頁/共72頁第九頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案10最主要的、影響最大的是：最主要的、影響最大的是：顧客相繼顧客相繼(xingj)到達的間隔時間分布到達的間隔時間分布服務(wù)時間的分布服務(wù)時間的分布服務(wù)臺數(shù)服務(wù)臺數(shù)，1953提出了分類法，稱為提出了分類法，稱為Kendall記號記號(適用于并列服務(wù)臺適用于并列服務(wù)臺),1971又擴展成為：又擴展成為：X/Y/Z/A/B/C第9頁/共72頁

5、第十頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案11第10頁/共72頁第十一頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案12Z填寫并列的服務(wù)臺數(shù)填寫并列的服務(wù)臺數(shù)A排隊系統(tǒng)排隊系統(tǒng)(xtng)的最大容量的最大容量NB顧客源數(shù)量顧客源數(shù)量m C排隊規(guī)則（排隊規(guī)則（FCFS、LCFS等。本章僅研究等。本章僅研究FCFS的排隊規(guī)則）的排隊規(guī)則）如如 M/M/1/FCFS即為顧客到達時間間隔為負指數(shù)分布，服務(wù)時間為負指數(shù)分布，單臺，無限容量，無限源，先到先服務(wù)的排隊系統(tǒng)即為顧客到達時間間隔為負指數(shù)分布，服務(wù)時間為負指數(shù)分布，單臺，無限容量，無

6、限源，先到先服務(wù)的排隊系統(tǒng)(xtng)模型。模型。第11頁/共72頁第十二頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案13( (靜態(tài)優(yōu)化靜態(tài)優(yōu)化) )，最優(yōu)運營（動態(tài)優(yōu)化）。，最優(yōu)運營（動態(tài)優(yōu)化）。第12頁/共72頁第十三頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案14統(tǒng)計(tngj)推斷最優(yōu)設(shè)計性態(tài)問題(wnt)排隊系統(tǒng)研究問題階段示意圖排隊系統(tǒng)研究問題階段示意圖第13頁/共72頁第十四頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案15第14頁/共72頁第十五頁，共72頁。2022-7-6運籌學(xué)校級重點

7、建設(shè)(jinsh)課程電子教案16 2、根據(jù)排隊(pi du)系統(tǒng)對應(yīng)的理論模型求出用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)量指標的概率分布或特征數(shù)。 數(shù)量指標主要包括:(1) 隊長：系統(tǒng)中的顧客數(shù)，它的數(shù)學(xué)期望記為Ls 。 隊列長：系統(tǒng)中排隊(pi du)等待服務(wù)的顧客數(shù)，它的數(shù)學(xué)期望記為Lq 。 系統(tǒng)中顧客數(shù)Ls =系統(tǒng)中排隊(pi du)等待服務(wù)的顧客數(shù)Lq +正被服務(wù)的顧客數(shù)(2) 逗留時間：指一個顧客在系統(tǒng)中的停留時間，它的數(shù)學(xué)期望記為Ws。 第15頁/共72頁第十六頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案17 等待時間：指一個顧客在系統(tǒng)中排隊等待的時間，它的數(shù)

8、學(xué)期望記為等待時間：指一個顧客在系統(tǒng)中排隊等待的時間，它的數(shù)學(xué)期望記為Wq 。逗留時間逗留時間=等待時間等待時間+服務(wù)時間服務(wù)時間(3)忙期：指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次忙期：指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次(zi c)為空閑這段時間長度。（忙期和一個忙期中平均完成服務(wù)顧客數(shù)都是衡量服務(wù)機構(gòu)效率的指標，忙期關(guān)系到工作強度）為空閑這段時間長度。（忙期和一個忙期中平均完成服務(wù)顧客數(shù)都是衡量服務(wù)機構(gòu)效率的指標，忙期關(guān)系到工作強度） 為了計算上述的數(shù)量指標，必須首先計算系統(tǒng)狀態(tài)的概率為了計算上述的數(shù)量指標，必須首先計算系統(tǒng)狀態(tài)的概率 系統(tǒng)狀態(tài)：系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。系統(tǒng)狀態(tài)：系

9、統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。第16頁/共72頁第十七頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案18 狀態(tài)概率：用狀態(tài)概率：用Pn(t)表示表示,即在即在t時刻系統(tǒng)中有時刻系統(tǒng)中有n個顧客個顧客(gk)的概率，也稱瞬態(tài)概率。它是表述系統(tǒng)的各種性能指標的基礎(chǔ)。的概率，也稱瞬態(tài)概率。它是表述系統(tǒng)的各種性能指標的基礎(chǔ)。 狀態(tài)的可能值：狀態(tài)的可能值： 隊長沒有限制時：隊長沒有限制時：n=0 ，1，2， 隊長有限制時：隊長有限制時：n= 0，1，2，3，N 即時制：服務(wù)臺個數(shù)是即時制：服務(wù)臺個數(shù)是c時，時，n=0 ，1，c 求解狀態(tài)求解狀態(tài)(zhungti)概率概率Pn(t)方

10、法：是建立含方法：是建立含Pn(t)的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此我們常常使用它的極限的微分差分方程，通過求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解一般求出確定值比較困難，即便求得一般也很難使用。因此我們常常使用它的極限(如果存在的話如果存在的話)：第17頁/共72頁第十八頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案19nttnp)(plim穩(wěn)態(tài)的物理意義見右圖，系統(tǒng)的穩(wěn)態(tài)一般很快都能達到，但實際中達不到穩(wěn)態(tài)的現(xiàn)象也存在穩(wěn)態(tài)的物理意義見右圖，系統(tǒng)的穩(wěn)態(tài)一般很快都能達到，但實際中

11、達不到穩(wěn)態(tài)的現(xiàn)象也存在(cnzi)。值得注意的是求穩(wěn)態(tài)概率。值得注意的是求穩(wěn)態(tài)概率Pn并不一定求并不一定求t的極限的極限,而只需求而只需求Pn(t)=0 即可。即可。過渡狀態(tài)穩(wěn)定狀態(tài)pnt圖3 排隊系統(tǒng)狀態(tài)變化示意圖 稱為稱為(chn wi)穩(wěn)態(tài)穩(wěn)態(tài)(steady state)解，或稱統(tǒng)計平衡狀態(tài)解，或稱統(tǒng)計平衡狀態(tài) (Statistical Equilibrium State)的解。的解。第18頁/共72頁第十九頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案20第19頁/共72頁第二十頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案2

12、1第20頁/共72頁第二十一頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案22第21頁/共72頁第二十二頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案23第22頁/共72頁第二十三頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案24隨機變量：數(shù)隨機變量：數(shù) 隨著實驗的結(jié)果的不同而變化隨著實驗的結(jié)果的不同而變化 離散型：離散型：的所有可能只有限的所有可能只有限(yuxin)或至多可列個或至多可列個 連續(xù)型：連續(xù)型：（）取值于某個區(qū)間（）取值于某個區(qū)間（a，b）分布函數(shù)分布函數(shù)(連續(xù)連續(xù)): xpxF aFbFbap

13、的概率分布的概率分布(離散): iixpxpi=1,2,311iixp第23頁/共72頁第二十四頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案25數(shù)學(xué)期望數(shù)學(xué)期望:(離散) E()= 1iiipxdxxxf (連續(xù)) E()= 方差方差: 2EED EE22= BApBpABp條件概率條件概率:密度函數(shù)密度函數(shù):(連續(xù)) dttfxFx 0 xf 1dttf,第24頁/共72頁第二十五頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案26式中式中為常數(shù)為常數(shù)(chngsh)(0)，稱，稱X服從參數(shù)為服從參數(shù)為的泊松分布。的泊松分布。若在上

14、式中引入時間參數(shù)若在上式中引入時間參數(shù)t，即令，即令t代替代替，則有：，則有：!nenxPnn=0,1,2, （1）tnnenttP!)(t0，n=0,1,2, （2）第25頁/共72頁第二十六頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案27)()(,1221ntNtNPttPn（t2t1，n0）第26頁/共72頁第二十七頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案28 無后效性（獨立性）：各區(qū)間內(nèi)的顧客無后效性（獨立性）：各區(qū)間內(nèi)的顧客(gk)到達數(shù)相互獨立，即到達數(shù)相互獨立，即Markov性。性。. . . . . . . t

15、0 t1 t2 tn-1 tn平穩(wěn)性：即對于足夠小的平穩(wěn)性：即對于足夠小的t，在時間，在時間(shjin)區(qū)間區(qū)間t，t+t)內(nèi)有內(nèi)有1個顧客到達的概率為個顧客到達的概率為)()(1tttttP， 當(dāng)當(dāng)Pn(t1,t2)符合于下述三個條件時，我們說顧客到達過程就是泊松過程或者說顧客到達形成普阿松流。符合于下述三個條件時，我們說顧客到達過程就是泊松過程或者說顧客到達形成普阿松流。 普阿松流的三個特性：普阿松流的三個特性：設(shè)表示單位時間內(nèi)有一個顧客到達的概率第27頁/共72頁第二十八頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案29 普通性：對充分小的普通性：對充分小的

16、t,在時間在時間(shjin)區(qū)間區(qū)間t,t+t）內(nèi)有）內(nèi)有2個或個或2個以上顧客到達的概率是個以上顧客到達的概率是t一高階無窮小一高階無窮小.)(1),(0tottttP 令令t1=0,t2=t, 則則Pn(t1,t2)=Pn(0,t)=Pn(t) 也就是也就是(jish)在在t,t+t內(nèi)有一個顧客到達的概率與內(nèi)有一個顧客到達的概率與t無關(guān)無關(guān),而與而與t成正比。成正比。 0 是常數(shù)，稱為概率強度是常數(shù)，稱為概率強度2)(),(nntotttP即即由此知，在由此知，在(t，t+t)區(qū)間內(nèi)沒有顧客到達的概率為區(qū)間內(nèi)沒有顧客到達的概率為:ttttttptttpii)(1),(1),(10區(qū)間長度

17、為t時有n個顧客的概率第28頁/共72頁第二十九頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案30 為了求為了求Pn(t)，即，即Pn(0,t)，需要研究它在時刻，需要研究它在時刻t到到t+t時刻的改變量，也就是要建立時刻的改變量，也就是要建立Pn(t)的微分方程。的微分方程。 對于區(qū)間對于區(qū)間0，t+t)可以分成可以分成0，t)和和t，t+t)，其到達總數(shù)是，其到達總數(shù)是n，不外有下列三種，不外有下列三種(sn zhn)情況：所以有：情況：所以有：第29頁/共72頁第三十頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案310，t)t,t+t

18、0,t+t 區(qū)間情形個數(shù)概率個數(shù)概率概率A n pn(t) 0 1-t+ pn(t)(1-t+ (t) (t)B n-1 pn-1(t) 1t pn-1(t)t(t) (t)n-2 Pn-2(t) 2C n-3 Pn-3(t) 30 P0(t) n第30頁/共72頁第三十一頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案32令令t0取極限取極限(jxin)（并注意初始條件）得：（并注意初始條件）得：當(dāng)當(dāng)n=0時，沒有時，沒有(mi yu)B，C兩種情況，則：兩種情況，則：1)0(0P)()(00tPdttdP(4)()()1)()(1tttPttPttPnnn)()()

19、()()(1tttPttPtPttPnnnntttPtPttPttPnnnn)()()()()(1)()()(1tPtPdttdPnnnn0 (3)(0)0nP第31頁/共72頁第三十二頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案33代初始條件代初始條件(t=0)有有：CCt01n C C = 0= 0ttP)(n0（3）式兩端）式兩端(lin dun)乘乘 et 并移項得：并移項得：tetP)(0(5)（沒有顧客到達的概率）dttPtdP)()(00由上式得：由上式得：CttP)(n0兩邊兩邊(lingbin)積分得：積分得：一階臺勞展開為一階臺勞展開為1-t第3

20、2頁/共72頁第三十三頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案34tntnetPetPdtd)()(1將將n=1,2,3代入（代入（6）得：）得：積分得：積分得：11101)()(dtetPetPtnttn(6)110011)()(dtetPetPttt(注意利用注意利用(5)式式)tdteettt1011tntntnetPetPedttdP)()()(1tntnntetPetPdttdPe)()()(1第33頁/共72頁第三十四頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案35如此繼續(xù)如此繼續(xù)(jx)遞推下去得：遞推下去得：te

21、ttP! 2)()(22（2個顧客到達的概率）個顧客到達的概率）（n個顧客到達的概率）個顧客到達的概率）tnnenttP!)()( 即隨機變量即隨機變量N(t)=n服從泊松分布。它的數(shù)學(xué)期望服從泊松分布。它的數(shù)學(xué)期望(qwng)和方差為：和方差為：tettP)(1（1個顧客到達的概率個顧客到達的概率）11011102111)()(dteetdtetPetPtttttt2221t第34頁/共72頁第三十五頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案361)0(,)(nxfexf則有由高等數(shù)學(xué)知，若設(shè)由高等數(shù)學(xué)知，若設(shè).!.! 212nxxxenx即：即：tkkekt!

22、)(0!)()()(11ntnetnPtNEnntnn)!1()(11nttennt令令k=n-1，則：，則：!)()(0kttetNEkkttetetNEtt)(第35頁/共72頁第三十六頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案372121)()!1()()!2()(tntntttennnttttttettett22)() 1()() 1(ttNVar)(即：即：21221)(!)()()(tntnnettPnnntnn22)()()(tNEtNEtNVar同理方差為：同理方差為：211121)()!1()()!1()() 1()()!1()(tntntnte

23、tntnennntnnt第36頁/共72頁第三十七頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案38其概率密度函數(shù)為：其概率密度函數(shù)為：tTTedtdFtf)(t0tTetPtF1)(1)(0t0tetP)(0 沒有顧客到達的概率沒有顧客到達的概率為：為： (由（由（5）式而來）式而來)第37頁/共72頁第三十八頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案39 由前知，由前知，表示單位時間內(nèi)顧客平均到達數(shù)，這里表示單位時間內(nèi)顧客平均到達數(shù)，這里1/表示顧客到達的平均間隔時間，兩者是吻合表示顧客到達的平均間隔時間，兩者是吻合(wnh)

24、的。的。 可以證明，間隔時間可以證明，間隔時間T獨立且服從負指數(shù)分布與顧客到達形成泊松流是等價的。獨立且服從負指數(shù)分布與顧客到達形成泊松流是等價的。 下面我們再談一下服務(wù)時間下面我們再談一下服務(wù)時間(shjin)的分布：的分布： 對顧客的服務(wù)時間對顧客的服務(wù)時間(shjin)，實際是系統(tǒng)處于忙期時兩顧客相繼離開系統(tǒng)的時間，實際是系統(tǒng)處于忙期時兩顧客相繼離開系統(tǒng)的時間(shjin)間隔，一般地也服從負指數(shù)分布，即：間隔，一般地也服從負指數(shù)分布，即：即即T服從負指數(shù)分布，由概率論知它的期望及方差為：服從負指數(shù)分布，由概率論知它的期望及方差為：1TE21TVar dxxxfTE)(第38頁/共72頁

25、第三十九頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案40其中：其中：表示單位時間內(nèi)能被服務(wù)完成的顧客數(shù)，即平均表示單位時間內(nèi)能被服務(wù)完成的顧客數(shù)，即平均(pngjn)服務(wù)率。服務(wù)率。 1/表示一個顧客的平均表示一個顧客的平均(pngjn)服務(wù)時間。服務(wù)時間。 3.愛爾朗愛爾朗(Erlang)分布分布 設(shè)設(shè)v1, v2，, vk是是k個獨立的隨機變量個獨立的隨機變量(su j bin lin)，服從相同參數(shù)，服從相同參數(shù)k的負指數(shù)分布，那么：的負指數(shù)分布，那么：tetF1)(tetf)(，則，則令令 ，則，則稱為稱為服務(wù)強度服務(wù)強度。第39頁/共72頁第四十頁，共7

26、2頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案41 串列的串列的k個服務(wù)臺，每臺服務(wù)時間相互獨立，服從相同的負指數(shù)分布（參數(shù)個服務(wù)臺，每臺服務(wù)時間相互獨立，服從相同的負指數(shù)分布（參數(shù)(cnsh)k），那么一顧客走完），那么一顧客走完k個服務(wù)臺總共所需要服務(wù)時間就服從上述的個服務(wù)臺總共所需要服務(wù)時間就服從上述的k階階Erlang分布。分布。0)!1()()(1tekktktftkkk則稱則稱T服從服從(fcng)k階愛爾朗分布，其特征值為階愛爾朗分布，其特征值為:1TE21kTVar,kT 21的概率密度是的概率密度是(可以證明可以證明)當(dāng)當(dāng)k=1k=1時，時， Erla

27、ng分布即為負指數(shù)分布；分布即為負指數(shù)分布；當(dāng)當(dāng)k增加時，增加時， Erlang分布逐漸變?yōu)閷ΨQ的；分布逐漸變?yōu)閷ΨQ的；當(dāng)當(dāng)k 30時，時， Erlang分布近似于正態(tài)分布；分布近似于正態(tài)分布；每一個服從每一個服從k ，因此，因此E(Ti)=1/ k ，且，且Ti之間相互獨立之間相互獨立bk(t)tk=1k=21/ Erlang分布曲線分布曲線k=3第40頁/共72頁第四十一頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案42 例例:有易碎物品有易碎物品500件件,由甲地運往乙地由甲地運往乙地,根據(jù)以往統(tǒng)計資料根據(jù)以往統(tǒng)計資料,在運輸過程中易碎物品按普阿松流發(fā)生破碎在運

28、輸過程中易碎物品按普阿松流發(fā)生破碎,其概率為其概率為0.002,現(xiàn)求現(xiàn)求:1.破碎破碎3件物品的概率件物品的概率;2.破碎少于破碎少于3件的概率和多于件的概率和多于3件的概率件的概率;3.至少至少(zhsho)有一件破損的概率有一件破損的概率. 解解:1.求破碎求破碎3件物品的概率件物品的概率: =0.002500=1 則則 P(k=3)=(3/3！)e-=(13/3！)e-1=0.0613 即物品破碎即物品破碎3件的概率為件的概率為6.13 2.破碎物品少于破碎物品少于3件的概率件的概率:第41頁/共72頁第四十二頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案

29、43 破碎物品少于破碎物品少于3件的概率件的概率(gil)為為91.97破碎物品多于破碎物品多于3件的概率件的概率(gil)為為:02. 098. 01!1430kkekp3.至少至少(zhsho)有一件破碎的概率為有一件破碎的概率為 Pk1=1-(1k/k!)e-=1-(10/0!)e-1=0.6329197. 02111!2120eekkknp第42頁/共72頁第四十三頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案44研究對象為單隊、單服務(wù)臺（服務(wù)臺數(shù)為研究對象為單隊、單服務(wù)臺（服務(wù)臺數(shù)為1），包括：），包括：（1）標準）標準(biozhn)M/M/1模型（模型（

30、M/M/1/）；）；（2）系統(tǒng)容量有限制（）系統(tǒng)容量有限制（M/M/1/N/）（3）有限顧客源（）有限顧客源（M/M/1/m）第43頁/共72頁第四十四頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案45 以后各節(jié)將介紹幾個常見以后各節(jié)將介紹幾個常見(chn jin)的排隊模型。對排隊模型，在給定輸入和服務(wù)條件下，主要研究系統(tǒng)的下述運行指標：的排隊模型。對排隊模型，在給定輸入和服務(wù)條件下，主要研究系統(tǒng)的下述運行指標： (1)系統(tǒng)的平均隊長系統(tǒng)的平均隊長Ls(期望值期望值)和平均隊列長和平均隊列長Lq期望值；期望值； (2)系統(tǒng)中顧客平均逗留時間系統(tǒng)中顧客平均逗留時間Ws

31、與隊列中平均等待時間與隊列中平均等待時間Wq； 本節(jié)只研究本節(jié)只研究M/M/1模型，下面分三種情況討論：模型，下面分三種情況討論：第44頁/共72頁第四十五頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案461、輸入過程：顧客源無限，顧客單個到達，相互獨立，服從普阿松分布，平穩(wěn)；2、排隊規(guī)則：單隊，隊長無限制，F(xiàn)CFS。3、服務(wù)機構(gòu)：單服務(wù)臺，各顧客服務(wù)時間相互獨立，服從負指數(shù)分布。此外：假設(shè)到達時間間隔和服務(wù)時間是相互獨立的。標準的標準的M/M/1模型即為模型即為M/M/1/FCFS模型模型第45頁/共72頁第四十六頁，共72頁。2022-7-6運籌學(xué)校級重點建

32、設(shè)課程電子(dinz)教案47區(qū)間(t,t+t)情況時刻t 的顧客 到達 離去時刻t+t的顧客(t, t+t)的概率0, t+t的概率(略去(t)Ann1-t+(t)1-t+(t)Pn(t)(1-t)(1-t)Bn+1n1-t+(t)t+(t)Pn+1(t) (1-t)(t)Cn-1nt+(t)1-t+(t)Pn-1(t) (t)(1-t)Dnnt+(t)t+(t)Pn(t) (t)(t)第46頁/共72頁第四十七頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案48 由于這四種情況是互不相容由于這四種情況是互不相容(xin rn)的，所以的，所以Pn(t+t)應(yīng)是

33、這四項之和，將所有的高階無窮小合并，則有：應(yīng)是這四項之和，將所有的高階無窮小合并，則有：tttPtttPtttPttPnnnn)1)()()1)(1)()(1)()1 ()(1ttttPn)()()()()()(1)(11ttPttPtPtttttPnnnn)()()()(11tttPttPnn第47頁/共72頁第四十八頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案49)()()()1)(11tttPttPtttPnnntttPtPtPttPttPnnnnn)()()()()()()(11令令t0，得關(guān)于，得關(guān)于Pn(t)的微分差分的微分差分(ch fn)方程：方程

34、：)()()()()(11tPtPtPdttdPnnnn(1) 當(dāng)當(dāng)n=0時，只有表中的（時，只有表中的（A）、（）、（B）兩種情況，因為在較小的）兩種情況，因為在較小的t內(nèi)不可能內(nèi)不可能(knng)發(fā)生（發(fā)生（D）（到達后即離去），若發(fā)生可將）（到達后即離去），若發(fā)生可將t取小即可。取小即可。第48頁/共72頁第四十九頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案50)()1)()1)()(100tttPttPttP)()()(100tPtPdttdP(2) 這種系統(tǒng)狀態(tài)(n)隨時間變化的過程(guchng)就是生滅過程(guchng)（Birth and D

35、eath Process），它可以描述細菌的生滅過程(guchng)。 對于方程(1)、(2)求解很麻煩，即便求得解也是瞬態(tài)解，無法應(yīng)用。為此,我們只要求得穩(wěn)態(tài)解即可。 穩(wěn)態(tài)時，Pn(t)與時間無關(guān)，可以寫成Pn， 它對時間的導(dǎo)數(shù)為0，所以由(1)、(2)兩式得：在時刻t系統(tǒng)處于無顧客狀態(tài)(zhungti)，而在t+t時刻內(nèi)又沒有顧客來到系統(tǒng)（必然沒有離去事件）在時刻t系統(tǒng)有一個顧客接受服務(wù)，在t+t時刻內(nèi)服務(wù)完畢離去，且在t+t時刻內(nèi)又沒有顧客來到系統(tǒng)第49頁/共72頁第五十頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案510)(11nnnPPP010PP(3

36、)(4) 上式即為關(guān)于上式即為關(guān)于(guny)Pn的差分方程。由此可得該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖：的差分方程。由此可得該排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移圖：012n-1nn+1. .狀態(tài)轉(zhuǎn)換圖由（由（4）得：）得：001PPP其中其中服務(wù)強度服務(wù)強度 將其代入（將其代入（3）式并令）式并令n=1,2,(也可從狀態(tài)轉(zhuǎn)移圖中看出狀態(tài)平衡也可從狀態(tài)轉(zhuǎn)移圖中看出狀態(tài)平衡(pnghng)方程方程)得：得：第50頁/共72頁第五十一頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案520)(120PPPn=10)(020PPP020202)()(1PPPPn=20)(231PPP0)(0230P

37、PP030302223)()(1PPPP第51頁/共72頁第五十二頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案53以此類推以此類推(y c li tu)，當(dāng)，當(dāng)n=n時，時，00)(PPPnnn(5)1(否則排隊無限遠，無法服務(wù)完否則排隊無限遠，無法服務(wù)完)10nnP以及概率性質(zhì)知：以及概率性質(zhì)知：111000PPnn(數(shù)列的極限為 )1110PnnP)1 (6)當(dāng)=1時，似乎好象來一個顧客服務(wù)一個顧客，但這是在均衡條件下和所有的顧客的服務(wù)時間都相等(xingdng)時，才會出現(xiàn)不存在排隊現(xiàn)象的這種理想的現(xiàn)象。在隨機的情況下，這是不可能的。第52頁/共72頁第五十三

38、頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案54 上式就是系統(tǒng)穩(wěn)態(tài)概率，以它為基礎(chǔ)可以上式就是系統(tǒng)穩(wěn)態(tài)概率，以它為基礎(chǔ)可以 算出系統(tǒng)的運行算出系統(tǒng)的運行(ynxng)指標。指標。 2. 系統(tǒng)的運行系統(tǒng)的運行(ynxng)指標計算指標計算 (1) 系統(tǒng)中的平均顧客數(shù)（隊長期望值系統(tǒng)中的平均顧客數(shù)（隊長期望值Ls）nnnnsnPnL001.)1(.)1 ( 3)1 ( 2)1 (32nn.3322143322nnnn1.32n(01)1第53頁/共72頁第五十四頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案55Ls即:(7)nnnnqnPn

39、L111) 1() 1(nnnnn111)1 (12sL(8) (3) 顧客在系統(tǒng)中的平均逗留時間顧客在系統(tǒng)中的平均逗留時間(shjin)Ws 顧客在系統(tǒng)中的逗留時間顧客在系統(tǒng)中的逗留時間(shjin)是隨機變量，可以證明，它服從參數(shù)為是隨機變量，可以證明，它服從參數(shù)為-的負指數(shù)分布，分布函數(shù)的負指數(shù)分布，分布函數(shù)(2) 隊列中等待的平均隊列中等待的平均(pngjn)顧客數(shù)顧客數(shù)Lq（隊列長期望值）（隊列長期望值）第54頁/共72頁第五十五頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案56和密度和密度(md)函數(shù)為：函數(shù)為：wewF)(1)(wewf)()()(

40、（w0） 1wEWs)(WsLs (4)顧客在隊列中的等待時間的期望值顧客在隊列中的等待時間的期望值Wq 顧客在隊列中的等待時間應(yīng)為顧客在隊列中的等待時間應(yīng)為Ws減去平均服務(wù)減去平均服務(wù)(fw)時間。時間。111WsWq)(WqLq第55頁/共72頁第五十六頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案57四個指標的關(guān)系四個指標的關(guān)系(gun x)為為(Little 公式公式)： 3. 系統(tǒng)(xtng)的忙期與閑期系統(tǒng)處于空閑狀態(tài)的概率：系統(tǒng)處于空閑狀態(tài)的概率：10P系統(tǒng)處于繁忙狀態(tài)的概率：系統(tǒng)處于繁忙狀態(tài)的概率：01) 0(PNPLsLq1swqwWsLsWqLq

41、1qswwqsLL下標s表示系統(tǒng)下標q表示隊列第56頁/共72頁第五十七頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案58排隊系統(tǒng) 服務(wù)臺顧客 N 4 3 2 1被拒絕第57頁/共72頁第五十八頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程(kchng)電子教案59)()()(100tPtPdttdP(2)對于對于(duy)(1)式，當(dāng)式，當(dāng)n=1,2,N-1時，也仍能成立。時，也仍能成立。)()()()()(1tPtPtPdttdPnnnn(1)(n=1,2,N-1)但當(dāng)?shù)?dāng)n=N時，有下面兩種情況：時，有下面兩種情況：第58頁/共72頁第五十九頁，共72頁

42、。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案60情 況時 刻t的 顧 客區(qū) 間 t, t+ t時 刻t+ t的 顧 客 數(shù)概 率AN無 離 去 （ 肯 定 不 到 達 ）NPN(t) (1- t)BN-1一 人 到 達 （ 無 離 去 ）NPN-1(t) tttPttPttPNNN)()1 ()()(1)()()(1tPtPdttdPNNN(8)其狀態(tài)其狀態(tài)(zhungti)轉(zhuǎn)移圖為轉(zhuǎn)移圖為:012n-1nn+1. .狀態(tài)轉(zhuǎn)換圖. .N-1N第59頁/共72頁第六十頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案61在穩(wěn)態(tài)情況在穩(wěn)態(tài)情況(qngk

43、ung)下有：下有：010PP0)(11nnnPPP01NNPP(9)解（解（9）式得：）式得：01PP022PP0PPNNNnnNnnNnnPPP000001 而等比數(shù)列而等比數(shù)列(dn b sh li)10111NnNn第60頁/共72頁第六十一頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)(jinsh)課程電子教案621011NPnNnP111(1,nN)(10) 注：當(dāng)注：當(dāng)=1時，試討論其概率時，試討論其概率Pn下面下面(xi mian)計算其運行指標：計算其運行指標：(1) 平均平均(pngjn)隊長隊長Ls：nPnLnNnNNnns01011nNnNn0111111) 1(1N

44、NN(1)試證=1時,Ls=N/2第61頁/共72頁第六十二頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案63（2）隊列）隊列(duli)長（期望值）長（期望值）NnsnqPLPnL10)1 () 1( 有效到達率有效到達率e的引入：的引入： Little公式可應(yīng)用的條件是：其平均到達率公式可應(yīng)用的條件是：其平均到達率是在系統(tǒng)是在系統(tǒng)有空時有空時的平均到達率。當(dāng)系統(tǒng)滿員時，就不能再應(yīng)用了。要用就應(yīng)該應(yīng)用有效到達率。的平均到達率。當(dāng)系統(tǒng)滿員時，就不能再應(yīng)用了。要用就應(yīng)該應(yīng)用有效到達率。 因為系統(tǒng)容量有限，當(dāng)滿員時，顧客將被拒絕，因此實際的顧客到達率為因為系統(tǒng)容量有限，當(dāng)

45、滿員時，顧客將被拒絕，因此實際的顧客到達率為0，與，與不一樣，為了求其他指標，需要求得有效到達率為不一樣，為了求其他指標，需要求得有效到達率為e：)1 (NeP)1 (0Pe可以驗證：可以驗證：第62頁/共72頁第六十三頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案64esesqLLLesSLWeqqLW此種情況此種情況(qngkung)的公式與的公式與前類似，前類似，只有只有Ls不不同，同，e與與 不同。求不同。求e必須先求必須先求得得P0或或Pn才行。才行。1)1 ()1 (0NqssPLPLw（3）顧客逗留）顧客逗留(duli)時間（期望值）時間（期望值）（4）

46、顧客等待時間（期望值）顧客等待時間（期望值）1sqwwLittle公式第63頁/共72頁第六十四頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(dinz)教案65例例2某單人理發(fā)館共有某單人理發(fā)館共有(n yu)六把椅子接待顧客排隊，六把椅子接待顧客排隊，無座時將離去，顧客平均到達率為無座時將離去，顧客平均到達率為3人人/h，理發(fā)時間平均為，理發(fā)時間平均為15分鐘，求：分鐘，求：(1) 求某一顧客到達就能理發(fā)的概率求某一顧客到達就能理發(fā)的概率;(2) 求需要等待的顧客數(shù)的期望值求需要等待的顧客數(shù)的期望值;(3) 求有效到達率求有效到達率;(4) 求一顧客在系統(tǒng)中的逗留時間和排隊時間平

47、均值求一顧客在系統(tǒng)中的逗留時間和排隊時間平均值;(5) 在可能到來的顧客中，有百分之幾不等待就離開？在可能到來的顧客中，有百分之幾不等待就離開？解：解：N=6+1=7，=3，=42778. 075. 0175. 0111810NP(1)11. 275. 0175. 0825. 075. 01) 1(18811NNsNL39. 1)2778. 01 (11. 2)1 (0PLLsq(2)第64頁/共72頁第六十五頁，共72頁。2022-7-6運籌學(xué)校級重點(zhngdin)建設(shè)課程電子教案66(3)89. 2)2778. 01 (4)1 (0Pemin8 .4373. 089. 211. 2hLWessmin86.2848. 089. 239. 1hLWeqq(4)(5)%71. 375. 075. 0175. 01117817NNPP0=0.27780P1=0.20836P2=0.15627P3=0.11720 = 0.9629=96.29%P4=0.08790 故拒絕的概率為3.71%P5=0.06593P6=0.04944第65頁/共72頁第六十六頁，共72頁。2022-7-6運籌學(xué)校級重點建設(shè)課程電子(di