運(yùn)籌學(xué)第三排隊(duì)論P(yáng)PT課件

1、1排隊(duì)論第1節(jié) 基本概念第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第3節(jié) 單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第4節(jié) 多服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第5節(jié) 一般服務(wù)時(shí)間M/G/1模型第6節(jié) 經(jīng)濟(jì)分析系統(tǒng)的最優(yōu)化第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法第1頁/共188頁2第1節(jié) 基 本 概 念 1.1 排隊(duì)過程的一般表示 1.2 排隊(duì)系統(tǒng)的組織和特征 1.3 排隊(duì)模型的分類 1.4 排隊(duì)問題的求解第2頁/共188頁3 不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊(duì)等待，則加入隊(duì)列排隊(duì)等待接受服務(wù)，然后服務(wù)臺(tái)按一定規(guī)則從隊(duì)列中選擇顧客進(jìn)行服務(wù)，獲得服務(wù)的

2、顧客立即離開系統(tǒng)。1.1 排隊(duì)過程的一般表示第3頁/共188頁41.1 排隊(duì)過程的一般表示 各個(gè)顧客由顧客源(總體)出發(fā)，到達(dá)服務(wù)機(jī)構(gòu)(服務(wù)臺(tái)、服務(wù)員)前排隊(duì)等候接受服務(wù)，服務(wù)完成后離開。 排隊(duì)結(jié)構(gòu)指隊(duì)列的數(shù)目和排列方式，排隊(duì)規(guī)則和服務(wù)規(guī)則是說明顧客在排隊(duì)系統(tǒng)中按怎樣的規(guī)則、次序接受服務(wù)的。排隊(duì)過程的一般模型排隊(duì)過程的一般模型第4頁/共188頁51.1 排隊(duì)過程的一般表示到達(dá)的顧客到達(dá)的顧客要求服務(wù)內(nèi)容要求服務(wù)內(nèi)容服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)1.不能運(yùn)轉(zhuǎn)的機(jī)器2.修理技工3.病人4.電話呼喚5.文件稿6.提貨單7.到達(dá)機(jī)場上空的飛機(jī)8.駛?cè)敫劭诘呢洿?.上游河水進(jìn)入水庫10.進(jìn)入我方陣地的敵機(jī)修理領(lǐng)取修配

3、零件診斷或動(dòng)手術(shù)通話打字提取存貨降落裝(卸)貨裝(卸)放水，調(diào)整水位我方高射炮進(jìn)行射擊修理技工發(fā)放修配零件的管理員醫(yī)生(或包括手術(shù)臺(tái))交換臺(tái)打字員倉庫管理員跑道貨碼頭(泊位)水閘管理員我方高射炮形形色色的排隊(duì)系統(tǒng) 第5頁/共188頁6 實(shí)際的排隊(duì)系統(tǒng)雖然千差萬別，但是它們有以下的共同特征： (1)有請求服務(wù)的人或物顧客； (2)有為顧客服務(wù)的人或物，即服務(wù)員或服務(wù)臺(tái)； (3)顧客到達(dá)系統(tǒng)的時(shí)刻是隨機(jī)的，為每一位顧客提供服務(wù)的時(shí)間是隨機(jī)的，因而整個(gè)排隊(duì)系統(tǒng)的狀態(tài)也是隨機(jī)的。排隊(duì)系統(tǒng)的這種隨機(jī)性造成某個(gè)階段顧客排隊(duì)較長，而另外一些時(shí)候服務(wù)員(臺(tái))又空閑無事。1.2 排隊(duì)系統(tǒng)的組成和特征 第6頁/共

4、188頁71.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)系統(tǒng)由三個(gè)基本部分組成： 輸入過程 排隊(duì)規(guī)則 服務(wù)機(jī)構(gòu)第7頁/共188頁81.2 排隊(duì)系統(tǒng)的組成和特征 輸入過程 輸入即指顧客到達(dá)排隊(duì)系統(tǒng)。輸入過程是指要求服務(wù)的顧客是按怎樣的規(guī)律到達(dá)排隊(duì)系統(tǒng)的過程，有時(shí)也把它稱為顧客流。 一般可以從以下幾個(gè)方面來描述個(gè)輸入過程(1) 顧客的總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。 顧客源可以是有限的，也可以是無限的。 例如，到售票處購票的顧客總數(shù)可以認(rèn)為是無限的；上游河水流入 水庫可以認(rèn)為顧客總體是無限的 例如，某個(gè)工廠因故障待修的機(jī)床則是有限的。第8頁/共188頁91.2 排隊(duì)系統(tǒng)的組成和特征 輸入過程(2

5、) 顧客到來的方式。這是描述顧客是怎樣來到系統(tǒng)的，他們是單個(gè)到達(dá)，還是成批到達(dá)。 病人到醫(yī)院看病是顧客單個(gè)到達(dá)的例子。 在庫存問題中如將生產(chǎn)器材進(jìn)貨或產(chǎn)品入庫看作是顧客，那么這種顧客則是成批到達(dá)的。第9頁/共188頁101.2 排隊(duì)系統(tǒng)的組成和特征 輸入過程(3)顧客流的概率分布，或稱相繼顧客到達(dá)的時(shí)間間隔的分布。這是求解排隊(duì)系統(tǒng)有關(guān)運(yùn)行指標(biāo)問題時(shí)，首先需要確定的指標(biāo)。這也可以理解為在一定的時(shí)間間隔內(nèi)到達(dá)K個(gè)顧客(K=1、2、)的概率是多大。 顧客相繼到達(dá)的間隔時(shí)間可以是確定型的，也可以是隨機(jī)型的。例如：在流水線上裝配的各部件必須按確定的時(shí)間間隔到達(dá)裝配點(diǎn)，定點(diǎn)運(yùn)行的列車、班機(jī)的到達(dá)也都是確定

6、的；例如：物流配送等待的顧客、辦理出關(guān)手續(xù)的顧客、通過路口的車輛的到達(dá)都是隨機(jī)的。第10頁/共188頁111.2 排隊(duì)系統(tǒng)的組成和特征 輸入過程 對于隨機(jī)的情形，必須了解單位時(shí)間的顧客到達(dá)數(shù)或相繼到達(dá)的時(shí)間間隔的概率分布。 顧客流的概率分布一般有定長分布、二項(xiàng)分布、泊松流(最簡單流)、愛爾朗分布等若干種。第11頁/共188頁121.2 排隊(duì)系統(tǒng)的組成和特征 輸入過程(4) 顧客的到達(dá)可以是相互獨(dú)立的。(5) 輸入過程可以是平穩(wěn)的，或稱對時(shí)間是齊次的，即描述相繼到達(dá)的間隔時(shí)間分布和所含參數(shù)(如期望值、方差等)都是與時(shí)間無關(guān)的。第12頁/共188頁131.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 這是指

7、服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序。一般可以分為損失制、等待制和混合制等3大類。 (1)損失制。這是指如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都已被先來的顧客占用，那么他們就自動(dòng)離開系統(tǒng)永不再來。 例如：電話拔號(hào)后出現(xiàn)忙音，顧客不愿等待而自動(dòng)掛斷電話，如要再打，就需重新拔號(hào)，這種服務(wù)規(guī)則即為損失制。 第13頁/共188頁141.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 (2)等待制。這是指當(dāng)顧客來到系統(tǒng)時(shí)，所有服務(wù)臺(tái)都不空，顧客加入排隊(duì)行列等待服務(wù)。 例如：排隊(duì)等待售票，故障設(shè)備等待維修等。 對于等待制，為顧客進(jìn)行服務(wù)的次序可以采用下列各種規(guī)則： 先到先服務(wù)(FCFS) 后到先服務(wù)(LCFS) 隨機(jī)服務(wù)

8、(RS) 有優(yōu)先權(quán)的服務(wù)第14頁/共188頁151.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 (2)等待制（續(xù)）。 先到先服務(wù)。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。 后到先服務(wù)。 例如：倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走。 隨機(jī)服務(wù)。即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)。 例如：電話交換臺(tái)接通呼叫電話。 優(yōu)先權(quán)服務(wù)。 例如：老人、兒童先進(jìn)車站； 危重病員先就診； 遇到重要數(shù)據(jù)需要處理計(jì)算機(jī)立即中斷其他數(shù)據(jù)的處理等。第15頁/共188頁161.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 (3)混合制這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是指允許排隊(duì)，但又不

9、允許隊(duì)列無限長下去。具體說來，大致有三種： 隊(duì)長有限。 等待時(shí)間有限。 逗留時(shí)間有限。第16頁/共188頁171.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 (3)混合制 隊(duì)長有限。當(dāng)排隊(duì)等待服務(wù)的顧客人數(shù)超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。 具體地，最多只能容納K個(gè)顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時(shí)，若系統(tǒng)中的顧客數(shù)(又稱為隊(duì)長)小于K，則可進(jìn)入系統(tǒng)排隊(duì)或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。 例如：水庫的庫容是有限的，旅館的床位是有限的。第17頁/共188頁181.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 (3)混合制 隊(duì)長有限。 等待時(shí)間有限。即顧客在系統(tǒng)中的等待時(shí)間

10、不超過某一給定的長度T，當(dāng)?shù)却龝r(shí)間超過T時(shí)，顧客將自動(dòng)離去，并不再回來。 例如：易損壞的電子元器件的庫存問題，超過一定存儲(chǔ)時(shí)間的元器件被自動(dòng)認(rèn)為失效。 例如：顧客到飯館就餐，等了一定時(shí)間后不愿再等而自動(dòng)離去另找飯店用餐。第18頁/共188頁191.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 (3)混合制 隊(duì)長有限。 等待時(shí)間有限。 逗留時(shí)間(等待時(shí)間與服務(wù)時(shí)間之和)有限。 例如：用高射炮射擊敵機(jī)，當(dāng)敵機(jī)飛越高射炮射擊有效區(qū)域的時(shí)間為t時(shí)，若在這個(gè)時(shí)間內(nèi)未被擊落，也就不可能再被擊落了。 不難注意到，損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務(wù)臺(tái)的個(gè)數(shù)，則當(dāng)K=s時(shí)，混合制即成為損失制；當(dāng)K

11、=時(shí)，混合制即成為等待制。第19頁/共188頁201.2 排隊(duì)系統(tǒng)的組成和特征 排隊(duì)規(guī)則 （續(xù)） 從允許排隊(duì)的空間看 隊(duì)列可以排在具體的處所，也可以是抽象的。 排隊(duì)空間可以有限，也可以無限。 從排隊(duì)的隊(duì)列數(shù)目看，可以是單列，也可以是多列。 在多列的情形，各列間的顧客有的可以互相轉(zhuǎn)移，有的不能。 有的排隊(duì)顧客因等候時(shí)間過長而中途退出，有的不能退出，必須堅(jiān)持到被服務(wù)為止。第20頁/共188頁211.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)服務(wù)臺(tái)可以從以下3方面來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。服務(wù)機(jī)構(gòu)可以沒有服務(wù)員，也可以有一個(gè)或多個(gè)服務(wù)員(服務(wù)臺(tái)、通道、窗口等)。從數(shù)量上說，服務(wù)臺(tái)

12、有單服務(wù)臺(tái)和多服務(wù)臺(tái)之分。在有多個(gè)服務(wù)臺(tái)的情形中，可以是平行排列的，也可以是前后排列的，或混合排列的。第21頁/共188頁221.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)服務(wù)臺(tái)可以從以下3方面來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺(tái)有： 單隊(duì)單服務(wù)臺(tái)式；如(a)圖 單隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(c)圖 服務(wù)臺(tái)的各服務(wù)臺(tái)的各種排列方式種排列方式第22頁/共188頁231.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)服務(wù)臺(tái)可以從以下3方面來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺(tái)有： 單隊(duì)單服務(wù)臺(tái)式；如(a)圖 單隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(c)圖 多隊(duì)多

13、服務(wù)臺(tái)并聯(lián)式；如(b)圖 服務(wù)臺(tái)的各服務(wù)臺(tái)的各種排列方式種排列方式第23頁/共188頁241.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)服務(wù)臺(tái)可以從以下3方面來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺(tái)有： 單隊(duì)單服務(wù)臺(tái)式；如(a)圖 單隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(c)圖 多隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(b)圖 單隊(duì)多服務(wù)臺(tái)串聯(lián)式；如(d)圖 服務(wù)臺(tái)的各服務(wù)臺(tái)的各種排列方式種排列方式第24頁/共188頁251.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)服務(wù)臺(tái)可以從以下3方面來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺(tái)有： 單隊(duì)單服務(wù)臺(tái)式；如(a)圖 單隊(duì)多服務(wù)

14、臺(tái)并聯(lián)式；如(c)圖 多隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(b)圖 單隊(duì)多服務(wù)臺(tái)串聯(lián)式；如(d)圖 單隊(duì)多服務(wù)臺(tái)并串聯(lián)混合式； 服務(wù)臺(tái)的各服務(wù)臺(tái)的各種排列方式種排列方式第25頁/共188頁261.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)服務(wù)臺(tái)可以從以下3方面來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺(tái)有： 單隊(duì)單服務(wù)臺(tái)式；如(a)圖 單隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(c)圖 多隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(b)圖 單隊(duì)多服務(wù)臺(tái)串聯(lián)式；如(d)圖 單隊(duì)多服務(wù)臺(tái)并串聯(lián)混合式； 多隊(duì)多服務(wù)臺(tái)并串聯(lián)混合式等等。服務(wù)臺(tái)的各服務(wù)臺(tái)的各種排列方式種排列方式第26頁/共188頁271.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)

15、機(jī)構(gòu) (服務(wù)臺(tái)情況)服務(wù)臺(tái)可以從以下3方面來描述：(1) 服務(wù)臺(tái)數(shù)量及構(gòu)成形式。從構(gòu)成形式上看，服務(wù)臺(tái)有： 單隊(duì)單服務(wù)臺(tái)式；如(a)圖 單隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(c)圖 多隊(duì)多服務(wù)臺(tái)并聯(lián)式；如(b)圖 單隊(duì)多服務(wù)臺(tái)串聯(lián)式；如(d)圖 單隊(duì)多服務(wù)臺(tái)并串聯(lián)混合式； 多隊(duì)多服務(wù)臺(tái)并串聯(lián)混合式等等。服務(wù)臺(tái)的各服務(wù)臺(tái)的各種排列方式種排列方式第27頁/共188頁281.2 排隊(duì)系統(tǒng)的組成和特征 服務(wù)機(jī)構(gòu) (服務(wù)臺(tái)情況)(2) 服務(wù)方式。這是指在某一時(shí)刻接受服務(wù)的顧客數(shù)，它有單個(gè)服務(wù)和成批服務(wù)兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務(wù)。(3) 服務(wù)時(shí)間的分布。服務(wù)時(shí)間可分為確定型和隨機(jī)型。一般來說，在

16、多數(shù)情況下，對每一個(gè)顧客的服務(wù)時(shí)間是一隨機(jī)變量，其概率分布有定長分布、負(fù)指數(shù)分布、K級(jí)愛爾良分布、一般分布(所有顧客的服務(wù)時(shí)間都是獨(dú)立同分布的)等等。 服務(wù)時(shí)間的分布通常假定是平穩(wěn)的。 指時(shí)間間隔分布及其特征參數(shù)（數(shù)學(xué)期望、方差等）不隨時(shí)間的變化而變化。第28頁/共188頁291.3 排隊(duì)模型的分類 排隊(duì)模型分類方法，1953 構(gòu)成排隊(duì)模型的三個(gè)主要特征指標(biāo) (1) 相繼顧客到達(dá)間隔時(shí)間的分布； (2) 服務(wù)時(shí)間的分布； (3) 服務(wù)臺(tái)的個(gè)數(shù)。 根據(jù)這三個(gè)特征對排隊(duì)模型進(jìn)行分類的Kendall記號(hào)： X/Y/Z X：表示相繼到達(dá)間隔時(shí)間的分布； Y：表示服務(wù)時(shí)間的分布； Z：并列的服務(wù)臺(tái)的數(shù)目

17、。第29頁/共188頁301.3 排隊(duì)模型的分類 M負(fù)指數(shù)分布(M是Markov的字頭，因?yàn)樨?fù)指數(shù)分布具有無記憶性，即Markov性) D確定型(deterministic) Ekk階愛爾朗(erlang)分布 GI 一般相互獨(dú)立(general independent)的時(shí)間間隔的分布 G 一般(general)服務(wù)時(shí)間的分布第30頁/共188頁311.3 排隊(duì)模型的分類 Kendall符號(hào)的擴(kuò)充 X/Y/Z/A/B/C其中前三項(xiàng)的意義不變，后三項(xiàng)的意義分別是： A：系統(tǒng)容量限制N，或稱等待空間容量。如系統(tǒng)有N個(gè)等待位子，則 0 N 00是常數(shù)，則稱是常數(shù)，則稱X 服從參數(shù)為服從參數(shù)為 的泊

18、松分布。的泊松分布。其均值為其均值為 方差為方差為 ekkPPkk! )(E )(D第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第44頁/共188頁45其中其中 00為常數(shù)，則稱為常數(shù)，則稱t t服從參數(shù)為服從參數(shù)為 的指數(shù)分布，其分布函數(shù)的指數(shù)分布，其分布函數(shù)F F( (t t) )為為其均值為其均值為 方差為方差為 ttttedtedttftF 1)()( 000)(ttetft 0001)(ttetFt 1)( tE21)( tDv 負(fù)指數(shù)分布的定義負(fù)指數(shù)分布的定義第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第45頁/共188頁46 如果隨機(jī)變量T的概率密度是則稱T服從負(fù)指數(shù)分布。它的分布函數(shù)是 數(shù)

19、學(xué)期望為 方差為 標(biāo)準(zhǔn)差為 e, 0( )0, 0tTtftt1 e, 0( )0, 0tTtF tt 1E T 21VarT 1Tv 負(fù)指數(shù)分布的定義負(fù)指數(shù)分布的定義第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第46頁/共188頁47經(jīng)驗(yàn)分布 例1 大連港大港區(qū)1979年載貨500噸以上船舶到達(dá)(不包括定期到達(dá)的船舶)逐日記錄見書上表12-2。 將表12-2整理成船舶到達(dá)數(shù)的分布表。 可以計(jì)算出：平均到達(dá)率=到達(dá)總數(shù)/總天數(shù)=1271/365=3.48(艘/天)船舶到達(dá)數(shù)n頻數(shù)頻率(%)0120.0331430.1182640.1753740.2034710.1955490.1346260.071

20、7190.052840.011920.00510以上以上10.003合計(jì)合計(jì)3651.000第47頁/共188頁482. 1.1 經(jīng)驗(yàn)分布 以i表示第i號(hào)顧客到達(dá)的時(shí)刻，以si表示對它的服務(wù)時(shí)間，這樣可算出相繼到達(dá)的間隔時(shí)間ti (ti=i+1-i)和排隊(duì)等待時(shí)間wi，它們的關(guān)系如下：iit1iw0, 00,iiiiiiiiitswtswtsw當(dāng)當(dāng)相繼到達(dá)時(shí)間間隔相繼到達(dá)時(shí)間間隔等待時(shí)間等待時(shí)間第48頁/共188頁492. 1.1 經(jīng)驗(yàn)分布 通過一個(gè)例題來說明原始資料的整理。 例2 某服務(wù)機(jī)構(gòu)是單服務(wù)臺(tái)，先到先服務(wù)，對41個(gè)顧客記錄到達(dá)時(shí)刻和服務(wù)時(shí)間s(單位為分鐘)如表12-4。在表中以第1號(hào)

21、顧客到達(dá)時(shí)刻為0，對所有顧客的全部服務(wù)時(shí)間為127分鐘。將原始記錄整理成下表。第49頁/共188頁50顧客編號(hào)i到達(dá)時(shí)刻i服務(wù)時(shí)間Si到達(dá)間隔ti等待時(shí)間wi顧客編號(hào)i到達(dá)時(shí)刻i服務(wù)時(shí)間Si到達(dá)間隔ti等待時(shí)間wi12345678910111213026111219222636384547495719243312541245173410272230362105650003522232425262728293031323334838688929510110510610911411611712136513221218423243264135214622675201000772. 1.1 經(jīng)驗(yàn)分布第

22、50頁/共188頁51顧客編號(hào)i到達(dá)時(shí)刻i服務(wù)時(shí)間Si到達(dá)間隔ti等待時(shí)間wi顧客編號(hào)i到達(dá)時(shí)刻i服務(wù)時(shí)間Si到達(dá)間隔ti等待時(shí)間wi14151617181920215261626570728081212134329135281230000102353637383940411271291301331351391421635241213243327710892. 1.1 經(jīng)驗(yàn)分布第51頁/共188頁522. 1.1 經(jīng)驗(yàn)分布 例2 某服務(wù)機(jī)構(gòu)是單服務(wù)臺(tái)，先到先服務(wù)，對41個(gè)顧客記錄到達(dá)時(shí)刻和服務(wù)時(shí)間s(單位為分鐘)如表12-4。在表中以第1號(hào)顧客到達(dá)時(shí)刻為0，對所有顧客的全部服務(wù)時(shí)間為127分鐘

23、。將原始記錄整理成下表。到達(dá)間隔到達(dá)間隔/ /分鐘分鐘次數(shù)次數(shù)162103846536272819110以上以上1合計(jì)合計(jì)40服務(wù)時(shí)間服務(wù)時(shí)間/ /分分鐘鐘次數(shù)次數(shù)1102103745546271819以上以上1合計(jì)合計(jì)41第52頁/共188頁532. 1.1 經(jīng)驗(yàn)分布 例2 平均間隔時(shí)間=142/40=3.55(分鐘/人) 平均到達(dá)率=41/142=0.28(人/分鐘) 平均服務(wù)時(shí)間=127/41=3.12(分鐘/人) 平均服務(wù)率=41/127=0.32(人/分鐘) 第53頁/共188頁54 普阿松流，又稱為泊松流、Poisson過程、最簡單流，是排隊(duì)論中一種常用來描述顧客到達(dá)規(guī)律的特殊的隨

24、機(jī)過程。普阿松流（泊松流）第54頁/共188頁55普阿松流（泊松流）設(shè) 表示在時(shí)間區(qū)間 內(nèi)到達(dá)的顧客數(shù) 令 表示在時(shí)間區(qū)間 內(nèi)有 個(gè)顧客到達(dá)的概率，即當(dāng) 滿足下列三個(gè)條件時(shí)，我們說顧客的到達(dá)形成泊松流。 (1) 在不相重疊的時(shí)間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨(dú)立的，即無后效性。 通俗地說就是以前到達(dá)的顧客情況，對以后顧客的到來沒有影響。否則就是關(guān)聯(lián)的。(2) 平穩(wěn)性。又稱作輸入過程是平穩(wěn)的，對充分小的 ，在時(shí)間區(qū)間內(nèi)有1個(gè)顧客到達(dá)的 概率與t無關(guān)，而與區(qū)間長度 成正比，即 其中 ，當(dāng) 時(shí)，是關(guān)于 的高階無窮小。 進(jìn)一步地，在長度為t的時(shí)段內(nèi)恰好到達(dá)k個(gè)顧客的概率僅與時(shí)段長度有關(guān)，而與時(shí)段起點(diǎn)無關(guān)。即對

25、任意(0,)，在(,+t或(0,t)內(nèi)恰好到達(dá)k個(gè)顧客的概率相等：(3) 單個(gè)性又稱普通性。對于充分小的 ，在時(shí)間區(qū)間 內(nèi)有2個(gè)或2個(gè)以上顧客到達(dá)的概率極小，以至于可以忽略，即 , t tt)()()0()()()(tVktPktPkataPk2( ,)()nnP t ttot0,t( )N t(0)t 12( , )nP t t1221,()t ttt( 0)n 122121( , )( )( ) (,0)nP t tP N tN tntt n12( , )nP t ttt1( ,)()P t tttot 0t ()ottt ()( ) ( )(0) ( )PatakPtkPtk第55頁/共

26、188頁56 當(dāng)顧客到達(dá)為泊松流時(shí)，研究顧客到達(dá)數(shù)n的概率分布。 由條件(2)，總可以取時(shí)間由0算起，并簡記 由條件(2)和(3)，容易推得在 區(qū)間內(nèi)沒有顧客到達(dá)的概率 將區(qū)間 分成兩個(gè)互不重疊的區(qū)間 和 。 則到達(dá)總數(shù)n分別出現(xiàn)在這兩個(gè)區(qū)間 和 上，有下列(A)(B)(C)三種情況：(0, )( )nnPtP t, t tt0( ,)1 ()P t tttot 0,tt0,t, t tt概率個(gè)數(shù)概率個(gè)數(shù)概率個(gè)數(shù)區(qū)間情況0,t, t tt0,tt( )( )( )ABC1230nnnn1230( )( )( )( )( )nnnnP tPtPtPtP t0123n1 ()()tottot nn

27、nnn1( )(1 ()( )()nnP ttotPttot 普阿松流（泊松流）0,t, t tt第56頁/共188頁57普阿松流（泊松流） 在 內(nèi)到達(dá)n個(gè)顧客應(yīng)是表中(A)(B)(C)三種互不相容的情況之一，所以概率 應(yīng)是表中三個(gè)概率之和(各 合為一項(xiàng)) 令 ，得下列方程，并注意到初始條件，則有 當(dāng)n=0 時(shí)，沒有(B)，(C)兩種情況， 所以得0,tt()nP tt()ot11 ()( )(1 )( )()()( )()( )( )nnnnnnnP ttP ttPttotP ttP totP tPttt 即 0t 1( )( )+( ), 1(125)( )0nnnndP tP tPtnd

28、tP o 000( )( )(126)( )1dP tP tdtP o ()( )(1)()()( )()( )nnnnnP ttP ttotP ttP totP ttt 即即 第57頁/共188頁58 解(12-5)式和(12-6)式，得 表示長為t的時(shí)間區(qū)間內(nèi)到達(dá)n個(gè)顧客（即N (t)=n）的概率，由(12-7)式得隨機(jī)變量 服從泊松分布。 結(jié)論：當(dāng)顧客到達(dá)為泊松流時(shí)，在長度為t的時(shí)間內(nèi)到達(dá)n個(gè)顧客的概率Pn(t)服從泊松分布! 它的數(shù)學(xué)期望和方差分別是(1)( )( )e(127)!0 0,1,2,ntntP tntn( )nP t( )()( )N tN stN s( ) , Var(

29、 )(128)E N ttN tt普阿松流（泊松流）相等！特別地，t=1時(shí)，EN(1)= ，因此表示單位時(shí)間平均到達(dá)的顧客數(shù)第58頁/共188頁59 我們再來研究兩個(gè)顧客先后到達(dá)的時(shí)間間隔T的概率分布。第59頁/共188頁60當(dāng)輸入過程是泊松流時(shí)，由于在單位時(shí)間里到達(dá)的顧客數(shù)是隨機(jī)變量，那么對應(yīng)的，前后兩個(gè)顧客到達(dá)的時(shí)間間隔也就是隨機(jī)變量了，即有的時(shí)間間隔長一些，有的時(shí)間隔又短一些。 設(shè)T的分布函數(shù)為FT(t)，則這個(gè)概率也就是在0，t)區(qū)間內(nèi)至少有一個(gè)顧客到達(dá)的概率。( )TF tP Tt普阿松流與負(fù)指數(shù)分布關(guān)系普阿松流與負(fù)指數(shù)分布關(guān)系第60頁/共188頁61泊松過程的顧客到達(dá)時(shí)間間隔分布

30、顧客到達(dá)的時(shí)間間隔小于顧客到達(dá)的時(shí)間間隔小于t t的概率，即的概率，即t t內(nèi)有顧客的概率分布。內(nèi)有顧客的概率分布。 兩相鄰顧客到達(dá)的時(shí)間間隔是一連續(xù)型隨機(jī)變量，用兩相鄰顧客到達(dá)的時(shí)間間隔是一連續(xù)型隨機(jī)變量，用T T表示。表示。在在t 時(shí)時(shí)間內(nèi)間內(nèi)沒有沒有顧客到達(dá)的概率為顧客到達(dá)的概率為 tteettP ! 0)()(00普阿松流與負(fù)指數(shù)分布關(guān)系第61頁/共188頁62 在區(qū)間 內(nèi)至少有1個(gè)顧客到達(dá)的概率是 即顧客相繼到達(dá)的間隔時(shí)間即顧客相繼到達(dá)的間隔時(shí)間T必然服從負(fù)指數(shù)分布。必然服從負(fù)指數(shù)分布。0,t01( )1, 0tP tet 其概率密度函數(shù)：其概率密度函數(shù)： tTetPtTPtTPtF

31、 1)(1)(1)()(0tTTedttdFtf )()(數(shù)學(xué)期望為 1E T 表示單位時(shí)間內(nèi)顧客平均到達(dá)數(shù)。 1/表示顧客到達(dá)的平均間隔時(shí)間。普阿松流與負(fù)指數(shù)分布關(guān)系第62頁/共188頁63 顧客相繼到達(dá)的間隔時(shí)間獨(dú)立且為同負(fù)指數(shù)分布(密度函數(shù)為 )，與輸入過程為泊松流(參數(shù)為)是等價(jià)的。 對于泊松流，表示單位時(shí)間平均到達(dá)的顧客數(shù)，1/ 表示相繼顧客到達(dá)平均間隔時(shí)間。0, tetv 相繼到達(dá)時(shí)間間隔為負(fù)指數(shù)分布與到達(dá)為泊松相繼到達(dá)時(shí)間間隔為負(fù)指數(shù)分布與到達(dá)為泊松流的等價(jià)性流的等價(jià)性上述內(nèi)容還可以用如下表達(dá)！ 對于泊松流，其相繼顧客到達(dá)時(shí)間間隔i，i=1,2,是相互獨(dú)立同分布的，其分布函數(shù)為負(fù)

32、指數(shù)分布： 0, 00,1)(ttetFti), 2 , 1(i普阿松流與負(fù)指數(shù)分布關(guān)系第63頁/共188頁64 當(dāng)輸入過程是泊松流時(shí)，那么顧客相繼到達(dá)的間隔時(shí)間T（注意T是隨機(jī)變量）必然服從負(fù)指數(shù)分布。普阿松流與負(fù)指數(shù)分布關(guān)系第64頁/共188頁65 負(fù)指數(shù)分布的性質(zhì)負(fù)指數(shù)分布的性質(zhì)由條件概率公式容易證明 該性質(zhì)稱為無記憶性或馬爾柯夫性。若T表示排隊(duì)系統(tǒng)中顧客相繼到達(dá)的間隔時(shí)間，該性質(zhì)說明：一個(gè)顧客到來所需的時(shí)間與過去一個(gè)顧客到來所需時(shí)間s 無關(guān)，也就是說該顧客是隨機(jī)地到達(dá)。(12 11)P Tts TsP Tt 普阿松流與負(fù)指數(shù)分布關(guān)系第65頁/共188頁66 例: :有易碎物品50050

33、0件, ,由甲地運(yùn)往乙地, ,根據(jù)以往統(tǒng)計(jì)資料, ,在運(yùn)輸過程中易碎物品按普阿松流發(fā)生破碎, ,其破損率為0.002,0.002,現(xiàn)求:1.:1.破碎3 3件物品的概率;2.;2.破碎少于3 3件的概率和多于3 3件的概率;3.;3.至少有一件破損的概率. . 解: : =0.002500=1 1 1破碎3 3件物品的概率為: : P(k=3)=( P(k=3)=( 3 3/3/3！)e)e- - =(1=(13 3/3/3！)e)e-1-1=0.0613=0.0613 即物品破碎3 3件的概率為6.136.13 2. 2.破碎物品少于3 3件的概率: :第66頁/共188頁67 破碎物品少于

34、3 3件的概率為91.9791.97 破碎物品多于3 3件的概率為: : 02. 098. 01!1330 kkekp 3.3.至少有一件破碎的概率為 PkPk 1=1-(11=1-(1k k/k!)e/k!)e- - =1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.632 9197. 021112120 eeknp第67頁/共188頁682.1 到達(dá)間隔的分布經(jīng)驗(yàn)分布（定長輸入）普阿松流（泊松流）普阿松流與負(fù)指數(shù)分布關(guān)系2.2 服務(wù)時(shí)間的分布經(jīng)驗(yàn)分布（定長分布）負(fù)指數(shù)分布愛爾朗分布第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第68頁/共188頁69 每一個(gè)顧客的服務(wù)時(shí)間都是

35、常數(shù)，此時(shí)服務(wù)時(shí)間t的分布函數(shù)為： xxxtPxB01)()(服務(wù)時(shí)間的定長分布第69頁/共188頁70 服務(wù)時(shí)間服務(wù)時(shí)間v v 的分布的分布 對顧客的服務(wù)時(shí)間，也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時(shí)間，有時(shí)也服從負(fù)指數(shù)分布。設(shè)它的分布函數(shù)和密度分別是其中, 表示對顧客的平均服務(wù)時(shí)間。表示單位時(shí)間能被服務(wù)完成的顧客數(shù)，稱為平均服務(wù)率， ( )1 e, ( )e(12 12)ttvvF tf t 1()Ev服務(wù)時(shí)間的負(fù)指數(shù)分布第70頁/共188頁71 是指相繼顧客到達(dá)時(shí)間間隔T相互獨(dú)立，其分布密度為 其中，k為非負(fù)整數(shù)。 1()( )0(1)!Kttf tetK v愛爾朗分布愛爾朗分布服務(wù)時(shí)間

36、的愛爾朗分布第71頁/共188頁72 設(shè) 是k個(gè)相互獨(dú)立的隨機(jī)變量，服從相同參數(shù) 的負(fù)指數(shù)分布，那么 的概率密度是稱T服從k階愛爾朗分布，其均值和方差分別為12,kv vvk12kTvvv1()( )e, 0(12 13)(1)!kktkkktb ttk 211;Var(12 14)E TTk可以證明如下結(jié)論。服務(wù)時(shí)間的愛爾朗分布第72頁/共188頁73 愛爾朗分布的意義愛爾朗分布的意義 當(dāng)k=1時(shí)，愛爾朗分布化為負(fù)指數(shù)分布，可看成是一種完全隨機(jī)的分布； 當(dāng)k增大時(shí)，愛爾朗分布的圖形逐漸變?yōu)閷ΨQ的； 當(dāng)k30時(shí)愛爾朗分布近似于正態(tài)分布； k時(shí)，VarT0，這時(shí)愛爾朗分布化為確定型分布。一般k階

37、愛爾朗分布可看成完全隨機(jī)與完全確定的中間型，能對現(xiàn)實(shí)世界提供更為廣泛的適應(yīng)性。1()( )e, 0(12 13)(1)!kktkkktb ttk服務(wù)時(shí)間的愛爾朗分布第73頁/共188頁74可以證明，在參數(shù)為的泊松輸人中，對任意的j與k,設(shè)第j與第j+k個(gè)顧客之間的到達(dá)間隔為 。則隨機(jī)變量Tk的分布必遵從參數(shù)為的愛爾朗分布，其分布密度為：)(21kkkTT1()( )0(1)!Kttf tetK 1/ k1/ k表示一個(gè)顧客的一個(gè)服務(wù)臺(tái)的平均服務(wù)時(shí)間。服務(wù)時(shí)間的愛爾朗分布第74頁/共188頁75 例如： 某排隊(duì)系統(tǒng)有并聯(lián)的k個(gè)服務(wù)臺(tái)，顧客流為泊松流，規(guī)定第i, K+i, 2K+i個(gè)顧客排入第i號(hào)

38、臺(tái)(i=1,2,K)，則第K臺(tái)所獲得的顧客流，即為愛爾朗輸入流，其他各臺(tái)，從它的第一個(gè)顧客到達(dá)以后開始所獲得的流也為愛爾朗輸入流。例如：串聯(lián)的k k個(gè)服務(wù)臺(tái)，每臺(tái)服務(wù)時(shí)間相互獨(dú)立，服從相同的負(fù)指數(shù)分布（參數(shù)k k ），那么一顧客走完k k個(gè)服務(wù)臺(tái)總共所需要服務(wù)時(shí)間就服從k k階ErlangErlang分布。服務(wù)時(shí)間的愛爾朗分布第75頁/共188頁76第1節(jié) 基本概念第2節(jié) 到達(dá)間隔的分布和服務(wù)時(shí)間的分布第3節(jié) 單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第4節(jié) 多服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析第5節(jié) 一般服務(wù)時(shí)間M/G/1模型第6節(jié) 經(jīng)濟(jì)分析系統(tǒng)的最優(yōu)化第7節(jié) 分析排隊(duì)系統(tǒng)的隨機(jī)模擬法排隊(duì)論第76頁/共1

39、88頁77排隊(duì)論 排隊(duì)論研究的首要問題是排隊(duì)系統(tǒng)主要數(shù)量指標(biāo)的概率規(guī)律，即研究系統(tǒng)的整體性質(zhì)，然后進(jìn)一步研究系統(tǒng)的優(yōu)化問題。與這兩個(gè)問題相關(guān)的還包括排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷問題。 (1)通過研究主要數(shù)量指標(biāo)在瞬時(shí)或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征，了解系統(tǒng)運(yùn)行的基本特征。 (2)統(tǒng)計(jì)推斷問題，建立適當(dāng)?shù)呐抨?duì)模型是排隊(duì)論研究的第一步，建立模型過程中經(jīng)常會(huì)碰到如下問題：檢驗(yàn)系統(tǒng)是否達(dá)到平穩(wěn)狀態(tài)；檢驗(yàn)顧客相繼到達(dá)時(shí)間間隔的相互獨(dú)立性；確定服務(wù)時(shí)間的分布及有關(guān)參數(shù)等。第77頁/共188頁78 (3)系統(tǒng)優(yōu)化問題，又稱為系統(tǒng)控制問題或系統(tǒng)運(yùn)營問題，其基本目的是使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。 系統(tǒng)優(yōu)化問題包括最

40、優(yōu)設(shè)計(jì)問題和最優(yōu)運(yùn)營問題，其內(nèi)容很多，有最少費(fèi)用問題、服務(wù)率的控制問題、服務(wù)臺(tái)的開關(guān)策略、顧客(或服務(wù))根據(jù)優(yōu)先權(quán)的最優(yōu)排序等方面的問題。 對于一般的排隊(duì)系統(tǒng)運(yùn)行情況的分析，通常是在給定輸入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為n(有n個(gè)顧客)的概率Pn(t)，再進(jìn)行計(jì)算其主要的運(yùn)行指標(biāo)： 排隊(duì)論第78頁/共188頁79 系統(tǒng)中顧客數(shù)(隊(duì)長)的期望值L或Ls； 排隊(duì)等待的顧客數(shù)(排隊(duì)長)的期望值Lq； 顧客在系統(tǒng)中全部時(shí)間(逗留時(shí)間)的期望值W或Ws； 顧客排隊(duì)等待時(shí)間的期望值Wq。 排隊(duì)系統(tǒng)中，由于顧客到達(dá)分布和服務(wù)時(shí)間分布是多種多樣的，加之服務(wù)臺(tái)數(shù)。顧客源有限無限，排隊(duì)容量有限無限等的不同組合，

41、就會(huì)有不勝枚舉的不同排隊(duì)模型，若對所有排隊(duì)模型都進(jìn)行分析與計(jì)算，不但十分繁雜而且也沒有必要。 下面擬分析幾種常見排隊(duì)系統(tǒng)模型。排隊(duì)論第79頁/共188頁80 3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/) 3.2 系統(tǒng)容量有限的情況(M/M/1/N/) 3.3 顧客源有限的情形(M/M/1/m)第3節(jié) 單服務(wù)臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)的分析本節(jié)討論輸入過程服從普阿松分布過程、服務(wù)時(shí)間服從負(fù)指數(shù)分布單服務(wù)臺(tái)的排隊(duì)系統(tǒng)。第80頁/共188頁81 標(biāo)準(zhǔn)的M/M/1模型 (1) 輸入過程顧客源是無限的，顧客單個(gè)到來，相互獨(dú)立，一定時(shí)間內(nèi)的到達(dá)數(shù)服從泊松分布，到達(dá)過程是平穩(wěn)的。 (2) 排隊(duì)規(guī)則單隊(duì)，且對隊(duì)長沒

42、有限制，先到先服務(wù)。 (3) 服務(wù)機(jī)構(gòu)單服務(wù)臺(tái)，各顧客的服務(wù)時(shí)間相互獨(dú)立，服從相同的負(fù)指數(shù)分布。 此外，還假定到達(dá)間隔時(shí)間和服務(wù)時(shí)間是相互獨(dú)立的。 3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)即已知條件：v ：顧客進(jìn)入系統(tǒng)的平均速度；單位時(shí)間到達(dá)的顧客數(shù)。v ：顧客離開系統(tǒng)的平均速度；單位時(shí)間能被服務(wù)完成的顧客數(shù)。第81頁/共188頁82 首先要求出：系統(tǒng)在任意時(shí)刻t的狀態(tài)為n(即系統(tǒng)中有n個(gè)顧客)的概率 ，它決定了系統(tǒng)運(yùn)行的特征。 現(xiàn)仍然通過研究區(qū)間t，t+t）的變化來求解。在時(shí)刻t+t，系統(tǒng)中有n個(gè)顧客不外乎有下列四種情況（ t，t+t）內(nèi)到達(dá)或離開2個(gè)以上沒列入）。( )nP t3.1

43、標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)第82頁/共188頁83 因已知到達(dá)規(guī)律服從參數(shù)為 的泊松過程，服務(wù)時(shí)間服從參數(shù)為 的負(fù)指數(shù)分布，所以在 時(shí)間區(qū)間內(nèi)分為： (1) 有1個(gè)顧客到達(dá)的概率為 沒有顧客到達(dá)的概率就是 (2) 當(dāng)有顧客在接受服務(wù)時(shí)，1個(gè)顧客被服務(wù)完了(離去)的概率是 ， 沒 有 離 去 的 概 率 就是 。 (3) 多于一個(gè)顧客的到達(dá)或離去的概率是 ，可以忽略。, t tt()tot 1()tot ()tot 1()tot ()ot3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)第83頁/共188頁843.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/) 在時(shí)刻 ，系統(tǒng)中有n個(gè)顧客(n0)存

44、在下列四種情況(到達(dá)或離去是2個(gè)以上的沒列入)：表示發(fā)生(1個(gè))；表示沒有發(fā)生。tttt , t ttnn(D)nn-1(C)nn+1(B)nn(A)離去到達(dá)在時(shí)刻 顧客數(shù)在區(qū)間在區(qū)間在時(shí)刻t顧客數(shù)情況第84頁/共188頁85第85頁/共188頁86 這四種情況是互不相容的，所以 應(yīng)是這四項(xiàng)之和，即 即 令 ，得關(guān)于 的微分差分方程 ()nP tt1111()( )(1 )( )( )()()( )()( )( )()( )nnnnnnnnnP ttP tttPttPttotP ttP totPtPtP ttt 0t ( )nP t11( )( )( )()( ) 1,2,(12 15)nnn

45、ndP tPtPtP tndt3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)( )(1 )(1)nP ttt 1( )(1)nPttt 1( ) (1)nPttt ( ) nP ttt 所有的高階無窮小和并tttPtttPtttPttPnnnn)1)()()1)(1)()(1)()1 ()(1tOtttPn第86頁/共188頁87v當(dāng) ，則只有上表中(A)(B)情況，因?yàn)樵谳^小的t內(nèi)不可能發(fā)生（D）（到達(dá)后即離去），若發(fā)生可將t取小即可。且式(A)中無離去的概率為1，即v同理求得 它們的概率分別是 情況(A) 情況(B) 情況(C) 情況(D) tt , t ttnn(D)nn-1(C)nn+1

46、(B)nn(A)離去到達(dá)在時(shí)刻 顧客數(shù)在區(qū)間在區(qū)間在時(shí)刻t 顧客數(shù)情況( )(1 )(1)nP ttt 1( )(1)nPttt 1( ) (1)nPttt ( ) nP ttt3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)0n 001()( )(1 )( )(1 )P ttP ttP ttt 001( )( )( )(12 16)dP tP tP tdt 第87頁/共188頁88 研究穩(wěn)態(tài)的情況。這時(shí) 與時(shí)間t無關(guān)，可寫成 ，它的導(dǎo)數(shù)為0。由(12-15)式和(12-16)式可得 這是關(guān)于 的差分方程，它表明了各狀態(tài)間的轉(zhuǎn)移關(guān)系：狀態(tài)0轉(zhuǎn)移到狀態(tài)1的轉(zhuǎn)移率為 ，狀態(tài)1轉(zhuǎn)移到狀態(tài)0的轉(zhuǎn)移率為 。

47、 ( )nP tnP01110(12 17,12 18)()0 1nnnPPPPPn0P1PnP3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)這種系統(tǒng)狀態(tài)(n)隨時(shí)間變化的過程就是生滅過程（Birth and Death Process）。 方程(12-15)、(12-16) 解是瞬態(tài)解，無法應(yīng)用。 第88頁/共188頁893.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/) 對狀態(tài)0必須滿足以下平衡方程 同樣對任何 的狀態(tài)，可得如(12-18)所示的平衡方程。 由(12-17)式可得 將它代入(12-18)式，令 ，得到 同理依次推得 今設(shè) (否則隊(duì)列將排至無限遠(yuǎn))，又由概率的性質(zhì)知 即 ，得到01P

48、P1n10(/)PP220020()(/) (/)PPPPP；所以 1n 0(/)nnPP101nnP01 1(12 19)(1), 1nnPPn 0000111nnnnppP01110(12 17,12 18)()0 1nnnPPPPPn 第89頁/共188頁90 對的實(shí)際意義的解釋/，是平均到達(dá)率與平均服務(wù)率之比，即在相同時(shí)區(qū)內(nèi)顧客到達(dá)的平均數(shù)與被服務(wù)的平均數(shù)之比。 若將表示為(1/)/(1/)，它是一個(gè)顧客的服務(wù)時(shí)間與到達(dá)間隔時(shí)間之比，稱為服務(wù)強(qiáng)度(traffic intensity)，或話務(wù)強(qiáng)度。 由(12-19)式可知，=1-P0，它刻畫了服務(wù)機(jī)構(gòu)的繁忙程度，所以又稱為服務(wù)機(jī)構(gòu)的利用

49、率。3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/) 系統(tǒng)處于空閑狀態(tài)的概率： 10P 系統(tǒng)處于繁忙狀態(tài)的概率： 010P)N(P第90頁/共188頁913.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/) 根據(jù)平穩(wěn)分布，求排隊(duì)系統(tǒng)的有關(guān)運(yùn)行指標(biāo)(1) 系統(tǒng)中的平均顧客數(shù)（平均隊(duì)長） 或 (2) 在隊(duì)列中等待的平均顧客數(shù) 012323423(1)(23)(23), 0 11nsnnnLnPn sL1112(1)1qnnnnnnsLnPnPPL 期望 10P第91頁/共188頁92顧客在系統(tǒng)中的逗留時(shí)間W(為一個(gè)隨機(jī)變量)在M/M/1情形下，服從參數(shù)為 的負(fù)指數(shù)分布，即 分布函數(shù) 概率密度 ()( )1 e

50、 0(1220)wF ww ()( )()ewf w 于是，得到(3) 在系統(tǒng)中顧客逗留時(shí)間的期望值 (4) 在隊(duì)列中顧客等待時(shí)間的期望值 1sWE W1qsWW3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/) 平均逗留時(shí)間減去平均服務(wù)時(shí)間。第92頁/共188頁93 將以上結(jié)果歸納如下： 它們的相互關(guān)系如下： 上式稱為Little公式。(1) (2) (1221)1(3) (4) sqsqLLWW(1) (2) (1222)1(3) (4) ssqqsqsqLWLWWWLL3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)第93頁/共188頁943.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)Ls ,L q

51、, ,Ws ,Wq之間的關(guān)系：幾何解釋： 穩(wěn)態(tài)時(shí)，一個(gè)顧客，進(jìn)入系統(tǒng)后，每單位時(shí)間，平均到達(dá)顧客。 逗留時(shí)間的期望值Ws 進(jìn)入時(shí)刻離開時(shí)刻隊(duì)長Ls由時(shí)間段內(nèi)個(gè)組成的Ls=Ws(1) (2) (12 22)1(3) (4) ssqqsqsqLWLWWWLL同理：Lq=Wq Ws=Wq+（1/）-Ws與Wq只相差一段平均服務(wù)時(shí)間1/ 第94頁/共188頁95泊松輸入負(fù)指數(shù)分布服務(wù)的排隊(duì)系統(tǒng)的一般決策過程： 根據(jù)已知條件繪制狀態(tài)轉(zhuǎn)移速度圖； 依據(jù)狀態(tài)轉(zhuǎn)移速度圖寫出各穩(wěn)態(tài)概率之間的關(guān)系； 求出 P0 及 Pn ； 計(jì)算各項(xiàng)數(shù)量運(yùn)行指標(biāo)； 用系統(tǒng)運(yùn)行指標(biāo)構(gòu)造目標(biāo)函數(shù)，對系統(tǒng)進(jìn)行優(yōu)化。3.1 標(biāo)準(zhǔn)的M/M

52、/1模型(M/M/1/)第95頁/共188頁96 例3 某醫(yī)院手術(shù)室根據(jù)病人來診和完成手術(shù)時(shí)間的記錄，任意抽查了100個(gè)工作小時(shí)，每小時(shí)來就診的病人數(shù)n的出現(xiàn)次數(shù)如下表所示；又任意抽查了100個(gè)完成手術(shù)的病歷，所用時(shí)間v(單位：小時(shí))出現(xiàn)的次數(shù)如下表所示。nf到達(dá)的病人數(shù)n出現(xiàn)人數(shù)010128229316410566以上以上1合計(jì)合計(jì)100vf為病人完成手術(shù)時(shí)間v(小時(shí))出現(xiàn)人數(shù)0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以上以上0合計(jì)合計(jì)1003.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)第96頁/共188頁97 (1) 每小時(shí)病人平均到達(dá)率

53、 (人/小時(shí)) 每次手術(shù)平均時(shí)間 (小時(shí)/人) 每小時(shí)完成手術(shù)人數(shù)(平均服務(wù)率) (人/小時(shí)) (2) 取 ， ，可以通過統(tǒng)計(jì)檢驗(yàn)的方法，認(rèn)為病人到達(dá)數(shù)服從參數(shù)為2.1的泊松分布，手術(shù)時(shí)間服從參數(shù)為2.5的負(fù)指數(shù)分布。 (3) 說明服務(wù)機(jī)構(gòu)(手術(shù)室)有84%的時(shí)間是繁忙的，有16%的時(shí)間是空閑的。 (4) 依次代入(12-21)式，算出各指標(biāo)： 在病房中病人數(shù)(期望值) (人) 排隊(duì)等待病人數(shù)(期望值) (人) 病人在病房中逗留時(shí)間(期望值) (小時(shí)) 病人排隊(duì)等待時(shí)間(期望值) (小時(shí))2.1100nnf0.4100vvf52.52.

54、1sL 0.84 5.254.41qL sW 0.8qW 3.1 標(biāo)準(zhǔn)的M/M/1模型(M/M/1/)第97頁/共188頁983.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)第98頁/共188頁993.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)第99頁/共188頁1003.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)第100頁/共188頁1013.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)第101頁/共188頁1023.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)第102頁/共188頁1033.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1

55、模型模型(M/M/1/)第103頁/共188頁104解：本例可看成一個(gè)解：本例可看成一個(gè)M/M/1/ 排隊(duì)問題，其中排隊(duì)問題，其中 =2， =3， = / =2/31系統(tǒng)中列車的平均數(shù)系統(tǒng)中列車的平均數(shù)L= / (1- )=(2/3)/(1-2/3)=2（列）（列）列車在系統(tǒng)中的平均停留時(shí)間列車在系統(tǒng)中的平均停留時(shí)間W=L/ = 2/2=1（小時(shí)）（小時(shí)）系統(tǒng)中等待編組的列車平均數(shù)系統(tǒng)中等待編組的列車平均數(shù)Lq=L- = 2-2/3=4/3（列）（列）列車在系統(tǒng)中的平均等待編組時(shí)間列車在系統(tǒng)中的平均等待編組時(shí)間 Wq = Lq/ =(4/3)/(1/2)=2/3（小時(shí)）（小時(shí)）3.1 標(biāo)準(zhǔn)的標(biāo)

56、準(zhǔn)的M/M/1模型模型(M/M/1/)第104頁/共188頁1053.1 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的M/M/1模型模型(M/M/1/)第105頁/共188頁106 如果系統(tǒng)的最大容量為N，對于單服務(wù)臺(tái)的情形，排隊(duì)等待的顧客最多為N-1，在某時(shí)刻一顧客到達(dá)時(shí)，如系統(tǒng)中已有N個(gè)顧客，那么這個(gè)顧客就被拒絕進(jìn)入系統(tǒng)。 當(dāng)N=1時(shí)為即時(shí)制的情形；當(dāng)N時(shí)為容量無限制的情形。3.2 系統(tǒng)的容量有限制的情況(M/M/1/N/)第106頁/共188頁107泊松輸入負(fù)指數(shù)分布服務(wù)的排隊(duì)系統(tǒng)的一般決策過程： 根據(jù)已知條件繪制狀態(tài)轉(zhuǎn)移速度圖； 依據(jù)狀態(tài)轉(zhuǎn)移速度圖寫出各穩(wěn)態(tài)概率之間的關(guān)系； 求出 P0 及 Pn ； 計(jì)算各項(xiàng)數(shù)量運(yùn)行

57、指標(biāo)； 用系統(tǒng)運(yùn)行指標(biāo)構(gòu)造目標(biāo)函數(shù)，對系統(tǒng)進(jìn)行優(yōu)化。3.2 系統(tǒng)的容量有限制的情況(M/M/1/N/)第107頁/共188頁1083.2 系統(tǒng)的容量有限制的情況(M/M/1/N/) 穩(wěn)態(tài)情形下各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系圖 狀態(tài)概率的穩(wěn)態(tài)方程 10111 (12-23a)(), 1 (12-23b) (12-23c)nnnNNPPPPPnNPP情情況況 時(shí)時(shí)刻刻 t 的的顧顧客客 區(qū)區(qū)間間 t, t+t t 時(shí)時(shí)刻刻 t+t t的的顧顧客客數(shù)數(shù) 概概率率 A A N N 無無離離去去 （肯肯定定不不到到達(dá)達(dá)） N N P Pn n( (t t) )( (1 1- -t t) ) B B N N-

58、 -1 1 一一人人到到達(dá)達(dá)（無無離離去去） N N P Pn n- -1 1( (t t) )t t ttPttPttPNNN)()1 ()()(1 )()()(1tPtPdttdPNNN 第108頁/共188頁1093.2 系統(tǒng)的容量有限制的情況(M/M/1/N/) 穩(wěn)態(tài)情形下各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系圖 狀態(tài)概率的穩(wěn)態(tài)方程 其中(12-23b)也可寫成 ，則有10111 (12-23a)(), 1 (12-23b) (12-23c)nnnNNPPPPPnNPP0(/)nnPP1001 (), 1 nnNNPPPPnNPP第109頁/共188頁1103.2 系統(tǒng)的容量有限制的情況(M/M/

59、1/N/) 由 1001 (), 1 nnNNPPPPnNPP N則 (/)nP0=1 n=0 N即 P0=1/(/)n= n=0(1-(1-/)/(1-()/(1-(/) )N N+1+1 1/(1/(N N +1) +1) = =011NPPP第110頁/共188頁111 M/M/1/N/排隊(duì)系統(tǒng)的各項(xiàng)指標(biāo)： (1) 隊(duì)長(期望值) (2) 隊(duì)列長(期望值) (3) 顧客逗留時(shí)間(期望值) (4) 顧客等待時(shí)間(期望值) (5) 有效到達(dá)率 110(1) 111NNsnNnNLnP01(1)(1)NqnsnLnPLP01(1)(1)qssNLLWPP1/qsWW(1)eNP3.2 系統(tǒng)的容

60、量有限制的情況(M/M/1/N/)v令 ，得到0111 111 (1224)1NnnNPPnN/第111頁/共188頁112 (1) 平均隊(duì)長Ls：nPnLnNnNNnns 01011nNnNn 0111111) 1(1 NNN (1) 試證=1=1時(shí),Ls=N/2,Ls=N/23.2 系統(tǒng)的容量有限制的情況系統(tǒng)的容量有限制的情況(M/M/1/N/)0111 111 (1224)1NnnNPPnN第112頁/共188頁113 M/M/1/N/排隊(duì)系統(tǒng)的各項(xiàng)指標(biāo)： (1) 隊(duì)長(期望值) (2) 隊(duì)列長(期望值) (3) 顧客逗留時(shí)間(期望值) (4) 顧客等待時(shí)間(期望值) (5) 有效到達(dá)率