《工作最优安排问题》由会员分享，可在线阅读，更多相关《工作最优安排问题（15页珍藏版）》请在金锄头文库上搜索。
1、对于“最优工作安排问题”数学模型的建立，其内容是通过分析给定人员和 人员所需完成的任务以及完成任务所花费的时间的关系，抽象出怎样把任务指派给人员使得任务的总效率达到最高的指派问题。 于是就本题目讨论，对项目而言， 越早完成越好；对人力资源而言，在该项目上所花费的人力越少越好。因此，可 以根据所优化的模型用变量代替分析变量关系，利用数学工具，进而求解。得出 最优结果。对于问题一而言，为了工作的连贯性，不允许两人或两人以上做同一 种工作。一个人在同一时间只能做一种工作。 在这种条件下，要想尽快完成工作 任务，则需要通过建立数学模型来解决。利用 Matlab软件中指派问题的匈牙利 算法和Lin go
2、软件来解决。可以得出结论是17天。对于冋题二而言，其和冋题 一十分类似，但是问题二规定每人最多只能承担一种工作，而问题一则可以一个人做两个以上的工作，因此需要通过建立数学模型利用Matlab软件中指派问题的匈牙利算法来解决。并且要考虑到一个人只能做一种工作， 所以得出的结论是 20天。对于问题三而言，对于每个工作，只有当该工作完全完成之后才能进行 检查工作。为了检查的连贯性，不允许两人或两人以上检查同一种工作。 一个人 在同一时间只能检查一种工作。言下之意，一个人完成的工作和检查的工作可以 是同样的，利用Matlab程序可以计算出答案是13天。对于问题四而言，规定每 人最多完成一种工作和另外一
3、件工作的检查任务。此时，如果继续用Matlab程序和匈牙利算法则会存在弊端，因为算下来之后的矩阵的每一行每一列只有一个 1,其余均为0,因此可以利用程序代码将问题四解决，答案是 48天。关键词：Lingo Matlab检查工作连贯性匈牙利算法程序代码#二问题的提出对于工作最优安排问题，最主要的就是在最少的时间里完成任务。 就本体而 言，一共有四个问题，一是要在最短的时间里，在允许两人或两人以上做同一种 工作。一个人在同一时间只能做一种工作的条件下， 如何用最少的时间完成任务 呢？而是要在最短的时间里，在问题一的基础上加上每个人只能做一种工作的条 件，如何求出最短的时间完成任务？三是要在问题一的
4、基础上增加一项检查工 作，对于每个工作，只有当该工作完全完成之后才能进行检查工作。 为了检查的 连贯性，不允许两人或两人以上检查同一种工作。 一个人在同一时间只能检查一 种工作，如何求出完成和检查任务的最短时间？四是要在问题三的基础上规定一 个人只能完成一种工作和检查另外一种工作， 如何求出最短的时间里完成这两项 工作？问题的解决都必须遵从人力安排的最优条件，以节省时间为前提，怎样才可以达到这样的目标呢？二基本假设基于本道题，提出如下假设：1）假设不能同一时间展开不同的工作，即只有当一项工作完成才能展开下 一项工作，也就是说完成各个工作的总时间需要通过累加完成；2）假设一完成工作就展开检查工作
5、，中间没有停顿；3）不允许两人或两人以上做同一种工作。一个人在同一时间只能做一种工 作；4）对于每个工作，只有当该工作完全完成之后才能进行检查工作。为了检 查的连贯性，不允许两人或两人以上检查同一种工作。 一个人在同一时间只能检 查一种工作。四问题的分析由题意知，根据问题的分析建立的数学模型，它要求指派的方案要使得工作 尽早完成。在求解的过程中不能使用枚举法而是通过建立数学模型来科学地思考 该问题。问题二可以利用Matlab数学软件中指派问题的匈牙利算法来解决，而 问题一，问题三中，由于条件的限制都不一样，但解决方案与问题二中十分接近， 可得到的结果也是相当理想的。对于问题四而言，相较于问题一
6、、问题二、问题 三都有些复杂，如果单纯地利用 Matlab程序来解决则会出现错误，所以还要再 次利用程序代码来解决问题四。但都需要对程序运行的结果进行充分的考察，再得出指派方案。五模型建立1）问题一模型建立:1.定义符号说明:Xj :此为0-1变量，对所有的i和j ：1，表示当指派第i个人去完成第j项工作时, 0，表示当指派第i个人去完成第j项工作时。将原题中的A,B,C,D,E,F,G人员对应X的下标i :i 1,2,3,4,5,6,7,;将原题中的甲，乙，丙，丁，戊对应 X的下标j :j 1,2,3,4,5;Min 2X11 15X12 13X13 X14 8X1510X21 4X2214
7、X23 - 15X24 7X259X3114X3216X3313X34 8X357X41 8X42 11X43 9X44 4X458X51 4X52 15X53 8X54 13X5512X61 4X62 6X63 8X64 - 13X655X7116X72 8X73 5X7410X75约束条件： 一人可完成0项或一项工作:X11X12X13X14X151X21X22X23X24X25-1X31X32X33X34X35-1X41X42X43X44X451X51X52X53X54X55乞1X61X62X63X64X65 1X71X72X73X74X75乞1一项工作只能由一人完成:X11X21X31
8、X41X51X61X71=1X12X22X32X42X52X62X72=1X13X23X33X43X53X63X73=1X14X24 X34 X44 X54X64X74=1X15X25 X35 X45 X55X65X75=12模型求解：由于是一个7X 5矩阵，因此为了 Matlab程序容易运行，多增加两列零向量 变成7X 7矩阵，如下：21513180010414157009141613800781194008415860012468130016851000c=2 15 13 1 8 0 0;10 4 14 15 7 0 0;9 14 16 13 8 0 0;7 8 11 9 4 0 0; 8
9、 4 15 8 6 0 0; 12 4 6 8 13 0 0;5 16 8 5 10 0 0;c=c(:);a=zeros(14,49);for i=1:7a(i,(i-1)*7+1:7*i)=1;a(7+i,i:7:49)=1;endb=ones(14,1);x,y=bintprog(c,a,b);Optimization terminated.x=reshape(x,7,7),y0 00 10 01 00 00 000100000 0 0 10 0 0 00 0 0 00 0 0 00 10 00 0 1010 0 020由模型可以看出一共有两种安排方法：A的工作：丁，耗时1天；D的工作：
10、戊，耗时4天；E的工作：乙，耗 时4天；F的工作：丙，耗时6天；G的工作：甲，耗时5天；B、C没有工作要 做；共消耗20天。A的工作：甲，丁，共耗时3天；D的工作：戊，耗时4天；E的工作： 乙，耗时4天；F的工作：丙，耗时6天；B C G没有工作要做；共消耗17 天。题目规定两人或两人以上不能做同一种工作并且一个人在同一时间只能做 一种工作，因此可以得出答案：17天。2）问题二模型建立:1. 定义符号说明:Xj :此为0-1变量，对所有的i和j ：1，表示当指派第i个人去完成第j项工作时, 0，表示当指派第i个人去完成第j项工作时。将原题中的A,B,C,D,E,F,G人员对应X的下标i :i
11、1,2,3,4,5,6,7,；将原题中的甲，乙，丙，丁，戊对应 X的下标j :j 1,2,3,4,5；Min 2X11 15X12 13X13 X14 8X1510X21 4X2214X23 15X24 7X259X3114X3216X3313X34 8X357 X 418 X 421 1X439X444X458X514X5215X538X5413X5512X614X626X638X6413X655X7116X728X735X7410X75约束条件： 一人可完成0项或一项工作：X11X12X13X14X 15_1X21X22X23X24X25 1X31X32X33X34X35X41X42X43
12、X44X45_1X51X52 X53X54X55 1X61X62X63X64X65-1X71X72X73X74X75 1 一项工作只能由一人完成:X11X21X31X41X51X61X71=1X12X22 X32 X42 X52X62X72=1X13X23 X33 X43 X53X63X73=1X14X24 X34 X44 X54X64X74=1X15X25 X35 X45 X55X65X75=12.模型求解:由于是一个7X 5矩阵，因此为了 Matlab程序容易运行，多增加两列零向量变成 7X 7矩阵，如下：215131800 11041415700914161380078119400841
13、58600124681300.516851000 一利用Lin go软件的程序如下:MODEL:SETS:WORKER/A.G/;JOB/J1.J7/;LINKS(WORKER,JOB):C,X;ENDSETSDATA:C=2,15,13,1,8,0,0,10,4,14,15,7,0,0,9,14,16,13,8,0,0,7,8,11,9,4,0,0,8,4,15,8,6,0,0,12,4,6,8,13,0,0,5,16,8,5,10,0,0;ENDDATAMIN = SUMLINKS:C*X);FOFRWORKER(I): SUIJOB(J):X(I,J)=1); FORJOB(J):SUMWORKER(I):X(I,J)=1);FORLINKS: BIN(X);END由模型可以看出一共有两种安排方法:A的工作：丁，耗时1天；D的工作：戊，耗时4天；E的工作：乙，耗时4天；F的工作：丙，耗时6天；G的工作：甲，耗时5天；B、C没有工 作要做；共消耗20天。A的工作：甲，
