蒙特卡洛方法及其建模應用20164(2)

1、蒙特卡洛蒙特卡洛方法方法介紹及其介紹及其建模應用建模應用排隊論排隊論排隊論的基本知識1排隊論模型排隊論模型21 背景介紹背景介紹 有形的隊伍有形的隊伍超市出口處排隊付款超市出口處排隊付款餐廳排隊買飯餐廳排隊買飯公共電話亭打電話公共電話亭打電話 無形的隊伍無形的隊伍114114查號臺等待服務查號臺等待服務網絡中數據包傳輸網絡中數據包傳輸報告等首長批示報告等首長批示一、排隊論的基本知識一、排隊論的基本知識排隊論研究的內容有三部分排隊論研究的內容有三部分1.1.性態(tài)問題：即研究排隊系統中的概率分布規(guī)律性態(tài)問題：即研究排隊系統中的概率分布規(guī)律2.2.最優(yōu)化問題：分為靜態(tài)最優(yōu)化和動態(tài)最優(yōu)化，即最優(yōu)化問題

2、：分為靜態(tài)最優(yōu)化和動態(tài)最優(yōu)化，即 為系統的最優(yōu)設計和系統的最優(yōu)運營為系統的最優(yōu)設計和系統的最優(yōu)運營3.3.排隊系統的統計推斷：排隊系統的統計推斷：判斷一個給定的排隊系統符合于哪種模型，以便于判斷一個給定的排隊系統符合于哪種模型，以便于根據排隊理論進行分析研究根據排隊理論進行分析研究 2.2.排隊系統描述排隊系統描述 排隊系統又稱為隨機服務系統，是研究服務排隊系統又稱為隨機服務系統，是研究服務 請求服務的人或者物請求服務的人或者物顧客；顧客；排隊系統的共同特征：排隊系統的共同特征： 顧客到達系統的時刻是隨機的，為每一位顧客顧客到達系統的時刻是隨機的，為每一位顧客 有為顧客服務的人或者物，即服務員

3、或服務臺；有為顧客服務的人或者物，即服務員或服務臺；過程和擁擠現象的隨機模型過程和擁擠現象的隨機模型. .提供服務的時間是隨機的，因而整個排隊系統提供服務的時間是隨機的，因而整個排隊系統的狀態(tài)也是隨機的的狀態(tài)也是隨機的. .排隊模型服務窗服務窗服務規(guī)則服務規(guī)則排隊排隊排隊規(guī)則排隊規(guī)則顧客源顧客源排隊系統排隊系統排隊系統的幾種形式排隊系統的幾種形式：基本排隊過程基本排隊過程： 從圖從圖6666可知，每個顧客由顧客源按一定方式可知，每個顧客由顧客源按一定方式到達服務系統，首先加入隊列排隊等待接受服務，到達服務系統，首先加入隊列排隊等待接受服務，然后服務臺按一定規(guī)則從隊列中選擇顧客進行服然后服務臺按

4、一定規(guī)則從隊列中選擇顧客進行服務，獲得服務的顧客立即離開務，獲得服務的顧客立即離開.排隊論所要研究解決的問題：排隊論所要研究解決的問題： 面對擁擠現象，人們通常的做法是增加服務設施面對擁擠現象，人們通常的做法是增加服務設施但是增加的數量越多，人力、物力的支出就越大，甚但是增加的數量越多，人力、物力的支出就越大，甚至會出現空閑浪費，如果服務設施太少，顧客排隊等至會出現空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響待的時間就會很長，這樣對顧客會帶來不良影響.如如何做到既保證一定的服務質量指標，又使服務設施費何做到既保證一定的服務質量指標，又使服務設施費用用經濟合理

5、經濟合理，恰當地解決顧客，恰當地解決顧客排隊時間排隊時間與與服務設施費服務設施費用大小用大小這對矛盾，就是隨機服務系統理論這對矛盾，就是隨機服務系統理論排隊論排隊論所要研究解決的問題。所要研究解決的問題。3.排隊系統的基本組成部分排隊系統的基本組成部分排隊系統是由輸入過程、排對規(guī)則和服務機構組成排隊系統是由輸入過程、排對規(guī)則和服務機構組成. .(1).輸入過程輸入過程 指要求服務的顧客是按怎樣的指要求服務的顧客是按怎樣的規(guī)律規(guī)律(i) 顧客總體數顧客總體數. 又稱顧客源、輸入源又稱顧客源、輸入源.這是指顧客這是指顧客(ii) 顧客到達方式顧客到達方式. 這是描述顧客是怎樣來到系這是描述顧客是怎

6、樣來到系統統到達排隊系統的過程，有時也把它稱為顧客流到達排隊系統的過程，有時也把它稱為顧客流. .一一般可以從般可以從3 3個方面來描述個方面來描述個輸入過程個輸入過程. . 的來源的來源.顧客源可以是有限的，也可以是無限的顧客源可以是有限的，也可以是無限的.的，是單個到達，還是成批到達的，是單個到達，還是成批到達. (iii) 顧客流的概率分布顧客流的概率分布. .或稱相繼顧客到達的時間或稱相繼顧客到達的時間(2).排對規(guī)則排對規(guī)則 指服務臺從隊列中選取顧客進行指服務臺從隊列中選取顧客進行 (i)損失制損失制 指如果顧客到達排隊系統時，所有指如果顧客到達排隊系統時，所有間隔的分布間隔的分布.

7、 .這是求解排隊系統有關運行指標問這是求解排隊系統有關運行指標問題題時，首先需要確定的指標時，首先需要確定的指標. .顧客流的概率分布一般顧客流的概率分布一般有定長分布、二項分布、泊松流有定長分布、二項分布、泊松流( (最簡單流最簡單流) )、愛爾、愛爾朗分布等若干種朗分布等若干種. .服務的順序服務的順序. .一般可以分為損失制、等待制和混一般可以分為損失制、等待制和混合制等合制等3 3大類大類. .服務臺都被先到的顧客占用，那么他們就自動服務臺都被先到的顧客占用，那么他們就自動離開系統永不再來離開系統永不再來. .(ii)等待制等待制 指當顧客來到系統時，所有服務臺指當顧客來到系統時，所有

8、服務臺a.先到先服務先到先服務FCFS FCFS 按顧客到達的先后順序對顧客按顧客到達的先后順序對顧客b.先到后服務先到后服務LCFSLCFSc.隨機服務隨機服務 即當服務臺空閑時，不按照排隊即當服務臺空閑時，不按照排隊d.優(yōu)先權服務優(yōu)先權服務都不空，顧客加入排隊行列等待服務都不空，顧客加入排隊行列等待服務. .等待制中，等待制中，服務臺在選擇顧客進行服務時常有如下四種規(guī)則：服務臺在選擇顧客進行服務時常有如下四種規(guī)則：進行服務進行服務. .序列而隨意指定某個顧客接受服務序列而隨意指定某個顧客接受服務. .(iii)混合制混合制 這是等待制與損失制相結合的一種服這是等待制與損失制相結合的一種服a

9、.隊長有限隊長有限. .當排隊等待服務的顧客人數超當排隊等待服務的顧客人數超b.等待時間有限等待時間有限. .即顧客在系統中的等待時即顧客在系統中的等待時c.逗留時間逗留時間( (等待時間與服務時間之和等待時間與服務時間之和) )有限有限. .務規(guī)則，一般是指允許排隊，但又不允許隊列無限務規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去長下去.具體說來，大致有三種：具體說來，大致有三種：過規(guī)定數量過規(guī)定數量K K時，后來的顧客就自動離去，另時，后來的顧客就自動離去，另求服務，即系統的等待空間是有限的求服務，即系統的等待空間是有限的. .間不超過某一給定的長度間不超過某一給定的長度T T，當等待

10、時間超，當等待時間超過過T T時，顧客將自動離去，并不再回來時，顧客將自動離去，并不再回來. .(3). 服務機構服務機構 (i)服務臺服務臺數量數量及構成及構成形式形式. 從數量上說，服務臺有單從數量上說，服務臺有單(ii)服務方式服務方式. 這是指在某一時刻接受服務的顧客數，這是指在某一時刻接受服務的顧客數，(iii)服務時間的分布服務時間的分布.在多數情況下，對每一個顧客的在多數情況下，對每一個顧客的服務臺和多服務臺之分服務臺和多服務臺之分. 從構成形式上看，服務臺有：從構成形式上看，服務臺有：單隊一單隊一-單服務臺式；單服務臺式；單隊一單隊一-多服務臺并聯多服務臺并聯式；式；多隊一多隊

11、一-多服務臺并聯式；多服務臺并聯式；單隊一單隊一-多服多服務臺串聯式；務臺串聯式；單隊一單隊一-多服務臺并串聯混合式，多服務臺并串聯混合式，以及多隊多服務臺并串聯混合式等等以及多隊多服務臺并串聯混合式等等.它有單個服務和成批服務兩種它有單個服務和成批服務兩種.服務時間是一隨機變量服務時間是一隨機變量. .常見顧客的服務時間分布有：常見顧客的服務時間分布有： 定長分布定長分布D(DeterministicD(Deterministic) )、 負指數分布負指數分布M(MarkovM(Markov) )、 k k階階ErlangErlang分布分布(Ek(Ek) )、 一般相互獨立的時間間隔分布一

12、般相互獨立的時間間隔分布 GI(GeneralGI(General Independent). Independent).n顧客到達時間間隔的分布顧客到達時間間隔的分布:假定假定 是獨立同分布，分布函數為是獨立同分布，分布函數為 ，排隊論中常用的有兩種：排隊論中常用的有兩種：nX)(tAnX（2 2）最簡流（即）最簡流（即PoissonPoisson流）（流）（M M）：）： 顧客到達時間間隔顧客到達時間間隔 為獨立的，為獨立的， 服從負指數分布，其密度函數為服從負指數分布，其密度函數為（1 1）定長分布（）定長分布（D D） 顧客到達時間間隔為確定的。顧客到達時間間隔為確定的。 000)(t

13、tetat 服務時間分布服務時間分布: 設某服務臺的服務時間為設某服務臺的服務時間為V V，其密，其密度函數為度函數為b b（t t），常見的分布有：），常見的分布有：（1 1）定長分布（）定長分布（D D）：每個顧客接受服務的）：每個顧客接受服務的時間是一個確定的常數。時間是一個確定的常數。（2 2）負指數分布（）負指數分布（M M）：每個顧客接受服務）：每個顧客接受服務時間相互獨立，具有相互的負指數分布：時間相互獨立，具有相互的負指數分布： 其中其中 ，為一常數。，為一常數。 000)(ttetbt 0 （3 3）k k階愛爾朗（階愛爾朗（ErlangErlang）分布：每個顧客）分布：每

14、個顧客接受服務時間服從接受服務時間服從k k階愛爾朗分布，其密度函階愛爾朗分布，其密度函數為：數為：tkkektkktb )!1()()(1- - 單位時間平均服務完成的顧客數單位時間平均服務完成的顧客數1/1/ - - 每個顧客的平均服務時間每個顧客的平均服務時間4. 排隊系統的主要數量指標排隊系統的主要數量指標 排隊論主要研究系統的性態(tài)，即與排隊有關排隊論主要研究系統的性態(tài)，即與排隊有關(1).排隊系統主要數量指標排隊系統主要數量指標等待時間、等待時間、 忙期、忙期、 隊長隊長.的數量指標的概率規(guī)律性；系統的優(yōu)化問題；統的數量指標的概率規(guī)律性；系統的優(yōu)化問題；統計推斷，根據資料合理建立模型

15、計推斷，根據資料合理建立模型. .目的是正確設目的是正確設計和有效運行各個服務系統，使之發(fā)揮最佳效益計和有效運行各個服務系統，使之發(fā)揮最佳效益. .所以必須確定判斷系統運行優(yōu)劣的基本數量指標所以必須確定判斷系統運行優(yōu)劣的基本數量指標. .(i).等待時間等待時間 從顧客到達時刻起到他從顧客到達時刻起到他開始開始接受服務止這接受服務止這(ii).忙期忙期 忙期忙期是指從顧客到達空閑著的服務機構起，到是指從顧客到達空閑著的服務機構起，到(iii).隊長隊長 隊長隊長是指系統中的顧客數是指系統中的顧客數(排隊等待的顧客數與排隊等待的顧客數與段時間稱為等待時間段時間稱為等待時間.等待時間是個隨機變量等

16、待時間是個隨機變量.從顧客從顧客到達時刻起到他接受服務到達時刻起到他接受服務完成完成止這段時間稱為逗留時止這段時間稱為逗留時間，也是隨機變量間，也是隨機變量.服務機構再次成為空閑止的這段時間，即服務機構服務機構再次成為空閑止的這段時間，即服務機構連續(xù)忙連續(xù)忙的時間的時間. .這是個隨機變量，是服務員最為關心的指標，因這是個隨機變量，是服務員最為關心的指標，因為它關系到服務員的為它關系到服務員的服務強度服務強度. .與忙期相對的是與忙期相對的是閑期閑期, ,即即服務機構連續(xù)保持空閑的時間服務機構連續(xù)保持空閑的時間. .在排隊系統中，忙期和閑在排隊系統中，忙期和閑期總是期總是交替交替出現的出現的.

17、 .正在接受服務的顧客數之和正在接受服務的顧客數之和)；排隊長排隊長是指系統中正在排隊是指系統中正在排隊等待服務的顧客數等待服務的顧客數.隊長和排隊長一般都是隨機變量隊長和排隊長一般都是隨機變量.(2).數量指標的常用記號數量指標的常用記號(i).主要數量指標主要數量指標WsWs平均逗留時間，即平均逗留時間，即( (在任意時刻在任意時刻) )進入進入的所有顧客數的期望值；的所有顧客數的期望值；等待服務的顧客數的期望值；等待服務的顧客數的期望值；穩(wěn)態(tài)系統的顧客逗留時間的期望值；穩(wěn)態(tài)系統的顧客逗留時間的期望值；穩(wěn)態(tài)系統的顧客等待時間的期望值穩(wěn)態(tài)系統的顧客等待時間的期望值. .Ls-Ls-平均隊長，

18、平均隊長， 即穩(wěn)態(tài)系統任一時刻即穩(wěn)態(tài)系統任一時刻平均等待時間，即平均等待時間，即( (在任意時刻在任意時刻) )進入進入qW 平均等待隊長，即穩(wěn)態(tài)系統任一時刻平均等待隊長，即穩(wěn)態(tài)系統任一時刻qL(ii).其它常用數量指標其它常用數量指標s 系統中并聯服務臺的數目系統中并聯服務臺的數目；N 穩(wěn)態(tài)系統任一時刻的狀態(tài)（即系統中穩(wěn)態(tài)系統任一時刻的狀態(tài)（即系統中U 任一顧客在穩(wěn)態(tài)系統中的逗留時間；任一顧客在穩(wěn)態(tài)系統中的逗留時間；Q 任一顧客在穩(wěn)態(tài)系統中的等待時間；任一顧客在穩(wěn)態(tài)系統中的等待時間；所有顧客數）；所有顧客數）；平均到達率；平均到達率； 平均到達間隔；平均到達間隔；1 平均服務率；平均服務率；

19、平均服務時間；平均服務時間；1 有服務臺全部空閑的概率；有服務臺全部空閑的概率；繁忙程度的重要尺度繁忙程度的重要尺度. .服務強度，即每個服務臺單位時間內的平服務強度，即每個服務臺單位時間內的平均服務時間，一般有均服務時間，一般有 ，這是衡量排隊系統，這是衡量排隊系統 s : :穩(wěn)態(tài)系統任意時刻狀態(tài)為穩(wěn)態(tài)系統任意時刻狀態(tài)為n n的概率；的概率；nPP Nn特別當特別當n=0n=0時時( (系統中顧客數為系統中顧客數為0)0)， 即穩(wěn)態(tài)系統所即穩(wěn)態(tài)系統所0P損失率：由于系統的條件限制，使顧客被拒絕服損失率：由于系統的條件限制，使顧客被拒絕服 務而使服務部門受到損失的概率。務而使服務部門受到損失的

20、概率。 5. 排隊系統的描述符號排隊系統的描述符號 描述符號：描述符號：X/Y/Z/A/B/CX/Y/Z/A/B/CXX顧客相繼到達的間隔時間的分布顧客相繼到達的間隔時間的分布 ；常用下；常用下MM表示到達的過程為泊松過程或負指數分布；表示到達的過程為泊松過程或負指數分布；DD表示定長輸入；表示定長輸入；GIGI表示一般相互獨立的時間間隔分布表示一般相互獨立的時間間隔分布. .YY服務時間的分布；所用符號與表示顧客服務時間的分布；所用符號與表示顧客列符號：列符號：到達間隔時間分布相同到達間隔時間分布相同. . 表示表示K K階愛爾朗分布；階愛爾朗分布；kEZZ服務臺個數服務臺個數 ； “ “1

21、”1”表示單個服務臺，表示單個服務臺，“s” (s1)s” (s1)A A系統容量限制系統容量限制( (默認為默認為)；如系統有；如系統有K K個等待位子，則個等待位子，則B B顧客源數目（默認為顧客源數目（默認為）；分有限與無限兩種，）；分有限與無限兩種，表表C C服務規(guī)則；服務規(guī)則； 常用下列符號：常用下列符號：FCFSFCFS：表示先到先服務的排隊規(guī)則；：表示先到先服務的排隊規(guī)則；LCFSLCFS：表示后到先服務的排隊規(guī)則；：表示后到先服務的排隊規(guī)則；PRPR： 表示優(yōu)先權服務的排隊規(guī)則表示優(yōu)先權服務的排隊規(guī)則。表示多個服務臺表示多個服務臺.0K0K1)s (s1)個服務臺；系個服務臺；

22、系統等待空間容量無限統等待空間容量無限( (等待制等待制) )；顧客源無限，采；顧客源無限，采用先到先服務規(guī)則用先到先服務規(guī)則. .中的前中的前3 3個符號個符號. .例如，某排隊問題為例如，某排隊問題為M MM MS S.無限；顧客源無限，先到先服務，單個服務的等無限；顧客源無限，先到先服務，單個服務的等待制系統待制系統. 已知已知: 顧客到達間隔時間分布顧客到達間隔時間分布, 服務時間分布服務時間分布. 求求: 隊長隊長: Ls - 系統中的顧客數系統中的顧客數. 排隊長排隊長(隊列長隊列長): Lq - 隊列中的顧客數隊列中的顧客數. Ls = Lq + 正在接受服務的顧客數正在接受服務

23、的顧客數 逗留時間逗留時間: W S- 顧客在系統中的停留時間顧客在系統中的停留時間 等待時間等待時間: Wq - 顧客在隊列中的等待時間顧客在隊列中的等待時間. WS = Wq + 服務時間服務時間 忙期忙期, 損失率損失率, 服務強度服務強度.排隊問題的求解排隊問題的求解二、二、M/M/sM/M/s排隊模型排隊模型 M/M/sM/M/s排隊模型是指排隊模型是指s s個服務員的排隊系統，個服務員的排隊系統，顧客到來間隔時間是獨立同分布的；顧客到來間隔時間是獨立同分布的；服務時間也是獨立同分布的；服務時間也是獨立同分布的；并且獨立于輸入過程；并且獨立于輸入過程；排隊規(guī)則是等待制；排隊規(guī)則是等待

24、制；含假定：含假定：顧客到來間隔時間服從參數為顧客到來間隔時間服從參數為 的指數分布，的指數分布，服務時間服從參數為服務時間服從參數為 的負指數分布，且有隱的負指數分布，且有隱 按排隊論的基本構成特征，來求解該排隊模型按排隊論的基本構成特征，來求解該排隊模型(1).基本構成基本構成(i) 顧客到達規(guī)律顧客到達規(guī)律()( ),0,1,2!kttP X tkekk 的主要數量指標：的主要數量指標：平均到達率平均到達率.表示在表示在 時間到達的顧客數，稱為排隊系統的輸入過程時間到達的顧客數，稱為排隊系統的輸入過程.()Xt( ,)t tt 其平均值為其平均值為 ，即單位時間內到達的顧客數為，即單位時

25、間內到達的顧客數為 ，并稱為，并稱為t它服從參數為它服從參數為 的泊松分布，即的泊松分布，即：t(ii) 服務時間服務時間服務率服務率 . .表示顧客到達間隔時間序列，其表示顧客到達間隔時間序列，其1|nnnnss 中中 表示第表示第n個顧客的到來時刻個顧客的到來時刻. .n 可以證明可以證明： 服從參數服從參數 為的泊松分布的充為的泊松分布的充( )X tt負指數分布負指數分布. .要條件是到要條件是到達間隔時間序列達間隔時間序列 獨立同分布且服從獨立同分布且服從ns記記Z Z為服務時間，為服務時間，Z Z服從參數為服從參數為 的負指數分布的負指數分布：01()00tteP Ztt 則則 ，

26、即為每個顧客平均服務時間為，即為每個顧客平均服務時間為 ，從，從1EZ 1 而單位時間內被服務的顧客的平均數為而單位時間內被服務的顧客的平均數為 ，稱為平均，稱為平均 (iii) 排隊規(guī)則排隊規(guī)則按顧客的到達的先后順序服務，即先到先服務按顧客的到達的先后順序服務，即先到先服務. . 滿足以上三個條件的模型在排隊論中記為模型滿足以上三個條件的模型在排隊論中記為模型(2).數量特征數量特征( (只討論只討論s=1s=1情形情形) )(i) 平均隊長平均隊長 穩(wěn)態(tài)下系統內等待服務的顧客數，其數學期穩(wěn)態(tài)下系統內等待服務的顧客數，其數學期望稱為平均等待隊長，即望稱為平均等待隊長，即M/M/s模模型，其中

27、型，其中s s為服務員的個數為服務員的個數. .1L( (其中其中稱為服務強度稱為服務強度.).)21qL (1)(ii)平均逗留時間和平均等待時間平均逗留時間和平均等待時間平均逗留時間為平均逗留時間為平均等待時間為平均等待時間為則公式則公式稱為稱為LittleLittle公式公式. .1LW 11()qW LW qqLW qLL1qWW(3). M/M/s M/M/s 排隊模型排隊模型(i) 當當s=2s=2時時 服務強度服務強度平均隊長平均隊長平均等待時間平均等待時間 (ii) 當當s s是任意的是任意的服務強度服務強度平均隊長平均隊長平均等待時間平均等待時間 212222221L 22222(1)LW s 02()!(1)sssLsps ssLW 其中其中為所有服務員均空閑的