運(yùn)籌(第十章排隊(duì)論)

1、2022-3-161運(yùn)籌學(xué)運(yùn)籌學(xué)OPERATIONS RESEARCH2022-3-1622022-3-1632022-3-1642022-3-1652022-3-1662022-3-1672022-3-1682022-3-1692022-3-16102022-3-16112022-3-16122022-3-16132022-3-16142022-3-16152022-3-16162022-3-16172022-3-16182022-3-16192022-3-16202022-3-16212022-3-1622f(t)=其中其中2022-3-1623f(t)=2022-3-16242022-3

2、-16252022-3-16262022-3-16272022-3-1628 2022-3-16292022-3-16302022-3-1631Little 公式公式ssWLqqWL/ssLW /qqLW 其中其中 是是單位時間內(nèi)到達(dá)的平均顧客數(shù)；單位時間內(nèi)到達(dá)的平均顧客數(shù)； 是是單位時間內(nèi)可以服務(wù)完的平均顧客數(shù)。單位時間內(nèi)可以服務(wù)完的平均顧客數(shù)。/1qsWW單位時間內(nèi)到達(dá)的平均顧客數(shù)單位時間內(nèi)到達(dá)的平均顧客數(shù)/qsLL0nnsnpL1)(snnqpsnL又又如果求得如果求得Pn ,則則 即可得到。即可得到。另外另外 1-P0 是系統(tǒng)的忙期概率。是系統(tǒng)的忙期概率。 qsqSWWLL,2022-

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

4、明：1、最簡單流的性質(zhì)可以簡化有關(guān)計(jì)算； 2、假設(shè)所研究的問題都是最簡單流，或近似最簡單流2022-3-1636二、最簡單流的有關(guān)計(jì)算二、最簡單流的有關(guān)計(jì)算1、單位時間內(nèi)到達(dá)的顧客數(shù)2、 內(nèi)沒有顧客到達(dá)的概率3、 恰有一個顧客到達(dá)的概率4、若顧客到達(dá)數(shù) poisson分布，則相繼到達(dá)間隔時 間 負(fù)指數(shù)分布 tt , t ,tttttotetvt1)(1)(0ttvtv)(1)(012022-3-1637三、服務(wù)時間三、服務(wù)時間設(shè)服務(wù)時間設(shè)服務(wù)時間 負(fù)指數(shù)分布負(fù)指數(shù)分布1、單位時間內(nèi)服務(wù)完畢，離去的顧客數(shù)2、 內(nèi)沒有顧客離去的概率3、 恰有一個顧客離去的概率4、若干負(fù)指數(shù)分布的最小值也是負(fù)指數(shù)分

5、說明： 服務(wù)機(jī)構(gòu)中有s個并聯(lián)服務(wù)臺，各臺 負(fù)指數(shù)分布，則整個服務(wù)時間 負(fù)指數(shù)分布。 ,ttt,tttst1t2022-3-1638第第38頁頁生滅過程2022-3-1639第第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)中有時刻

6、系統(tǒng)中有n n個顧客的個顧客的概率為概率為tt) t(ot) t (p1n1n4、t t時刻為時刻為n,n-1,n+1n,n-1,n+1個顧客之外的情況，個顧客之外的情況， 時刻時刻系統(tǒng)中有系統(tǒng)中有n n個顧客的概率為個顧客的概率為tt) t(o2022-3-1640第第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-3-164

7、1第第41頁頁移項(xiàng)求極限，得差分微分方程移項(xiàng)求極限，得差分微分方程)()()()()()()()(110001111tPtPtPtPtPtPtPnnnnnnnnt時時,平穩(wěn)狀態(tài)平穩(wěn)狀態(tài)nntPtP)(lim0n11n0n0.11P01n01nnp.P推導(dǎo)過程見書推導(dǎo)過程見書P2602022-3-1642排隊(duì)模型排隊(duì)模型一、一、M/M/1/ M/M/1/ 模型模型 ：顧客相繼到達(dá)時間服從參數(shù)為顧客相繼到達(dá)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為1 1； 系統(tǒng)的空間為無限，允許永遠(yuǎn)排隊(duì)。系統(tǒng)的空間為無限，

8、允許永遠(yuǎn)排隊(duì)。2022-3-16432022-3-16442022-3-16452022-3-16462022-3-16472022-3-1648/(/() )= =/() 2022-3-16492022-3-16502022-3-16512022-3-16522022-3-16532022-3-16542022-3-1655二、二、M/M/1/ NM/M/1/ N 模型模型 ：顧客相繼到達(dá)時間服從參數(shù)為顧客相繼到達(dá)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為1 1； 系統(tǒng)的空間為有限，最大容量系統(tǒng)的空間

9、為有限，最大容量N N。2022-3-16561 1、 穩(wěn)定狀態(tài)下，系統(tǒng)中有穩(wěn)定狀態(tài)下，系統(tǒng)中有n n個顧客的概率個顧客的概率nP012N-1N。1110111,)(NNnnnppNnppppp2022-3-1657由由 及上述差分方程可解得：及上述差分方程可解得： 10NnnP) 1(/,1111110nNnNPP單位時間內(nèi)的平均到達(dá)率單位時間內(nèi)的平均到達(dá)率 )1 (NeP單位時間內(nèi)的平均單位時間內(nèi)的平均有效到達(dá)率有效到達(dá)率 系統(tǒng)中有系統(tǒng)中有N N個顧客時，到達(dá)率為個顧客時，到達(dá)率為0 0，只有在少于，只有在少于N N個顧客時個顧客時到達(dá)率才有意義。到達(dá)率才有意義。 還可驗(yàn)證還可驗(yàn)證 )1

10、(0Pe2022-3-16582 2、系統(tǒng)運(yùn)行指標(biāo)系統(tǒng)運(yùn)行指標(biāo)1N1NN1nns1) 1N(1nPL)1 () 1(01PLPnLSNnnq)P1 (LLW0SeSs1WWsq2022-3-1659例、例、單人理發(fā)店有六張椅子接待客人排隊(duì)理發(fā)，當(dāng)單人理發(fā)店有六張椅子接待客人排隊(duì)理發(fā)，當(dāng)6 6張椅張椅子坐滿時，后來的顧客就不進(jìn)店，隨即離開，顧客平子坐滿時，后來的顧客就不進(jìn)店，隨即離開，顧客平均到達(dá)率均到達(dá)率3 3人人/ /小時，理發(fā)平均需時小時，理發(fā)平均需時1515分鐘，求：分鐘，求： 1 1、求顧客一到達(dá)就能理發(fā)的概率；、求顧客一到達(dá)就能理發(fā)的概率； 2 2、求需要等待的平均顧客數(shù)；、求需要等

11、待的平均顧客數(shù)； 3 3、求有效到達(dá)率；、求有效到達(dá)率； 4 4、每個顧客的平均逗留時間；、每個顧客的平均逗留時間； 5 5、在可能到來的顧客中有百分之幾不等待就離開？、在可能到來的顧客中有百分之幾不等待就離開？2022-3-1660解、解、該問題中該問題中 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-3-1661小時）人/(89. 2)2778. 01 (4)1 (0Pe3

12、 3、 4 4、5.5. 損失率損失率分鐘小時43.80.732.892.11eSsLW%3.73/43/414/317177）（）（P2022-3-1662三、三、M/M/s/ M/M/s/ 模型模型 ：顧客相繼到達(dá)時間服從參數(shù)為顧客相繼到達(dá)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為s s； 系統(tǒng)的空間為無限系統(tǒng)的空間為無限2022-3-16631 1、 穩(wěn)定狀態(tài)下，系統(tǒng)中有穩(wěn)定狀態(tài)下，系統(tǒng)中有n n個顧客的概率個顧客的概率nP012nn+1n) 1( n。n-12nn+1ssn-1sn sn 202

13、2-3-1664snpnppnsnpsppsppnnnnnn1,)() 1(,)(111101由由 及上述差分方程可解得：及上述差分方程可解得： 10nnPsnPsssnPnPskPnsnnnsksk,!1) 1(/,!111!1!10011002022-3-16652 2、系統(tǒng)運(yùn)行指標(biāo)系統(tǒng)運(yùn)行指標(biāo)/qsLL021)1 ( !)()(PssPsnLssnnqSsLW qqLW 2022-3-1666例、例、某售票點(diǎn)有三個窗口，顧客的到達(dá)服從某售票點(diǎn)有三個窗口，顧客的到達(dá)服從poisson poisson 過過程，平均到達(dá)率程，平均到達(dá)率 ，服務(wù)時間服從負(fù)，服務(wù)時間服從負(fù)指數(shù)分布，平均服務(wù)率指數(shù)

14、分布，平均服務(wù)率 。 現(xiàn)在假設(shè)顧客到達(dá)后排成一隊(duì)，一次到空閑的窗口買現(xiàn)在假設(shè)顧客到達(dá)后排成一隊(duì)，一次到空閑的窗口買票。分析下列各問題：票。分析下列各問題： 1 1、整個售票點(diǎn)空閑的概率；、整個售票點(diǎn)空閑的概率； 2 2、平均排隊(duì)長；、平均排隊(duì)長； 3 3、平均排隊(duì)時間；、平均排隊(duì)時間； 4 4、顧客到達(dá)后必須等待的概率。、顧客到達(dá)后必須等待的概率。分鐘人/9 . 0分鐘人/4 . 02022-3-1667解、解、該問題中該問題中 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-3-1668四、四、M/M/s/ NM/M/s/ N 模型模型 ：顧客相繼到達(dá)時間服從參數(shù)為顧客相繼到達(dá)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)時間服從參數(shù)為服務(wù)時間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)臺數(shù)為服務(wù)臺數(shù)為s s； 系統(tǒng)的空間為有限，最多為系統(tǒng)的空間為有限，最多為N