《排班问题的最优数学规划》由会员分享，可在线阅读，更多相关《排班问题的最优数学规划（11页珍藏版）》请在金锄头文库上搜索。
1、排班问题的最优数学规划摘要本文主要研究的是在规定条件下排班问题的最优化方案。通过对问题条件的分析，建立相应的数学模型，得到各种情况下最小的机房总支付报酬。针对问题一：我们用数学规划方法中的目标规划方法，确定总支付报酬的目标函数以及约束条件，建立目标规划模型。在模型中我们采用等效替代的方法，假设无人值班情况为学生 7，学生 7 可在任意时刻“值班” ，机房需支付学生 7 报酬 50 元/小时。借助于 lingo 软件对模型进行求解，最终得到多组值班表，且每组值班表所对应的最小机房总支付报酬均为 827 元。针对问题二：我们延续问题一的目标规划模型，在模型中加入题设所给定的两个约束条件，在此基础上
2、建立模型。借助 lingo 软件对模型进行求解，最终得到总支付报酬最小情况下唯一的一组值班表，且其所对应的最小机房总支付报酬为 1071 元。针对问题三：通过 Excel 随机函数来产生 6 名学生的课表，针对此课表修改前面已建立模型。通过 lingo 软件对模型进行求解，最终可得到在该课表下最优的值班表，且其所对应的最小机房总支付报酬为 809 元。关键字：目标规划模型 等效替代 lingo 软件 Excel 随机函数 目录第一部分 问题重述(1)第二部分 问题分析(1)第三部分 模型的假设(2)第四部分 定义与符号说明(2)第五部分 模型的建立与求解(3)1.问题 1 的模型(3)模型 (
3、4)2问题 2 的模型(4)模型 (4)3.问题 3 的模型(5)模型(5)第六部分 模型的评价(6)第七部分 参考文献(6)第八部分 附录(7)- 1 -一、 问题重述某实验教学中心机房准备聘用 4 名本科学生（代号 1、2、3、4）和 2 名研究生（代号 5、6）值班进行答疑。已知每人从周一到周五最多可安排的值班时间及每小时值班报酬。由于该机房开放时间为上午 8:00 到晚 22:00，开放时间内须有且仅需一名学生值班，又规定每名本科生每周值班不得少于 8 小时，研究生每周值班不少于 7 小时。若某时段无人值班则每小时损失 50 元。要求 1、建立该机房总支付报酬最小的数学模型并求解。2、
4、在上述基础上补充下面两个要求，一是每名学生每周值班不超过 2 次，二是每天安排的学生不超过 3 人，重新建立数学模型并求解。 3、考虑到实际情况中，学生需要上课，学生只能在空闲时间值班（可以不考虑上表中的每天值班时间上限）。在此条件下建立数学模型，求解出支付报酬最小的值班方案。（学生课程表可以调查周围同学课程表或者按照一天 36节课，一周两次晚自习的条件随机生成）。二、 问题分析本题属于求解最优化问题，需要用数学规划方法对问题进行求解；针对问题一:本题属于在规定条件下的规划问题，在给定的条件下建立最小支付报酬的目标函数，同时确定约束条件，确立合适的数学模型。借助计算机软件 lingo 编程对模
5、型进行求解，得到机房的最小支付报酬。模式图如下：排 班 要 求人 员 信 息目 标 函 数 检 测综 合 择 优排 班 结 果- 2 -针对问题二：问题二在问题一的基础上新增了两个约束条件，保持问题一中的模型不变，再加上两个约束条件后得到新的模型，随后对模型进行求解。针对问题三：问题三中，由于本科生和研究生的课表未确定，首先应用软件随机产生六名学生的课表。随后这个问题就回归到问题一的模型当中，然后再对模型进行求解，得到机房所需最低的支付报酬。三、 模型假设假设一：假设题目中所给的数据真实可靠；假设二：假设本科生和研究生值班的效果相同；假设三：无人值班时所支付的报酬相当于代号为 7 的学生值班所
6、得报酬。则 7号学生在岗位时无人值班，且机房需要支付报酬 50 元/小时；假设四：本科生的课程数目比研究生多；四、 定义与符号说明为了便于描述问题，我们用一些符号来代替问题中涉及的一些基本变量，如下图所示。期同期的一些变量将陆续在文中说明。符号 意义i学生编号j星期数SUM总支付报酬,ijT编号为 的学生星期 值班时间ijiC编号为 的学生星期 值班报酬,ijb媒介函数五、 模型的建立与求解第一部分：准备工作（1） 数据的处理：- 3 -由于考虑到某时刻无人值班，假设无人值班这种情况为学生编号为 7。则学生 7 在周一到周五任何时段均有可能“值班” ，且机房需支付 50 元/小时报酬。经过处理
7、，可得到以下数据：每天最多安排的值班时间/小时学生代号 报酬（元/小时） 周一 周二 周三 周四 周五1 10 6 0 6 0 72 10 0 6 0 6 03 12 4 8 3 0 54 12 5 5 6 0 45 15 3 0 4 8 06 16 0 6 0 6 37 50 14 14 14 14 14第二部分:问题一的模型（1） 模型根据题意可知，令机房总支付报酬 取最小值，得到目标函数为：SUM(1)75,1minijiCT:st(2)7,14(1,235,67)ijT(3)4,18(,)ij(4)5,17(,6)ijjT(5),2ijijijbab注： 为媒介函数，且：,ij=0；
8、=0,ijT,ijb=1； 0,ij模型的求解：- 4 -通过 lingo 软件编程(源程序见附录【1】)，可以得到多组最优解，每组最优解的机房支付总报酬为 827 元。因为最优解在一般条件下一组已经足够，此处列出具体两种值班安排: 值班安排表 1值班安排表 2第三部分:问题二的数学模型(1) 模型问题二在问题一的模型基础上，补充了两个要求。保持模型的条件不变，在模型的条件下增加两个约束条件。即：（6）5,14(,235,67)ijjb（7）7,1(,)ij模型的求解：再次通过 lingo 软件编程(源程序见附录【2】)，只得到一组最优解，而且最优解的机房支付总报酬为 1071 元。在此列出程
9、序执行所得结果以及值班安排表，如下：- 5 -值班时间分布图学生代号 报酬 周一 周二 周三 周四 周五 总计1 10 6 0 0 0 7 1302 10 0 6 0 6 0 1203 12 0 8 0 0 5 1564 12 5 0 6 0 0 1325 15 3 0 4 0 0 1056 16 0 0 0 6 2 1287 50 0 0 4 2 0 3001071值班安排表 3第四部分:问题三的数学模型(1) 应用模型求解：通过 Excel 软件通过随机函数产生学生的课程表。在产生课程表的时，按照一天 36 节课（包括晚自习） ，并且考虑本科生的课程数目较多、而研究生的课程数目较少。具体的
10、产生结果如下：- 6 -由于问题三和问题一的前提条件相同，因此将生成的课程表代入模型，通过 lingo 软件编程（源程序见附录【3】 ） ，得到在此课表下的支付报酬最小的排班情况和排班表如下，机房最少总支付报酬为 809 元。六、 模型的推广与评价模型的评价：(1) 模型利用目标规划问题的基本方法，采用 lingo 软件对模型进行求解，最终可以具体地列出排班情况表，最终求得的结果比较精确、可靠性好。(2) 模型在利用软件求解时得到的排班情况较多，不可能一一列出，而且不能将学生在当时时间段是否有课。同时采用 excel 软件产生本科生和研究生的课表，与实际情况相差可能比较大。(3) 模型可以进行
11、适当改进，使用多种算法，如“模拟退火算法”或者“遗传算法”来进一步解决排班问题，实现总支付报酬最低。同时也可以将计算结果育模型一的结果进行比较，进一步得到排班问题的最优解，实现支付报酬最小化。(4) 模型的运用功能强大，可以应用到生活中的各种排班问题当中，实现支付报酬的最优化。模型的推广：此模型利用起来相对容易，可以容易地用各大于企业、学校等单位的排班问题，实现经费的最低化。- 7 -七、 参考文献1 马超群、兰秋军、周忠宝， 运筹学 ，长沙：湖南大学出版社，2008.12。第 3343 页；2 隋树林、杨树国、朱善良， 数学建模教程 ，北京：化学工业出版社，2015.7。第 93 页；3 赖
12、炎连、贺国平， 最优化方法 ，北京：清华大学出版社，2008.12。4 张冬梅、颜丽、金鑫，数学建模排班问题http:/ 附录附录【1】model:title:实验教学中心机房值班问题 1;sets:peo/1.7/:pay;week/1.5/;link(peo,week):t,a,b;endsetsdata:pay=10,10,12,12,15,16,50;a=6 0 6 0 70 6 0 6 04 8 3 0 55 5 6 0 43 0 4 8 00 6 0 6 314 14 14 14 14;enddatamin=sum(link(i,j):t(i,j)*pay(i);for(week(
13、j):sum(peo(i):t(i,j)=14);for(link(i,j):t(i,j)=b(i,j);for(link(i,j):t(i,j)=8);for(peo(i)|i#le#6:sum(week(j):t(i,j)=7);for(link:bin(b);end- 8 -附录【2】model:title:实验教学中心机房值班问题 2;sets:peo/1.7/:pay;week/1.5/;link(peo,week):t,a,b;endsetsdata:pay=10,10,12,12,15,16,50;a=6 0 6 0 70 6 0 6 04 8 3 0 55 5 6 0 43 0
14、 4 8 00 6 0 6 314 14 14 14 14;enddatamin=sum(link(i,j):t(i,j)*pay(i);for(week(j):sum(peo(i):t(i,j)=14);for(link(i,j):t(i,j)=b(i,j);for(link(i,j):t(i,j)=8);for(peo(i)|i#le#6:sum(week(j):t(i,j)=7);for(week(j):sum(peo(i)|i#le#6:b(i,j)=b(i,j);for(link(i,j):t(i,j)=8);for(peo(i)|i#le#6:sum(week(j):t(i,j)=7);for(link:bin(b);end
