摘要：排队是日常生活中常见的现象。本文讨论的是如何安排受检人员的体检顺序，以提高设备利用率、降低受检人员等待时间的问题，针对个人和团体建立了体检排队系统的优化模型，实现了以体检时间、路途时间及排队时间之和最小为目标函数的非线性规划模型，即排队动力学模型。将对原目标函数的求解转化为求最优问题，求最优解，从而运用图论原理、VC6.0软件编程对个人的体检顺序做出定性分析和定量安排，并设计数据予以检验。在此基础上，将团体的各队员全部分开,建立各体检者的等待时间最短为约束条件的非线性规划模型，求得团体时间最短，解决体检排队问题。 关键词：排队动力学模型；排队论；最优解；图论原理；VC++6.0；
一、问题重述
在某城市的体检中心每天有许多人前去体检，全部体检项目包括：抽血、内科、外科、B超、五官科、胸透、身高、体重、…等等。每个人的体检项目可能各不相同，假设每个体检项目的服务时间是确定的，并且只有1个医生值班，每次只能为1个客户服务。为提高设备利用率、降低客人的等待时间，中心请你帮助完成如下任务： 火地人1.请你为某个新来的客人安排他的体检顺序，使其完成需要的全部检查的时间尽量少（在各个体检项目处都可能有人排队等待）；
2.设计1组数据来验证上述结论；
3.接待团体客人时，如何安排每个人的体检顺序，使得体检中心能尽快完成任务，设计1组数据来验证该结论。
二、问题分析
病人在就诊检查时，由于医院的医疗器件、医生人数的限制，或是由于病人就诊检查规则的不合理，会导致时间的浪费。为了节约时间并保证体检有序的进行，那么选择一个合适的检查科目是非常有必要的。
问题一：假设客人到来之前就有人在排队等候就诊，那么新来的客人则需选择排队时间最少的科室，某科室排队的队长，科室就诊的速度为，那么第一次所需等候的时间，选择最小的值记为，确定体检科室，检查完毕后，继续选择下一个科室； 中途科室与科室之间有一定距离，需要的时间为t，在选择下一个科室时，选择出的最小值，记为；
在经历k-1次科室的变换后，选择最后一个科室进行体检，所需的时间记为xjw，结束体检，则该客人体检所需的总时间为，即为，，……，之和。
张德英问题二：根据问题一提供的排队优化方法，输入k,i,t,,,……，的值，验证问题一的正确性。
问题三：因为为团体客人并且每个人的体检项目可能各不相同，所以团体客人是同时到达体检地点，要求体检中心能尽快完成任务，所以需要团体检查时间最少，而团体检查时间最少，则是团体之中最后一位客人被检查完毕，即团体时间最少。在团体之中，各个成员按照问题一的解决方法，即可得到各位客人的最短体检时间，由于各位客人是同时到达，各客人中个人最短时间中的最大值即为团体体检的最短时间。
三、模型假设
1.假设一开始就站在了最优选择的科室的队列之中；
2.省略其他医院体检流程，直接进入排队体检项目；
3.在体检室旁边具有显示各个科室排队长度及就诊速度的显示仪器；
4.从一个科室到另一个科室的时间一定；
5.在同一次做出选择的时候，没有出现两个最优科室；
阮筠庭插画6.按先到先服务的原则进行体检，不考虑插队和优先等特殊情况；
7.在接待团队客人，如果多个客人选择同一科室，增加的队列长队忽略不计。
四、符号说明
对抽血、内科、外科、B超、五官科、胸透、身高、体重等科室分别用1，2，3……，n表示，其参数变量如下：
：第i个科室在就诊前的队长（i=1,2,3……n）
：第i个科室的平均就诊速度（i=1,2,3……n）
：第k次变换科室后，在第i个科室的等待及就诊时间（k=0,1,2……；i=1,2,3……n）
t：从一个科室到另一个科室所需的时间
：第k次变换科室后，科室i的新增队长（k=0,1,2……；i=1,2,3……n）
：就诊完所需的总时间
五、模型的建立与求解
该模型为排队优化模型。运用、排队论构建体检排队系统的优化模型，旨在提高设备利用率、减少受检人员等待时间，运用图论知识、元胞自动机算法，建立以体检时间、路途时间及排队时间之和最小为目标函数的排队优化模型。
5.1 问题一模型的建立与求解
在第零次变换科室，即第一次选择科室时，如果去第i科室所需的时间，在，，……，之中，选择值最小的科室就诊，所用的最短时间记为，此科室检查完毕后，选择另一个科室体检;
第一次换科室时，各个科室所需的等候时间
,
选择中的最小值所在科室体检，所用时间记为，此科室检查完毕后，选择另一个科室体检;
同理可得到：
第k-2次换科室时，剩余科室所需的等候时间可以表示为：,从表示的两个值中，选择最小值的所在科室体检，所用时间记为，进行最后一个科室的体检。
第k-1次换科室时，最后一个科室所需的等候时间可以表示为：将最后一个科室检查的时间作为，体检结束。
因此，新顾客排队体检的总时间可表示为：
5.2问题二：
根据问题一，设计的具体数据为：附录一（问题一数据检验），C++程序见附录三。
在第零次变换科室，即第一次选择科室时，如果去1，2，3，4，5科室所需的时间分别为13，44，24，18，44，则选择值最小的科室1体检，所用的最短时间记为1t1t，即=13，此科室检查完毕后，选择另一个科室体检;
第一次换科室时，2，3，4，5科室所需的等候时间为41，13，7，41,则选择4科室体检，所用时间记为，即=7，此科室检查完毕后，选择另一个科室体检;
第二次换科室时，2，3，5科室所需的等候时间为52，16，40,则选择3科室体检，所用时间记为，即=16，此科室检查完毕后，选择另一个科室体检;
第三次换科室时，2，5科室所需的等候时间为50，38,则选择5科室体检，所用时间记为，即=38，此科室检查完毕后，直接去最后一个科室体检;
第四次换科室，即最后一个科室项目体检时，2科室所需的等候时间为14,则所用时间记为，即=14，体检结束。
因此，新顾客排队体检的总时间可表示为：
85sss
=13+7+16+38+14+（5-1）*2=96
检查顺序：
符合问题一中的结论。
5.3问题三：
接待团体客人时，使得体检中心能尽快完成任务，但是团体客人并非每个客人都到相同的科室检验，所以客人的体检项目可能各不相同。由于团体客人是同时到达，因此，团体客人里单个客人的最短时间中的最大值就是团体体检最小值。同时，在接待团队客人，如果多个客人选择同一科室，增加的队列长队忽略不计
