论文总字数：23225字

摘 要

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

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

Abstract: The assignment problems were generally divided 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]计算比较量大，比较适合用来编写程序算法，所以一般都会把非平衡指派问题转化为平衡指派问题进行求解，转化方法的本质是通过加边法对效率矩阵进行转化，然后用匈牙利法对其进行求解.

一般的指派问题中，按照匈牙利法得到的最优解^[6]，每个人都可以分配到一项任务，在这种指派下可使企业的总效益最高.但是在团队合作中，经常会由于每个人的任务、技术能力的不同，影响任务的完成的先后顺序，从而导致时间的浪费.当今这个既竞争又合作的社会普遍要求充分利用有限的资源，加强合作，提高工作效率，比如某大型机械设备出现故障，需要在最短的时间内完成抢修.因此，在允许协助条件^[7]下，研究工作时间较短的任务安排就显得很有意义.

总之，运筹学在企业人员指派优化中的应用作为一个综合性多学科交叉的科学分支^[8].贯穿了企业管理部门人事安排的全过程，它在企业的生产、运输、管理等各个方面都具有重要的作用，运筹学在企业指派优化中的应用为管理部门人事安排决策服务提供科学合理的依据.

2 指派问题的数学模型

指派问题也称分配问题，是一种特殊的整数规划问题.由于实际情况不同，从而产生了各种各样的分配方案，如果完成任务是以效率为前提的，考虑的方案是如何使目标值极大化.反之，如果完成任务是以资源消耗为前提的，则要考虑的是如何分配，使目标值极小化.虽然上述说法不一样，但由于相似的性质，同一个数学模型都可以进行求解.

2.1 平衡指派的数学模型

许多管理部门经常面临这样的问题：有n项工作要完成，恰有n个人可以完成这项工作. 但是由于工作的性质及人员的专业水平的不同，各人的效率就会有差别，因此成本也会有差别. 在要求一人只能完成一项工作且一项工作只能由一个人完成的平衡指派的情况下，如何安排人员使总的效率最高.

设用表示指派第i个人去完成第项任务时所用的时间，定义决策变量：

则指派问题可转化为0-1线性规划问题模型如下：

2.2 非平衡指派的数学模型

非平衡指派问题指的是任务数和人员数不等的情况，同样用表示指派第人去完成第项任务所用的时间，定义决策变量：

则指派问题的数学模型为：

3 平衡指派问题的解法

运筹学中一般的线性规划问题可以用单纯形法来求解，然而有很多的线性规划问题，由于它们约束条件的存在使得它们具有特殊的矩阵形式，可以找到比单纯形法更简单的操作方法，从而可大量的节约计算的时间，伏格尔法是针对运输问题常用的解决方法，指派问题可以看作是产销量都是n的产销平衡的运输问题，所以指派问题就是一种特殊的运输问，伏格尔法可以用来对其进行求解.

3.1 伏格尔法

伏格尔法又称差值法，是最小元素法的优化.最小元素法只从局部观点考虑就近供应，可能会造成总体的不合理，而伏格尔法的基本思路是从表中分别找出每行与每列的最小的两个元素之差，在从差值最大的行或列中找出最短时间,确定指派方案.指派问题中的具体伏格尔法步骤如下：

（1）分别计算出表格中各列各行的最小值和次最小值的差；

剩余内容已隐藏，请支付后下载全文，论文总字数：23225字