1、2022-6-51運籌學(xué)運籌學(xué)OPERATIONS RESEARCH2022-6-522022-6-532022-6-542022-6-552022-6-562022-6-572022-6-582022-6-592022-6-5102022-6-5112022-6-5122022-6-5132022-6-5142022-6-5152022-6-5162022-6-5172022-6-5182022-6-5192022-6-5202022-6-5212022-6-522f(t)=其中其中2022-6-523f(t)=2022-6-5242022-6-5252022-6-5262022-6-527

2、2022-6-528 2022-6-5292022-6-5302022-6-531Little 公式公式ssWLqqWL/ssLW /qqLW 其中其中 是是單位時間內(nèi)到達的平均顧客數(shù)；單位時間內(nèi)到達的平均顧客數(shù)； 是是單位時間內(nèi)可以服務(wù)完的平均顧客數(shù)。單位時間內(nèi)可以服務(wù)完的平均顧客數(shù)。/1qsWW單位時間內(nèi)到達的平均顧客數(shù)單位時間內(nèi)到達的平均顧客數(shù)/qsLL0nnsnpL1)(snnqpsnL又又如果求得如果求得Pn ,則則 即可得到。即可得到。另外另外 1-P0 是系統(tǒng)的忙期概率。是系統(tǒng)的忙期概率。 qsqSWWLL,2022-6-5322022-6-5332022-6-534一、最簡單流

3、一、最簡單流1、定義、定義;在時長為 t 的時間段內(nèi)，有k個顧客到達的概率 服從poisson分布： t時段內(nèi)平均到達顧客數(shù)； ,.2 , 1 , 0,!)()(kekttvtkk) (tvk, tE,tE單位時段內(nèi)平均到達顧客數(shù)2022-6-5352、最簡單流的性質(zhì)、最簡單流的性質(zhì)（1）平穩(wěn)性平穩(wěn)性：在一定時間間隔內(nèi)，有k個顧客到達的概率只與時長有關(guān)，與起始時刻無關(guān)；（2）無后效性無后效性：a,a+t時段內(nèi)有k個顧客到達的概率與a時刻之前的客流無關(guān)；（3）普通性：普通性：在足夠小的時段內(nèi)有2個或個以上顧客到來的概率為零。說明：1、最簡單流的性質(zhì)可以簡化有關(guān)計算； 2、假設(shè)所研究的問題都是最簡

4、單流，或近似最簡單流2022-6-536二、最簡單流的有關(guān)計算二、最簡單流的有關(guān)計算1、單位時間內(nèi)到達的顧客數(shù)2、 內(nèi)沒有顧客到達的概率3、 恰有一個顧客到達的概率4、若顧客到達數(shù) poisson分布，則相繼到達間隔時 間 負指數(shù)分布 tt , t ,tttttotetvt1)(1)(0ttvtv)(1)(012022-6-537三、服務(wù)時間三、服務(wù)時間設(shè)服務(wù)時間設(shè)服務(wù)時間 負指數(shù)分布負指數(shù)分布1、單位時間內(nèi)服務(wù)完畢，離去的顧客數(shù)2、 內(nèi)沒有顧客離去的概率3、 恰有一個顧客離去的概率4、若干負指數(shù)分布的最小值也是負指數(shù)分說明： 服務(wù)機構(gòu)中有s個并聯(lián)服務(wù)臺，各臺 負指數(shù)分布，則整個服務(wù)時間 負指

5、數(shù)分布。 ,ttt,tttst1t2022-6-538第第38頁頁生滅過程2022-6-539第第39頁頁2、t t時刻有時刻有n-1n-1個顧客，個顧客， 時刻系統(tǒng)中有時刻系統(tǒng)中有n n個顧客的個顧客的概率為概率為1、t t時刻有時刻有n n個顧客，個顧客， 時刻系統(tǒng)中仍有時刻系統(tǒng)中仍有n n個顧客的個顧客的概率為概率為 時刻系統(tǒng)中有時刻系統(tǒng)中有n個顧客的概率個顧客的概率tttt) t(o tt1)t (pnnntt) t(ot) t (p1n1n3、t t時刻有時刻有n+1n+1個顧客，個顧客， 時刻系統(tǒng)中有時刻系統(tǒng)中有n n個顧客的個顧客的概率為概率為tt) t(ot) t (p1n1n

6、4、t t時刻為時刻為n,n-1,n+1n,n-1,n+1個顧客之外的情況，個顧客之外的情況， 時刻時刻系統(tǒng)中有系統(tǒng)中有n n個顧客的概率為個顧客的概率為tt) t(o2022-6-540第第40頁頁于是于是) t(ot) t (pt) t (p tt1)t (p) t(o) t(ot) t (p) t(ot) t (p) t(o tt1)t (p) tt (p1n1n1n1nnnn1n1n1n1nnnnn特別的，特別的，n=0時時) t(ot) t (p t1)t (p) tt (p110002022-6-541第第41頁頁移項求極限，得差分微分方程移項求極限，得差分微分方程)()()()(

7、)()()()(110001111tPtPtPtPtPtPtPnnnnnnnnt時時,平穩(wěn)狀態(tài)平穩(wěn)狀態(tài)nntPtP)(lim0n11n0n0.11P01n01nnp.P推導(dǎo)過程見書推導(dǎo)過程見書P2602022-6-542排隊模型排隊模型一、一、M/M/1/ M/M/1/ 模型模型 ：顧客相繼到達時間服從參數(shù)為顧客相繼到達時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為1 1； 系統(tǒng)的空間為無限，允許永遠排隊。系統(tǒng)的空間為無限，允許永遠排隊。2022-6-5432022-6-5442022-6-5452022-

8、6-5462022-6-5472022-6-548/(/() )= =/() 2022-6-5492022-6-5502022-6-5512022-6-5522022-6-5532022-6-5542022-6-555二、二、M/M/1/ NM/M/1/ N 模型模型 ：顧客相繼到達時間服從參數(shù)為顧客相繼到達時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為1 1； 系統(tǒng)的空間為有限，最大容量系統(tǒng)的空間為有限，最大容量N N。2022-6-5561 1、 穩(wěn)定狀態(tài)下，系統(tǒng)中有穩(wěn)定狀態(tài)下，系統(tǒng)中有n n個顧客的概

9、率個顧客的概率nP012N-1N。1110111,)(NNnnnppNnppppp2022-6-557由由 及上述差分方程可解得：及上述差分方程可解得： 10NnnP) 1(/,1111110nNnNPP單位時間內(nèi)的平均到達率單位時間內(nèi)的平均到達率 )1 (NeP單位時間內(nèi)的平均單位時間內(nèi)的平均有效到達率有效到達率 系統(tǒng)中有系統(tǒng)中有N N個顧客時，到達率為個顧客時，到達率為0 0，只有在少于，只有在少于N N個顧客時個顧客時到達率才有意義。到達率才有意義。 還可驗證還可驗證 )1 (0Pe2022-6-5582 2、系統(tǒng)運行指標系統(tǒng)運行指標1N1NN1nns1) 1N(1nPL)1 () 1(

10、01PLPnLSNnnq)P1 (LLW0SeSs1WWsq2022-6-559例、例、單人理發(fā)店有六張椅子接待客人排隊理發(fā)，當單人理發(fā)店有六張椅子接待客人排隊理發(fā)，當6 6張椅張椅子坐滿時，后來的顧客就不進店，隨即離開，顧客平子坐滿時，后來的顧客就不進店，隨即離開，顧客平均到達率均到達率3 3人人/ /小時，理發(fā)平均需時小時，理發(fā)平均需時1515分鐘，求：分鐘，求： 1 1、求顧客一到達就能理發(fā)的概率；、求顧客一到達就能理發(fā)的概率； 2 2、求需要等待的平均顧客數(shù)；、求需要等待的平均顧客數(shù)； 3 3、求有效到達率；、求有效到達率； 4 4、每個顧客的平均逗留時間；、每個顧客的平均逗留時間；

11、5 5、在可能到來的顧客中有百分之幾不等待就離開？、在可能到來的顧客中有百分之幾不等待就離開？2022-6-560解、解、該問題中該問題中 N=7 N=7，1 1、 2 2、4/3/, 4, 32778. 0)4/3(14/31111710NP11. 2)4/3(1) 17(4/314/3171771nnsnPL39. 1)2778. 01 (11. 2)1 () 1(071PLPnLSnnq2022-6-561小時）人/(89. 2)2778. 01 (4)1 (0Pe3 3、 4 4、5.5. 損失率損失率分鐘小時43.80.732.892.11eSsLW%3.73/43/414/3171

12、77）（）（P2022-6-562三、三、M/M/s/ M/M/s/ 模型模型 ：顧客相繼到達時間服從參數(shù)為顧客相繼到達時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為s s； 系統(tǒng)的空間為無限系統(tǒng)的空間為無限2022-6-5631 1、 穩(wěn)定狀態(tài)下，系統(tǒng)中有穩(wěn)定狀態(tài)下，系統(tǒng)中有n n個顧客的概率個顧客的概率nP012nn+1n) 1( n。n-12nn+1ssn-1sn sn 2022-6-564snpnppnsnpsppsppnnnnnn1,)() 1(,)(111101由由 及上述差分方程可解得：及上述

13、差分方程可解得： 10nnPsnPsssnPnPskPnsnnnsksk,!1) 1(/,!111!1!10011002022-6-5652 2、系統(tǒng)運行指標系統(tǒng)運行指標/qsLL021)1 ( !)()(PssPsnLssnnqSsLW qqLW 2022-6-566例、例、某售票點有三個窗口，顧客的到達服從某售票點有三個窗口，顧客的到達服從poisson poisson 過過程，平均到達率程，平均到達率 ，服務(wù)時間服從負，服務(wù)時間服從負指數(shù)分布，平均服務(wù)率指數(shù)分布，平均服務(wù)率 。 現(xiàn)在假設(shè)顧客到達后排成一隊，一次到空閑的窗口買現(xiàn)在假設(shè)顧客到達后排成一隊，一次到空閑的窗口買票。分析下列各問題

14、：票。分析下列各問題： 1 1、整個售票點空閑的概率；、整個售票點空閑的概率； 2 2、平均排隊長；、平均排隊長； 3 3、平均排隊時間；、平均排隊時間； 4 4、顧客到達后必須等待的概率。、顧客到達后必須等待的概率。分鐘人/9 . 0分鐘人/4 . 02022-6-567解、解、該問題中該問題中 s=3 s=3，1 1、 2 2、3 3、4 4、 75. 0/, 4 . 0, 9 . 0s0748. 011!1!11100skskskP)(70. 1)1 ( !)()(021人PssPsnLssnnq)(89. 19 . 070. 1分鐘qqLW57. 01)3(210PPPnP2022-6-568四、四、M/M/s/ NM/M/s/ N 模型模型 ：顧客相繼到達時間服從參數(shù)為顧客相繼到達時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負指數(shù)分布；的負指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為s s； 系統(tǒng)的空間為有限，最多為系統(tǒng)的空間為有限，