排队系统的优化

§6排队系统的优化一、排队系统的优化问题有两类最优设计=静态问题：系统设计的最优化;（运行前）最优控制=动态问题：系统控制的最优化;（运行中）只讨论静态问题；一般,顾客满意，服务成本高;服务简单，顾客等待多.最优化的目标之一是兼顾两者，使之合理.方法：数学中的极值原理，或经济中的边际法.

二、MW7模型中最优服务率p1.M/M/V^模型优化设。为单位时间服务成本,。为在系统中逗留费用,TOC\o"1-5"\h\zS W则目标函数取为z=cH+。LS W将乙=入/(._>)代入，得z=c|Ll+CX/(|Ll-X),sw足 dz X々 —=c-c =0,d|LlsW(|LX—A)2得服务率应订在|L1*=X+J%人(口>人).

2.M/M/1/K模型优化顾客被拒概率为？，接受概率1-〃，K K有效进入概率人=Mi—p），即有效到达率.e K设每服务一个顾客服务机构获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,进而确定出使服务系统最优的H*.一般用数值计算方法求解，或图解法.

设人,G,K,%为已知.由具体的G/c,找出对应的'口*=（口/入）入，.实际做法是：令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对某服务台进行实测，得到如下数据：系统中的顾客数(n):0 1 2 3

记录到的次数(mJ:161975334平均服务时间为10min，服务一个顾客的收益2元,服务机构运行单位时间成本为1元，问服务率为多少时可使单位时间平均收益最大？解这是M/M/1/3模型,G=2,%=1,下面从现在运行的数据中，估计出顾客的人.因为'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).下面进行优化分析：作当K=3时，x=-与y=上的关系图，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的关系图，同样可由值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 （ ）单位时间内平均增加收益1.858-0.485=1.373（元/h）.相当不错.例2考虑一个M/M/1/K系统，具有人=10（人/h）,H=30（人/h）,K=2管理者想改进服务，方案有二个：方案A是增加一个等待空间，即使K=3;方案B是提高平均服务率到H=40（人/h）.设每服务一个顾客的平均收入不变，问哪个方案将获得更大的收入或利润？当人增加到30人/h时，又将得到什么结

果？解：对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)所以此时，若考虑增加收益，则应采用B方案.

三、M/M/s模型中最优的服务台数c仅讨论M/M/s/^模型且为稳态，设全部费用z=c，•s+cL. (###)其中：c'是每个服务台的单位时间的成本；sc是顾客在系统中逗留单位时间的费用，Ws是服务台数；L是平均队长.由于c：和八是给定的，所以L是服务台数s的函数,可记为z=z(s).因为s是整数，所以不易求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某检验中心为各工厂服务，要求作检验的工厂(顾客)的到来为〜泊松流，平均到达率人为48次/天，每次检验时，因停工要损失6元.

服务时间〜负指数分布，平均服务率R为25次/天，设置一个检验员成本每天4元，其他条件同M/M/s.问，应设多少检验员，使总费用平均值最少？解已矢口c'=4，c=6,X=48,p=25,人/p=1.92令检验员数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

得如下表格检验员数s平均顾客数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排队系统的随机模拟分析法当到达、服务分布未知，或难于解析表达时，可用随机模拟方法.例设一卸货场，货车夜间到达，白天卸货，每天只卸3车，余车次曰再卸.求每天推迟卸货的平均车数（车/天）.根据长年统计，得出.到达车数0123456概率0.050.30.30.10.050.20解由夜到白卸的特点，这不是泊松流，服务时间也不服负指数分布（实际是定长服务时间）.

由上表可得平均到达的车辆2.4辆/天，a=[0123456];p=[0.050.30.30.10.050.20];a*p’=2.4理想中应能正常卸货，推迟卸货的车辆数为0?随机模拟法的思想：计算每天到达的车辆，可卸货的车辆，推迟卸货的车辆.最后计算一个平均推迟的车辆数.即Lq具体步骤为(1)根据概率的经验表，做100张卡表示概率卡号:0〜99,卡号和卡值(到达车数)如下表

到达车数概率累积概率对应的卡号00.050.050~410.300.355~3420.300.6535~6430.100.7565~7440.050.8075~7950.201.0080~99模拟时，随机抽取第一张卡，若卡号=55表示：第一天到达车数为2.随机抽取第二张卡，若卡号=82

表示第二天有5辆车到达，以此类推模拟几十个.如100等.［计算机模拟时，随机生成100个数（0〜99号码的数）］然后列出到达数-需要卸货车数-实卸车数-推迟卸货数，如表10-8.注：需要卸货车数=前天推迟的车数+当天到达车数最后计算（第二版）表10-8最后一列的平均推迟卸货车数.

程序如下%先模拟3天，从第4天至33天进行统计计算%随机发生33(更多)个0〜99中的数%排队系统随机模拟法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中的随机数k=33;d33=fix(rand(1,k)*100);%初始余量为0;r33=zeros(1,k);%试运行前3天x=1;%第一天n=d33(1)+1;%n是1~100之间的数cs=cd(n);%到达数ifcs-3>0

r33(1)=cs-3;%推迟卸货车辆数endforx=2:3%第2,3天也如此n=d33(x)+1;%随机数cs=cd(n)+r33(x-1);%需要卸货车数ifcs-3>0r33(x)=cs-3;%推迟卸货车数endend%正式运行30天fori=4:k%第4天正式开始

n=d33(i)+1;%随机数cs=cd(n)+r33(i-1);%%需要