河南理工大学2014年数学建模竞赛.doc 14页

'河南理工大学2014年数学建模竞赛基于0-1整体线性规划法的工作分配问题【摘要】效率是指对于有限资源(如原材料，人力现金等)的最佳分配方法.是经济发展和社会稳定的基础。自古以来，不论是大到国家、社会，小到公司、个体。效率都是其追求的重要目标。而减小成本也是相当重要的。特别是在提高效率的同时减小成本和代价，这样能给公司，国家等带来最大程度上的的经济效益，还能促进他们更好更快的发展。本模型旨在通过对6个人员进行合适的工作分配，从而达到得到较大效率的同时尽可能的降低成本。本问题中首先确定第i人做或者不做第j工作将问题定量化，再以全部的工作效率和工作成本为目标函数，在人员现有的情况下，通过分析各种影响因素，排除掉一些不必要的干扰因素，运用整数线性规划及0-1规划的知识建立数学模型，并使用LINGO软件进行编程，最后对目标函数求最优解得出最终结果。即人员分配的最佳方案。并在对本模型优缺点评价和对结果进行深度的分析之后，对模型进行了改进。关键词：最大效率；最少成本；最优解；0-1模型；Lingo线性规划；人员分配优化工作安排方案。一、问题的重述14 经济效益是一个企业甚至国家最重视的问题之一，而经济效益的实现主要是靠提高效率和降低成本，对工作人员进行最优的工作分配能极大地提高效率和降低成本。在本问题中已知有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人员5527474人员6851081113问题：1、如何安排每个人的工作，使得总的工作效率最大。2、如何安排每个人的工作，使得总的成本最低。3、如何兼顾工作效率和成本，优化工作安排方案。14 二、模型的假设1、假设题目中所给的数据都是可靠无误的。2、假设问题中的任何人对于参与各项工作都没有限制；3、假设每个人完成工工作的质量相同。4、假设每个人做每项工作的其他因素都相同。5、每个人都能按自己的效率完成工作。6、每个人只能做一个工作，即既不能同时做两个工作，也不能在一个工作做完后再做其他工作。7、每件工作都必须有人做，且只能由一个人独立完成。8、各个工作之间没有相互联系。即一个工作的完成与否，不受另一工作的限制。三、符号说明符号含义为0时表示不让第个人去完成第项工作；为1时表示让第个人去完成第项工作。表示第个人去完成第项工作的工作效率表示第个人去完成第项工作的工作成本14 四、模型的建立与求解（一）问题一1.1.问题分析该问题属于这样一类的分派问题：有若干项任务，每项任务必须有一人且必须有一人承担，每人也只能承担其中的一项，不同的人员承担不同任务的收益或成本不同，问题是怎样的分配方案能使总收益最大（或总成本最小）。他又称为指派问题。在现实生活中，有各种性质的指派问题（AssignmentProblem）。例如，在生产管理中，总希望把人员进行最佳分配，以发挥最大的工作效率；建立0-1规模型是解决这类问题的常用方法。0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此0-1规划非常适合描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等特别是像本题的分派问题有很好的效果。本问题是指派问题中工作任务的数量与能够承担的人员数量相等的情况，需要对六项任务进行合适的分配，得到其最大效率（暂不考虑成本的情况下）。定义表示是否指派第个人去完成第项工作，从而使工作效率量化。由于这一问题中数据较少且每个人的效率差别明显，因此要使得这六项工作能尽早完成，可转化为选出在所有的指派方案中工作效率最大的方案，因此我们以运筹学中的指派问题为基础建立模型，并根据题目要求建立目标函数和约束条件。14 1.2.模型的建立为了将工作效率定量，首先将第个人做或者不做第项工作定量化，再以六件工作完成总效率作为目标函数，最后对目标函数求最优解得出最终结果。设:将原题中的人员1,2,3,4,5,6对应的下标：；将原题中的工作1,2,3,4,5,6对应的下标：。则，目标函数为：其中：表示完成工作所需总效率；表示第个人完成第项工作所需效率。由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只能有一人完成。同时，每个人同时最多完成一件工作。因此，约束条件为：同时，每个人同时最多完成一件工作。因此，约束条件为：14 1.3.模型的求解根据目标函数及其约束条件可知，该模型为0-1整体线性规划模型。因此，利用Lingo软件编写程序对此问题求解。（程序见附录）可解得：表1.3.1问题一解VariableValuex(1,2)1.000000x(2,1)1.000000x(3,3)1.000000x(4,4)1.000000x(5,5)1.000000x(6,6)1.000000由表1.3.1可得到表1.3.2：表1.3.2工作安排工作工人效率215126332443554666综合以上所述：应该安排工人1做工作2，效率为5；安排工人2做工作1，效率为6；安排工人3做工作3，效率为2；安排工人4做工作4，效率为3；安排工人5做工作5，效率为4；安排工人6做工作6，效率为6；即工作的最大效率为26。1.4.模型检验由于每个人最多做一件工作，且每件工作只由一位工人完成，可知上述答案满足题目要求，具有合理性。14 （二）问题二2.1.问题分析本小题是通过对六个人员的工作分配，求解其最低成本时的方案（暂不考虑他们的工作效率），即只有一个优化目标的单目标规划问题。可引入“0-1变量”，定义表示是否指派第个人去完成第项工作，从而使工作成本量化。由于这一问题中数据较少且每个人每项工作的成本差别明显，因此要使得这六项工作能低成本完成，可转化为选出在所有的指派方案中工作成本最小的方案，因此我们以运筹学中的指派问题为基础建立模型，并根据题目要求建立目标函数和约束条件。2.2.模型建立为了将工作成本定量，首先将第个人做或者不做第项工作定量化，再以六件工作完成总成本作为目标函数，最后对目标函数求最优解得出最终结果。设：将原题中的人员1,2,3,4,5,6对应的下标：；将原题中的工作1,2,3,4,5,6对应的下标：。则，目标函数为：14 其中：表示完成工作所需总成本；表示第个人完成第项工作所需成本。由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只能有一人完成。同时，每个人同时最多完成一件工作。因此，约束条件为：同时，每个人同时最多完成一件工作。因此，约束条件为：2.3.模型求解根据目标函数及其约束条件可知，该模型为0-1整体线性规划模型。因此，利用Lingo软件编写程序对此问题求解。（程序见附录）可解得：表2.3.1问题二解VariableValuex(1,3)1.000000x(2,4)1.000000x(3,5)1.000000x(4,1)1.000000x(5,6)1.000000x(6,2)1.000000由表2.3.1可得到表2.3.2：14 表2.3.2工作安排工作工人成本311423532142654265综合以上所述：应该安排工人1做工作3，成本为1；安排工人2做工作4，成本为3；安排工人3做工作5，成本为2；安排工人4做工作1，成本为2；安排工人5做工作6，成本为4；安排工人6做工作2，成本为5；即工作的最小成本为17。3.3.模型检验由于每个人最多做一件工作，且每件工作只由一位工人完成，可知上述答案满足题目要求，具有合理性。（三）问题三3.1问题分析本小题是对前两个小题的综合，再得到效率的同时也要降低成本（即兼顾效率与成本），它是有多个优化目标的多目标规划问题，多目标规划的目标函数相当于一个向量，这类多目标最优化方法的基本思想是将多目标问题转化为一个或一系列的单目标优化问题，通过求解一个或一系列单目标优化问题来完成多目标优化问题的求解。在本体这种情况下，需要将前两个问题的一个结果作为约束条件。再结合实际问题，将效率不低于75％作为约束条件，即效率约为20。3.2模型建立14 为了将工作成本定量，首先将第个人做或者不做第项工作定量化，再以六件工作完成总成本作为目标函数，最后对目标函数求最优解得出最终结果。设：将原题中的人员1,2,3,4,5,6对应的下标：；将原题中的工作1,2,3,4,5,6对应的下标：。则，目标函数为：其中：表示完成工作所需总成本；表示第个人完成第项工作所需成本。由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只能有一人完成。同时，每个人同时最多完成一件工作。因此，约束条件为：同时，每个人同时最多完成一件工作。因此，约束条件为：又由于题目要求兼顾效率与成本，再结合实际问题，将效率不低于75％作为约束条件，即效率约为20。因此，约束条件为：14 3.3模型求解根据目标函数及其约束条件可知，该模型为0-1整体线性规划模型。因此，利用Lingo软件编写程序对此问题求解。（程序见附录）可解得：表3.3.1问题三解VariableValuex(1,1)1.000000x(2,2)1.000000x(3,4)1.000000x(4,3)1.000000x(5,6)1.000000x(6,5)1.000000由表3.3.1可得到表3.3.2：表3.3.2工作安排工作工人成本1142274343456545611综合以上所述：在效率不低于最大效率的75％的前提下，应该安排工人1做工作1，成本为4；安排工人2做工作2，成本为7；安排工人3做工作4，成本为4；安排工人4做工作3，成本为5；安排工人5做工作6，成本为4；安排工人6做工作5，成本为11；即工作的最小成本为35，是最低成本的2倍。3.4模型检验14 由于每个人最多做一件工作，且每件工作只由一位工人完成，同时要求效率不低于最大效率的75％，成本增大了一倍。可知上述答案满足题目要求，符合实际情况，具有合理性。如果不低于最大效率的60％，成本几乎也增加了一倍。五、模型的误差分析本文针对工作分配问题采用的是0-1整体规划的方法，其思想比较简单，但是十分实用，当然在实际问题中不可避免的存在着误差。本模型的误差在于，在实际工作的过程中有可能为了追求最大的工作效率和最小的工作成本而存在这么几种情况：有可能某些人会在自己规定的时间范围内提前完成任务，休息抑或是去帮助他人完成工作；有可能某一项的工作进度会受到另外一项工作的限制，从而会耽误原本的工作计划；也有可能某些工作的完成需要依靠温度、湿度等自然条件的约束而无法按时完成任务等等，但是这些误差都是允许存在的。六、模型的评价优点：模型明了简洁，具有相当的可推广性。而且对于工作分配中存在的关于一人是否可以做多项工作进行了分析求解。本模型首先通过限定一人只能做一项工作，对问题作了lingo运算，并得到正确结果。之后又通过不限定每项工作的人数，同样的得到lingo结果。本模型可以在两者得到相同效率的时候比较两种想法得到的结果，从而进行更合适的工作指派。企业的最终目的都是以盈利为目的，对于问题3中建模的完成在实际问题中是具有绝对实用价值的。14 缺点：模型考虑的影响因素较少。比如说对于实际情况下，某个人对于某项工作有限制性；比如说，对于同一项工作每个人完成的质量不同，从而会对最终的盈利（最终目的）产生不同的影响；比如说，表格中对于某些人的数据统计存在误差；比如说，在实际工作中，人工作的效率和使用的成本是否就会一成不变；比如说，某项工作是否完成会不会对另外一项工作产生影响等等。总的来说，本模型同时存在优点和缺点，当然这也是每个模型都存在的问题。但是对于此模型来说，优点是绝对大于缺点的。所以本模型是绝对成功的。七、模型的推广与改进在该问题的求解中，考虑的方面较为简略，还有很多因素可以考虑。例如在可以协作的情况下，各个人做完了分配工作后可以再其他工作的情况下，以及该情形下他们不同的休息时间，各道工作有关联时的情况等因素。但在单一工作及简单考虑情况下，该模型具有较大的生存空间，只需改动少许数值即可推广应用。另外，关于对问题3的分析，可以同时推广到对于多目标决策问题的求解。比如说，在商业投资的过程中，收益和风险都是共同存在的，而且风险随着收益的增大而增大。那么如何选择合适的投资组合方案，才能使收益最高风险最小呢?这就可以对于本模型进行些修改来求解。八、参考文献14 九、附录14'