2022年数学建模排班实用

《2022年数学建模排班实用》由会员分享，可在线阅读，更多相关《2022年数学建模排班实用（12页珍藏版）》请在金锄头文库上搜索。

1、运用运筹学和lingo对值班问题的初步探究作者：张冬梅颜丽金鑫摘要本文主要从运筹学中的对偶问题求解方法、0-1 模型以及 lingo线性规划问题求解方法， 对值班问题进行合理规划， 此次建立的模型最大的特点就是不孤道而行，这样在解题过程中实现了互补不足作用，在具体的解题过程中,我们所采用两种解题方法 ,运筹学与 lingo 的解题方法，以便最终达到较为完善的方案。最终求出符合题目要求的解答，经过结果分析与验证，所得结果完全正确。问题重述某大学有四名大学生与两名研究生，对其进行值班安排， 使得每天学生工作总时间 14 个小时，大学生每周值班时间不少于10 小时，研究生每周不少于8小时，每个人每周

2、值班不超过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 列）个变量，运算量较大，不过我们可以观察表格

3、可以得到，有16 个变量是一直为零的，我们可以将这些变量进行剔除，余下16 个变量，实际解答中虽计算量依旧很大，不过相比之下，简单些许。此问题的最终目的是制定合理的值班表，使得所支付报酬最小， 首先列出目标函数，其次根据已知条件列出线性相关不等式组，其中对于是否会安排学生值班，我们用 0-1 模型表示。在模型的求解过程中运用到运筹学中的对偶问题、线性规划、单纯形法来制定可实施性方案， 并用 matlab 及 lingo 软件进行编程求解。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

4、 1 页，共 12 页 - - - - - - - - - 符号说明符号说明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. 假设每位同学工作时长均为整数。模型建立目标函数：约束条件：错误！未找到引用源。错误！未找到引用源。名师资料总结 - -

5、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 媒介函数（bij） ：当错误！未找到引用源。0 时，错误！未找到引用源。0;当错误！未找到引用源。0 时,错误！未找到引用源。1；模型求解法一：运用运筹学中线性规划对偶问题求解方法首先，观察上述约束条件， 重要约束条件为前5 个，后 3 个约束条件作为最终解的检验条件， 这样易于将两类变量进行分离， 又不是合理性，不违背科学性。实际求解问题：目标函数：约束条件：错误！未找到引用源。1 (i=1,2,

6、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 个式子，其中七个为等式，放置到后面进行考虑。目标函数：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - Max

7、 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错误！未找到引用源

8、。对于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

9、 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - C6 Y6 B6 6 C7 Y7 B7 -z -cibi 0 0 0 0 注：在运用此问题的过程中， 有相关问题未能运用所学知识进行求解，参考相关资料后仍未能进行解决， 希望老师给予指点， 以进行完善， 并希望能够更有效率地学习更多的相关知识。法二： lingo编程求解所求最小报酬为： miny=1045元具体值班安排如下表周一周二周三周四周五周六周日1 6h 0h 6h

10、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. 百度文库。附录相关

11、程序如下：model : sets: ren/1.6/:qian; ri/1.7/; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - link(ren,ri):t,a,b; endsetsdata: 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

12、; enddatamin =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)=2*b(i,j); for (link(i,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)=1); for (link:bin (b); end运算结果： Global optimal solution found. Objective value: 1045.00

13、0 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

14、( 1, 3) 6.000000 0.000000 T( 1, 4) 0.000000 0.000000 T( 1, 5) 7.000000 0.000000 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 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(

15、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,

16、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)

17、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.0

18、00000 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - A( 2, 1) 0.000

19、000 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

20、 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.

21、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.000

22、000 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 名师资料总结 - - -精品资料欢迎下载 -

23、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 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

24、.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

25、 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.

26、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 1 1045.000 -1.000000 2 0.000000 -15.00000 3 0.000000 -10.00000 4 0.000000 -15.00000 5 0.000000 -15.00000 6 0.000000 -16.00000 7 0.000000 -15.00000 8 0.000000 -9.000000 9 0.000000 0

27、.000000 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 14 1.000000 0.000000 15 0.000000 0.000000 16 4.000000 0.000000 17 0.000000 0.000000 18 4.000000 0.0

28、00000 19 0.000000 0.000000 20 5.000000 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 2.000000 0.000000 25 0.000000 0.000000 26 4.000000 0.000000 27 0.000000 0.000000 28 0.000000 0.000000 29 0.000000 0.000000 30 0.000000 0.000000 31 6.000000 0.000000 32 0.000000 0.000000

29、33 0.000000 0.000000 34 3.000000 0.000000 35 10.00000 0.000000 36 0.000000 0.000000 37 3.000000 0.000000 38 0.000000 0.000000 39 4.000000 0.000000 40 0.000000 0.000000 41 0.000000 0.000000 42 0.000000 0.000000 43 8.000000 0.000000 44 1.000000 0.000000 45 0.000000 0.000000 46 0.000000 0.000000 47 4.0

30、00000 0.000000 48 0.000000 0.000000 49 0.000000 0.000000 50 0.000000 0.000000 51 0.000000 0.000000 52 0.000000 -6.000000 53 0.000000 0.000000 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 54 0.000000 -1.000000 55 0.000000 0.000000 56 0.

31、000000 0.000000 57 0.000000 -7.000000 58 0.000000 5.000000 59 0.000000 0.000000 60 0.000000 5.000000 61 0.000000 5.000000 62 0.000000 6.000000 63 0.000000 5.000000 64 0.000000 0.000000 65 0.000000 5.000000 66 2.000000 0.000000 67 0.000000 5.000000 68 0.000000 5.000000 69 0.000000 6.000000 70 0.00000

32、0 5.000000 71 0.000000 0.000000 72 0.000000 6.000000 73 0.000000 1.000000 74 0.000000 6.000000 75 0.000000 6.000000 76 0.000000 7.000000 77 0.000000 6.000000 78 10.00000 0.000000 79 0.000000 6.000000 80 0.000000 1.000000 81 0.000000 6.000000 82 0.000000 6.000000 83 0.000000 7.000000 84 0.000000 6.00

33、0000 85 2.000000 0.000000 86 0.000000 0.000000 87 0.000000 0.000000 88 2.000000 0.000000 89 2.000000 0.000000 90 0.000000 1.000000 91 10.00000 0.000000 92 0.000000 0.000000 93 0.000000 0.000000 94 4.000000 0.000000 95 0.000000 0.000000 96 4.000000 0.000000 97 1.000000 0.000000 名师资料总结 - - -精品资料欢迎下载 -

34、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 98 0.000000 0.000000 99 10.00000 0.000000 100 9.000000 0.000000 101 0.000000 0.000000 102 17.00000 0.000000 103 11.00000 0.000000 104 5.000000 0.000000 105 0.000000 0.000000 106 1.000000 0.000000 107 1.000000 0.0

35、00000 108 1.000000 0.000000 109 1.000000 0.000000 110 1.000000 0.000000 111 2.000000 0.000000 112 1.000000 0.000000 113 0.000000 0.000000 114 0.000000 0.000000 115 0.000000 0.000000 116 1.000000 0.000000 117 0.000000 0.000000 118 0.000000 0.000000 119 0.000000 0.000000 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -