排隊論(Lingo方法)

1、編輯ppt1數(shù)學(xué)建模講座排排 隊隊 論論 模模 型型編輯ppt2排隊系統(tǒng)的描述排隊系統(tǒng)的描述顧客總體顧客總體隊伍隊伍服務(wù)臺服務(wù)臺服務(wù)系統(tǒng)輸出輸出輸入輸入編輯ppt3排隊服務(wù)系統(tǒng)的基本概念排隊服務(wù)系統(tǒng)的基本概念輸入過程：描述顧客來源是按怎樣的規(guī)律抵達(dá)排隊輸入過程：描述顧客來源是按怎樣的規(guī)律抵達(dá)排隊系統(tǒng)。系統(tǒng)。1.顧客源總體顧客源總體:有限還是無限有限還是無限2.到達(dá)類型：單個到達(dá)還是成批到達(dá)到達(dá)類型：單個到達(dá)還是成批到達(dá) 3.相繼顧客到達(dá)的時間間隔：相互獨立、同分布的相繼顧客到達(dá)的時間間隔：相互獨立、同分布的;等時間間隔的等時間間隔的;服從服從Poisson分布的；分布的； k階階Erlang分

2、分布布泊松分布泊松分布適合于描述單位時間內(nèi)隨機(jī)事件發(fā)生的次數(shù)。如某一服務(wù)設(shè)施在一適合于描述單位時間內(nèi)隨機(jī)事件發(fā)生的次數(shù)。如某一服務(wù)設(shè)施在一定時間內(nèi)到達(dá)的人數(shù)，電話交換機(jī)接到呼叫的次數(shù)，汽車站臺的候客人數(shù)，定時間內(nèi)到達(dá)的人數(shù)，電話交換機(jī)接到呼叫的次數(shù)，汽車站臺的候客人數(shù)，機(jī)器出現(xiàn)的故障數(shù)，自然災(zāi)害發(fā)生的次數(shù)等等。機(jī)器出現(xiàn)的故障數(shù)，自然災(zāi)害發(fā)生的次數(shù)等等。編輯ppt4排隊服務(wù)系統(tǒng)的基本概念排隊服務(wù)系統(tǒng)的基本概念排隊規(guī)則：指服務(wù)系統(tǒng)是否允許排隊，顧客是否愿意排隊排隊規(guī)則：指服務(wù)系統(tǒng)是否允許排隊，顧客是否愿意排隊1.損失制排隊系統(tǒng)：顧客到達(dá)若所有服務(wù)臺被占，服務(wù)損失制排隊系統(tǒng)：顧客到達(dá)若所有服務(wù)臺被占

3、，服務(wù)機(jī)構(gòu)又不允許顧客等待，此時該顧客就自動離去。機(jī)構(gòu)又不允許顧客等待，此時該顧客就自動離去。2.等待制排隊系統(tǒng)：顧客到達(dá)時若服務(wù)臺均被占，他們等待制排隊系統(tǒng)：顧客到達(dá)時若服務(wù)臺均被占，他們就排隊等待。服務(wù)順序有：先到先服務(wù)、后到先服務(wù)、就排隊等待。服務(wù)順序有：先到先服務(wù)、后到先服務(wù)、隨機(jī)服務(wù)、有優(yōu)先權(quán)的服務(wù)隨機(jī)服務(wù)、有優(yōu)先權(quán)的服務(wù)3.混合制排隊系統(tǒng)：損失制與等待制的混合。隊長（容混合制排隊系統(tǒng)：損失制與等待制的混合。隊長（容量）有限的混合；等待時間有限的混合；逗留時間有限量）有限的混合；等待時間有限的混合；逗留時間有限的混合的混合編輯ppt5排隊服務(wù)系統(tǒng)的基本概念排隊服務(wù)系統(tǒng)的基本概念服務(wù)機(jī)

4、構(gòu)：服務(wù)機(jī)構(gòu)：1.服務(wù)臺的數(shù)目服務(wù)臺的數(shù)目2.顧客所需的服務(wù)時間服從怎樣的概率分布顧客所需的服務(wù)時間服從怎樣的概率分布(常見顧客的服務(wù)時間分布有常見顧客的服務(wù)時間分布有:定長分布、負(fù)定長分布、負(fù)指數(shù)分布、超指數(shù)分布、指數(shù)分布、超指數(shù)分布、k階階Erlang分布、分布、幾何分布、一般分布幾何分布、一般分布)編輯ppt6排隊論模型的符號表示排隊論模型的符號表示通常由通常由3-5個英文字母組成，個英文字母組成，其形式為其形式為 A/B/C/n，其中其中 A表示輸入過程，表示輸入過程， B表示服務(wù)時間，表示服務(wù)時間， C表示服務(wù)臺數(shù)目，表示服務(wù)臺數(shù)目， n表示系統(tǒng)空間數(shù)表示系統(tǒng)空間數(shù)排隊模型的表示：排

5、隊模型的表示：X/Y/Z/A/B/CX顧客相繼到達(dá)的間隔時顧客相繼到達(dá)的間隔時間的分布；間的分布；Y服務(wù)時間的分布；服務(wù)時間的分布；Z服務(wù)臺個數(shù)；服務(wù)臺個數(shù)；A系統(tǒng)容量限制（默認(rèn)為系統(tǒng)容量限制（默認(rèn)為）；）；B顧客源數(shù)目（默認(rèn)為顧客源數(shù)目（默認(rèn)為）；）；C服務(wù)規(guī)則服務(wù)規(guī)則 （默認(rèn)為先到（默認(rèn)為先到先服務(wù)先服務(wù)FCFS)。 M負(fù)指數(shù)分布、負(fù)指數(shù)分布、D確定確定型、型、Ek k階愛爾朗分布。階愛爾朗分布。編輯ppt7描述排隊論系統(tǒng)的主要數(shù)量指標(biāo)描述排隊論系統(tǒng)的主要數(shù)量指標(biāo)1.1.隊長隊長(L(Ls s) ) ：指在系統(tǒng)中顧客的平均數(shù)：指在系統(tǒng)中顧客的平均數(shù) 等待隊長等待隊長(L(Lq q) )：指

6、系統(tǒng)中等待的顧客的平均數(shù)：指系統(tǒng)中等待的顧客的平均數(shù)2.2.顧客的平均等待時間顧客的平均等待時間(W(Wq q) )：指顧客進(jìn)入系統(tǒng)的時刻起到開始接：指顧客進(jìn)入系統(tǒng)的時刻起到開始接 受服務(wù)止的平均時間受服務(wù)止的平均時間與平均逗留時間與平均逗留時間(W(Ws s) )：指顧客在系統(tǒng)中平均等待時間與平均服務(wù)：指顧客在系統(tǒng)中平均等待時間與平均服務(wù)時間之和時間之和3.3.系統(tǒng)的忙期與閑期系統(tǒng)的忙期與閑期服務(wù)機(jī)構(gòu)工作強(qiáng)度服務(wù)機(jī)構(gòu)工作強(qiáng)度= =由于服務(wù)顧客的時間由于服務(wù)顧客的時間/ /服務(wù)設(shè)施總的服務(wù)時間服務(wù)設(shè)施總的服務(wù)時間 = =1-1-服務(wù)設(shè)施總的空閑時間服務(wù)設(shè)施總的空閑時間/ /服務(wù)設(shè)施總的服務(wù)時間

7、服務(wù)設(shè)施總的服務(wù)時間編輯ppt8與排隊論模型有關(guān)的與排隊論模型有關(guān)的LINGO函數(shù)函數(shù)1.peb(load,S)該函數(shù)返回值是當(dāng)?shù)竭_(dá)負(fù)荷為該函數(shù)返回值是當(dāng)?shù)竭_(dá)負(fù)荷為load，系統(tǒng)中有，系統(tǒng)中有S個服務(wù)臺且允個服務(wù)臺且允許排隊時系統(tǒng)繁忙的概率，也就是顧客等待的概率許排隊時系統(tǒng)繁忙的概率，也就是顧客等待的概率2.pel(load,S)該函數(shù)返回值是當(dāng)?shù)竭_(dá)負(fù)荷為該函數(shù)返回值是當(dāng)?shù)竭_(dá)負(fù)荷為load，系統(tǒng)中有，系統(tǒng)中有S個服務(wù)臺且不個服務(wù)臺且不允許排隊時系統(tǒng)損失的概率，也就是顧客得不到服務(wù)離開的概允許排隊時系統(tǒng)損失的概率，也就是顧客得不到服務(wù)離開的概率率3.pfs(load,S,K)該函數(shù)的返回值是當(dāng)?shù)?/p>

8、達(dá)負(fù)荷為該函數(shù)的返回值是當(dāng)?shù)竭_(dá)負(fù)荷為load ，顧客數(shù)為，顧客數(shù)為K,平行服務(wù)臺平行服務(wù)臺數(shù)量為數(shù)量為S時，有限源的時，有限源的Poisson服務(wù)系統(tǒng)等待或返修顧客數(shù)的期服務(wù)系統(tǒng)等待或返修顧客數(shù)的期望值望值編輯ppt9等待制排隊模型等待制排隊模型等待制排隊模型中最常見的模型是：等待制排隊模型中最常見的模型是： M/M/S/,即顧客到達(dá)系統(tǒng)的相繼到達(dá)時間間隔獨立，且即顧客到達(dá)系統(tǒng)的相繼到達(dá)時間間隔獨立，且服從參數(shù)為服從參數(shù)為的負(fù)指數(shù)分布（即輸入過程為過的負(fù)指數(shù)分布（即輸入過程為過程），服務(wù)臺的服務(wù)時間也獨立同分布，且服程），服務(wù)臺的服務(wù)時間也獨立同分布，且服從參數(shù)為從參數(shù)為的負(fù)指數(shù)分布，而且系統(tǒng)

9、空間無限，的負(fù)指數(shù)分布，而且系統(tǒng)空間無限，允許永遠(yuǎn)排隊允許永遠(yuǎn)排隊編輯ppt10等待制排隊模型等待制排隊模型的基本參數(shù)的基本參數(shù)1 1. .顧客等待的概率顧客等待的概率:P:Pwaitwait=peb(load,S),=peb(load,S),其中其中S S是服務(wù)臺或服務(wù)員的個數(shù)，是服務(wù)臺或服務(wù)員的個數(shù)，load= load= / / =RT, =RT,其中其中R= R= ,T= 1/,T= 1/，R R是顧客的平均到達(dá)率，是顧客的平均到達(dá)率，T T是平均是平均服務(wù)時間服務(wù)時間2.2.顧客的平均等待時間顧客的平均等待時間：W Wq q= P= PwaitwaitT/(S-load),T/(S-

10、load),其中其中T/(S-load)T/(S-load)可以看成一個合理的長度間隔，可以看成一個合理的長度間隔，3.3.顧客的平均逗留時間、隊長和等待隊長顧客的平均逗留時間、隊長和等待隊長（littlelittle公式）公式） W Ws s= W= Wq q+1/ +1/ =W=Wq q+T L+T Ls s= = W Ws s=RW=RWs s Lq= Wq=R Wq編輯ppt11等待制排隊模型實例等待制排隊模型實例1.S=1 (M/M/1/)例例1：某維修中心在周末現(xiàn)只安排一名員工為顧客提供服務(wù)，：某維修中心在周末現(xiàn)只安排一名員工為顧客提供服務(wù)，新來維修的新來維修的 顧客到達(dá)后，若已有

11、顧客正在接受服務(wù)，則需要顧客到達(dá)后，若已有顧客正在接受服務(wù)，則需要排隊等待，假設(shè)來維修的顧客到達(dá)過程為排隊等待，假設(shè)來維修的顧客到達(dá)過程為Poisson流，平均每流，平均每小時小時4人，維修時間服從負(fù)指數(shù)分布，平均需要人，維修時間服從負(fù)指數(shù)分布，平均需要6min,試求該試求該系統(tǒng)的主要數(shù)量指標(biāo)。系統(tǒng)的主要數(shù)量指標(biāo)。2.S=3 (M/M/S/)例例2：設(shè)打印室有：設(shè)打印室有3名打字員，平均每個文件的打印時間為名打字員，平均每個文件的打印時間為10min,而文件到達(dá)率為每小時而文件到達(dá)率為每小時15件，試求該打印室的主要數(shù)件，試求該打印室的主要數(shù)量指標(biāo)。量指標(biāo)。編輯ppt12等待制排隊模型實例等待

12、制排隊模型實例例例1：Model:S=1;R=4;T=6/60;load=R*T;Pwait=peb(load,S);W_q=Pwait*T/(S-load);L_q=R*W_q;W_s=W_q+T;L_s=W_s*R;End例例2：Model:S=3;R=15;T=10/60;load=R*T;Pwait=peb(load,S);W_q=Pwait*T/(S-load);L_q=R*W_q;W_s=W_q+T;L_s=W_s*R;END編輯ppt13損失制排隊模型損失制排隊模型損失制排隊模型通常記為損失制排隊模型通常記為 M/M/S/S,當(dāng)當(dāng)S個服務(wù)器被占用后，顧客自動離個服務(wù)器被占用后，顧

13、客自動離去去編輯ppt14損失制排隊模型的基本參數(shù)損失制排隊模型的基本參數(shù)1.系統(tǒng)損失的概率：系統(tǒng)損失的概率：Plost=pel(load,S)2.單位時間內(nèi)平均進(jìn)入系統(tǒng)的顧客數(shù)：單位時間內(nèi)平均進(jìn)入系統(tǒng)的顧客數(shù)： e=Re= e=Re= (1-Plost)=R(1-Plost)3.系統(tǒng)的相對通過能力系統(tǒng)的相對通過能力(Q)與絕對通過能力與絕對通過能力(A) Q=1-Plost, A= eQ= (1-Plost)2 =ReQ= R(1-Plost)2 4.系統(tǒng)在單位時間內(nèi)占用服務(wù)臺的均值系統(tǒng)在單位時間內(nèi)占用服務(wù)臺的均值:Ls= e/=ReT 注意：在損失制系統(tǒng)中，注意：在損失制系統(tǒng)中，Lq=0,

14、即等待隊長為即等待隊長為05.系統(tǒng)服務(wù)臺的效率：系統(tǒng)服務(wù)臺的效率：=Ls/S6.顧客在系統(tǒng)內(nèi)平均逗留時間顧客在系統(tǒng)內(nèi)平均逗留時間:Ws=1/ =T注意：在損失制系統(tǒng)中，注意：在損失制系統(tǒng)中，Wq=0,即等待時間為即等待時間為0編輯ppt15損失制排隊模型實例損失制排隊模型實例S=1(M/M/1/1)例例1：設(shè)某條電：設(shè)某條電話線，平均每話線，平均每分鐘有分鐘有0.6次呼次呼喚，若每次通喚，若每次通話時間平均為話時間平均為1.25min,求系求系統(tǒng)相應(yīng)的參數(shù)統(tǒng)相應(yīng)的參數(shù)指標(biāo)。指標(biāo)。model:S=1;R=0.6;T=1.25;load=R*T;Plost=pel(load,S);Q=1-Plos

15、t;R_e=Q*R;A=Q*R_e;L_s=R_e*T,eta=L_s/S;endEta-編輯ppt16損失制排隊模型實例損失制排隊模型實例S1(M/M/S/S)例例2：某單位電話交換臺有一臺：某單位電話交換臺有一臺200門內(nèi)線的總門內(nèi)線的總機(jī)，已知在上班機(jī)，已知在上班8小時內(nèi)，有小時內(nèi)，有20%的內(nèi)線分機(jī)的內(nèi)線分機(jī)平均每平均每40min要一次外線電話，要一次外線電話，80%的分機(jī)的分機(jī)平均間隔平均間隔120min要一次外線。又知外線打入要一次外線。又知外線打入內(nèi)線的電話平均每分鐘內(nèi)線的電話平均每分鐘1次。假設(shè)與外線通話次。假設(shè)與外線通話的時間為平均的時間為平均3min，并且上述時間均服從負(fù)，

16、并且上述時間均服從負(fù)指數(shù)分布，如果要求電話的通話率為指數(shù)分布，如果要求電話的通話率為95%，問該交換臺應(yīng)設(shè)置多少條外線？問該交換臺應(yīng)設(shè)置多少條外線？編輯ppt17損失制排隊模型實例損失制排隊模型實例例例2：分析：分析：1)電話交換臺的服務(wù)分成兩類，第一類內(nèi)電話交換臺的服務(wù)分成兩類，第一類內(nèi)線打外線，其強(qiáng)度為線打外線，其強(qiáng)度為 1=（0.260/40+0.860/120）200=140第二類是外線打內(nèi)線，其強(qiáng)度為第二類是外線打內(nèi)線，其強(qiáng)度為 2 =160=60因此總的強(qiáng)度為因此總的強(qiáng)度為 = 1+ 2=140+60=2002)按題目要求，系統(tǒng)損失的概率不能超過按題目要求，系統(tǒng)損失的概率不能超過5

17、%，即，即Plost0.053）外線是整數(shù)，在滿足條件下，條數(shù)越）外線是整數(shù)，在滿足條件下，條數(shù)越少越好少越好Model:R=200;T=3/60;load=R*T;Plost=pel(load,S);Plost=0.05;Q=1-Plost;R_e=Q*R;A=Q*R_e;L_s=R_e*T;eta=L_s/S;Min=S;gin(S);end編輯ppt18混合制排隊模型混合制排隊模型混合制排隊模型通常記為：混合制排隊模型通常記為：M/M/S/K,即有即有S個服個服務(wù)臺或服務(wù)員，系統(tǒng)空間容量為務(wù)臺或服務(wù)員，系統(tǒng)空間容量為K，當(dāng)，當(dāng)K個位置已個位置已被顧客占用時，新到的顧客自動離去，當(dāng)系統(tǒng)中被

18、顧客占用時，新到的顧客自動離去，當(dāng)系統(tǒng)中有空位置時，新到的顧客進(jìn)入系統(tǒng)排隊等待。有空位置時，新到的顧客進(jìn)入系統(tǒng)排隊等待。編輯ppt19閉合式排隊模型閉合式排隊模型設(shè)系統(tǒng)內(nèi)有設(shè)系統(tǒng)內(nèi)有M個服務(wù)臺，顧客到達(dá)系統(tǒng)的間隔時間個服務(wù)臺，顧客到達(dá)系統(tǒng)的間隔時間和服務(wù)臺的服務(wù)時間均為負(fù)指數(shù)分布，而系統(tǒng)的容和服務(wù)臺的服務(wù)時間均為負(fù)指數(shù)分布，而系統(tǒng)的容量和潛在的顧客數(shù)都為量和潛在的顧客數(shù)都為K，顧客到達(dá)率為，顧客到達(dá)率為 ，服務(wù)，服務(wù)臺的平均服務(wù)率為臺的平均服務(wù)率為 ，這樣的系統(tǒng)稱為閉合式排隊，這樣的系統(tǒng)稱為閉合式排隊模型，記為：模型，記為：M/M/S/K/K編輯ppt20閉合式排隊模型的基本參數(shù)閉合式排隊模型

19、的基本參數(shù)1.平均隊長：平均隊長：Ls=pfs(load,S,K),load=K / =KRT即即: 系統(tǒng)的負(fù)荷系統(tǒng)的負(fù)荷=系統(tǒng)的顧客數(shù)系統(tǒng)的顧客數(shù)顧客到達(dá)率顧客到達(dá)率顧客的服務(wù)時間顧客的服務(wù)時間2.單位時間平均進(jìn)入系統(tǒng)的顧客數(shù)單位時間平均進(jìn)入系統(tǒng)的顧客數(shù): e= （KLs）=R(KLs)=Re3.顧客處于正常情況的概率顧客處于正常情況的概率:P=(KLs)/K4.平均逗留時間、平均等待隊長和平均排隊等待時間平均逗留時間、平均等待隊長和平均排隊等待時間Ws=Ls/ e=Ls/Re Lq=Ls e/ =Ls-ReTWq=Ws1/ =WsT5.每個服務(wù)臺的工作強(qiáng)度每個服務(wù)臺的工作強(qiáng)度:Pwork=

20、 e/(S)編輯ppt21排隊系統(tǒng)的最優(yōu)化模型排隊系統(tǒng)的最優(yōu)化模型1.系統(tǒng)服務(wù)時間的確定系統(tǒng)服務(wù)時間的確定例：某工人照管例：某工人照管4臺自動臺自動機(jī)床，機(jī)床運轉(zhuǎn)時間平均機(jī)床，機(jī)床運轉(zhuǎn)時間平均為負(fù)指數(shù)分布，假定平均為負(fù)指數(shù)分布，假定平均每周有一臺機(jī)床損壞需要每周有一臺機(jī)床損壞需要維修，機(jī)床運轉(zhuǎn)單位時間維修，機(jī)床運轉(zhuǎn)單位時間內(nèi)平均收入內(nèi)平均收入100元，而每元，而每增加一單位增加一單位的維修費用的維修費用為為75元，求使總利益達(dá)到元，求使總利益達(dá)到最大的最大的*分析分析：這是一個閉合式排隊：這是一個閉合式排隊系統(tǒng)系統(tǒng)M/M/1/K/K,且且K=4，設(shè)，設(shè)Ls是隊長，則正常運轉(zhuǎn)的機(jī)是隊長，則正常運轉(zhuǎn)的機(jī)器為器為KLs部，因此目標(biāo)函數(shù)部，因此目標(biāo)函數(shù)為：為：f=100(KLs) 75 Model:S=1;K=4;R=1;L_s=pfs(K*R/mu,S,K);Max=100*(K-L_s)-75*mu;end編輯ppt22排隊系統(tǒng)的最優(yōu)化模型排隊系統(tǒng)的最優(yōu)化模型2.系統(tǒng)服務(wù)臺的確定系統(tǒng)服務(wù)臺的確定例：一個大型露天礦山，例：一個大型露天礦山，正考慮修建礦石卸位的個正考慮修建礦石卸位的個數(shù)，估計運礦石的車將按數(shù)，估計運礦石的車將按Poisson流到達(dá)，平均每流到達(dá)，平均每小時小時15輛，卸礦石時間服輛，卸礦石時間服從負(fù)指數(shù)分布，平均從負(fù)指數(shù)分