數(shù)學建模排隊模型2015-7-12

1、排隊模型及其應用中北大學理學院數(shù)學學科張張 峰峰數(shù)學建模暑期培訓系列講座排隊模型簡介排隊模型簡介經(jīng)典排隊模型經(jīng)典排隊模型布傳播的風險因素以及動力學建模布傳播的風險因素以及動力學建模 123推廣的排隊模型推廣的排隊模型34排隊系統(tǒng)的優(yōu)化排隊系統(tǒng)的優(yōu)化1 排隊模型排隊模型簡介簡介 （背景）（背景）超市排隊為什么不多開個窗口銀行排隊1 排隊模型排隊模型簡介簡介 （背景）（背景）服務效率忒低購票排隊哥 要 回 家1 排隊模型排隊模型簡介簡介 （背景）（背景）高速公路車輛排隊Where is the toilet?1 排隊模型排隊模型簡介簡介 （背景）（背景）壯哉！壯哉！購票排隊1 排隊模型排隊模型簡介

2、簡介 （背景）（背景）呼叫中心排隊1 排隊模型排隊模型簡介簡介 （背景）（背景）9為什么會出現(xiàn)排隊現(xiàn)象？為什么會出現(xiàn)排隊現(xiàn)象？假定每小時平均有假定每小時平均有4位顧客到達，服務人員為每位顧客的平均服務時間位顧客到達，服務人員為每位顧客的平均服務時間為為15分鐘。如果顧客到達的間隔時間正好是分鐘。如果顧客到達的間隔時間正好是15分鐘，而服務人員為每位顧分鐘，而服務人員為每位顧客的服務時間也正好是客的服務時間也正好是15分鐘，那么，就只需要一名服務人員，顧客也根分鐘，那么，就只需要一名服務人員，顧客也根本用不著等待。本用不著等待。 在以下情況將出現(xiàn)排隊現(xiàn)象：在以下情況將出現(xiàn)排隊現(xiàn)象： 平均到達率高

3、于平均服務率平均到達率高于平均服務率 顧客到達的間隔時間不一樣（隨機）顧客到達的間隔時間不一樣（隨機） 服務時間不一樣（隨機）服務時間不一樣（隨機）顧客離開顧客離開顧客顧客顧客排隊顧客排隊服務設施服務設施1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念） 排隊論排隊論(Queuing Theory)，又稱隨機服務隨機服務系統(tǒng)系統(tǒng)是一門研究擁擠現(xiàn)象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎上，解決相應排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制問題。 每個顧客的等待時間多長？每個顧客的等待時間多長？ 選擇哪個隊列時間最短？選擇哪個隊列時間最短？ 多開一個窗口？多開一個窗口？ 顧客

4、消費收入與超市成本之間博弈顧客消費收入與超市成本之間博弈 怎樣設計最優(yōu)怎樣設計最優(yōu) ；最優(yōu)運行（）；最優(yōu)運行（）排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述一、排隊模型的描述相似的特征及數(shù)學抽象相似的特征及數(shù)學抽象顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客提供服務的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是隨機的，因此排隊論排隊論又稱為隨機服務系統(tǒng)隨機服務系統(tǒng)顧客顧客-請求服務的人或者物服務員或服務臺服務員或服務臺-為顧客服務的人或者物排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述（組成）一、排隊

5、模型的描述（組成）基本排隊過程基本排隊過程排隊系統(tǒng)一般有三個基本組成部分：排隊系統(tǒng)一般有三個基本組成部分：1.輸入過程；輸入過程；2.排隊規(guī)則；排隊規(guī)則；3.服務機構服務機構排隊結構服務機構顧客源顧客到達排隊規(guī)則服務規(guī)則離去圖1 排 隊系統(tǒng)示意圖排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述（組成）一、排隊模型的描述（組成）基本排隊過程基本排隊過程1.輸入過程輸入過程 顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也把它稱為把它稱為顧客流顧客流（1 1）顧客顧客總數(shù)總數(shù) 有限有限 無限？無限？ （2 2）

6、到達方式到達方式 單個單個 成批？成批？ （3 3）顧客流的概率分布族顧客流的概率分布族 相繼到達的顧客間的概率分布相繼到達的顧客間的概率分布排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述（組成）一、排隊模型的描述（組成）基本排隊過程基本排隊過程2. 排隊規(guī)則排隊規(guī)則 服務臺以怎樣的順序和方式服務顧客服務臺以怎樣的順序和方式服務顧客（1 1）損失制損失制 如果顧客到達排隊系統(tǒng)時，所有服務臺都已被先來的如果顧客到達排隊系統(tǒng)時，所有服務臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)顧客占用，那么他們就自動離開系統(tǒng)。（2 2）等待制等待制 當顧客來到

7、系統(tǒng)時，所有服務臺都不空，顧客加入排隊當顧客來到系統(tǒng)時，所有服務臺都不空，顧客加入排隊行列等待服務行列等待服務 FCFS LCFS PR RO（3 3）混合制混合制 等待制與損失制等待制與損失制的混合的混合 一般是指允許排隊，但又不一般是指允許排隊，但又不允許隊列無限長下去允許隊列無限長下去排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述（組成）一、排隊模型的描述（組成）基本排隊過程基本排隊過程3. 服務機構服務機構（1 1）服務臺數(shù)量及構成方式服務臺數(shù)量及構成方式 單服務臺單服務臺 多服務臺；多服務臺；（2 2）服務方式服務方式 單個服務，批量

8、服務；單個服務，批量服務；（3 3）服務時間的概率分布服務時間的概率分布 服務過程是泊松過程？高斯過程？服務過程是泊松過程？高斯過程？一個顧客的服務時間是指數(shù)分布還是一般概率分布？一個顧客的服務時間是指數(shù)分布還是一般概率分布？排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述（組成）一、排隊模型的描述（組成）基本排隊過程基本排隊過程3. 服務機構服務機構 （結構）（結構）單隊多服務臺并聯(lián)單隊多服務臺并聯(lián) 例如例如 學校內(nèi)的一些小超市學校內(nèi)的一些小超市排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述（組

9、成）一、排隊模型的描述（組成）基本排隊過程基本排隊過程3. 服務機構服務機構 （結構）（結構）單隊多服務臺并聯(lián)單隊多服務臺并聯(lián) （銀行排隊）（銀行排隊）排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排隊模型的描述（組成）一、排隊模型的描述（組成）基本排隊過程基本排隊過程3. 服務機構服務機構 （結構）（結構）多隊多服務臺并聯(lián)多隊多服務臺并聯(lián) 大型超市、火車站窗口、醫(yī)院窗大型超市、火車站窗口、醫(yī)院窗口、口、 高速公路收費、高速公路收費、 多車道路口車輛通行等多車道路口車輛通行等排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）一、排

10、隊模型的描述（組成）一、排隊模型的描述（組成）基本排隊過程基本排隊過程3. 服務機構服務機構 （結構）（結構）單隊列多服務臺串聯(lián)單隊列多服務臺串聯(lián) 柔性制造業(yè)柔性制造業(yè) 產(chǎn)品按工序加工產(chǎn)品按工序加工 排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）二、建模過程及主要指標二、建模過程及主要指標 1 排隊系統(tǒng)的統(tǒng)計推斷排隊系統(tǒng)的統(tǒng)計推斷 確定或擬合排隊系統(tǒng)顧客到達的時間間隔分布和服務時間分布確定或擬合排隊系統(tǒng)顧客到達的時間間隔分布和服務時間分布。2 模型的性態(tài)模型的性態(tài)在確定模型的基礎上，求解主要性能指標，如隊長分布、等在確定模型的基礎上，求解主要性能指標，如隊長分布

11、、等待時間分布。待時間分布。3 模型進行優(yōu)化模型進行優(yōu)化系統(tǒng)的最優(yōu)設計（系統(tǒng)的最優(yōu)設計（參數(shù)選擇，服務質(zhì)量評價）如機場跑道數(shù)量，呼參數(shù)選擇，服務質(zhì)量評價）如機場跑道數(shù)量，呼 叫中心坐席量。叫中心坐席量。已有系統(tǒng)的最優(yōu)控制已有系統(tǒng)的最優(yōu)控制 如從顧客和服務機構雙方利益出發(fā)，對排隊如從顧客和服務機構雙方利益出發(fā)，對排隊系統(tǒng)進行最優(yōu)控制系統(tǒng)進行最優(yōu)控制排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）二、建模過程及主要指標二、建模過程及主要指標 1 隊長隊長: 系統(tǒng)中的顧客數(shù)系統(tǒng)中的顧客數(shù), 平均隊長平均隊長LS 等待隊長等待隊長 : 系統(tǒng)中排隊等待服務的顧客數(shù)系統(tǒng)中排隊

12、等待服務的顧客數(shù), 平均等待隊長平均等待隊長Lq 系統(tǒng)系統(tǒng)中顧中顧客客 數(shù)數(shù)在隊列中等在隊列中等待服務的顧待服務的顧客數(shù)客數(shù)正 被 服正 被 服務 的 顧務 的 顧客數(shù)客數(shù)+=一般情形，一般情形，Ls(或或Lq)越大，說明服務效率越低。越大，說明服務效率越低。排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）二、建模過程及主要指標二、建模過程及主要指標2. 逗留時間逗留時間:一個顧客在系統(tǒng)中的停留時間一個顧客在系統(tǒng)中的停留時間,平均逗留時間平均逗留時間 WS等待時間等待時間: 一個顧客排隊等待的時間一個顧客排隊等待的時間,平均等待時間平均等待時間Wq等待時間等待時間

13、服務時間服務時間+逗留時間逗留時間= =顯然，顯然，Ws(或或Wq)越大，顧客滿意度越低。越大，顧客滿意度越低。排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）二、建模過程及主要指標二、建模過程及主要指標 3. 忙期忙期：從顧客到達空閑服務機構起到服務機構再次為從顧客到達空閑服務機構起到服務機構再次為空閑這段時間長度?？臻e這段時間長度?？梢院饬糠諜C構效率的指標，及可以衡量服務機構效率的指標，及工作強度工作強度4. 絕對通行能力絕對通行能力：單位時間內(nèi)被服務完的平均顧客數(shù)：單位時間內(nèi)被服務完的平均顧客數(shù)5. 相對通行能力相對通行能力：單位時間內(nèi)被服務完顧客數(shù)與請求

14、服：單位時間內(nèi)被服務完顧客數(shù)與請求服務的顧客數(shù)之比務的顧客數(shù)之比6. 平均被占服務臺數(shù)平均被占服務臺數(shù) 7 損失率損失率 排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）三、排隊模型應用三、排隊模型應用從從2020世紀世紀6060年代至今年代至今 對業(yè)務突發(fā)性和帶有各種網(wǎng)絡協(xié)議控制的通信系統(tǒng)進行對業(yè)務突發(fā)性和帶有各種網(wǎng)絡協(xié)議控制的通信系統(tǒng)進行性能評價、仿真及模擬性能評價、仿真及模擬。2020世紀初期世紀初期 主要研究應用于電話網(wǎng)和遠程通信系統(tǒng)等無隊列的排隊主要研究應用于電話網(wǎng)和遠程通信系統(tǒng)等無隊列的排隊系統(tǒng)系統(tǒng)( (損失制損失制) )2020世紀中期世紀中期 主要

15、研究通信系統(tǒng)中有隊列主要研究通信系統(tǒng)中有隊列( (等待制等待制) )的排隊系統(tǒng)和排隊網(wǎng)絡的排隊系統(tǒng)和排隊網(wǎng)絡排隊模型排隊模型簡介簡介1 排隊模型排隊模型簡介簡介 （基本概念）（基本概念）三、排隊模型應用三、排隊模型應用2005 2005 研究生建模研究生建模 出租車最佳數(shù)量預測出租車最佳數(shù)量預測20002005 20002005 智能地雷反坦克研究，滅火兵力部署智能地雷反坦克研究，滅火兵力部署19902000 19902000 碼頭與船舶的分配，工程土方的創(chuàng)新，停車場面碼頭與船舶的分配，工程土方的創(chuàng)新，停車場面積的計算，圖書館信息處理積的計算，圖書館信息處理20052010 20052010

16、公廁建筑面積的分配，教務處教務員崗位確定公廁建筑面積的分配，教務處教務員崗位確定 新的前沿應用新的前沿應用 社交網(wǎng)絡性能社交網(wǎng)絡性能 評估評估 云計算性能指標估計等云計算性能指標估計等1 排隊模型排隊模型簡介簡介三、排隊模型應用三、排隊模型應用20092009眼科醫(yī)院病床合理安排眼科醫(yī)院病床合理安排提高醫(yī)療體系的服務效率，提高資源利用率，提高病人滿意度以及緩解患者于醫(yī)院之間的矛盾；提出了一些具體的優(yōu)化標準如下：1、以費用作為優(yōu)化指標計算最優(yōu)目標值條件下最優(yōu)的服務水平：總費用= 排隊損失費+ 服務費 2、“優(yōu)先權選擇或等級”來優(yōu)化醫(yī)院服務 （眼科醫(yī)院病床）3、構造合理的調(diào)度方式來進行優(yōu)化4、建立

17、了“預留病床模型，逐步優(yōu)先權就診模式”1 排隊模型排隊模型簡介簡介三、排隊模型應用三、排隊模型應用20132013年年 A A題題 車道被占用對城市道路通行能力的影響車道被占用對城市道路通行能力的影響 （1） 研究公交車發(fā)車間隔與排隊長度 （2）研究停車場的車輛排隊 （3）研究車輛排隊現(xiàn)象、車輛延誤 路口通行能力分析 2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型一 單服務臺 排隊模型1 標準的標準的 模型模型1/MM2 模型條件模型條件 模型模型 表示，顧客到達過程服從泊松分布，表示，顧客到達過程服從泊松分布，服務時間服從負指數(shù)分布，單服務臺，隊長和顧客來源無服務時間服從負指數(shù)分布，單服務臺，

18、隊長和顧客來源無限限.簡記為簡記為 ./1/ MM1/ MM1）已知單位時間平均到達率）已知單位時間平均到達率 和平均服務率和平均服務率 .2）系統(tǒng)容量無限，顧客源總數(shù)無限）系統(tǒng)容量無限，顧客源總數(shù)無限.3）排隊規(guī)則為單隊，先到先服務）排隊規(guī)則為單隊，先到先服務)(1/MM2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型一 單服務臺 排隊模型3 模型的求解模型的求解1/MM1/MM 研究研究系統(tǒng)狀態(tài)的概率系統(tǒng)狀態(tài)的概率- - 系統(tǒng)中顧客數(shù)。狀態(tài)概率用系統(tǒng)中顧客數(shù)。狀態(tài)概率用Pn( (t) )表表示示, ,即在即在t時刻系統(tǒng)中有時刻系統(tǒng)中有n個顧客的概率，也稱瞬態(tài)概率。個顧客的概率，也稱瞬態(tài)概率。

19、實際中更關心實際中更關心 穩(wěn)態(tài)概率穩(wěn)態(tài)概率 limnntPP t穩(wěn)態(tài)概率求法穩(wěn)態(tài)概率求法 馬爾科夫鏈理論馬爾科夫鏈理論 母函數(shù)母函數(shù) 遞推等遞推等穩(wěn)態(tài)概率求解步驟穩(wěn)態(tài)概率求解步驟 1 畫出穩(wěn)態(tài)概率轉(zhuǎn)移圖畫出穩(wěn)態(tài)概率轉(zhuǎn)移圖 2 列出穩(wěn)態(tài)概率平衡方程組列出穩(wěn)態(tài)概率平衡方程組3 求出穩(wěn)態(tài)概率或者母函數(shù)求出穩(wěn)態(tài)概率或者母函數(shù)2排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型一 單服務臺 排隊模型1/MM系統(tǒng)在穩(wěn)定情況下的狀態(tài)轉(zhuǎn)移如圖系統(tǒng)在穩(wěn)定情況下的狀態(tài)轉(zhuǎn)移如圖圖1.1Pn 1P2P1P0PnPn 1 可以得到如下平衡方程可以得到如下平衡方程：nnnPPP11（1.1）01PP（1.2）4 穩(wěn)態(tài)概率公式穩(wěn)態(tài)概

20、率公式2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型一 單服務臺 排隊模型1/MM5 5 模型的數(shù)量指標公式模型的數(shù)量指標公式由（1.1）和（1.2）可以遞推求解，01PP02102)()1 (-PPPP.0)(PPnn.nnPP110式中 表示平均到達率與平均服務率之比，稱為服務強度.2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型一 單服務臺 排隊模型1/MM6 模型的性能指標模型的性能指標 1）在系統(tǒng)里沒有顧客的概）在系統(tǒng)里沒有顧客的概率率2011111LPLPnPPnLnnnnnnq10P000)1 ()1 (nqnnnnnsLkknPL2）平均排隊的顧客數(shù)平均排隊的顧客數(shù) 3）在系統(tǒng)里的平

21、均顧客數(shù)）在系統(tǒng)里的平均顧客數(shù)u2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型一 單服務臺 排隊模型1/MM 4 4）一位顧客花在系統(tǒng)里的平均逗留時間）一位顧客花在系統(tǒng)里的平均逗留時間1)(XEWs 5 5）一位顧客花在排隊上的平均時間（等于逗留時間減去服）一位顧客花在排隊上的平均時間（等于逗留時間減去服 務時間）務時間） 6 6）顧客到達系統(tǒng)時，得不到及時的服務，必須等待服務的）顧客到達系統(tǒng)時，得不到及時的服務，必須等待服務的 概率概率 7 7）系統(tǒng)里正好有）系統(tǒng)里正好有 個顧客的概率個顧客的概率1qsWW 01wPP 0)(PPnnn6 模型的性能指標模型的性能指標2 排隊模型排隊模型經(jīng)典排

22、隊模型經(jīng)典排隊模型一 單服務臺 排隊模型 應用舉例應用舉例 1/MM庫存問題庫存問題 進貨多，保管費用大；存貨不足缺貨會引起經(jīng)濟進貨多，保管費用大；存貨不足缺貨會引起經(jīng)濟損失，假設貨物需求量是參數(shù)為損失，假設貨物需求量是參數(shù)為 的泊松過程，生產(chǎn)一個的泊松過程，生產(chǎn)一個產(chǎn)品實際是參數(shù)為產(chǎn)品實際是參數(shù)為 的指數(shù)分布，單位時間庫存費用的指數(shù)分布，單位時間庫存費用c元，元，缺貨一個產(chǎn)品損失為缺貨一個產(chǎn)品損失為h元，確定最優(yōu)庫存使得庫存費和損失元，確定最優(yōu)庫存使得庫存費和損失費之和達到最小費之和達到最小.分析分析 將生產(chǎn)廠看成服務機構，需求看成輸入流將生產(chǎn)廠看成服務機構，需求看成輸入流 M/M/1 排隊

23、排隊平均缺貨數(shù)平均缺貨數(shù)11squenn sEns p平均庫存數(shù)平均庫存數(shù)1011sscunnnEsn ps2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型一 單服務臺 排隊模型 應用舉例應用舉例 1/MM分析分析 將生產(chǎn)廠看成服務機構，需求看成輸入流將生產(chǎn)廠看成服務機構，需求看成輸入流 M/M/1 排隊排隊單位時間總費用單位時間總費用 1111sscunquef scEhEc sh由邊際分析法由邊際分析法 1f sf s 1f sf s由邊際分析法由邊際分析法scch1scch最佳最佳s滿足滿足ln/ln1ln/lnccschch 36例例一個碼頭，設待卸貨船到達時間間隔服從負指數(shù)一個碼頭，設待

24、卸貨船到達時間間隔服從負指數(shù)分布，平均到達分布，平均到達 2 艘艘/小時；服務臺是小時；服務臺是1臺吊車，卸臺吊車，卸貨時間服從負指數(shù)分布，平均每貨時間服從負指數(shù)分布，平均每 20 分鐘可卸一艘分鐘可卸一艘貨船，當被占用時，新到貨船只能停在碼頭等待。貨船，當被占用時，新到貨船只能停在碼頭等待。求在平穩(wěn)狀態(tài)下碼頭上貨船的平均數(shù)；等待卸貨求在平穩(wěn)狀態(tài)下碼頭上貨船的平均數(shù)；等待卸貨船只的平均數(shù)；每艘貨船在碼頭的平均停留時間；船只的平均數(shù)；每艘貨船在碼頭的平均停留時間；貨船平均需等待多長時間可以開始卸貨。貨船平均需等待多長時間可以開始卸貨。2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型37解：解：這是一

25、個典型的這是一個典型的M/M/1排隊排隊問題問題213r260320u 22()32sLu艘24233qsLLr(艘)423()23LqWq小時21()2LsWs小時2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型38例例某醫(yī)院手術室根據(jù)病人就診和完成手術時間某醫(yī)院手術室根據(jù)病人就診和完成手術時間的記錄，任意抽查的記錄，任意抽查100個工作小時，每小時個工作小時，每小時來就診的病人數(shù)來就診的病人數(shù)n的出現(xiàn)次數(shù)如表的出現(xiàn)次數(shù)如表6所示。又所示。又任意抽查了任意抽查了100個完成手術的病例，所用時個完成手術的病例，所用時間間t出現(xiàn)的次數(shù)如下表所示。試分別用公式、出現(xiàn)的次數(shù)如下表所示。試分別用公式、ex

26、cel和仿真求解：和仿真求解：2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型39 到達病人數(shù)到達病人數(shù) n出現(xiàn)次數(shù)出現(xiàn)次數(shù) f n0101282293164105661合計合計100到達病人數(shù)到達病人數(shù)為病人完成手術為病人完成手術時間時間t/小時小時出現(xiàn)次數(shù)出現(xiàn)次數(shù) ft 0.00.2380.20.4250.40.6170.6 1.890.81.061.01.251.20合計合計100手術時間手術時間2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型40解：解：這也是一個這也是一個M/M/1排隊排隊問題問題（1）計算平均到達率）計算平均到達率2.1(/)100nnf人 時 平均手術時間平均手術時間0.

27、4()100ttfT 時/人 平均服務率平均服務率12.5()0.4u 人/時2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型41（2）取）取=2.1，=2.5，通過統(tǒng)計檢驗方法認為病人到達，通過統(tǒng)計檢驗方法認為病人到達數(shù)服從參數(shù)為數(shù)服從參數(shù)為2.1的泊松分布，手術時間服從參數(shù)為的泊松分布，手術時間服從參數(shù)為2.5的指數(shù)分布。的指數(shù)分布。（3）服務設備利用率服務設備利用率2.10.842.5這說明服務機構（手術室）有這說明服務機構（手術室）有84%的時間是繁忙的時間是繁忙的的（被利用），有（被利用），有16%的時間是空閑的。的時間是空閑的。420.84ru2.12.5u 2.15.25()2.52

28、.1sLu人5.250.844.41qsLLr(人)4.412.1()2.1LqWq小時5.252.5()2.1LsWs小時（4）依次帶入公式，算出各指標得：依次帶入公式，算出各指標得：43單通道單通道Excel求解求解2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型二二 多服務臺 排隊模型1 標準的標準的 模型模型/M M c2 模型描述模型描述 模型模型 表示，顧客到達過程服從泊松分布，服表示，顧客到達過程服從泊松分布，服務時間服從負指數(shù)分布，務時間服從負指數(shù)分布，C 個服務臺，隊長和顧客來源無個服務臺，隊長和顧客來源無限限./MMC/M M C 已知單位時間平均到達率已知單位時間平均到達率

29、， C 個服務臺，每個服務臺個服務臺，每個服務臺的工作相互獨立且平均服務率相同，都等于的工作相互獨立且平均服務率相同，都等于 ，顧客源無限，顧客源無限，容量無限，排隊規(guī)則為等待制容量無限，排隊規(guī)則為等待制3.系統(tǒng)的狀態(tài)概率和主要運行指標系統(tǒng)的狀態(tài)概率和主要運行指標)1(n)1(nn20P2P1P1nPnP1nP,)(,)1(,111101cnnnnnPcPcPPnPPnPP）（),.,2, 1(cn ,.)2, 1(ccn(1) 系統(tǒng)的狀態(tài)概率系統(tǒng)的狀態(tài)概率系統(tǒng)的空閑概率4 系統(tǒng)的狀態(tài)概率和主要運行指標系統(tǒng)的狀態(tài)概率和主要運行指標系統(tǒng)內(nèi)有n個顧客的概率CnPCCCnPnPnCnnn00)(!1

30、)(!11100)(11!1)(!1CkCkCkP1C2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型二二 多服務臺 排隊模型4 主要運行指標主要運行指標/M M C02()!(1)1cqqqqqcLPLLcLLWWW系統(tǒng)平均隊長、平均等待時間平均占用服務臺數(shù)K系統(tǒng)通行能力 0LP損失率系統(tǒng)相對通過能力11LQP系統(tǒng)絕對通過能力AQ48例例某售票所有三個窗口，顧客的到達服從泊松分布，某售票所有三個窗口，顧客的到達服從泊松分布，平均到達速率平均到達速率 = 0.9人人/min；售票時間服從負指；售票時間服從負指數(shù)分布，平均服務速率數(shù)分布，平均服務速率= 0.4人人/min ?，F(xiàn)設顧客到?，F(xiàn)設顧客到達

31、后排成一隊，依次向空閑的窗口購票，如圖所達后排成一隊，依次向空閑的窗口購票，如圖所示。試分別用公式、示。試分別用公式、excel和仿真求解：和仿真求解：u(1) 整個售票所空閑概率整個售票所空閑概率u(2) 平均隊列長和平均隊長平均隊列長和平均隊長u(3)平均等待時間和逗留時間平均等待時間和逗留時間u(4)顧客到達后必須等待的概率（顧客到達后必須等待的概率（n3)2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型49顧客到達和服務圖顧客到達和服務圖 顧客離去 排隊 = 0.9 顧客到達 窗口1 = 0.4 窗口2 = 0.4 窗口3 = 0.42 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型50解：解：

32、這是一個典型的這是一個典型的M/M/C 排隊排隊問題問題0.90.75130.4C0.90.4u (1) 整個售票所空閑概率整個售票所空閑概率r1100!(1)nccnrrPnc012352.2510!1!2!3!10.750.07482 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型51(2) 平均排隊長度和平均隊列長平均排隊長度和平均隊列長02!(1)cqrLpc322.250.750.07481.703!(10.75)1.702.253.95sqLLr(3)平均等待時間和逗留時間平均等待時間和逗留時間1.701.890.9qqLW111.894.39

33、0.4sqWWu2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型52(4)顧客到達后必須等待的概率（顧客到達后必須等待的概率（n3)331nnPPnP0!nrpn(0)nc01!nncrpccg()nc00.0748P 230(1)(12.252.531)0.07480.4322nrPrP2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型53M/M/3 Excel求解求解54例例 銀行取號系統(tǒng)有用嗎？銀行取號系統(tǒng)有用嗎？就例就例5，如果其他條件不變，顧客到達后在每個窗，如果其他條件不變，顧客到達后在每個窗口前各排一隊，且進入隊列后堅持不換，就形成口前各排一隊，且進入隊列后堅持不換，就形成3個隊列，如下圖

34、所示。試分別用公式、個隊列，如下圖所示。試分別用公式、excel求解：求解：u(1) 整個售票所空閑概率整個售票所空閑概率u(2) 平均隊列長度和平均隊長平均隊列長度和平均隊長u(3) 平均等待時間和逗留時間平均等待時間和逗留時間u(4)顧客到達后必須等待的概率（顧客到達后必須等待的概率（n3)2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型55顧客到達和服務圖顧客到達和服務圖 顧客離去= 0.3顧客到達 = 0.9窗口1= 0.4窗口2= 0.4窗口3= 0.4= 0.3= 0.32 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型56解：解：這是這是3個個M/M/1同時服務的同時服務的排隊排隊問題問題

35、0.30.7510.4r0.30.4u (1) 整個售票所空閑概率整個售票所空閑概率(每個窗口空閑每個窗口空閑)0110.750.25p(4)顧客到達必須等待的概率（每個窗口顧客到達必須等待的概率（每個窗口n1)10110.250.75npP2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型57(2) 平均排隊長度和平均隊列長平均排隊長度和平均隊列長0.30.7qLu2.250.753sqLLr(3)平均等待時間和逗留時間平均等待時間和逗留時間2.257.50.3qqLW3100.3ssLW339系統(tǒng)（3個窗口）隊長2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型583個個M/M/

36、1 Excel求解求解2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型59結論：銀行取號系統(tǒng)是有效的結論：銀行取號系統(tǒng)是有效的指標指標數(shù)值數(shù)值排隊長度排隊長度1.70系統(tǒng)隊長系統(tǒng)隊長3.95平均排隊時間平均排隊時間1.89服務臺空閑概率服務臺空閑概率0.075顧客必須等待的概率顧客必須等待的概率0.57指標指標數(shù)值數(shù)值排隊長度排隊長度2.25系統(tǒng)隊長系統(tǒng)隊長9平均排隊時間平均排隊時間7.5服務臺空閑概率服務臺空閑概率0.25顧客必須等待的概率顧客必須等待的概率0.752 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型二二 多服務臺 排隊模型/M M C眼科醫(yī)院病床安排眼科醫(yī)院病床安排 2 排隊模型排隊模

37、型經(jīng)典排隊模型經(jīng)典排隊模型眼科醫(yī)院病床安排眼科醫(yī)院病床安排 簡單而言：每一類病人應安排多少床位簡單而言：每一類病人應安排多少床位2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型眼科醫(yī)院病床安排眼科醫(yī)院病床安排 2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型眼科醫(yī)院病床安排眼科醫(yī)院病床安排 2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型二二 多服務臺 排隊模型/M M C車道被占用對城市道路通行能力的影響車道被占用對城市道路通行能力的影響 1 根據(jù)視頻1（附件1），描述視頻中交通事故發(fā)生至撤離期間,事故所處橫斷面實際通行能力的變化過程。 2 根據(jù)問題1所得結論，結合視頻2（附件2），分析說明同一橫斷面交

38、通事故所占車道不同對該橫斷面實際通行能力影響的差異。2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型二二 多服務臺 排隊模型/M M C車道被占用對城市道路通行能力的影響車道被占用對城市道路通行能力的影響2 排隊模型排隊模型經(jīng)典排隊模型經(jīng)典排隊模型二二 多服務臺 排隊模型/M M C車道被占用對城市道路通行能力的影響車道被占用對城市道路通行能力的影響123/3,/1M MM MMM67 排隊系統(tǒng)最優(yōu)設計排隊系統(tǒng)最優(yōu)設計成本分析成本分析1 概述概述排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制，即排隊系排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制，即排隊系統(tǒng)的最優(yōu)化問題，其目的在于使排隊系統(tǒng)達統(tǒng)的最優(yōu)化問題，其目的在于使排隊系統(tǒng)達到

39、到最大效益最大效益或者說在一定指標下使排隊系統(tǒng)或者說在一定指標下使排隊系統(tǒng)最為經(jīng)濟最為經(jīng)濟。3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化68服務成本與等待成本的權衡（成本效益平衡）服務成本與等待成本的權衡（成本效益平衡）總成本成本最佳能力等待成本服務成本最小值排隊分析的目的是使顧客等待成本與服務能力成本這兩項成本之和最小3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化69M/M/1模型中的最優(yōu)服務率模型中的最優(yōu)服務率u 最佳服務能力是使總成本最小化：總成本=顧客等候成本+服務能力成本1wswssCuC uC LCz為時服務機構單位時間的費用為每個顧客在系統(tǒng)中逗即：留時間的費用/1SMMLu

40、模型中 swzC uCu所以：3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化70 M/M/1模型中的最優(yōu)服務率模型中的最優(yōu)服務率u swzC uCu0dzdu令20()swCCu即：所以M/M/1模型的最優(yōu)服務率為：wsCuC3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化71例例設某服務機構，單服務臺，顧客到達率為每設某服務機構，單服務臺，顧客到達率為每小時小時12位顧客。假定每位接受顧客的顧客其位顧客。假定每位接受顧客的顧客其等待費用為每小時等待費用為每小時5元，服務成本為每位顧元，服務成本為每位顧客客2元，欲使總平均費用最小，服務率應為元，欲使總平均費用最小，服務率應為多少？多少？3

41、排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化72解：解：這是一個標準的這是一個標準的M/M/1排隊排隊問題問題2sC元12/ h人5wC元因而swSzC uC L最 小 總 費 用5121217.5(/ h)2wsCuC最優(yōu)服務率人122.1817.512sLu*217.552.1846Z120.68617.5u最 優(yōu) 系 統(tǒng) 利 用 率3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化73、Lq 、Ls三者的關系三者的關系-1當系統(tǒng)利用率增加時，隊列平均等候數(shù)與顧當系統(tǒng)利用率增加時，隊列平均等候數(shù)與顧客排隊等候的平均時間呈指數(shù)增長?？团抨牭群虻钠骄鶗r間呈指數(shù)增長。3 排隊模型排隊模型排隊模型的

42、優(yōu)化排隊模型的優(yōu)化74隊列中平均等 侯數(shù)100% 系統(tǒng)利用率 0、Lq 、Ls三者的關系-2qqLWqW./ 1exMM 3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化75、Lq 、Ls三者的關系三者的關系-3平均隊長（和平均等待時間）與服務臺利用平均隊長（和平均等待時間）與服務臺利用率之間的關系不是線性的關系。資產(chǎn)利用率率之間的關系不是線性的關系。資產(chǎn)利用率太高會造成服務質(zhì)量急速下降，因而要權衡太高會造成服務質(zhì)量急速下降，因而要權衡利弊。利弊。要保證服務質(zhì)量，就必須保持要保證服務質(zhì)量，就必須保持“過剩過剩的的”生產(chǎn)或服務能力。生產(chǎn)或服務能力。3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化

43、76 僅討論標準的僅討論標準的M/M/C模型，且在穩(wěn)態(tài)下，單位時間全部費用模型，且在穩(wěn)態(tài)下，單位時間全部費用的期望值為：的期望值為：(包括服務成本與等待費用包括服務成本與等待費用)zC sCC wL式中式中: : 每個服務臺單位服務時間成本；每個服務臺單位服務時間成本； 每個顧客在系統(tǒng)中停留單位時間成本每個顧客在系統(tǒng)中停留單位時間成本； L系統(tǒng)中顧客的平均數(shù)系統(tǒng)中顧客的平均數(shù)Ls或隊列平均數(shù)或隊列平均數(shù)Lq，是是C的函的函數(shù)數(shù)。這里這里Z是是C的函數(shù)的函數(shù),且且C只能取整數(shù)解只能取整數(shù)解,故不能用微分法求故不能用微分法求C*, 而只而只能用邊際分析法能用邊際分析法(Marginal Analy

44、sis)：CsCw3 排隊模型排隊模型排隊模型的優(yōu)化排隊模型的優(yōu)化77因為因為 z(c*) 是最小值，則有是最小值，則有：) 1 () 1*() 1*(*)(* CLCwCsCCLCwCsC)1*(*)(czcz) 1*(*)(czcz將將z期望費用公式代入：期望費用公式代入：)2() 1*() 1*(*)(* CLCwCsCCLCwCsC*)()1*(/)1(CLCLCwsC得：由)1*(*)(/)2(CLCLCwsC得：由合并化簡得合并化簡得：*)() 1*(/) 1*(*)(CLCLCsCCLCLw依次求依次求C=1,2,3C=1,2,3，的的 L L值，即可找出符合上式的值，即可找出符

45、合上式的C C* *。78 例例6某檢驗中心，為各用戶檢驗產(chǎn)品，用戶每天到達按泊松流某檢驗中心，為各用戶檢驗產(chǎn)品，用戶每天到達按泊松流=48個個/天，每個用戶每天停工損失天，每個用戶每天停工損失6元，服務時間服從負指數(shù)元，服務時間服從負指數(shù)分布分布=25個個/天，每設天，每設1個檢驗臺每天服務成本個檢驗臺每天服務成本4元，其他條件為元，其他條件為標準標準M/M/C模型，問設幾個服務臺費用最少？模型，問設幾個服務臺費用最少？ 解：解： =4元元 Cw=6=48 =25,下面再分別計算當服務臺下面再分別計算當服務臺C=1,2,3,時時Ls值。計算過程如下：值。計算過程如下：C12345/cWq.L

46、s1.92-0.9610.255021.6100.640.39612.6800.480.07722.0680.380.01701.952Cs79 計算計算 L(CL(C* *)-L(C)-L(C* *+1)+1)及及 L(CL(C* *-1)-L(C-1)-L(C* *) ) c=1 - c=1 - c=2 18.930 c=2 18.930 （相當于無窮）（相當于無窮） c=3 0.612 18.930 c=3 0.612 18.930 c=4 0.116 0.612c=4 0.116 0.612667.03/26/4/ CwsC即為所求。3* C0.612/18.930CsCw（見陸書（見

47、陸書239239頁隊長表達式）頁隊長表達式） 系統(tǒng)容量有限的系統(tǒng)容量有限的 模型模型/1/NMM 系統(tǒng)容量為N，系統(tǒng)中排隊等待的顧客數(shù)最多為N-1，所以在某一時刻某位顧客到達時，如果系統(tǒng)中已有N位顧客，那么這位顧客被拒絕進入系統(tǒng)，如圖2.2N-1 N0PnP1nP2P1P圖2.2由狀態(tài)轉(zhuǎn)移圖，可以建立系統(tǒng)概率平衡方程如下：,)(,11101NNkkkPPPPPPP1 Nk4 排隊模型排隊模型推廣推廣 系統(tǒng)容量有限的系統(tǒng)容量有限的 模型模型/1/NMMNkNPNPkk,11110；于是時，當,11, 110NkkkkNPN得，又設NnnP011NkPPNkkN,11111110；，模型的各數(shù)量指標參數(shù)如下： 1）系統(tǒng)里沒有顧客的概率11111110NPN4 排隊模型排隊模型推廣推廣 系統(tǒng)容量有限的系統(tǒng)容量有限的 模型模型/1/NMM 2）系統(tǒng)里有n個顧