排隊系統(tǒng)的優(yōu)化

§6排隊系統(tǒng)的優(yōu)化一、排隊系統(tǒng)的優(yōu)化問題有兩類最優(yōu)設(shè)計=靜態(tài)問題：系統(tǒng)設(shè)計的最優(yōu)化;（運行前）最優(yōu)控制=動態(tài)問題：系統(tǒng)控制的最優(yōu)化;（運行中）只討論靜態(tài)問題；一般,顧客滿意，服務(wù)成本高;服務(wù)簡單，顧客等待多.最優(yōu)化的目標之一是兼顧兩者，使之合理.方法：數(shù)學中的極值原理，或經(jīng)濟中的邊際法.

二、MW7模型中最優(yōu)服務(wù)率p1.M/M/V^模型優(yōu)化設(shè)。為單位時間服務(wù)成本,。為在系統(tǒng)中逗留費用,TOC\o"1-5"\h\zS W則目標函數(shù)取為z=cH+。LS W將乙=入/(._>)代入，得z=c|Ll+CX/(|Ll-X),sw足 dz X々 —=c-c =0,d|LlsW(|LX—A)2得服務(wù)率應(yīng)訂在|L1*=X+J%人(口>人).

2.M/M/1/K模型優(yōu)化顧客被拒概率為？，接受概率1-〃，K K有效進入概率人=Mi—p），即有效到達率.e K設(shè)每服務(wù)一個顧客服務(wù)機構(gòu)獲G元，則單位時間收入期望值為k（l-p）GK利潤z=人（1一p）G—cpt= ~ -cptK s 1—pK+1$TOC\o"1-5"\h\z\o"CurrentDocument"c -Xk=AptG _cp\o"CurrentDocument"|tXK+1—入K+1 s

1-P1-pK+1(注p°=n=1=v1 ,Pk=PKP°)(注p°=n=1、K+1令dz/叩=0,得K—(K+1)p+pk+1_c_PK+' (1—PK+1)2 =G由此確定出P,進而確定出使服務(wù)系統(tǒng)最優(yōu)的H*.一般用數(shù)值計算方法求解，或圖解法.

設(shè)人,G,K,%為已知.由具體的G/c,找出對應(yīng)的'口*=（口/入）入，.實際做法是：令y=1/p,x=G/c,s—x=0則上述方程化為(—x=0則上述方程化為(yK+11)2Kyk+1一(K+1)yK+1ezplot('(y"2T)”2/(y”2-2*y+1)-x',[0,16])

axis([01603])holdon;pause;%%%%%k=2ezplot('(y“3T)“2/(2*y“3-3*y“2+1)-x',[0,16])axis([01603])%%%k=3ezplot('(y“4T)“2/(3*y"4-4*y“3+1)-x',[0,16])axis([01603])例1對某服務(wù)臺進行實測，得到如下數(shù)據(jù)：系統(tǒng)中的顧客數(shù)(n):0 1 2 3

記錄到的次數(shù)(mJ:161975334平均服務(wù)時間為10min，服務(wù)一個顧客的收益2元,服務(wù)機構(gòu)運行單位時間成本為1元，問服務(wù)率為多少時可使單位時間平均收益最大？解這是M/M/1/3模型,G=2,%=1,下面從現(xiàn)在運行的數(shù)據(jù)中，估計出顧客的人.因為'n= —=P,所以pmn-1 n-1P=-4=2(0.60+0.55+0.64)=0.63m3n=1n-1

由u=1/(10/60)=6(人/h),得人=0u=0.6x6=3.6(人/h).下面進行優(yōu)化分析：作當K=3時，x=-與y=上的關(guān)系圖，cPsezplot('(y“4T)“2/(3*y"4-4*y“3+1)-x',[0,16])axis([01603])

G i—=2,由圖得土=0.82s P|Li*=X/p*=3.6x0.82~3（人/h）

但然也可作;與P的關(guān)系圖，同樣可由值c=1G G2去求出P*=1.21,及日*=人/p*=3.6/1.21=3.收益分析：當H=6（人/h）時，總收益為z=2x3.61-0.63—1x6=0.485（元/h）1-0.64 v'當R=3（人/h）時，總收益為

1-1.213z=2X3.6 -1x6=1.858（元/h）1-1.214 （ ）單位時間內(nèi)平均增加收益1.858-0.485=1.373（元/h）.相當不錯.例2考慮一個M/M/1/K系統(tǒng)，具有人=10（人/h）,H=30（人/h）,K=2管理者想改進服務(wù)，方案有二個：方案A是增加一個等待空間，即使K=3;方案B是提高平均服務(wù)率到H=40（人/h）.設(shè)每服務(wù)一個顧客的平均收入不變，問哪個方案將獲得更大的收入或利潤？當人增加到30人/h時，又將得到什么結(jié)

果？解：對A:人=10,R=30,K=3,有人=人(1—p)=X!^￡!=101-(1/3)3=9.75A 3 1—p4 1—(1/3)4對B：x=10,H=40,K=2,有人=X(1—p)=10~(，？2=9.52(人/h)B 2 1—(1/4)3由利潤公式z=X(1—p)G—cp=XG1—PK—c日K s 1—pK+1 ，

采用A,將獲得更多利潤.當人30,而仍|i=30,K=3,則P=1,代入得人廣30==22.5（人/h）,A3+1對于人=30,而H=40,K=2,則得301301-(3/4)21-(3/4)3=22.7(人/h)所以此時，若考慮增加收益，則應(yīng)采用B方案.

三、M/M/s模型中最優(yōu)的服務(wù)臺數(shù)c僅討論M/M/s/^模型且為穩(wěn)態(tài)，設(shè)全部費用z=c，?s+cL. (###)其中：c'是每個服務(wù)臺的單位時間的成本；sc是顧客在系統(tǒng)中逗留單位時間的費用，Ws是服務(wù)臺數(shù)；L是平均隊長.由于c：和八是給定的，所以L是服務(wù)臺數(shù)s的函數(shù),可記為z=z(s).因為s是整數(shù)，所以不易求z',改用邊際法.(增減1

分析法)由minz=z(s*),貝0\z(s*)<z(s*-1)[z(s*)<z(s*+1)用(###)代入，得Ic'-s*+cL(s*)<c'-(s*-1)+cL(s*-1)<s w s w[c‘?s*+cL(s*)<c-(s*+1)+cL(s*+1)s w s wc從第一式得一<L(s*-1)—L(s*)c

_ _一c從第二式得L(s*)—L(s*+1)<—,cw, -，、一， 八c-， 八_,、故合為:L(s*)—L(s*+1)<——<L(s*—1)—L(s*)cw依次試s=1,2,...,取使上式成立的s*.例3某檢驗中心為各工廠服務(wù)，要求作檢驗的工廠(顧客)的到來為?泊松流，平均到達率人為48次/天，每次檢驗時，因停工要損失6元.

服務(wù)時間?負指數(shù)分布，平均服務(wù)率R為25次/天，設(shè)置一個檢驗員成本每天4元，其他條件同M/M/s.問，應(yīng)設(shè)多少檢驗員，使總費用平均值最少？解已矢口c'=4，c=6,X=48,p=25,人/p=1.92令檢驗員數(shù)s，將s=1，2，...，5分別代入-寸11.92〃 1 1.92s]t"*+"FL〃=0 」和L=L+p=P0?L92"1+1.92q (s-1)!(s-1.92)2

得如下表格檢驗員數(shù)s平均顧客數(shù)L(s)L(s)-L(s+1)?L(s-1)-L(s)總費用(元/d)188224.4921.845?8154.9432.6450.582?21.84527.87*42.0630.111?0.58228.3851.95231.71由于c/c=4/6=0.676(0.582,21.845),故s*—3.即當s*—3時，總費用z最小，最小值為z(3)—27.87(元).

§7排隊系統(tǒng)的隨機模擬分析法當?shù)竭_、服務(wù)分布未知，或難于解析表達時，可用隨機模擬方法.例設(shè)一卸貨場，貨車夜間到達，白天卸貨，每天只卸3車，余車次曰再卸.求每天推遲卸貨的平均車數(shù)（車/天）.根據(jù)長年統(tǒng)計，得出.到達車數(shù)0123456概率0.050.30.30.10.050.20解由夜到白卸的特點，這不是泊松流，服務(wù)時間也不服負指數(shù)分布（實際是定長服務(wù)時間）.

由上表可得平均到達的車輛2.4輛/天，a=[0123456];p=[0.050.30.30.10.050.20];a*p’=2.4理想中應(yīng)能正常卸貨，推遲卸貨的車輛數(shù)為0?隨機模擬法的思想：計算每天到達的車輛，可卸貨的車輛，推遲卸貨的車輛.最后計算一個平均推遲的車輛數(shù).即Lq具體步驟為(1)根據(jù)概率的經(jīng)驗表，做100張卡表示概率卡號:0?99,卡號和卡值(到達車數(shù))如下表

到達車數(shù)概率累積概率對應(yīng)的卡號00.050.050~410.300.355~3420.300.6535~6430.100.7565~7440.050.8075~7950.201.0080~99模擬時，隨機抽取第一張卡，若卡號=55表示：第一天到達車數(shù)為2.隨機抽取第二張卡，若卡號=82

表示第二天有5輛車到達，以此類推模擬幾十個.如100等.［計算機模擬時，隨機生成100個數(shù)（0?99號碼的數(shù)）］然后列出到達數(shù)-需要卸貨車數(shù)-實卸車數(shù)-推遲卸貨數(shù)，如表10-8.注：需要卸貨車數(shù)=前天推遲的車數(shù)+當天到達車數(shù)最后計算（第二版）表10-8最后一列的平均推遲卸貨車數(shù).

程序如下%先模擬3天，從第4天至33天進行統(tǒng)計計算%隨機發(fā)生33(更多)個0?99中的數(shù)%排隊系統(tǒng)隨機模擬法clear;cd=ones(1,100);%卡號因matlab中無0下標cd(1,1:5)=0*cd(1,1:5);%相當于5%的概率無船到達cd(1,6:35)=1*cd(1,6:35);%意義同上cd(1,36:65)=2*cd(1,36:65);cd(1,66:75)=3*cd(1,66:75);cd(1,76:80)=4*cd(1,76:80);

cd(1,81:100)=5*cd(1,81:100);%33個0~99中的隨機數(shù)k=33;d33=fix(rand(1,k)*100);%初始余量為0;r33=zeros(1,k);%試運行前3天x=1;%第一天n=d33(1)+1;%n是1~100之間的數(shù)cs=cd(n);%到達數(shù)ifcs-3>0

r33(1)=cs-3;%推遲卸貨車輛數(shù)endforx=2:3%第2,3天也如此n=d33(x)+1;%隨機數(shù)cs=cd(n)+r33(x-1);%需要卸貨車數(shù)ifcs-3>0r33(x)=cs-3;%推遲卸貨車數(shù)endend%正式運行30天fori=4:k%第4天正式開始

n=d33(i)+1;%隨機數(shù)cs=cd(n)+r33(i-1);%%需要