机房值班的调度问题--赖增强

2015暑期数学建模培训第二次模拟承诺书我们仔细阅读了数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们授权五一数学建模联赛赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号为（从A/B/C中选择一项填写）：B我们的参赛报名号为：参赛组别（研究生或本科或专科）：本科所属学校（请填写完整的全名）中国矿业大学孙越崎学院14级参赛队员(打印并签名)：1.赖增强2.兰卫旗3.李康杰日期：2015年8月21日获奖证书邮寄地址：中国矿业大学南湖校区桃4B5032邮政编码：221116收件人姓名：赖增强联系电话：183612308562015暑期数学建模培训第二次模拟编号专用页竞赛评阅编号（由竞赛评委会评阅前进行编号）：评阅记录评阅人评分备注裁剪线裁剪线裁剪线竞赛评阅编号（由竞赛评委会评阅前进行编号）：参赛队伍的参赛号码：（请各参赛队提前填写好）：1实验教学中心机房值班问题摘要本文针对现实生活中排班的合理规划问题，结合运筹学中的0-1整数规划与多元线性规划模型以及高等代数学中的相关知识，综合运用LINGO[1]和MATLAB编程，建立了以最小支付报酬为目标的求解模型[2]。问题一，针对招聘学生类型的不确定性、学生每周可值班时长的差异性、可值班时间点的散乱性等限制因素，我们把问题中的参数、决策变量、目标函数和约束条件用多元约束函数规划模型表示出来。把各种约束都转化为数值函数，经过整理添加到目标函数中，使整个目标函数作为算法的适应性函数，其表达式为：min=+50×14−（1）要使得总支付报酬最小，分别运用LINGO软件，MATLAB[3]的optimizationtoolbox和yalmiptoolbox进行求解，得到三种最优的学生值班方案，并得出该机房总支付报酬最小均为827元。问题二，在模型一的基础之上，我们引入了决策矩阵P，在参考运筹学[2]中的对偶问题、线性规划、单纯形法的基础上，来制定可实施性方案，并对模型进行了合理的理论证明和验证。同样要使得总支付报酬最小，采用LINGO，yalmiptoolbox求解，再次得到两种学生值班方案，计算可得该机房总支付报酬最小分别为1071元和1118元。问题三，我们利用中国矿业大学教务系统统计了不同专业j个学生周i第m节课的上课情况，获得确定性假设，形成了6个赢得矩阵L。在模型二的基础上建立了新的约束条件：=2×7=1=1,2,…,5，=1,2…,6（2）对其采用LINGO软件进行求解，计算可得该机房总支付报酬最小为1415元。由于在我们的假设中，班次总数为35，大于可调配的人次数为12。而在实际操作中，可以安排一个学生多次值班。于是我们弱化了第二问部分约束条件，再次运用yalmiptoolbox求解得到最小支付报酬940元。在排班模型的推广中，我们可以将其归结为偶图的边着色问题。其实质为一个在多项式时间内不可求解的NP-Hard问题，可用遗传算法求得其最优解。关键字：混合整数规划模型，LINGO，单纯形法，yalmiptoolbox，matlab，NP-Hard2一.问题重述某实验教学中心机房准备聘用4名本科学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一到周五最多可安排的值班时间及每小时值班报酬如表一所示：表1人员可值班时间及其薪酬一览表该机房开放时间为上午8:00到晚上10:00(22:00)，开放时间内须有且仅需一名学生值班，又规定每名本科生每周值班不少于8小时，研究生每周值班不少于7小时。若某时段无人值班则每小时损失50元。要求：1、建立该机房总支付报酬最小的数学模型并求解。2、在上述基础上补充下面两个要求，一是每名学生每周值班不超过2次，二是每天安排的学生不超过3人，重新建立数学模型并求解。3、考虑到实际情况中，学生需要上课，学生只能在空闲时间值班（可以不考虑上表中的每天值班时间上限）。在此条件下建立数学模型，求解出支付报酬最小的值班方案。（学生课程表可以调查周围同学课程表或者按照一天3~6节课，一周两次晚自习的条件随机生成）。二.问题分析2.1问题一的分析分析题目可知，机房总支付报酬受到多元因素的影响。学生的类型、每名学生每天可安排的时间、学生每周值班时间等等都成为约束目标函数的因素，因此，建立多元约束函数规划模型，并用LINGO和MATLAB优化工具箱对模型求解。2.2问题二的分析在问题一的基础上，要加入每名学生每周值班次数、每天安排的学生数约束条件，为此我们引入了决策矩阵P，重新建立了约束规划模型并再次求解。2.3问题三的分析考虑到学生只能在空闲时间值班，我们采用了周边同学的课表，并合理假设学生的课程及其上课情况。利用中国矿业大学的教务系统统计了不同专业j个学生周i第m节课的上课情况，形成了6个赢得矩阵L，重新建立新的约束条件模型并求解[4]。三．基本假设3.1.假设题目中给出的数据真实可靠，且不会发生变动。3.2.假设不考虑客观因素对问题求解的影响（突发停电时间、值班人员请假等）3.3.假设不考虑学生换班时的时间消耗。3.4.假设6个学生有7节课程，且每节课上下课时间为2小时。3四．符号说明为了便于描述问题，我们用一些符号来代替问题中涉及的一些基本变量，如下所示：4.1jj=1…6表示六个学生的代号4.2y该机房总支付报酬4.3ii=1…5表示周数4.4P学生j是否被安排工作的决策矩阵4.54.6Aｑ表示学生j在周i需要值班的时间表示某时段因无人值班而损失的钱数4.7C学生j每个小时的报酬4.8L第m节课的赢得矩阵,m=1,2,…,74.9B表示学生j在周i最多的工作时间五.模型的建立与求解5.1问题一5.1.1模型建立考虑到学生类型、每名学生可值班时间、每名学生每周值班时间的不同。按照题目要求，我们建立了多元约束函数规划模型：由于某时段无人值班则每小时损失50元，可得每周总损失ｑ为：q=50×14−为方便模型的建立与求解，在此我们先假设每周都能排满14个小时，没有出现因无人值班而引起的经济损失即：=14(=1,2,3,4,5)如果运行结果不满足此条件则将其改为：≤14(=1,2,3,4,5)此时我们可以得到目标函数的数学表达式：min=+50×14−（1）其约束条件为：=14(=1,2,3,4,5)≥8(=1,2,3,4)≥7(=5,6)≤4其中B表示学生j周i最多工作的时间，结合题中值班表，我们对其进行简化，简化结果如下：⎝⎜⎜⎛606070606048305556043048006063⎠⎟⎟⎞5.1.2模型求解我们采用LINGO软件（附录一），MATLAB的optimizationtoolbox和yalmiptoolbox（附录二）分别针对学生工作时间为小数或者整数，采用不同的编程思想，进行三次最优化求解，对约束条件进行处理，得到了如下的值班人员安排结果：表5.1.2.1值班人员时间安排表（lingo）周一周二周三周四周五160607206060333002425604530220600061表5.1.2.2值班人员时间安排表（optimizationtoolbox）周一周二周三周四周五16.00000.00006.00000.00007.000020.00006.00000.00006.00000.000032.88503.44032.31900.00003.772143.30752.29033.81170.00003.158751.80750.00001.80403.38850.000060.80772.26930.00004.61150.1192表5.1.2.3值班人员时间安排表（yalmiptoolbox）周一周二周三周四周五160607206060308300450302530220600061此时满足每周值满14个班的条件，所以不需要考虑总损失。结合表中的数据计算得支付总报酬最小费用均为827元。5.2问题二5.2.1模型建立在问题一的基础之上，每名学生每周的值班次数不超过2次即：5≤2(=1,2,3,4,5,6)以及每天安排的学生人数不超过3人：≤3(=1,2,3,4,5)得到的新的约束条件：≤14(=1,2,3,4,5)≥8(=1,2,3,4)≥7(=5,6)≤≤3(=1,2,3,4,5)≤2(=1,2,3,4,5,6)其目标函数仍为：min=+50×14−（1）5.2.2模型求解由于optimizationtoolbox中linprog最优化结果会产生小数，考虑到现实生活中值班的时间尽量为整数，结合问题一中每人每天最多工作时间的简化表，所以只采用LINGO和yalmiptoolbox软件（附录三）对约束条件进行处理，得到了如下的值班人员安排结果：表5.2.2.1值班人员时间安排表（LINGO）周一周二周三周四周五160007206060308005450600530400600062表5.2.2.2值班人员时间安排表（yalmiptoolbox）周一周二周三周四周五1006072060603400054506005002806000026由表中的数据和学生的工资标准，通过目标函数（2）计算得到支付总报酬最小费用分别为1071元和1181元。分别产生的决策矩阵p1（lingo）p2（yalmiptoolbox）为：1=⎝⎜⎜⎛100010101001001101001010000001⎠⎟⎟⎞2=⎝⎜⎜⎛001010101010001101000011001001⎠⎟⎟⎞其中1代表有人在值班，0代表没人值班。5.3问题三5.3.1模型的建立在实际情况中，我们假设6个学生有7节课程，每节课上下课时间为2小时，我们利用中国矿业大学教务系统统计了不同专业j个学生周i第m节课的上课情况，形成了6个时间赢得矩阵L：1=⎝⎜⎜⎜⎛10100000111000110101101000100111000⎠⎟⎟⎟⎞2=⎝⎜⎜⎜⎛01101010110100111100101000010110100⎠⎟⎟⎟⎞3=⎝⎜⎜⎜⎛11001010100010110100111000100111001⎠⎟⎟⎟⎞4=⎝⎜⎜⎜⎛00101110100110100000001001010101000⎠⎟⎟⎟⎞5=⎝⎜⎜⎜⎛00001101010101001001100001001001001⎠⎟⎟⎟⎞6=⎝⎜⎜⎜⎛00001010100100010001101000000001011⎠⎟⎟⎟⎞矩阵中1代表学生不上课，能够值班；0代表学生上课，不能值班。在问题二约束条件的基础之上，我们继续加入约束条件：=2×=1,2,…,5，=1,2…,6（3）其中j≤6,i≤5,m≤7。至此我们建立了满足实际情况的多元约束函数规划模型。在上述问题的基础上，给出了实际情况下目标函数的数学表达式：min=+