運(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 其中其中 是是單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)；單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)； 是是單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)。單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)。/1qsWW單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)/qsLL0nnsnpL1)(snnqpsnL又又如果求得如果求得Pn ,則則 即可得到。即可得到。另外另外 1-P0 是系統(tǒng)的忙期概率。是系統(tǒng)的忙期概率。 qsqSWWLL,2022-

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

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

5、說(shuō)明： 服務(wù)機(jī)構(gòu)中有s個(gè)并聯(lián)服務(wù)臺(tái)，各臺(tái) 負(fù)指數(shù)分布，則整個(gè)服務(wù)時(shí)間 負(fù)指數(shù)分布。 ,ttt,tttst1t2022-3-1638第第38頁(yè)頁(yè)生滅過(guò)程2022-3-1639第第39頁(yè)頁(yè)2、t t時(shí)刻有時(shí)刻有n-1n-1個(gè)顧客，個(gè)顧客， 時(shí)刻系統(tǒng)中有時(shí)刻系統(tǒng)中有n n個(gè)顧客的個(gè)顧客的概率為概率為1、t t時(shí)刻有時(shí)刻有n n個(gè)顧客，個(gè)顧客， 時(shí)刻系統(tǒng)中仍有時(shí)刻系統(tǒng)中仍有n n個(gè)顧客的個(gè)顧客的概率為概率為 時(shí)刻系統(tǒng)中有時(shí)刻系統(tǒng)中有n個(gè)顧客的概率個(gè)顧客的概率tttt) t(o tt1)t (pnnntt) t(ot) t (p1n1n3、t t時(shí)刻有時(shí)刻有n+1n+1個(gè)顧客，個(gè)顧客， 時(shí)刻系統(tǒng)中有時(shí)刻

6、系統(tǒng)中有n n個(gè)顧客的個(gè)顧客的概率為概率為tt) t(ot) t (p1n1n4、t t時(shí)刻為時(shí)刻為n,n-1,n+1n,n-1,n+1個(gè)顧客之外的情況，個(gè)顧客之外的情況， 時(shí)刻時(shí)刻系統(tǒng)中有系統(tǒng)中有n n個(gè)顧客的概率為個(gè)顧客的概率為tt) t(o2022-3-1640第第40頁(yè)頁(yè)于是于是) 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時(shí)時(shí)) t(ot) t (p t1)t (p) tt (p110002022-3-164

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

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í)間服從參數(shù)為顧客相繼到達(dá)時(shí)間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)時(shí)間服從參數(shù)為服務(wù)時(shí)間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)臺(tái)數(shù)為服務(wù)臺(tái)數(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個(gè)顧客的概率個(gè)顧客的概率nP012N-1N。1110111,)(NNnnnppNnppppp2022-3-1657由由 及上述差分方程可解得：及上述差分方程可解得： 10NnnP) 1(/,1111110nNnNPP單位時(shí)間內(nèi)的平均到達(dá)率單位時(shí)間內(nèi)的平均到達(dá)率 )1 (NeP單位時(shí)間內(nèi)的平均單位時(shí)間內(nèi)的平均有效到達(dá)率有效到達(dá)率 系統(tǒng)中有系統(tǒng)中有N N個(gè)顧客時(shí)，到達(dá)率為個(gè)顧客時(shí)，到達(dá)率為0 0，只有在少于，只有在少于N N個(gè)顧客時(shí)個(gè)顧客時(shí)到達(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張椅張椅子坐滿時(shí)，后來(lái)的顧客就不進(jìn)店，隨即離開(kāi)，顧客平子坐滿時(shí)，后來(lái)的顧客就不進(jìn)店，隨即離開(kāi)，顧客平均到達(dá)率均到達(dá)率3 3人人/ /小時(shí)，理發(fā)平均需時(shí)小時(shí)，理發(fā)平均需時(shí)1515分鐘，求：分鐘，求： 1 1、求顧客一到達(dá)就能理發(fā)的概率；、求顧客一到達(dá)就能理發(fā)的概率； 2 2、求需要等待的平均顧客數(shù)；、求需要等

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

12、 3、 4 4、5.5. 損失率損失率分鐘小時(shí)43.80.732.892.11eSsLW%3.73/43/414/317177）（）（P2022-3-1662三、三、M/M/s/ M/M/s/ 模型模型 ：顧客相繼到達(dá)時(shí)間服從參數(shù)為顧客相繼到達(dá)時(shí)間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)時(shí)間服從參數(shù)為服務(wù)時(shí)間服從參數(shù)為 的負(fù)指數(shù)分布；的負(fù)指數(shù)分布； 服務(wù)臺(tái)數(shù)為服務(wù)臺(tái)數(shù)為s s； 系統(tǒng)的空間為無(wú)限系統(tǒng)的空間為無(wú)限2022-3-16631 1、 穩(wěn)定狀態(tài)下，系統(tǒng)中有穩(wěn)定狀態(tài)下，系統(tǒng)中有n n個(gè)顧客的概率個(gè)顧客的概率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)有三個(gè)窗口，顧客的到達(dá)服從某售票點(diǎn)有三個(gè)窗口，顧客的到達(dá)服從poisson poisson 過(guò)過(guò)程，平均到達(dá)率程，平均到達(dá)率 ，服務(wù)時(shí)間服從負(fù)，服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率指數(shù)

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