基于区间数的瓶颈指派问题及应用

衡阳市第八中学 黄诗琦

1 引言

指派问题的研究是目前规划论中的一个活跃内容，其中一种常见的指派问题是：指派n个人去完成n项工作，每个人必须做一项工作，也只能做一项工作；每项工作必须有一人去做，也只能由一人做，求使总效率最大的分配方案。这类指派问题可以用匈牙利法求解。近年来有人对这类指派问题作了一些有意义的推广，如“一事多人”和“一人多事”的指派问题。相关研究还给出了分配任务数不超过总人数也不超过总任务数的指派问题，即从m个人中派出k个人去干n项工作中的k项工作。这些问题的推广都具有一定的实际应用背景。

另一类指派问题是：指派n个人去完成n项工作，每个人必须做一项工作，也只能做一项工作；每项工作必须有一人去做，也只能由一人做。第 i 个人做第 j 项工作所需要的时间为 cij（i =1,2,…,n；j =1,2,…,n），求使任务全部完工的时间最短的分配方案。其数学模型为：

例如，某供电系统有数处发生故障急需停电检修，而供电系统只有在所有故障都排除后才能恢复供电，如何分配检修任务才能使供电系统停电检修时间最短的问题就属于该类指派问题。

上述模型所研究的问题是在第 i 个人完成第 j 项工作的效率 cij为已知的条件下给出的。实际中由于问题存在许多随机性、模糊性或信息不完全性等不确定因素，要完全确定第 i 个人完成第 j 项工作的效率 cij是非常困难的，相关文献中研究了 cij不能完全确定，但可以判断 cij所在区间的条件下，求总效益最大的指派问题。……