隨機過程與排隊論12

1、隨機過程與排隊論隨機過程與排隊論計算機科學(xué)與工程學(xué)院計算機科學(xué)與工程學(xué)院顧小豐顧小豐Email：2022年年6月月29日星期三日星期三2022-6-292022-6-29計算機科學(xué)與工程學(xué)院計算機科學(xué)與工程學(xué)院顧小豐顧小豐上一講內(nèi)容回顧上一講內(nèi)容回顧 生滅過程生滅過程 排隊論簡介排隊論簡介排隊的概念排隊的概念基本的排隊系統(tǒng)基本的排隊系統(tǒng)排隊系統(tǒng)的基本組成排隊系統(tǒng)的基本組成經(jīng)典排隊系統(tǒng)的符號表示方法經(jīng)典排隊系統(tǒng)的符號表示方法40402 22022-6-292022-6-29計算機科學(xué)與工程學(xué)院計算機科學(xué)與工程學(xué)院顧小豐顧小豐本講主要內(nèi)容本講主要內(nèi)容 無限源的簡單排隊系統(tǒng)無限源的簡單排隊系統(tǒng)M/M

2、/1/ 問題的引入問題的引入隊長隊長等待時間與逗留時間等待時間與逗留時間Little公式公式忙期忙期輸出過程輸出過程40403 32022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐5.1 M/M/1/ 1. 問題的敘述問題的敘述v 顧客到達為參數(shù)顧客到達為參數(shù) ( 0)的泊松過程，即相繼到的泊松過程，即相繼到達的間隔時間序列達的間隔時間序列 n，n 1獨立、服從參數(shù)為獨立、服從參數(shù)為 ( 0)的負指數(shù)分布的負指數(shù)分布F(t)1-e- t，t 0；v 顧客所需的服務(wù)時間序列顧客所需的服務(wù)時間序列 n,n 1獨立、服從參獨立、服從參數(shù)為數(shù)為 ( 0)的負指數(shù)分

3、布的負指數(shù)分布G(t)1-e- t，t 0；v 系統(tǒng)中只有一個服務(wù)臺；系統(tǒng)中只有一個服務(wù)臺；v 容量為無窮大，而且到達過程與服務(wù)過程彼此容量為無窮大，而且到達過程與服務(wù)過程彼此獨立。獨立。40404 42022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐2.隊長隊長 假定假定N(t)表示在時刻表示在時刻t系統(tǒng)中的顧客數(shù)，包括正在被服系統(tǒng)中的顧客數(shù)，包括正在被服務(wù)的顧客數(shù)，即務(wù)的顧客數(shù)，即N(t)表示時刻表示時刻t系統(tǒng)的隊長，系統(tǒng)的隊長，t 0，且令，且令pij( t)PN(t+ t)j|N(t)i，i,j0,1,2,則則1)pi,i+1( t)P在在 t內(nèi)到

4、達一個而服務(wù)未完成內(nèi)到達一個而服務(wù)未完成 在在 t內(nèi)到達內(nèi)到達j個而服務(wù)完個而服務(wù)完j-1個個 P 1t， 1 t 1+ jt 1+ j+1， 1+ j-1t t， 1t 1+ jt 1+ j+1， 1+ j+1t 1+ j+2(1-e-t)e-to( t)to( t)i1,2,3, 1jP 1jP3) 類似分析可得類似分析可得pij( t)o( t)，|i-j| 240406 62022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐隊長隊長(續(xù)續(xù)2)綜合上述綜合上述1)2)3)得得 2| ji |) t(o1i , 1ij) t(ot0i , 1ij) t(

5、ot) t(pijN(t)，t 0是可列無限狀態(tài)是可列無限狀態(tài)E0,1,2,上的上的生滅過程生滅過程，其參數(shù)為其參數(shù)為 1i,0i,ii此生滅過程的絕對分布此生滅過程的絕對分布pj(t)PN(t)=j，j=0,1,2,的?？说母？似绽士朔匠探M為普朗克方程組為 1j),t (p) t (p) t (p)() t (p) t (p) t (p) t (p1j1j1j1jjjjj1100040407 72022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐隊長隊長(續(xù)續(xù)3)令令 ，則稱，則稱 為系統(tǒng)的為系統(tǒng)的交通強度交通強度(Trafficindensity)。有如

6、下結(jié)論：有如下結(jié)論： 令令pj ，j=0,1,2,，則，則1)當(dāng)當(dāng)1時，時，pj0，j=0,1,2,不構(gòu)成概率分布；不構(gòu)成概率分布；2)當(dāng)當(dāng) 1時，時，pj，j=0,1,2,存在，與初始條件無存在，與初始條件無關(guān)，且關(guān)，且pj(1- ) j，j=0,1,2,構(gòu)成一個幾何概率分布。構(gòu)成一個幾何概率分布。 ) t (plimjt ,2,1 ,0k,1,3,2,1k,1111kk2102101kk1k0k211k10k11jj211j100j11jj211j1001jj211j10 時時當(dāng)當(dāng)40408 82022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐結(jié)論結(jié)論

7、在統(tǒng)計平衡的條件下在統(tǒng)計平衡的條件下( 1)：jjj 0j 0NE(N)jpj(1) 平均隊長平均隊長j 1jj 0j 0(1)j(1) 1(1)11 40409 92022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐結(jié)論結(jié)論(續(xù)續(xù)1)等待隊長的分布等待隊長的分布201qj 1j 1pp1,j0PNjp(1),j1 j 1qj 1j 0j 0Njpj(1) 平均等待隊長平均等待隊長 j 1j22j 0j 0(1)j(1) j222j 01(1)(1)11 404010102022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐

8、結(jié)論結(jié)論(續(xù)續(xù)2)隊長的方差隊長的方差2222jj 0D(N)E(N )E (N)j pN 22jj 0j (1)1 2j 1 j j 0(1)()() )1 2j 1 j j 0j 0(1)()() )1 221(1)()() )1111 404011112022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐結(jié)論結(jié)論(續(xù)續(xù)3)等待隊長的方差等待隊長的方差2222qqqqj 1j 1D(N )E(N)E (N )j pN 222j 1j 1j (1)1 242(1)1 404012121-PNq=0=1-(1- 2)= 22022-6-292022-6-29計

9、算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐結(jié)論結(jié)論(續(xù)續(xù)4)1NP jNP1NP1N, jNP1N| jNPqqqqqqq 在等待條件下的等待隊長分布在等待條件下的等待隊長分布j 1qqj 11E(N |N1)j(1),11 在等待條件下的平均等待隊長在等待條件下的平均等待隊長根據(jù)隊長分布意知：根據(jù)隊長分布意知： p0=1 也是也是系統(tǒng)空閑的概率系統(tǒng)空閑的概率，而，而 正是正是系系統(tǒng)繁忙的概率統(tǒng)繁忙的概率。顯然，。顯然， 越大，系統(tǒng)就越繁忙越大，系統(tǒng)就越繁忙。1j , 1,)1()1(1j21j =pj-1404013132022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計

10、算機科學(xué)與工程學(xué)院顧小豐3.等待時間與逗留時間等待時間與逗留時間1. 假定顧客是先到先服務(wù)。假定顧客是先到先服務(wù)。 定理定理 在統(tǒng)計平衡在統(tǒng)計平衡( 0時，有時，有Wq(t)PWq=0P0Wq tp0- 00)的隨機變量，即參數(shù)為的隨機變量，即參數(shù)為 的泊松流。的泊松流。2.當(dāng)系統(tǒng)空閑后，從開始空閑時刻起，到下一個顧客服當(dāng)系統(tǒng)空閑后，從開始空閑時刻起，到下一個顧客服務(wù)完畢離去時之間的間隔時間不與服務(wù)時間同分布。務(wù)完畢離去時之間的間隔時間不與服務(wù)時間同分布。 令令Tn+表示第表示第n個顧客服務(wù)完畢的離去時刻，則個顧客服務(wù)完畢的離去時刻，則Tn+1+-Tn+表示離去的時間間隔，表示離去的時間間隔，

11、n 1，于是，對，于是，對t 0有有 PTn+1+Tn+tPNn+=0PTn+1+Tn+t|Nn+=0 PNn+ 1PTn+1+Tn+t|Nn+ 1PNn+=0P n+1 n+1t PNn+ 1P n+1t其中其中 n+1表示剩余到達間隔時間，與表示剩余到達間隔時間，與 n+1獨立，而獨立，而Nn+表示表示第第n個離去顧客服務(wù)完畢離開系統(tǒng)時的隊長。個離去顧客服務(wù)完畢離開系統(tǒng)時的隊長。 404023232022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐輸出過程輸出過程( (續(xù)續(xù)) ) 1, 01,10NPlimnn因此因此 tTTPlimn1nn 由于由于此

12、式表示在統(tǒng)計平衡下，相繼輸出的間隔時間服從參數(shù)為此式表示在統(tǒng)計平衡下，相繼輸出的間隔時間服從參數(shù)為 （ 00）的負指數(shù)分布。）的負指數(shù)分布。 另外，在統(tǒng)計平衡下，輸出的間隔時間相互獨立，因另外，在統(tǒng)計平衡下，輸出的間隔時間相互獨立，因此對此對M/M/1/M/M/1/ 系統(tǒng)，其統(tǒng)計平衡下的輸出過程與到達過程系統(tǒng)，其統(tǒng)計平衡下的輸出過程與到達過程相同。相同。0t,eeee)1(tttt 404024242022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例1 某火車站一個售票窗口，若到達該窗口購票的某火車站一個售票窗口，若到達該窗口購票的顧客按泊松流到達，平均

13、每分鐘到達顧客按泊松流到達，平均每分鐘到達1人，假定售人，假定售票時間服從負指數(shù)分布，平均每分鐘可售票時間服從負指數(shù)分布，平均每分鐘可售2人，試人，試研究該售票窗口前的排隊情況。研究該售票窗口前的排隊情況。解解 由題設(shè)知，由題設(shè)知， 1(人人/分分)， 2(人人/分分)， ，該系統(tǒng)按該系統(tǒng)按M/M/1/ 型處理，于是在統(tǒng)計平衡下，型處理，于是在統(tǒng)計平衡下，有有21, 2 , 1 , 0j,)21()1(p1jjj 平均隊長為平均隊長為11N (人人)平均等待隊長為平均等待隊長為211N2q (人人)404025252022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)

14、院顧小豐例例1(1(續(xù)續(xù)) )平均等待時間為平均等待時間為21)1(Wq (分鐘分鐘)平均逗留時間為平均逗留時間為11W (分鐘分鐘)顧客到達不需要等待的概率為顧客到達不需要等待的概率為21p0 等待隊長超過等待隊長超過5人的概率為人的概率為66k1kq)21()21(6NP5NP 404026262022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例2 考慮某種產(chǎn)品的庫存問題。如果進貨過多，則會帶考慮某種產(chǎn)品的庫存問題。如果進貨過多，則會帶來過多的保管費，如果存貨不足，則缺貨時影響生產(chǎn)，來過多的保管費，如果存貨不足，則缺貨時影響生產(chǎn)，造成經(jīng)濟損失。最好的

15、辦法是能及時供應(yīng)，但由于生產(chǎn)造成經(jīng)濟損失。最好的辦法是能及時供應(yīng)，但由于生產(chǎn)和運輸?shù)确矫娴囊蛩?，一般講這是難以滿足的，因此希和運輸?shù)确矫娴囊蛩兀话阒v這是難以滿足的，因此希望找到一種合理的庫存望找到一種合理的庫存s s，使得庫存費與缺貨損失費的總，使得庫存費與缺貨損失費的總和達到最小。假定需求是參數(shù)和達到最小。假定需求是參數(shù) 的泊松流，生產(chǎn)是一個一的泊松流，生產(chǎn)是一個一個產(chǎn)品生產(chǎn)的，每生產(chǎn)一個產(chǎn)品所需時間為參數(shù)個產(chǎn)品生產(chǎn)的，每生產(chǎn)一個產(chǎn)品所需時間為參數(shù) 的負指的負指數(shù)分布。庫存一個產(chǎn)品的單位時間費用為數(shù)分布。庫存一個產(chǎn)品的單位時間費用為c c元，缺一個產(chǎn)元，缺一個產(chǎn)品造成的損失費為品造成的損失

16、費為h h元，尋找一個最優(yōu)庫存量元，尋找一個最優(yōu)庫存量s s，使得庫，使得庫存費與損失費之和達到最?。ú豢紤]產(chǎn)品的運輸時間）。存費與損失費之和達到最?。ú豢紤]產(chǎn)品的運輸時間）。404027272022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例2(續(xù)續(xù)1)解解 把生產(chǎn)產(chǎn)品的工廠看成是服務(wù)機構(gòu)，需求看作是輸入把生產(chǎn)產(chǎn)品的工廠看成是服務(wù)機構(gòu)，需求看作是輸入流，于是把問題化成流，于是把問題化成M/M/1/ 系統(tǒng)，需求量表示隊長，系統(tǒng)，需求量表示隊長，pk表示生產(chǎn)廠有表示生產(chǎn)廠有k個訂貨未交的概率。設(shè)庫存量為個訂貨未交的概率。設(shè)庫存量為s，則缺貨，則缺貨時的平均

17、缺貨數(shù)為時的平均缺貨數(shù)為 snnsnnsnn)1(s)1(np) sn(E缺缺ssnns)1(n 平均庫存數(shù)為平均庫存數(shù)為 1s0nn1s0nn1s0nn)1(n)1(sp)ns (E存存 snns)1(n1)1( s404028282022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例2(續(xù)續(xù)2)單位時間的期望總費用為單位時間的期望總費用為s)1(nh)1(n1)1( s c) s ( fssnnsnns 1h1)1(ccs1ss用邊際分析法解上式，使上式最小的用邊際分析法解上式，使上式最小的s應(yīng)滿足應(yīng)滿足f(s-1) f(s)， f(s+1) f(s)

18、hcc1s ，于是，于是1lnhcclns 由由f(s+1) f(s)得得hccs ，于是，于是 lnhcclns由由f(s-1) f(s)得得因此取最佳因此取最佳s*為最靠近為最靠近 lnhccln的正整數(shù)即可。的正整數(shù)即可。404029292022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例3 設(shè)船按泊松流進港口，平均每天到達設(shè)船按泊松流進港口，平均每天到達2條，裝卸時間條，裝卸時間服從負指數(shù)分布，平均每天裝卸服從負指數(shù)分布，平均每天裝卸3條船，求：條船，求：1) 平均等待對長與平均等待時間；平均等待對長與平均等待時間；2) 如果船在港口的停留時間超

19、過一個值如果船在港口的停留時間超過一個值t0就要罰款，求就要罰款，求遭罰款的概率；遭罰款的概率；3) 若每超過一天罰款若每超過一天罰款c元，提前一天獎勵元，提前一天獎勵b元。假定服元。假定服務(wù)費與服務(wù)率成正比，每天務(wù)費與服務(wù)率成正比，每天 h元，裝卸一條船收入元，裝卸一條船收入a元，求使港口每天收入最大的服務(wù)率元，求使港口每天收入最大的服務(wù)率 *的值。的值。404030302022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例3(續(xù)續(xù)1)解解 由題設(shè)知，由題設(shè)知， 2(條條/天天)， 3(條條/天天)， ，該，該系統(tǒng)按系統(tǒng)按M/M/1/ 型處理。型處理。1

20、) 平均等待對長為平均等待對長為32341N2q (條船條船)平均等待時間為平均等待時間為32)1(Wq (天天)2) 由于遭到罰款當(dāng)且僅當(dāng)船在港口的逗留時間超過由于遭到罰款當(dāng)且僅當(dāng)船在港口的逗留時間超過t0，所，所以遭到罰款的概率為以遭到罰款的概率為00tt )(0eetWPp 3) 從費用方面考慮，每天裝卸完從費用方面考慮，每天裝卸完 條船收入條船收入 a元，每天服元，每天服務(wù)費為務(wù)費為h 元。元。404031312022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例3(續(xù)續(xù)2)平均提前完成時間為平均提前完成時間為e1 1tdte )(tt (t00t

21、 )(0t0t )(0 前前平均延后時間為平均延后時間為00t )(tt )(0e1dte )(tt (t 后后所以，港口一天的總收入為所以，港口一天的總收入為前前后后btctah)( f 00t )(0t )(ebbbtecah )bta(becbh0t )(0 404032322022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例3(續(xù)續(xù)3)對對f求導(dǎo)得求導(dǎo)得e ) cb(1t )()(hb)(1t )(d)(df0t )(0220 討論：討論：1) bc時，時，hb* 2) bc時，由于時，由于 的符號在的符號在 時完全由括號內(nèi)的兩時完全由括號內(nèi)的兩

22、項決定。令項決定。令 d)(df0t )(2021e ) cb(y,1t )()(hby 404033332022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例3(續(xù)續(xù)4)由上圖看出，由上圖看出，y1與與y2兩曲線有唯一交點，其橫坐標(biāo)為兩曲線有唯一交點，其橫坐標(biāo)為 *， b (b-c) *y hb y2y1且且 *唯一存在、有限，唯一存在、有限，hb* 404034342022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例3(續(xù)續(xù)5) b (b-c) *y hb y2y13)bc時，時，由下圖看出，由下圖看出，y1與與

23、y2兩曲線仍有唯一交點，兩曲線仍有唯一交點，其橫坐標(biāo)為其橫坐標(biāo)為 *，且，且 *唯一存在、有限，唯一存在、有限，hb* 404035352022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例4 設(shè)顧客到達為泊松流，平均每小時到達設(shè)顧客到達為泊松流，平均每小時到達 個顧個顧客是已知的。一個顧客在系統(tǒng)內(nèi)逗留每小時損失客是已知的。一個顧客在系統(tǒng)內(nèi)逗留每小時損失c1元，服務(wù)機構(gòu)的費用正比于服務(wù)率元，服務(wù)機構(gòu)的費用正比于服務(wù)率 ，每小時每，每小時每位顧客的費用為位顧客的費用為c2元。假定服務(wù)時間為參數(shù)元。假定服務(wù)時間為參數(shù) 的負的負指數(shù)分布，求最佳指數(shù)分布，求最佳服務(wù)率服務(wù)率 *，使得整個系統(tǒng)總費，使得整個系統(tǒng)總費用最少。用最少。解解 平均對長平均對長 每小時顧客的平均損失費為每小時顧客的平均損失費為 元元 1N 1c404036362022-6-292022-6-29計算機科學(xué)與工程學(xué)院顧小豐計算機科學(xué)與工程學(xué)院顧小豐例例4