数字建模 2007D题评阅要点.docx

2007高教社杯全国大学生数学建模竞赛D题评阅要点说明本要点仅供参考，各赛区评阅组应根据对题目的理解及学生的解答，自主地进行评阅。这个题目的初稿是某高校一位同学提供的，反映了他们学校一次体能测试的实际情况，题目加工时除对各班学生人数做了一些改动外其他数据均保持原状。若将该题目抽象为一般的数学模型，会涉及装箱问题及工件在机器上加工的排序问题等，超出了学生掌握的知识，我们只要求学生针对这个具体问题进行分析和求解（一般是可行的近似解或启发式解），大致有以下几部分内容。一.问题分析、假设与建模1 .五个测试项目（体重、立定跳远、肺活量、握力和台阶试验）分别记作i=12345,各项目仪器一次可测试的学生数量为尸3,1,1,2,10,各项目仪器一次测试的平均时间为后10,20,20,15,210（秒）。2 .同一班学生的学号相连，按学号顺序测试每人可节省5秒录入时间，故设一个班集体测试。已知第j班（附表中班号）学生人数为物/=1,2,56,可计算j班i项的测试时间q=芍/M+行+5（秒，+为向上取整，5为一个班测试开始的录入时间）。5项测试在容量为150人的小型场所进行，设每个班进入场所后全部测试完毕方退出，且忽略测试项目间的转换时间。3 .根据学校安排的测试时间（8：0012：10与13：3016:45）,设测试时段的长度（秒）为/=15000（无为奇数）,1170O（A为偶数）,仁1,2,。4 .问题归结为：将用（i=l,2,3,4,5,/=1,2,56）排入Ti,及,，7k,使K最少，且全体学生的等待时间尽量少。约束条件：同一八不同，的加不得在相同时刻安排；同一i在相同时刻不得安排两个及两个以上的研同一人所有i的6需安排在同一时段入内；任何时刻在测试场所的总人数不超过150o注班学生的等待时间O可定义为该班退出与进入测试场所的时刻之差（包括该班的测试时间，这个时间是常数），全体学生的等待时间为为行对/求和。要求论文中含有（最好指出）一.4中的内容，但不一定给严格的数学表达式。二,算法不要求最优解法，只需给出较好的启发式算法。一个参考算法的步骤如下：1.计算一个学生各项测试的平均时间却尸3.3,20,20,7.5,21,按其大小排列为i=5,3,2,4,l,i按此顺序安排；按各班人数从多到少排序，重编班号为尸1,2,56,放入集合R,/按此顺序安排，每班设进入和退出测试场所时刻力和心2 .安排时段A（初始上1）,用数组S记录已安排班级各项测试的开始及结束时刻，设当前时刻，（初始为0）,当前测试场所剩余容量C（初始为150）,/为R中的最小编号（初始为1）O3 .在R中按照3的顺序寻找容量c的班，若有，取出最小的/和为,即在一.4给出的约束下以，为力，按照i的顺序尽量向前安排防，以全部测试结束时刻为加检查是否加ETL转4；若没有，找到尚在测试场所中最早退出班的3,作为新的用150减去此时在测试场所中班级人数和作为新的j/取R中的最小编号，转3。4 .若加ETi,将/班各项测试的开始及结束时刻记入S,c减去为作为新的c,R中去掉令R中大于/的最小编号为新的转3；若toui>Tk,检查）是否在R中编号最大，若是，安排时段7,转2；若不是，令R中大于/的最小编号为新的力转3。5 .按2,3,4执行直至R为空，结束。三.结果应用上述算法4个时段可将全部测试安排完毕，每个时段全部项目结束后的剩余时间约为760秒（即使将一.2场的计算再加5秒也可以排下）；全体学生的等待时间约为7x106秒（包括测试时间），平均每个学生的等待时间约1小时。要求用清晰、直观的图表形式给出（注意要便于使用）：1）为学校工作人员使用，提供按照时段和测试项目划分的各班测试的开始和结束时刻，除表格数据外，下面的图（称甘特图）是一种直观的表达形式。2）为学生使用，提供各班各项测试的开始和结束时刻，特别是进入及退出测试场所的时刻。四.对学校的建议属于进一步的发挥，如：引进测量仪器的数量使一个学生各项测试的时间尽量均衡;测试场所的人员容量加大对计划的影响（如计算取消容量限制可增加多少学生测试）；一个班集体测试会导致某些仪器（如台阶试验）能力的浪费，将一个班的学生分组测试（如各班台阶试验不足10人的合并）可能更有效；人数太多的班拆成两个班可能更便于安排。测试握力时段1454423128O50001000015000注：此图仅为例子，非标准答案。图中数字为班的编号，相邻两班用不同高度仅是为了区别。