忻展紅-運(yùn)籌學(xué)-課件運(yùn)籌七

1、管理與人文學(xué)院1999，4忻展紅第七章隨機(jī)服務(wù)理論概述確定型只是隨機(jī)現(xiàn)象的特例7.1 隨機(jī)服務(wù)系統(tǒng) 系統(tǒng)的輸入與輸出是隨量 A.k.Erlang 于19091920年發(fā)表了一系列根據(jù)話務(wù)量計(jì)算電話機(jī)鍵配置的方法，為隨機(jī)服務(wù)理論奠定了基礎(chǔ) 又稱為排隊(duì)論(Queuing Theory)或擁塞理論(Congestion Theory)三個(gè)服務(wù)臺(tái)隨機(jī)服務(wù)系統(tǒng)離去的顧客.排隊(duì)等待顧客2顧客源與服務(wù)系統(tǒng)性能相關(guān)的特性 服務(wù)系統(tǒng)存在來(lái)自兩個(gè)矛盾方面的要求 顧客希望服務(wù)質(zhì)量好，如排隊(duì)等待時(shí)間短，損失率低 系統(tǒng)運(yùn)營(yíng)方希望設(shè)備利用率高 給用戶一個(gè)經(jīng)濟(jì)上能夠承受的滿意的質(zhì)量 哪些系統(tǒng)特性會(huì)影響系統(tǒng)的性能？ 服務(wù)機(jī)構(gòu)

2、的組織方式與服務(wù)方式 顧客的輸入過(guò)程和服務(wù)時(shí)間分布 系統(tǒng)采用的服務(wù)規(guī)則7.1.1 服務(wù)機(jī)構(gòu)的組織方式與服務(wù)方式 單臺(tái)制和多臺(tái)制 并聯(lián)服務(wù) 串聯(lián)服務(wù) 串并聯(lián)服務(wù)、網(wǎng)絡(luò)服務(wù) 全利用度、部分利用度3與服務(wù)系統(tǒng)性能相關(guān)的特性7.1.2 輸入過(guò)程和服務(wù)時(shí)間 顧客單個(gè)到達(dá)或成批到達(dá) 顧客到達(dá)時(shí)間間隔的分布和服務(wù)時(shí)間的分布 顧客源是有限的還是無(wú)限的7.1.3 服務(wù)規(guī)則 損失制 等待制：先到先服務(wù)(FIFO)，后到先服務(wù)，隨機(jī)服務(wù)，優(yōu)先權(quán)服務(wù) 混合制 逐個(gè)到達(dá)，成批服務(wù)；成批到達(dá)，逐個(gè)服務(wù)47.2隨機(jī)服務(wù)過(guò)程 單臺(tái)服務(wù)系統(tǒng)、等待制、先到先服務(wù) 顧客在系統(tǒng)中的總時(shí)長(zhǎng)：逗留時(shí)間=等待時(shí)長(zhǎng)+服務(wù)時(shí)長(zhǎng) 等待時(shí)長(zhǎng)與顧客

3、到達(dá)率和服務(wù)時(shí)長(zhǎng)有關(guān)51234顧客t1t2t3t4到達(dá)時(shí)刻開(kāi)始服務(wù)時(shí)刻w2w3服務(wù)t終結(jié)時(shí)刻h1h2h3空h41234當(dāng)服務(wù)臺(tái)連續(xù)不斷服務(wù)時(shí)，有如下關(guān)系：wi+1+ti+1= wi+hiwi+hi 表示了累計(jì)的未完成的服務(wù)時(shí)長(zhǎng)，一般地有ti , wi , hi 可通過(guò)寫實(shí)來(lái)獲得，另一種寫實(shí)法a(t) 代表時(shí)段(0, t)中累計(jì)到達(dá)顧客數(shù)b(t) 代表時(shí)段(0, t)中累計(jì)接受服務(wù)的顧客數(shù)g(t) 代表時(shí)段(0, t)中累計(jì)服務(wù)完畢的顧客數(shù)則在任意考察時(shí)刻 t，有正在等待的顧客數(shù)：L(t)= a(t) - b(t)正在接受服務(wù)的顧客數(shù)：Ls(t)= b(t) - g(t)系統(tǒng)中逗留的顧客數(shù)：N(

4、t)= a(t) - g(t)6w= wi + hi - t i+1if wi + hi - t i+1 0i+10if wi + hi - t i+1 0 上述關(guān)系是普遍成立的，與服務(wù)臺(tái)設(shè)置和服務(wù)規(guī)則無(wú)關(guān) 下面分析等待顧客數(shù)、等待時(shí)間和顧客到達(dá)率的關(guān)系 到達(dá)率定義為單位時(shí)間內(nèi)平均到達(dá)的顧客數(shù)，即lt= a(t) / t 令 d(t) 表示在時(shí)段(0, t)內(nèi)到達(dá)系統(tǒng)內(nèi)顧客的總逗留時(shí)長(zhǎng) 則每一個(gè)顧客的平均逗留時(shí)間為Wdt= d(t) /a(t) 系統(tǒng)中平均逗留顧客數(shù)可表達(dá)為L(zhǎng)dt= d(t) / t = (a(t) / t )(d(t) /a(t) ) = lt Wdt(Little form

5、ula)7系統(tǒng)中逗留顧客數(shù)平均逗留顧客數(shù)t 系統(tǒng)處于穩(wěn)態(tài)時(shí)的利特爾公式：Ld= l Wd 利特爾公式也是普遍成立的，已知其中任兩個(gè)量，可以求出另一個(gè)量 利特爾公式的分解：Ld = l Wd = l (Wq + h ) = Lq+ LnLq = l WqLn = l hWq 是顧客的平均排隊(duì)等待時(shí)間Lq 是排隊(duì)等待的平均隊(duì)長(zhǎng)h是顧客的平均服務(wù)時(shí)長(zhǎng)Ln 是同時(shí)接受服務(wù)的平均顧客數(shù)(即平均服務(wù)臺(tái)占用數(shù))87.3 服務(wù)時(shí)間與間隔時(shí)間7.3.1 概述 顧客的服務(wù)時(shí)間由于多種原因具有不確定性，最好的描述方法就是概率分布；同樣顧客到達(dá)的間隔時(shí)間也具有一定的概率分布 服務(wù)時(shí)間和到達(dá)間隔時(shí)間服從什么分布？可以先

6、通過(guò)統(tǒng)計(jì)得到經(jīng)驗(yàn)分布，然后再做理論假設(shè)和檢驗(yàn) 經(jīng)驗(yàn)分布一般采用直方圖來(lái)表示，如下圖頻率%302010通話分鐘24689 若統(tǒng)計(jì)區(qū)間分得越細(xì)，樣本越多，則經(jīng)驗(yàn)分布的輪廓越接近曲線 一般服務(wù)時(shí)間和間隔時(shí)間都是非負(fù)的連續(xù)實(shí)變量，令 h 代表服務(wù)時(shí)間，t 代表間隔時(shí)間，t 為給定的時(shí)間，則它們的概率分布函數(shù)分別表示為F(t)=Pt tF(t)=Ph t 它們的概率密度函數(shù)為f(t)=F(t)，具有性質(zhì)：f(t)0，f(t)dt=1 服務(wù)時(shí)間落在區(qū)間(a, c)的概率為 服務(wù)時(shí)間落在區(qū)間(t, t+Dt)的概率為Pt h t+Dt= f(t)Dt 平均服務(wù)時(shí)長(zhǎng)和平均間隔時(shí)長(zhǎng) 平均服務(wù)時(shí)長(zhǎng)的倒數(shù)為服務(wù)率，

7、平均間隔時(shí)長(zhǎng)的倒數(shù)為到達(dá)率10m = 1 hl = 1 th = Eh = tf (t)dtt= Et = tf (t)dt00Pa h c= c f (t)dt = F(c) - F(a)a7.3.2 常用的概率分布1、定長(zhǎng)分布流水線的加工時(shí)間2、負(fù)指數(shù)分布一類最常用的分布，如上述通話時(shí)長(zhǎng)，可靠性m110lt0t定長(zhǎng)分布負(fù)指數(shù)分布11f(t) F(t)F(t)f(t)F (t ) = 1 - e -mtf (t ) = me -mth = tme -mt dt = 1/ m0F (t) = 1當(dāng)t l0當(dāng)t t0 = Ph t + t0 h t0 =Pt0 t0 Ph t0 = 1 - e

8、-m (t +t0 ) - (1 - e -m t0 ) =-m t1 - (1 - e -m t0 )1 - eQ.E.D7.3.3 負(fù)指數(shù)分布的特點(diǎn) 一個(gè)服從負(fù)指數(shù)分布的服務(wù)，在下一瞬間結(jié)束的概率 在Dt 內(nèi)服務(wù)終結(jié)的概率只與 m 和Dt 成正比，與 t0 無(wú)關(guān)；因此 m 又稱為終結(jié)率，或離去率 同理，在 Dt 內(nèi)服務(wù)不終結(jié)的概率為1m Dt +o(Dt ) n 個(gè)獨(dú)立同分布(負(fù)指數(shù))的服務(wù)臺(tái)同時(shí)被占用，在Dt 內(nèi)只有一個(gè)服務(wù)臺(tái)終結(jié)的概率為 C1(mD t + o(Dt)(1- m Dt + o(Dt)n-1 = nmD t + o(Dt)n 在Dt 內(nèi)有 k 1 個(gè)服務(wù)臺(tái)終結(jié)的概率為 o

9、(Dt )，稱為普通性 Ck (m Dt + o(Dt)k (1- mD t + o(Dt)n-k = o(Dt)n14應(yīng)用無(wú)記憶性Ph t0 + Dt h t0 = 1 - e -m Dt= 1 - 1 - m Dt + (m Dt )22! - (m Dt )33! + L= m Dt + o(Dt )7.4 輸入過(guò)程 即顧客到達(dá)的分布，可用相繼到達(dá)顧客的間隔時(shí)間描述， 也可以用單位時(shí)間內(nèi)到達(dá)的顧客數(shù)描述 間隔時(shí)間服從定長(zhǎng)分布 單位時(shí)間內(nèi)到達(dá)的顧客數(shù)服從波松分布(法國(guó)數(shù)學(xué)家Poisson, 1837) 間隔時(shí)間服從愛(ài)爾蘭分布 一般獨(dú)立同分布7.4.1 波松輸入過(guò)程及其特點(diǎn) (0, t)時(shí)間

10、內(nèi)到達(dá) k 個(gè)顧客的個(gè)數(shù)服從波松分布，若l 為到達(dá)率電話呼叫的到達(dá)，商店的顧客到達(dá)，十字路口的汽車流，港口到達(dá)的船只，機(jī)場(chǎng)到達(dá)的飛機(jī)等15(l t )k-l tPk (t) =k!e7.4.1 波松輸入過(guò)程及其特點(diǎn)(1) 平穩(wěn)性：顧客到達(dá)數(shù)只與時(shí)間區(qū)間長(zhǎng)度有關(guān)(2) 無(wú)后效性：不相交的時(shí)間區(qū)間內(nèi)所到達(dá)的顧客數(shù)是獨(dú)立的(3) 普通性：在Dt 時(shí)間內(nèi)到達(dá)一個(gè)顧客的概率為 l Dt +o(Dt )， 到達(dá)兩個(gè)或兩個(gè)以上顧客的概率為 o(Dt )；即兩個(gè)顧客不可能同時(shí)到達(dá) 波松過(guò)程具有可迭加性即獨(dú)立的波松分布變量的和仍為波松分布(l t )i-l t(l t ) j-l t設(shè)兩個(gè)波松分布為:P (t

11、) = 1e1, P (t ) = 2e2ii!jj!令 n = i + j, 在(0, t )內(nèi)兩個(gè)流共來(lái)到n 個(gè)顧客的概率為nPx+ x= n=Px=j Px= n - j1212j =0= n(l t ) j-l t (l t )n- j-l t = (l+ l)n t n-(l + l )t 1e1 2e2 12e12j=0j!(n - j)!n!167.4.1 波松輸入過(guò)程及其特點(diǎn) 波松過(guò)程的到達(dá)間隔時(shí)間為負(fù)指數(shù)分布 令 t 代表間隔時(shí)間，則概率 Pt t代表時(shí)間區(qū)間(0, t)內(nèi)沒(méi)有顧客來(lái)的概率；由波松分布可知P0(t)= Pt t=e-lt 故間隔時(shí)間 t 的分布為 Pt t=1

12、-e-lt7.4.2 馬爾科夫鏈 馬爾科夫鏈(Markov Chain)又簡(jiǎn)稱馬氏鏈，是一種離散隨機(jī)過(guò)程。用數(shù)學(xué)式表達(dá)為PXn+1=xn+1| X1=x1, X2=x2, . , Xn=xn= PXn+1=xn+1| Xn=xn Xn+1的狀態(tài)只與 Xn的狀態(tài)有關(guān)，與 Xn 前的狀態(tài)無(wú)關(guān)， 具有無(wú)記憶性，或無(wú)后效性，又稱馬氏性 狀態(tài)轉(zhuǎn)移是一步一步發(fā)生的，一步狀態(tài)轉(zhuǎn)移概率Pij(t)=PXn+1=j| Xn=i17例 7.4.2一售貨員出售兩種商品A和B，每日工作 8 小時(shí)。購(gòu)買每種 商品的顧客到達(dá)過(guò)程為波松分布，到達(dá)率分別為 lA=8人/日，lB=16人/日，試求：(1) 1小時(shí)內(nèi)來(lái)到顧客總數(shù)

13、為 3 人的概率；(2) 三個(gè)顧客全是購(gòu)買B類商品的概率。解：(1)總到達(dá)率為 lA+ lB=24人/日，1 小時(shí)=1/8 日，故(2) 3 個(gè)顧客全是購(gòu)買B 類商品的概率為18(16 1 / 8)3-161 / 8-81 / 8PB3 (1/ 8)PA0 (1/ 8) =3!e e= 0.0664(24 1/ 8)3-241 / 8P3 (1/ 8) =3!e= 0.2247.5 生滅過(guò)程 采用馬氏鏈 令 N(t)代表系統(tǒng)在時(shí)刻 t 的狀態(tài)，下一瞬間 t+Dt 系統(tǒng)的狀態(tài)只能轉(zhuǎn)移到相鄰狀態(tài)，或維持不變，如圖所示 三種轉(zhuǎn)移是不相容的，三者必居其一 只有具有無(wú)記憶性和普通性的過(guò)程(分布)才適用馬

14、氏鏈 令 Pj(t)=PN(t)=j代表系統(tǒng)在時(shí)刻 t 處于狀態(tài) j 的概率19ljDtj+11-(l j+mj)DtjjmjDtj-1tt+Dt生滅過(guò)程的馬氏鏈 根據(jù)馬氏鏈，應(yīng)用全概率公式，有狀態(tài)轉(zhuǎn)移概率方程 另有兩個(gè)邊界方程 p0 (t + Dt) = p1(t)m1Dt + p0 (t)(1 - l0Dt) + o(Dt) pn (t + Dt) = pn-1(t)ln-1Dt + pn (t)(1 - mnDt) + o(Dt)20p j (t + Dt ) = p j-1 (t)l j-1Dt + p j+1 (t)m j+1Dt+ p j (t)(1 - l jDt - m jDt

15、) + o(Dt)j = 1,2,L, n - 11-l0Dt1-(l1+m1)Dt1-(lj-1+mj-1)Dt1-(lj+mj)Dt1-(lj+1+mj+1)Dt1-mnDtl0Dtl1Dtlj-1DtljDtln-1Dt01.j-1jj+1.nm1Dtmj-1DtmjDtmj+1DtmnDt生滅方程的推導(dǎo)過(guò)程 將上述三個(gè)差分方程化為微分方程 上述三個(gè)方程是動(dòng)態(tài)方程，當(dāng)系統(tǒng)處于穩(wěn)態(tài)時(shí)，系統(tǒng)處于統(tǒng)計(jì)平衡狀態(tài)，即狀態(tài)概率不隨時(shí)間變化，從而狀態(tài)概率導(dǎo)數(shù)為 0；令上三個(gè)方程左側(cè)為 0，得穩(wěn)態(tài)方程組m1 p1 - l0 p0 = 0j = 0(1)m j+1 p j +1 + l j-1 p j -

16、1 - (l j + m j ) p j = 01 j n(2)mn pn - ln-1 pn-1 = 0j = n(3)21pj (t + Dt) - pj (t)lim= l j -1 pj -1(t) + m j +1 pj +1(t)Dt0Dt- (l j + m j ) pj (t)j = 1,2,L, n - 1即pj (t) = l j-1 pj -1(t) + m j+1 pj +1(t) - (l j + m j ) pj (t)同理有 p0 (t) = m1 p1 (t) - l0 p0 (t)pn (t) = ln-1 pn-1 (t) - mn pn (t)生滅過(guò)程穩(wěn)態(tài)

17、解 方程(1), (2), (3) 與穩(wěn)態(tài)狀態(tài)轉(zhuǎn)移圖一一對(duì)應(yīng)；遞歸解如下：= l0l0l1m1m2令 j = 1, 將p1 代入(2)式得:p2 =p1p0p0m1l j -1l0l1 Ll j -1p j =依次遞推, 得p j -1p0(歸納法)mmmLmj12j-1llLlnj -1 01n p jp0 = 1 + = 1,得由0m1m2 Lm j22j=1m1 p1 - l0 p0 = 0j = 0(1)m j+1 p j +1 + l j-1 p j -1 - (l j + m j ) p j = 01 j n(2)mn pn - ln-1 pn-1 = 0j = n(3)l0l1l

18、j-1ljln-101.j-1jj+1.nm1mj-1mjmj+1mn滿足生滅過(guò)程的條件 系統(tǒng)的輸入過(guò)程和服務(wù)過(guò)程具有平穩(wěn)、無(wú)記憶性和普通性 服務(wù)臺(tái)是獨(dú)立的、相同的、并聯(lián)的 波松輸入過(guò)程和負(fù)指數(shù)服務(wù)時(shí)長(zhǎng)就具有這些性質(zhì) 可以用馬氏鏈來(lái)描述系統(tǒng)的狀態(tài)轉(zhuǎn)移 這種系統(tǒng)稱為生滅服務(wù)系統(tǒng)，一般用M/M/n 表示，又稱為標(biāo)準(zhǔn)服務(wù)系統(tǒng)； 標(biāo)準(zhǔn)服務(wù)系統(tǒng)的形式很多，但都是基于生滅方程，關(guān)鍵是找出 lj , mj 的不同表達(dá)式，將它們代入生滅方程 標(biāo)準(zhǔn)服務(wù)系統(tǒng)的表示法：(X/Y/Z: A/B/C)，X 表示輸入過(guò)程， Y 表示服務(wù)過(guò)程，Z 表示并聯(lián)服務(wù)臺(tái)的個(gè)數(shù)，A 表示顧客源， B 表示系統(tǒng)容量，C 表示服務(wù)規(guī)則 (M/M/n: /m/FIFO) 表示波松輸入，負(fù)指數(shù)服