高等運籌第十講大連海事大學(xué)ppt課件

1、高等運籌學(xué)高等運籌學(xué)大連海事大學(xué)大連海事大學(xué)劉巍劉巍目錄 第一篇第一篇 運籌學(xué)開展歷史運籌學(xué)開展歷史 第二篇第二篇 運籌學(xué)中的數(shù)學(xué)規(guī)劃運籌學(xué)中的數(shù)學(xué)規(guī)劃 第三篇第三篇 運籌學(xué)中的組合優(yōu)化運籌學(xué)中的組合優(yōu)化 第四篇第四篇 運籌學(xué)中的隨機優(yōu)化運籌學(xué)中的隨機優(yōu)化 第五篇第五篇 運籌學(xué)中的博弈論運籌學(xué)中的博弈論 第六篇第六篇 運籌學(xué)中管文科學(xué)運籌學(xué)中管文科學(xué) 第七篇第七篇 運籌學(xué)中智能計算運籌學(xué)中智能計算 第八篇第八篇 運籌學(xué)開展勢態(tài)運籌學(xué)開展勢態(tài)第四篇 運籌學(xué)中的隨機優(yōu)化 第十二章第十二章 排隊論排隊論 第十三章第十三章 隨機優(yōu)化的相關(guān)問題隨機優(yōu)化的相關(guān)問題隨機優(yōu)化 隨機最優(yōu)化問題是特指帶有隨機要素

2、的最隨機最優(yōu)化問題是特指帶有隨機要素的最優(yōu)化問題，需求利用概率統(tǒng)計、隨機過程優(yōu)化問題，需求利用概率統(tǒng)計、隨機過程以及隨機分析等工具。以及隨機分析等工具。 所謂的隨機要素，包括環(huán)境的隨機要素、所謂的隨機要素，包括環(huán)境的隨機要素、控制變量不確定要素、準(zhǔn)那么值的不確定控制變量不確定要素、準(zhǔn)那么值的不確定要素等等。要素等等。港口排隊系統(tǒng) 港口的消費過程構(gòu)成了一個復(fù)雜的動態(tài)系統(tǒng)港口的消費過程構(gòu)成了一個復(fù)雜的動態(tài)系統(tǒng), 船舶到港船舶到港及其卸船活動可以看成一個排隊過程及其卸船活動可以看成一個排隊過程,： 船舶是排隊論中的船舶是排隊論中的“顧客顧客, 顧客到來的多少是一個隨機顧客到來的多少是一個隨機要素；要

3、素； 港口可作為效力機構(gòu)港口可作為效力機構(gòu), 效力時間即裝卸時間效力時間即裝卸時間也是隨機變量。也是隨機變量。 港口作業(yè)過程的隨機過程描畫為：港口作業(yè)過程的隨機過程描畫為： 輸入過程普通服從泊松分布；輸入過程普通服從泊松分布； 效力過程普通服從負(fù)指數(shù)分布；效力過程普通服從負(fù)指數(shù)分布； 效力臺即裝卸泊位數(shù)普通為多個。效力臺即裝卸泊位數(shù)普通為多個。 關(guān)懷和研討的問題 1. 效力強度效力強度 2. 無船概率無船概率 3.平均船數(shù)平均船數(shù) 4.平均在港時間平均在港時間 5.平均排隊時間平均排隊時間 6.平均排隊長度平均排隊長度 7.平均效力時間平均效力時間第十二章第十二章排隊論排隊論醫(yī)院、理發(fā)、火車售

4、票排隊景象、為什么研討它？ 排隊景象：顧客到商店去買東西，病人到醫(yī)院去看病，排隊景象：顧客到商店去買東西，病人到醫(yī)院去看病，汽車去加油站加油，旅客到車站購票；汽車去加油站加油，旅客到車站購票； 當(dāng)要求效力的對象的數(shù)量超越效力機構(gòu)的容量就會出當(dāng)要求效力的對象的數(shù)量超越效力機構(gòu)的容量就會出現(xiàn)排隊景象；現(xiàn)排隊景象； 排隊景象由于顧客到達(dá)人數(shù)和效力時間的隨機性而不排隊景象由于顧客到達(dá)人數(shù)和效力時間的隨機性而不可防止；可防止； 當(dāng)添加效力設(shè)備能減少排隊景象，但這樣勢必添加投當(dāng)添加效力設(shè)備能減少排隊景象，但這樣勢必添加投資且能夠出現(xiàn)因供大于求而使設(shè)備經(jīng)常閑置、導(dǎo)致浪資且能夠出現(xiàn)因供大于求而使設(shè)備經(jīng)常閑置、

5、導(dǎo)致浪費；費； 研討排隊問題，就是要把排隊的時間控制到一定的程研討排隊問題，就是要把排隊的時間控制到一定的程度內(nèi)，在效力質(zhì)量的提高和本錢的降低之間獲得平衡，度內(nèi)，在效力質(zhì)量的提高和本錢的降低之間獲得平衡，找到最適當(dāng)?shù)慕?。找到最適當(dāng)?shù)慕狻?在排隊論中，我們把要求效力的對象稱為“顧客，而將從事效力的機構(gòu)或人稱為“效力臺。 在顧客到達(dá)效力臺時，能夠立刻得到效力，也能夠要等待到可以利用效力臺的時候為止。 排隊系統(tǒng)隊列除了有形的還有無形的。 排隊系統(tǒng)中的“顧客與“效力臺這兩個名詞可以從不同的角度去了解。排隊系統(tǒng)排隊系統(tǒng)顧客顧客服務(wù)臺服務(wù)臺上、下班的工人乘公共汽車上、下班的工人乘公共汽車工人工人公共汽車公

6、共汽車病人到醫(yī)院看病病人到醫(yī)院看病病人病人醫(yī)生醫(yī)生高炮擊退敵機高炮擊退敵機敵機敵機高炮高炮機器發(fā)生故障需要維修機器發(fā)生故障需要維修機器機器修理工修理工 在上述顧客-效力臺組成的排隊系統(tǒng)中，顧客到來的時辰與效力臺進(jìn)展效力的時間普通來說是隨不同的時機與條件而變化的，往往預(yù)先無法確定。因此，系統(tǒng)的形狀是隨機的，故而排隊論也稱隨機效力系統(tǒng)。顧客源第1節(jié) 排隊模型排隊系統(tǒng)排隊構(gòu)造效力機構(gòu)排隊規(guī)那么效力規(guī)那么接受效力離去輸入過程顧客源總體：顧客的來源能夠是有限的，也可 能是無限的到達(dá)的類型：顧客是單個到達(dá)，或是成批到達(dá)相繼顧客到達(dá)的間隔時間：通常假定是相互獨立、同分布的，有的是等距間隔時間，有的是服從Po

7、isson分布，有的是服從k階Erlang分布輸入過程是描畫顧客來源及顧客是按怎樣的規(guī)律抵達(dá)排隊系統(tǒng)輸入過程顧客源輸入過程顧客源 顧客到達(dá)時間間隔的分布顧客到達(dá)時間間隔的分布:：第n個顧客與第n-1個顧客到達(dá)的時間間隔；nXnT：第n個顧客到達(dá)的時辰；設(shè)nTTT100, 2 , 1,1nTTXnnn令1T2TnT1nT1nT0TnXn顧客到達(dá)時間間隔的分布:假定 是獨立同分布，分布函數(shù)為 ，排隊論中常用的有兩種：nX)(tAnX2最簡流即Poisson流M： 顧客到達(dá)時間間隔 為獨立的， 服從負(fù)指數(shù)分布，其密度函數(shù)為1定長分布D：顧客到達(dá)時間間隔為確定的。000)(ttetat由于負(fù)指數(shù)分布具

8、有無后效性即Markov性排隊規(guī)那么損失制排隊系統(tǒng)：顧客到達(dá)時,假設(shè)有效力臺均被占,效力機構(gòu) 又不允許顧客等待, 此時該顧客就自動辭去 排隊系統(tǒng)等待制排隊系統(tǒng)：顧客到達(dá)時假設(shè)一切效力臺均被占，他們 就排隊等待效力。在等待制系統(tǒng)中,效力順序又分為：先到先效力,即顧客按到達(dá)的先后順序接受效力；后到先效力 .混合制排隊系統(tǒng)：損失制與等待制的混合，分為隊長(容量) 有限的混合制系統(tǒng)，等待時間有限的混 合制系統(tǒng)，以及逗留時間有限制的混合系統(tǒng).排隊規(guī)那么是指效力允許不允許排隊，顧客能否情愿排隊效力機構(gòu)效力臺的數(shù)目效力臺的數(shù)目: : 在多個效力臺的情形下，是串在多個效力臺的情形下，是串 聯(lián)或是并聯(lián)；聯(lián)或是并

9、聯(lián)； 效力系統(tǒng)顧客所需的效力時間服從什么樣的概率分布，顧客所需的效力時間服從什么樣的概率分布，每個顧客所需的效力時間能否相互獨立，是成每個顧客所需的效力時間能否相互獨立，是成批效力或是單個效力等。常見顧客的效力時間批效力或是單個效力等。常見顧客的效力時間分布有：定長分布、負(fù)指數(shù)分布、超指數(shù)分分布有：定長分布、負(fù)指數(shù)分布、超指數(shù)分布、布、k k階階ErlangErlang分布、幾何分布、普通分布等分布、幾何分布、普通分布等. .效力機構(gòu)效力機構(gòu)效力臺(a) 一個隊列、單效力臺階段效力臺1效力臺2(b) 一個隊列、s個效力階段效力機構(gòu)效力機構(gòu)效力臺1效力臺2效力機構(gòu)效力機構(gòu)(c) (c) 一個隊列

10、、一個隊列、s s個效力臺個效力臺 一個效力階段一個效力階段效力臺3效力臺4效力臺1效力臺2效力機構(gòu)效力機構(gòu)(d) s(d) s個隊列、個隊列、s s個效力階段個效力階段效力臺3效力臺4效力臺1效力臺2: 124: 243: 3214效力機構(gòu)效力機構(gòu)(e)混合型排隊構(gòu)造排隊構(gòu)造效力臺(f) 一個隊列效力臺(g) s個隊列 效力時間分布效力時間分布: 設(shè)某效力臺的效力時間為V，其密度函數(shù)為bt，常見的分布有：1定長分布D：每個顧客接受效力的時間 是一個確定的常數(shù)。2負(fù)指數(shù)分布M：每個顧客接受效力時間 相互獨立，具有相互的負(fù)指數(shù)分布： 其中 ，為一常數(shù)。000)(ttetbt0- - 單位時間平均

11、效力完成的顧客數(shù)單位時間平均效力完成的顧客數(shù)1/ - 1/ - 每個顧客的平均效力時間每個顧客的平均效力時間 效力時間分布效力時間分布:3k階愛爾朗Erlang分布：每個顧客接受效力 時間服從k階愛爾朗分布，其密度函數(shù)為：tkkektkktb)!1()()(1 符號表示符號表示: X/Y/Z X - 客到達(dá)間隔時間分布客到達(dá)間隔時間分布 Y - 效力時間分布效力時間分布 Z - 效力臺個數(shù)效力臺個數(shù) X, Y 可以是可以是: M - 負(fù)指數(shù)分布負(fù)指數(shù)分布 D - 確定性的確定性的 Ek - k階階Erlang分布分布 GI - 普通相互獨立的到達(dá)時間間隔分布普通相互獨立的到達(dá)時間間隔分布 G

12、- 普通普通(General)時間分布時間分布排隊系統(tǒng)的分類 擴(kuò)展符號表示擴(kuò)展符號表示: X/Y/Z/A/B/C A - 系統(tǒng)容量系統(tǒng)容量 B - 顧客源中顧客的數(shù)量顧客源中顧客的數(shù)量 C - 效力規(guī)那么效力規(guī)那么: FCFS, LCFS, 等等等等.n假設(shè)省略后三項，即是指下面的情形： n X/Y/Z/ / /FCFS M/M/S/ 表示輸入過程是Poisson流, 效力時間服從負(fù)指數(shù)分布, 系統(tǒng)有S個效力臺平行效力, 系統(tǒng)容量為無窮的等待制排隊系統(tǒng).(2) M/G/1/ 表示輸入過程是Poisson流，顧客所需的效力時間為獨立、服從普通概率分布，系統(tǒng)中只需一個效力臺，容量為無窮的等待制系統(tǒng)

13、.GI/M/1/表示輸入過程為顧客獨立到達(dá)且相繼到達(dá)的間隔時間服從一船概率分布，效力時間是相互獨立、服從負(fù)指數(shù)分布，系統(tǒng)中只需一個效力臺，容量為無窮的等待制系統(tǒng)(4) Ek/G/1/K表示相繼到達(dá)的間隔時間獨立、服從k階Erlang分布，效力時間為獨立、服從普通概率分布，系統(tǒng)中只需一個效力臺，容量為K的混合制系統(tǒng).(5) D/M/S/K表示相繼到達(dá)的間隔時間獨立、服從定長分布、效力時間相互獨立、服從負(fù)指數(shù)分布，系統(tǒng)中有S個效力臺平行效力，容量為K的混合制系統(tǒng). 描畫排隊系統(tǒng)的主要數(shù)量目的 隊長與等待隊長隊長(通常記為LS)是指在系統(tǒng)中的顧客的平均數(shù)(包括正在接受效力的顧客),而等待隊長(通常記

14、為Lq)是指系統(tǒng)中排隊等待的顧客的平均數(shù)，它們是顧客和效力機構(gòu)雙方都非常關(guān)懷的數(shù)量目的。顯然隊長等于等待隊長加上正在被效力的顧客數(shù). 顧客的平均等待時間與平均逗留時間顧客的平均等待時間(通常記為Wq)是指從顧客進(jìn)入系統(tǒng)的時辰起直到開場接受效力止的平均時間。平均逗留時間(通常記為Ws)是指顧客在系統(tǒng)中的平均等待時間與平均效力時間之和。平均等待時間與平均效力時間是顧客最關(guān)懷的數(shù)量目的. 描畫排隊系統(tǒng)的主要數(shù)量目的 系統(tǒng)的忙期與閑期 從顧客到達(dá)空閑的系統(tǒng)，效力立刻開場，直到系統(tǒng)再次變?yōu)榭臻e，這段時間是系統(tǒng)延續(xù)忙碌的時間，我們稱為系統(tǒng)的忙期，它反映了系統(tǒng)中效力機構(gòu)的任務(wù)強度，是衡量效力機構(gòu)利用效率的目

15、的，即與忙期對應(yīng)的是系統(tǒng)的閑期，即系統(tǒng)延續(xù)堅持空閑的時間長度.效力機構(gòu)任務(wù)強度用于效力顧客的時間效力設(shè)備總的效力時間用于效力顧客的時間效力設(shè)備總的效力時間1 Little利特爾公式用 表示單位時間內(nèi)顧客到達(dá)的平均數(shù),表示單位時間內(nèi)被效力終了離去的平均顧客數(shù)，因此1/ 表示相鄰兩顧客到達(dá)的平均時間，1/ 表示對每個顧客的平均效力時間.J. D. C. Little給出了如下公式：,ssssLWWL或,qqqqLWWL或,1qsWW,qsLL 知: 顧客到達(dá)間隔時間分布, 效力時間分布. 求:隊長: Ls - 系統(tǒng)中的顧客數(shù). 排隊長(隊列長): Lq - 隊列中的顧客數(shù). Ls = Lq + 正

16、在接受效力的顧客數(shù)逗留時間: W S- 顧客在系統(tǒng)中的停留時間 等待時間: Wq - 顧客在隊列中的等待時間. WS = Wq + 效力時間忙期, 損失率, 效力強度.排隊問題的求解第第2 2節(jié)節(jié) 單效力臺負(fù)指數(shù)分布單效力臺負(fù)指數(shù)分布排隊系統(tǒng)分析排隊系統(tǒng)分析 2.1 M/M/1模型2.2 M/M/1/N/ 模型(即系統(tǒng)的容量有限)2.3 M/M/1/ /m 模型即顧客源為有限顧客源排隊系統(tǒng)排隊構(gòu)造效力機構(gòu)排隊規(guī)那么效力規(guī)那么接受效力后離去 2.1 M/M/1模型無限輸入過程服從參數(shù)為 的Poisson過程單隊隊長無限先到先效力效力時間服從參數(shù)為 的負(fù)指數(shù)分布輸入過程船舶到港服從泊松分布效力時間

17、裝卸時間服從負(fù)指數(shù)分布 求解：np:系統(tǒng)到達(dá)平穩(wěn)后，系統(tǒng)有n個顧客的概率。1n 0)(0n 01110nnnPPPPP平衡方程：1n )1(1 0nnPP1 :令，且當(dāng)時01102101.,.2, 1,ppCnpCpnnnnnnnnn其中 關(guān)于 的幾點闡明：)1 (/1/1(2)01(3)p顧客平均到達(dá)率顧客平均效力率一個顧客效力時間一個顧客到達(dá)時間效力強度, 1) 4(即顧客的顧客平均到達(dá)率小于顧客平均效力率時，系統(tǒng)才干到達(dá)統(tǒng)計平穩(wěn)。系統(tǒng)中至少有一個顧客的概率；效力臺處于忙的形狀的概率；反映系統(tǒng)忙碌程度 計算有關(guān)目的計算有關(guān)目的101.)2(.)32()1 ( 3232321n0nsnnsL

18、nnPLn隊長隊列長隊列長 1)1 () 1( 201n10nssnnnnqLPLPnPPnL 計算有關(guān)目的 逗留時間逗留時間: : 可以證明可以證明, Ws, Ws服從參數(shù)為服從參數(shù)為-的負(fù)指數(shù)分布的負(fù)指數(shù)分布. . 那么那么: :等待時間等待時間1 sW1 sqWW服務(wù)WWWsq 計算有關(guān)目的計算有關(guān)目的 Little公式相互關(guān)系qsqsqqssLLWWWLWL 1 小結(jié)1 sWqW qLsL平均效力時間平均在忙的效力臺數(shù)/正在接受效力的顧客數(shù)有效到達(dá)率 平均忙期 B , 忙期出現(xiàn)的概率 平均閑期 I , 閑期出現(xiàn)的概率 (1-)n忙期 B : 閑期 I = : (1-)n平均閑期 I =

19、 1 / 閑期的分布與顧客閑期的分布與顧客到達(dá)時間間隔的一樣到達(dá)時間間隔的一樣-服從參數(shù)為服從參數(shù)為的的負(fù)指數(shù)分布負(fù)指數(shù)分布計算有關(guān)目的n忙期與閑期 WHY?1-P0= 平均忙期平均忙期 B , 忙期出現(xiàn)的概率忙期出現(xiàn)的概率 平均閑期平均閑期 I , 閑期出現(xiàn)的概率閑期出現(xiàn)的概率 (1-)n忙期 B : 閑期 I = : (1-)n平均閑期 I = 1 / n平均忙期 B = ( / (1-) / = 1/( - )計算有關(guān)目的n忙期與閑期 與逗留時間Ws一樣!?例：某醫(yī)院手術(shù)室每小時就診病人數(shù)和手術(shù)例：某醫(yī)院手術(shù)室每小時就診病人數(shù)和手術(shù) 時間的記錄如下：時間的記錄如下：到達(dá)的病人數(shù) 出現(xiàn)次數(shù)

20、 n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合計 100完成手術(shù)時間 出現(xiàn)次數(shù) r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上 0 合計 100 解：到達(dá)的病人數(shù) 出現(xiàn)次數(shù) n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合計 100每小時病人平均到達(dá)率1.2100nnu人/小時每次手術(shù)平均時間4 .0100rrv小時/人每小時完成手術(shù)人數(shù)平均效力率5 .24 .01人/小時?, 解：到達(dá)的病人數(shù) 出現(xiàn)次數(shù) n un 0 10 1

21、28 2 29 3 16 4 10 5 6 6 以上 1 合計 100每小時病人平均到達(dá)率1.2100nnu人/小時每次手術(shù)平均時間4 .0100rrv小時/人每小時完成手術(shù)人數(shù)平均效力率5 .24 .01人/小時完成手術(shù)時間 出現(xiàn)次數(shù) r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上 0 合計 1005 . 2, 1 . 2解：5 . 2, 1 . 21 sWqW 41. 425. 55 . 21 . 2sqLL25. 51 . 25 . 21 . 2sL2.2 2.2 系統(tǒng)容量有限制的情形系統(tǒng)容量有限制

22、的情形 (M/M/1/N/FCFS (M/M/1/N/FCFS 形狀轉(zhuǎn)移圖 形狀轉(zhuǎn)移方程 Nn 1-Nn )(0n 11101NNnnnPPPPPPPN-1N求排隊系統(tǒng)顧客數(shù)的分布情況01102101.,.2, 1,ppCnpCpnnnnnnnnn其中 1 1 .,.2 , 1,002000110210pppppCwherenpCpNNnnnnnnnnnnn N1,2,.,n 11 11110nNnNPP1) 1 (20NP求排隊系統(tǒng)顧客數(shù)的分布情況 隊長隊長 隊列長隊列長 1101)1(1NNNnnsNnPL)1 ()1(00PLPnLsNnnq計算有關(guān)目的 逗留時間逗留時間 等待時間等待時

23、間111Little1 100）（）（公式根據(jù)）（）或（有效到達(dá)率：NqsesseNePLPLLWPP1sqWW計算有關(guān)目的系統(tǒng)已滿顧客不能到達(dá)的概率-損失率/10eP ）服務(wù)強度：（ 有6個椅子接待人們排隊，超越6人顧客就分開，平均到達(dá)率3人/小時，理發(fā)需時平均15分鐘。7為系統(tǒng)中的最大顧客數(shù)。平均到達(dá)率: 3人/小時 平均效力率: 4人/小時舉例：單人理發(fā)館排隊問題 顧客到達(dá)就能理發(fā)的概率 -相當(dāng)于理發(fā)店內(nèi)沒有顧客 等待顧客數(shù)的期望值2778. 0)4/3(14/3111810NP39. 1)2778. 01 (11. 2)1 (11. 2)4/3(1)4/3(84/314/31) 1(1

24、08811PLLNLsqNNs 求有效到達(dá)率求有效到達(dá)率 顧客在理發(fā)館內(nèi)逗留的期望時間顧客在理發(fā)館內(nèi)逗留的期望時間8 .4373. 089. 2/11. 2/essLW小時分鐘89. 2)2778. 01 (41 10eeNePP）（）或（人/小時 能夠的顧客中有百分之幾不等待就分開 -求系統(tǒng)中有7個顧客的概率%7 . 3)4/3(14/31)43()/(1/1)(87877P 設(shè)：設(shè)：m ：為顧客總體數(shù)，：為顧客總體數(shù)， ： 每個顧客的到達(dá)率，每個顧客的到達(dá)率， m - Ls ：系統(tǒng)外顧客的平均數(shù)，：系統(tǒng)外顧客的平均數(shù)， e = m - Ls：為系統(tǒng)有效到達(dá)率。：為系統(tǒng)有效到達(dá)率。2.3 2

25、.3 顧客源有限制的情形顧客源有限制的情形 (M/M/1/m/FCFS (M/M/1/m/FCFS含義與上節(jié)不同對顧客而言，而不是對系統(tǒng)m對系統(tǒng)而言,有一個顧客到達(dá)的概率狀態(tài)轉(zhuǎn)移圖01mn-1n(m-n+1) (m-n)n+1. . . . .m-1m. . .(m-1) 2形狀轉(zhuǎn)移方程形狀轉(zhuǎn)移方程 mn 1-mn )() 1(0n 11101mmnnnPPPnmPnmPPmP11mnnPF留意到 ， 求解形狀轉(zhuǎn)移方程得求解形狀轉(zhuǎn)移方程得m1,2,.,n )()!(!)()!(!1010PnmmPimmPnnimi有效到達(dá)率)(seLm ）（01 Pe求解顧客數(shù)概率分布 等待時間等待時間 正常

26、運轉(zhuǎn)的平均設(shè)備臺數(shù)正常運轉(zhuǎn)的平均設(shè)備臺數(shù)1sqWW)1(0PLms計算有關(guān)目的 隊長隊長 隊列長隊列長 逗留時間逗留時間)1(0PmLs)1(0PLLsq1)1(0PmWs計算有關(guān)目的第第3節(jié)節(jié) 多效力臺負(fù)指數(shù)多效力臺負(fù)指數(shù)分布排隊系統(tǒng)分析分布排隊系統(tǒng)分析規(guī)定：規(guī)定：各效力臺任務(wù)是相互獨立的，且平均效力率一樣各效力臺任務(wù)是相互獨立的，且平均效力率一樣，均為，均為 。整個效力機構(gòu)的平均效力率為：整個效力機構(gòu)的平均效力率為： c c ( (當(dāng)當(dāng)n n c ) c )， n n ( (當(dāng)當(dāng)n c );n c );記記 = = / / , , s= s= /c/c = = /c /c 為效力系統(tǒng)的平均

27、利用為效力系統(tǒng)的平均利用率率 當(dāng)當(dāng) / c/ c 1 1時，不會排成無限隊列。時，不會排成無限隊列。 1 2 c.系統(tǒng)人數(shù)n人 1 2 c.系統(tǒng)人數(shù)n人n c狀態(tài)轉(zhuǎn)移圖01n-1nn(n+1)n+1. . . . .22n-1nccn+1. . . . .n c 形狀轉(zhuǎn)移方程形狀轉(zhuǎn)移方程 n )(cn 1 )() 1(0n 111101cPcPPcPnPPnPPnnnnnn解差分方程，求得形狀概率為解差分方程，求得形狀概率為 )(!1)(!1)(11!1)(!1001100cnPcccnPnPckPncnnnckck 顧客等候的概率顧客等候的概率 )(!1)( !1010cnPcccnPnPn

28、nnn0)1( !)(PcPcnPsccnn n平均正接受效力的顧客數(shù)=正忙的效力臺數(shù)cnncnnPcnPc10qsLL解釋? )(!1)( !1010cnPcccnPnPnnnn 隊長隊長 隊列長隊列長 逗留時間及等待時間逗留時間及等待時間qqsLLL021)1( !)()(PcPcnLssccnnqssqqLWLW ;獨一 某售票一切三個窗口，顧客到達(dá)服從Poisson過程，到達(dá) = 0.9 人/分鐘，效力 =0.4人/分鐘。設(shè)顧客到達(dá)后依次排成一隊向空閑的窗口購票，如圖 a. 圖 a 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.9圖 a 窗口1 =0.4 窗口2 =0.

29、4 窗口3 =0.4 = 0.3 = 0.3 = 0.3 = 0.9圖 b 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.9 屬于M/M/c型系統(tǒng) c =3, =/ =2.25, s = /c =2.25/3 1,符合要求.整個售票所空閑概率平均隊長95.370.10748.0)4/1 ( ! 34/3)25.2(23qsqLLL0748.03/25.211! 325.2!25.212030nnnp平均等待時間和逗留時間分鐘分鐘39.44.0/189.1/189.19.0/70.1qsqqWWLW57.00748.04/1!3)25.2()3(3nP顧客到達(dá)后必需等待概率 以上

30、例闡明,設(shè)顧客到達(dá)后在每個窗口前各排一隊(其它條件不變),共三隊,每隊平均到達(dá)率為:3 . 03/9 . 0321 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.3 = 0.3 = 0.3 = 0.9圖 b結(jié)果比較 形狀圖是多效力臺和容量有限的綜合形狀圖是多效力臺和容量有限的綜合 平衡方程平衡方程他會嗎?Nncccnnnnnn 0 N 01N,0,1,2, 1 ) 1(! 1 )1 ( !)1 (! ! 0 !1101101000ccncnccnccNccncnnnncNcncnpNncpcccnpnp 求系統(tǒng)有求系統(tǒng)有n位顧客的概率分布位顧客的概率分布 求系統(tǒng)的目的求系統(tǒng)的目

31、的)1 (Nep有效到達(dá)率有效到達(dá)率)1 ( 10NNcnncnnppcnpc平均被占用的效力臺平均被占用的效力臺 求系統(tǒng)的目的求系統(tǒng)的目的1 , )(seqqessqsNcnnqWLWLWcLLpcnL設(shè)系統(tǒng)的平均到達(dá)率為設(shè)系統(tǒng)的平均到達(dá)率為 ，任一顧客的效力時間為，任一顧客的效力時間為 V , 且有：且有： E(V ) = 1/ ，D(V ) = 2 效力強度效力強度 ： = / 不論不論V服從什么分布，只需服從什么分布，只需 1 ,系統(tǒng)就會到達(dá)穩(wěn)態(tài)，并有穩(wěn)態(tài)概率為：系統(tǒng)就會到達(dá)穩(wěn)態(tài)，并有穩(wěn)態(tài)概率為： P0 = 1 - 根據(jù)波拉切克根據(jù)波拉切克PollacekPollacek-欣欽欣欽Kh

32、intchineKhintchine公式可導(dǎo)出：公式可導(dǎo)出：)1(2222qL其它相關(guān)結(jié)果110qssqqqsWLWLWLLp 系統(tǒng)對各顧客的效力時間相互獨立且為同一個常數(shù) v， 那么有： E(v) = v = 1/ 0,s0,PN(s+t)-N(t)=k=排隊論課件Poisson Processexp()ititi顧客到達(dá)時間間隔（t）exp( (t)t)T 顧客 接受服務(wù)的時間（t）和 的確定都將在后面仿真的部分給出排隊論課件112 分析1：能否得到準(zhǔn)確的前往時間？ (1. ),1immii1,m+1ii1,m+1如果能夠準(zhǔn)確得知前面所有顧客的到達(dá)時間間隔t 和接受服務(wù)的時間T當(dāng)然可以知道

33、第個顧客到達(dá)就可以馬上接受服務(wù)的時間隔t.可現(xiàn)在t 和T都是隨機變量，我們只能用隨機過程的方法，求出t期望值。 2 在我們開場動手建模之前，先要問幾個問題：排隊論課件113 分析2：運用FastPass后排隊是不是可以防止的？FastPass給出的前往時間只是期望值，而非確定值假設(shè)一切的顧客都運用FastPass,但需思索有的顧客能夠會不遵守FastPass給出的前往時間 2 在我們開場動手建模之前，先要問幾個問題：FastPass2,m+1結(jié)論：使用后顧客仍需排隊，但是排隊的時間會大大減少。并設(shè)第m+1個顧客排隊的時間是t排隊論課件114 分析3：我們優(yōu)化的目的函數(shù)或cost functio

34、n是什么？是排隊時間嗎？ 2 在我們開場動手建模之前，先要問幾個問題：1.FastPass1,iw2,i給 出 的 顧 客 i的 等 待 時 間 t太 長 ,同 樣 會 引來 抱 怨 ,并 且 不 能 超 過 公 園 的 開 放 時 間 T2.排 隊 的 時 間 t也 要 考 慮但 是 后 者 引 來 的 抱 怨 更 大 ； 而 且 等 待 的 時 間 越 長 ， 抱怨 越 多 .結(jié) 論 ： 目 標(biāo) 函 數(shù) 應(yīng) 該 是 兩 者 的 時 變 加 權(quán) 和 （ time-variantweighted average） 優(yōu)化問題的目的函數(shù)為： 11221,11,11,1min ( )( ) . .i

35、jiwjiiiwzE Uc t tc t tttTs ttttT公園一天的開放時間 模型的建立1目的函數(shù) 根據(jù)排隊論的分類規(guī)那么,X/Y/Z/A代表一類排隊，其中 X:顧客流到達(dá)所符合的分布 Y:顧客接受效力的時間所服從的分布 Z:效力臺的個數(shù) A:效力臺一次可效力的顧客數(shù)量系統(tǒng)的容量 針對各個游樂工程的特點，我們主要討論兩種排隊系統(tǒng):模型的建立2 排隊模型的分類/1/ / %M MM M c ac電話亭（phonebooth）的隊列模型和過山車（scenic railway）的隊列模型 特點：系統(tǒng)容量為1，顧客的到達(dá)是Poisson流，效力時間服從指數(shù)分布，只需一條隊列模型的建立3 亭模型

36、求出這類系統(tǒng)的代價函數(shù)表達(dá)式模型的建立3亭模型12,( , )1()*nn kkini ktEPA *,0;( )0,0.x xxx1,1nnnjjkiAttEP第n個顧客的返回時間：是第k個顧客可以接受服務(wù)的時刻是隊列中的顧客i仍會停留的時間（包括使用系統(tǒng)的時間） 近似將總的優(yōu)化目的函數(shù)等效為對顧客i的目的函數(shù)：模型的建立3亭模型11,22,111,2,2,( , )0,min ( )( )min()nnnnnn kn kkn kzE Uc t tc t tc E tcQ tQP nk其中，顧客前有 個顧客在排隊,111, 2212,1111111,1 ,1 ,1 ,1,11()(.),(1

37、),(), (0 )kkknkkkknkskskksnkkkkkkkkkkkikikikikkkiniQPEPAQPEPPAQPEPPAAAEPEEPAEPQQQQQPAE下 面 求 出 狀 態(tài) 轉(zhuǎn) 換 平 衡 狀 態(tài) 方 程 ：）且模型的建立3亭模型 假設(shè)簡化c1,c2為常數(shù)，并計算第二個人的無需等待前往時間的期望值，得 用MatLab可以作出 的函數(shù)，并從圖中得出結(jié)果3. 模型的求解亭模型21 1,22121,221,2()(1()Uc tcPttN tt22wTtT0( )1,0 xtxtN xedtex 21,2()Ut排隊論課件模型的求解2亭模型Average call time (

38、min*10) U2 t2508.051617.08023.051632.5 第三個人的無需等待前往時間的期望值，同理可以算出，并用圖解法求出模型的求解3亭模型2,3231,31231,3231,321,231,31,21,2231,321,2231,312231,321,2231,312231,3(1()()()()(1()()(1()(1()()(1()(1()()tN tttPtttN tttN ttN ttttPttN ttG tttPPtttN ttG tttPPttt 但是第4個人，第5個人呢？ 這種方法太繁瑣似乎不好用 可否有近似的算法？排隊論課件125 與前一個模型的區(qū)別在于：

39、系統(tǒng)容量是c1,效力時間固定，顧客的到達(dá)依然是Poisson流。4. 模型的建立 過山車模型排隊論課件還要思索：實踐的FastPass系統(tǒng) 有兩條隊列： FastPass和Standby隊列 不思索standby隊列， 將得到Greedy algorithm模型 思索standby隊列， 將得到成效函數(shù)模型模型的建立2過山車排隊論課件127模型的建立3過山車模型貪婪算法模型的建立4過山車模型很容易想到，全局優(yōu)化的目的變量1. 假設(shè)開車的時間不固定，那么a%是多少最優(yōu)？就是說顧客坐滿多少就開車？ 2.假設(shè)開車的時間間隔是固定的，那么多長時間開一次是最優(yōu)的？衡量的規(guī)范：目的函數(shù)模型的建立5過山車模

40、型排隊論課件131一個區(qū)間內(nèi)的顧客前往表示圖排隊論課件132目的函數(shù)：模型的建立6過山車模型121121,1,2,1,2 2,2212121212,.()()()()()()kjjiij kkkkkjkjkjkkkjkkkjjkjkkkkkh hhbbbttzzEc tc tE c tc tc EEtc bEcc Ectc bccctcj-1i2,iii個人被安排在中的一班車設(shè)i個人的返回時間是則t121)()jjkkkbEccctk常數(shù)， 由 決定，222%,jjjjkjjcacbc bckb ，如果開車時坐滿的人數(shù)固定如果開車的時間間隔固定則常數(shù)模型的建立7過山車模型怎樣求解最優(yōu)的怎樣求解

41、最優(yōu)的a%ca%c和最優(yōu)的開車間隔？和最優(yōu)的開車間隔？對于這類復(fù)雜的問題，離散仿真是最對于這類復(fù)雜的問題，離散仿真是最好的方法了好的方法了仿真：用計算機生成一些符合某種分布的隨機數(shù)據(jù)點，模擬離散時間的發(fā)生這里的仿真用MatLab完成：步驟：1.生成Poisson顧客流模擬到達(dá)時間 2.給定不同的a%c, 開車時間間隔不定，計算代價函數(shù)，畫出代價函數(shù)性能曲線 3.開車時間固定，給出不同的開車時間間隔，計算畫出代價函數(shù)性能曲線 4.得出最優(yōu)的結(jié)論5. 模型的仿真過山車模型 過山車模型的仿真5.1得到在第在第j j天的某一固天的某一固定時辰定時辰 i i 采集樣本采集樣本, ,i=1m,i=1m,j

42、=1100j=1100構(gòu)成樣本空間的構(gòu)成樣本空間的矩陣矩陣11121,10021222,100,1,2,100. . . . . .mmmlllllllll( ) t 過山車模型的仿真5.1 用列向量的均值用列向量的均值估計參數(shù)估計參數(shù)樣本的更新用時間序列樣本的更新用時間序列的方法的方法time serial time serial analysisanalysis, ,計算列向計算列向量的量的EucilidEucilid間隔間隔dthresholddthreshold就更新一就更新一次次( )it,1,2,100,. Tiiimeanlll21()mkkkdll 對某一個或一組變量x(t)進(jìn)展察看丈量，將在一系列時辰t1, t2, , tn (t為自變量且t1t2 tn ) 所得到的離散數(shù)字組成序列集合 x(t1), x(t2), , x(tn) 稱為時間序列，這種有時間意義的序列也稱為動態(tài)數(shù)據(jù)。時間序列分析是根據(jù)系統(tǒng)觀測得到的時間序列數(shù)據(jù)，經(jīng)過曲線擬合和參數(shù)估計來建立數(shù)學(xué)模型的實際和方法 時間序列分析time serial analysis排隊論課件138生成的樣本空間過山車模型