数学建模排班问题

运用运筹学和lingo对值班问的初步探究 作者：张冬梅 颜  丽 金  鑫 摘要 本文主要从运筹学中的对偶问题求解、0-1模型以及lingo线性规划问题求解方法，对值班问题进行合理规划，此次建立的模型最大的特点就是不孤道而行，这样在解题过程中实现了互补不足作用，在具体的解题过程中,我们所采用两种解题方法,运筹学与lingo的解题方法，以便最终达到较为完善的。最终求出符合题目要求的解答，经过结果分析与验证，所得结果完全正确。 问题重述 某大学有四名大学生与两名研究生，对其进行值班安排，使得每天学生工作总时间14个小时，大学生每周值班时间不少于10小时，研究生每周不少于8小时，每个人每周值班不超过4次，每次不超过2小时，每天至多有三个人值班，并且每天至少有一名研究生。制定一个合理的值班，使得支付的薪酬最少。 其他相关数据参考下表： 值班员代号 报酬（元/小时） 每天最多可安排的值班时间 周一 周二 周三 周四 周五 周六 周日 1 10 6 0 6 0 7 12 0 2 10 0 6 0 6 0 0 12 3 9 4 8 3 0 5 12 12 4 9 5 5 6 0 4 0 12 5 15 3 0 4 8 0 12 0 6 16 0 6 0 6 3 0 12                   问题分析及符号说明 在研究此问题中，若直接采用变量进行求解，但是会涉及到42（6行7列）个变量，运算量较大，不过我们可以观察可以得到，有16个变量是一直为零的，我们可以将这些变量进行剔除，余下16个变量，实际解答中虽计算量依旧很大，不过相比之下，简单些许。 此问题的最终目的是制定合理的值班表，使得所支付报酬最小，首先列出目标函数，其次根据已知条件列出线性相关不等式组，其中对于是否会安排学生值班，我们用0-1模型表示。在模型的求解过程中运用到运筹学中的对偶问题、线性规划、单纯形法来制定可实施性方案，并用matlab及lingo软件进行编程求解。 符号 说明 符号 说明 i i=1…6表示六个人 y 需付总报酬 j j=1…7表示星期 b(i,j) 学生i是否被安排工作 t(i,j) 表示每人每天安排的时间 C(i) 学生i每个小时的报酬 a(I,j) 表示每人每天最多工作的时间 其中：i=1,2,…,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,…,6;j=1,2,…,7) 将上述求最小值问题转化为其对偶问题： 原函数有42个未知数，42个系数，决定优化方案的13个式子（前三行），则目标函数有有13个变量（y1,y2,y3,y4,y5,y6,y7,y8,y9,y10,y11,y12,y13），42个式子，其中七个为等式，放置到后面进行考虑。 目标函数： Max z=10(y1+y2+y3+y4)+8(y5+y6)+14(y7+y8+y9+y10+y11+y12+y13) 关于等式，写成七个等式为： t11+t21+t31+t41+t51+t61 t12+t22+t32+t42+t52+t62 t13+t23+t33+t43+t53+t63 t14+t24+t34+t44+t54+t64 t15+t25+t35+t45+t55+t65 t16+t26+t36+t46+t56+t66 t17+t27+t37+t47+t57+t67 对于 6个不等式，7个变量进行对偶转化，得到有关6个变量，7个不等式的问题求解。 目标函数： Max z=10(y1+y2+y3+y4)+8(y5+y6) 约束条件中不等式： 注：此处未能进行公式成功转化 在基变量y1,y2,y3,y4,y5,y6中加入非基变量，使其转化为等式将目标函数添加项（非基变量）系数为0. 运用单纯形法求出可行解： Cj C1 C2 C3 C4 C5 C6     cb xb b Y1 Y2 Y3 Y4 Y5 Y6 0   C1 Y1 B1 此处为y1,y2,y3,y4,y5,y6对应的系数矩阵 θ1   C2 Y2 B2 θ2   C3 Y3 B3 θ3   C4 Y4 B4 θ4   C5 Y5 B5 θ5   C6 Y6 B6 θ6   C7 Y7 B7     -z -∑cibi 0 0 0 0                               注：在运用此问题的过程中，有相关问题未能运用所学知识进行求解，参考相关资料后仍未能进行解决，希望老师给予指点，以进行完善，并希望能够更有效率地学习更多的相关知识。 法二：lingo编程求解 所求最小报酬为：miny=1045元 具体值班安排如下表   周一 周二 周三 周四 周五 周六 周日 1 6h 0h 6h 0h 7h 0h 0h 2 0h 4h 0h 6h 0h 0h 0h 3 0h 8h 0h 0h 5h 12h 2h 4 5h 0h 6h 0h 0h 0h 10h 5 3h 0h 2h 6h 0h 2h 0h 6 0h 2h 0h 2h 2h 0h 2h                 注：相关程序及运行结果见附录 结果分析与评价 通过比较运筹学求解与lingo求解，易知，运筹学逻：辑性强，过程严谨，很有启发性；lingo：过程简单，求值较精确。本模型的优点是求解方式多样，不足是建模过程创新不足，计算能力有待加强，知识面有待拓展。 参考文献 1.《数学模型》（第四版）姜启源，谢金星； 2.《数学建模》王连堂； 3.百度文库。 附录 相关程序如下： model: sets: ren/1..6/:qian; ri/1..7/; link(ren,ri):t,a,b; endsets data: qian=10,10,9,9,15,16; a= 6,0,6,0,7,12,0 0,6,0,6,0,0,12 4,8,3,0,5,12,12 5,5,6,0,4,0,12 3,0,4,8,0,12,0 0,6,0,6,3,0,12; enddata min=@sum(link(i,j):t(i,j)*qian(i)); @for(ri(j):@sum(ren(i):t(i,j))=14); @for(ri(j):@sum(ren(i):b(i,j))<=3); @for(link(i,j):t(i,j)>=2*b(i,j)); @for(link(i,j):t(i,j)<=a(i,j)*b(i,j)); @for(ren(i)|i#le#4:@sum(ri(j):t(i,j))>=10); @for(ren(i)|i#ge#5:@sum(ri(j):t(i,j))>=8); @for(ri(j):@sum(ren(i):b(i,j))<=4); @for(ri(j):@sum(ren(i)|i#ge#5:b(i,j))>=1); @for(link:@bin(b)); end 运算结果： Global optimal solution found. Objective value:                              1045.000 Extended solver steps:                              0 Total solver iterations:                            19 Variable          Value        Reduced Cost QIAN( 1)        10.00000            0.000000 QIAN( 2)        10.00000            0.000000 QIAN( 3)        9.000000            0.000000 QIAN( 4)        9.000000            0.000000 QIAN( 5)        15.00000            0.000000 QIAN( 6)        16.00000            0.000000 T( 1, 1)        6.000000            0.000000 T( 1, 2)        0.000000            0.000000 T( 1, 3)        6.000000            0.000000 T( 1, 4)        0.000000            0.000000 T( 1, 5)        7.000000            0.000000 T( 1, 6)        0.000000            0.000000 T( 1, 7)        0.000000            1.000000 T( 2, 1)        0.000000            0.000000 T( 2, 2)        4.000000            0.000000 T( 2, 3)        0.000000            0.000000 T( 2, 4)        6.000000            0.000000 T( 2, 5)        0.000000            0.000000 T( 2, 6)        0.000000            0.000000 T( 2, 7)        0.000000            1.000000 T( 3, 1)        0.000000            0.000000 T( 3, 2)        8.000000            0.000000 T( 3, 3)        0.000000            0.000000 T( 3, 4)        0.000000            0.000000 T( 3, 5)        5.000000            0.000000 T( 3, 6)        12.00000            0.000000 T( 3, 7)        2.000000            0.000000 T( 4, 1)        5.000000            0.000000 T( 4, 2)        0.000000            0.000000 T( 4, 3)        6.000000            0.000000 T( 4, 4)        0.000000            0.000000 T( 4, 5)        0.000000            0.000000 T( 4, 6)        0.000000            0.000000 T( 4, 7)        10.00000            0.000000 T( 5, 1)        3.000000            0.000000 T( 5, 2)        0.000000            5.000000 T( 5, 3)        2.000000            0.000000 T( 5, 4)        6.000000            0.000000 T( 5, 5)        0.000000            0.000000 T( 5, 6)        2.000000            0.000000 T( 5, 7)        0.000000            6.000000 T( 6, 1)        0.000000            1.000000 T( 6, 2)        2.000000            0.000000 T( 6, 3)        0.000000            1.000000 T( 6, 4)        2.000000            0.000000 T( 6, 5)        2.000000            0.000000 T( 6, 6)        0.000000            1.000000 T( 6, 7)        2.000000            0.000000 A( 1, 1)        6.000000            0.000000 A( 1, 2)        0.000000            0.000000 A( 1, 3)        6.000000            0.000000 A( 1, 4)        0.000000            0.000000 A( 1, 5)        7.000000            0.000000 A( 1, 6)        12.00000            0.000000 A( 1, 7)        0.000000            0.000000 A( 2, 1)        0.000000            0.000000 A( 2, 2)        6.000000            0.000000 A( 2, 3)        0.000000            0.000000 A( 2, 4)        6.000000            0.000000 A( 2, 5)        0.000000            0.000000 A( 2, 6)        0.000000            0.000000 A( 2, 7)        12.00000            0.000000 A( 3, 1)        4.000000            0.000000 A( 3, 2)        8.000000            0.000000 A( 3, 3)        3.000000            0.000000 A( 3, 4)        0.000000            0.000000 A( 3, 5)        5.000000            0.000000 A( 3, 6)        12.00000            0.000000 A( 3, 7)        12.00000            0.000000 A( 4, 1)        5.000000            0.000000 A( 4, 2)        5.000000            0.000000 A( 4, 3)        6.000000            0.000000 A( 4, 4)        0.000000            0.000000 A( 4, 5)        4.000000            0.000000 A( 4, 6)        0.000000            0.000000 A( 4, 7)        12.00000            0.000000 A( 5, 1)        3.000000            0.000000 A( 5, 2)        0.000000            0.000000 A( 5, 3)        4.000000            0.000000 A( 5, 4)        8.000000            0.000000 A( 5, 5)        0.000000            0.000000 A( 5, 6)        12.00000            0.000000 A( 5, 7)        0.000000            0.000000 A( 6, 1)        0.000000            0.000000 A( 6, 2)        6.000000            0.000000 A( 6, 3)        0.000000            0.000000 A( 6, 4)        6.000000            0.000000 A( 6, 5)        3.000000            0.000000 A( 6, 6)        0.000000            0.000000 A( 6, 7)        12.00000            0.000000 B( 1, 1)        1.000000          -30.00000 B( 1, 2)        0.000000            0.000000 B( 1, 3)        1.000000          -30.00000 B( 1, 4)        0.000000            0.000000 B( 1, 5)        1.000000          -42.00000 B( 1, 6)        0.000000          -60.00000 B( 1, 7)        0.000000            0.000000 B( 2, 1)        0.000000            0.000000 B( 2, 2)        1.000000            0.000000 B( 2, 3)        0.000000            0.000000 B( 2, 4)        1.000000          -30.00000 B( 2, 5)        0.000000            0.000000 B( 2, 6)        0.000000            0.000000 B( 2, 7)        0.000000            0.000000 B( 3, 1)        0.000000          -24.00000 B( 3, 2)        1.000000          -8.000000 B( 3, 3)        0.000000          -18.00000 B( 3, 4)        0.000000            0.000000 B( 3, 5)        1.000000          -35.00000 B( 3, 6)        1.000000          -72.00000 B( 3, 7)        1.000000            0.000000 B( 4, 1)        1.000000          -30.00000 B( 4, 2)        0.000000          -5.000000 B( 4, 3)        1.000000          -36.00000 B( 4, 4)        0.000000            0.000000 B( 4, 5)        0.000000          -28.00000 B( 4, 6)        0.000000            0.000000 B( 4, 7)        1.000000            0.000000 B( 5, 1)        1.000000            0.000000 B( 5, 2)        0.000000            0.000000 B( 5, 3)        1.000000            0.000000 B( 5, 4)        1.000000            0.000000 B( 5, 5)        0.000000            0.000000 B( 5, 6)        1.000000            0.000000 B( 5, 7)        0.000000            0.000000 B( 6, 1)        0.000000            0.000000 B( 6, 2)        1.000000            12.00000 B( 6, 3)        0.000000            0.000000 B( 6, 4)        1.000000            2.000000 B( 6, 5)        1.000000            0.000000 B( 6, 6)        0.000000            0.000000 B( 6, 7)        1.000000            14.00000 Row    Slack or Surplus      Dual Price