zhimaoyong 发表于 2005-9-11 03:28:42

[分享]排队问题

<P ><FONT face="Times New Roman" size=3>function=MM1queue(mean_arr,mean_lea,peo_num)</FONT></P>
<P ><FONT face="Times New Roman" size=3>status=zeros(3,peo_num);</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                     %</FONT>用一个<FONT face="Times New Roman">3</FONT>行矩阵表示每个顾客的状态<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                  %</FONT>到达时间间隔,服务时间,等待时间<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>status(1,:)=exprnd(mean_arr,1,peo_num);</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                     %</FONT>随机生成各顾客的到达间隔<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>status(2,:)=exprnd(mean_lea,1,peo_num);</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                     %</FONT>随机生成各顾客的服务时间<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>for i=2:peo_num</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>    if status(1,i)&lt;=status(2,i-1)+status(3,i-1)</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>         status(3,i)=status(2,i-1)+status(3,i-1)-status(1,i);</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>    else</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>         status(3,i)=0;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>    end;</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                     %</FONT>对状态进行更新;</FONT></P>
<P ><FONT face="Times New Roman" size=3>end;</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>arr_time=cumsum(status(1,:));</FONT></P>
<P ><FONT face="Times New Roman" size=3>status(1,:)=arr_time;</FONT></P>
<P ><FONT face="Times New Roman" size=3>lea_time=sum(status);</FONT></P>
<P ><FONT face="Times New Roman" size=3>stairs(,0:peo_num);</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                            %</FONT>绘出各顾客的到达时间图<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>hold on;</FONT></P>
<P ><FONT face="Times New Roman" size=3>stairs(,0:peo_num,'r');</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                            %</FONT>绘出各顾客的离去时间图<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>legend('Arrive curve','leave curve',0)</FONT></P>
<P ><FONT face="Times New Roman" size=3>hold off</FONT></P>
<P ><FONT face="Times New Roman" size=3>figure;</FONT></P>
<P ><FONT face="Times New Roman" size=3>plot(1:peo_num,status(3,:),'r:',1:peo_num,status(2,:)+status(3,:),'k-');</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                            %</FONT>绘出每个顾客的等待时间和停留时间<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>legend('Wait Time','Stay Time',0);</FONT></P>
<P ><FONT face="Times New Roman" size=3>n1=1;</FONT></P>
<P ><FONT face="Times New Roman" size=3>n2=1;</FONT></P>
<P ><FONT face="Times New Roman" size=3>mstay_t=(sum(status(2,:))+sum(status(3,:)))/peo_num;</FONT></P>
<P ><FONT face="Times New Roman" size=3>mwait_t=mean(status(3,:));</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                            %</FONT>求平均停留时间和等待时间<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>queue_num=zeros(1,2*peo_num+1);</FONT></P>
<P ><FONT face="Times New Roman" size=3>queue_time=zeros(1,2*peo_num+1);</FONT></P>
<P ><FONT face="Times New Roman" size=3>n3=1;</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                            %while</FONT>循环求每个时间队列的长度<FONT face="Times New Roman">;</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>while n1&lt;=peo_num</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>    n3=n3+1;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>    if arr_time(n1)&lt;lea_time(n2)</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>       queue_num(1,n3)=n1-n2+1;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>       queue_time(1,n3)=arr_time(n1);</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>       n1=n1+1;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>      else</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>       queue_num(1,n3)=n1-n2-1;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>       queue_time(1,n3)=lea_time(n2);</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>       n2=n2+1;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>   end;</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>end;</FONT></P>
<P ><FONT face="Times New Roman" size=3>while n2&lt;=peo_num</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>   n3=n3+1;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>   queue_num(1,n3)=peo_num-n2;</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>   queue_time(1,n3)=lea_time(n2);</FONT></FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>   n2=n2+1;</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>end;</FONT></P>
<P ><FONT face="Times New Roman" size=3>figure;</FONT></P>
<P ><FONT face="Times New Roman" size=3>stairs(queue_time,queue_num,'k');</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">                     %</FONT>绘出队列长度的时间变化曲线<FONT face="Times New Roman">, stairs </FONT>是<FONT face="Times New Roman">Matlab</FONT>的函数</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>legend('Queue Length Curve',0);</FONT></P>
<P ><FONT face="Times New Roman" size=3>hold off;</FONT></P>
<P ><FONT face="Times New Roman" size=3>temp=diff(queue_time);</FONT></P>
<P ><FONT face="Times New Roman" size=3>overtime=max(queue_time);</FONT></P>
<P ><FONT face="Times New Roman" size=3>queue_l=sum(temp.*queue_num(2:(2*peo_num+1)))/overtime;</FONT></P>
<P ><FONT face="Times New Roman" size=3>use_rate=sum(temp(find(queue_num)))/overtime;</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">maxque=max(queue_num); % </FONT>最大队长</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3> <p></p></FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">%</FONT>然后在<FONT face="Times New Roman">Matlab</FONT>命令窗口中输入命令即可,如:<FONT face="Times New Roman">=mm1queue(0.5,0.4,200)</FONT>,其中<FONT face="Times New Roman">0.5</FONT>表示平均来到时间间隔,</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">%0.4</FONT>表示平均离开时间,<FONT face="Times New Roman">200</FONT>为人数</FONT></P>
<P ><FONT size=3>注意以下几点:</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>1.</FONT></FONT><FONT size=3>首先因为<FONT face="Times New Roman">M/M/1</FONT>中,各个实体的到达时间和服务时间相互独立,所以才能首先把每个实体的这两个时间,根据所给的参数产生模拟的随机数来。而在<FONT face="Times New Roman">Matlab</FONT>中,产生指数分布的随机数的参数是平均时间,而非到达率,这一点需要注意。</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>2.</FONT></FONT><FONT size=3>确定排队系统状态的程序很简单,只有很短的一部分,程序的后面几块主要是计算该排队系统的队长随时间的变化情况,平均队长和占用率。</FONT></P>
<P ><FONT size=3>计算某时刻的队长的基本思想是用在此时刻前到达的总实体数,减去</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>3.</FONT></FONT><FONT size=3>在此时刻前结束服务的实体数,然后不难求出平均队长和占用率。</FONT></P>
<P ><FONT size=3>在实体数很大的情况下,计算机仿真的结果和理论推导的结果很接近,这也说明了理论推导结果的正确性。</FONT></P>
<P ><FONT size=3>关于排队论的的一些知识</FONT></P>
<P ><FONT size=3>排队系统主要有:<FONT face="Times New Roman">X/Y/Z</FONT>,其中<FONT face="Times New Roman">X</FONT>表示到达时间间隔的分布,<FONT face="Times New Roman">Y</FONT>表示服务时间的分布,<FONT face="Times New Roman">Z</FONT>表示并列的服务设备的数目。表示相继到达的时间间隔或服务时间的分布的符号是:</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">M</FONT>——负指数分布,<FONT face="Times New Roman">D</FONT>——确定性,<FONT face="Times New Roman">Ek</FONT>——<FONT face="Times New Roman">k</FONT>阶<FONT face="Times New Roman">Erlang</FONT>,<FONT face="Times New Roman">GI</FONT>——相互独立的一般随机分布,<FONT face="Times New Roman">G</FONT>——一般的随机分布。</FONT></P>
<P ><FONT size=3>例如:<FONT face="Times New Roman">M/M/1</FONT>表示达到时间间隔为负指数分布,服务时间为负指数分布,单服务设备的排队系统。</FONT></P>
<P ><FONT size=3>这里我们用静态仿真的思想来实现<FONT face="Times New Roman">M/M/1</FONT>仿真。</FONT></P>
<P ><FONT size=3>在排队系统中的每一个动态实体的状态可以有三个量来反映:与前一个实体到达的时间间隔,在排到自己服务前的等待时间以及服务时间。其中服务时间和到达时间间隔服从指数分布,不受别的因素的影响。开始服务前的等待时间则受到排在前面的动态实体的状态的影响。其更新算法如下:</FONT></P>
<P ><FONT size=3>即:如果某个实体到达以后,发现处在它前面的动态实体已经结束服务,所以这个实体就不用等待,直接接受服务;反之,处在它前面的动态实体如果没有结束服务(包括没有开始服务),则这个实体的等待时间就是它前一实体结束服务的时刻减去它到达的时刻。</FONT></P>
<P ><FONT size=3>即:</FONT></P>
<P ><FONT face="Times New Roman"><FONT size=3>if arr_time(i)&lt;=arr_time(i-1)+wait_time(i-1)+sever_time(i-1)</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">%</FONT>第<FONT face="Times New Roman">i</FONT>个实体到达时刻和第<FONT face="Times New Roman">i-1</FONT>个实体的离开时刻相比较,</FONT></P>
<P ><FONT face="Times New Roman" size=3>then      wait_time(i)= wait_time(i-1)+ sever_time(i-1)+ arr_time(i-1)- arr_time(i);</FONT></P>
<P ><FONT face="Times New Roman" size=3>else wait_time(i)=0;</FONT></P>
<P ><FONT size=3>也就是:</FONT></P>
<P ><FONT face="Times New Roman" size=3>if arr_interval(i) &lt;= wait_time(i-1)+sever_time(i-1)</FONT></P>
<P ><FONT face="Times New Roman" size=3>then      wait_time(i)= wait_time(i-1)+ sever_time(i-1)- arr_interval(i);</FONT></P>
<P ><FONT face="Times New Roman" size=3>else wait_time(i)=0;</FONT></P>
<P ><FONT size=3>其中:<FONT face="Times New Roman">arr_interval(i)= arr_time(i)- arr_time(i-1); </FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">arr_time(i-1)+wait_time(i-1)+sever_time(i-1)</FONT>表示第<FONT face="Times New Roman">i-1</FONT>个实体的离开时刻。</FONT></P>
<P ><FONT size=3>程序中关于队长求法的解释如下:</FONT></P>
<P ><FONT size=3>我们要求木某一时刻的队长,那要看这个因素;第一个因素是在该时刻正在接受服务的实体(排在最前面的实体)和该时刻到达的人(即此刻排在队尾的人),此时队长很容易求出。第一个排在最前面的实体也就是第一个到达的实体<FONT face="Times New Roman">n2=1</FONT>,此时如果要求在某一时刻的队长,后来的人的到达时间<FONT face="Times New Roman">arr_time(n1)</FONT>要和<FONT face="Times New Roman">lea_time(n2) </FONT>相比较<FONT face="Times New Roman"> </FONT>(注意:<FONT face="Times New Roman">n1</FONT>从<FONT face="Times New Roman">1</FONT>开始到总实体数),相应的可以计算出某时刻的队长,同时排在最前面的实体也在变化<FONT face="Times New Roman">(n2=n2+1)</FONT>;由于总实体数目一定,因此当<FONT face="Times New Roman">n2</FONT>到某一数值时,将不会再有人到达,此时影响队长的就是排在最前面的人的离开了,因此也可以把队长求出来;总之我们可以把队长得到,详细的实现步骤请看程序中的相应的部分。</FONT></P>
<P ><FONT size=3>严庆强的新程序</FONT></P>
<Palign=center><FONT size=3>仿真程序</FONT></P>
<Palign=center><B><FONT size=3><FONT face="Times New Roman"> <p></p></FONT></FONT></B></P>
<P ><FONT face="Times New Roman" size=3>function=mvqueue(mean_arr,mean_lea,r,m,peo_num)</FONT></P>
<P ><FONT face="Times New Roman" size=3>status=zeros(6,peo_num);</FONT></P>
<P ><FONT face="Times New Roman" size=3>status(1,:)=exprnd(mean_arr,1,peo_num);</FONT></P>
<P ><FONT face="Times New Roman" size=3>status(2,:)=exprnd(mean_arr,1,peo_num);</FONT></P>
<P ><FONT face="Times New Roman" size=3>status(4,1)=status(2,1);</FONT></P>
<P ><FONT face="Times New Roman" size=3>for i=2:peo_num</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    if status (1,i)&lt;=status(2,i-1)+status(3,i-1)</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">      status(3,i)=status(2,i-1)+status(3,i-1)-status(1,i);</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    else</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">      status(3,i)=0;</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    end;</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    status(4,i)=status(2,i)+status(2,i-1)-status(1,i);</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    if status(4,i)&lt;=m</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">      status(5,i)=status(4,i);</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    else</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">      status(5,i)=status(4,i)/r+m*(1-1/r);</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    end;</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    if status(1,i)&lt;=status(5,i-1)</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">      status(6,i)=status(5,i-1)-status(1,i);</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    else </FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">      status(6,i)=0;</FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman">    end;</FONT></FONT></P>
<P ><FONT face="Times New Roman" size=3>end;</FONT></P>
<P ><FONT face="Times New Roman" size=3>arr_time=cumsum(status(1,:));</FONT></P>
<P ><FONT face="Times New Roman" size=3>status(1,:)=arr_time;</FONT></P>
<P ><FONT face="Times New Roman" size=3>lea_time=sum(status);</FONT></P>
<P ><FONT face="Times New Roman" size=3>figure;</FONT></P>
<P ><FONT face="Times New Roman" size=3>plot(1:peo_num,status(3,:),'r:',1:peo_num,status(6,:),'k-');</FONT></P>
<P ><FONT face="Times New Roman" size=3>legend('Wait Time','V-wait time',0);</FONT></P>
<P ><FONT face="Times New Roman" size=3>hold off;</FONT></P>
<P ><FONT face="Times New Roman" size=3>mwait_t=mean(status(3,:));</FONT></P>
<P ><FONT face="Times New Roman" size=3>vmwait_t=mean(status(6,:));</FONT></P>
<P ><FONT size=3><FONT face="Times New Roman"> <p></p></FONT></FONT></P>
<P ><FONT size=3><FONT face="Times New Roman"> <p></p></FONT></FONT></P>

mofen 发表于 2005-9-14 04:41:58

非常感谢

ruanshijian 发表于 2008-6-25 11:33:35

排队问题,服务台变为3个,程序要怎么变化。着急 :(

默默鱼 发表于 2009-9-17 11:30:07

谢谢分享
:)
页: [1]
查看完整版本: [分享]排队问题