体检排队问题.doc

精品文档体检排队问题摘要本文讨论的是如何安排顾客的体检顺序，以提高设备利用率、降低顾客等待时间的问题。本文的创新之处在于利用计算机编程模拟排队模型，结合调查得到的资料，直接利用编程模拟产生了每个人的体检顺序及其相应的时间，使得解答更加周密、全面，而且模拟时只需要输入原始数据即可得到相应的结果，操作简便易行，故而具备较强的实用性。本文依据顾客的到达人数的随机性，建立了以体检时间最小为目标函数的微分模型，即排队模型，又巧妙地将对原目标函数的求解转化为求每个项目当前排队人数问题，从而运用微分、利用MATLAB软件编程对个人的体检顺序做出定性的分析，并代入数据予以检验。问题一，根据建立的模型，利用MATLAB软件插值拟合体检人员到达率与时间的关系，再根据到达率，计算出时间内的到达人数。最后，计算出当前每个项目的等待时间，通过比较得出等待时间较少的体检顺序。问题二，利用问题一的模型，本文设计出一组较为合理的数据来验证上述结论。人数到达时间检查项目体检顺序体检时间1t=2.5(即上午十点半到达)抽血 外科 B超 身高体重B超、身高体重、抽血、外科63分钟问题三，我们将团体体检分为将团体视为一个整体，将团体的各队员全部分开情况予以讨论。经过模型计算，得到团队体检顺序的较优值，其结果见正文。关键词：插值拟合、MATLAB、体检项目、贪心算法一、 问题重述某城市的体检中心每天有许多人前去体检，全部体检项目包括：抽血、内科、外科、B超、五官科、胸透、身高、体重、等等。每个人的体检项目可能各不相同，假设每个体检项目的服务时间是确定的，并且只有1个医生值班，每次只能为1个客户服务。为提高设备利用率、降低客人的等待时间，中心请你帮助完成如下任务：1. 请你为某个新来的客人安排他的体检顺序，使其完成需要的全部检查的时间尽量少（在各个体检项目处都可能有人排队等待）；2. 设计1组数据来验证上述结论。3. 接待团体客人时，如何安排每个人的体检顺序，使得体检中心能尽快完成任务，设计1组数据来验证该结论。二、 问题分析问题一，要使完成需要的全部检查的时间尽量少，就必须考虑一下几个因素：（1）当前体检人员及待检人员的统计情况；（2）该体检人员所需检查的项目以及每个项目所需要的时间；（3）单位时间内到达和离开检查中心的人数；（4）体检医疗设施和医务人员的限制；因此，不同时间每个因素所处的状态不同，这些状态都将影响检查所需要的总时间。问题二，要求设计一组数据来验证第一问的结论，因此我们除了要考虑第一题中提到的因素以外，还要考虑设计数据的合理性以及有效的说服力。问题三，对于团体客人时，由于团队客人所需要检查的项目是相同的，而且团队客人是同时到达的。所以在安排时，要考虑到在同一时间内对团队客人的初次体检项目进行分配。然后再根据每个项目的实际待检人数以及每个项目的服务时间再次对客人进行安排，直到最后一名团队客人在较短的时间内完成所需体检的项目。三、基本假设与符号说明3.基本假设（1）假设每个体检项目的服务时间是确定的，并且只有1个医生值班，每次只能为1个体检人员服务。（2）假设将体检人员的路途时间计入服务时间内。（3）假设需要体检的人员没有来源限制, 即其相互约束可忽略不计, 来自无限群体。（4）假设团队客人同时到达体检中心。（5）假设每天每个体检项目同一时刻的体检人员到达率基本相当。（6）假设体检中心工作时间从8：00开始32符号说明编号服务时间t时间排队人数t时间到达的人数dpi(t)/dt到达率1抽血A1S1(t)P1(t)2内科A2S2(t)P2(t)3外科A3S3(t)P3(t)4B超A4S4(t)P4(t)5五官科A5S5(t)P5(t)6胸透A6S6(t)P6(t)7身高体重A7S7(t)P7(t)四、模型准备1、贪心算法（Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 贪婪算法可解决的问题通常大部分都有如下的特性: （1） 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。 （2） 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 （3） 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 （4） 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。 （5） 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 （6） 最后，目标函数给出解的值。 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。 贪心解的确不错，可惜不一定是最优解。2、数值微分(numerical differentiation)：根据函数在一些离散点的函数值，推算它在某点的导数或高阶导数的近似值的方法。通常用差商代替微商，或者用一个能够近似代替该函数的较简单的可微函数（如多项式或样条函数等）的相应导数作为能求导数的近似值。例如一些常用的数值微分公式(如两点公式、三点公式等)就是在等距步长情形下用插值多项式的导数作为近似值的。此外，还可以采用待定系数法建立各阶导数的数值微分公式，并且用外推技术来提高所求近似值的精确度。当函数可微性不太好时，利用样条插值进行数值微分要比多项式插值更适宜。如果离散点上的数据有不容忽视的随机误差，应该用曲线拟合代替函数插值，然后用拟合曲线的导数作为所求导数的近似值，这种做法可以起到减少随机误差的作用。数值微分公式还是微分方程数值解法的重要依据。当函数是以离散点列给出时，当函数的表达式过于复杂时，常用数值微分近似计算的导数。在微积分中，导数表示函数在某点上的瞬时变化率，它是平均变化率的极限；在几何上可解释为曲线的斜率；在物理上可解释为物体变化的速率。以下是导数的三种定义形式：（1）在微积分中，用差商的极限定义导数；在数值计算中返璞归真，导数取用差商（平均变化率）作为其近似值。最简单的计算数值微分的方法是用函数的差商近似函数的导数，即取极限的近似值。下面是与式（1）相应的三种差商形式的数值微分公式以及相应的截断误差。五、模型的建立我们根据体检中心的排队流程，做出如下流程图。问题一：给定某体检中心的7种体检项目所需的时间表（表一）以及各个时段的体检人数（表二），根据表一和表二中数据我们初步建立了微分方程模型，；其中，表示从0到t时刻某项检查到达的总人数，表示t时刻某项检查到达率：，即 ；为了近似的求解出， 时，则，此时的即为每隔一个小时到来体检中心做某项检查的人数，通过查阅资料得到西南医院体检中心各时段每个项目体检人数变化不大，最后我们用5天的平均数据（见表二），在用三次函数拟合出。表一 体检项目服务时间表项目抽血内科外科B超五官科胸透身高体重服务时间4min4min4min12min4min3min3min表二 各个时段体检人数表人数项目时间抽血内科外科B超五官科胸透身高体重8：009：008111151517159：0010：00151515718201810：0011：00201716815232011：0012：00171514712201714：0015：0013101058151315：0016：008772510816：0017：00555138517：0018：002240266为了确立体检人数与时间的关系，利用插值拟合，通过MATLAB软件编程（见附录1），拟合出每一个体检项目的到达率与时间的函数关系。 为使客人完成需要的全部检查的时间尽量少，我们初步建立如下微分方程模型：；利用该模型，我们可以算出在0-t时间内每一项检查项目当前的等待的人数，根据当前等待人数，我们可以确定当前所有检查项目中等待时间最短的一个，以此确定待检人员下一个体检项目。 但是，由于当前模型中的时间表示的是该体检中心工作时间内较长的一段时间，以此算出的等待的人数不能满足及时性、合理性，为了避免这一不足，我们对模型进行了进一步优化，优化的思想即把工作时间等分为若干个适当的时间段，每一时间段后计算一次当前等待人数，求出每个项目需要等待的时间，并对系统数据进行更新，计算出剩余项目中等待时间最少的体检项目，对待检人员做出合理的检查安排。优化后的模型如下：；当 0； 其他 优化后的模型可以有效地计算出在时间内到达每个项目排队的的人数，从而可以计算出当前每个项目需要等待的时间为：T= 然后，通过采用公式计算的时间，比较每个项目所需等待的时间，找出其中的最小值，进行待体检人员下个体检项目的安排。该模型避免出现在一个较长的时间段内的某一时间点以前待检人员排队等待体检服务，而在时间点以后医生等待体检人员的情况，提高医疗器械及人员的工作效率。问题二：通过查阅资料，我们设计出一组合理数据（表四），利用该组数据对上述模型进行检验。问题三：利用问题一中建立的优化后模型对团体人员进行安排。（1）团体人员在同一时刻到达体检中心，团队人员人数确定为，体检项目确定。在比较时刻体检项目的等待时间后，将第一个人员分配到当前等待时间最小的项目中。接着，对当前的体检项目的等待时间再次进行比较后，将第二个人员分配到当前等待时间最小的项目中。连续进行次比较后，将全团队的人员分配到待检项目中。注意，这个分配的过程是在到达的时刻，一下完成的。（2）将团队中的人员进行第一次分配后，按照问题一中建立的模型，对团队中的每个人员进行检查顺序的进一步分配，直到完成规定的体检项目为止。六、模型的求解问题一：首先，利用MATLAB对表二中的数据进行插值拟合，得到每个体检项目的（不考虑空闲时间）（1）求得抽血项目的各项系数分别为：0.2910 -4.8192 21.6051 -10.6410可以得到到达率与时间的关系式为：（2）求得内科项目的各项系数分别为：0.2029 -3.2580 13.4821 -0.2735可以得到到达率与时间的关系式为：（3）求得外科科项目的各项系数分别为:0.2061 -3.1724 12.6796 0.6358可以得到到达率与时间的关系式为：同理可得，通过插值拟合（图形见附录3）可以得到其他体检项目的到达率与时间的关系式为：根据上述关系式可以求出到t时刻到达的人数；而上一时段剩余的待检人数为：；上一时段检查完离开的人数为：；因此可以得到当前队列中待检人员的人数。我们已知每个体检项目的体检时间，可以得到当前时刻每个项目的等待时间：，结果如表三所示：表三 计算结果抽血内科外科B超五官科胸透身高体重现假设有一个待检人员需要检查四个项目，分别是抽血、五官科、胸透、身高体重，该人员在时刻到达体检中心。（1）利用模型计算出当前这四个项目中正在排队的人数，再计算出每个项目的等待时间，将四个项目的等待时间进行比较，找出最小值，记为,该人员前往最小值项目排队。（2）该人员在+Ai时刻将第一个项目检查完毕，求出时刻其他三个项目的等待时间，进行比较，找出最小值，记为,该人员前往当前最小值项目排队。（3）同理可找出其他两个项目的时间、,以及排队顺序、。（4）可以的到该人员做四个项目所需的最小等待时间为排队顺序是。问题二：通过查阅相关资料，我们设计某位体检人员的数据（表四）：、表四 个人体检试验数据到达时间检查项目t=2.5(即上午十点半到达)抽血 外科 B超 身高体重利用上表数据运行程序（见附录一）求解得到，该人员的体检顺序为B超、身高体重、抽血、外科，所用的等待时间分别为0分钟、0分钟、4分钟、36分钟，体检总时间为63分钟。问题三：由于采用的是问题一已经求解的模型，在这里我们省去求解的步骤。通过查阅相关资料，我们设计某个团队人员的数据（表五）：表五 团队体检试验数据团队人员数到达时间检查项目10t=2.5(即上午十点半到达)抽血 内科 胸透 身高体重利用数据运行程序（见附录二）求解得到团队体检的体检顺序和每个项目的等待时间，表六所示：表六 团队体检结果表序号体检顺序等待时间分钟体检总时间分钟1内科 身高体重 胸透 抽血0 0 3 8252身高体重 胸透 抽血 内科0 3 4 8293胸透 身高体重 抽血 内科3 3 8 8324身高体重 抽血 内科 胸透3 4 8 12375抽血 身高体重 内科 胸透4 6 8 12406内科 身高体重 胸透 抽血4 6 9 16457身高体重 胸透 内科 抽血6 9 12 20578内科 胸透 身高体重 抽血8 9 9 20569胸透 身高体重 抽血 内科 9 9 16 166010身高体重 胸透 内科 抽血9 15 16 2474经过上述计算，可以看到，当某个10人的团队前往体检中心进行四个项目体检时，团队中最短完成的体检时间为25分钟，最长的是74分钟。所以，体检中心可以在74分钟左右完成这个团队的体检任务。七、 模型评价与推广1、模型的优点：我们建立的数学模型的合理性主要体现在以下几个方面：（1）假设的合理性假设1-4确定了建立模型的整体环境，排除了突发事件对模型的影响，提高了模型建立的准确度。假设5、6对我们模型建立所需要的时间跨度和人员流动给出了定义，且是科学的、合理的，使得模型建立更合理。（2）方法的科学性本文针对不同时间段的预测，使用了可靠的科学建模方法，其间我们运用了微分方程模型。该模型分别对单个客人和团队客人的体检顺序进行排列，得出的结果相对准确。所以用这个模型求解问题也是合理的、科学的。（3）结果的合理性根据模型求出的结果，符合实际生活的情况，具有一定的参考价值。2、模型的缺点（1）由于体检中心每个项目每天的到达率与实际到达率存在一定的误差，这将导致计算出的等待时间也会出现相应的误差。（2）实际生活中各个体检项目的地点存在一定的距离，在模型中没有计算在体检过程中因故耽搁的时间。（3）对于团队体检时，所花费的最短时间与最长时间之间相差过大，在模型中没有考虑花费时间的均衡度 ，这也将影响整个模型的效果。3、模型的推广本文上述结果表明利用计算机模拟完全有能力完成对多人、多项体检项目的分析, 并做出仅需等待较短时间的最优安排; 同时兼顾提高设备利用率, 使得各项体检设备都得以发挥其最大效用。对此不仅能够定性分析, 而且作出了定量安排, 故而是切实可行的, 值得在临床实践中推广应用。尤其在医院排队挂号、就诊,战时大批量伤病员的救治排队等方面具备一定优越性, 藉此可以合理利用资源。在此基础上, 对本算法进一步优化, 可以考虑团队体检时检查不同项目如何排队, 建立以所有受检人员完成检查的总时间最短为目标函数、各体检者的等待时间最短为约束条件的非线性规划模型,探讨团体体检排队的最优方案将是下一步研究方向。八、 参考文献刘卫国，MATLAB程序设计与应用，北京：高等教育出版社，2006年。茆诗松、程依明、濮晓龙，概率论与数理统计教程，北京：高等教育出版社，2011年。姜启源、谢金星、叶俊，数学模型，北京：高等教育出版社，2011年。唐应辉、唐小我，排队论基础与分析技术M，北京：科学出版社,2006年。叶彦谦,常微分方程，上海：上海科学技术出版社，2006年。运筹学教材组，运筹学，北京：清华大学出版社，2005年附录1：x=1:8;x1=1:0.2:8;y=15 18 20 17 13 8 5 6;y1=interp1(x,y,x1,nearest);p=polyfit(x1,y1,3);y2=p(1)*x1.3+p(2)*x1.2+p(3)*x1+p(4);plot(x,y,r,x1,y2);title(待检人员到达率拟合);xlabel(时间);ylabel(到达率);legend(真实到达率,拟合后的到达率);附录2：%医院排队问题%主函数 function paidui%初始化变量 a=zeros(1,7); %定义服务时间的变量a(1)=4; %抽血时间5mina(2)=4; %内科时间5mina(3)=4; %外科时间5mina(4)=12; %B超时间15mina(5)=4; %五官时间5mina(6)=3; %胸透时间4mina(7)=3; %身高体重时间4mint=zeros(1,7); %定义7个变量存t(i)放第i样检查的当前时间s=zeros(1,7); %定义7个变量存t(i)放第i样检查的当前时间%体检的项目1：抽血 ，2：内科 ，3：外科 ，4：B超 ，5：五官科， 6：胸透， 7：身高体重。tj=1 2 3 4 5 6 7; %例如要检查抽血、内科、外科，则用tj=1 2 3表示。shun=zeros(1,length(tj);dengdai=zeros(1,length(tj);k=1;t1=3; %当前时间chang=length(tj);while(1) for kk=1:length(tj) if tj(kk)=1 s(1)=look1(t1,a(1); t(1)=s(1)*a(1); end if tj(kk)=2 s(2)=look2(t1,a(2); t(2)=s(2)*a(2); end if tj(kk)=3 s(3)=look3(t1,a(3); t(3)=s(3)*a(3); end if tj(kk)=4 s(4)=look4(t1,a(4); t(4)=s(4)*a(4); end if tj(kk)=5 s(5)=look5(t1,a(5); t(5)=s(5)*a(5); end if tj(kk)=6 s(6)=look6(t1,a(6); t(6)=s(6)*a(6); end if tj(kk)=7 s(7)=look7(t1,a(7); t(7)=s(7)*a(7); endendaa=;for j=1:length(tj) aa=aa,t(tj(j);endt2,xb=min(aa);shun(k)=tj(xb);dengdai(k)=t2;k=k+1;t1=t1+(t2+a(tj(xb)/60;tj(xb)=;if kchang break;endendfprintf(【检查顺序 %d】,shun)fprintf(n)fprintf(【等待的时间 %d】,dengdai) %函数look1 %t1时刻抽血剩余人数计算( t1(dt*60/a) s=(s+quad(matt1,i*dt,(i+1)*dt)-dt*60/a; else s=0; endend%计算t1时刻剩余的人数 tx=fix(t1/dt)*dt;if s+quad(matt1,tx,t1)(t1-tx)*60/a s=s+quad(matt1,tx,t1)-(t1-tx)*60/a;else s=0;endif s-fix(s)0.5 s=fix(s)+1;else s=fix(s);endtt=s; %函数look2%t1时刻内科剩余人数计算( t1dt*60/a s=s+quad(matt1,i*dt,(i+1)*dt)-dt*60/a; else s=0; endend%计算t1时刻剩余的人数tx=fix(t1/dt)*dt;if s+quad(matt1,tx,t1)(t1-tx)*60/a s=s+quad(matt1,tx,t1)-(t1-tx)*60/a;else s=0;endif s-fix(s)0.5 s=fix(s)+1;else s=fix(s);endtt=s; %函数look3 %t1时刻外科剩余人数计算( t1dt*60/a s=s+quad(matt1,i*dt,(i+1)*dt)-dt*60/a; else s=0; endend%计算t1时刻剩余的人数tx=fix(t1/dt)*dt;if s+quad(matt1,tx,t1)(t1-tx)*60/a s=s+quad(matt1,tx,t1)-(t1-tx)*60/a;else s=0;endif s-fix(s)0.5 s=fix(s)+1;else s=fix(s);endtt=s; %函数look4 %t1时刻B超剩余人数计算( t1dt*60/a s=s+quad(matt1,i*dt,(i+1)*dt)-dt*60/a; else s=0; endend%计算t1时刻剩余的人数tx=fix(t1/dt)*dt;if s+quad(matt1,tx,t1)(t1-tx)*60/a s=s+quad(matt1,tx,t1)-(t1-tx)*60/a;else s=0;endif s-fix(s)0.5 s=fix(s)+1;else s=fix(s);endtt=s; %函数look5%t1时刻五官科剩余人数计算( t1dt*60/a s=s+quad(matt1,i*dt,(i+1)*dt)-dt*60/a; else s=0; endend%计算t1时刻剩余的人数tx=fix(t1/dt)*dt;if s+quad(matt1,tx,t1)(t1-tx)*60/a s=s+quad(matt1,tx,t1)-(t1-tx)*60/a;else s=0;endif s-fix(s)0.5 s=fix(s)+1;else s=fix(s);endtt=s; %函数look6 %t1时刻胸透剩余人数计算( t1dt*60/a s=s+quad(matt1,i*dt,(i+1)*dt)-dt*60/a; else s=0; endend%计算t1时刻剩余的人数 tx=fix(t1/dt)*dt;if s+quad(matt1,tx,t1)(t1-tx)*60/a s=s+quad(matt1,tx,t1)-(t1-tx)*60/a;else s=0;endif s-fix(s)0.5 s=fix(s)+1;else s=fix(s);endtt=s; %函数look7 %t1时刻身高体重剩余人数计算( t1dt*60/a s=s+quad(matt1,i*dt,(i+1)*dt)-dt*60/a; else s=0; endend%计算t1时刻剩余的人数 tx=fix(t1/dt)*dt;if s+quad(matt1,tx,t1)(t1-tx)*60/a s=s+quad(matt1,tx,t1)-(t1-tx)*60/a;else s=0;endif s-fix(s)0.5 s=fix(s)+1;else s=fix(s);endtt=s;附录3附录4%医院排队问题三%团队安排逐一安排%主函数function paidui%初始化变量a=zeros(1,7);%定义服务时间的变量a(1)=4; %抽血时间5mina(2)=4; %内科时间5mina(3)=4; %外科时间5mina(4)=12; %B超时间1