-
第８卷第３期
２
０
０
９年８月
广东交通职业技术学院学报
ＪｏＵＲＮＡＬ
ｏＦ
ＧＵＡＮＧ
ＤｏＮＧ
Ｖ０１．８
Ａｕｇｕｓｔ
２００９
Ｃ
ｏＭＭＵＮＩＣＡＴＩＯＮＳ
ＰＯＬＹＴＥＣＨＮＩＣ
文章编号
：１６７１—８４９６一（２００９）０３－００８５－０４
体ｔ～－，ｇ，，、：ｒｏ
ｌ。ｌ试时间安排的研究
崔春雷
（广东交通职业技术学院，广东
广州５１０６５０）
摘要：按照教学计划安排各班学生进行体能测试，以了解学生的身体
状况。文中首先对身高与体重、立
定跳远、肺活量、握力和台阶的测试仪进行了合理的分
配使用，然后利用背包问题中的贪婪法对各个班级
的测试顺序进行了安排；按照所给出的
时间安排表可以节省学生的等待时间并减少所需的总时间段数。
关键词：优化分配；背包
问题；贪婪法
中图分类号：０１４
文献标识码：＾
‘
Ｓｔｕｄｙ
ｏｎ
ｔｈｅ
Ｔｉｍｉｎｇ
ｏｆ
ｔｈｅ
Ｐｈｙｓ
ｉｃａｌ
Ｆｉｔｎｅｓｓ
Ｔｅｓｔ
ＣＵＩ
Ｃｈｕｎ．１ｅｉ
（Ｇｕａｎｇｄｏｎｇ
Ｃｏｍｍｕｎ
ｉｃａｔｉｏｎｓ
Ｐｏｌｙｔｅｃｈｎｉｃ，Ｇｕａｎｇｚｈｏｕ
Ａｂｓｔｒａｃｔ：Ｉｎ
ａｃｃｏｒｄａｎｃｅ
ｗｉｔｈ也ｅ
< br>ｔｅａｃｈｉｎｇ
ｐｌａｎｓ．ａ
ｐｈｙｓｉｃａｌ
５
１
０６５０，Ｃｈｉｎａ）
Ｉｎｏ
ｋ
ｉｎｔｏ
ｔｈｅｉｒ
ｐｈｙｓｉｃａｌ
ｔＯ
ｔｅｓｔ
ｔｅｓｔ
ｏｆ<
/p>
ｓｔｕｄｅｎｔｓ
ｉＳ
ｃｏｎｄｕｃｔｅｄ
ｔｏ
ｃｏｎｄｉｔｉｏｎ．ｉｎ
ｔｈｉｓ
ｐａｐ
ｅｒ，ｒａｔｉｏｎａｌ
ｄｉｓｔｒｉｂｕｔｉｏｎ
ｉｓ
ｈｉｇｈｌｉｇｈｔｅｄ
ｂｙ
ｖａｒｉｏｕｓ
ｔ ｅｓｔ
ｅｑｕｉｐｍｅｎｔｓ
ａｒｒａｎｇｅｄ
ｏｒｄｅ ｒｌｙ
ｓｔｕｄｅｎｔｓ’ｗｅｉｇｈｔ
ａｎｄ
ｔｈｅ
ｈｅｉ曲ｔ，ｔｈｅｉｒ
ｌｅｎｇｔｈ
ｏｆ
ｌｏｎｇ
ｊｕｍｐ，ｌｕｎｇ
ｃａｐａｃｉｔｙ，ｇｒｉｐ
ｓｔｒｅｎｇｔｈ
ａｎｄ
ｊｕｍｐｉｎｇ
ｓｔｅｐｓ．Ｔｈｅｎ，Ｇｒｅｅｄ
< br>ａｌｇｏｒｉｔｈｍ
ｏｆ
ｔｈｅ
ｋｎａｐ
ｓａｃｋ
ｐｒｏｂｌｅｍ
ｉｓ
ａｄｏｐ
ｔｅｄ
ｔＯ
ｃｏｍｐｌｅｔｅ
ａ
ｐｈｙｓｉｃａｌ
ａｒｒａｎｇｅｍｅｎｔ
ｏｆ
ｔｈｅ
ｓｔｕｄｅｎｔｓ
ｆｒｏｍ
ｖａｒｉｅｄ
ｃｌａｓｓｅｓ．
Ｔｈｅｒｅｆｏｒｅ，ｂｅｈａｖｉｎｇ
ａｃｃｏｒｄｉｎｇ
ｔｏ
ｔｈｅ
ｔｉ
ｍｅ
ｓｃｈｅｄｕｌｅ
ｏｆｆｅｒｅｄ，ｔｈｅ
ｓｔｕｄｅｎｔｓ
ｃｏｕｌｄ
ｓａｖｅ
ｔｈｅｉ
ｒ
ｔｉｍｅ
ｗｈｉｌｅ
ｗａｉｔｉｎｇ
ａｎｄ
ｔｈｅ
ｗｈｏｌｅ
ｐｅｒｉｏｄ
ｏｆｔｈｅ
Ｋｅｙ
ｔｉ
ｍｅ
ｎｅｅｄｅｄ
ｗｏｕｌｄ
ｂｅ
ｒｅｄｕｃｅｄ．
ｗｏｒｄｓ：ｏｐｔｉｍａｌ
ｄｉ
ｓｐａｍｈｉｎｇ；ｄｎａｐｓａｃｋ
ｐｒｏｂｌｅｍ；ｇｒｅｅｄ
ａｌｇｏｒｉｔｈｍ
作为广东交通职业技术学院数学建模指导教
师，笔者指导的参赛队获得了２００７年全国大学生
数学建模比赛乙组全国一等奖。
下面就２００７年全
国大学生数学建模Ｄ题的解题思路给予论述。
某校按照教学计划安排各班学生进行体能测
试，以了解学生的身体状况。测试包括身高
与体
重、立定跳远、肺活量、握力和台阶试验共５个
项目，均由
电子仪器自动测量、记录并保存信
息。该校引进身高与体重测量仪器３台．立定跳
远、肺活量测量仪器各ｌ台。握力和台阶试验测
量仪器各２台。身高与
体重、立定跳远、肺活量、
握力４个项目每台仪器每个学生的平均测试（包
括学生的转换）时间分别为１０、２０、２０、１５
台阶试验每台仪器一次测
试５个学生。需要２１０
ｓ，
表１参加体能测试的各班人数
班号
ｌ
２
３
４
５
６
７
８
９
１０
１ｌ
１２
１３
人数
４１
４５
４４
４４
２６<
/p>
班号
１５
１６
１
７
１８
１９
２０
２ｌ
２２
２３
２４
< br>２５
２６
２７
２８
人数
４５
４４
２０
３０
３９
３５
３８
３８
２８
２５
３０
３６
２０
２４
班号
２９
３０
３１
３２
３３
３４
３５
３６
３７
３８
３９
４０
４ｌ
人数
３２
３３
４ｌ
３３
５ｌ<
/p>
３９
２０
２０
班
号
４３
人数
３７
５０
５０
４２
４３
< br>４ｌ
４４
４５
４６
４７
４８
４９
５０
５ｌ
５２
５３
５４
５５
５６
４４
４２
２０
２０
３８
３７
２５
４５
４５
４２
４５
４２
１９
３９
７５
１７
１７
４４
３７
３８
３９
４２
４０
ｓ。
１４<
/p>
４２
每个学生测试每个项目前要录入个人信息．
即
学号，平均需时５
ｓ。仪器在每个学生测量完毕
收稿日期：２００９－０
１．０６
作者简介：崔春雷（１９７８．），男，助教，硕士
研
究方向：通信技术与数学建模
后学号将自动后移一位。于是如果前后测试的学
万方数据
广东交通职业技术学院学报
第８卷
生学号相连，就可以省去录入时间，而同一班学
生的学号是相连的。学校安排每
天的测试时间为
８：００—１２：１０‘ｊ
１３：３０一１６：
４５两个时间段。５项测试
都伍最多容纳１５０个学生的小型场所进行。测试
项目没有固定的先后顺序。参加体能测试的各班
人数见表ｌ。
１问题提出
学校要求同一班的所有学生在同一时间段内
完成所有项目的测试．并且在整个测试所需时间
段数最少的条件下．尽量节省学生的等
待时间。
最后，请学生对学校以后的体能测试就以下方面
提出建
议，并说明理由：如引进各项测量仪器的
数量；测试场所的人员容量；一个班的学生是否
需要分成几个组进行测试等。
２符号说明
设备Ａ：肺活量测量仪器：
设备Ｂ：立定跳远测量仪器：
设备
Ｃ：握力测量仪器：
设备Ｄ：身高与体重测量仪器：
设备Ｅ：台
阶实验测量仪器。
瓦：测量肺活量一次用时２０
Ｓ；
％：测量立定跳远一次用时２０
ｓ；
％：测量握力
仪器一次用时１５
ｓ；
％：测量身高与体重一次用时１０
Ｓ；
％：测量台阶实验一次用时２１０
ｓ；<
/p>
（ｉ＝１，２，３，…５６）。
∑∑ｘ盯）＝２
< br>０３６．／２
ｉ
３
ＰＡ、ＰＢ、
Ｐｃ、ＰＤ、ＰＥ分别是设备Ａ、Ｂ、Ｃ、
Ｄ、Ｅ的处理能力。
ｘ，ｑ）：第ｉ个班的学号为鳓号的学生；
死：表示第ｉ个班进行测试所需要的时间：<
/p>
Ｍ：表示第ｉ个班的总人数。
３模型建立、求解与数据分析
根据设备Ａ、Ｂ、Ｃ、Ｄ、Ｅ的处理能力的不
问。可以将设备Ｅ单独作
为一个测试模块，而其
它４项作为一个模块采用学号相连的学生排队的
< br>循环模式进行测量。假如有２０个学号相连的学
万方数据
生，在如图１所示的第一阶段前１０名同学进行Ａ．Ｄ
项目的测试．后１０名进行项目Ｅ
的测试。此时：
双ｌＡ—Ｄ）段用时：孔ｌＡ—Ｄ户（５＋％卜９７≯２０５
Ｓ，
而孔１，Ｅ）用时为：及ｌ，Ｅ）＝ＴＥ＋５＝２１５
ｓ
所以ｒ１段用时：Ｔ１＝Ｔ（１，Ｅ）＝２１５
ｓ<
/p>
做完丁ｌ段后将ｑ（１）、Ｘ（２）、……Ｘ（１０））与何
（１
１）、Ｘ（１２）、……Ｘ（２０））调换，如图２所示。即调
换所做模块。
图２第二阶段测试方案
与ｒｌ段计算同理可得７２＝Ｔ１＝２１５
Ｓ。
结论一：小组中没有测试间断点时２０人一
组的总用时Ｔ＝Ｔ１＋死＝４３０
ｓ。
３．１测试间断点的定义
测试间断点是指测试中某个学生的学号和其
即将测试的那台仪器
所记录的上一个学生的学号
不是顺序相连的情况，此时就需要增加额外的５
Ｓ
的学号录入时间。
由于题中给出的任何一个班的人
数都大于１０
人．因此一个小组中不可能出现两个或两个以上
的
测试间断点。
利用前面采取每组１０人、２组同时进行的方
案．
对各班进行人数搭配。搭配方法以几个班人
数是２０的倍数和零散的无法结合成２０整倍
数的班
Ｘｉ：表示第ｉ个班；