工作人员的最优时间分配问题的研究
【摘要】
由于每个人的工作效率不同，导致不同的分配方式会有不同的时间开销。
本文建立了0-1规划模型对最少时间成本下的工作人员分配问题进行了研究。
本问题中首先确定第i人做或者不做第j工作将问题定量化，再以全部的工作时间为目标函数，最后使用Lingo对目标函数求最优解得出最终结果。
关键词：最少时间最优解时间分配0-1模型Lingo 线性规划
一、问题重述
设有人员12个，工作10件，且一人做一个工作，第i人做第j件工作的时间（或费用）c（取值见表1.1），问：如何分派可使工作时间（或总费用）最少。
为
ij
表1.1 c ij
二、问题假设
1.每个人都能在自己的花销时间内完成工作。
2.每个人只能做一个工作，即既不能同时做两个工作，也不能在一个工作做完后再做其他工作。
3.每件工作都必须有人做，且只能由一个人独立完成。
4.各个工作之间没有相互联系。
即一个工作的完成与否，不受另一个工作的制约。
三、符号说明
z：完成所有工作的总时间
x：第i人做第j件工作的时间
ij
四、问题分析、模型的建立与求解
1.问题的分析
最少时间（即人力资源成本）是最大利润一个很有参考价值的数据，往往需要利用数学建模的方法对其进行定量的分析，首先确定第i人做或者不做第j工作将问题定量化，再以全部的工作时间为目标函数，最后对目标函数求最优解得出最终结果。
2.模型的建立
设：
10...3,2,112...3,2,1{.1.0===
j i x ij j i j i ，件工作
人做第第件工作人不做第第 则工作时间为： ∑∑===12110
1z i ij j ij x c
限定条件为：
12...3,2,11101=≤∑=i x
j ij ，（即每个人只能做一个工作（假设2），可以小
于1是因为人比工作多，允许有人空闲）
10...3,2,11121i ==∑=j x
ij ，（即每个工作都要有人做，且只能由一个人做
（假设3））
10or x ij =
不能完成任务的人：
,,
,
,,,,,
,
,,
,,,,
4
,122,129,1099989610,77865575110,448474326=x x x x x x x x x x x x x x x x
3.模型的求解
化为标准形式如下：
∑∑===12110
1
z Min i ij j ij x c
s.t. 12...3,2,11101=≤∑=i x
j ij ，
10...3,2,11121i ==∑=j x
ij ，
10
or x ij =
,,
,
,,,,,
,
,,
,,,,
4
,122,129,1099989610,77865575110,448474326 x x x x x x x x x x x x x x x x
将上述条件，以及数据写入Lingo 中，编写程序求解。
源程序及输出结果详见附件。
4.结果分析
程序调试完成后，得到结果如下：
X( 1, 7) =
1.000000 X( 2, 10) =
1.000000 X( 5, 5) =
1.000000 X( 6, 6) =
1.000000 X( 7, 4) =
1.000000 X( 8, 2) =
1.000000 X( 9, 1) =
1.000000 X( 10, 3) =
1.000000 X( 11, 8) =
1.000000 X( 12, 9) = 1.000000
最小时间为：
z = 23
将工作分派情况与表1.1，即每个人的花费时间作对比，如下表（表1.2）：
表1.2 加粗的单元格即为选择做第j件事的第i个人
现在我们可以看到，最优解基本上是集中于取值较低（即花费时间较少）的人上面，受假设2（每个人只能做一个工作，即既不能同时做两个工作，也不能在一个工作做完后再做其他工作）的约束，每一横行只能选一个格子（即每个人只能做一件工作），可不选。
模型再受到假设3的约束（每件工作都必须有人做，且只能由一个人独立完成）），所以，每一竖行必须且只能选一个格子。
对照约束条件与表1.2，我们发现有些事件取值并非该人最高效事件（如第10人），但为满足约束，所以程序从全局高度对结果进行了取舍。
由表1.2，我们可以推断，在没有计算机辅助，或待求解量较少且对结果要求不高的情况下，可以采取“画格子”的方式粗糙地求解类似问题。
但也可从思维过程看出在计算机辅助的情况下节省了大量的较繁运算。
五、模型的评价
优点
模型明了简洁，具有相当的可推广性。
缺点
模型考虑的影响因素较少。
六、模型的推广与改进
在该问题的求解中，考虑的方面较为简略，还有很多因素可以考虑。
例如在可以协作的情况下，各个人做完了分配工作后可以再其他工作的情况下，以及该情形下他们不同的休息时间，各道工作有关联时的情况等因素。
但在单一工作及简单考虑情况下，该模型具有较大的生存空间，只需改动少许数值即可推广应用。
七、附件
Lingo源程序：
model:
sets:
si/1..12/;
sj/1..10/;
sij(si,sj):c,x;
endsets
data:
c=2 5 8 3 6 12 2 4 6 7
5 4 7 2 2 0 7 3 3 1
7 23 5 4 7 4 9 6 4 6
7 9 0 5 8 8 0 0 4 0
0 8 3 2 1 7 0 8 7 9
5 9
6 8 0 3 4
7
8 7
5 5
6 4
7 5 9 0 5 0
2 2 8 8 2 9 4
3 8 5
3 5 5 7 3 0 8 0 0 6
8 7 4 3 7 5 9 8 0 3
3 8 8 1
4 8 2 1 9 5
3 0 5 0 5 7 2 8 2 10;
enddata
min = @sum(sij:c*x);
@for(sij:@bin(x));!限制x为0-1变量;
@for(sj(j):@sum(si(i):x(i,j))=1); !（即每个工作都要有人做，且只能由一个人做（假设3））;
@for(si(i):@sum(sj(j):x(i,j))<=1); !（即每个人只能做一个工作（假设2），可以小于1是因为人比工作多，允许有人空闲）;
!强制等于0的量。
即无法完成某项工作的人;
x(2,6)=0;
x(4,3)=0; x(4,7)=0; x(4,8)=0; x(4,10)=0;
x(5,1)=0; x(5,7)=0;
x(6,5)=0;
x(7,8)=0; x(7,10)=0;
x(9,6)=0; x(9,8)=0; x(9,9)=0;
x(10,9)=0;
x(12,2)=0; x(12,4)=0;
Lingo求解输出结果：
Global optimal solution found at iteration: 21
Objective value: 23.00000
Variable Value Reduced Cost
X( 1, 7) 1.000000 2.000000
X( 2, 10) 1.000000 1.000000
X( 5, 5) 1.000000 1.000000
X( 6, 6) 1.000000 3.000000
X( 7, 4) 1.000000 4.000000
X( 8, 2) 1.000000 2.000000
X( 9, 1) 1.000000 3.000000
X( 10, 3) 1.000000 4.000000
X( 11, 8) 1.000000 1.000000
X( 12, 9) 1.000000 2.000000
【参考文献】
[1] 姜启源,谢金星,叶俊. 数学模型[M].北京:高等教育出版社,2003.8。