本文在研究体检排队问

1、8/8摘要本文在研究体检排队问题的同时，采用了M/M/1/S排队论和抽象的迪克斯特拉（Dijkstra）算法，分别对科室抽血、内科、外科等等进行了有效地估计。通过顾客的到达时间、离开时间、停留时间、等待时间反映了在研究体检所用时间最短的相对优化的时间模型 问题1：为某个新来的客人安排他的体检顺序，使其完成需要的全部检查的时间尽量少（在各个体检项目处都可能有人排队等待），通过对数据的处理，对于抽血A、内科B、外科B、B超D、五官科E、胸透F、身高G和体重H八个科室排出耗费时间相对最短的路径的算法。 问题2：通过表格一的数据和上述的算法思想，在有效的假设中，用MATLAB软件得出了八个科室的有效地

2、相对最佳路径AFHGBCED。推导所消耗的时间最短。问题3： 关键词：M/M/1/S排队论 （Dijkstra）算法 1. 问题重述医院就医排队是大家都非常熟悉的现象，我们现通过考虑某医院眼科病床的合理安排的数学建模问题，提出安排策略，尽量减少病人排队等待时间。 该医院门诊每天开放，每天来的体检人数都是同分布的，体检项目包括抽血、内科、外科、B超、五官科、胸透、身高和体重等八个项目 当前医院没有完备的系统来确定来的人群的径向流量，提高设备利用率、降低客人的等待时间，医院要求完备的方案来对体检的人进行有效地指导就医。问题1：为某个新来的客人安排他的体检顺序，使其完成需要的全部检查的时间尽量少（在

3、各个体检项目处都可能有人排队等待），求出时间最短的路径问题2：通过数据来验证问题1的模型的优劣。问题3： 2.1 模型假设1)各个体检项目之间相互独立，互不影响。2)病人排队体检和体检完毕到下一个科室之间没有时间延迟。3)入院体检的顾客单个到达，相继到达时间间隔服从参数为的负指数分布。4)各个科室可以抽象一个点。5）每个服务台的服务时间相互独立，且服从参数为的负指数分布。6）在团体病人来体检时，假设每个科室的服务设施是空缺的。 2.2 符号说明 1：抽血A1、内科B1、外科C3、B超D4、五官科E5、胸透F6、身高G7、体重H82：（i）和lamuda(i) 表示单位时间平均到达的顾客数, 称

4、为平均到达率3：(i)和mu(i) 位时间能被服务完成的顾客数，称为平均服务率4：t(i)：在ABCDEFGH各个科室检查的时间5：(i):表示在ABCDEFGH各个科室的受检比率3. 问题一3.1 问题分析 3.1.1 背景分析“三长一短”（挂号时间长、候诊时间长、交费时间长、看病时间短)一直是中国各大医院的顽疾，也成为影响病人满意度的主要因素。现有某医院住院部采取了一些方案安排病人住院，却使等待病人越来越多。为了使该医院的体检病人在最短的时间内完成体检项目，设计一个可以有效的解决的上述问题的算法。3.1.2 评价分析 通常医院的采取的各个方案按照大众的顾客考虑的，在排队体检的过程中由于在各

5、个科室体检时间不相等，同时在各个科室个的等待人数比率不同。 给出评价标准是体检的时间最短 表格 SEQ 表格 * ARABIC 1抽血内科外科B超五官科胸透身高体重时间222122111检率0.950.20.20.70.21.00.50.73.1.3模型的阐述：泊松流与指数分布 设N(t)表示在时间区间0,t)内到达的顾客数（t 0），令P( t1, t2) 1表示在时间区间 内有n( 0)个顾客到达的概率.当合于下列三个条件时，我们说顾客的到达形成泊松流。这三个条件是：1o 在不相重叠的时间区间内顾客到达数是相互独立的，我们称这性质为无后效性。2o 对充分小的t，在时间区间t,t + t)内

6、有一个顾客到达的概率与t无关，而约与区间长t成正比，即 其中o(t)，当t 0时，是关于t的高阶无穷小。 0是常数，它表示单位时间有一个顾客到达的概率，称为概率强度。3o 对于充分小的t，在时间区间t,t + t)内有两个或两个以上顾客到达的概率极小，以致可以忽略，即在上述条件下，我们研究顾客到达数n 的概率分布。由条件2o，我们总可以取时间由0算起，并简记由条件1o 和2o，有由条件2o 和3o 得 因而有在以上两式中，取t趋于零的极限，当假设所涉及的函数可导时，得到以下微分方程组取初值，容易解出 。再令 ，可以得到 及其它U (t) n 所满足的微分方程组，即 由此容易解得对于泊松流, 表

7、示单位时间平均到达的顾客数,所以1/就表示相继顾客到达平均间隔时间，而这正和ET 的意义相符。表示单位时间能被服务完成的顾客数，称为平均服务率，而1/表示一个顾客的平均服务时间。 根据表格一的数据和实际情况，给出每个科室的和的表格表格 SEQ 表格 * ARABIC 2 lamuda130mu120 lamuda230 mu224 lamuda330mu325 Lamuda4 5mu43 lamuda530mu521 Lamuda6 60mu642 Lamuda7 60mu730 Lamuda8 60mu845 根据表格2的数据，用MATLAB编程得出了抽血科室的到达时间和离开时间的图，和等待

8、时间与停留时间。 根据对抽血科室的时间和表格一的数据处理，通过上面的图可以看出：当人数呈数据流的泊松分布，与现实相符。 把每个科室抽象成一个点，时间与检比的积根当做权重。据迪克斯特拉（Dijkstra）算法，其基本思想是按距 从近到远为顺序，依次求得A到G 的各顶点的最短路和距离，直至（或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法把达到这个最小值的一个顶点记为，令 。|,停止。算法结束后，可以知道遍历的最短路径。通过数据的处理：网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述

9、图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5 种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法 ，在下面数据结构的讨论中，我们首先假设是一个简单有向图。m，并假设V 中的顶点用自然数1,2,L,n表示或编号， A中的弧用自然数1,2,L,m表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。的邻接矩阵是如下定义： 也就是说，如果两节点之间有一条弧

10、，则邻接矩阵中对应的元素为 1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有n2个元素中，只有m个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。 对于上述的问题，可以分别在A、B、C、D、E、F、G、H等各个体检项目抽象成一个点，边权近似等于时间和受检比率的内积。可以得到邻接矩阵: A BCDEFGHA01.51.57.71.50.51.41.2B00800.60.10.3C0800.60.10.3D087.47.97.7E00.60.10.3F00.50.3G00.2H0同样，对于网络中的权，也可以用类似邻接矩阵的88 矩阵

11、表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。用矩阵A88来存放各边权的邻接矩阵，行向量pb,index1，index2，d分别表示存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量index2(i)存放始点到第i各点最短路径的第i个顶点的序号 d(i):存放由始点到i个点的最短路径。用MATLAB算出最短路径AFHGBCED.附录：程序代码：clear clc %* %初始化顾客源 %* %总仿真时间 Total_time = 10; %队列最大长度 N = 10000000000; %到达率与服务率 l

12、ambda =30; mu =20; %平均到达时间与平均服务时间 arr_mean = 1/lambda; ser_mean = 1/mu; arr_num = round(Total_time*lambda*2); events = ; %按负指数分布产生各顾客达到时间间隔 events(1,:) = exprnd(arr_mean,1,arr_num); %各顾客的到达时刻等于时间间隔的累积和 events(1,:) = cumsum(events(1,:); %按负指数分布产生各顾客服务时间 events(2,:) = exprnd(ser_mean,1,arr_num); %计算仿真

13、顾客个数，即到达时刻在仿真时间内的顾客数 len_sim = sum(events(1,:)Total_time break; else number = sum(events(4,member) events(1,i); %如果系统已满，则系统拒绝第 i个顾客，其标志位置 0 if number = N+1 events(5,i) = 0; %如果系统为空，则第 i个顾客直接接受服务 else if number = 0 %其等待时间为 0%PROGRAMLANGUAGEPROGRAMLANGUAGEevents(3,i) = 0; %其离开时刻等于到达时刻与服务时间之和 events(4,

14、i) = events(1,i)+events(2,i); %其标志位置 1 events(5,i) = 1; member = member,i; %如果系统有顾客正在接受服务，且系统等待队列未满，则 第 i个顾客进入系统 else len_mem = length(member); %其等待时间等于队列中前一个顾客的离开时刻减去其到 达时刻 events(3,i)=events(4,member(len_mem)-events(1,i); %其离开时刻等于队列中前一个顾客的离开时刻加上其服 %务时间 events(4,i)=events(4,member(len_mem)+events(2

15、,i); %标识位表示其进入系统后，系统内共有的顾客数 events(5,i) = number+1; member = member,i; end end end end %仿真结束时，进入系统的总顾客数 len_mem = length(member); %* %输出结果 %* %绘制在仿真时间内，进入系统的所有顾客的到达时刻和离 %开时刻曲线图（stairs：绘制二维阶梯图） stairs(0 events(1,member),0:len_mem); hold on; stairs(0 events(4,member),0:len_mem,.-r); legend(到达时间 ,离开时间

16、); hold off; grid on; %绘制在仿真时间内，进入系统的所有顾客的停留时间和等 %待时间曲线图（plot：绘制二维线性图） figure; plot(1:len_mem,events(3,member),r-*,1: len_mem,events(2,member)+events(3,member),k-); legend(等待时间 ,停留时间 ); grid on;其余的图改一下lamuda和mu值。程序2：clear;clc;n=8; a=zeros(n);a(1,2)=1.5;a(1,3)=1.5;a(1,4)=7.7;a(1,5)=1.5;a(1,6)=0.5;a(1,7)=1.4;a(1,8)=1.2;a(2,4)=8;a(2,6)=0.6;a(2,7)=0.1;a(2,8)=0.3;a(3,4)=8;a(3,6)=0.6;a(3,7)=0.1;a(3,8)=0.3;a(4,5)=8;a(4,6)=7.4;a(4,7)=7.9;a(4,8)=