給16萌萌噠的小學(xué)妹弟研一上運(yùn)籌學(xué)

1、1OPERATIONS RESEARCH運(yùn)籌學(xué)把握住隨機(jī) 鄭江波2排隊(duì)論(Queuing Theory) 排隊(duì)論（queuing),也稱(chēng)隨機(jī)服務(wù)系統(tǒng)理論，是運(yùn)籌學(xué)的一個(gè)主要分支。 1909年，丹麥哥本哈根電子公司電話工程師A. K. Erlang的開(kāi)創(chuàng)性論文“概率論和電話通訊理論”標(biāo)志此理論的誕生。排隊(duì)論的發(fā)展最早是與電話，通信中的問(wèn)題相聯(lián)系的，直到現(xiàn)在這還是排隊(duì)論的傳統(tǒng)的應(yīng)用領(lǐng)域。近年來(lái)在計(jì)算機(jī)通訊網(wǎng)絡(luò)系統(tǒng)、交通運(yùn)輸、醫(yī)療衛(wèi)生系統(tǒng)、庫(kù)存管理、作戰(zhàn)指揮等各領(lǐng)域中均得到應(yīng)用。31.1 排隊(duì)系統(tǒng)的組成與特征 排隊(duì)系統(tǒng)一般有三個(gè)基本組成部分：1.輸入過(guò)程；2.排隊(duì)規(guī)則；3.服務(wù)機(jī)構(gòu)。1 排隊(duì)論的基本

2、概念4輸入即為顧客的到達(dá)，可有下列3種情況：1）顧客來(lái)源。顧客總體(稱(chēng)為顧客源)的組成可能是有限的，也可能是無(wú)限的。如，上游河水流入水庫(kù)可以認(rèn)為總體是無(wú)限的，工廠內(nèi)停機(jī)待修的機(jī)器顯然是有限的總體。2）顧客到達(dá)方式。顧客到來(lái)的方式可能是一個(gè)一個(gè)的，也可能是成批的。如，到餐廳就餐就有單個(gè)到來(lái)的顧客和受邀請(qǐng)來(lái)參加宴會(huì)的成批顧客。 1. 輸入過(guò)程53）顧客流的概率分布。顧客隨機(jī)一個(gè)(批)個(gè)(批)來(lái)到排隊(duì)系統(tǒng)，顧客流的概率分布用來(lái)描述相繼到達(dá)的顧客之間的間隔時(shí)間分布是確定的還是隨機(jī)的，分布參數(shù)是什么，到達(dá)的間隔時(shí)間是否獨(dú)立，分布是隨時(shí)間變化的還是平穩(wěn)的。62. 排隊(duì)規(guī)則 1）損失制。顧客到達(dá)時(shí)，如果所有

3、的服務(wù)臺(tái)都被占用，且服務(wù)機(jī)構(gòu)又不允許顧客等待，顧客只能離去，這種服務(wù)規(guī)則就是損失制。2）等待制。當(dāng)顧客到達(dá)時(shí)，如果所有服務(wù)臺(tái)都被顧客占用而無(wú)空閑，這時(shí)該顧客自動(dòng)加入隊(duì)列排隊(duì)等待服務(wù)，服務(wù)完才離開(kāi)。 （1）先到先服務(wù) FCFS （2）后到先服務(wù) LCFS（3）隨機(jī)服務(wù)RAND （4）有優(yōu)先權(quán)服務(wù) PR 73. 服務(wù)機(jī)構(gòu) 1）服務(wù)機(jī)構(gòu)可以是單服務(wù)員和多服務(wù)員服務(wù)，這種服務(wù)形式與隊(duì)列規(guī)則聯(lián)合后形成了多種不同隊(duì)列，不同形式的排隊(duì)服務(wù)機(jī)構(gòu)，如：8 2)服務(wù)方式分為單個(gè)顧客服務(wù)和成批顧客服務(wù)。 3)服務(wù)時(shí)間分為確定型和隨機(jī)型。 4)服務(wù)時(shí)間的分布在這里我們假定是平穩(wěn)的。9上述特征中最主要的、影響最大的是：

4、顧客相繼到達(dá)的間隔時(shí)間分布服務(wù)時(shí)間的分布服務(wù)臺(tái)數(shù) D.G.Kendall，1953提出了分類(lèi)法，稱(chēng)為Kendall記號(hào)(適用于并列服務(wù)臺(tái))即：X/Y/Z:A/B/C1.2 排隊(duì)系統(tǒng)的模型分類(lèi)10式中：X顧客相繼到達(dá)間隔時(shí)間分布。M負(fù)指數(shù)分布Markov，D確定型分布（Deterministic）EkK階愛(ài)爾朗分布Erlang， G 一般隨機(jī)分布GI 一般相互獨(dú)立隨機(jī)分布(General Independent) Y填寫(xiě)服務(wù)時(shí)間分布（與上同）Z填寫(xiě)并列的服務(wù)臺(tái)數(shù)A排隊(duì)系統(tǒng)的最大容量B顧客源數(shù)量 C排隊(duì)規(guī)則 如 M/M/1:/FCFS即為顧客到達(dá)為泊松過(guò)程，服務(wù)時(shí)間為負(fù)指數(shù)分布，單臺(tái)，無(wú)限容量，無(wú)

5、限源，先到先服務(wù)的排隊(duì)系統(tǒng)模型。11系統(tǒng)指標(biāo)隊(duì)長(zhǎng)，指在系統(tǒng)中的顧客數(shù)，它的期望值記Ls；(2) 排隊(duì)長(zhǎng)，指在系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)，它的期望值記作Lq 系統(tǒng)中顧客 數(shù)在隊(duì)列中等待服務(wù)的顧客數(shù)正被服務(wù)的顧客數(shù)+=一般情形，Ls(或Lq)越大，說(shuō)明服務(wù)效率越低。12(3) 逗留時(shí)間，指一個(gè)顧客在系統(tǒng)中的停留時(shí)間，它的期望值記作Ws；(4) 等待時(shí)間，指一個(gè)顧客在系統(tǒng)中排隊(duì)等待的時(shí)間，它的期望值記作Wq；等待時(shí)間服務(wù)時(shí)間+逗留時(shí)間=131.3 排隊(duì)論研究的基本問(wèn)題 （1）排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷:即通過(guò)對(duì)排隊(duì)系統(tǒng)主要參數(shù)的統(tǒng)計(jì)推斷和對(duì)排隊(duì)系統(tǒng)的結(jié)構(gòu)分析，判斷一個(gè)給定的排隊(duì)系統(tǒng)符合于哪種模型，以便根據(jù)排

6、隊(duì)理論進(jìn)行研究。 （2）系統(tǒng)性態(tài)問(wèn)題:即研究各種排隊(duì)系統(tǒng)的概率規(guī)律性，主要研究隊(duì)長(zhǎng)分布、等待時(shí)間分布和服務(wù)期分布等統(tǒng)計(jì)指標(biāo),包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。 （3）最優(yōu)化問(wèn)題：即包括最優(yōu)設(shè)計(jì)(靜態(tài)優(yōu)化)，最優(yōu)運(yùn)營(yíng)（動(dòng)態(tài)優(yōu)化）。 141.4 排隊(duì)問(wèn)題求解(主要指性態(tài)問(wèn)題) 排隊(duì)問(wèn)題的一般步驟： 1. 確定或擬合排隊(duì)系統(tǒng)顧客到達(dá)的時(shí)間間隔分布和服務(wù)時(shí)間分布(可實(shí)測(cè))。 2. 研究系統(tǒng)狀態(tài)的概率。系統(tǒng)狀態(tài)是指系統(tǒng)中顧客數(shù)。狀態(tài)概率用Pn(t)表示,即在t時(shí)刻系統(tǒng)中有n個(gè)顧客的概率，也稱(chēng)瞬態(tài)概率。15 求解狀態(tài)概率Pn(t)方法是建立含Pn(t)的微分差分方程，通過(guò)求解微分差分方程得到系統(tǒng)瞬態(tài)解，由于瞬態(tài)解

7、一般求出確定值比較困難，即便求得一般也很難使用。因此我們常常使用它的極限(如果存在的話)： 穩(wěn)態(tài)的物理意義見(jiàn)右圖，系統(tǒng)的穩(wěn)態(tài)一般很快都能達(dá)到，但實(shí)際中達(dá)不到穩(wěn)態(tài)的現(xiàn)象也存在。值得注意的是求穩(wěn)態(tài)概率Pn并不一定求t的極限,而只需求Pn(t)=0 即可。過(guò)渡狀態(tài)穩(wěn)定狀態(tài)pnt圖3 排隊(duì)系統(tǒng)狀態(tài)變化示意圖 稱(chēng)為穩(wěn)態(tài)(steady state)解，或稱(chēng)統(tǒng)計(jì)平衡狀態(tài) (Statistical Equilibrium State)的解。162 到達(dá)間隔時(shí)間分布和服務(wù)時(shí)間的分布 一個(gè)排隊(duì)系統(tǒng)的最主要特征參數(shù)是顧客的到達(dá)間隔時(shí)間分布與服務(wù)時(shí)間分布。要研究到達(dá)間隔時(shí)間分布與服務(wù)時(shí)間分布需要首先根據(jù)現(xiàn)存系統(tǒng)原始資

8、料統(tǒng)計(jì)出它們的經(jīng)驗(yàn)分布，然后與理論分布擬合，若能對(duì)應(yīng)，我們就可以得出上述的分布情況。172.1 經(jīng)驗(yàn)分布 經(jīng)驗(yàn)分布是對(duì)排隊(duì)系統(tǒng)的某些時(shí)間參數(shù)根據(jù)經(jīng)驗(yàn)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，并依據(jù)統(tǒng)計(jì)分析結(jié)果假設(shè)其統(tǒng)計(jì)樣本的總體分布，選擇合適的檢驗(yàn)方法進(jìn)行檢驗(yàn)，當(dāng)通過(guò)檢驗(yàn)時(shí)，我們認(rèn)為時(shí)間參數(shù)的經(jīng)驗(yàn)數(shù)據(jù)服從該假設(shè)分布。 分布的擬合檢驗(yàn)一般采用2檢驗(yàn)。由數(shù)理統(tǒng)計(jì)的知識(shí)我們知：若樣本量n充分大(n50)，則當(dāng)假設(shè)H0為真時(shí)，統(tǒng)計(jì)量總是近似地服從自由度為k-r-1的 2分布，其中k為分組數(shù)，r為檢驗(yàn)分布中被估計(jì)的參數(shù)個(gè)數(shù)。182.2 理論分布 式中為常數(shù)(0)，稱(chēng)X服從參數(shù)為的泊松分布，若在上式中引入時(shí)間參數(shù)t，即令t代替，

9、則有： 1.泊松分布 在概率論中，我們?cè)鴮W(xué)過(guò)泊松分布，設(shè)隨機(jī)變量為X，則有：n=0,1,2, （1） 與時(shí)間有關(guān)的隨機(jī)變量的概率，是一個(gè)隨機(jī)過(guò)程，即泊松過(guò)程。 t0，n=0,1,2, （2）19（t2t1，n0） 若設(shè)N(t)表示在時(shí)間區(qū)間0,t)內(nèi)到達(dá)的顧客數(shù)(t0),Pn(t1,t2)表示在時(shí)間區(qū)間t1,t2)(t2t1)內(nèi)有n(0)個(gè)顧客到達(dá)的概率。即： 在一定的假設(shè)條件下 顧客的到達(dá)過(guò)程就是一個(gè)泊松過(guò)程。 當(dāng)Pn(t1,t2)符合下述三個(gè)條件時(shí)，顧客到達(dá)過(guò)程就是泊松過(guò)程(顧客到達(dá)形成泊松流)。20 無(wú)后效性：各區(qū)間的到達(dá)相互獨(dú)立,即Markov性。 也就是說(shuō)過(guò)程在tn所處的狀態(tài)與 以前

10、所處的狀態(tài)無(wú)關(guān)(t+t的狀態(tài)與t之前的狀態(tài)無(wú)關(guān)） 。平穩(wěn)性：即對(duì)于足夠小的t，有：泊松流具有如下特性： 在t,t+t內(nèi)有一個(gè)顧客到達(dá)的概率與t無(wú)關(guān),而與t成正比。21 普通性：對(duì)充分小的t,在時(shí)間區(qū)間（t,t+t）內(nèi)有2個(gè)或2個(gè)以上顧客到達(dá)的概率是一高階無(wú)窮小.由此知，在(t，t+t)區(qū)間內(nèi)沒(méi)有顧客到達(dá)的概率為： 令t1=0,t2=t,則P(t1,t2)=Pn(0,t)=Pn(t) 0 是常數(shù)，它表示單位時(shí)間到達(dá)的顧客數(shù)，稱(chēng)為概率強(qiáng)度。即P0+P1+P2=1在上述假設(shè)下，t時(shí)刻系統(tǒng)中有n個(gè)顧客的概率pn(t)： 22 A n pn(t) 01-t+ (t) pn(t)(1-t+ (t)B n-

11、1 pn-1(t) 1t pn-1(t)t(t) (t)n-2 Pn-2(t) 2C n-3 Pn-3(t) 30 P0(t) n23(1)(2)當(dāng)n=0時(shí)，則(3)（沒(méi)有顧客到達(dá)的概率）將（3）代入（1）式，運(yùn)用數(shù)學(xué)歸納法求出（4）瞬態(tài)方程求解（2）的微分方程，可得：24級(jí)數(shù)令k=n-1，則：同理方差為：顧客到達(dá)過(guò)程是一個(gè)泊松過(guò)程(泊松流)。期望252.負(fù)指數(shù)分布 可以證明當(dāng)輸入過(guò)程是泊松流時(shí)，兩顧客相繼到達(dá)的時(shí)間間隔T獨(dú)立且服從負(fù)指數(shù)分布。（等價(jià)） 因?yàn)榈竭_(dá)為泊松流，所以，t時(shí)段內(nèi)沒(méi)有來(lái)顧客的概率為所以， t時(shí)段內(nèi)有顧客到來(lái)（即間隔T t ）的概率為而這正是負(fù)指數(shù)分布的分布函數(shù)，說(shuō)明T 服

12、從負(fù)指數(shù)分布，且參數(shù)同為 。26 表示單位時(shí)間內(nèi)顧客平均到達(dá)數(shù),1/表示顧客到達(dá)的平均間隔時(shí)間。對(duì)顧客的服務(wù)時(shí)間：系統(tǒng)處于忙期時(shí)兩顧客相繼離開(kāi)系統(tǒng)的時(shí)間間隔，一般地也服從負(fù)指數(shù)分布，服務(wù)時(shí)間的分布：，則其中：表示單位時(shí)間內(nèi)能被服務(wù)的顧客數(shù)，即平均服務(wù)率。 1/表示一個(gè)顧客的平均服務(wù)時(shí)間。令 ，則稱(chēng)為服務(wù)強(qiáng)度?？梢宰C明：27 3.愛(ài)爾朗(Erlang)分布 設(shè)v1, v2，, vk是k個(gè)獨(dú)立的隨機(jī)變量，服從相同參數(shù) k 的負(fù)指數(shù)分布，那么：其概率密度是28 串聯(lián)的k個(gè)服務(wù)臺(tái)，每臺(tái)服務(wù)時(shí)間相互獨(dú)立，服從相同的負(fù)指數(shù)分布（參數(shù)k），那么一顧客走完k個(gè)服務(wù)臺(tái)總共所需要服務(wù)時(shí)間就服從上述的k階Erlan

13、g分布。則稱(chēng)T服從k階愛(ài)爾朗分布。其特征值為：,1/ k表示一個(gè)顧客的一個(gè)服務(wù)臺(tái)的平均服務(wù)時(shí)間。29 例:有易碎物品500件,由甲地運(yùn)往乙地,根據(jù)以往統(tǒng)計(jì)資料,在運(yùn)輸過(guò)程中易碎物品按泊松分布發(fā)生破碎,其破損率為0.002,現(xiàn)求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破損的概率. 解: =0.002500=1 1破碎3件物品的概率為: P(k=3)=(3/3！)e-=(13/3！)e-1=0.0613 即物品破碎3件的概率為6.13 2.破碎物品少于3件的概率:30 破碎物品少于3件的概率為91.97破碎物品多于3件的概率為:3.至少有一件破碎的概率為 P

14、k1=1-(1k/k!)e-=1-(10/0!)e-1=0.63231 對(duì)排隊(duì)模型，在給定輸入和服務(wù)條件下，主要研究系統(tǒng)的下述運(yùn)行指標(biāo)： (1)系統(tǒng)的平均隊(duì)長(zhǎng)Ls(期望值)和平均隊(duì)列長(zhǎng)Lq(期望值)； (2)系統(tǒng)中顧客平均逗留時(shí)間Ws與隊(duì)列中平均等待時(shí)間Wq； 本節(jié)只研究M/M/1模型，下面分三種情況討論：3.M/M/1模型323.1 標(biāo)準(zhǔn)的M/M/1模型 M/M/1:/FCFS模型 1.穩(wěn)態(tài)概率Pn的計(jì)算 在任意時(shí)刻t，狀態(tài)為n的概率Pn(t)（瞬態(tài)概率），它決定了系統(tǒng)的運(yùn)行特征。 已知顧客到達(dá)服從參數(shù)為的泊松過(guò)程，服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布。現(xiàn)仍然通過(guò)研究區(qū)間t，t+t）的變化來(lái)求解。

15、在時(shí)刻t+t，系統(tǒng)中有n個(gè)顧客不外乎有下列四種情況（ t，t+t）內(nèi)到達(dá)或離開(kāi)2個(gè)以上沒(méi)列入）。？ 33 由于這四種情況是互不相容的，所以Pn(t+t)應(yīng)是這四項(xiàng)之和，則有：所有的高階無(wú)窮小合并34令t0，得關(guān)于Pn(t)的微分差分方程：(1) 當(dāng)n=0時(shí)，只有表中的（A）、（B）兩種情況，因?yàn)樵谳^小的t內(nèi)不可能發(fā)生（D）（到達(dá)后即離去），若發(fā)生可將t取小即可。(2)生滅過(guò)程瞬態(tài)解35由此可得該排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移圖：由（4）得：其中服務(wù)強(qiáng)度 將其代入（3）式并令n=1,2,(也可從狀態(tài)轉(zhuǎn)移圖中看出狀態(tài)平衡方程)得：關(guān)于Pn的差分方程n-1nn+1201穩(wěn)態(tài)時(shí)， 它對(duì)時(shí)間的導(dǎo)數(shù)為0，所以由(1)

16、、(2)兩式得：Pn(t)與時(shí)間無(wú)關(guān),可以寫(xiě)成Pn,(3)(4)36n=1n=237以此類(lèi)推，當(dāng)n=n時(shí)，(5)以及概率性質(zhì)知：(數(shù)列的極限為 )(6)否則排隊(duì)無(wú)限遠(yuǎn)系統(tǒng)穩(wěn)態(tài)概率系統(tǒng)的運(yùn)行指標(biāo)382. 系統(tǒng)的運(yùn)行指標(biāo)計(jì)算 (1) 系統(tǒng)中的隊(duì)長(zhǎng)Ls（平均隊(duì)長(zhǎng)）(00)=Lq43例1 某修理店只有一個(gè)修理工人，來(lái)修理的顧客到達(dá)服從泊松流，平均每小時(shí)4人；修理時(shí)間服從負(fù)指數(shù)分布，平均需6分鐘。求：（1）修理店空閑的概率；（2）店內(nèi)有3個(gè)顧客的概率；（3）店內(nèi)至少有1個(gè)顧客的概率；（4）店內(nèi)顧客的平均數(shù)；（5）顧客在店內(nèi)的平均逗留時(shí)間；（6）等待服務(wù)的顧客平均數(shù)；（7）平均等待修理時(shí)間；（8）必須在店內(nèi)消耗15分鐘以上的概率。4445例2： 某醫(yī)院手術(shù)室根據(jù)病人來(lái)診和完成手術(shù)的時(shí)間記錄，任意抽查100個(gè)工作小時(shí)，每小時(shí)來(lái)就診的病人數(shù)n的出現(xiàn)次數(shù)如表1。又任意抽查了100個(gè)完成手術(shù)的病歷，所用時(shí)間v(小時(shí))出現(xiàn)的次數(shù)如表2。計(jì)算手術(shù)室的各項(xiàng)指標(biāo)。46到達(dá)的病人數(shù)n出現(xiàn)次數(shù)fn010128229316410566以上1合計(jì)100為病人完成手術(shù)時(shí)間v(小時(shí))出現(xiàn)次數(shù)fv0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以