体能测试时间安排优化模型

...wd......wd......wd...体能测试时间安排优化模型摘要本文讨论了一类时间表优化问题。首先.我们根据机器测试时间和台数求得所需总时间段数的下届为4。在同一个班级人数不进行分组的前提下.将56个班级分成19个小组.计算出每个小组测试完所有工程所需的时间。然后建设了0-1规划模型.将这19个小组的时间段放入每天的两个测试时间段内.使得全部放完这19个小组的时段所需要的总测试时间段数最少.并求得最少测试时间段数恰好为下届4段。其次.为了节省学生等待时间.我们将每个班级人数进展分组.每组为20人.共分成103组。由于这20人最多来自两个不同的班级.我们求得完成20人的时间只可能为425秒、430秒、435秒这三种情况。这样将原来问题转化为假设何用最少时间段数放入102个435秒。通过求解得到的时间段数为4段..等待时间最长的同学仅需等待2.6分钟.从而说明了分组的必要。最后.通过给出了每项测试的人均时间应该相等的结论.用来配置机器台数.并讨论了场地容量对所需时段和等待时间的影响。关键词：等待时间时间段数时间等级分组问题重述某校按照教学方案安排各班学生进展体能测试.以了解学生的身体状况。测试包括身高与体重、立定跳远、肺活量、握力和台阶试验共5个工程.均由电子仪器自动测量、记录并保存信息。该校引进身高与体重测量仪器3台.立定跳远、肺活量测量仪器各1台.握力和台阶试验测量仪器各2台。身高与体重、立定跳远、肺活量、握力4个工程每台仪器每个学生的平均测试〔包括学生的转换〕时间分别为10秒、20秒、20秒、15秒.台阶试验每台仪器一次测试5个学生.需要3分30秒。每个学生测试每个工程前要录入个人信息.即学号.平均需时5秒。仪器在每个学生测量完毕后学号将自动后移一位.于是如果前后测试的学生学号相连.就可以省去录入时间.而同一班学生的学号是相连的。学校安排每天的测试时间为8：00－12：10与13：30－16：45两个时间段。5项测试都在最多容纳150个学生的小型场所进展.测试工程没有固定的先后顺序。参加体能测试的各班人数见附表。学校要求同一班的所有学生在同一时间段内完成所有工程的测试.并且在整个测试所需时间段数最少的条件下.尽量节省学生的等待时间。请你用数学符号和语言表述各班测试时间安排问题.给出该数学问题的算法.尽量用清晰、直观的图表形式为学校工作人员及各班学生表示出测试时间的安排方案.并且说明该方案假设何满足学校的上述要求和条件。最后.请对学校以后的体能测试就以下方面提出建议.并说明理由：如引进各项测量仪器的数量；测试场所的人员容量；一个班的学生是否需要分成几个组进展测试等。附表参加体能测试的各班人数班号123456789101112131415人数414544442644422020383725454545班号161718192021222324252627282930人数442030393538382825303620243233班号313233343536373839404142434445人数413351392020443738394240375050班号4647484950515253545556人数4243414245421939751717二、问题分析首先.我们在不考虑将一个班级的学生分成几个小组的情况下.求解最小的时间段数和学生等待时间。通过对机器台数、每个工程测试时间和场地容量等因素的分析计算.我们将所有的56个班级人数划分成19个小组.其中最后一个小组只有2个班级.其余小组的班级数量均为3。并且.每个小组内的班级人数对比接近.这样可以减少等待时间。我们算出每个小组测试所需要的最少时间.然后将19个小组的时间段进展合理组合.以便得到最少的时间段数能包含这所有的19个时间段。其次.在保证时间段数最少的情况下.假设我们将同一班级人数进展合理的分组.按照我们定义的等待时间.没有进入测试场所的同学不算是等待.这样可较大程度上节约学生的等待时间.从而说明分组是必要的。模型假设和符号约定忽略人员进入和离开测试场地所用时间；假设学生等待时间指该生进入测试场地后开场的等待时间.不考虑其在未进入测试场地之前的时间；把身高与体重、立定跳远、肺活量、握力、台阶实验测试分别称为第一、二、三、四、五项测试；五个测试工程没有先后顺序；任何班级的学生做完所有测试即可离开场地；——第轮测试所花费的时间；——第个班级的人数。模型的建设与求解由于56个班级的总人数为2036.假设每台机器不停顿工作.所有人完成第一项测试至少需要2036×10÷3+56×5=7066.67〔s〕。同理可得所有人完成第二、三、四、五项测试至少需要的时间分别为41000、41000、15550、43036秒。那么.至少需要43036秒才能让所有人完成全部的测试工程。由于时间段长一次为15000秒、11700秒.因此至少需要4个时间段才能完成所有人的测试工程.即时间段的下届为4段。在不对单个班级进展分组的前提下.由于第五项每次可以测5名学生.且有两台机器.则对不同班级的总人数.可得班级测试完第五项所需时间分布表：表1班级总人数〔单位：人〕测试完台阶实验所需时间〔单位：秒〕1～10215112042521～3063531～4084341～50105551～60126561～70147571～801685当人数多余80时.可以依次类推班级人数为n时测试台阶实验所需时间计算公式为：t=+5定义：在只进展第五项测试时.把所有人数可能不同但测试完第五项所需时间一样的班级称为一个时间等级。例如：班级人数为35和40的两个班级分别做完第五项测试所用时间均为845秒.那么按照.这两个班级为同一时间等级。命题1：假设同一班级的人数不在进展分组.假设每次同时进入测试场地的班级数为3.且每个班级的人数不小于17人时.那么有：同时进入场地的3个班级全部完成第二项、第三项、第五项测试所需时间与这3个班级完成所有五项测试所需时间一样。证明：假设同时入场的班级分别为、、.其人数分别为、、。现让这三个班级分别去做第二、三、五项测试.这三个班级都已经完成各自的测试称为第一轮；第一轮测试完成后.让班去做第三项测试.让班去做第五项测试.让班去做第二项测试.这三个班级都已经完成各自的测试称为第二轮；第二轮完毕后.依次类推.让班去做第五项测试.让班去做第二项测试.让班去做第三项测试.这三个班级都已经完成各自的测试称为第三轮。如表2所示：表2第二项测试第三项测试第五项测试第一轮第二轮第三轮在第一轮中.班的第一个学生在做完第二项测试后.该同学完全可以利用等待该班第二位同学的第二项测试的时间去进展第一项测试〔共需要10+5秒〕.而当他测试完第二项时.班第二位同学依然在进展第二项测试.而此时班的第一个同学再去做第四项测试.由于班的人数不小于17.因此班还有局部同学尚未完成第二项测试。班的第二个同学完全按照该班第一个同学的路线进展.以此类推。那么该班级除了后两位同学.其余均可以在班全部测完第二项之前.也完成第一、四项的测试。倒数后两位可以在第二轮开场.即进展第三项测试时.离开班队列去做完第一、四项测试.然后回到对列继续等待第三项测试。由于第三项测试的机器为三台.第四项测试的机器为二台.完全足够.并且在第一轮中和班分别做第二、三项的时间均为20秒每人.班的同学的路线与班相似。对于班也可以在第一、二、三轮测试的间隙完成第一、四项的测试。另外.第二、三项测试需要20秒.而第五项测试序言210秒.但可以同时测试5人且有2台机器.那么人均耗时约为21秒。并有以上的命题讨论我们知道假设三个班级的人数相差不大.则对比节约时间.因此我讲56个班级分组.每组的班级同时入场。表3组号班级编号对应的人数第1组〔525556〕〔191717〕第2组〔273536〕〔202020〕第3组〔8917〕〔202020〕第4组〔122428〕〔252524〕第5组〔25235〕〔302826〕第6组〔322918〕〔333230〕第7组〔262030〕〔363533〕第8组〔113843〕〔373737〕第9组〔212239〕〔383838〕第10组〔405310〕〔393838〕第11组〔421934〕〔403939〕第12组(13148)(414141)第13组〔464951〕〔424242〕第14组〔47741〕〔434242〕第15组〔61637〕〔444444〕第16组〔4350〕〔444445〕第17组〔131415〕〔454545〕第18组〔24544〕〔455050〕第19组〔5433〕〔7551〕按照表3.可以分一下两种情况讨论：情况一：假设该组中的三个班级人数为、、均处于同一时间等级.则完成第一轮测试所需时间为：=210+5〔这里「」是上取整数函数〕；这是因为假设班级人数、、处于同一时间等级.则显然有：20×210×；再加上第一位同学录入学号的5秒.则完成第一轮总共所需时间为：=210+5同理可得第二、三轮时间分别为=210+5和=210+5;则完成三轮测试所需的时间为：=++=「」+15〔1〕有上面的分组我们可以知道除了第6、19两组.其他分组均出在同一时间等级.可按照〔1〕式计算完成时间〔结果见表5〕情况二：假设三个班级不全处于同一时间等级.则由于人数不同有多种情况出现.具体情况时具体计算这里不给出计算公式。表3中有两组的班级不同一时间等级.这两组为第6组和第19组。现在分别计算器完成时间：表4第二项测试第三项测试第五项测试每轮测试所需要的时间〔秒〕班级编号〔人数〕所需时间〔秒〕班级编号〔人〕所需时间〔秒〕班级编号〔人〕所需时间〔秒〕第一轮32〔33〕66529(32)64518(30)635665第二轮18〔30〕60532〔33〕66529〔32〕845845第三轮29〔32〕64518〔30〕60532(33)845845由表4得完成三轮测试所需的总时间T=665+845+845=2355秒。同理可得第19组完成三轮测试所需的总时间T=4695秒。综合上面两种情况.我们得到所有组合做完全部测试的时间如下表所示：表5组号班级编号对应的人数测试所需时间第1组〔525556〕〔191717〕1275第2组〔273536〕〔202020〕1275第3组〔8917〕〔202020〕1275第4组〔122428〕〔252524〕1905第5组〔25235〕〔302826〕1905第6组〔322918〕〔333230〕2355第7组〔262030〕〔363533〕2535第8组〔113843〕〔373737〕2535第9组〔212239〕〔383838〕2535第10组〔405310〕〔393838〕2535第11组〔421934〕〔403939〕2535第12组(13148)(414141)3165第13组〔464951〕〔424242〕3165第14组〔47741〕〔434242〕3165第15组〔61637〕〔444444〕3165第16组〔4350〕〔444445〕3165第17组〔131415〕〔454545〕3165第18组〔24544〕〔455050〕3165第19组〔5433〕〔7551〕4695现在问题转化为：将上述19个时间按照某种组合方式全部填入每天的两个时间段.从而使得所需的总时间段数最少。设表示所需的时间段总数.表示表5中第个组合所需时间.表示第个时间段长度.其中=1.2....19；=1.2.....显然有：=.进一步假设0-1变量:=.其中=1.2....19；=1.2.....即得到0-1规划模型一：min,=1;=1,2,...,19;;=1.2.....上述模型中：第一个约束表示每个组能且只能安排在某一时段;第二个约束表示安排进任一时段的所有组的测试总时间必不大于该时段长度。利用LINGO编程解得结果如下：表6组号班级号班级人数测试时间安排第一天上午第1组〔525556〕〔191717〕8:00:00～8:21:15第2组〔273536〕〔202020〕8:21:15～8:42:30第7组〔262020〕〔363533〕8:42:30～9:24:45第8组〔113843〕9373737)9:24:45～10:07:00第9组(212239)(383838)10:07:00～10:49:15第19组〔5433〕〔7551〕10:49:15～12:07:30下午第5组〔25235〕〔302826〕13:30:00～14:01:45第15组〔61637〕〔444444〕14:01:45～14:54:30第16组〔4350〕〔444445〕14:54:30～15:47:15第17组(131415)(454545)15:47:15～16:40:00第二天上午第3组(8917)(202020)8:00:00～8:21:15第4组〔122428〕〔252524〕8:21:15～8:53:00第10组〔405310〕〔393838〕8:53:00～9:35:15第11组〔421934〕〔403939〕9:35:15～10:17:30第13组〔464951〕〔424242〕10:17:30～11:10:15第14组(47741)〔434242〕11:10:15～12:03:00下午第6组〔322918〕〔333230〕13:30:00～14:2109:15第12组〔13148〕〔414141〕14:009:15～15:02:00第18组〔24544〕〔455050〕15:02:00～15:54:45由结果可知整个测试所需时间段数最少为4段。由于已经知道所需时段的下限也是4.故以上结果为最优方案。对于以上的方案.基于假设〔2〕和〔5〕.每个组最后一名离开的同学〔在该组中等待时间最长〕等待时间完全由分组情况决定.与该组进入次序无关。因为最后一名同学的等待时间即为该组所需时间减去275秒〔每个同学完成五项测试的时间〕。则由表5可得.每组等待时间最长的同学的等待时间。第一组最后一名同学总等待时间为1275-275=1000秒；第19组最后一名同学总等待时间为4420秒〔约1.23个小时〕。等待时间较长.需要改良.当班级人数较多时.假设不对同一个班级的学生分组会使得学生的等待时间较长。为了减少学生的等待时间.可以将同一个班级人数分组进入场地进展测试。现在考虑对同一班级学生进展分组的情况。命题2：假设每次同时进入场地的人数为20人.且这20人学好顺序相连.则完成这20人全部的5项测试最少需要425秒.且可以到达425秒。证明：首先证明至少425秒。因为即使不考虑其他4项.只做完第五个工程.这20人就需要425秒〔见表1〕。其次证明可以到达425秒。我们假设这20人的学号次序为从1到20.则让学号为1到5的学生测试第一台台阶试验机.与此同时让学号为6到10的学生测试立定跳远.让学号为11到15的同学测试第二台台阶实验机.让学号为16到20的同学测试肺活量。如以以以下列图所示：立定跳远肺活量台阶实验台阶实验学号学号学号学号6161117172128183139194141020515这样16～20号与6～10号同时测完〔都用了105秒〕。两个交换测试工程每次同时测完(都用了105秒).这两轮共用了210秒.而测试台阶的两个组由于要用215秒.因此第二轮进展太极实验测试的组还在继续测试。过程如以以以下列图所示：立定跳远肺活量台阶实验台阶实验学号学号学号学号16611117721218831319941420105156～10.16～20这两组在等待了5秒后有同时去做台阶实验测试.由于学号刚好能衔接.不需要输入学号时间。做完台阶实验测试的两组去做剩余项的测试。过程如以以以下列图所示：立定跳远肺活量台阶实验台阶实验学号学号学号学号1116162127173138184149195151020这样