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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、 1 / 閑期的分布與顧客閑期的分布與顧客到達(dá)時(shí)間間隔的一樣到達(dá)時(shí)間間隔的一樣-服從參數(shù)為服從參數(shù)為的的負(fù)指數(shù)分布負(fù)指數(shù)分布計(jì)算有關(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/( - )計(jì)算有關(guān)目的n忙期與閑期 與逗留時(shí)間Ws一樣!?例：某醫(yī)院手術(shù)室每小時(shí)就診病人數(shù)和手術(shù)例：某醫(yī)院手術(shù)室每小時(shí)就診病人數(shù)和手術(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 合計(jì) 100完成手術(shù)時(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 合計(jì) 100 解：到達(dá)的病人數(shù) 出現(xiàn)次數(shù) n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合計(jì) 100每小時(shí)病人平均到達(dá)率1.2100nnu人/小時(shí)每次手術(shù)平均時(shí)間4 .0100rrv小時(shí)/人每小時(shí)完成手術(shù)人數(shù)平均效力率5 .24 .01人/小時(shí)?, 解：到達(dá)的病人數(shù) 出現(xiàn)次數(shù) n un 0 10 1

21、28 2 29 3 16 4 10 5 6 6 以上 1 合計(jì) 100每小時(shí)病人平均到達(dá)率1.2100nnu人/小時(shí)每次手術(shù)平均時(shí)間4 .0100rrv小時(shí)/人每小時(shí)完成手術(shù)人數(shù)平均效力率5 .24 .01人/小時(shí)完成手術(shù)時(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 合計(jì) 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求排隊(duì)系統(tǒng)顧客數(shù)的分布情況01102101.,.2, 1,ppCnpCpnnnnnnnnn其中 1 1 .,.2 , 1,002000110210pppppCwherenpCpNNnnnnnnnnnnn N1,2,.,n 11 11110nNnNPP1) 1 (20NP求排隊(duì)系統(tǒng)顧客數(shù)的分布情況 隊(duì)長(zhǎng)隊(duì)長(zhǎng) 隊(duì)列長(zhǎng)隊(duì)列長(zhǎng) 1101)1(1NNNnnsNnPL)1 ()1(00PLPnLsNnnq計(jì)算有關(guān)目的 逗留時(shí)間逗留時(shí)間 等待時(shí)間等待時(shí)

23、間111Little1 100）（）（公式根據(jù)）（）或（有效到達(dá)率：NqsesseNePLPLLWPP1sqWW計(jì)算有關(guān)目的系統(tǒng)已滿顧客不能到達(dá)的概率-損失率/10eP ）服務(wù)強(qiáng)度：（ 有6個(gè)椅子接待人們排隊(duì)，超越6人顧客就分開，平均到達(dá)率3人/小時(shí)，理發(fā)需時(shí)平均15分鐘。7為系統(tǒng)中的最大顧客數(shù)。平均到達(dá)率: 3人/小時(shí) 平均效力率: 4人/小時(shí)舉例：?jiǎn)稳死戆l(fā)館排隊(duì)問題 顧客到達(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)逗留的期望時(shí)間顧客在理發(fā)館內(nèi)逗留的期望時(shí)間8 .4373. 089. 2/11. 2/essLW小時(shí)分鐘89. 2)2778. 01 (41 10eeNePP）（）或（人/小時(shí) 能夠的顧客中有百分之幾不等待就分開 -求系統(tǒng)中有7個(gè)顧客的概率%7 . 3)4/3(14/31)43()/(1/1)(87877P 設(shè)：設(shè)：m ：為顧客總體數(shù)，：為顧客總體數(shù)， ： 每個(gè)顧客的到達(dá)率，每個(gè)顧客的到達(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é)不同對(duì)顧客而言，而不是對(duì)系統(tǒng)m對(duì)系統(tǒng)而言,有一個(gè)顧客到達(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ù)概率分布 等待時(shí)間等待時(shí)間 正常

26、運(yùn)轉(zhuǎn)的平均設(shè)備臺(tái)數(shù)正常運(yùn)轉(zhuǎn)的平均設(shè)備臺(tái)數(shù)1sqWW)1(0PLms計(jì)算有關(guān)目的 隊(duì)長(zhǎng)隊(duì)長(zhǎng) 隊(duì)列長(zhǎng)隊(duì)列長(zhǎng) 逗留時(shí)間逗留時(shí)間)1(0PmLs)1(0PLLsq1)1(0PmWs計(jì)算有關(guān)目的第第3節(jié)節(jié) 多效力臺(tái)負(fù)指數(shù)多效力臺(tái)負(fù)指數(shù)分布排隊(duì)系統(tǒng)分析分布排隊(duì)系統(tǒng)分析規(guī)定：規(guī)定：各效力臺(tái)任務(wù)是相互獨(dú)立的，且平均效力率一樣各效力臺(tái)任務(wù)是相互獨(dú)立的，且平均效力率一樣，均為，均為 。整個(gè)效力機(jī)構(gòu)的平均效力率為：整個(gè)效力機(jī)構(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時(shí)，不會(huì)排成無限隊(duì)列。時(shí)，不會(huì)排成無限隊(duì)列。 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ù)=正忙的效力臺(tái)數(shù)cnncnnPcnPc10qsLL解釋? )(!1)( !1010cnPcccnPnPnnnn 隊(duì)長(zhǎng)隊(duì)長(zhǎng) 隊(duì)列長(zhǎng)隊(duì)列長(zhǎng) 逗留時(shí)間及等待時(shí)間逗留時(shí)間及等待時(shí)間qqsLLL021)1( !)()(PcPcnLssccnnqssqqLWLW ;獨(dú)一 某售票一切三個(gè)窗口，顧客到達(dá)服從Poisson過程，到達(dá) = 0.9 人/分鐘，效力 =0.4人/分鐘。設(shè)顧客到達(dá)后依次排成一隊(duì)向空閑的窗口購票，如圖 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,符合要求.整個(gè)售票所空閑概率平均隊(duì)長(zhǎng)95.370.10748.0)4/1 ( ! 34/3)25.2(23qsqLLL0748.03/25.211! 325.2!25.212030nnnp平均等待時(shí)間和逗留時(shí)間分鐘分鐘39.44.0/189.1/189.19.0/70.1qsqqWWLW57.00748.04/1!3)25.2()3(3nP顧客到達(dá)后必需等待概率 以上

30、例闡明,設(shè)顧客到達(dá)后在每個(gè)窗口前各排一隊(duì)(其它條件不變),共三隊(duì),每隊(duì)平均到達(dá)率為:3 . 03/9 . 0321 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.3 = 0.3 = 0.3 = 0.9圖 b結(jié)果比較 形狀圖是多效力臺(tái)和容量有限的綜合形狀圖是多效力臺(tái)和容量有限的綜合 平衡方程平衡方程他會(huì)嗎?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ái)平均被占用的效力臺(tái) 求系統(tǒng)的目的求系統(tǒng)的目的1 , )(seqqessqsNcnnqWLWLWcLLpcnL設(shè)系統(tǒng)的平均到達(dá)率為設(shè)系統(tǒng)的平均到達(dá)率為 ，任一顧客的效力時(shí)間為，任一顧客的效力時(shí)間為 V , 且有：且有： E(V ) = 1/ ，D(V ) = 2 效力強(qiáng)度效力強(qiáng)度 ： = / 不論不論V服從什么分布，只需服從什么分布，只需 1 ,系統(tǒng)就會(huì)到達(dá)穩(wěn)態(tài)，并有穩(wěn)態(tài)概率為：系統(tǒng)就會(huì)到達(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)對(duì)各顧客的效力時(shí)間相互獨(dú)立且為同一個(gè)常數(shù) v， 那么有： E(v) = v = 1/ 0,s0,PN(s+t)-N(t)=k=排隊(duì)論課件Poisson Processexp()ititi顧客到達(dá)時(shí)間間隔（t）exp( (t)t)T 顧客 接受服務(wù)的時(shí)間（t）和 的確定都將在后面仿真的部分給出排隊(duì)論課件112 分析1：能否得到準(zhǔn)確的前往時(shí)間？ (1. ),1immii1,m+1ii1,m+1如果能夠準(zhǔn)確得知前面所有顧客的到達(dá)時(shí)間間隔t 和接受服務(wù)的時(shí)間T當(dāng)然可以知道

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

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

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

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

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

38、min*10) U2 t2508.051617.08023.051632.5 第三個(gè)人的無需等待前往時(shí)間的期望值，同理可以算出，并用圖解法求出模型的求解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個(gè)人，第5個(gè)人呢？ 這種方法太繁瑣似乎不好用 可否有近似的算法？排隊(duì)論課件125 與前一個(gè)模型的區(qū)別在于：

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

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

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

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