河南理工大学2014年数学建模竞赛

《河南理工大学2014年数学建模竞赛》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、河南理工大学2014年数学建模竞赛基于0-1整体线性规划法的工作分配问题【摘要】效率是指对于有限资源(如原材料，人力现金等)的最佳分配方法.是经济发展和社会稳定的基础。自古以来，不论是大到国家、社会，小到公司、个体。效率都是其追求的重要目标。而减小成本也是相当重要的。特别是在提高效率的同时减小成本和代价，这样能给公司，国家等带来最大程度上的的经济效益，还能促进他们更好更快的发展。本模型旨在通过对6个人员进行合适的工作分配，从而达到得到较大效率的同时尽可能的降低成本。本问题中首先确定第i人做或者不做第j工作将

2、问题定量化，再以全部的工作效率和工作成本为目标函数，在人员现有的情况下，通过分析各种影响因素，排除掉一些不必要的干扰因素，运用整数线性规划及0-1规划的知识建立数学模型，并使用LINGO软件进行编程，最后对目标函数求最优解得出最终结果。即人员分配的最佳方案。并在对本模型优缺点评价和对结果进行深度的分析之后，对模型进行了改进。关键词：最大效率；最少成本；最优解；0-1模型；Lingo线性规划；人员分配优化工作安排方案。一、问题的重述14经济效益是一个企业甚至国家最重视的问题之一，而经济效益的实现主要是靠提高效

3、率和降低成本，对工作人员进行最优的工作分配能极大地提高效率和降低成本。在本问题中已知有6个人员，可以做6项工作，每个人做每项工作的效率如表1所示和所用的成本如表2中所示。表1：每个人做每项工作的效率工作人员工作1工作2工作3工作4工作5工作6人员1351002人员2643254人员3142212人员4123331人员5213242人员6325466表2：每个人做每项工作的成本工作人员工作1工作2工作3工作4工作5工作6人员1481004人员212753119人员32104425人员4255794人员5527

4、474人员6851081113问题：1、如何安排每个人的工作，使得总的工作效率最大。2、如何安排每个人的工作，使得总的成本最低。3、如何兼顾工作效率和成本，优化工作安排方案。14二、模型的假设1、假设题目中所给的数据都是可靠无误的。2、假设问题中的任何人对于参与各项工作都没有限制；3、假设每个人完成工工作的质量相同。4、假设每个人做每项工作的其他因素都相同。5、每个人都能按自己的效率完成工作。6、每个人只能做一个工作，即既不能同时做两个工作，也不能在一个工作做完后再做其他工作。7、每件工作都必须有人做，且只

5、能由一个人独立完成。8、各个工作之间没有相互联系。即一个工作的完成与否，不受另一工作的限制。三、符号说明符号含义为0时表示不让第个人去完成第项工作；为1时表示让第个人去完成第项工作。表示第个人去完成第项工作的工作效率表示第个人去完成第项工作的工作成本14四、模型的建立与求解（一）问题一1.1.问题分析该问题属于这样一类的分派问题：有若干项任务，每项任务必须有一人且必须有一人承担，每人也只能承担其中的一项，不同的人员承担不同任务的收益或成本不同，问题是怎样的分配方案能使总收益最大（或总成本最小）。他又称为指派

6、问题。在现实生活中，有各种性质的指派问题（AssignmentProblem）。例如，在生产管理中，总希望把人员进行最佳分配，以发挥最大的工作效率；建立0-1规模型是解决这类问题的常用方法。0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此0-1规划非常适合描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等特别是像本题的分派问题有很好的效果。本问题是指派问题中工作任务的数量与能够承担的人员数量相

7、等的情况，需要对六项任务进行合适的分配，得到其最大效率（暂不考虑成本的情况下）。定义表示是否指派第个人去完成第项工作，从而使工作效率量化。由于这一问题中数据较少且每个人的效率差别明显，因此要使得这六项工作能尽早完成，可转化为选出在所有的指派方案中工作效率最大的方案，因此我们以运筹学中的指派问题为基础建立模型，并根据题目要求建立目标函数和约束条件。141.2.模型的建立为了将工作效率定量，首先将第个人做或者不做第项工作定量化，再以六件工作完成总效率作为目标函数，最后对目标函数求最优解得出最终结果。设:将原题中

8、的人员1,2,3,4,5,6对应的下标：；将原题中的工作1,2,3,4,5,6对应的下标：。则，目标函数为：其中：表示完成工作所需总效率；表示第个人完成第项工作所需效率。由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只能有一人完成。同时，每个人同时最多完成一件工作。因此，约束条件为：同时，每个人同时最多完成一件工作。因此，约束条件为：141.3.模型的求解根据目标函数及其约束条件可知，该模型为