運(yùn)籌學(xué)教程課件七隨機(jī)服務(wù)理論概述

1第七章隨機(jī)服務(wù)理論概述確定型只是隨機(jī)現(xiàn)象的特例27.1隨機(jī)服務(wù)系統(tǒng)系統(tǒng)的輸入與輸出是隨機(jī)變量A.k.Erlang于1909~1920年發(fā)表了一系列根據(jù)話務(wù)量計(jì)算電話機(jī)鍵配置的方法，為隨機(jī)服務(wù)理論奠定了基礎(chǔ)又稱為排隊(duì)論(QueuingTheory)或擁塞理論(CongestionTheory)3

與服務(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)的組織方式與服務(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ù)全利用度、部分利用度4

與服務(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ù)57.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)與顧客到達(dá)率和服務(wù)時(shí)長(zhǎng)有關(guān)6當(dāng)服務(wù)臺(tái)連續(xù)不斷服務(wù)時(shí)，有如下關(guān)系：wi+1+i+1=wi+hiwi+hi

表示了累計(jì)的未完成的服務(wù)時(shí)長(zhǎng)，一般地有

忙期和忙時(shí)系統(tǒng)連續(xù)不斷服務(wù)的時(shí)期稱為忙期。而系統(tǒng)最繁忙的一個(gè)小時(shí)稱為忙時(shí)。排隊(duì)系統(tǒng)的指標(biāo)及其關(guān)系1）Wq

、Wd分別是顧客的平均排隊(duì)等待時(shí)間和平均逗留時(shí)間2）Lq

、Ld分別是系統(tǒng)平均排隊(duì)的顧客數(shù)和系統(tǒng)的平均顧客數(shù)3）h

是顧客的平均服務(wù)時(shí)長(zhǎng)，是顧客的平均到達(dá)率。4）Ln

是同時(shí)接受服務(wù)的平均顧客數(shù)(即平均服務(wù)臺(tái)占用數(shù))5）Ld=

Wd=

(Wq+h)=Lq+Ln，Lq=

Wq，Ln=

h77.3服務(wù)時(shí)間與間隔時(shí)間

7.3.1概述顧客的服務(wù)時(shí)間由于多種原因具有不確定性，最好的描述方法就是概率分布；同樣顧客到達(dá)的間隔時(shí)間也具有一定的概率分布服務(wù)時(shí)間和到達(dá)間隔時(shí)間服從什么分布？可以先通過(guò)統(tǒng)計(jì)得到經(jīng)驗(yàn)分布，然后再做理論假設(shè)和檢驗(yàn)經(jīng)驗(yàn)分布一般采用直方圖來(lái)表示，如下圖8若統(tǒng)計(jì)區(qū)間分得越細(xì)，樣本越多，則經(jīng)驗(yàn)分布的輪廓越接近曲線一般服務(wù)時(shí)間和間隔時(shí)間都是非負(fù)的連續(xù)實(shí)變量，令h

代表服務(wù)時(shí)間，代表間隔時(shí)間，t

為給定的時(shí)間，則它們的概率分布函數(shù)分別表示為

F(t)=P{ht} F(t)=P{

t}它們的概率密度函數(shù)為 f(t)=F(t)，具有性質(zhì)：

f(t)0，f(t)dt=1服務(wù)時(shí)間落在區(qū)間(a,c)的概率為服務(wù)時(shí)間落在區(qū)間(t,t+t)的概率為P{t<ht+t}=f(t)t平均服務(wù)時(shí)長(zhǎng)和平均間隔時(shí)長(zhǎng)平均服務(wù)時(shí)長(zhǎng)的倒數(shù)為服務(wù)率，平均間隔時(shí)長(zhǎng)的倒數(shù)為到達(dá)率97.3.2常用的概率分布1、定長(zhǎng)分布流水線的加工時(shí)間2、負(fù)指數(shù)分布一類最常用的分布，如上述通話時(shí)長(zhǎng)，可靠性107.3.2常用的概率分布3、愛爾蘭分布一種代表性更廣的分布k

為整數(shù)，稱為

k

階愛爾蘭分布；當(dāng)k=1

時(shí)，退化為負(fù)指數(shù)分布；k

時(shí)趨向定長(zhǎng)分布愛爾蘭分布實(shí)際上是k

個(gè)獨(dú)立同分布的負(fù)指數(shù)分布隨機(jī)變量的和的分布，即k

個(gè)服務(wù)臺(tái)的串聯(lián)，每個(gè)服務(wù)臺(tái)的平均服務(wù)時(shí)長(zhǎng)為1/k117.3.3負(fù)指數(shù)分布的特點(diǎn)負(fù)指數(shù)分布之所以常用，是因?yàn)樗泻芎玫奶匦?，使?shù)學(xué)分析變得方便無(wú)記憶性。指的是不管一次服務(wù)已經(jīng)過(guò)去了多長(zhǎng)時(shí)間，該次服務(wù)所剩的服務(wù)時(shí)間仍服從原負(fù)指數(shù)分布127.3.3負(fù)指數(shù)分布的特點(diǎn)一個(gè)服從負(fù)指數(shù)分布的服務(wù)，在下一瞬間結(jié)束的概率在t

內(nèi)服務(wù)終結(jié)的概率只與和t

成正比，與t0

無(wú)關(guān)；因此又稱為終結(jié)率，或離去率同理，在t

內(nèi)服務(wù)不終結(jié)的概率為1–t+o(t)n

個(gè)獨(dú)立同分布(負(fù)指數(shù))的服務(wù)臺(tái)同時(shí)被占用，在t

內(nèi)只有一個(gè)服務(wù)臺(tái)終結(jié)的概率為

在t

內(nèi)有k>1個(gè)服務(wù)臺(tái)終結(jié)的概率為o(t)，稱為普通性

137.4輸入過(guò)程即顧客到達(dá)的分布，可用相繼到達(dá)顧客的間隔時(shí)間描述，也可以用單位時(shí)間內(nèi)到達(dá)的顧客數(shù)描述間隔時(shí)間服從定長(zhǎng)分布單位時(shí)間內(nèi)到達(dá)的顧客數(shù)服從波松分布(法國(guó)數(shù)學(xué)家Poisson,1837)間隔時(shí)間服從愛爾蘭分布一般獨(dú)立同分布

7.4.1波松輸入過(guò)程及其特點(diǎn)(0,t)時(shí)間內(nèi)到達(dá)

k

個(gè)顧客的個(gè)數(shù)服從波松分布，若為到達(dá)率電話呼叫的到達(dá)，商店的顧客到達(dá)，十字路口的汽車流，港口到達(dá)的船只，機(jī)場(chǎng)到達(dá)的飛機(jī)等147.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)普通性：在t

時(shí)間內(nèi)到達(dá)一個(gè)顧客的概率為t+o(t)，到達(dá)兩個(gè)或兩個(gè)以上顧客的概率為o(t)；即兩個(gè)顧客不可能同時(shí)到達(dá)(4)有限性：在有限的時(shí)間區(qū)間內(nèi)，到達(dá)的顧客數(shù)是有限的。波松過(guò)程具有可迭加性即獨(dú)立的波松分布變量的和仍為波松分布157.4.1波松輸入過(guò)程及其特點(diǎn)波松過(guò)程的到達(dá)間隔時(shí)間為負(fù)指數(shù)分布令代表間隔時(shí)間，則概率P{>t}代表時(shí)間區(qū)間(0,t)內(nèi)沒(méi)有顧客來(lái)的概率；由波松分布可知

P0(t)=P{>t}=et故間隔時(shí)間的分布為P{t}=1et

7.4.2馬爾科夫鏈馬爾科夫鏈(MarkovChain)又簡(jiǎn)稱馬氏鏈，是一種離散事件隨機(jī)過(guò)程。用數(shù)學(xué)式表達(dá)為P{Xn+1=xn+1|X1=x1,X2=x2,...,Xn=xn}=P{Xn+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)=P{Xn+1=j|Xn=i}16

例7.4.2

一售貨員出售兩種商品A和B，每日工作8小時(shí)。購(gòu)買每種商品的顧客到達(dá)過(guò)程為波松分布，到達(dá)率分別為A=8人/日，B=16人/日，試求：(1)1小時(shí)內(nèi)來(lái)到顧客總數(shù)為3人的概率；(2)三個(gè)顧客全是購(gòu)買B類商品的概率。解：(1)總到達(dá)率為A+B=24人/日，1小時(shí)=1/8日，故(2)3個(gè)顧客全是購(gòu)買B類商品的概率為177.5生滅過(guò)程一種描述自然界生滅現(xiàn)象的數(shù)學(xué)方法，如細(xì)菌的繁殖和滅亡，人口的增減，生物種群的滅種現(xiàn)象等采用馬氏鏈令N(t)代表系統(tǒng)在時(shí)刻

t

的狀態(tài)，下一瞬間t+t

系統(tǒng)的狀態(tài)只能轉(zhuǎn)移到相鄰狀態(tài)，或維持不變，如圖所示三種轉(zhuǎn)移是不相容的，三者必居其一只有具有無(wú)記憶性和普通性的過(guò)程(分布)才適用馬氏鏈令Pj(t)=P{N(t)=j}代表系統(tǒng)在時(shí)刻t

處于狀態(tài)

j

的概率18

生滅過(guò)程的馬氏鏈根據(jù)馬氏鏈，應(yīng)用全概率公式，有狀態(tài)轉(zhuǎn)移概率方程另有兩個(gè)邊界方程19

生滅方程的推導(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)方程組20

生滅過(guò)程穩(wěn)態(tài)解方程(1),(2),(3)與穩(wěn)態(tài)狀態(tài)轉(zhuǎn)移圖一一對(duì)應(yīng)；遞歸解如下：21

滿足生滅過(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)鍵是找出j,j

的不同表達(dá)式，將它們代入生滅方程