2007高教社杯全国大学生数学建模竞赛D题评阅要点

sclgzp

2007高教社杯全国大学生数学建模竞赛D题评阅要点

[说明]本要点仅供参考，各赛区评阅组应根据对题目的理解及学生的解答，自主地进行评阅。

这个题目的初稿是某高校一位同学提供的，反映了他们学校一次体能测试的实际情况，题目加工时除对各班学生人数做了一些改动外其他数据均保持原状。
若将该题目抽象为一般的数学模型，会涉及装箱问题及工件在机器上加工的排序问题等，超出了学生掌握的知识，我们只要求学生针对这个具体问题进行分析和求解（一般是可行的近似解或启发式解），大致有以下几部分内容。

一．问题分析、假设与建模

1. 五个测试项目（体重、立定跳远、肺活量、握力和台阶试验）分别记作i=1,2,3,4,5，各项目仪器一次可测试的学生数量为ni=3，1，1，2，10，各项目仪器一次测试的平均时间为ti=10，20，20，15，210（秒）。

2. 同一班学生的学号相连，按学号顺序测试每人可节省5秒录入时间，故设一个班集体测试。已知第j班（附表中班号）学生人数为xj，j=1,2,…,56,可计算j班i项的测试时间tij=[xj/ni]+´ ti+5（秒，[]+为向上取整，5为一个班测试开始的录入时间）。5项测试在容量为150人的小型场所进行，设每个班进入场所后全部测试完毕方退出，且忽略测试项目间的转换时间。

3. 根据学校安排的测试时间（8：00－12：10与13：30－16：45），设测试时段的长度（秒）为 Tk=15000 (k为奇数), 11700 (k为偶数)，k=1,2,……。

4. 问题归结为：将tij (i=1,2,3,4,5，j=1,2,…,56) 排入T1, T2, …, TK，使K最少，且全体学生的等待时间尽量少。约束条件：同一j、不同i的tij不得在相同时刻安排；同一i在相同时刻不得安排两个及两个以上的tij；同一j、所有i的tij需安排在同一时段Tk内；任何时刻在测试场所的总人数不超过150。

注：j班学生的等待时间cj可定义为该班退出与进入测试场所的时刻之差（包括该班的测试时间，这个时间是常数）,全体学生的等待时间为xjcj对j求和。

l
要求论文中含有（最好指出）一.4中的内容，但不一定给严格的数学表达式。

sclgzp

二．算法

不要求最优解法，只需给出较好的启发式算法。一个参考算法的步骤如下：

1.
计算一个学生各项测试的平均时间ti/ ni=3.3, 20, 20, 7.5, 21，按其大小排列为i=5,3,2,4,1，i按此顺序安排；按各班人数从多到少排序，重编班号为j=1,2,…,56, 放入集合R，j按此顺序安排，每班设进入和退出测试场所时刻tin和tout。

2.
安排时段Tk（初始k=1）,用数组S记录已安排班级各项测试的开始及结束时刻，设当前时刻t（初始为0），当前测试场所剩余容量c（初始为150），j为R中的最小编号（初始为1）。

3.
在R中按照 ≥j的顺序寻找容量≤c的班，若有，取出最小的j和xj,tij, 在一.4给出的约束下以t为tin，按照i的顺序尽量向前安排tij，以全部测试结束时刻为tout，检查是否tout≤Tk，转4；若没有，找到尚在测试场所中最早退出班的tout作为新的t，用150减去此时在测试场所中班级人数和作为新的c , j取R中的最小编号，转3。

4.
若tout≤Tk, 将j班各项测试的开始及结束时刻记入S，c减去xj作为新的c ,R中去掉j，令R中大于j的最小编号为新的j，转3；若tout>Tk, 检查j是否在R中编号最大，若是，安排时段Tk+1，转2；若不是，令R中大于j的最小编号为新的j，转3。

5.
按2，3，4执行直至R为空，结束。

三．结果

应用上述算法4个时段可将全部测试安排完毕，每个时段全部项目结束后的剩余时间约为760秒（即使将一.2 tij的计算再加5秒也可以排下）；全体学生的等待时间约为7×106秒（包括测试时间），平均每个学生的等待时间约1小时。

要求用清晰、直观的图表形式给出（注意要便于使用）：

sclgzp

1）为学校工作人员使用，提供按照时段和测试项目划分的各班测试的开始和结束时刻，除表格数据外，下面的图（称甘特图）是一种直观的表达形式。

2）为学生使用，提供各班各项测试的开始和结束时刻，特别是进入及退出测试场所的时刻。

四．对学校的建议

属于进一步的发挥，如：引进测量仪器的数量使一个学生各项测试的时间尽量均衡；测试场所的人员容量加大对计划的影响（如计算取消容量限制可增加多少学生测试）；一个班集体测试会导致某些仪器（如台阶试验）能力的浪费，将一个班的学生分组测试（如各班台阶试验不足10人的合并）可能更有效；人数太多的班拆成两个班可能更便于安排。

sclgzp

注：此图仅为例子，非标准答案。图中数字为班的编号，相邻两班用不同高度仅是为了区别。

srzwmlzx

基本思路：
1、每次进场20人（学号相连），其中10人做台阶试验，另10人做其余四项测试，然后相互交换测试项目。如不多消耗录入信息时间则420秒（台阶试验与另四项测试各210秒）可完成该批20人的所有项目测试。
2、如果20人中出现两个班级的学生，或某个班级1号学生带头进场，则可能多消耗5或10秒录入时间。
3、编排各班进场顺序，应尽可能减少出现两个班级的学生同批（20人）进场测试的情况。
4、编排得当，每个上午（15000秒）可测试约700人或680人，3个上午可确保完成所有2036名学生的体能测试。
以上做法不对吗？请各位指点。

[ 本帖最后由 srzwmlzx 于 2007-9-30 19:15 编辑 ]

problems1978

等待时间是一个重要的数据，没看到确定的结果！
在测试场外的学生的等待时间计算在内吗，怎么计算？