運籌學教材(第六章-排隊論)ppt課件(全)

1、運 籌 學運籌學（普通高等教育“十二五”經(jīng)濟與管理類專業(yè)核心課程規(guī)劃教材） 主編：郭鵬出版社：西安交通大學出版社出版時間：2013-12-01 緒論 第1章 線性規(guī)劃 第2章 線性規(guī)劃的對偶理論 第3章 特殊線性規(guī)劃 第4章 動態(tài)規(guī)劃 第5章 圖與網(wǎng)絡分析 第6章 排隊論 第7章 庫存論 第8章 決策論 第9章 對策論運 籌 學 6.1 排隊系統(tǒng)的特征與基本排隊系統(tǒng) 6.2 單服務臺指數(shù)分布排隊系統(tǒng) 6.3 多服務臺指數(shù)分布排隊系統(tǒng) 6.4 一般服務時間的排隊系統(tǒng) 6.5 排隊系統(tǒng)的優(yōu)化 6.6 案例分析 第6章 排隊論郭鵬制作 6.1.1 排隊系統(tǒng)及其組成 圖6-1 排隊系統(tǒng)基本模型 排隊系

2、統(tǒng)都有三個基本組成部分：（1）輸入過程：顧客按怎樣的規(guī)律到達（2）排隊規(guī)則：顧客接受服務的先后次序問題（3）服務機構：服務機構的特征主要包括：服務臺數(shù)目和服務時間的分布6.1 排隊系統(tǒng)的特征與基本排隊 輸入過程需要三個方面的內(nèi)容：（1）顧客的總體數(shù)或顧客源數(shù)：可能到達服務機構的顧客總數(shù)（2）顧客到達的類型：顧客是單個到達，還是成批到達（3）顧客相繼到達的時間間隔分布：顧客相繼到達服務臺，常常服從某種統(tǒng)計規(guī)律，如定長分布(D)，負指數(shù)分布(M)，K階愛爾朗分布(Ek)等6.1.1 排隊系統(tǒng)及其組成 排隊規(guī)則所研究的是顧客接受服務的先后次序問題，可分幾種情形來討論：（1）損失制：顧客到達時，如果所

3、有的服務臺都正被占用，而顧客隨即離去，不再接受服務。（2）等待制：顧客到達時，如果所有的服務臺都正被占用，而顧客排隊等待服務。先到先服務(FCFS)；后到先服務(LCFS)；隨機服務(SIRO)；優(yōu)先權服務（PR）。（3）混合制：混合制是損失制和等待制的結合。隊長有限制；排隊等待時間有限制。6.1.1 排隊系統(tǒng)及其組成 服務機構的特征主要包括：服務臺數(shù)目和服務時間的分布。在多個服務臺時，是串聯(lián)還是并聯(lián)；對顧客是逐個進行服務還是成批服務。服務時間所遵循的分布有：定長分布（D），指數(shù)分布(N)，K階愛爾朗分布（Ek），一般服務（G）等。6.1.1 排隊系統(tǒng)及其組成 排隊系統(tǒng)的描述形式：A/B/C：

4、D/E/FA顧客到達排隊系統(tǒng)的時間間隔分布。B服務時間的分布。C服務臺數(shù)（或服務通道數(shù)）。(C=1 ，2 ，n)D排隊系統(tǒng)的容量，即系統(tǒng)中允許的最大顧客數(shù) E顧客源的總體數(shù)目 F服務規(guī)則 FCFS，LCFS，SIRO，PR 6.1.1 排隊系統(tǒng)及其組成 排隊系統(tǒng)研究的問題大體分為三類：（1）系統(tǒng)性態(tài)的研究（即數(shù)量指標的研究）（2）統(tǒng)計問題的研究（3）最優(yōu)化問題6.1.2 排隊系統(tǒng)研究的問題 系統(tǒng)數(shù)量指標的研究旨在了解系統(tǒng)的基本特征，其主要的數(shù)量指標如下：（1）隊長（L）：系統(tǒng)內(nèi)顧客數(shù)的期望值。（2）列長（Lq）：系統(tǒng)中排隊顧客數(shù)的期望值，即排隊等待服務顧客數(shù)的期望值。（3）顧客在系統(tǒng)內(nèi)停留時間

5、的期望值（W）（4）顧客在系統(tǒng)內(nèi)等待時間的期望值（Wq）（5）忙期分布（6）服務設備利用率（7）顧客損失率6.1.2 排隊系統(tǒng)研究的問題泊松分布 設N(t)表示在時間區(qū)間0，t內(nèi)到達的顧客數(shù)（t0），令 表示在時間區(qū)間 內(nèi)有 個顧客到達的概率，即 泊松分布具有如下三個特性：（1）無后效性（2）平穩(wěn)性（3）普遍性6.1.3 排隊論中常見的幾種理論分布負指數(shù)分布 隨機變量T服從負指數(shù)分布，其分布密度是:分布函數(shù)為: 負指數(shù)分布有下面兩條性質(zhì)：（1）當單位時間內(nèi)的顧客到達數(shù)服從以 為平均數(shù)的泊松分布時，則顧客相繼到達的間隔時間T服從負指數(shù)分布。（2）無記憶性6.1.3 排隊論中常見的幾種理論分布愛爾

6、朗分布 設顧客在系統(tǒng)內(nèi)所接受服務可以分為k個階段，每個階段的服務時間 為服從同一分布 的k個相互獨立的隨機變量，顧客在完成全部服務內(nèi)容并離開系統(tǒng)后，另一個顧客才能進入系統(tǒng)服務，則顧客在系統(tǒng)內(nèi)接受服務時間和 服從愛爾朗分布 ，其分布密度函數(shù)為：6.1.3 排隊論中常見的幾種理論分布 6.2.1 排隊模型 適用于滿足以下條件的排隊系統(tǒng)：(1) 輸入過程：顧客源是無限的，顧客單個到來，相互獨立，一定時間內(nèi)的到達數(shù)服從泊松分布，到達過程是平穩(wěn)的。(2) 排隊規(guī)則：單隊，且對隊長沒有限制，先到先服務。(3) 服務機構：單服務臺，各顧客的服務時間相互獨立，服從相同的負指數(shù)分布。此外，還假定到達間隔時間和服

7、務時間是相互獨立的。 6.2 單服務臺指數(shù)分布排隊系統(tǒng) 系統(tǒng)穩(wěn)態(tài)概率 的計算已知顧客到達率為 ，服務率為 ，在時間 時，系統(tǒng)內(nèi)n個顧客的狀態(tài)由以下四種方式構成：（1）在時刻t時有n個顧客，在隨后 時間內(nèi)沒有顧客到達，也沒有顧客離去；（2）在時刻t時有n1個顧客，在隨后的 時間內(nèi)沒有顧客離去，有一個顧客到達；（3）在時刻t時有n+1個顧客，在隨后的 時間內(nèi)有一個顧客離去，沒有顧客到達；（4）在時刻t時有n個顧客，在隨后的 時間內(nèi)有一個顧客到達，同時有一個顧客離去。 6.2.1 排隊模型 各種方式所發(fā)生的概率如表6-1所示：表61 四種方式所發(fā)生的概率表6.2.1 排隊模型時刻t的狀態(tài)概率t內(nèi)發(fā)生

8、的事件發(fā)生的概率nPn(t)無到達，無離去（1 ）（1 ）n1Pn-1 (t)到達一個，無離去(1 )n1Pn-1 (t)離去一個，無到達（1 ） nPn(t)到達一個，離去一個 由于這四種方式互不相容，故由概率的加法定律得：6.2.1 排隊模型 當 時， 則有差分微分方程 （6-1）求此差分微分方程的穩(wěn)態(tài)解，穩(wěn)態(tài)解是指系統(tǒng)運行的時間t充分大時所得到的解。此時系統(tǒng)狀態(tài)的概率分布已不隨時間而變化，達到了統(tǒng)計平衡。穩(wěn)態(tài)解與時間無關，因此有6.2.1 排隊模型 方程式（6-1）可以寫為： （6-2） 聯(lián)立求解得： 6.2.1 排隊模型 令 ，由 得系統(tǒng)的穩(wěn)態(tài)解為： （6-3） 刻畫了服務效率和服務機

9、構利用程度，稱為服務強度（在通訊領域里 稱為話務強度）。在推導公式中限制 ，因此 是系統(tǒng)能夠到達穩(wěn)定狀態(tài)的充要條件。若 ，即到達率大于等于服務率，對于系統(tǒng)容量和顧客源均無限，到達和服務又是隨機的，將出現(xiàn)隊列排至無限遠，無法達到穩(wěn)定狀態(tài)的情形。 6.2.1 排隊模型狀態(tài)轉(zhuǎn)移圖 穩(wěn)態(tài)方程式（62）也可以通過所謂狀態(tài)轉(zhuǎn)移圖列出見圖62），然后求解。 P0 P1 Pn-1 Pn Pn+1 圖62 狀態(tài)轉(zhuǎn)移圖( 型狀態(tài)轉(zhuǎn)移圖) 對于狀態(tài)n,轉(zhuǎn)入率為 ，轉(zhuǎn)出率為因此有平衡方程： 6.2.1 排隊模型系統(tǒng)的數(shù)量指標(1) 服務臺空閑的概率和服務臺忙的概率：由式（63）可以得到服務臺空閑的概率 ，忙的概率為(

10、2) 系統(tǒng)中顧客數(shù)的期望值 L： （6-4）或 （6-5）6.2.1 排隊模型(3)排隊等待服務顧客數(shù)的期望值 （6-6）或 （6-7）(4)顧客在系統(tǒng)中排隊等待時間的期望值 （6-8） 6.2.1 排隊模型(5)顧客在系統(tǒng)中逗留時間的期望值W （6-9）本模型中最主要的四個指標公式歸納如下： （6-10） 6.2.1 排隊模型四個指標L，L ，W，W 之間的關系（1）里特公式從（610）很容易得到： （6-11） 6.2.1 排隊模型（2）里特公式的擴展設 是平均每單位時間進入系統(tǒng)的顧客數(shù)，稱 為有效到達率。里特證明了在很寬的條件下都有以下關系式：里特公式就變成： （6-12） 6.2.1

11、排隊模型 例 61 某理發(fā)店只有一個理發(fā)師，每小時平均有4個顧客到來，為一個顧客服務所需平均時間為6分鐘。到達人數(shù)服從泊松分布，服務時間服從負指數(shù)分布，求：（1）理發(fā)店空閑和忙的概率。（2）顧客在店內(nèi)平均逗留時間。（3）顧客在店內(nèi)必須消耗15分鐘以上的概率。（4）店內(nèi)至少有一個顧客的概率。 6.2.1 排隊模型 分析：依題知此題為 型， (1)理發(fā)店空閑的概率(2)顧客在店內(nèi)平均逗留時間 (3)由于達到間隔和服務時間均服從指數(shù)分布，所以顧客在系統(tǒng)內(nèi)的逗留時間也服從指數(shù)分布。已知平均逗留時間為 ，則逗留時間T的概率密度為 所以(4)店內(nèi)至少有一個顧客的概率相當于店內(nèi)忙的概率，為0.4。 6.2.

12、1 排隊模型 例 62 設有一單管汽車加油站，平均20分鐘有一輛汽車來加油，每輛汽車平均需要15分鐘。假設此為 型，希望有足夠的停車位置給前來加油的汽車停放，要求沒有位置停車的概率不超過0.01。試問至少準備多少個汽車停車等待的位置？ 6.2.1 排隊模型 分析：設應準備N個汽車停車的等待位置，依題意知：在加油站中不超過N+1輛汽車的概率應不小于0.99，即要求取對數(shù)又因為 所以 ，故 ，即至少準備14個汽車停車等待位置。6.2.1 排隊模型 分析：設應準備N個汽車停車的等待位置，依題意知：在加油站中不超過N+1輛汽車的概率應不小于0.99，即要求取對數(shù)又因為 所以 ，故 ，即至少準備14個汽

13、車停車等待位置。6.2.1 排隊模型 排隊模型圖6-3 排隊模型 6.2.2 排隊模型和 排隊模型系統(tǒng)穩(wěn)定概率的計算 P0 P1 P2 PN-1 PN 圖64 型狀態(tài)轉(zhuǎn)移圖對于任一狀態(tài)，轉(zhuǎn)移率等于轉(zhuǎn)出率，可求得系統(tǒng)的穩(wěn)態(tài)概率為 （6-13） 6.2.2 排隊模型和 排隊模型系統(tǒng)的數(shù)量指標（1）服務臺閑的概率和服務臺忙的概率：由式（613）可以得到服務臺閑的概率為 ，忙的概率為 （2）系統(tǒng)中顧客數(shù)的期望值6.2.2 排隊模型和 排隊模型 顧客數(shù)為N時，有效到達率為：利用式（612）里特公式得： （6-14）6.2.2 排隊模型和 排隊模型 型的數(shù)量指標如下 （6-15）6.2.2 排隊模型和 排

14、隊模型 例6-3 為開辦一個小型汽車加油站，只設一處加油點，需要決定等待汽車使用場地的大小，設需要加油的汽車到達為泊松過程，平均每4分鐘到達1輛，加油時間服從指數(shù)分布，平均每3分鐘完成1輛。如果要求因等待場地不足而轉(zhuǎn)向其它加油站的汽車占需加油汽車的比例接近7時，應修建幾輛汽車使用場地？ 6.2.2 排隊模型和 排隊模型 分析：依題意知 并設應修建N輛汽車使用場地，由公式知又因為轉(zhuǎn)向其它加油站的汽車數(shù)與到達加油汽車的比例為 ，而 ，所以 計算結果如表62所示，由此可知應修建5輛汽車使用場地。表62 例63 計算結果6.2.2 排隊模型和 排隊模型 排隊模型圖65 排隊模型6.2.2 排隊模型和

15、排隊模型系統(tǒng)穩(wěn)態(tài)概率的計算 P0 P1 P2 Pn Pm 圖66 排隊模型系統(tǒng)的穩(wěn)態(tài)概率為 （6-16）6.2.2 排隊模型和 排隊模型系統(tǒng)的數(shù)量指標 設各個顧客的到達概率都是相同的 ，系統(tǒng)中顧客的有效到達率 又由于 ，所以 ，解之得 ，其它指標可由里特公式得到，歸納如下： （6-17）6.2.2 排隊模型和 排隊模型 例64 某工廠擁有許多同類型的自動機，已知每臺機器的正常運轉(zhuǎn)時間服從平均數(shù)為2小時的指數(shù)分布，工廠看管一臺機器的時間服從平均數(shù)為12分鐘的指數(shù)分布，每個人只能看管自己的機器，工廠要求每臺機器的正常運轉(zhuǎn)時間不得少于87.5%。問在這條件下每個工人最多能看管幾臺機器？6.2.2 排

16、隊模型和 排隊模型 分析：設每個工廠最多能夠看管m臺機器，則就成為排隊模型，且 ，那么機器平均故障臺數(shù) ，而 ，根據(jù)要求出現(xiàn)故障的機器數(shù) ，當m=1，2，3，4，5時計算結果如表63所示。結算結果為四臺。 表63 例64計算結果表6.2.2 排隊模型和 排隊模型 6.3.1 排隊模型 圖6-7 排隊模型 此模型是顧客按泊松過程到達，服務服從負指數(shù)分布，C個服務臺，系統(tǒng)容量和顧客源均無限，屬于等待制。6.3 多服務臺指數(shù)分布排隊系統(tǒng)系統(tǒng)穩(wěn)態(tài)概率的計算 P0 P1 P2 PC Pn 圖6-8 型狀態(tài)轉(zhuǎn)移圖可以求出系統(tǒng)穩(wěn)態(tài)的概率為 （6-18）6.3.1 排隊模型系統(tǒng)的數(shù)量指標則有 ，對那如下： （

17、6-19） 6.3.1 排隊模型 例65 某維修部有兩個維修工人，需要修理的電器到達服從泊松分布，維修電器時間服從指數(shù)分布，電器平均每小時到達20臺，平均每5分鐘修理1臺，已知每臺電器停工一分鐘的平均損失費2元，試問電器站平均每臺電器損失多少？ 分析：先求一臺電器在維修部的平均逗留時間。由題意知 由 ，而 ，代入數(shù)據(jù)得W=16.34分鐘。所以電器站平均每臺電器損失16.342=32.68元。 6.3.1 排隊模型M/M/C模型系統(tǒng)與M/M/1的比較 例66 某紡織廠的織布機車間有兩個布機維修組，它們分別負責各自承包的那部分布機的維修。若每一部分布機平均每天有4臺布機需要維修，而每組平均每一天可

18、維修5臺布機。那么，是兩組分別負責各自承包的那部分布機的維修效率高呢，還是兩組合在一起共同負責這一車間的布機的維修效率高呢？也就是說，應建立一個單隊多服務臺系統(tǒng)，還是建立兩個單隊單服務臺系統(tǒng)？（見圖69）。 圖69 (a)單隊多服務臺 (b)單隊單服務臺6.3.1 排隊模型 分析：對于兩個單隊系統(tǒng) 等待時間 （天） 對于單隊多服務臺系統(tǒng) （天） 顯然單隊多服務臺系統(tǒng)比多個單隊單服務臺系統(tǒng)的工作效率大為提高，由于單隊多服務臺系統(tǒng)的等待時間小于多個單隊單服務臺系統(tǒng)的等待時間。6.3.1 排隊模型6.3.2 和 排隊模型 運用“嵌入馬爾可夫鏈”方法推導出對于任意一種服務時間分布，排隊系統(tǒng)中顧客數(shù)的期

19、望值L有下列關系： （6-20）這就是樸拉切克欣欽（Pollazakkhintchine）公式，它是排隊論中最重要的公式之一。根據(jù)這個公式，不論何種服務時間分布，只要知道 ，E(T)，和Var(T)，那么在泊松輸入的系統(tǒng)中，就可以求出排隊系統(tǒng)中顧客數(shù)的期望值，再利用里特公式。可求出 等數(shù)量指標。6.4 一般服務時間的排隊系統(tǒng) 如果服務時間服從k階愛爾朗分布 ，利用公式（6-20）可得 （6-21）如果服務時間是確定的常數(shù) 則有 （6-22）6.4 一般服務時間的排隊系統(tǒng) 圖6-10 服務水平關系圖 一般情形下，提高服務水平(數(shù)量，質(zhì)量) 會降低顧客的等待費用(損失)，但卻常常增加了服務機構的成

20、本最優(yōu)化的目標之一是使二者費用之和為最小，并確定達到這個目標的最優(yōu)的服務水平。另一個常用目標是使純收入或利潤(服務收入與服務成本之差)為最大。6.5 排隊系統(tǒng)的優(yōu)化 模型中最優(yōu)的總費用其中 表示每增大1單位的 所需的單位時間服務費用； 表示每個顧客在系統(tǒng)中停留單位時間的費用。將 代入上式得 ，為求極小值，令求得最優(yōu)的 ，由知 為最小值。 6.5.1 M/M/1的最優(yōu)服務率 例69 興建一座港口碼頭，只有一個裝卸船員的裝置，要求設計裝卸能力用每日裝卸的船數(shù)表示。已知單位裝卸能力每日平均耗費生產(chǎn)費用a=2千元，船只到港后如不能及時裝卸，停留一日損失運輸費b=1.5千元，預計船的平均到達率是。該船只

21、到達時間間隔和裝卸時間均服從負指數(shù)分布，問港口裝卸能力多大時，每天的總支出最少？ 分析：依題意知， ，即 ，由式（623）得則最優(yōu)裝卸能力為每日裝5只。6.5.1 M/M/1的最優(yōu)服務率 模型中最優(yōu)的總費用令 得 此式是一個關于 的高次方程，要解出 是比較困難的，所以通常用數(shù)值計算來求得 或用圖形法近似求出 。6.5.1 M/M/1的最優(yōu)服務率 模型中最優(yōu)的總費用 ，令 得其中 由上式解出 很困難，通常利用泊松分布表通過數(shù)值計算來求得或圖形法近似求出 。 6.5.1 M/M/1的最優(yōu)服務率 總費用函數(shù)為 其中必須有為求最優(yōu)的 ，采用邊際分析法。由得：依次求 時L的值，并做兩相鄰的L值之差，因為

22、 為已知數(shù)，根據(jù)這個數(shù)落在哪個不等式的區(qū)間里就可定出最優(yōu)值 。6.5.2 模型中最優(yōu)的服務臺 例610 某健康檢測中心為人檢查身體的健康狀況，來檢查的人平均到達率為48人次/天，每次來檢查由于請假等原因帶來的損失為6元，檢查時間服從負指數(shù)分布，平均服務率 為25人次/天，每安排一位醫(yī)生的服務成本為每天4元，問應安排幾位醫(yī)生（設備）才能使總費用最?。?分析：由題意知，首先，須滿足 解得 。又因為而6.5.2 模型中最優(yōu)的服務臺 令 將已知數(shù)據(jù)代入上面兩個式子，算得結果如下表所示： 表65 例610計算結果因為 ，故由及以上計算結果可知：故 ，即安排3位醫(yī)生可使總費用最小。6.5.2 模型中最優(yōu)的服務臺 問題的提出：某市準備在市中心設立一家銀行。已知顧客的到達服從泊松分布，顧客平均到達率為0.33人/分。