運(yùn)籌學(xué)

OPERATIONSRESEARCH

2022/12/211運(yùn)籌學(xué)

OPERATIONSRESEARCH

2022/1§1排隊(duì)服務(wù)系統(tǒng)的基本概念

排隊(duì)論是研究排隊(duì)系統(tǒng)（又稱隨機(jī)服務(wù)系統(tǒng)）的數(shù)學(xué)理論和方法，是運(yùn)籌學(xué)的一個(gè)重要分支。

有形排隊(duì)現(xiàn)象：進(jìn)餐館就餐，到圖書館借書，車站等車，去醫(yī)院看病，售票處售票，到工具房領(lǐng)物品等現(xiàn)象。

第十章排隊(duì)論2022/12/212§1排隊(duì)服務(wù)系統(tǒng)的基本概念第十章排隊(duì)論2022/12/1

無形排隊(duì)現(xiàn)象：如幾個(gè)旅客同時(shí)打電話訂車票；如果有一人正在通話，其他人只得在各自的電話機(jī)前等待，他們分散在不同的地方，形成一個(gè)無形的隊(duì)列在等待通電話。排隊(duì)的不一定是人，也可以是物。如生產(chǎn)線上的原材料，半成品等待加工；因故障而停止運(yùn)行的機(jī)器設(shè)備在等待修理；碼頭上的船只等待裝貨或卸貨；要下降的飛機(jī)因跑道不空而在空中盤旋等。2022/12/213無形排隊(duì)現(xiàn)象：如幾個(gè)旅客同時(shí)打電話訂車票；如果有一當(dāng)然，進(jìn)行服務(wù)的也不一定是人，可以是跑道，自動(dòng)售貨機(jī)，公共汽車等。顧客——要求服務(wù)的對(duì)象。服務(wù)員——提供服務(wù)的服務(wù)者（也稱服務(wù)機(jī)構(gòu)）。顧客、服務(wù)員的含義是廣義的。2022/12/214當(dāng)然，進(jìn)行服務(wù)的也不一定是人，可以是跑道，自動(dòng)售貨機(jī)，公共汽隨機(jī)性——顧客到達(dá)情況與顧客接受服務(wù)的時(shí)間是隨機(jī)的。一般來說，排隊(duì)論所研究的排隊(duì)系統(tǒng)中，顧客相繼到達(dá)時(shí)間間隔和服務(wù)時(shí)間這兩個(gè)量中至少有一個(gè)是隨機(jī)的，因此，排隊(duì)論又稱隨機(jī)服務(wù)理論。隨機(jī)服務(wù)理論研究如何合理的設(shè)置服務(wù)系統(tǒng)，更好的為顧客服務(wù)，減少排隊(duì)時(shí)間，同時(shí)又要使得費(fèi)用盡可能節(jié)省。2022/12/215隨機(jī)性——顧客到達(dá)情況與顧客接受服務(wù)的時(shí)間是隨機(jī)的。2022排隊(duì)系統(tǒng)類型1：服務(wù)臺(tái)顧客到達(dá)服務(wù)完成后離開單服務(wù)臺(tái)排隊(duì)系統(tǒng)2022/12/216排隊(duì)系統(tǒng)類型1：服務(wù)臺(tái)顧客到達(dá)服務(wù)完成后離開單服務(wù)臺(tái)排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)類型2：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，一個(gè)隊(duì)列的排隊(duì)系統(tǒng)服務(wù)臺(tái)s服務(wù)臺(tái)12022/12/217排隊(duì)系統(tǒng)類型2：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，一排隊(duì)系統(tǒng)類型3：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，S個(gè)隊(duì)列的排隊(duì)系統(tǒng)服務(wù)臺(tái)s服務(wù)臺(tái)1服務(wù)完成后離開服務(wù)完成后離開2022/12/218排隊(duì)系統(tǒng)類型3：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，排隊(duì)系統(tǒng)類型4：服務(wù)臺(tái)1顧客到達(dá)離開多服務(wù)臺(tái)串聯(lián)排隊(duì)系統(tǒng)服務(wù)臺(tái)s2022/12/219排隊(duì)系統(tǒng)類型4：服務(wù)臺(tái)1顧客到達(dá)離開多服務(wù)臺(tái)串聯(lián)排隊(duì)系統(tǒng)服務(wù)排隊(duì)系統(tǒng)的描述

實(shí)際中的排隊(duì)系統(tǒng)各不相同，但概括起來都由三個(gè)基本部分組成：

1、輸入過程;

2、排隊(duì)及排隊(duì)規(guī)則;

3、服務(wù)機(jī)構(gòu)2022/12/2110排隊(duì)系統(tǒng)的描述2022/12/1910

河流上游流入水庫的水量可認(rèn)為是無限的；車間內(nèi)停機(jī)待修的機(jī)器顯然是有限的。到達(dá)方式：是單個(gè)到達(dá)還是成批到達(dá)。

庫存問題中，若把進(jìn)來的貨看成顧客，則為成批到達(dá)的例子。1、輸入過程顧客總體（顧客源）數(shù)：可能是有限，也可能是無限。2022/12/2111河流上游流入水庫的水量可認(rèn)為是無限的；車間內(nèi)停機(jī)待修顧客（單個(gè)或成批）相繼到達(dá)的時(shí)間間隔分布：這是刻劃輸入過程的最重要內(nèi)容。令T0=0，Tn表示第n顧客到達(dá)的時(shí)刻，則有T0T1T2…..Tn……記Xn=Tn–Tn-1n=1,2,…,則Xn是第n顧客與第n-1顧客到達(dá)的時(shí)間間隔。一般假定{Xn}是獨(dú)立同分布，并記分布函數(shù)為A(t)。2022/12/2112顧客（單個(gè)或成批）相繼到達(dá)的時(shí)間間隔分布：這是刻劃輸入過程的{Xn}的分布A(t)常見的有：定長(zhǎng)分布（D）：顧客相繼到達(dá)的時(shí)間間隔為確定的。如產(chǎn)品通過傳送帶進(jìn)入包裝箱就是定常分布。最簡(jiǎn)單流（或稱Poisson)（M）：顧客相繼到達(dá)的時(shí)間間隔{Xn}為獨(dú)立的，同為負(fù)指數(shù)分布，其密度函數(shù)為：f(t)=e-tt00t<02022/12/2113{Xn}的分布A(t)常見的有：f(t)=e-t2、排隊(duì)及排隊(duì)規(guī)則排隊(duì)有限排隊(duì)——排隊(duì)系統(tǒng)中顧客數(shù)是有限的。（損失制排隊(duì)系統(tǒng)，混合制排隊(duì)系統(tǒng)）無限排隊(duì)——顧客數(shù)是無限，隊(duì)列可以排到無限長(zhǎng)（等待制排隊(duì)系統(tǒng)）。2022/12/21142、排隊(duì)及排隊(duì)規(guī)則2022/12/1914有限排隊(duì)還可以分成：損失制排隊(duì)系統(tǒng)：排隊(duì)空間為零的系統(tǒng)，即不允許排隊(duì)。（顧客到達(dá)時(shí)，服務(wù)臺(tái)占滿，顧客自動(dòng)離開，不再回來）（電話系統(tǒng)）混合制排隊(duì)系統(tǒng)：是等待制與損失制結(jié)合，即允許排隊(duì)，但不允許隊(duì)列無限長(zhǎng)。2022/12/2115有限排隊(duì)還可以分成：2022/12/1915混合制排隊(duì)系統(tǒng)：1.隊(duì)長(zhǎng)有限,即系統(tǒng)等待空間是有限的。例：最多只能容納K個(gè)顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時(shí)，若系統(tǒng)中的顧客數(shù)（又稱為隊(duì)長(zhǎng)）小于K，則可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。2022/12/2116混合制排隊(duì)系統(tǒng)：2022/12/19162.等待時(shí)間有限。即顧客在系統(tǒng)中等待時(shí)間不超過某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超過T時(shí)，顧客將自動(dòng)離開，不再回來。如:易損失的電子元件的庫存問題，超過一定存儲(chǔ)時(shí)間的元器件被自動(dòng)認(rèn)為失效?；旌现婆抨?duì)系統(tǒng)：3.逗留時(shí)間（等待時(shí)間與服務(wù)時(shí)間之和）有限。例：用高射炮射擊飛機(jī)，當(dāng)敵機(jī)飛越射擊有效區(qū)域的時(shí)間為t時(shí)，若這個(gè)時(shí)間內(nèi)未被擊落，也就不可能再被擊落了。2022/12/21172.等待時(shí)間有限。即顧客在系統(tǒng)中等待時(shí)間不超過某一給定的長(zhǎng)說明：損失制和等待制可看成是混合制的特殊情形.如:記s為系統(tǒng)中服務(wù)臺(tái)個(gè)數(shù)，則當(dāng)k=s時(shí)，混合制即為損失制；當(dāng)k=時(shí)，即成為等待制。2022/12/2118說明：損失制和等待制可看成是混合制的特殊情形.2022/12排隊(duì)規(guī)則當(dāng)顧客到達(dá)時(shí)，若所有服務(wù)臺(tái)都被占有且又允許排隊(duì)，則該顧客將進(jìn)入隊(duì)列等待。服務(wù)臺(tái)對(duì)顧客進(jìn)行服務(wù)所遵循的規(guī)則通常有：先來先服務(wù)（FCFS）2022/12/2119排隊(duì)規(guī)則2022/12/1919后來先服務(wù)（LCFS）。在許多庫存系統(tǒng)中就會(huì)出現(xiàn)這種情況。如：鋼板存入倉庫后，需要時(shí)總是從最上面取出；又如在情報(bào)系統(tǒng)中，后來到達(dá)的信息往往更重要，首先要加以分析和利用。具有優(yōu)先權(quán)的服務(wù)（PS）。服務(wù)臺(tái)根據(jù)顧客的優(yōu)先權(quán)的不同進(jìn)行服務(wù)。如：病危的病人應(yīng)優(yōu)先治療；重要的信息應(yīng)優(yōu)先處理；出價(jià)高的顧客應(yīng)優(yōu)先考慮。2022/12/2120后來先服務(wù)（LCFS）。在許多庫存系統(tǒng)中就會(huì)出現(xiàn)這種情況。具3、服務(wù)機(jī)制包括：服務(wù)員的數(shù)量及其連接方式（串聯(lián)還是并聯(lián)） 顧客是單個(gè)還是成批接受服務(wù)； 服務(wù)時(shí)間的分布記某服務(wù)臺(tái)的服務(wù)時(shí)間為V，其分布函數(shù)為B(t),密度函數(shù)為b(t),則常見的分布有：定長(zhǎng)分布（D）負(fù)指數(shù)分布（M）K階愛爾朗分布（Ek）2022/12/21213、服務(wù)機(jī)制定長(zhǎng)分布（D）負(fù)指數(shù)分布（M）K階愛爾朗分布（E定長(zhǎng)分布（D）：每個(gè)顧客接受的服務(wù)時(shí)間是一個(gè)確定的常數(shù)。負(fù)指數(shù)分布（M）：每個(gè)顧客接受的服務(wù)時(shí)間相互獨(dú)立，具有相同的負(fù)指數(shù)分布：f(t)=e-tt00t<0其中>0為一常數(shù)。2022/12/2122定長(zhǎng)分布（D）：每個(gè)顧客接受的服務(wù)時(shí)間是一個(gè)確定的常數(shù)。f(K階愛爾朗分布（Ek）：f(t)=k(kt)k-1(K-1)!·e-kt當(dāng)k=1時(shí)即為負(fù)指數(shù)分布；k30,近似于正態(tài)分布;當(dāng)k時(shí)，方差0即為完全非隨機(jī)的。2022/12/2123K階愛爾朗分布（Ek）：f(t)=k(kt)k-1·排隊(duì)系統(tǒng)的符號(hào)表示：“Kendall”記號(hào)：X/Y/Z/W其中：X表示顧客相繼到達(dá)的時(shí)間間隔分布；Y表示服務(wù)時(shí)間的分布；Z表示服務(wù)臺(tái)個(gè)數(shù)；W表示系統(tǒng)的容量，即可容納的最多顧客數(shù)。2022/12/2124排隊(duì)系統(tǒng)的符號(hào)表示：2022/12/1924例1M/M/1/

M表示顧客相繼到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布；M表示服務(wù)時(shí)間為負(fù)指數(shù)分布；單個(gè)服務(wù)臺(tái)；系統(tǒng)容量為無限（等待制）的排隊(duì)模型。例2M/M/S/K顧客到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布；服務(wù)時(shí)間為負(fù)指數(shù)分布；S個(gè)服務(wù)臺(tái)；系統(tǒng)容量為K的排隊(duì)模型。當(dāng)K=S時(shí)為損失制排隊(duì)模型；當(dāng)K=時(shí)為等待制排隊(duì)模型。2022/12/2125例1M/M/1/例2M/M/S/K排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)：系統(tǒng)狀態(tài)：也稱為隊(duì)長(zhǎng)，指排隊(duì)系統(tǒng)中的顧客數(shù)（排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和）。排隊(duì)長(zhǎng)：系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。2022/12/2126排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)：2022/12/1926N(t)：時(shí)刻t(t0)的系統(tǒng)狀態(tài)；pn(t)：時(shí)刻t系統(tǒng)處于狀態(tài)n的概率；S：排隊(duì)系統(tǒng)中并行的服務(wù)臺(tái)數(shù)；n：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，新來的顧客的平均到達(dá)率（單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)）；n：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，整個(gè)系統(tǒng)的平均服務(wù)率（單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)）；2022/12/2127N(t)：時(shí)刻t(t0)的系統(tǒng)狀態(tài)；2022/12/192當(dāng)n為常數(shù)時(shí)記為；（單位時(shí)間內(nèi)到達(dá)的顧客數(shù)） 當(dāng)每個(gè)服務(wù)臺(tái)的平均服務(wù)率為常數(shù)時(shí)，記每個(gè)服務(wù)臺(tái)的服務(wù)率為， 則當(dāng)ns時(shí)，有n=s

（單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)）因此，

顧客相繼到達(dá)的平均時(shí)間間隔為E(T1)=1/，平均服務(wù)時(shí)間為E(T2)=

1/，令=/s，則為系統(tǒng)的服務(wù)強(qiáng)度。2022/12/2128當(dāng)n為常數(shù)時(shí)記為；（單位時(shí)間內(nèi)到達(dá)的顧客數(shù)）2022平穩(wěn)狀態(tài)：pn(t)稱為系統(tǒng)在時(shí)刻t的瞬間分布，一般不容易求得，同時(shí)，由于排隊(duì)系統(tǒng)運(yùn)行一段時(shí)間后，其狀態(tài)和分布都呈現(xiàn)出與初始狀態(tài)或分布無關(guān)的性質(zhì)，稱具有這種性質(zhì)的狀態(tài)或分布為平穩(wěn)狀態(tài)或平穩(wěn)分布。排隊(duì)論一般更注意研究系統(tǒng)在平穩(wěn)狀態(tài)下的性質(zhì)。2022/12/2129平穩(wěn)狀態(tài)：pn(t)稱為系統(tǒng)在時(shí)刻t的瞬間分布，一般不容易求排隊(duì)系統(tǒng)在平穩(wěn)狀態(tài)時(shí)一些基本指標(biāo)：Pn

:系統(tǒng)中恰有n個(gè)顧客的概率；Ls：系統(tǒng)中顧客數(shù)的平均值，又稱為平均隊(duì)長(zhǎng)；Lq：系統(tǒng)中正在排隊(duì)的顧客數(shù)的平均值，又稱為平均排隊(duì)長(zhǎng)；T：顧客在系統(tǒng)中的逗留時(shí)間；Ws=E(T)

：顧客在系統(tǒng)中的平均逗留時(shí)間；Tq：顧客在系統(tǒng)中的排隊(duì)等待時(shí)間；Wq=E(Tq)：顧客在系統(tǒng)中的平均排隊(duì)等待時(shí)間。2022/12/2130排隊(duì)系統(tǒng)在平穩(wěn)狀態(tài)時(shí)一些基本指標(biāo)：Ws=E(T)：顧客在Little公式其中是單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)；是單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)。系統(tǒng)中平均顧客數(shù)=單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)×平均逗留時(shí)間又如果求得Pn,則即可得到。另外1-P0

是系統(tǒng)的忙期概率。2022/12/2131Little公式其中是單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)；系統(tǒng)排隊(duì)論研究的基本問題：通過研究主要數(shù)量指標(biāo)在瞬時(shí)或平穩(wěn)狀態(tài)下的概率分布及數(shù)字特征，了解系統(tǒng)運(yùn)行的基本特征。統(tǒng)計(jì)推斷問題：建立適當(dāng)?shù)呐抨?duì)模型是排隊(duì)論研究的第一步，建立模型過程中，系統(tǒng)是否達(dá)到平穩(wěn)狀態(tài)的檢驗(yàn)；顧客相繼到達(dá)時(shí)間間隔相互獨(dú)立性的檢驗(yàn)，服務(wù)時(shí)間的分布及有關(guān)參數(shù)的確定等。2022/12/2132排隊(duì)論研究的基本問題：2022/12/1932排隊(duì)研究的基本問題：系統(tǒng)優(yōu)化問題：又稱為系統(tǒng)控制問題或系統(tǒng)運(yùn)營(yíng)問題，其基本目的是使系統(tǒng)處于最優(yōu)的或最合理的狀態(tài)。包括：最優(yōu)設(shè)計(jì)問題和最優(yōu)運(yùn)營(yíng)問題。2022/12/2133排隊(duì)研究的基本問題：2022/12/1933§2輸入與服務(wù)時(shí)間的分布一、最簡(jiǎn)單流1、定義;在時(shí)長(zhǎng)為t的時(shí)間段內(nèi)，有k個(gè)顧客到達(dá)的概率服從poisson分布：

t時(shí)段內(nèi)平均到達(dá)顧客數(shù)；

單位時(shí)段內(nèi)平均到達(dá)顧客數(shù)2022/12/2134§2輸入與服務(wù)時(shí)間的分布一、最簡(jiǎn)單流單位時(shí)段內(nèi)平均到達(dá)顧2、最簡(jiǎn)單流的性質(zhì)（1）平穩(wěn)性：在一定時(shí)間間隔內(nèi)，有k個(gè)顧客到達(dá)的概率只與時(shí)長(zhǎng)有關(guān)，與起始時(shí)刻無關(guān)；（2）無后效性：[a,a+t]時(shí)段內(nèi)有k個(gè)顧客到達(dá)的概率與a時(shí)刻之前的客流無關(guān)；（3）普通性：在足夠小的時(shí)段內(nèi)有2個(gè)或個(gè)以上顧客到來的概率為零。說明：1、最簡(jiǎn)單流的性質(zhì)可以簡(jiǎn)化有關(guān)計(jì)算；2、假設(shè)所研究的問題都是最簡(jiǎn)單流，或近似最簡(jiǎn)單流2022/12/21352、最簡(jiǎn)單流的性質(zhì)2022/12/1935二、最簡(jiǎn)單流的有關(guān)計(jì)算1、單位時(shí)間內(nèi)到達(dá)的顧客數(shù)2、內(nèi)沒有顧客到達(dá)的概率3、恰有一個(gè)顧客到達(dá)的概率4、若顧客到達(dá)~poisson分布，則相繼到達(dá)間隔時(shí)間

~負(fù)指數(shù)分布

2022/12/2136二、最簡(jiǎn)單流的有關(guān)計(jì)算2022/12/1936三、服務(wù)時(shí)間設(shè)服務(wù)時(shí)間~負(fù)指數(shù)分布1、單位時(shí)間內(nèi)服務(wù)完畢，離去的顧客數(shù)2、內(nèi)沒有顧客離去的概率3、恰有一個(gè)顧客離去的概率4、若干負(fù)指數(shù)分布的最小值也是負(fù)指數(shù)分說明：服務(wù)機(jī)構(gòu)中有s個(gè)并聯(lián)服務(wù)臺(tái)，各臺(tái)~負(fù)指數(shù)分布，則整個(gè)服務(wù)時(shí)間~負(fù)指數(shù)分布。

2022/12/2137三、服務(wù)時(shí)間2022/12/1937第38頁生滅過程2022/12/2138第38頁生滅過程2022/12/1938第39頁2、t時(shí)刻有n-1個(gè)顧客，時(shí)刻系統(tǒng)中有n個(gè)顧客的概率為1、t時(shí)刻有n個(gè)顧客，時(shí)刻系統(tǒng)中仍有n個(gè)顧客的概率為

時(shí)刻系統(tǒng)中有n個(gè)顧客的概率3、t時(shí)刻有n+1個(gè)顧客，時(shí)刻系統(tǒng)中有n個(gè)顧客的概率為4、t時(shí)刻為n,n-1,n+1個(gè)顧客之外的情況，時(shí)刻系統(tǒng)中有n個(gè)顧客的概率為2022/12/2139第39頁2、t時(shí)刻有n-1個(gè)顧客，時(shí)刻系統(tǒng)中有n個(gè)顧第40頁于是特別的，n=0時(shí)2022/12/2140第40頁于是特別的，n=0時(shí)2022/12/1940第41頁移項(xiàng)求極限，得差分微分方程時(shí),平穩(wěn)狀態(tài)2022/12/2141第41頁移項(xiàng)求極限，得差分微分方程時(shí),平穩(wěn)狀態(tài)2022/12

§4最簡(jiǎn)單的排隊(duì)模型一、M/M/1/模型：

顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)臺(tái)數(shù)為1；系統(tǒng)的空間為無限，允許永遠(yuǎn)排隊(duì)。2022/12/2142§4最簡(jiǎn)單的排隊(duì)模型2022/12/19421、隊(duì)長(zhǎng)的分布記Pn=p{N=n},n=0,1,2….為系統(tǒng)達(dá)到平衡狀態(tài)后隊(duì)長(zhǎng)的概率分布，則n=；n=，=/<1，有Pn=(1-)n,

n=0,1,2….2022/12/21431、隊(duì)長(zhǎng)的分布2022/12/19432、幾個(gè)數(shù)量指標(biāo)平均隊(duì)長(zhǎng)：L=nPn=n(1-)n=

/(1-)=/(-)平均排隊(duì)長(zhǎng)：Lq=(n-1)Pn=2/(1-)=2/(-)2022/12/21442、幾個(gè)數(shù)量指標(biāo)2022/12/1944平均逗留時(shí)間：W=E(T)=1/(-)（little公式)平均等待時(shí)間：Wq=/(-)2022/12/2145平均逗留時(shí)間：2022/12/1945例3：考慮一個(gè)鐵路列車編組站。設(shè)待編列車到達(dá)時(shí)間間隔服從負(fù)指數(shù)分布，平均每小時(shí)到達(dá)2列；服務(wù)臺(tái)是編組站，編組時(shí)間服從負(fù)指數(shù)分布，平均每20分鐘可編一組。已知編組站上共有2股道，當(dāng)均被占用時(shí)，不能接車，再來的列車只能停在站外或前方站。求在平衡狀態(tài)下系統(tǒng)中列車的平均數(shù)；每一列車的平均逗留時(shí)間；等待編組的列車平2022/12/2146例3：考慮一個(gè)鐵路列車編組站。設(shè)待編列車到達(dá)時(shí)間間隔服從負(fù)指均數(shù)。如果列車因站中2股道均被占用而停在站外或前方站時(shí)，每列車每小時(shí)費(fèi)用為a元，求每天由于列車在站外等待而造成的損失。解：本例可看成一個(gè)M/M/1/排隊(duì)問題，其中=2，=3，=/=2/3<1系統(tǒng)中列車的平均數(shù)L=/(1-)=(2/3)/(1-2/3)=2（列）2022/12/2147均數(shù)。如果列車因站中2股道均被占用而停在站外或前方站列車在系統(tǒng)中的平均停留時(shí)間WS=L/=1/(-)=

2/2=1（小時(shí)）系統(tǒng)中等待編組的列車平均數(shù)Lq=L-=/(-)

=2-2/3=4/3（列）列車在系統(tǒng)中的平均等待編組時(shí)間

Wq=Lq/=(4/3)/(1/2)=2/3（小時(shí)）2022/12/2148列車在系統(tǒng)中的平均停留時(shí)間2022/12/1948記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時(shí)間為W0則W0=WSP{N>2}=WS{1-P0-P1-P2}=WS{1-(l-)-(l-)1-(l-)2}=1*3=

3=(2/3)3=0.296（小時(shí)）故每天列車由于等待而支出的平均費(fèi)用E=24W0a=24*2*0.296*a=14.2a元2022/12/2149記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時(shí)間為W0例：某修理店只有一位修理工，來修理的顧客到達(dá)過程為Poisson流，平均每小時(shí)4人；修理時(shí)間服從負(fù)指數(shù)分布，平均需要6分鐘。試求：修理店空閑的概率；店內(nèi)恰有3位顧客的概率；店內(nèi)至少有一位顧客的概率；在店內(nèi)平均顧客數(shù)；每位在店內(nèi)平均逗留時(shí)間；等待服務(wù)的平均顧客數(shù)；每位顧客平均等待服務(wù)時(shí)間；顧客在店內(nèi)時(shí)間超過10分鐘的概率。2022/12/2150例：某修理店只有一位修理工，來修理的顧客到達(dá)過程為Poiss解：本例可看成一個(gè)M/M/1/排隊(duì)問題，其中=4，=1/0.1=10(人/小時(shí)），=/=2/5<1修理店內(nèi)空閑的概率P0=1-=(1-2/5)=0.6店內(nèi)恰有3個(gè)顧客的概率P3=3(1-)=(2/5)3(1-2/5)=0.0382022/12/2151解：本例可看成一個(gè)M/M/1/排隊(duì)問題，其中=4，店內(nèi)至少有1位顧客的概率P{N1}=1-P0=1-

(1-)==2/5=0.4在店內(nèi)平均顧客數(shù)L=/(1-)=(2/5)/(1-2/5)=0.67(人）每位顧客在店內(nèi)平均逗留時(shí)間W=L/=0.67/4=10分鐘2022/12/2152店內(nèi)至少有1位顧客的概率2022/12/1952等待服務(wù)的平均顧客數(shù)Lq=L-=0.67-2/5=0.27(人)每個(gè)顧客平均等待服務(wù)時(shí)間Wq=Lq/=0.27/4=0.0675小時(shí)

=4分鐘2022/12/2153等待服務(wù)的平均顧客數(shù)2022/12/1953顧客在店內(nèi)停留時(shí)間超過10分鐘的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(-)tt=10分鐘,=10人/小時(shí)=10/60=1/6=4人/小時(shí)=4/60=1/152022/12/2154顧客在店內(nèi)停留時(shí)間超過10分鐘的概率2022/12/1954

二、M/M/1/N

模型：

顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)臺(tái)數(shù)為1；系統(tǒng)的空間為有限，最大容量N。2022/12/2155二、M/M/1/N模型：2022/12/19551、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系：012N-1N。。。。。2022/12/21561、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率012N-1N。由及上述差分方程可解得：

單位時(shí)間內(nèi)的平均到達(dá)率

單位時(shí)間內(nèi)的平均有效到達(dá)率

系統(tǒng)中有N個(gè)顧客時(shí)，到達(dá)率為0，只有在少于N個(gè)顧客時(shí)到達(dá)率才有意義。

還可驗(yàn)證

2022/12/2157由及上述差分方程可解得：?jiǎn)挝粫r(shí)間2、系統(tǒng)運(yùn)行指標(biāo)2022/12/21582、系統(tǒng)運(yùn)行指標(biāo)2022/12/1958例、單人理發(fā)店有六張椅子接待客人排隊(duì)理發(fā)，當(dāng)6張椅子坐滿時(shí)，后來的顧客就不進(jìn)店，隨即離開，顧客平均到達(dá)率3人/小時(shí)，理發(fā)平均需時(shí)15分鐘，求：1、求顧客一到達(dá)就能理發(fā)的概率；2、求需要等待的平均顧客數(shù)；3、求有效到達(dá)率；4、每個(gè)顧客的平均逗留時(shí)間；5、在可能到來的顧客中有百分之幾不等待就離開？2022/12/2159例、單人理發(fā)店有六張椅子接待客人排隊(duì)理發(fā)，當(dāng)6張椅子坐滿時(shí)，解、該問題中N=7，1、

2、2022/12/2160解、該問題中2022/12/19603、

4、5.損失率2022/12/21613、2022/12/1961

三、M/M/s/∞

模型：

顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)臺(tái)數(shù)為s；系統(tǒng)的空間為無限2022/12/2162三、M/M/s/∞模型：2022/12/19621、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系：012nn+1。。。n-1nn+1n-12022/12/21631、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率012nn+1。由及上述差分方程可解得：

2022/12/2164由及上述差分方程可解得：20222、系統(tǒng)運(yùn)行指標(biāo)2022/12/21652、系統(tǒng)運(yùn)行指標(biāo)2022/12/1965例、某售票點(diǎn)有三個(gè)窗口，顧客的到達(dá)服從poisson過程，平均到達(dá)率，服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率。

現(xiàn)在假設(shè)顧客到達(dá)后排成一隊(duì)，一次到空閑的窗口買票。分析下列各問題：1、整個(gè)售票點(diǎn)空閑的概率；2、平均排隊(duì)長(zhǎng)；3、平均排隊(duì)時(shí)間；4、顧客到達(dá)后必須等待的概率。2022/12/2166例、某售票點(diǎn)有三個(gè)窗口，顧客的到達(dá)服從poisson過程，解、該問題中s=3，1、

2、3、4、2022/12/2167解、該問題中2022/12/1967

四、M/M/s/N

模型：

顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)臺(tái)數(shù)為s；系統(tǒng)的空間為有限，最多為N2022/12/2168四、M/M/s/N模型：2022/12/19681、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率當(dāng)s=N時(shí)愛爾朗呼喚損失公式2022/12/21691、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率愛爾朗呼喚損失公2、系統(tǒng)運(yùn)行指標(biāo)2022/12/21702、系統(tǒng)運(yùn)行指標(biāo)2022/12/19702022/12/21712022/12/1971

M/M/S等待制排隊(duì)模型多服務(wù)臺(tái)問題，又表示為M/M/S/：顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)臺(tái)數(shù)為S；每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間相互獨(dú)立，且服從參數(shù)為的負(fù)指數(shù)分布。當(dāng)顧客到達(dá)時(shí)，若有空閑服務(wù)臺(tái)馬上被進(jìn)行服務(wù)，否則便排成一隊(duì)列等待，等待空間為無限。2022/12/2172M/M/S等待制排隊(duì)模型2022/12/1972隊(duì)長(zhǎng)的分布記Pn=p{N=n},n=0,1,2….為系統(tǒng)達(dá)到平衡狀態(tài)后隊(duì)長(zhǎng)N的概率分布，對(duì)多服務(wù)臺(tái)有

n=；n=0,1,2….

n=nn=0,1,2….sn=sn=s,s+1,s+2….2022/12/2173隊(duì)長(zhǎng)的分布2022/12/1973s=/s=/s,當(dāng)s<1時(shí)，有Cn=(/)nn!(/)ss!(/s)n-s=(/)n

s!sn-sn=1,2,…..snspn=(p)nn!n=1,2,…..sn

s!sn-snsp0p02022/12/2174s=/s=/s,當(dāng)s<1時(shí)，有C其中：p0=[0s-1pn/n!+s/s!(1-s)]-1當(dāng)ns時(shí)，顧客必須等待，記C(s,)=spn=s/s!(1-s)p0稱為Erlang等待公式，它給出了顧客到達(dá)系統(tǒng)時(shí)，需要等待的概率。2022/12/2175其中：2022/12/1975平均排隊(duì)長(zhǎng)：Lq=s(n-s)pn=p0ss

/s!(1-s)2或Lq

=C(s,)s

/(1-s)記系統(tǒng)中正在接受服務(wù)的顧客平均數(shù)s,顯然s也是正在忙的服務(wù)臺(tái)平均數(shù)。S=0s-1npn+

s*spn=

2022/12/2176平均排隊(duì)長(zhǎng)：2022/12/1976平均隊(duì)長(zhǎng)：L=平均排隊(duì)長(zhǎng)+正在接受服務(wù)的顧客的平均數(shù)=Lq

+對(duì)多服務(wù)臺(tái)，Little公式依然成立：

W=L/Wq=Lq/=W-(1/)2022/12/2177平均隊(duì)長(zhǎng)：2022/12/1977運(yùn)籌學(xué)

OPERATIONSRESEARCH

2022/12/2178運(yùn)籌學(xué)

OPERATIONSRESEARCH

2022/1§1排隊(duì)服務(wù)系統(tǒng)的基本概念

排隊(duì)論是研究排隊(duì)系統(tǒng)（又稱隨機(jī)服務(wù)系統(tǒng)）的數(shù)學(xué)理論和方法，是運(yùn)籌學(xué)的一個(gè)重要分支。

有形排隊(duì)現(xiàn)象：進(jìn)餐館就餐，到圖書館借書，車站等車，去醫(yī)院看病，售票處售票，到工具房領(lǐng)物品等現(xiàn)象。

第十章排隊(duì)論2022/12/2179§1排隊(duì)服務(wù)系統(tǒng)的基本概念第十章排隊(duì)論2022/12/1

無形排隊(duì)現(xiàn)象：如幾個(gè)旅客同時(shí)打電話訂車票；如果有一人正在通話，其他人只得在各自的電話機(jī)前等待，他們分散在不同的地方，形成一個(gè)無形的隊(duì)列在等待通電話。排隊(duì)的不一定是人，也可以是物。如生產(chǎn)線上的原材料，半成品等待加工；因故障而停止運(yùn)行的機(jī)器設(shè)備在等待修理；碼頭上的船只等待裝貨或卸貨；要下降的飛機(jī)因跑道不空而在空中盤旋等。2022/12/2180無形排隊(duì)現(xiàn)象：如幾個(gè)旅客同時(shí)打電話訂車票；如果有一當(dāng)然，進(jìn)行服務(wù)的也不一定是人，可以是跑道，自動(dòng)售貨機(jī)，公共汽車等。顧客——要求服務(wù)的對(duì)象。服務(wù)員——提供服務(wù)的服務(wù)者（也稱服務(wù)機(jī)構(gòu)）。顧客、服務(wù)員的含義是廣義的。2022/12/2181當(dāng)然，進(jìn)行服務(wù)的也不一定是人，可以是跑道，自動(dòng)售貨機(jī)，公共汽隨機(jī)性——顧客到達(dá)情況與顧客接受服務(wù)的時(shí)間是隨機(jī)的。一般來說，排隊(duì)論所研究的排隊(duì)系統(tǒng)中，顧客相繼到達(dá)時(shí)間間隔和服務(wù)時(shí)間這兩個(gè)量中至少有一個(gè)是隨機(jī)的，因此，排隊(duì)論又稱隨機(jī)服務(wù)理論。隨機(jī)服務(wù)理論研究如何合理的設(shè)置服務(wù)系統(tǒng)，更好的為顧客服務(wù)，減少排隊(duì)時(shí)間，同時(shí)又要使得費(fèi)用盡可能節(jié)省。2022/12/2182隨機(jī)性——顧客到達(dá)情況與顧客接受服務(wù)的時(shí)間是隨機(jī)的。2022排隊(duì)系統(tǒng)類型1：服務(wù)臺(tái)顧客到達(dá)服務(wù)完成后離開單服務(wù)臺(tái)排隊(duì)系統(tǒng)2022/12/2183排隊(duì)系統(tǒng)類型1：服務(wù)臺(tái)顧客到達(dá)服務(wù)完成后離開單服務(wù)臺(tái)排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)類型2：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，一個(gè)隊(duì)列的排隊(duì)系統(tǒng)服務(wù)臺(tái)s服務(wù)臺(tái)12022/12/2184排隊(duì)系統(tǒng)類型2：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，一排隊(duì)系統(tǒng)類型3：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，S個(gè)隊(duì)列的排隊(duì)系統(tǒng)服務(wù)臺(tái)s服務(wù)臺(tái)1服務(wù)完成后離開服務(wù)完成后離開2022/12/2185排隊(duì)系統(tǒng)類型3：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，排隊(duì)系統(tǒng)類型4：服務(wù)臺(tái)1顧客到達(dá)離開多服務(wù)臺(tái)串聯(lián)排隊(duì)系統(tǒng)服務(wù)臺(tái)s2022/12/2186排隊(duì)系統(tǒng)類型4：服務(wù)臺(tái)1顧客到達(dá)離開多服務(wù)臺(tái)串聯(lián)排隊(duì)系統(tǒng)服務(wù)排隊(duì)系統(tǒng)的描述

實(shí)際中的排隊(duì)系統(tǒng)各不相同，但概括起來都由三個(gè)基本部分組成：

1、輸入過程;

2、排隊(duì)及排隊(duì)規(guī)則;

3、服務(wù)機(jī)構(gòu)2022/12/2187排隊(duì)系統(tǒng)的描述2022/12/1910

河流上游流入水庫的水量可認(rèn)為是無限的；車間內(nèi)停機(jī)待修的機(jī)器顯然是有限的。到達(dá)方式：是單個(gè)到達(dá)還是成批到達(dá)。

庫存問題中，若把進(jìn)來的貨看成顧客，則為成批到達(dá)的例子。1、輸入過程顧客總體（顧客源）數(shù)：可能是有限，也可能是無限。2022/12/2188河流上游流入水庫的水量可認(rèn)為是無限的；車間內(nèi)停機(jī)待修顧客（單個(gè)或成批）相繼到達(dá)的時(shí)間間隔分布：這是刻劃輸入過程的最重要內(nèi)容。令T0=0，Tn表示第n顧客到達(dá)的時(shí)刻，則有T0T1T2…..Tn……記Xn=Tn–Tn-1n=1,2,…,則Xn是第n顧客與第n-1顧客到達(dá)的時(shí)間間隔。一般假定{Xn}是獨(dú)立同分布，并記分布函數(shù)為A(t)。2022/12/2189顧客（單個(gè)或成批）相繼到達(dá)的時(shí)間間隔分布：這是刻劃輸入過程的{Xn}的分布A(t)常見的有：定長(zhǎng)分布（D）：顧客相繼到達(dá)的時(shí)間間隔為確定的。如產(chǎn)品通過傳送帶進(jìn)入包裝箱就是定常分布。最簡(jiǎn)單流（或稱Poisson)（M）：顧客相繼到達(dá)的時(shí)間間隔{Xn}為獨(dú)立的，同為負(fù)指數(shù)分布，其密度函數(shù)為：f(t)=e-tt00t<02022/12/2190{Xn}的分布A(t)常見的有：f(t)=e-t2、排隊(duì)及排隊(duì)規(guī)則排隊(duì)有限排隊(duì)——排隊(duì)系統(tǒng)中顧客數(shù)是有限的。（損失制排隊(duì)系統(tǒng)，混合制排隊(duì)系統(tǒng)）無限排隊(duì)——顧客數(shù)是無限，隊(duì)列可以排到無限長(zhǎng)（等待制排隊(duì)系統(tǒng)）。2022/12/21912、排隊(duì)及排隊(duì)規(guī)則2022/12/1914有限排隊(duì)還可以分成：損失制排隊(duì)系統(tǒng)：排隊(duì)空間為零的系統(tǒng)，即不允許排隊(duì)。（顧客到達(dá)時(shí)，服務(wù)臺(tái)占滿，顧客自動(dòng)離開，不再回來）（電話系統(tǒng)）混合制排隊(duì)系統(tǒng)：是等待制與損失制結(jié)合，即允許排隊(duì)，但不允許隊(duì)列無限長(zhǎng)。2022/12/2192有限排隊(duì)還可以分成：2022/12/1915混合制排隊(duì)系統(tǒng)：1.隊(duì)長(zhǎng)有限,即系統(tǒng)等待空間是有限的。例：最多只能容納K個(gè)顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時(shí)，若系統(tǒng)中的顧客數(shù)（又稱為隊(duì)長(zhǎng)）小于K，則可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。2022/12/2193混合制排隊(duì)系統(tǒng)：2022/12/19162.等待時(shí)間有限。即顧客在系統(tǒng)中等待時(shí)間不超過某一給定的長(zhǎng)度T，當(dāng)?shù)却龝r(shí)間超過T時(shí)，顧客將自動(dòng)離開，不再回來。如:易損失的電子元件的庫存問題，超過一定存儲(chǔ)時(shí)間的元器件被自動(dòng)認(rèn)為失效?；旌现婆抨?duì)系統(tǒng)：3.逗留時(shí)間（等待時(shí)間與服務(wù)時(shí)間之和）有限。例：用高射炮射擊飛機(jī)，當(dāng)敵機(jī)飛越射擊有效區(qū)域的時(shí)間為t時(shí)，若這個(gè)時(shí)間內(nèi)未被擊落，也就不可能再被擊落了。2022/12/21942.等待時(shí)間有限。即顧客在系統(tǒng)中等待時(shí)間不超過某一給定的長(zhǎng)說明：損失制和等待制可看成是混合制的特殊情形.如:記s為系統(tǒng)中服務(wù)臺(tái)個(gè)數(shù)，則當(dāng)k=s時(shí)，混合制即為損失制；當(dāng)k=時(shí)，即成為等待制。2022/12/2195說明：損失制和等待制可看成是混合制的特殊情形.2022/12排隊(duì)規(guī)則當(dāng)顧客到達(dá)時(shí)，若所有服務(wù)臺(tái)都被占有且又允許排隊(duì)，則該顧客將進(jìn)入隊(duì)列等待。服務(wù)臺(tái)對(duì)顧客進(jìn)行服務(wù)所遵循的規(guī)則通常有：先來先服務(wù)（FCFS）2022/12/2196排隊(duì)規(guī)則2022/12/1919后來先服務(wù)（LCFS）。在許多庫存系統(tǒng)中就會(huì)出現(xiàn)這種情況。如：鋼板存入倉庫后，需要時(shí)總是從最上面取出；又如在情報(bào)系統(tǒng)中，后來到達(dá)的信息往往更重要，首先要加以分析和利用。具有優(yōu)先權(quán)的服務(wù)（PS）。服務(wù)臺(tái)根據(jù)顧客的優(yōu)先權(quán)的不同進(jìn)行服務(wù)。如：病危的病人應(yīng)優(yōu)先治療；重要的信息應(yīng)優(yōu)先處理；出價(jià)高的顧客應(yīng)優(yōu)先考慮。2022/12/2197后來先服務(wù)（LCFS）。在許多庫存系統(tǒng)中就會(huì)出現(xiàn)這種情況。具3、服務(wù)機(jī)制包括：服務(wù)員的數(shù)量及其連接方式（串聯(lián)還是并聯(lián)） 顧客是單個(gè)還是成批接受服務(wù)； 服務(wù)時(shí)間的分布記某服務(wù)臺(tái)的服務(wù)時(shí)間為V，其分布函數(shù)為B(t),密度函數(shù)為b(t),則常見的分布有：定長(zhǎng)分布（D）負(fù)指數(shù)分布（M）K階愛爾朗分布（Ek）2022/12/21983、服務(wù)機(jī)制定長(zhǎng)分布（D）負(fù)指數(shù)分布（M）K階愛爾朗分布（E定長(zhǎng)分布（D）：每個(gè)顧客接受的服務(wù)時(shí)間是一個(gè)確定的常數(shù)。負(fù)指數(shù)分布（M）：每個(gè)顧客接受的服務(wù)時(shí)間相互獨(dú)立，具有相同的負(fù)指數(shù)分布：f(t)=e-tt00t<0其中>0為一常數(shù)。2022/12/2199定長(zhǎng)分布（D）：每個(gè)顧客接受的服務(wù)時(shí)間是一個(gè)確定的常數(shù)。f(K階愛爾朗分布（Ek）：f(t)=k(kt)k-1(K-1)!·e-kt當(dāng)k=1時(shí)即為負(fù)指數(shù)分布；k30,近似于正態(tài)分布;當(dāng)k時(shí)，方差0即為完全非隨機(jī)的。2022/12/21100K階愛爾朗分布（Ek）：f(t)=k(kt)k-1·排隊(duì)系統(tǒng)的符號(hào)表示：“Kendall”記號(hào)：X/Y/Z/W其中：X表示顧客相繼到達(dá)的時(shí)間間隔分布；Y表示服務(wù)時(shí)間的分布；Z表示服務(wù)臺(tái)個(gè)數(shù)；W表示系統(tǒng)的容量，即可容納的最多顧客數(shù)。2022/12/21101排隊(duì)系統(tǒng)的符號(hào)表示：2022/12/1924例1M/M/1/

M表示顧客相繼到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布；M表示服務(wù)時(shí)間為負(fù)指數(shù)分布；單個(gè)服務(wù)臺(tái)；系統(tǒng)容量為無限（等待制）的排隊(duì)模型。例2M/M/S/K顧客到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布；服務(wù)時(shí)間為負(fù)指數(shù)分布；S個(gè)服務(wù)臺(tái)；系統(tǒng)容量為K的排隊(duì)模型。當(dāng)K=S時(shí)為損失制排隊(duì)模型；當(dāng)K=時(shí)為等待制排隊(duì)模型。2022/12/21102例1M/M/1/例2M/M/S/K排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)：系統(tǒng)狀態(tài)：也稱為隊(duì)長(zhǎng)，指排隊(duì)系統(tǒng)中的顧客數(shù)（排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和）。排隊(duì)長(zhǎng)：系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。2022/12/21103排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)：2022/12/1926N(t)：時(shí)刻t(t0)的系統(tǒng)狀態(tài)；pn(t)：時(shí)刻t系統(tǒng)處于狀態(tài)n的概率；S：排隊(duì)系統(tǒng)中并行的服務(wù)臺(tái)數(shù)；n：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，新來的顧客的平均到達(dá)率（單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)）；n：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，整個(gè)系統(tǒng)的平均服務(wù)率（單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)）；2022/12/21104N(t)：時(shí)刻t(t0)的系統(tǒng)狀態(tài)；2022/12/192當(dāng)n為常數(shù)時(shí)記為；（單位時(shí)間內(nèi)到達(dá)的顧客數(shù)） 當(dāng)每個(gè)服務(wù)臺(tái)的平均服務(wù)率為常數(shù)時(shí)，記每個(gè)服務(wù)臺(tái)的服務(wù)率為， 則當(dāng)ns時(shí)，有n=s

（單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)）因此，

顧客相繼到達(dá)的平均時(shí)間間隔為E(T1)=1/，平均服務(wù)時(shí)間為E(T2)=

1/，令=/s，則為系統(tǒng)的服務(wù)強(qiáng)度。2022/12/21105當(dāng)n為常數(shù)時(shí)記為；（單位時(shí)間內(nèi)到達(dá)的顧客數(shù)）2022平穩(wěn)狀態(tài)：pn(t)稱為系統(tǒng)在時(shí)刻t的瞬間分布，一般不容易求得，同時(shí)，由于排隊(duì)系統(tǒng)運(yùn)行一段時(shí)間后，其狀態(tài)和分布都呈現(xiàn)出與初始狀態(tài)或分布無關(guān)的性質(zhì)，稱具有這種性質(zhì)的狀態(tài)或分布為平穩(wěn)狀態(tài)或平穩(wěn)分布。排隊(duì)論一般更注意研究系統(tǒng)在平穩(wěn)狀態(tài)下的性質(zhì)。2022/12/21106平穩(wěn)狀態(tài)：pn(t)稱為系統(tǒng)在時(shí)刻t的瞬間分布，一般不容易求排隊(duì)系統(tǒng)在平穩(wěn)狀態(tài)時(shí)一些基本指標(biāo)：Pn

:系統(tǒng)中恰有n個(gè)顧客的概率；Ls：系統(tǒng)中顧客數(shù)的平均值，又稱為平均隊(duì)長(zhǎng)；Lq：系統(tǒng)中正在排隊(duì)的顧客數(shù)的平均值，又稱為平均排隊(duì)長(zhǎng)；T：顧客在系統(tǒng)中的逗留時(shí)間；Ws=E(T)

：顧客在系統(tǒng)中的平均逗留時(shí)間；Tq：顧客在系統(tǒng)中的排隊(duì)等待時(shí)間；Wq=E(Tq)：顧客在系統(tǒng)中的平均排隊(duì)等待時(shí)間。2022/12/21107排隊(duì)系統(tǒng)在平穩(wěn)狀態(tài)時(shí)一些基本指標(biāo)：Ws=E(T)：顧客在Little公式其中是單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)；是單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)。系統(tǒng)中平均顧客數(shù)=單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)×平均逗留時(shí)間又如果求得Pn,則即可得到。另外1-P0

是系統(tǒng)的忙期概率。2022/12/21108Little公式其中是單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)；系統(tǒng)排隊(duì)論研究的基本問題：通過研究主要數(shù)量指標(biāo)在瞬時(shí)或平穩(wěn)狀態(tài)下的概率分布及數(shù)字特征，了解系統(tǒng)運(yùn)行的基本特征。統(tǒng)計(jì)推斷問題：建立適當(dāng)?shù)呐抨?duì)模型是排隊(duì)論研究的第一步，建立模型過程中，系統(tǒng)是否達(dá)到平穩(wěn)狀態(tài)的檢驗(yàn)；顧客相繼到達(dá)時(shí)間間隔相互獨(dú)立性的檢驗(yàn)，服務(wù)時(shí)間的分布及有關(guān)參數(shù)的確定等。2022/12/21109排隊(duì)論研究的基本問題：2022/12/1932排隊(duì)研究的基本問題：系統(tǒng)優(yōu)化問題：又稱為系統(tǒng)控制問題或系統(tǒng)運(yùn)營(yíng)問題，其基本目的是使系統(tǒng)處于最優(yōu)的或最合理的狀態(tài)。包括：最優(yōu)設(shè)計(jì)問題和最優(yōu)運(yùn)營(yíng)問題。2022/12/21110排隊(duì)研究的基本問題：2022/12/1933§2輸入與服務(wù)時(shí)間的分布一、最簡(jiǎn)單流1、定義;在時(shí)長(zhǎng)為t的時(shí)間段內(nèi)，有k個(gè)顧客到達(dá)的概率服從poisson分布：

t時(shí)段內(nèi)平均到達(dá)顧客數(shù)；

單位時(shí)段內(nèi)平均到達(dá)顧客數(shù)2022/12/21111§2輸入與服務(wù)時(shí)間的分布一、最簡(jiǎn)單流單位時(shí)段內(nèi)平均到達(dá)顧2、最簡(jiǎn)單流的性質(zhì)（1）平穩(wěn)性：在一定時(shí)間間隔內(nèi)，有k個(gè)顧客到達(dá)的概率只與時(shí)長(zhǎng)有關(guān)，與起始時(shí)刻無關(guān)；（2）無后效性：[a,a+t]時(shí)段內(nèi)有k個(gè)顧客到達(dá)的概率與a時(shí)刻之前的客流無關(guān)；（3）普通性：在足夠小的時(shí)段內(nèi)有2個(gè)或個(gè)以上顧客到來的概率為零。說明：1、最簡(jiǎn)單流的性質(zhì)可以簡(jiǎn)化有關(guān)計(jì)算；2、假設(shè)所研究的問題都是最簡(jiǎn)單流，或近似最簡(jiǎn)單流2022/12/211122、最簡(jiǎn)單流的性質(zhì)2022/12/1935二、最簡(jiǎn)單流的有關(guān)計(jì)算1、單位時(shí)間內(nèi)到達(dá)的顧客數(shù)2、內(nèi)沒有顧客到達(dá)的概率3、恰有一個(gè)顧客到達(dá)的概率4、若顧客到達(dá)~poisson分布，則相繼到達(dá)間隔時(shí)間

~負(fù)指數(shù)分布

2022/12/21113二、最簡(jiǎn)單流的有關(guān)計(jì)算2022/12/1936三、服務(wù)時(shí)間設(shè)服務(wù)時(shí)間~負(fù)指數(shù)分布1、單位時(shí)間內(nèi)服務(wù)完畢，離去的顧客數(shù)2、內(nèi)沒有顧客離去的概率3、恰有一個(gè)顧客離去的概率4、若干負(fù)指數(shù)分布的最小值也是負(fù)指數(shù)分說明：服務(wù)機(jī)構(gòu)中有s個(gè)并聯(lián)服務(wù)臺(tái)，各臺(tái)~負(fù)指數(shù)分布，則整個(gè)服務(wù)時(shí)間~負(fù)指數(shù)分布。

2022/12/21114三、服務(wù)時(shí)間2022/12/1937第115頁生滅過程2022/12/21115第38頁生滅過程2022/12/1938第116頁2、t時(shí)刻有n-1個(gè)顧客，時(shí)刻系統(tǒng)中有n個(gè)顧客的概率為1、t時(shí)刻有n個(gè)顧客，時(shí)刻系統(tǒng)中仍有n個(gè)顧客的概率為

時(shí)刻系統(tǒng)中有n個(gè)顧客的概率3、t時(shí)刻有n+1個(gè)顧客，時(shí)刻系統(tǒng)中有n個(gè)顧客的概率為4、t時(shí)刻為n,n-1,n+1個(gè)顧客之外的情況，時(shí)刻系統(tǒng)中有n個(gè)顧客的概率為2022/12/21116第39頁2、t時(shí)刻有n-1個(gè)顧客，時(shí)刻系統(tǒng)中有n個(gè)顧第117頁于是特別的，n=0時(shí)2022/12/21117第40頁于是特別的，n=0時(shí)2022/12/1940第118頁移項(xiàng)求極限，得差分微分方程時(shí),平穩(wěn)狀態(tài)2022/12/21118第41頁移項(xiàng)求極限，得差分微分方程時(shí),平穩(wěn)狀態(tài)2022/12

§4最簡(jiǎn)單的排隊(duì)模型一、M/M/1/模型：

顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)臺(tái)數(shù)為1；系統(tǒng)的空間為無限，允許永遠(yuǎn)排隊(duì)。2022/12/21119§4最簡(jiǎn)單的排隊(duì)模型2022/12/19421、隊(duì)長(zhǎng)的分布記Pn=p{N=n},n=0,1,2….為系統(tǒng)達(dá)到平衡狀態(tài)后隊(duì)長(zhǎng)的概率分布，則n=；n=，=/<1，有Pn=(1-)n,

n=0,1,2….2022/12/211201、隊(duì)長(zhǎng)的分布2022/12/19432、幾個(gè)數(shù)量指標(biāo)平均隊(duì)長(zhǎng)：L=nPn=n(1-)n=

/(1-)=/(-)平均排隊(duì)長(zhǎng)：Lq=(n-1)Pn=2/(1-)=2/(-)2022/12/211212、幾個(gè)數(shù)量指標(biāo)2022/12/1944平均逗留時(shí)間：W=E(T)=1/(-)（little公式)平均等待時(shí)間：Wq=/(-)2022/12/21122平均逗留時(shí)間：2022/12/1945例3：考慮一個(gè)鐵路列車編組站。設(shè)待編列車到達(dá)時(shí)間間隔服從負(fù)指數(shù)分布，平均每小時(shí)到達(dá)2列；服務(wù)臺(tái)是編組站，編組時(shí)間服從負(fù)指數(shù)分布，平均每20分鐘可編一組。已知編組站上共有2股道，當(dāng)均被占用時(shí)，不能接車，再來的列車只能停在站外或前方站。求在平衡狀態(tài)下系統(tǒng)中列車的平均數(shù)；每一列車的平均逗留時(shí)間；等待編組的列車平2022/12/21123例3：考慮一個(gè)鐵路列車編組站。設(shè)待編列車到達(dá)時(shí)間間隔服從負(fù)指均數(shù)。如果列車因站中2股道均被占用而停在站外或前方站時(shí)，每列車每小時(shí)費(fèi)用為a元，求每天由于列車在站外等待而造成的損失。解：本例可看成一個(gè)M/M/1/排隊(duì)問題，其中=2，=3，=/=2/3<1系統(tǒng)中列車的平均數(shù)L=/(1-)=(2/3)/(1-2/3)=2（列）2022/12/21124均數(shù)。如果列車因站中2股道均被占用而停在站外或前方站列車在系統(tǒng)中的平均停留時(shí)間WS=L/=1/(-)=

2/2=1（小時(shí)）系統(tǒng)中等待編組的列車平均數(shù)Lq=L-=/(-)

=2-2/3=4/3（列）列車在系統(tǒng)中的平均等待編組時(shí)間

Wq=Lq/=(4/3)/(1/2)=2/3（小時(shí)）2022/12/21125列車在系統(tǒng)中的平均停留時(shí)間2022/12/1948記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時(shí)間為W0則W0=WSP{N>2}=WS{1-P0-P1-P2}=WS{1-(l-)-(l-)1-(l-)2}=1*3=

3=(2/3)3=0.296（小時(shí)）故每天列車由于等待而支出的平均費(fèi)用E=24W0a=24*2*0.296*a=14.2a元2022/12/21126記列車平均延誤（由于站內(nèi)2股道均被占用而不能進(jìn)站）時(shí)間為W0例：某修理店只有一位修理工，來修理的顧客到達(dá)過程為Poisson流，平均每小時(shí)4人；修理時(shí)間服從負(fù)指數(shù)分布，平均需要6分鐘。試求：修理店空閑的概率；店內(nèi)恰有3位顧客的概率；店內(nèi)至少有一位顧客的概率；在店內(nèi)平均顧客數(shù)；每位在店內(nèi)平均逗留時(shí)間；等待服務(wù)的平均顧客數(shù)；每位顧客平均等待服務(wù)時(shí)間；顧客在店內(nèi)時(shí)間超過10分鐘的概率。2022/12/21127例：某修理店只有一位修理工，來修理的顧客到達(dá)過程為Poiss解：本例可看成一個(gè)M/M/1/排隊(duì)問題，其中=4，=1/0.1=10(人/小時(shí)），=/=2/5<1修理店內(nèi)空閑的概率P0=1-=(1-2/5)=0.6店內(nèi)恰有3個(gè)顧客的概率P3=3(1-)=(2/5)3(1-2/5)=0.0382022/12/21128解：本例可看成一個(gè)M/M/1/排隊(duì)問題，其中=4，店內(nèi)至少有1位顧客的概率P{N1}=1-P0=1-

(1-)==2/5=0.4在店內(nèi)平均顧客數(shù)L=/(1-)=(2/5)/(1-2/5)=0.67(人）每位顧客在店內(nèi)平均逗留時(shí)間W=L/=0.67/4=10分鐘2022/12/21129店內(nèi)至少有1位顧客的概率2022/12/1952等待服務(wù)的平均顧客數(shù)Lq=L-=0.67-2/5=0.27(人)每個(gè)顧客平均等待服務(wù)時(shí)間Wq=Lq/=0.27/4=0.0675小時(shí)

=4分鐘2022/12/21130等待服務(wù)的平均顧客數(shù)2022/12/1953顧客在店內(nèi)停留時(shí)間超過10分鐘的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(-)tt=10分鐘,=10人/小時(shí)=10/60=1/6=4人/小時(shí)=4/60=1/152022/12/21131顧客在店內(nèi)停留時(shí)間超過10分鐘的概率2022/12/1954

二、M/M/1/N

模型：

顧客相繼到達(dá)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布；服務(wù)臺(tái)數(shù)為1；系統(tǒng)的空間為有限，最大容量N。2022/12/21132二、M/M/1/N模型：2022/12/19551、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系：012N-1N。。。。。2022/12/211331、穩(wěn)定狀態(tài)下，系統(tǒng)中有n個(gè)顧客的概率012N-1N。由及上述差分方程可解得：

單位時(shí)間內(nèi)的平均到達(dá)率

單位時(shí)間內(nèi)的平均有效到達(dá)率

系統(tǒng)中有N個(gè)顧客時(shí)，到達(dá)率為0，只有在少于N個(gè)顧客時(shí)到達(dá)率才有意義。

還可驗(yàn)證

2022/12/21134由及上述差分方程可解得：?jiǎn)挝粫r(shí)間2、系統(tǒng)運(yùn)行指標(biāo)2022/12/211352、系統(tǒng)運(yùn)行指標(biāo)2022/12/1958例、單人理發(fā)店有六張椅子接待客人排隊(duì)理發(fā)，當(dāng)6張椅子坐滿時(shí)，后來的顧客就不進(jìn)店，隨即離開，顧客平均到達(dá)率3人/小時(shí)，理發(fā)平均需時(shí)15分鐘，求：1、求顧客一到達(dá)就能理發(fā)的概率；