资源描述:
《数学建模排班问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、运用运筹学和lingo对值班问题的初步探究作者:张冬梅颜丽金鑫摘要本文主要从运筹学中的对偶问题求解方法、0-1模型以及lingo线性规划问题求解方法,对值班问题进行合理规划,此次建立的模型最大的特点就是不孤道而行,这样在解题过程中实现了互补不足作用,在具体的解题过程中,我们所采用两种解题方法,运筹学与lingo的解题方法,以便最终达到较为完善的方案。最终求出符合题目要求的解答,经过结果分析与验证,所得结果完全正确。问题重述某大学有四名大学生与两名研究生,对其进行值班安排,使得每天学生工作总时间14个小时,大学生每周值班时间不少于10小时,研究生每周不少于8小时,
2、每个人每周值班不超过4次,每次不超过2小时,每天至多有三个人值班,并且每天至少有一名研究生。制定一个合理的值班表,使得支付的薪酬最少。其他相关数据参考下表:值班员代号报酬(元/小时)每天最多可安排的值班时间周一周二周三周四周五周六周日11060607120210060600123948305121249556040125153048012061606063012问题分析及符号说明在研究此问题中,若直接采用变量进行求解,但是会涉及到42(6行7列)个变量,运算量较大,不过我们可以观察表格可以得到,有16个变量是一直为零的,我们可以将这些变量进行剔除,余下16个变量
3、,实际解答中虽计算量依旧很大,不过相比之下,简单些许。此问题的最终目的是制定合理的值班表,使得所支付报酬最小,首先列出目标函数,其次根据已知条件列出线性相关不等式组,其中对于是否会安排学生值班,我们用0-1模型表示。在模型的求解过程中运用到运筹学中的对偶问题、线性规划、单纯形法来制定可实施性方案,并用matlab及lingo软件进行编程求解。符号说明符号说明ii=1…6表示六个人y需付总报酬jj=1…7表示星期b(i,j)学生i是否被安排工作t(i,j)表示每人每天安排的时间C(i)学生i每个小时的报酬a(I,j)表示每人每天最多工作的时间其中:i=1,2,…,
4、6;j=1,2,…,7.模型假设1.假设每位同学均能准时到达实验室,并且换班时间忽略不计;2.假设每位同学的可工作时间不具有时刻性,也就是说每天可值班时间可以分配到任意时刻;3.假设每位同学工作时长均为整数。模型建立目标函数:约束条件:媒介函数(bij):当=0时,0;当≠0时,1;模型求解法一:运用运筹学中线性规划对偶问题求解方法首先,观察上述约束条件,重要约束条件为前5个,后3个约束条件作为最终解的检验条件,这样易于将两类变量进行分离,又不是合理性,不违背科学性。实际求解问题:目标函数:约束条件:≠1(i=1,2,…,6;j=1,2,…,7)(i=1,2,…
5、,6;j=1,2,…,7)将上述求最小值问题转化为其对偶问题:原函数有42个未知数,42个系数,决定优化方案的13个式子(前三行),则目标函数有有13个变量(y1,y2,y3,y4,y5,y6,y7,y8,y9,y10,y11,y12,y13),42个式子,其中七个为等式,放置到后面进行考虑。目标函数:Maxz=10(y1+y2+y3+y4)+8(y5+y6)+14(y7+y8+y9+y10+y11+y12+y13)关于等式,写成七个等式为:t11+t21+t31+t41+t51+t61t12+t22+t32+t42+t52+t62t13+t23+t33+t43
6、+t53+t63t14+t24+t34+t44+t54+t64t15+t25+t35+t45+t55+t65t16+t26+t36+t46+t56+t66t17+t27+t37+t47+t57+t67对于6个不等式,7个变量进行对偶转化,得到有关6个变量,7个不等式的问题求解。目标函数:Maxz=10(y1+y2+y3+y4)+8(y5+y6)约束条件中不等式:注:此处未能进行公式成功转化在基变量y1,y2,y3,y4,y5,y6中加入非基变量,使其转化为等式将目标函数添加项(非基变量)系数为0.运用单纯形法求出可行解:CjC1C2C3C4C5C6cbxbbY1
7、Y2Y3Y4Y5Y60C1Y1B1此处为y1,y2,y3,y4,y5,y6对应的系数矩阵θ1C2Y2B2θ2C3Y3B3θ3C4Y4B4θ4C5Y5B5θ5C6Y6B6θ6C7Y7B7-z-∑cibi0000注:在运用此问题的过程中,有相关问题未能运用所学知识进行求解,参考相关资料后仍未能进行解决,希望老师给予指点,以进行完善,并希望能够更有效率地学习更多的相关知识。法二:lingo编程求解所求最小报酬为:miny=1045元具体值班安排如下表周一周二周三周四周五周六周日16h0h6h0h7h0h0h20h4h0h6h0h0h0h30h8h0h0h5h12h2h
8、45h0h6h0h0h0