最优工作安排问题数学建模

《最优工作安排问题数学建模》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、B最优工作安排问题摘要：最优工作安排在当今这个劳动力不再廉价的社会至关重要。本文主要研究最优工作安排问题，可视为运筹学屮的指派问题。对于指派问题，分别通过建立0-1整体线性规划模型，多目标线性规划模型以及二次o-i整数线性规划模型加以解决。考虑到一个人可在不同的时间做不同的工作，因此我们引入"0-1变量”©表示是否指派第i个人去完成第/项工作。对于多目标问题，为解决不同目标之间产生的矛盾，将多目标问题转化为单目标问题，例如：在第三问中，采用极大极小法。通过翻译题目要求来建立目标函数和约束条件，并利用Lingo软件编写程序，对问题求解。最后对所得到的最优解进行

2、检验，以提高答案的科学性与可靠性。关键字：0-1模型最优解多目标线性规划Lingo一.背景分析1.1问题重述现有五件工作甲、乙、丙、丁、戊要交给A、B、C、D、E、F和G七个人來完成。完成这个工作所需要花费的时间如表1所示，且这七个人均表示可参加该项目。【注意：为了工作的连贯性，不允许两人或两人以上做同一种工作。一个人在同一时间只能做一种工作。】表1.七人五件工作用时表（单位：天）甲乙A215B104C914D78E84F124G516丙T戊131814157161381194158668138510试通过建立数学模型（而非枚举法）回答下述问题。问题1.应该

3、如何进行工人的安排使得这五件工作能尽早完成？问题2.在问题1屮若规定每人最多承担一种工作，试求相应的最优人力安排方案。问题3.接上级通知，为了保证工作的质量，需要对完成工作之后进行检查且规定同一个人不能即做这件工作又检查这件工作。显然，在这种新的要求下，这五件工作完成当且仅当所有的工作检查完。己知这七人均表示可以参加检查工作，他们检查这五种工作的用时如表2所示。【注意：对于每个工作，只有当该工作完全完成之后才能进行检查工作。为了检查的连贯性，不允许两人或两人以上检查同一种工作。一个人在同一吋间只能检查一种工作。】问：应该如何进行人力的安排使得该五项工作尽早完

4、成？表2.七人五件工作检查用时表（单位：天）甲乙丙T戊A1131018B1048105C861096D671184E631585F1146710G412632问题4.在问题3中若规定每人最多完成一种工作和另外一件工作的检查任务,试求相应的最优人力安排方案。1.2问题分析整个问题均可视为运筹学中的指派问题。对于问题一，为了使得这五项工作能尽早完成，可引入"0-1变量”，定义©表示是否指派第j个人去完成第./•项工作，从而使时间量化。由于问题一中数据较少口每个人的效率差别明显，因此要使得这五项工作能尽早完成，可转化为选出在所有的指派方案中所用总时间最少的方案，因

5、此我们以运筹学中的指派问题为基础建立模型，并根据题目要求建立目标函数和约束条件。对于问题二，最优人力安排方案可理解为考虑时间、成本等因素下的效率最大化，即做完这五件事所用的总时间最小。又由于题目要求每人最多承担一种工作，即在第一问的基础上，增加约束条件：=,7。./=!对于问题三，由于存在两个目标，因此可将该小题视为多目标规划问题，尽早完成工作即为保证做完某工作及检查完毕的吋间和向量中的最大值最小化。由于在多目标规划问题屮，不同目标Z间往往会发生矛盾。为解决该矛盾，将多目标问题转化为单口标问题，即采用极大极小法。对于问题四，题目耍求求解每人最多完成一种工作和

6、另外一件工作的检查任务的最优人力安排方案。与第二问类似，即效率最大化的总时间最小原则。因此在第二问模型的基础上再次使用“0-1”模型，称为二次0-1整数线性规划模型。二、符号定义符号含义Xij为0时表示不指派第i个人去完成第丿•项工作；为1吋表示指派第j个人去完成第./•项工作。Cij第i个人完成第丿•项工作所需时间厶表示完成工作所需总吋间%为0时表示不指派第/个人去检查第j项工作；为1时表示指派第「个人去检查第丿•项工作。aij表示第i个人检查第丿•项工作所需时间z2表示完成工作所需时间与检查工作所需时间总和三.模型假设1、假设题目中所给数据可靠无误；2、

7、假设问题中的任何人对于参与各项工作都没有限制；3、假设每个人完成工作的质量相同；4、假设每个人做每项工作的其他因素(成本、资源等)相同。5、对于问题一与问题三，一个人在完成一件事情之后可继续做另一件事；6、对于问题一、问题二以及问题四，认为五个工作完成时间之和最小时的方案即最优人力安排方案；7、各个工作之间没有相互联系。即这五个工作中，某一个工作的完成与否，不受另一个工作的制约。四.0-1整体线性规划模型设立3.1问题一3.1.1模型建立为了将工作时间定量，首先将第厂个人做或者不做第丿•项工作定量化，再以五件工作完成总时间作为目标函数，最后对目标函数求最优解

8、得出最终结果。设：=J(),不指派第2•个人做第/•