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

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

二、MW7模型中最優(yōu)服務(wù)率p1.M/M/V^模型優(yōu)化設(shè)。為單位時(shí)間服務(wù)成本,。為在系統(tǒng)中逗留費(fèi)用,TOC\o"1-5"\h\zS W則目標(biāo)函數(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有效進(jìn)入概率人=Mi—p），即有效到達(dá)率.e K設(shè)每服務(wù)一個(gè)顧客服務(wù)機(jī)構(gòu)獲G元，則單位時(shí)間收入期望值為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,進(jìn)而確定出使服務(wù)系統(tǒng)最優(yōu)的H*.一般用數(shù)值計(jì)算方法求解，或圖解法.

設(shè)人,G,K,%為已知.由具體的G/c,找出對應(yīng)的'口*=（口/入）入，.實(shí)際做法是：令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ù)臺(tái)進(jìn)行實(shí)測，得到如下數(shù)據(jù)：系統(tǒng)中的顧客數(shù)(n):0 1 2 3

記錄到的次數(shù)(mJ:161975334平均服務(wù)時(shí)間為10min，服務(wù)一個(gè)顧客的收益2元,服務(wù)機(jī)構(gòu)運(yùn)行單位時(shí)間成本為1元，問服務(wù)率為多少時(shí)可使單位時(shí)間平均收益最大？解這是M/M/1/3模型,G=2,%=1,下面從現(xiàn)在運(yùn)行的數(shù)據(jù)中，估計(jì)出顧客的人.因?yàn)?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).下面進(jìn)行優(yōu)化分析：作當(dāng)K=3時(shí)，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.收益分析：當(dāng)H=6（人/h）時(shí)，總收益為z=2x3.61-0.63—1x6=0.485（元/h）1-0.64 v'當(dāng)R=3（人/h）時(shí)，總收益為

1-1.213z=2X3.6 -1x6=1.858（元/h）1-1.214 （ ）單位時(shí)間內(nèi)平均增加收益1.858-0.485=1.373（元/h）.相當(dāng)不錯(cuò).例2考慮一個(gè)M/M/1/K系統(tǒng)，具有人=10（人/h）,H=30（人/h）,K=2管理者想改進(jìn)服務(wù)，方案有二個(gè)：方案A是增加一個(gè)等待空間，即使K=3;方案B是提高平均服務(wù)率到H=40（人/h）.設(shè)每服務(wù)一個(gè)顧客的平均收入不變，問哪個(gè)方案將獲得更大的收入或利潤？當(dāng)人增加到30人/h時(shí)，又將得到什么結(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,將獲得更多利潤.當(dāng)人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)所以此時(shí)，若考慮增加收益，則應(yīng)采用B方案.

三、M/M/s模型中最優(yōu)的服務(wù)臺(tái)數(shù)c僅討論M/M/s/^模型且為穩(wěn)態(tài)，設(shè)全部費(fèi)用z=c，?s+cL. (###)其中：c'是每個(gè)服務(wù)臺(tái)的單位時(shí)間的成本；sc是顧客在系統(tǒng)中逗留單位時(shí)間的費(fèi)用，Ws是服務(wù)臺(tái)數(shù)；L是平均隊(duì)長.由于c：和八是給定的，所以L是服務(wù)臺(tái)數(shù)s的函數(shù),可記為z=z(s).因?yàn)閟是整數(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某檢驗(yàn)中心為各工廠服務(wù)，要求作檢驗(yàn)的工廠(顧客)的到來為?泊松流，平均到達(dá)率人為48次/天，每次檢驗(yàn)時(shí)，因停工要損失6元.

服務(wù)時(shí)間?負(fù)指數(shù)分布，平均服務(wù)率R為25次/天，設(shè)置一個(gè)檢驗(yàn)員成本每天4元，其他條件同M/M/s.問，應(yīng)設(shè)多少檢驗(yàn)員，使總費(fèi)用平均值最少？解已矢口c'=4，c=6,X=48,p=25,人/p=1.92令檢驗(yàn)員數(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

得如下表格檢驗(yàn)員數(shù)s平均顧客數(shù)L(s)L(s)-L(s+1)?L(s-1)-L(s)總費(fèi)用(元/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.即當(dāng)s*—3時(shí)，總費(fèi)用z最小，最小值為z(3)—27.87(元).

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

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

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

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

程序如下%先模擬3天，從第4天至33天進(jìn)行統(tǒng)計(jì)計(jì)算%隨機(jī)發(fā)生33(更多)個(gè)0?99中的數(shù)%排隊(duì)系統(tǒng)隨機(jī)模擬法clear;cd=ones(1,100);%卡號因matlab中無0下標(biāo)cd(1,1:5)=0*cd(1,1:5);%相當(dāng)于5%的概率無船到達(dá)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個(gè)0~99中的隨機(jī)數(shù)k=33;d33=fix(rand(1,k)*100);%初始余量為0;r33=zeros(1,k);%試運(yùn)行前3天x=1;%第一天n=d33(1)+1;%n是1~100之間的數(shù)cs=cd(n);%到達(dá)數(shù)ifcs-3>0

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

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