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

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

二、M/M/1模型中最優(yōu)服務(wù)率卩1.M/M/1/w模型優(yōu)化設(shè)c為單位時(shí)間服務(wù)成本,c為在系統(tǒng)中逗留費(fèi)用,TOC\o"1-5"\h\zsw則目標(biāo)函數(shù)取為z二c卩+cLsw將L二九/（卩一九）代入，得z二cJi+c九/（卩一九）,sw令蟲(chóng)=c-C二0,disw（1一九）2得服務(wù)率應(yīng)訂在

得服務(wù)率應(yīng)訂在2.M/M/1/K模型優(yōu)化顧客被拒概率為p,接受概率1-p,KK有效進(jìn)入概率九=1(1-p),即有效到達(dá)率.eK設(shè)每服務(wù)一個(gè)顧客服務(wù)機(jī)構(gòu)獲G元，則單位時(shí)間收入期望值為九(1-p)GK利潤(rùn)z=九(1-p)G一c卩=九G-一c卩Ks1—pK+1s

11-p1-pK1-pK+1十1,Pk=PKP。)(注p=—01+芳pnn=1令dz/dy=0,得K-(K+1)p+pk+1cPK+1=―~(1-pK+1)2G由此確定出p,進(jìn)而確定出使服務(wù)系統(tǒng)最優(yōu)的卩*一般用數(shù)值計(jì)算方法求解，或圖解法.

設(shè)九,G,K,c為已知.s由具體的G/c,s找出對(duì)應(yīng)的卩*=(卩/九)九,.實(shí)際做法是：令y=1/p,x=G/c,s卩/入G/cs(y卩/入G/cs(yK+1—1)2則上述方程化為KyK+1—(K+1)yK+1clear;clf%%%%%k=l;ezplot('(y"2T)"2/(y"2-2*y+l)-x',[0,16])

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

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

由r=1/(10/60)=6(人/h),得九二0r二0.6x6二3.6(人/h).下面進(jìn)行優(yōu)化分析：G作當(dāng)K二3時(shí)，x=—與y=丄的關(guān)系圖，cPsezplot('(y"4T)"2/(3*y"4-4*y"3+l)-x',[0,16])axis([01603])

2.5y1.5(y4-2.5y1.5(y4-)2/(3y4"y3+i)-x=0-■■■-"a/0.5Gi由一=2,由圖得丄=0.82cp*sy*二九/p*=3.6x0.82u3(人/h)

cc1但然也可作gs與p的關(guān)系圖，同樣可由值g=2去求出p*=1.21,及卩*二九/p*二3.6/1.21二3.收益分析：當(dāng)R=6（人/h）時(shí)，總收益為z=2X3.61-0.63-1X6=0.485（元/h）1-0.64當(dāng)卩=3（人/h）時(shí)，總收益為

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

果？=9.75解：對(duì)A:九二10,卩二30,K=3,有=9.75九=X(1—p)=X上一a31—p4對(duì)B:X二10,卩二40,K=2,有二X(1二X(1—p)=1021—(1/4)21—(1/4)3=9.52(人/h)由利潤(rùn)公式z=X(1—p)G—cy=Xg1—pK—c卩Ks1—pK+1s

采用A,將獲得更多利潤(rùn).當(dāng)九30,而仍R=30,K=3,則P=1,代入得3九A=30371=22?5（人他）,對(duì)于九=30,而卩=40,K=2,則得=22.7=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.（###）sw其中：c'是每個(gè)服務(wù)臺(tái)的單位時(shí)間的成本；sc是顧客在系統(tǒng)中逗留單位時(shí)間的費(fèi)用，ws是服務(wù)臺(tái)數(shù)；L是平均隊(duì)長(zhǎng).由于c'和c是給定的，所以L是服務(wù)臺(tái)數(shù)s的函數(shù),sw可記為z=z（s）.因?yàn)閟是整數(shù)，所以不易求z',改用邊際法?（增減1

分析法)由minz=z(s*),貝I」\z(s*)<z(s*-1)[z(s*)<z(s*+1)用(###)代入，得Ic'-s*+cL(s*)<C-(s*-1)+cL(s*-1)<swsw[c'-s*+cL(s*)<c-(s*+1)+cL(s*+1)swswc'從第一式得一<L(s*-1)-L(s*)c

c從第二式得L(s*)—L(s*+1)<,cwc故合為:L(s*)—L(s*+1)<<L(s*—1)—L(s*)c依次試s=1,2,...,取使上式成立的s*.例3某檢驗(yàn)中心為各工廠服務(wù)，要求作檢驗(yàn)的工廠（顧客）的到來(lái)為?泊松流,平均到達(dá)率九為48次/天，每次檢驗(yàn)時(shí)，因停工要損失6元.

服務(wù)時(shí)間?負(fù)指數(shù)分布，平均服務(wù)率卩為25次/天，設(shè)置一個(gè)檢驗(yàn)員成本每天4元，其他條件同M/M/s.問(wèn)，應(yīng)設(shè)多少檢驗(yàn)員，使總費(fèi)用平均值最少？解已知c'二4，c二6,九二4&卩二25,九/卩二1.92sw-1令檢驗(yàn)員數(shù)s，將s=1，2，...，5-11.92n11.92s+?一n!(s-1)!s-1.92+1.92p1.92s+1+1.920--(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)1gg224.4921.845?g154.9432.6450.582?21.84527.87*42.0630.111?0.58228.3851.95231.71由于c'/c二4/6二0.67e(0.582,21.845),故sws*=3.即當(dāng)s*二3時(shí)，總費(fèi)用z最小，最小值為z⑶二27.87(元).

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

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

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

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

程序如下%先模擬3天，從第4天至33天進(jìn)行統(tǒng)計(jì)計(jì)算%隨機(jī)發(fā)生33(更多)個(gè)0?99中的數(shù)%排隊(duì)系統(tǒng)隨機(jī)模擬法clear;cd=ones(l,100);%卡號(hào)因matlab中無(wú)0下標(biāo)cd(l,l:5)=0*cd(l,l:5);%相當(dāng)于5%的概率無(wú)船到達(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(l,81:100)=5*cd(l,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(l)=cs-3;%推遲卸貨車(chē)輛數(shù)endforx=2:3%第2,3天也如此n=d33(x)+1;%隨機(jī)數(shù)cs=cd(n)+r33(x-1);%需要卸貨車(chē)數(shù)ifcs-3>0r33(x)=cs-3;%推遲卸貨車(chē)數(shù)endend%正式運(yùn)行30天fori=4:k%第4天正式開(kāi)始

n=d33(i)+l;%隨機(jī)數(shù)cs=cd(n)+r33(i-l);%%需要卸貨車(chē)數(shù)ifcs