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

摘要：

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

关键字：0-1模型 最优解 多目标 线性规划 Lingo

一、背景分析

1.1 问题重述

现有五件工作甲、乙、丙、丁、戊要交给A、B、C、D、E、F和G七个人来完成。完成这个工作所需要花费的时间如表1所示，且这七个人均表示可参加该项目。【注意：为了工作的连贯性，不允许两人或两人以上做同一种工作。一个人在同一时间只能做一种工作。】

表1. 七人五件工作用时表（单位：天） 甲 乙 丙 丁 戊 A 2 15 13 1 8 B 10 4 14 15 7 C 9 14 16 13 8 D 7 8 11 9 4 E 8 4 15 8 6 F 12 4 6 8 13 G 5 16 8 5 10 试通过建立数学模型（而非枚举法）回答下述问题。 问题1. 应该如何进行工人的安排使得这五件工作能尽早完成？

问题2. 在问题1中若规定每人最多承担一种工作，试求相应的最优人力安排方案。

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

表2. 七人五件工作检查用时表（单位：天） 甲 乙 丙 丁 戊 A 1 13 10 1 8 B 10 4 8 10 5 C 8 6 10 9 6 D 6 7 11 8 4 E 6 3 15 8 5 F 11 4 6 7 10 G 4 12 6 3 2 问题4. 在问题3中若规定每人最多完成一种工作和另外一件工作的检查任务，试求相应的最优人力安排方案。

1.2 问题分析

整个问题均可视为运筹学中的指派问题。 对于问题一，为了使得这五项工作能尽早完成，可引入“0-1变量”，定义xij表示是否指派第i个人去完成第j项工作，从而使时间量化。由于问题一中数据较少且每个人的效率差别明显，因此要使得这五项工作能尽早完成，可转化为选出在所有的指派方案中所用总时间最少的方案，因此我们以运筹学中的指派问题为基础建立模型，并根据题目要求建立目标函数和约束条件。

对于问题二，最优人力安排方案可理解为考虑时间、成本等因素下的效率最大化，即做完这五件事所用的总时间最小。又由于题目要求每人最多承担一种工作，即在第一问的基础上，增加约束条件：xij1,i1,2,j15,7。

对于问题三，由于存在两个目标，因此可将该小题视为多目标规划问题，尽早完成工作即为保证做完某工作及检查完毕的时间和向量中的最大值最小化。由于在多目标规划问题中，不同目标之间往往会发生矛盾。为解决该矛盾，将多目标问题转化为单目标问题，即采用极大极小法。

对于问题四，题目要求求解每人最多完成一种工作和另外一件工作的检查任务的最优人力安排方案。与第二问类似，即效率最大化的总时间最小原则。因此在第二问模型的基础上再次使用“0-1”模型，称为二次0-1整数线性规划模型。

二、符号定义

符号 xij 含义 为0时表示不指派第i个人去完成第j项工作； 为1时表示指派第i个人去完成第j项工作。 cij 第i个人完成第j项工作所需时间 表示完成工作所需总时间 为0时表示不指派第i个人去检查第j项工作； Z1 yij 为1时表示指派第i个人去检查第j项工作。 aij 表示第i个人检查第j项工作所需时间 表示完成工作所需时间与检查工作所需时间总和 Z2

三、模型假设

1、假设题目中所给数据可靠无误；

2、假设问题中的任何人对于参与各项工作都没有； 3、假设每个人完成工作的质量相同；

4、假设每个人做每项工作的其他因素（成本、资源等）相同。

5、对于问题一与问题三，一个人在完成一件事情之后可继续做另一件事；

6、对于问题一、问题二以及问题四，认为五个工作完成时间之和最小时的方案即最优人力安排方案；

7、各个工作之间没有相互联系。即这五个工作中，某一个工作的完成与否，不受另一个工作的制约。

四、0-1整体线性规划模型设立

3.1 问题一 3.1.1 模型建立

为了将工作时间定量，首先将第i个人做或者不做第j项工作定量化，再以五件工作完成总时间作为目标函数，最后对目标函数求最优解得出最终结果。

设：

0,不指派第i个人做第j项工作xiji1,27,j15

1,指派第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。

则，目标函数为：

minZcijxij

j1i157其中：

Z表示完成工作所需总时间；

cij表示第i个人完成第j项工作所需时间。

由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只能有一人完成。因此，约束条件为：

xi17ij1,j1,,5

3.1.2 模型求解

根据目标函数及其约束条件可知，该模型为0-1整体线性规划模型。因此，利用Lingo软件编写程序对此问题求解。（程序见附录一）

可解得：

表3.1.2.1 问题一解 Variable Value VOLUME( X1, W1) 1.000000 VOLUME( X1, W4) 1.000000 VOLUME( X4, W5) 1.000000 VOLUME( X5, W2) 1.000000 VOLUME( X6, W3) 1.000000

由表3.1.2.1可得到表3.1.2.2：

表3.1.2.2 工作安排 工作 工人 时间（天） 甲 A 2 乙 E 4 丙 F 6 丁 A 1 戊 D 4

综合以上所述：应该安排工人A做甲和丁两件事，共需3天；安排工人D做戊，需4天；安排E做乙，需4天；安排F做丙，需6天；即总耗时6天。

3.1.3 模型检验

由于丙工作所需最少时间为6天，且每件工作只由一位工人完成，可知上述答案满足题目要求，具有合理性。

3.2 问题二 3.2.1 模型建立

问题二中规定每人最多承担一种工作，则五个工作完成时间之和最小时的方案即最优人力安排方案。在问题一的基础上，可得到，目标函数为:

minZ1cijxij

j1i157其中：

Z表示完成工作所需总时间；

cij表示第i个人完成第j项工作所需时间。

由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只

能有一人完成。因此，约束条件①为：

xi157ij1,j1,,5

由于每人最多承担一种工作，因此，约束条件②为：

xj1ij1,i1,2,,7

3.2.2 模型求解

根据目标函数及其约束条件可知，该模型为0-1整体线性规划模型。因此，利用Lingo软件编写程序对此问题求解。（程序见附录二）

可解得：

表3.2.2.1 问题二解 Variable Value VOLUME( X1, W4) 1.000000 VOLUME( X4, W5) 1.000000 VOLUME( X5, W2) 1.000000 VOLUME( X6, W3) 1.000000 VOLUME( X7, W1) 1.000000

由表3.2.2.1可得到表3.2.2.2：

表3.2.2.2 工作安排 工作 工人 时间（天） 甲 G 5 乙 E 4 丙 F 6 丁 A 1 戊 D 4

综合以上所述：应该安排工人A做丁，共需1天；安排工人D做戊，需4天；安排E做乙，需4天；安排F做丙，需6天；安排工人G做甲，需5天；即总耗时6天。

3.2.3 模型检验

由于丙工作所需最少时间为6天，且每个人只做一件工作，每件工作只由一位工人完成，可知上述答案满足题目要求，具有合理性。

五、多目标线性规划模型（问题三）

5.1 模型建立

线性规划只研究在满足一定条件下，单一目标函数取得最优解。而在问题三中要求五项工作尽早完成，即保证做完某工作及检查完毕的时间和向量中的最大值最小化，即可将问题三转化为多目标线性规划问题。在多目标规划问题中，不同目标之间往往会发生矛盾。未解决该矛盾，将多目标问题转化为单目标问题，即采用极大极小法。

设：

0,不指派第i个人做第j项工作xiji1,27,j15

1,指派第i个人做第j项工作0,不指派第i个人检查第j项工作yiji1,27,j15

1,指派第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。

则，目标函数为：

minmax{cijxijaijyij}

1j5i1i177其中：

aij表示第i个人检查第j项工作所需时间；

由于为了工作的连贯性，不允许两人或两人以上检查同一种工作，即一项工作只能由一人检查。因此，约束条件①为：

yi17ij1,j1,,5

又由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只能有一人完成。因此，约束条件②为：

xi17ij1,j1,,5

由于同一个人不能既做这件工作又检查这件工作，因此，约束条件⑤为：

xijyij1

5.2 模型求解

根据目标函数及其约束条件可知，该模型为多目标线性规划模型。因此，可以在第一小题成立的前提下（即x11，x14，x45，x52，x63都为0），利用Lingo软件编写程序对此问题求解。（程序见附录三）

可解得：

Variable X11 X14 X45 X52 X63 表5.2.1 问题三解 Value Variable 1.000000 Y71 1.000000 Y32 1.000000 Y73 1.000000 Y74 1.000000 Y75 Value 1.000000 1.000000 1.000000 1.000000 1.000000

由表5.2.1可得到表5.2.2：

表5.2.2 工作安排 工作 工人 时间（天） 检查工作 工人 时间（天） 甲 A 2 甲 G 4 乙 E 4 乙 C 4 丙 F 6 丙 G 6 丁 A 1 丁 G 3 戊 D 4 戊 G 2

综合以上所述：应该安排工人A做甲，共需2天；安排工人E做乙，需4天；安排F做戊，需6天；安排A做丙，需1天；安排工人D做丁，需4天；安排G检查丁，需4天；安排C检查丙，需4天；安排G检查甲，需6天；安排G检查乙，需3天；安排G检查戊，需2天；总耗时16天。

六、二次0-1整数线性规划模型（问题四）

6.1 模型建立

问题四规定每人最多完成一种工作和另外一件工作的检查任务，那么该问题可回归到第二问，即效率最大化，而总时间最小原则，因此在运筹学的指派问题模型基础上改进模型，建立二次0-1整数线性规划模型，并针对完成工作和检查工作设立约束条件，建立最终优化模型。

设：

0,不指派第i个人做第j项工作xiji1,27,j15

1,指派第i个人做第j项工作0,不指派第i个人检查第j项工作yiji1,27,j15

1,指派第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。

则，目标函数为：

minZ2cijxijaijyij

j1i157其中：Z2表示完成工作所需时间与检查工作所需时间总和； aij表示第i个人检查第j项工作所需时间；

由于为了工作的连贯性，不允许两人或两人以上检查同一种工作，即一项工作只能由一人检查。因此，约束条件①为：

yi17ij1,j1,,5

又由于为了工作的连贯性，不允许两人或两人以上做同一种工作，即一项工作只能有一人完成。因此，约束条件②为：

xi17ij1,j1,5,5

,7。

由于每人最多完成一种工作和另外一件工作的检查任务，因此，约束条件③为：

xj15ij1,i1,2,,7；约束条件④为：yij1,i1,2,j1由于同一个人不能既做这件工作又检查这件工作，因此，约束条件⑤为：

xijyij1

6.2 模型求解

根据目标函数及其约束条件可知，该模型为二次0-1整数线性规划模型。因此，利用Lingo软件编写程序对此问题求解。（程序见附录四）

可解得：

表6.2.1 问题四解 Variable Value Variable Value X11 1.000000 Y14 1.000000 X22 1.000000 Y23 1.000000 X45 1.000000 Y41 1.000000 X63 1.000000 Y52 1.000000 X74 1.000000 Y75 1.000000

由表6.2.1可得到表6.2.2：

表6.2.2 工作安排 工作 工人 时间（天） 检查工作 工人 时间（天） 甲 A 2 甲 D 6 乙 B 4 乙 E 3 丙 F 6 丙 B 8 丁 G 5 丁 A 1 戊 D 4 戊 G 2

综合以上所述：应该安排工人A做甲，共需2天；安排工人B做乙，需4天；安排D做戊，需4天；安排F做丙，需6天；安排工人G做丁，需5天；安排A检查丁，需1天；安排B检查丙，需8天；安排D检查甲，需6天；安排E检查乙，需3天；安排G检查戊，需2天；完成工作以及检查工作总共需41小时。

七 模型评价与改进

7.1 模型评价

在模型的建立过程中，认真审读题目要求，将题目要求转化为线性规划中的目标函数以及约束条件。根据已有知识，并且参考大量文献，可知该问题为指派问题。利用Lingo软件编写程序对该问题进行求解，求得最优方案后并进行验证，从而提高最终方性以及可靠性。

1）在模型一，二中，首先将最少时间即人力资源成本利用0-1变量将其量化，进行定量分析，其次根据已有文献，准确将其定位为运筹学中的指派问题，依据题中所给条件确定约束条件，建立“0-1”整数规划模型，并成功利用Lingo软件求解，体现科学、最优、准确的原则。

2）在模型三中，将尽早完成工作即为保证做完某工作及检查完毕的时间和向量中的最大值最小化。由于存在两个目标，二不同目标之间往往会发生矛盾。为解决该矛盾，将多目标问题转化为单目标问题，采用了极大极小法，使得结果更为科学，可靠。

3）在模型四中，由于存在多个目标，因此我们利用总时间最小的效率最大化原则，在模型二的基础上建立二次“0-1”整数规划模型，巧妙的将多目标的问题转化为单目标问题，整体操作简单、易懂，方法合理科学有效。

4）本模型的实用性和适用性都非常广泛，且模型结果具有一定的说服力和可靠性。尤其是在单一工作及简单考虑情况下，该模型具有较大的生存空间，具有较大的借鉴意义。除此之外，对于类似的问题，也可以采用利用excel使用匈牙利解法极其方便地获得相应的方案，使得模型具有很强的应用价值。

5）模型可以运用Lingo等相对比较简单和基础的软件进行求解，使得模型的应用性较强。如果采纳此模型，各项操作也就得以简化。

7.2 模型缺点

1) 模型的众多假设带来了不可避免的不同程度上的误差。 2) 在模型一中，在对工作能够尽早完成这一目标进行定量转化时，只简单考虑了总时间最小原则，而忽略其运行成本问题，使模型具有一定的局限性。

3) 在问题三与问题四的求解中，考虑的方面较为简单，没有考虑到甲、乙、丙、丁、戊这五件工作以及检查工作之间的关联情况。尤其在在模型三中，使用极大极小化模型，却间接忽略了一个人在同一时间只能做一件事这一条件，因此得到的模型不是最优解，可靠性不高。

八 参考文献

[1] 韩伯棠 管理运筹学（第三版） 北京 高等教育出版社 2004.9

[2] 汪晓银 周保平 数学建模与数学实验（第二版） 北京 科学出版社 2012.8 [3] http://www.docin.com/p-676730124.html 《最优人力资源安排问题》

[4] http://www.docin.com/p-248372112.html?qq-pf-to=pcqq.c2c 工作人员的最优时间分配问题的研究

[5] 吴有平 刘杰 何杰，多目标规划的LINGO求解法，《湖南工业大学学报》，第26卷 第3期，2012.5

九 附录

附录一：

问题一Lingo运行程序，如下：

model:

!7个人5份工作的分配问题; sets:

warehouses/x1..x7/:a; vendors/w1..w5/:b;

links(warehouses,vendors):cost,volume; endsets !目标函数;

min=@sum(links:cost*volume); !需求约束;

@for(vendors(J):

@sum(warehouses(I):volume(I,J))=b(J)); !数据; data:

a=1 1 1 1 1 1 1; b=1 1 1 1 1;

cost=2 15 13 1 8 10 4 14 15 7 9 14 16 13 8 7 8 11 9 4 8 4 15 8 6 12 4 6 8 13 5 16 8 5 10; enddata end

附录二：

问题二Lingo运行程序，如下：

model:

!7个人5份工作的分配问题; sets:

warehouses/x1..x7/:a; vendors/w1..w5/:b;

links(warehouses,vendors):cost,volume; endsets !目标函数;

min=@sum(links:cost*volume); !需求约束;

@for(vendors(J):

@sum(warehouses(I):volume(I,J))=b(J)); !产量约束;

@for(warehouses(I):

@sum(vendors(J):volume(I,J))a=1 1 1 1 1 1 1; b=1 1 1 1 1;

cost=2 15 13 1 8 10 4 14 15 7 9 14 16 13 8 7 8 11 9 4 8 4 15 8 6 12 4 6 8 13 5 16 8 5 10; enddata end

附录三：

问题三Lingo运行程序，如下： model: sets:

si/1..7/; sj/1..5/;

sij(si,sj):c,x; endsets

data:

c=1 13 10 1 8 10 4 8 10 5 8 6 10 9 6 6 7 11 8 4 6 3 15 8 5 11 4 6 7 10 4 12 6 3 2; enddata

min = @sum(sij:c*x); @for(sij:@bin(x));

@for(sj(j):@sum(si(i):x(i,j))=1);

x(1,1)=0; x(1,4)=0; x(4,5)=0; x(5,2)=0; x(6,3)=0;

附录四：

问题四Lingo运行程序，如下：

model:

min=2*x11+15*x12+13*x13+1*x14+8*x15+10*x21+4*x22+14*x23+15*x24+7*x25+9*x31+14*x32+16*x33+13*x34+8*x35+7*x41+8*x42+11*x43+9*x44+4*x45+8*x51+4*x52+15*x53+8*x54+6*x55+12*x61+4*x62+6*x63+8*x+13*x65+5*x71+16*x72+8*x73+5*x74+10*x75+1*y11+13*y12+10*y13+1*y14+8*y15+10*y21+4*y22+8*y23+10*y24+5*y25+8*y31+6*y32+10*y33+9*y34+6*y35+6*y41+7*y42+11*y43+8*y44+4*y45+6*y51+3*y52+15*y53+8*y54+5*y55+11*y61+4*y62+6*y63+7*y+10*y65+4*y71+12*y72+6*y73+3*y74+2*y75;

x11+x21+x31+x41+x51+x61+x71=1; x12+x22+x32+x42+x52+x62+x72=1; x13+x23+x33+x43+x53+x63+x73=1; x14+x24+x34+x44+x54+x+x74=1; x15+x25+x35+x45+x55+x65+x75=1; x11+x12+x13+x14+x15<1; x21+x22+x23+x24+x25<1; x31+x32+x33+x34+x35<1; x41+x42+x43+x44+x45<1; x51+x52+x53+x54+x55<1; x61+x62+x63+x+x65<1; x71+x72+x73+x74+x75<1;

y11+y21+y31+y41+y51+y61+y71=1; y12+y22+y32+y42+y52+y62+y72=1; y13+y23+y33+y43+y53+y63+y73=1; y14+y24+y34+y44+y54+y+y74=1; y15+y25+y35+y45+y55+y65+y75=1; y11+y12+y13+y14+y15<1; y21+y22+y23+y24+y25<1; y31+y32+y33+y34+y35<1; y41+y42+y43+y44+y45<1; y51+y52+y53+y54+y55<1; y61+y62+y63+y+y65<1; y71+y72+y73+y74+y75<1; x11+y11<1; x12+y12<1; x13+y13<1; x14+y14<1; x15+y15<1; x21+y21<1;

x22+y22<1; x23+y23<1; x24+y24<1; x25+y25<1; x31+y31<1; x32+y32<1; x33+y33<1; x34+y34<1; x35+y35<1; x41+y41<1; x42+y42<1; x43+y43<1; x44+y44<1; x45+y45<1; x51+y51<1; x52+y52<1; x53+y53<1; x54+y54<1; x55+y55<1; x61+y61<1; x62+y62<1; x63+y63<1; x+y<1; x65+y65<1; x71+y71<1; x72+y72<1; x73+y73<1; x74+y74<1; x75+y75<1; end