算法大全第06章排隊論

1、- - -第六章排隊論模型排隊論起源丁1909年丹麥電話工程師AK.愛爾朗的工作，他對電話通話擁擠問題進行了研究。1917年，愛爾朗發(fā)表了他的著名的文章一“自動電話交換中的概率理論的幾個問題的解決”。排隊論已廣泛應用丁解決軍事、運輸、維修、生產(chǎn).服務.庫存、醫(yī)療衛(wèi)生、教育.水利灌溉之類的排隊系統(tǒng)的問題，顯示了強人的生命力。排隊是在口常生活中經(jīng)常遇到的現(xiàn)彖，如顧客到商店購買物品、病人到醫(yī)院看病常常要排隊。此時要求服務的數(shù)危超過服務機構(gòu)(服務臺、服務員等)的容鼠。也就是說,到達的顧客不能立即得到服務，因而出現(xiàn)了排隊現(xiàn)彖。這種現(xiàn)彖不僅在個人口常生活中出現(xiàn)，電話局的占線問題，車站、碼頭等交通樞紐的車船

2、堵塞和疏導，故障機器的停機待修，水庫的存貯調(diào)節(jié)等都是有形或無形的排隊現(xiàn)彖。由顧客到達和服務時間的隨機性。可以說排隊現(xiàn)彖兒乎是不可避免的。排隊論(QueuingTheory)也稱隨機服務系統(tǒng)理論，就是為解決上述問題而發(fā)展的一門學科。它研究的內(nèi)容有下列三部分：性態(tài)問題，即研究各種排隊系統(tǒng)的概率規(guī)律性，主要是研究隊長分布.等待時間分布和忙期分布等，包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。最優(yōu)化問題，又分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設(shè)計。后者指現(xiàn)有排隊系統(tǒng)的最優(yōu)運營。排隊系統(tǒng)的統(tǒng)計推斷，即判斷一個給定的排隊系統(tǒng)符合丁哪種模型，以便根據(jù)排隊理論進行分析研究。這里將介紹排隊論的一些基本知識，分析兒個常見的排隊模型。1

3、基本概念1.1排隊過程的一般表示卜圖是排隊論的一般模型。圖1井隊模型圖中虛線所包含的部分為排隊系統(tǒng)。各個顧客從顧客源出發(fā)，隨機地來到服務機構(gòu)，按一定的排隊規(guī)則等待服務，直到按一定的服務規(guī)則接受完服務后離開排隊系統(tǒng)。凡要求服務的對彖統(tǒng)稱為顧客，為顧客服務的人或物稱為服務員，由顧客和服務員組成服務系統(tǒng)。対J：一個服務系統(tǒng)來說，如果服務機構(gòu)過小，以致不能滿足要求服務的眾多顧客的需耍，那么就會產(chǎn)生擁擠現(xiàn)彖而使服務質(zhì)杲降低。因此，顧客總希望服務機構(gòu)越人越好，但是，如果服務機構(gòu)過人，人力和物力方而的開支也就相應增加，從U會造成浪費，因此研究排隊模型的目的就是要在顧客需要和服務機構(gòu)的規(guī)模Z間進行權(quán)衡決策，使

4、其達到合理的平衡。1.2排隊系統(tǒng)的組成和特征一般的排隊過程都由輸入過程、排隊規(guī)則、服務過程三部分組成，現(xiàn)分述如卜I1.2.1輸入過程輸入過程是指顧客到來時間的規(guī)律性，可能有下列不同情況：顧客的組成可能是有限的，也可能是無限的。顧客到達的方式可能是一個一個的，也可能是成批的。顧客到達可以是相互獨立的，即以前的到達情況對以后的到達沒有影響；否則是相關(guān)的。(込)輸入過程可以是平穩(wěn)的，即相繼到達的間隔時間分布及其數(shù)學期望、方差等數(shù)字特征都與時間無關(guān)，否則是非平穩(wěn)的。1.2.2排隊規(guī)則排隊規(guī)則指到達排隊系統(tǒng)的顧客按怎樣的規(guī)則排隊等待，可分為損失制，等待制和混合制二種。損失制(消失制)。當顧客到達時，所有

5、的服務臺均被占用，顧客隨即離去。等待制。當顧客到達時，所有的服務臺均被占用，顧客就排隊等待，直到接受完服務才離去。例如出故障的機器排隊等待維修就是這種情況?；旌现?。介丁損失制和等待制之間的是混合制，即既有等待又有損失。有隊列長度有限和排隊等待時間有限兩種情況，在限度以內(nèi)就排隊等待，超過一定限度就離去。排隊方式還分為單列、多列和循壞隊列。1.2.3服務過程服務機構(gòu)。主耍有以卜兒種類型：單服務臺；多服務臺并聯(lián)(每個服務臺同時為不同顧客服務)；多服務臺串聯(lián)(多服務臺依次為同一顧客服務)；混合型。服務規(guī)則。按為顧客服務的次序采用以卜幾種規(guī)則：先到先服務，這是通常的情形。后到先服務，如情報系統(tǒng)中，最后到

6、的情報信息往往最有價值，因而常被優(yōu)先處理。隨機服務，服務臺從等待的顧客中隨機地取其一進行服務，而不管到達的先后。優(yōu)先服務，如醫(yī)療系統(tǒng)對病情嚴重的病人給予優(yōu)先治療。1.3排隊模型的符號表示排隊模型用六個符號表示，在符號之間用斜線隔開,即X/Y/Z/A/B/C.第一個符號%表示顧客到達流或顧客到達間隔時間的分布；第二個符號丫表示服務時間的分布；第三個符號Z表示服務臺數(shù)目；第四個符號A是系統(tǒng)容鼠限制；第五個符號是顧客源數(shù)目；第六個符號C是服務規(guī)則，如先到先服務FCFS,后到先服務LCFS等。并約定，如略去后三項，即指X/y/Z/s/s/FCFS的情形。我們只討論先到先服務FCFS的情形，所以略去第六

7、項。表示顧客到達間隔時間和服務時間的分布的約定符號為：指數(shù)分布(M是Markov的字頭，因為指數(shù)分布具有無記憶性，即Markov性)；D確定型(Deterministic)；Ekk階愛爾朗(Erlang)分布：G般(general)服務時間的分布；GI般相互獨立(GeneralIndependent)的時間間隔的分布。例如，M/M/1表示相繼到達間隔時間為指數(shù)分布、服務時間為指數(shù)分布、單服務臺、等待制系統(tǒng)。D/M/c表示確定的到達時間、服務時間為指數(shù)分布、c個平行服務臺(但顧客是一隊)的模型。1.4排隊系統(tǒng)的運行指標為了研究排隊系統(tǒng)運行的效率，估計其服務質(zhì)鼠，確定系統(tǒng)的最優(yōu)參數(shù)，評價系統(tǒng)的結(jié)構(gòu)

8、是否合理并研究其改進的措施，必須確定用以判斷系統(tǒng)運行優(yōu)劣的基本數(shù)起指標，這些數(shù)駅指標通常是：平均隊長：指系統(tǒng)內(nèi)顧客數(shù)(包括正被服務的顧客與排隊等待服務的顧客)的數(shù)學期望，記作平均排隊長:指系統(tǒng)內(nèi)等待服務的顧客數(shù)的數(shù)學期望，記作q。平均逗留時間：顧客在系統(tǒng)內(nèi)逗留時間(包括排隊等待的時間和接受服務的時間)的數(shù)學期望，記作W、.。平均等待時間：指一個顧客在排隊系統(tǒng)中排隊等待時間的數(shù)學期望，記作(V)平均忙期：指服務機構(gòu)連續(xù)繁忙時間(顧客到達空閑服務機構(gòu)起，到服務機構(gòu)再次空閑止的時間)長度的數(shù)學期塑，記為。還有由j:顧客被拒絕而使企業(yè)受到損失的損失率以及以后經(jīng)常遇到的服務強度等,這些都是很重要的指標。

9、計算這些指標的基礎(chǔ)是表達系統(tǒng)狀態(tài)的概率。所謂系統(tǒng)的狀態(tài)即指系統(tǒng)中顧客數(shù),如果系統(tǒng)中有個顧客就說系統(tǒng)的狀態(tài)是“，它的可能值是隊長沒有限制時，“=0丄2,，隊長有限制，最大數(shù)為N時，h=,N,損失制,服務臺個數(shù)是c時,n=0,l,-,co這些狀態(tài)的概率一般是隨時刻/而變化，所以在時刻/、系統(tǒng)狀態(tài)為“的概率用P(t)表示。穩(wěn)態(tài)時系統(tǒng)狀態(tài)為n的概率用Pn表示。2輸入過程與服務時間的分布排隊系統(tǒng)中的事件流包括顧客到達流和服務時間流。由J：顧客到達的間隔時間和服務時間不可能是負值，因此它的分布是非負隨機變堂的分布。最常用的分布有泊松分布、確定型分布，指數(shù)分布和愛爾朗分布。2.1泊松流與指數(shù)分布設(shè)N(f)表

10、示在時間區(qū)間0,0內(nèi)到達的顧客數(shù)(f0),令代(GG)表示在時間區(qū)間心)內(nèi)有“(no)個顧客到達的概率，即代(PN(fJ-N(t2tl9n0)當化J合于卜列三個條件時，我們說顧客的到達形成泊松流。這三個條件是：1擊不相重疊的時間區(qū)間內(nèi)顧客到達數(shù)是和互獨立的，我們稱這性質(zhì)為無后效性。2對充分小的在時間區(qū)間/,/+)內(nèi)有一個顧客到達的概率與f無關(guān)，而約與區(qū)間長/成正比，即片(/+/)=2d+o(d)(1)其中0(),當dTO時，是關(guān)于M的高階無窮小。久0是常數(shù)，它表示單位時間有一個顧客到達的概率，稱為概率強度。3對充分小的/,在時間區(qū)間/,/+/)內(nèi)有兩個或兩個以上顧客到達的概率極小，以致可以忽略

11、，即土化,/+/)=0(h)(2)在上述條件卜，我們研究顧客到達數(shù)的概率分布。由條件2,我們總可以取時間由0算起，并簡記代(0,f)=Pn(t)。由條件1和2,有4(f+0)=A(f)(d)化(/+卜)=化_卍)人(4),=1,2,k=0由條件2和3得Pq(/)=1-AAt+o(M)因而有乙(/+zf)-化(/)/一恥)+讐PQ_=PM)=_厲+砒T(f)+氣2在以上兩式中，取/趨丁零的極限，當假設(shè)所涉及的函數(shù)可導時，得到以卜微分方程組：at嗎=一2化(/)+吧_(),“=1,2,.at取初值4(0)=1,代(0)=0(=1,2,)，容易解出p(f)=”；再令代(/)=“(/)幺7,可以得到/

12、(/)及其它匕所滿足的微分方程組，即d匕dt=久匕t()，匕(/)=0由此容易解得代(0=哼“，=1,2,.n正如在概率論中所學過的，我們說隨機變量(/)=N(s+/)-N(s)服從泊松分布。它的數(shù)學期望和方差分別是EN(t)=At；VarN(f)=2/當輸入過程是泊松流時，那么顧客相繼到達的時間間隔T必服從指數(shù)分布。這是由于PT/=POJ)內(nèi)呼叫次數(shù)為零=P0(t)=eA,那么，以尸(f)表示T的分布函數(shù)，則有PTo0,t0對J泊松流，久表示單位時間平均到達的顧客數(shù)，所以丄就表示和繼顧客到達平均2間隔時間，而這正和ET的意義相符。對一顧客的服務時間也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時間，

13、有時也服從指數(shù)分布。這時設(shè)它的分布函數(shù)和密度函數(shù)分別是G(/)=l-嚴，我們得到vPTtvPtTt這表明，在任何小的時間間隔/+()內(nèi)一個顧客被服務完了(離去)的概率是+“表示單位時間能被服務完成的顧客數(shù)，稱為平均服務率，而丄表示一個顧客的平均服務時間。2.2常用的兒種概率分布及其產(chǎn)生2.2.1常用的連續(xù)型概率分布我們只給出這些分布的參數(shù)、記號和通常的應用范F乩更詳細的內(nèi)容參看專門的概率論書籍。均勻分布區(qū)間(。丄)內(nèi)的均勻分布記作U,b)。服從(0、1)分布的隨機變量又稱為隨機數(shù)，它是產(chǎn)生其它隨機變量的基礎(chǔ)。如若X為(0,1)分布，則Y=a+(b-a)X服從U(a,b)o正態(tài)分布以為期羞，0為

14、方差的正態(tài)分布記作N(/ACT2)o正態(tài)分布的應用十分廣泛。正態(tài)分布還可以作為二項分布一定條件卜的近似。指數(shù)分布指數(shù)分布是單參數(shù)久的非對稱分布，記作Exp(Q),概率密度函數(shù)為：r0r0為一個隨機過程。若N(f)的概率分布貝有以卜性質(zhì)：假設(shè)N(t)=n,則從時刻/起到卜一個顧客到達時刻止的時間服從參數(shù)為人的負指數(shù)分布，”=0,1,2,。假設(shè)N(t)=n,則從時刻/起到I、一個顧客離去時刻止的時間服從參數(shù)為的負指數(shù)分別，“=0丄2,。同一時刻只有一個顧客到達或離去。則稱N(f),f0為一個生滅過程。一般來說,得到N的分布pn(t)=PN=n(n=0,1,2,)是比較困難的,因此通常是求當系統(tǒng)到達

15、平衡后的狀態(tài)分布，記為p,n=0,1,2,o為求平穩(wěn)分布，考慮系統(tǒng)可能處的任一狀態(tài)。假設(shè)記錄了一段時間內(nèi)系統(tǒng)進入狀態(tài)和離開狀態(tài)“的次數(shù)，則因為“進入”和“離開”是交替發(fā)生的，所以這兩個數(shù)要么相等，要么相差為1。但就這兩種事件的平均發(fā)生率來說，可以認為是相等的。即當系統(tǒng)運行相當時間而到達平衡狀態(tài)后，刈任一狀態(tài)來說，單位時間內(nèi)進入該狀態(tài)的平均次數(shù)和單位時間內(nèi)離開該狀態(tài)的平均次數(shù)應該相等，這就是系統(tǒng)在統(tǒng)計平衡卜的“流入=流出”012原理。根據(jù)這一原理，可得到任一狀態(tài)卜的平衡方程如卜：APi=oPo兄0P0+“2=（入+叢）刃入“+仏必之入+叢）/（3）H&L1Pl+“出幾+1=（九+MJPnTOC

16、o 1-5 h znPi=Pl+丄(“2-幾oPo)=牛卩1=Po“2“2Z*21z兄兒*&久oP.=Pl+(ZAP：-AA)=V/?2=“3“33由上述平衡方程，可求得0：1:去養(yǎng)%2：Pn+1=Pn+ZAr+1Arr+1記TOC o 1-5 h zC=血心乞77=1,2,-（4）”角則平穩(wěn)狀態(tài)的分布為幾“”幾，=1,2,由概率分布的要求n=O有i+ix幾=1_/r=l.于是Po=I（6）1+工Gn=l注意：（6）只有當級數(shù)工二C“收斂時才有意義，即當5=1C,_colhf,才能由上(9)(9)述公式得到平穩(wěn)狀態(tài)的概率分布。4M/M/s等待制排隊模型4.1單服務臺模型單服務臺等待制模型M/M

17、/l/oo是指：顧客的相繼到達時間服從參數(shù)為兄的負指數(shù)分布，服務臺個數(shù)為1,服務時間u服從參數(shù)為“的負指數(shù)分布，系統(tǒng)空間無限，允許無限排隊，這是一類最簡單的排隊系統(tǒng)。4.1.1隊長的分布記幾=PN=n（“=（M2）為系統(tǒng)達到平衡狀態(tài)后隊長N的概率分布，則由式（4）（6）,并注意到入=入=0丄2,和九=/厶=0,1,2,。記2P=并設(shè)p（否則隊列將排至無限遠），則故其中因此C,=,“=1,2,k)Pn=pnP=121=E1+工礦/?=!(7)Pn=(1-P)”=12(8)公式（7）和（8）給出了在平衡條件卜系統(tǒng)中顧客數(shù)為的概率。由式（7）不難看出,p是系統(tǒng)中至少有一個顧客的概率，也就是服務臺處J

18、：忙的狀態(tài)的概率，因而也稱。為服務強度，它反映了系統(tǒng)繁忙的程度。此外，（8）式只有在p=-幾=1(1一/t=OH=1=(p+2p2+33+)_(p2+2q3+3q4+)r3P=Q+0+Q+=7=rp/-X平均排隊長d為- - - -00J2=(_1)A=C_(1_A)=C_P=,I、(10)/r=l/(/-X)關(guān)J：顧客在系統(tǒng)中的逗留時間T,可說明它服從參數(shù)為“-2的復指數(shù)分布，即PTt=e,r0因此，平均逗留時間TOC o 1-5 h zWs=(11)因為，顧客在系統(tǒng)中的逗留時間為等待時間7；和接受服務時間VZ和，即T=Tq+V故由比=E(T)=E(Tq)+E(V)=VV+丄(12)可得平均

19、等待時間w。為W=W-=一-一(13)“(“-久)從式(9)和式(11),可發(fā)現(xiàn)平均隊長厶與平均逗留時間W、.貝有關(guān)系厶=久叱(14)同樣，從式(10)和式(13),可發(fā)現(xiàn)平均排隊長厶與平均等待時間具有關(guān)系=化(15)式(14)和式(15)通常稱為Little公式，是排隊論中一個非常重要的公式。4.1.3忙期和閑期在平衡狀態(tài)卜,忙期和閑期/一般均為隨機變量，求它們的分布是比較麻煩的。因此，我們來求一卜平均忙期B和平均閑期T.由J：忙期和閑期出現(xiàn)的概率分別為p和1-，所以在一段時間內(nèi)可以認為忙期和閑期的總長度之比為p：(l-p)o又因為忙期和閑期是交替出現(xiàn)的，所以在允分長的時間里，它們出現(xiàn)的平均

20、次數(shù)應是相同的。J：是，忙期的平均長度歹和閑期的平均長度7之比也應是p：(l-p),即2=-(16)1l-p又因為在到達為Poisson流時，根據(jù)負指數(shù)分布的無記憶性和到達與服務相互獨立的假設(shè)，容易證明從系統(tǒng)空閑時刻起到卜一個顧客到達時刻止(即閑期)的時間間隔仍服從參數(shù)為人的負指數(shù)分布，且與到達時間間隔相互獨立。因此，平均閑期應為丄，這樣,便求得平均忙期為8=-=(17)1-p2_2與式(11)比較，發(fā)現(xiàn)平均逗留時間(W)=平均忙期(直)。這一結(jié)呆直觀看上去是顯然的，顧客在系統(tǒng)中逗留的時間越長，服務員連續(xù)繁忙的時間也就越長。因此，一個顧客在系統(tǒng)內(nèi)的平均逗留時間應等服務員平均連續(xù)忙的時間。2與排

21、隊論模型有關(guān)的LINGO函數(shù)peb(load,S)該函數(shù)的返回值是當?shù)竭_負荷為load,服務系統(tǒng)中有S個服務臺且允許排隊時系統(tǒng)繁忙的概率，也就是顧客等待的概率。pel(load,S)該函數(shù)的返回值是當?shù)竭_負荷為load,服務系統(tǒng)中有S個服務臺且不允許排隊時系統(tǒng)損失概率，也就是顧客得不到服務離開的概率。pfs(load,S,K)該函數(shù)的返回值是當?shù)竭_負荷為load,顧客數(shù)為K,平行服務臺數(shù)看為S時，有限源的Poisson服務系統(tǒng)等待或返修顧客數(shù)的期望值。例1某修理店只有一個修理工，來修理的顧客到達過程為Poisson流，平均4人/h；修理時間服從負指數(shù)分布，平均需要6mino試求：(1)修理店空

22、閑的概率；(2)店內(nèi)恰有3個顧客的概率；(3)店內(nèi)至少有1個顧客的概率；(4)在店內(nèi)的平均顧客數(shù);(5)每位顧客在店內(nèi)的平均逗留時間；(6)等待服務的平均顧客數(shù)；(7)每位顧客平均等待服務時間；(8)顧客在店內(nèi)等待時間超過lOmin的概率。解本例可看成一個M/M/1/s排隊問題，其中2=4,/=-!-=10,p=0.40.1/修理店空閑的概率/?0=1-/?=1-0.4=0.6店內(nèi)恰有3個顧客的概率“3=p3(1-p)=0.45x(1-0.4)=0.38店內(nèi)至少有1個顧客的概率PN1=1-p0=p=04在店內(nèi)的平均顧客數(shù)Lv=-=0.67(人)P每位顧客在店內(nèi)的平均逗留時間=(h)=lO(mi

23、n)24等待服務的平均顧客數(shù)L=Lsp=0.267(人)q-p1-0.4每位顧客平均等待服務時間L0.267打、Wg=-(h)=4(min)顧客在店內(nèi)逗留時間超過lOmin的概率-10(1-)PT10=e615=0.3679編寫LINGO程序如卜：model:(5)(6)(8)(21)- #-(21)- - #-s=l;lamda=4;mu=10;rho=lamda/mu;Pwait=peb(rho,s);pO=l-Pwait;Pt_gt_10=exp(-1);end4.3多服務臺模型（M/M/s/s）設(shè)顧客單個到達，相繼到達時間間隔服從參數(shù)為久的負指數(shù)分布，系統(tǒng)中共有s個服務臺，每個服務臺的

24、服務時間相互獨立，且服從參數(shù)為“的負指數(shù)分布。當顧客到達時，若有空閑的服務臺則馬上接受服務，否則便排成一個隊列等待，等待時間為無限。卜面來討論這個排隊系統(tǒng)的平穩(wěn)分布。記pn=PN=n（n=0J?2,-）為系統(tǒng)達到平穩(wěn)狀態(tài)后隊長W的概率分布，注意到対個數(shù)為s的多服務臺系統(tǒng)，有2“=2,n=0丄2,(21)- #-(21)- #- #-(21)- #-(21)- #- #-2丫=“）”云J一s!嚴(18)Pn=np(19)記ps=，則當QV1時，由式（4）,式（5）和式（6）,有S5/(W川Cn=5時，即系統(tǒng)中顧客數(shù)人J：或等J：服務臺個數(shù)，這時再來的顧客必須等待，因此記Xc(s,Q)=工pn=t

25、l=S式（21）稱為Erlang等待公式，它給出了顧客到達系統(tǒng)時需要等待的概率。対多服務臺等待制排隊系統(tǒng)，由已得到的平穩(wěn)分布可得平均排隊長場為:3C$0Ch=jt+1、rr=j(22)(22)- - - #-Popds!dps/=!L_c(SQ、q1_A記系統(tǒng)中正在接受服務的顧客的平均數(shù)為顯然f也是正在忙的服務臺的平均數(shù)，故IXInon、5=Vnpn+5Ypn=YPo+spQ曰嚴FL“=i(-1)!(5-l)!(l-pj式(24)說明，平均在忙的服務臺個數(shù)不依賴于服務臺個數(shù)s,這是一個有趣的結(jié)果。由式(24),可得到平均隊長厶為Ls=平均排隊長+正在接受服務的顧客的平均數(shù)=Lq+p對多服務臺系

26、統(tǒng)，Little公式依然成立，即有例2某俗票處有3個窗口，顧客的到達為Poisson流，平均到達率為2=0.9人/mm；服務(售票)時間服從負指數(shù)分布，平均服務率“=0.4人/min?，F(xiàn)設(shè)顧客到達后排成一個隊列，依次向空閑的窗口購栗，M/M/s/oo系統(tǒng)，其中久a*Q2.25s=3,p=2.25,p=久3=03（人/min）3卜表給出了M/M/3/s和3個M/M/1/s的比較，不難看出一個M/M/3/s系統(tǒng)比由3個M!M/l/s系統(tǒng)組成的排隊系統(tǒng)具有顯著的優(yōu)越性。即在服務臺個數(shù)和服務率都不變的條件卜單隊排隊方式比多隊排隊方式要優(yōu)越，這是在對排隊系統(tǒng)進行設(shè)計和管理的時候應注意的地方。表1排隊系統(tǒng)

27、的指標值項目M/M/3/s3個M/M/1/co空閑的概率0.07480.25（每個子系統(tǒng)）顧客必須等待的概率0.57075平均隊長3.959（整個系統(tǒng)）平均排隊長1.702.25（每個子系統(tǒng)平均逗留時間4.39(min)10(min)平均等待時間1.8975(min)求解的LINGO程序如卜：model:s=3;lamda=09;mu=04;rho=lamda/mu;rho_s=rho/s;P_wait=peb(rhozs);p0=6*(l-rho_s)/rhoA3*P_wait;L_q=P_wait*rho_s/(l-rho_s);L_s=L_q+rho;W_q=L_q/1amda;W_s=

28、L_s/lamda;end5M/M/s/s損失制排隊模型當s個服務臺被占用后，顧客自動離去。這里我們著重介紹如何使用LINGO軟件中的相關(guān)函數(shù)。5.1損失制排隊模型的基本參數(shù)對損失制排隊模型，其模型的基本參數(shù)與等待制排隊模型有些不同，我們關(guān)心如下指標。（1）系統(tǒng)損失的概率心嚴Pel（rho,s）其中rho是系統(tǒng)到達負荷一，s是服務臺或服務員的個數(shù)。（2）單位時間內(nèi)平均進入系統(tǒng)的顧客數(shù)（心）（3）系統(tǒng)的相対通過能力（0）與絕對通過能力（4）2=1-A=AeQ=-Pozi）=lx0.2+x0.81x200=1401（40120丿第二類是外線打內(nèi)線，其強度為入=lx60=60（4）系統(tǒng)在單位時間內(nèi)占

29、用服務臺（或服務員）的均值（即厶）Ls=入“注意：在損失制排隊系統(tǒng)中，d=o,即等待隊長為0。（5）系統(tǒng)服務臺（或服務員）的效率n=Ls（6）顧客在系統(tǒng)內(nèi)平均逗留時間（即W,）W$=l/注意：在損失制排隊系統(tǒng)中，vv=o,即等待時間為0。在上述公式中，引入人.是十分重要的，因為盡管顧客以平均兄的速率到達服務系統(tǒng)，但當系統(tǒng)被占滿后，有一部分顧客會自動離去，因此，真正進入系統(tǒng)的顧客輸入率是它小于幾。5.2損失制排隊模型計算實例2.1S=1的情況（M/M/1/1）例3設(shè)某條電話線，平均每分鐘有0.6次呼喚，若每次通話時間平均為1.25min,求系統(tǒng)相應的參數(shù)指標。解其參數(shù)為S=l,兄=0.6,/=!

30、o編寫LINGO程序如卜：1.25model:s=l;lamda=06;mu=l/l25;rho=lamda/mu;Plost=pelrho,s）;Q=l-Plost;1amda_e=Q*1amda;A=Q*lamda_e;L_s=1amda_e/mu;eta=L_s/s;end求得系統(tǒng)的顧客損失率為43%,即43%的電話沒有接通，有57%的電話得到了服務，通話率為平均每分鐘有0.195次，系統(tǒng)的服務效率為43%o對于一個服務臺的損失制系統(tǒng),系統(tǒng)的服務效率等于系統(tǒng)的顧客損失率，這一點在理論上也是止確的。5.2.2S1的情況（M/M/S/S）例4某單位電話交換臺有一臺200門內(nèi)線的總機，已知在上

31、班8h的時間內(nèi)，有20%的內(nèi)線分機平均每40min要一次外線電話，80%的分機平均隔120min要一次外線。又知外線打入內(nèi)線的電話平均每分鐘1次。假設(shè)與外線通話的時間平均為3min,并且上述時間均服從負指數(shù)分布，如果要求電話的通話率為95%,問該交換臺應設(shè)置多少條外線？解（1）電話交換臺的服務分成兩類，第一類內(nèi)線打外線，其強度為- #-因此，總強度為兄=人+心=140+60=200這是損金制服務系統(tǒng)，按題日要求，系統(tǒng)損失的概率不能超過5%,即Pg0.05外線是整數(shù)，在滿足條件下，條數(shù)越小越好。由上述三條，寫出相應的LINGO程序如下：model:lamda=200;mu=60/3;rho=la

32、mda/mu;Plost=pel(rho,s);PlostK由式(4),式(5)和式(6),有0,nK- #- #- #-故Pn=P”Po,=其中(28)1Po=Kl+wn=l由已得到的單服務臺混合制排隊系統(tǒng)平穩(wěn)狀態(tài)卜隊長的分布，可知當QH1時，平均隊長厶為：4=工啊=PoPb7i=0/?=!P(K+1)嚴1-p1一嚴(29)- #- #- #-當。=1時,KKKK(30)厶=2”Po=E,7=tn=0/r=lI+L/r=lL(31)類似地可得到平均排隊長Lq為d=i-i)p“=厶一(i一幾)/r=l或Lq=K、中、0nssnKJ：是- - - #-其中Pn=OSvsnpn!嚴Po.snK-1

33、Po=S2n衛(wèi)（1一久）（Tnno工市+DA=1l“05.丿由平穩(wěn)分布pn=0丄2,，K,可得平均排隊長為nsi厶廠工（7）幾lt=SKt1-於曲-(1-Q)(K7+l)pj,O豐1Pop(K-S)(K-5+1)14=12s!(42)(43)(44)為求平均隊長，由Lq=工（一S）幾=工一S工Pnn=sh=jfr=j=工啊一士啊一/i一幾=4-工（一s）p-/r=0/?=0/?=0/?=0得到厶詁+S+壯心0/r=0n(45)由系統(tǒng)空間的有限性，必須考慮顧客的有效到達率&。對多服務臺系統(tǒng)，仍有入=2（1-Pk）再利用Little公式，得到W占,wq=ws-丄AeAe“平均被占用的服務臺數(shù)（也是

34、正在接受服務的顧客的平均數(shù)）為pTn-s(46)(47)y-lKE=Dp“+sp“=pon=Q/r=j/r=O-“一1)!仕w51n=c=PoPP_Krss(48)(48)- - #- #-=P(i-rPo)=PU-Pj(49)因此，又有厶=Lq+E=Lq+pQpK)例6某汽車加油站設(shè)有兩個加油機，汽車按Poisson流到達，平均每分鐘到達2輛：汽車加油時間服從負指數(shù)分布，平均加油時間為2分鐘。又知加油站上最多只能停放3輛等待加油的汽車，汽車到達時，若已滿員，則必須開到別的加油站去，試対該系統(tǒng)進行分析。解可將該系統(tǒng)看作一個M/M/2/5排隊系統(tǒng)，其中2=2,“=0.5,p=4,5=2,K=5f

35、1+4+W4z2O2!(1-4/2)系統(tǒng)空閑的概率=0.008顧客損失率Ps=45x0.0082!x2=0.512(48)(48)- #- #- #-（3）加油站內(nèi)在等待的平均汽車數(shù)-=駕;二爲；)1-(4/2)5-2+1-(1-4/2)(5-2+1)(4/2嚴=2.18(輛)加油站內(nèi)汽車的平均數(shù)為厶=d+p(l“5)=2.18+4(1-0.512)=4.13(輛)汽車在加油站內(nèi)平均逗留時間為IV=一匕一=一-一=4.23(分鐘)2(1-p5)2(1-0.512)汽車在加油站內(nèi)平均等待時間為iv=iv1=4.23-2=2.23(分鐘)被占用的加油機的平均數(shù)為5=4-=4.13-2.18=1.9

36、5(個)編寫LINGO程序如卜:model:sets:state/15/:p;endsetslamda=2;mu=05;rho=lamda/mu;s=2;k=5;lamda*pO=mu*p(1);(lamda+mu)*p(1)=lamda*p0+2*mu*p(2);forstatei)Ii#gt#1#and#i#lt#s:(lamda+i*mu)*p(i)=lamda*p(i-1)+i+1)*mu*p(i+1);- - -(56)- -for(state(i)Ii#ge#s#and#i#It#k:(lamda+s*mu)*p(i)=lamda*p(i-1)+s*mu*pi+1);lamda*p

37、(k-1)=s*mu*p(k);pO+sum(state:p)=l;P_lost=p(k);1amda_e=1amda*(1-P_lost);L_s=sum(state(i):i*p(i)；L_q=L_s-1amda_e/mu;W_s=L_s/1amda_e;W_q=W_s-l/mu;end在對上述多服務臺混合制排隊模型M/M/s/K的討論中，當s=K時，即為多服務臺損失制系統(tǒng)。對損失制系統(tǒng)，有(50)其中n(51)顧客的損失率為心)=幾=務仗務)(52)式(52)稱為Erlang損失公式，(S,)亦表示了到達系統(tǒng)后由J：系統(tǒng)空間已被占滿而不能進入系統(tǒng)的顧客的百分比。対損失制系統(tǒng)，平均被占用的

38、服務臺數(shù)(正在接受服務的顧客的平均數(shù))為答幾TOC o 1-5 h zn=0n=0=彳斗-斗怎斗IQ(1-B(S,p)(53)l”=on$!人”=川丿此外，還有平均隊長Ls=s=Q(1-B(s,p)(54)平均逗留時間W.=經(jīng)=”1-()=丄(55)&/I-B(s,p)“其中&,=兄(1一化)為有效到達率。在損失制系統(tǒng)中，還經(jīng)常用4=/(l-pj表示系統(tǒng)的絕對通過能力，即單位時間內(nèi)系統(tǒng)實際可完成的服務次數(shù)；用0=1-化表示系統(tǒng)的相對通過能力，即被服務的顧客數(shù)與請求服務的顧客數(shù)的比值。系統(tǒng)的服務臺利用率(或通道利用率)為s=S7其它排隊模型簡介7.1有限源排隊模型現(xiàn)在，來分析一卜顧客源為有限的排

39、隊問題。這類排隊問題的主耍特征是顧客總數(shù)是有限的，如果有加個顧客。每個顧客來到系統(tǒng)中接受服務后仍回到原來的總體，還有可能再來，這類排隊問題的典型例子是機器看管問題。如一個工人同時看管加臺機器，當機器發(fā)生故障時即停卜來等待維修，修好后再投入使用，且仍然可能再發(fā)生故障。類似的例子還有加個終端共用一臺打印機等，如圖2所示。腿客圾陡列O00C眼券臺-圖2有曲胡排隊系統(tǒng)關(guān)J：顧客的平均到達率，在無限源的情形中是按全體顧客來考慮的，而在有限源的情形廠必須按每一顧客來考慮。設(shè)每個顧客的到達率都是相同的，均為幾(這里久的含義是指單位時間內(nèi)該顧客來到系統(tǒng)請求服務的次數(shù))，且每一顧客在系統(tǒng)外的時間均服從參數(shù)為兄的

40、負指數(shù)分布。由在系統(tǒng)外的顧客的平均數(shù)為7-厶，故系統(tǒng)的有效到達率為&=A(m-Ls)下面討論平穩(wěn)狀態(tài)下隊長N的分布pn=PN=/?=(M2間的轉(zhuǎn)移率為血=A(m-n)fn=0丄2,，amn/A=1225/,“=S+1，7由式(4),式(5)和式(6),有(記p=)Cn=”)h=0n=0或L$=Lq七二=Lq+p(m-Ls)特別，對單服務臺(s=l)系統(tǒng)，有MPn=-PP。，=1、2,，7(加一n)廠A加h”0=pLh=o(m-n)md=dP/r=lLs=Lq+Q_Po)或(61)(62)(63)(61)(65)(66)(67)w、=2=巴丄，w=WK-人“(1-Po)入卩系統(tǒng)的相対通過能力0=

41、1,絕對通過能力A=AS=2(加-&)=“(1-Po)(68)(69)(70)例7設(shè)有一工人看管5臺機器，每臺機器正常運轉(zhuǎn)的時間服從負指數(shù)分布，平均為15分鐘。當發(fā)生故障后，每次修理時間服從負指數(shù)分布，平均為12分鐘，試求該系統(tǒng)的有關(guān)運行指標。解用有限源排隊模型處理本問題。已知A=,u=,p=0.8？=51512”于是,有(1)修理工人空閑的概率=豐(0.8)。+晉(0.8)+弓(0.8)2+害(0.8)瓷(0.8)4+罟(0.8)5(2)5臺機器都出故障的概率p5=|(O.S)0=0.287=0.0073- - #-(56)- #-（3）出故障機器的平均數(shù)厶=5-丄（10.0073）=3.7

42、6（臺）0.8（4）等待修理機器的平均數(shù)厶“=3.76（10.0073）=2.77（臺）（5）每臺機器發(fā)生一次故障的平均停工時間IV=15=46（分鐘）土（10.0073）(6)每臺機器平均待修時間=46-12=34（分鐘）（7）系統(tǒng)絕対通過能力（即工人的維修能力）4=+（10.0073）=0.083冶）即該工人每小時可修理機器的平均臺數(shù)為0.083x60=4.96臺。上述結(jié)果表面，機器停工時間過長，看管工人幾乎沒有空閑時間，應采取措施提高服務率或增加工人。LINGO計算程序如卜model:lamda=l/15;mu=l/12;rho=lamda/mu;s=l;m=5;load=m*rho;L

43、_s=pfs（load,s,m）;p_0=l-（m-L_s）*rho;lamda_e=lamda*（m-L_s）;p_5=exp（lgm（6）*0.8A5*p_0;L_q=L_s-（l-p_0）；w_s=L_s/lamda_e;w_q=L_q/1amda_e;end7.2服務率或到達率依賴狀態(tài)的排隊模型在前而的各類排隊模型的分析中，均假設(shè)顧客的到達率為常數(shù)2,服務臺的服務率也為常數(shù)“。而在實際的排隊問題中，到達率或服務率可能是隨系統(tǒng)的狀態(tài)而變化的。例如，當系統(tǒng)中顧客數(shù)已經(jīng)比較多時，后來的顧客可能不愿意再進入系統(tǒng)；服務員的服務率當顧客較多時也可能會提高。因此對單服務臺系統(tǒng)，實際的到達率和服務率（

44、它們均依賴于系統(tǒng)所處的狀態(tài)“）可假設(shè)為A=,n=（+1）“1,2,對多服務臺系統(tǒng)，實際到達率和服務率假設(shè)為ns-l77/uns77/uns其中九和“”分別為系統(tǒng)處J：狀態(tài)時的到達率和服務率。上述假設(shè)表明，到達率血同系統(tǒng)中已有顧客數(shù)呈反比關(guān)系：服務率“同系統(tǒng)狀態(tài)呈正比關(guān)系。由式（4）,對多服務臺系統(tǒng)有“丫1）,歸,2,snl（入仏）”1;7-_n=$,s+l,卜面看一個簡單的特例，考慮一個到達依賴狀態(tài)的單服務臺等待制系統(tǒng)M/M/1/s,其參數(shù)為7n=0,2,/7+1“=1,2,J：是由式（5）,式（6）,并設(shè)p=-b有Cn=(71)nPo=e-p平均隊長(72)(73)XXcL嚴“咕工哈P。*h

45、=o；j=o(74)平均排隊長ocLq=工（-OPn=厶_（1-”0）=P+Q_1n=l有效到達率（單位時間內(nèi)實際進入系統(tǒng)的顧客的平均數(shù)）心=厶幾=“（1一-）辭“+1平均逗留時間為VV=丄=匕&“（1-嚴）平均等待時間厶1W=-=W9&(75)(76)(77)7.3非生滅過程排隊模型- #- #-18- - - -18- #-，個排隊系統(tǒng)的特征是由輸入過程，服務機制和排隊規(guī)則決定的。本章前而所討論的排隊模型都是輸入過程為Poisson流，服務時間服從負指數(shù)分布的生滅過程排隊模型。這類排隊系統(tǒng)的一個主要特征是馬爾可夫性，而馬爾可夫性的一個主耍性質(zhì)是由系統(tǒng)當前的狀態(tài)可以推斷未來的狀態(tài)。但是，當輸

46、入過程不是Poisson流或服務時間不服從負指數(shù)分布時，僅知道系統(tǒng)內(nèi)當前的顧客數(shù)，對推斷系統(tǒng)未來的狀態(tài)是不充足的,因為正在接受服務的顧客，己經(jīng)被服務了多長時間，將影響其離開系統(tǒng)的時間。因此,必須引入新的方法來分析具有非負指數(shù)分布的排隊系統(tǒng)。7.3.1M/G/1排隊模型M/G/1系統(tǒng)是指顧客的到達為Poisson流，單個服務臺，服務時間為一般分布的排隊系統(tǒng)。現(xiàn)假設(shè)顧客的平均到達率為幾，服務時間的均值為丄，方差為則可證明：當p=系統(tǒng)可以達到平穩(wěn)狀態(tài)，而給出平穩(wěn)分布的表示是比較困難的。已有的幾個結(jié)呆為：Po=lP（79）Lq=A2a2+p22(1P)(80)(81)LW=（82）q2Ws=w+-（8

47、3）由式（80）可看出，S厶,等僅依賴和服務時間的方差b，而與分布的類型沒有關(guān)系，這是排隊論中一個非常重要且令人驚奇的結(jié)果，式（80）通常被稱為Pollaczek-Khintchine（P-K）公式。從式（80）還不難發(fā)現(xiàn)，當服務率“給定后，當方差減少時，平均隊長和等待時間等都將減少。因此可通過改變服務時間的方差來縮短平均隊長，當且僅當r2=0,即服務時間為定長時，平均隊長（包括等待時間）可減少到最少水平，這一點是符合直觀的，因為服務時間越有規(guī)律，等候的時間也就越短。例8有一汽車沖洗臺，汽車按Poisson流到達，平均每小時到達18輛，沖洗時間V根據(jù)過去的經(jīng)驗表明，有（V）=0.05/?/輛，

48、Vai（y）=0.01（h）,求有關(guān)運行指標，并對系統(tǒng)進行評價。解本例中，2=18,p=Af（V）=18x0.05=0.9,o(88)伙-1)!故其均值和方差分別為(89)(89)18- #-將p=(JE(E)=丄，Vai(J=-L“k茁=厶代入式(80)式(83),得L_心+1)_伙_1)F厲一2kQ_p)_p2kQ-p)p伙1)0厶=+p=“-p2R(1Q)叱=1伙一1)。(90)“(1-p)2R“(1-p)%=P伙一1)。(91)(92)“(1-p)2kpQ_p)例10設(shè)一電話間的顧客按Poisson流到達，平均每小時到達6人，平均通話時間為8分鐘，方差為16分鐘。直觀上估計通話時間服從

49、愛爾朗分布，管理人員想知道平均排隊長度和顧客平均等待時間是多少？解設(shè)V為通話時間，服從R階Erlang分布，由k一E(V)F_V_Var(V)_16Q可知該系統(tǒng)為M/E./l/oo系統(tǒng)，其中p=6x=0.8o由式(89),有60(0.8/(4+1)=2(人)q2x4(1-0.8)L2W=-=033(h)qz68排隊系統(tǒng)的優(yōu)化排隊系統(tǒng)中的優(yōu)化模型，一般可分為系統(tǒng)設(shè)計的優(yōu)化和系統(tǒng)控制的優(yōu)化。前者為靜態(tài)優(yōu)化，即在服務系統(tǒng)設(shè)置以前根據(jù)一定的質(zhì)吊指標，找出參數(shù)的最優(yōu)值，從而使系統(tǒng)最為經(jīng)濟。后者為動態(tài)優(yōu)化，即対已有的排隊系統(tǒng)尋求使其某一目標函數(shù)達到最優(yōu)的運營機制。由r対后一類問題的闡述需耍較多的數(shù)學知識，

50、所以本節(jié)著重介紹靜態(tài)最優(yōu)問題。在優(yōu)化問題的處理方法上，一般根據(jù)變鼠的類型是離散的還是連續(xù)的，相應地采用邊際分析方法或經(jīng)典的微分法，対較為復雜的優(yōu)化問題需要用非線性規(guī)劃或動態(tài)規(guī)劃等方法。8.1M!M/I模型中的最優(yōu)服務率“先考慮M/M/l/oo模型，取目標函數(shù)z為單位時間服務成本與顧客在系統(tǒng)中逗留費用之和的期望值，即Z=cji+cwLs其中C$為服務一個顧客時單位時間內(nèi)的服務費用，5為每個顧客在系統(tǒng)中逗留單位時(93)(93)- - #-18- #-間的費用，則由式（9）,有dz_?1_n=CsCwAp=0解出最優(yōu)服務率為F+護卜面考慮M/M/1/K模型，從使服務機構(gòu)利潤最人化來考慮。由J：在平

51、穩(wěn)狀態(tài)下,單位時間內(nèi)到達并進入系統(tǒng)的平均顧客數(shù)為人=2（1-/“,），它也等單位時間內(nèi)實際服務完的平均顧客數(shù)。設(shè)每服務一個顧客服務機構(gòu)的收入為G尤，J：是單位時間內(nèi)收入的期望值是2（1-以）G元，故利潤z為l-nKK+lZ=2（1_PK）G-cji=AG-一備_c$“P=解負嚴-側(cè)K+l(93)(93)- #- #-18- #-令傘=0,得pgK_(K+Y)p+p（1嚴）2(94)(93)(93)- #- #-18- #-(93)(93)- #- #-18- #-當給定K和尋后，即可由（94）式得到最優(yōu)利潤的例11設(shè)某工人照管4臺自動機床，機床運轉(zhuǎn)時間（或各臺機床損壞的相繼時間）平均為負指數(shù)分

52、布，假定平均每周有一臺機床損壞需要維修，機床運轉(zhuǎn)單位時間內(nèi)平均收入100元,而每增加1單位“的維修費用為75元。求使總利益達到最大的/Z。解該系統(tǒng)為M/M/1/K/K系統(tǒng)，其中K=4,2=1,G=100,Cs=75設(shè)厶是隊長，則正常運裝的機器為K-4部，因此目標函數(shù)為/=100（K-厶）-75/題意就是在上述條件卜，求目標函數(shù)/的最人值。編寫LINGO程序如卜：model:s=l;k=4;lamda=l;L_s=pfs（k*lamda/muzszk）;max=100*（k-L_s）-75*mu;end求得/=1.799,最優(yōu)目標值廠=31.49- #- -18- #-例12假定有一混合制排隊系

53、統(tǒng)M/M/1/K,其中K=3，顧客的到達率為每小時3.6人，其到達間隔服從Poissonid程，系統(tǒng)服務一個顧客收費2元。又設(shè)系統(tǒng)的服務強度(“=*，T為服務時間)服從負指數(shù)分布，其服務成本為每小時0.5“元。求系統(tǒng)為每個顧客的最佳服務時間。解系統(tǒng)的損失率為“K，則系統(tǒng)每小時服務的人數(shù)為2(1-Pk)，每小時運行成本為0.5/,因此目標函數(shù)為f=22(1-pK)-0.5/題意就是在上述條件卜，求目標函數(shù)/的最人值。編寫LINGO程序如卜：model:sets:state/1.3/:p;endsetslamda=36;k=3;lamda*p0=p1)/t;(lamda+l/t)*p(1)=lam

54、da*p0+p(2)/t;forstatei)Ii#gt#1#and#i#It#k:(lamda+l/t)*p(i)=lamda*p(i-1)+p(i+1)/t);lamda*p(k-1)=p(k)/t;p0+sumstate:p)=1;max=2*lamda*(l-p(k)一05/t;end求得系統(tǒng)為每位顧客最佳服務時間是0.2238h,系統(tǒng)每小時贏利370元。8.2M/M/S模型中的最優(yōu)的服務臺數(shù)h這里僅討論M/M/s/s系統(tǒng)，已知在平穩(wěn)狀態(tài)卜單位時間內(nèi)總費用(服務費用與等待費用)之和的平均值為z=css+cwL(95)其中S為服務臺數(shù)，C；是每個服務臺單位時間內(nèi)的費用，厶是平均隊長。由T

55、c；,5是給定的，故唯一可變的是服務臺數(shù)S,所以可將z看成是S的函數(shù)，記為z=z(s),并求使Z(s)達到最小的因為S只取整數(shù)，z(s)不是連續(xù)函數(shù)，故不能用經(jīng)典的微分法，卜面采用邊際分析方法。根據(jù)應為最小的特點，有（96）妒）（“-1）Z（5*）Z（5*+1）將式（95）代入式（96）,得+久厶（門C；_1）+-1）C.F+久以門C；（b+1）+C.tZ（5*+1）化簡后得到(97)(97)- - #-18- #-L(門-L(j*+1)-1)-L(s)5依次求當$=1、2,3,時厶的值，并計算相鄰兩個厶值的差。因2是己知數(shù)，根據(jù)其落在哪個與$有關(guān)的不等式中，即可定出最優(yōu)的S*。例13某檢驗中

56、心為各工廠服務,耍求進行檢驗的工廠（顧客）的到來服從Poisson流，平均到達率為2=48（次/d）；每天來檢驗由J：停工等原因損失6川服務（檢驗）時間服從負指數(shù)分布，平均服務率為”=25（次/d）；每設(shè)置一個檢驗員的服務成本為4元/d,其它條件均適合M/M/s/s系統(tǒng)。問應設(shè)幾個檢驗員可使總費用的平均值最少？解已知c；=4,cM.=6,2=48,“=25,-=1.92，設(shè)檢驗員數(shù)為s,由式（20）和式（25）Po=f(1.92)”/=0n(5-1)1(5-1.92)(97)(97)- #- #-18- #-(97)(97)- #- #-18- #-L=-+p=一+1.92（sl）!（s192

57、廣c4將s=1,2,345依次代入得到表2。由1=一=0.67落在區(qū)間（0.582,21.845）之間,56故S*=3,即當設(shè)3個檢驗員時可使總費用z最小，最小值為Z（Z）=z（3）=27.87（元）表2檢驗員數(shù)S平均顧客數(shù)厶（$）L(s)一L(s+1)L(s-1)-L(s)總費用Z（S）1OCOC224.4921.845oo154.9432.6450.5822184527.8742.0630.111058228.3851.95231.71求解的LINGO程序如卜：model:lamda=48;mu=25;rho=lamda/mu;P_wait=peb(rho,s);L_q=P_wait*rh

58、o/(s-rho);L_s=L_q+rho;min=4*s+6*L_s;gin(s);bnd(2zsz5);end9產(chǎn)生給定分布的隨機數(shù)的方法Matlab可以產(chǎn)生常用分布的隨機數(shù)。卜而我們介紹按照給定的概率分布產(chǎn)生隨機- - -18- #-數(shù)的一般方法，這些方法都以(0,1)分布的隨機變最為基礎(chǔ)。反變換法定理設(shè)X是一個貝有連續(xù)分布函數(shù)尸(x)的隨機變量，則F(X)在0,1上服從均勻分布。設(shè)概率分布函數(shù)F(x)是嚴格單調(diào)增的，F(xiàn)的反函數(shù)記作FT。先產(chǎn)生(0,1),再取X=FU)即為所求，稱為反變換法。指數(shù)分布Exp(/l)能夠方便地用反變換法產(chǎn)生。由Exp)的分布函數(shù)F(x)=l-e_/U,可得

59、X=Fu)=-hKU)思考有的書上用X=代替上式，對嗎，為什么？/I卷積法如果隨機變量x是“個獨立、同分布的另一隨機變量丫之和,ifijr又容易產(chǎn)生時,先產(chǎn)生個獨立的再令x=y1+.+yn即可。因為x的分布函數(shù)是K，厶，,打分布函數(shù)的卷積,故稱為卷積法。二項分布可以用卷積法產(chǎn)生。因為XBgp)是”個獨立的YBern(p)之和，而YBegp)很容易由U(7(0,1)按以卜方法得到：若Up,令y=1；否則令r=0o取舍法若隨機變鼠X在有限區(qū)間(a,b)內(nèi)變化，但概率密度/(x)具有任意形式(茯至沒有解析表達式)，無法用前面的方法產(chǎn)生時，可用取舍法。一種比較簡單的取舍法的步驟是：1產(chǎn)生YU(a,b)

60、和/(0小2iElC=max/(x),若U則取X=/；否則，舍去，返回1。ax6概率0.230.300.300.10.050.020.00解這是單服務臺的排隊系統(tǒng)，可驗證到達車數(shù)不服從泊松分布，服務時間也不服從指數(shù)分布（這是定長服務時間）。隨機模擬法首先要求事件能按歷史的概率分布規(guī)律出現(xiàn)。模擬時產(chǎn)生的隨機數(shù)與事件的對應關(guān)系如表4o表4到達車數(shù)的概率及其對應的隨機數(shù)到達車數(shù)概率累積概率對應的隨機數(shù)00.230.230X0.2310.300.530.23x0.5320.300.830.53X0.8330.10.930.83X0.9310.050.980.93X0.9850.021.000.98X1