Abstract: Aim at the disadvantages of operation complex, time-consuming and low accuracy of the existing algorithms of solving multidimensional assignment problem, the method which is originally applied to search the optimal matching in bipartite graph is extended. Furthermore, the methods, such as test assignment, saturated road adjustment and augmented road adjustment, are employed to search the optimal solution of multidimensional assignment problem. On this basis, the mixed algorithms of the minimum zero-surface preferred assignment and random test assignment are proposed in this paper. In addition, the effectiveness of mixed algorithms is proved theorically, and its temporal and spatial complexities are analyzed. Meanwhile, according to comparing the computing time of solving the cost matrix involving different amount of initial zero elements by the two mixed algorithms, and comparing time consuming and accuracy of solving the multidimensional assignment problem using mixed algorithms, Lagrangian relaxation algorithm and pruning algorithm, the applicability and high effectiveness of the two mixed algorithms are proved respectively. Finally, the validity of the two mixed algorithms is verified by an numerical example.

Key words: operations research, mixed algorithm, adjustment of augmented road, multidimensional assignment

摘要： 针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。

关键词: 运筹学, 混合算法, 增广路调整, 多维分配