-值班分配问题-题目2

1、实验室值班分配问题论文摘要：某大学实验室准备聘请4 名大学生 (代号为 1、2、3、4) 和 2名研究生（代号为5、6）值班答疑。在合理分配学生时间的前提下，使总支付的报酬最小。 本文将值班分配问题归结为混合整数规划模型问题，并对每个同学的值班时间做约束，另外实验室的开放时间也是约束条件之一。经过合理的假设，并用matlab 数学软件进行计算，得出了大学生和研究生的安排时间，得到最少的总支付为1045. 关键词：整数规划、分支定界、值班时间、总支付1.问题的重述： 某大学实验室准备聘请4 名大学生 (代号为 1、 2、 3、4)和 2 名研究生（代号为5、6）值班答疑。已知每人从周一到周日每天

2、最多可以安排的值班时间及每人每小时值班的报酬如下表所示值班时间要求和实验室开放时间如下：?实验室开放时间为上午8:00 至晚上 10:00; ?开放时间内须有且仅段一名学生值班; ?规定大学生每周值班不少于8 小时; ?研究生每周值班不少于7 小时; ?每名大学生每周值班不超3 次; ?每次值班不少于 2 小时; ?每天安排值班的学生不超过3 人，且其中必须有一名研究生. 在满足以上条件的前提下，安排学生值班时间，使得总支付最小。2.模型假设：（1）假设实验室的开放时间没有变化（2）假设学生严格遵守时间安排3.符号约定 : 设第 i 人第 j 天的最大值班时间为aij设第 i 人第 j 天的值

3、班时间为xij设第 i 人第 j 天是否值班为yij(yij0,1) 设第 i 人每小时报酬为ki设总支付为 z 4.模型的建立根据要求，建立一个求最小值的优化模型，建立模型如下minz=61iik71ijjxs.t 2yijxijaijyij（i=1,2 6, j=1,27）（1）71jijx8（i=1,2,3,4）（2）71jijx7 （i=5,6 ）（3）61ijijiyx=14 (j=1,2 7) （4）71jijy3 （i=1,2,3,4）（5）61iijy3 (j=1,2 7) （6）yj5+yj61 （j=1,2 7) （7）xij0，且为整数（i=1,2 6, j=1,27）（

4、8）yij=0 或 1 （i=1,2 6, j=1,27）（9）约束条件说明：第（1）是每次值班不少于2 小时；第（ 2）是大学生每周值班不少于8 小时；第（ 3）是研究生每周值班不少于7 小时；第（ 4）是实验室开放时间为上午 8:00 至晚上 10:00 共 14 小时；第（ 5）是每名大学生每周值班不超 3 次；第 （6）(7) 是每天安排值班的学生不超过3 人，且其中必须有一名研究生. 5.模型的求解通过编程用 matlab 实现可得以下两个表，表（ 1）表示第 i 个学生在第 j 天的工作时间；表（ 2）表示第 i 个学生在第 j 天是否值班表（1）代号日期周一周二周三周四周五周六周

5、日1 6 0 6 0 7 0 0 2 0 4 0 6 0 0 0 3 0 8 0 0 5 12 0 4 5 0 6 0 0 0 12 5 3 0 2 6 0 2 0 6 0 2 0 2 2 0 2 表（2）代号日期周一周二周三周四周五周六周日1 1 0 1 0 1 0 0 2 0 1 0 1 0 0 0 3 0 1 0 0 1 1 0 4 1 0 1 0 0 0 1 5 1 0 1 1 0 1 0 6 0 1 0 1 1 0 1 将以上两表进行整合可得到分配表如下表（3）周一代号 1 代号 4 代号 5 6 小时5 小时3 小时周二代号 2 代号 3 代号 6 4 小时8 小时2 小时周三代号 1 代号 4 代号 5 6 小时6 小时2 小时周四代号 2 代号 5 代号 6 6 小时6 小时2 小时周五代号 1 代号 3 代号 6 7 小时5 小时2 小时周六代号 3 代号 5 12 小时2 小时周日代号 4 代号 6 12 小时2 小时综上：按照变（ 3）的安排可使得总支付最小，最小值是1045 元6.参考文献1韩中庚， 数学建模方法及其应用 ，北京，高等教育出