摘要
本文在研究体检排队问题的同时，采用了M/M/1/S排队论和抽象的迪克斯特拉（Dijkstra）算法，分别对科室抽血、内科、外科等等进行了有效地估计。通过顾客的到达时间、离开时间、停留时间、等待时间反映了在研究体检所用时间最短的相对优化的时间模型
问题1：为某个新来的客人安排他的体检顺序，使其完成需要的全部检查的时间尽量少（在各个体检项目处都可能有人排队等待），通过对数据的处理，对于抽血A、内科B、外科B、B超D、五官科E、胸透F、身高G和体重H八个科室排出耗费时间相对最短的路径的算法。
问题2：通过表格一的数据和上述的算法思想，在有效的假设中，用MATLAB软件得出了八个科室的有效地相对最佳路径AFHGBCED。推导所消耗的时间最短。 问题3：
关键词：M/M/1/S排队论 （Dijkstra）算法
1. 问题重述
医院就医排队是大家都非常熟悉的现象，我们现通过考虑某医院眼科病床的合理安排的数学建模问题，提出安排策略，尽量减少病人排队等待时间。 该医院门诊每天开放，每天来的体检人数都是同分布的，体检项目包括抽血、内科、外科、B超、五官科、胸透、身高和体重等八个项目
当前医院没有完备的系统来确定来的人群的径向流量，提高设备利用率、降低客人的等待时间，医院要求完备的方案来对体检的人进行有效地指导就医。
问题1：为某个新来的客人安排他的体检顺序，使其完成需要的全部检查的时间尽量少（在各个体检项目处都可能有人排队等待），求出时间最短的路径
问题2：通过数据来验证问题1的模型的优劣。 问题3： 2.1 模型假设
1) 各个体检项目之间相互，互不影响。
2) 病人排队体检和体检完毕到下一个科室之间没有时间延迟。 3) 入院体检的顾客单个到达，相继到达时间间隔服从参数为λ的负指数分布。 4) 各个科室可以抽象一个点。
5）每个服务台的服务时间相互，且服从参数为μ的负指数分布。 6）在团体病人来体检时，假设每个科室的服务设施是空缺的。 2.2 符号说明
1：抽血A1、内科B1、外科C3、B超D4、五官科E5、胸透F6、身高G7、体重H8 2：λ（i）和lamuda(i) 表示单位时间平均到达的顾客数, 称为平均到达率 3：μ(i)和mu(i) 位时间能被服务完成的顾客数，称为平均服务率
4：t(i)：在ABCDEFGH各个科室检查的时间
5：β(i):表示在ABCDEFGH各个科室的受检比率
3. 问题一
3.1 问题分析 3.1.1 背景分析
“三长一短”（挂号时间长、候诊时间长、交费时间长、看病时间短)一直是中国各大医院的顽疾，也成为影响病人满意度的主要因素。现有某医院住院部采取了一些方案安排病人住院，却使等待病人越来越多。为了使该医院的体检病人在最短的时间内完成体检项目，设计一个可以有效的解决的上述问题的算法。 3.1.2 评价分析
通常医院的采取的各个方案按照大众的顾客考虑的，在排队体检的过程中由于在各个科室体检时间不相等，同时在各个科室个的等待人数比率不同。 给出评价标准是体检的时间最短
表格 1
时间 抽血 内科 外科 B超 2 2 0.2 2 0.2 12 0.7
五官科 2 0.2 胸透 1 1.0 身高 1 0.5 体重 1 0.7 检率 0.95 3.1.3模型的阐述： 泊松流与指数分布
设N(t)表示在时间区间[0,t)内到达的顾客数（t > 0），令P( t1, t2) 1表示在时间区 间
内有n(≥ 0)个顾客到达的概率.
当
合于下列三个条件时，我们说顾客的到达形成泊松流。这三个条件是：
1o 在不相重叠的时间区间内顾客到达数是相互的，我们称这性质为无后效 性。
2o 对充分小的Δt，在时间区间[t,t + Δt)内有一个顾客到达的概率与t无关，而
约与区间长Δt成正比，即
其中o(Δt)，当Δt →0时，是关于Δt的高阶无穷小。λ > 0是常数，它表示单位时间
有一个顾客到达的概率，称为概率强度。
3o 对于充分小的Δt，在时间区间[t,t + Δt)内有两个或两个以上顾客到达的概率
极小，以致可以忽略，即
在上述条件下，我们研究顾客到达数n 的概率分布。 由条件2o，我们总可以取时间由0算起，并简记由条件1o 和2o，有
由条件2o 和3o 得
因而有
在以上两式中，取Δt趋于零的极限，当假设所涉及的函数可导时，得到以下微分方程 组 取初值再令 程组，即
，，可以得到
，容易解出
。
及其它U (t) n 所满足的微分方
由此容易解得
对于泊松流,λ 表示单位时间平均到达的顾客数,所以1/λ就表示相继顾客到达平均
间隔时间，而这正和ET 的意义相符。
μ表示单位时间能被服务完成的顾客数，称为平均服务率，而1/μ表示一个顾客
的平均服务时间。
根据表格一的数据和实际情况，给出每个科室的λ和μ的表格 表格 2 lamuda1 30 mu1 20 lamuda2 30 mu2 24 lamuda3 30 mu3 25 Lamuda4 5 mu4 3 lamuda5 30 mu5 21 Lamuda6 60 mu6 42 Lamuda7 60 mu7 30 Lamuda8 60 mu8 45 根据表格2的数据，用MATLAB编程得出了抽血科室的到达时间和离开时间的图，和等待时间与停留时间。
根据对抽血科室的时间和表格一的数据处理，通过上面的图可以看出： 当人数呈数据流的泊松分布，与现实相符。
把每个科室抽象成一个点，时间与检比的积根当做权重。
据迪克斯特拉（Dijkstra）算法，其基本思想是按距 从近到远为顺序，依次求得A到G 的各顶点的最短路和距离，直至（或直至G 的所有
顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法
把达到这个最小值的一个顶点记为。 |,停止。
算法结束后，可以知道遍历的最短路径。 通过数据的处理：
网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。
，令
一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5 种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法 ，在下面数据结构的讨论中，我们首先假设
是一个简单有向图。m，并假
设V 中的顶点用自然数1,2,L,n表示或编号， A中的弧用自然数1,2,L,m表示或编号。对于有多重边或无向网络的情
况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。
的邻接矩阵是如下定义：
也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为 1；否则为0。 可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有n2个元素中，只有m个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。
对于上述的问题，可以分别在A、B、C、D、E、F、G、H等各个体检项目抽象成一个点，边权近似等于时间和受检比率的内积。可以得到邻接矩阵:
A B C D E F G H A 0 1.5 1.5 7.7 1.5 0.5 1.4 1.2 B 0 0 8 0 0.6 0.1 0.3 C 0 8 0 0.6 0.1 0.3 D 0 8 7.4 7.9 7.7 E 0 0.6 0.1 0.3 F 0 0.5 0.3 G 0 0.2 H 0
同样，对于网络
中的权，也可以用类似邻接矩阵的8×8 矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。用矩阵A8×8来存放各边权的
邻接矩阵，行向量pb,index1，index2，d分别表示存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量
index2(i)存放始点到第i各点最短路径的第i个顶点的序号 d(i):存放由始点到i个点的最短路径。 用MATLAB算出最短路径AFHGBCED.
附录：程序代码： clear clc
%***************************************** %初始化顾客源
%***************************************** %总仿真时间
Total_time = 10; %队列最大长度 N = 10000000000; %到达率与服务率 lambda =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);
%计算仿真顾客个数，即到达时刻在仿真时间内的顾客数 len_sim = sum(events(1,:)<= Total_time); %***************************************** %计算第 1个顾客的信息
%***************************************** %第 1个顾客进入系统后直接接受服务，无需等待 events(3,1) = 0;
%其离开时刻等于其到达时刻与服务时间之和 events(4,1) = events(1,1)+events(2,1); %其肯定被系统接纳，此时系统内共有 %1个顾客，故标志位置1 events(5,1) = 1;
%其进入系统后，系统内已有成员序号为 1 member = [1];
for i = 2:arr_num
%如果第 i个顾客的到达时间超过了仿真时间，则跳出循环
if events(1,i)>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
%PROGRAMLANGUAGEPROGRAMLANGUAGE events(3,i) = 0;
%其离开时刻等于到达时刻与服务时间之和 events(4,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,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('到达时间 ','离开时间 ');
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)=7.7;a(5,6)=0.6;a(5,7)=0.1;a(5,8)=0.3; a(6,7)=0.5;a(6,8)=0.3;a(7,8)=0.2
a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数 a=a+((a==0)-eye(n))*M; path=zeros(n); for k=1:n for i=1:n for j=1:n
if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end
end end
a, path 副本图：内科
其余的改变lamudah和mu值。
