摘要 : 指派问题通常分成平衡指派问题和非平衡指派问题.本文分别讨论了平衡指派问题中的伏格尔法和匈牙利法，非平衡指派问题中的全局搜索算法和转化为平衡指派问题的求解方法.通过分析比较，突出了匈牙利法在企业人员指派优化应用中的重要性，并给出了匈牙利法的LINGO程序.63114

毕业论文关 键 词：运筹学，指派问题，伏格尔法，匈牙利法，全局搜索法，LINGO

Abstract: The assignment problems were generally pided into balanced assignment problem and unbalanced assignment problem. We respectively discussed the Vogel Method and Hungarian method in the balanced assignment, the global search method in the unbalanced assignment, and the solving methods translated into balanced assignment. Through the comparative analysis, it highlighted the importance of Hungarian method in the assignment optimization application of enterprise personnel, and gave the Lingo program in Vogel Method. 

Keywords：operational research, assignment problem, Vogel method, Hungarian method, overall situation searching, LINGO

1  引言 4

2  指派问题的数学模型 5

2.1  平衡指派的数学模型 5

2.2  非平衡指派的数学模型 5

3  平衡指派问题的解法 6

3.1  伏格尔法 6

3.2  匈牙利法 8

4  非平衡指派问题的解法 9

4.1  全局搜索算法 9

4.2  转化法 12

5  匈牙利法的LINGO程序 16

6  允许协助条件下工作时间较短的任务安排 22

结  论 24

参考文献 25

致  谢 26

1  引言

随着我国经济的快速发展，企业数量的不断增加，企业之间竞争日趋激烈.许多拥有先进技术的企业在竞争中处于下风，归根究底是企业的管理方法落后导致产品成本过高，使企业的生存和发展受到严峻挑战.所以为了降低企业的成本，提高企业的效益，运筹学在企业人员指派优化中得到了越来越广泛的应用.

许多企业的管理部门在企业的生产安排中都会面临这样的问题：有n个人需要完成n项任务，每个人都可以胜任每一项任务且每项任务只能由一个人完成，但员工素质的不同,导致了完成每一项任务所需时间的不同，则如何科学合理的指派人员以使企业的总效益最高.这类问题就称之为指派问题[1].

人员数和任务数相等的平衡指派[2]是最基本的指派问题.针对平衡指派问题有很多解决方法，伏格尔法是其中的一种，伏格尔法常被用来解决运输问题，由于指派问题可以看作是产销都是同一地点的运输问题，所以指派问题可以看作为一类特殊的运输问题[3].伏格尔法虽然计算比较容易且步骤较少，但是有的时候初始解只是很接近最优解，还需要在闭合回路中进行调整，所以应用不是特别广泛.目前研究的主流是在利用匈牙利法的基础上根据企业的实际情况及外部因素制定科学合理的指派方案.

限于实际情况，在指派过程中常常需要提出一些新的约束条件[4]，从而导致目标函数的变动、平衡指派问题模型的改动，这就出现了各种不同的非平衡的指派问题.非平衡指派问题是目前研究的重点.对于非平衡指派问题的求解，可以用全局搜索算法，但是全局搜索算法[5]计算比较量大，比较适合用来编写程序算法，所以一般都会把非平衡指派问题转化为平衡指派问题进行求解，转化方法的本质是通过加边法对效率矩阵进行转化，然后用匈牙利法对其进行求解.源[自[优尔^`论`文]网·www.youerw.com/