运筹学课程设计--某大学计算机机房值班安排的优化.doc

题 目 某大学计算机机房值班安排的优化目录1.1研究的背景31.2研究的主要内容与目的31.3研究的意义31.4研究的主要方法和思路32模型的建立. 42.1 基础数据的建立42.2 变量的设定62.3 目标函数的建立62.4 限制条件的确定62.5 模型的建立73 模型的求解及解的分析.93.1 模型的求解93.2 模型的分析与评价144 结论与建议 . 144.1 研究结论144.2 建议与对策14某大学计算机机房值班安排的优化1.1研究的背景某大学计算机机房为裁减值班人员并同时向在校学生提供勤工俭学的机会 ，特此聘用3名大学生和3名研究生为实验室值班。但学校并没有充裕的资金，于是需依照各学生可工作的时间和每小时的薪酬，安排一个产生报酬最少的值班表，并保证每天13个小时均有学生值班。机房面临的问题有以下几方面：第一、如何才能满足各学生值班的时间和次数。第二、如何才能保证每一天都需给至少一个研究生安排值班时间。第三、综合各约束条件，如何才能使总支付的报酬最少。1.2研究的主要内容与目的此项研究的主要内容是根据学生可工作的时间进行合理规划。目的是依据各学生工作每小时所需的报酬、机房对于工作时间和次数的要求，以使学校总支付的报酬达到最低。1.3研究的意义通过科学、合理的计算与规划，使学校总支付的报酬最少，节省更多资金，并为在校学生提供勤工俭学的机会，锻炼其能力，减轻学费负担。1.4研究的主要方法和思路由于该研究题目是在计算机机 房要求的条件下使总支付报酬最少，这完全符合运筹学线性规划的理论。因此可以按照线性规划求解模式计算出既科学又合理的的最优方案。具体思路如下：预算总支付报酬在使值班时间达到校方要求的情况下，用每个学生可值班的时间乘以每小时的报酬计算出总成本。成本=时薪时间 根据各种限定性因素得出目标函数和各个约束条件 应用计算机软件进行求解2 模型的建立2.1基础数据的建立聘用三名大学生(代号1，2，3)和三名研究生（代号4，5，6）值班。、每人从周一至周五每天最多可安排的值班时间及每人每小时的报酬见表。学生代号报酬(元/h)每天最多可安排的值班时间(h)周一周二周三周四周五110606072100606031148305412556045143048061306063计算机机房为使各个学生工作时间均衡，让大家都得到锻炼的机会，特此对具体的值班安排作出了要求：实验室开放时间为上午9：00至晚上10：00，开放时间内须有且仅须一名学生值班，规定大学生每周值班不少于7小时，研究生每周不少于8小时，每名学生每天至多值1次，每次值班不少于2小时，每天安排值班的学生最多为4人，其中必须有一名研究生。2.2变量的设定1号学生周一工作时间:x11小时; 1号学生周二工作时间:x12小时；1号学生周三工作时间:x13小时; 1号学生周四工作时间:x14小时；1号学生周五工作时间:x15小时; 2号学生周一工作时间:x21小时; 2号学生周二工作时间:x22小时；2号学生周三工作时间:x23小时; 2号学生周四工作时间:x24小时；2号学生周五工作时间:x25小时；3号学生周一工作时间:x31小时; 3号学生周二工作时间:x32小时；3号学生周三工作时间:x33小时; 3号学生周四工作时间:x34小时；3号学生周五工作时间:x35小时；4号学生周一工作时间:x41小时; 4号学生周二工作时间:x42小时；4号学生周三工作时间:x43小时; 4号学生周四工作时间:x44小时；4号学生周五工作时间:x45小时；5号学生周一工作时间:x51小时; 5号学生周二工作时间:x52小时；5号学生周三工作时间:x53小时; 5号学生周四工作时间:x54小时；5号学生周五工作时间:x55小时；6号学生周一工作时间:x61小时; 6号学生周二工作时间:x62小时；6号学生周三工作时间:x63小时; 6号学生周四工作时间:x64小时；6号学生周五工作时间:x65小时.2.3目标函数的建立根据上述基础数据可以得出如下目标函数Minf(x)=10x11+10x13+10x15+10x22+10x24+11x31+11x32+11x33+11x35+12x41+12x42+12x43+12x45+14x51+14x53+14x54+13x62+13x64+13x65该目标函数是用每个学生可值班的时间乘以每小时的报酬，结果为学校每周需支出的总费用。要使总支出最小，只需该目标函数取得极小值即可，这与研究问题的目的是相一致的。2.4.1 各学生每周工作时间的限定x11+x13+x15=7 x22+x24=7 x31+x32+x33+x35=7 x41+x42+x43+x45=8 x51+x53+x54=8 x62+x64+x65=82.4.2每天值班总时间 x11+x31+x41+x51=13 x22+x32+x42+x62=13 x13+x33+x43+x53=13 x24+x54+x64=13 x15+x35+x45+x65=132.4.3每个学生每天工作时间的限定x11=2 x11=2 x13=2 x15=2 x22=2 x24=2 x31=2 x32=2 x33=2 x35=2 x41=2 x42=2 x43=2 x45=2 x51=2 x53=2 x54=2 x62=2 x64=2 x65=7 x22+x24=7 x31+x32+x33+x35=7 x41+x42+x43+x45=8 x51+x53+x54=8 x62+x64+x65=8x11+x31+x41+x51=13 x22+x32+x42+x62=13 x13+x33+x43+x53=13 x24+x54+x64=13 x15+x35+x45+x65=13x11=2 x11=2 x13=2 x15=2 x22=2 x24=2 x31=2 x32=2 x33=2 x35=2 x41=2 x42=2 x43=2 x45=2 x51=2 x53=2 x54=2 x62=2 x64=2 x65=3end 3 模型的求解及解的分析3.1 模型的最优解利用线性规划计算软件Lindo进行求解,结果如下： LP OPTIMUM FOUND AT STEP 39 OBJECTIVE FUNCTION VALUE 1) 732.0000 VARIABLE VALUE REDUCED COST X11 6.000000 0.000000 X13 6.000000 0.000000 X15 7.000000 0.000000 X22 6.000000 0.000000 X24 6.000000 0.000000 X31 2.000000 0.000000 X32 3.000000 0.000000 X33 3.000000 0.000000 X35 2.000000 0.000000 X41 2.000000 0.000000 X42 2.000000 0.000000 X43 2.000000 0.000000 X45 2.000000 0.000000 X51 3.000000 0.000000 X53 2.000000 0.000000 X54 3.000000 0.000000 X62 2.000000 0.000000 X64 4.000000 0.000000 X65 2.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 12.000000 0.000000 3) 5.000000 0.000000 4) 3.000000 0.000000 5) 0.000000 0.000000 6) 0.000000 -3.000000 7) 0.000000 -2.000000 8) 4.000000 0.000000 9) 0.000000 1.000000 10) 4.000000 0.000000 11) 0.000000 1.000000 12) 5.000000 0.000000 13) 0.000000 0.000000 14) 4.000000 0.000000 15) 0.000000 1.000000 16) 4.000000 0.000000 17) 0.000000 1.000000 18) 0.000000 0.000000 19) 2.000000 0.000000 20) 1.000000 0.000000 21) 5.000000 0.000000 22) 1.000000 0.000000 23) 0.000000 0.000000 24) 0.000000 -1.000000 25) 3.000000 0.000000 26) 0.000000 -1.000000 27) 3.000000 0.000000 28) 0.000000 -1.000000 29) 3.000000 0.000000 30) 0.000000 -1.000000 31) 4.000000 0.000000 32) 0.000000 -2.000000 33) 2.000000 0.000000 34) 1.000000 0.000000 35) 0.000000 0.000000 36) 0.000000 0.000000 37) 2.000000 0.000000 38) 1.000000 0.000000 39) 5.000000 0.000000 40) 0.000000 0.000000 41) 4.000000 0.000000 42) 2.000000 0.000000 43) 2.000000 0.000000 44) 0.000000 -1.000000 45) 1.000000 0.000000 46) 0.000000 -11.000000 47) 0.000000 -11.000000 48) 0.000000 -11.000000 49) 0.000000 -11.000000 50) 0.000000 -10.000000 NO. ITERATIONS= 39 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X11 10.000000 1.000000 INFINITY X13 10.000000 1.000000 INFINITY X15 10.000000 1.000000 INFINITY X22 10.000000 1.000000 INFINITY X24 10.000000 1.000000 INFINITY X31 11.000000 INFINITY 0.000000 X32 11.000000 0.000000 1.000000 X33 11.000000 0.000000 0.000000 X35 11.000000 INFINITY 1.000000 X41 12.000000 INFINITY 1.000000 X42 12.000000 INFINITY 1.000000 X43 12.000000 INFINITY 1.000000 X45 12.000000 INFINITY 2.000000 X51 14.000000 0.000000 1.000000 X53 14.000000 0.000000 0.000000 X54 14.000000 2.000000 0.000000 X62 13.000000 INFINITY 0.000000 X64 13.000000 0.000000 2.000000 X65 13.000000 INFINITY 1.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 7.000000 12.000000 INFINITY 3 7.000000 5.000000 INFINITY 4 7.000000 3.000000 INFINITY 5 8.000000 0.000000 INFINITY 6 8.000000 1.000000 0.000000 7 8.000000 1.000000 0.000000 8 2.000000 4.000000 INFINITY 9 6.000000 1.000000 0.000000 10 2.000000 4.000000 INFINITY 11 6.000000 1.000000 0.000000 12 2.000000 5.000000 INFINITY 13 7.000000 INFINITY 0.000000 14 2.000000 4.000000 INFINITY 15 6.000000 1.000000 4.000000 16 2.000000 4.000000 INFINITY 17 6.000000 1.000000 0.000000 18 2.000000 1.000000 0.000000 19 4.000000 INFINITY 2.000000 20 2.000000 1.000000 INFINITY 21 8.000000 INFINITY 5.000000 22 2.000000 1.000000 INFINITY 23 3.000000 INFINITY 0.000000 24 2.000000 3.000000 0.000000 25 5.000000 INFINITY 3.000000 26 2.000000 1.000000 0.000000 27 5.000000 INFINITY 3.000000 28 2.000000 1.000000 0.000000 29 5.000000 INFINITY 3.000000 30 2.000000 1.000000 0.000000 31 6.000000 INFINITY 4.000000 32 2.000000 2.000000 0.000000 33 4.000000 INFINITY 2.000000 34 2.000000 1.000000 INFINITY 35 3.000000 INFINITY 0.000000 36 2.000000 0.000000 INFINITY 37 4.000000 INFINITY 2.000000 38 2.000000 1.000000 INFINITY 39 8.000000 INFINITY 5.000000 40 2.000000 0.000000 1.000000 41 6.000000 INFINITY 4.000000 42 2.000000 2.000000 INFINITY 43 6.000000 INFINITY 2.000000 44 2.000000 0.000000 0.000000 45 3.000000 INFINITY 1.000000 46 13.000000 0.000000 1.000000 47 13.000000 5.000000 1.000000 48 13.000000 0.000000 1.000000 49 13.000000 0.000000 1.000000 50 13.000000 0.0