第五章 匈牙利法与最佳指派问题

摘要在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。

然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指派问题。

指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。

这类问题研究的是n个人执行n项任务，执行每项任务的人数以及总的指派人项数均有限制，要求最优指派。

在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个0-1整数规划问题，本文先对指派问题进行陈述，引出对实际问题的求解。

在指派问题的背景、描述中充分理解该问题，先运用匈牙利算法实现指派问题，然后再建立一个0-1整数规划模型，并运用matlab和lingo编译程序对问题进行编译，运用软件解决模型问题，最终实现指派问题在实际问题中的运用。

通过运用匈牙利算法和0-1整数规划同时对指派问题求解，我们发现用0-1整数规划的方法来求解可以更简单，也更方便程序的阅读和理解。

与此同时，我们还对0-1整数规划问题由整数数据深入研究到小数数据。

最后通过实例来说明运用matlab，lingo编译程序来解决整数规划问题的简便和有效性。

关键词：指派问题；匈牙利算法；0-1整数规划；matlab模型；lingo模型AbstractIn business, the company's operations and management, managers always want the best distribution of the staff to maximize their efficiency, reduce costs and improve efficiency. However, if there is no scientific method is difficult to achieve optimal management, which we introduced the assignment problem. Multi-assignment problem is to get the project working hours at least, and in many cases people do not care about how much the total project work, but only care about whether the project can be completed within the shortest possible time, that lasted for at least the assignment problem. Such problems is the n individual execution of tasks n, the number of people to perform each task and assign the total number of items are restricted to two people, requiring the optimal assignment. Integer programming in operations research for solving the assignment problem is usually solved by Hungarian algorithm, but the assignment problem can be reduced to a 0-1 integer programming problem, this paper first to make a statement on the assignment problem, leads to the solution of practical problems. Assignment problem in the background to fully understand the problem description, the first assignment problem using Hungarian algorithm, and then a 0-1 integer programming model and compiler using matlab and the lingo of the problem to be compiled using the software solution model problem Ultimately in the assignment of the application in practical problems. By using the Hungarian algorithm and the 0-1 integer programming to solve assignment problems simultaneously, we found that 0-1 integer programming method to solve a more simple and easier to read and understand the program. At the same time, we also 0-1 integer programming problem in-depth study by the integer data to a decimal data. Finally, an example to illustrate the use of matlab, lingo compiler to solve the integer programming problem is simple and effective.Keywords:assignment problem; Hungarian algorithm; 0-1 integer programming;matlab model; lingo model目录1. 问题陈述 (1)2. 指派问题的背景 (1)3. 指派问题的描述 (1)3.1 指派问题的一般形式 (1)3.2 问题的数学模型一般形式 (2)3.3 目标函数极大化的指派问题 (2)4．指派问题实现 (3)4.1 匈牙利算法 (3)4.1.1 匈牙利算法的理论基础 (3)4.1.2 匈牙利算法的实现步骤 (3)4.1.3 匈牙利算法实现指派问题 (4)4.2 0-1整数规划 (5)4.2.1 模型假设 (6)4.2.2 模型建立 (6)4.2.3 模型求解 (7)5. 问题的深入（0-1整数规划） (10)5.1 模型建立 (10)5.2 模型求解 (11)5.2.1 用matlab求解问题 (11)5.2.2 用lingo求解问题 (12)6. 结论 (14)6.1 总结概论 (14)6.2 具体分工.................................. 错误！未定义书签。

3.2 求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig 提出的更为简便的解法—匈牙利算法。

算法主要依据以下事实：如果系数矩阵)(ij c C =一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵)(ij b B = ，则以C 或B 为系数矩阵的指派问题具有相同的最优指派。

利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B ，而最优解不变。

若能在B 中找出n 个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B 为系数阵的指派问题的最优解，从而也是原问题的最优解。

由C 到B 的转换可通过先让矩阵C 的每行元素均减去其所在行的最小元素得矩阵D ，D 的每列元素再减去其所在列的最小元素得以实现。

下面通过一例子来说明该算法。

例7 求解指派问题，其系数矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=16221917171822241819211722191516C 解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=06310157124074011B 再将第3列元素各减去1，得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=****20531005711407301B 以2B 为系数矩阵的指派问题有最优指派⎪⎪⎭⎫ ⎝⎛43124321 由等价性，它也是例7的最优指派。

有时问题会稍复杂一些。

例8 求解系数矩阵C 的指派问题⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=61071041066141512141217766698979712C 解：先作等价变换如下∨∨∨⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡→⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡----- 2636040*08957510*00*0032202*056107104106614151214121776669897971246767 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但5=n ，最优指派还无法看出。

指派问题匈牙利算法最大值
匈牙利算法(匈牙利算法,也被称为“插入-删除算法”或“排序算法”)是一种整数排序算法,在指派问题中可以将一个整数数组按照一定规则排序,使得所有指派中最大的元素出现的位置都不相同。

以下是匈牙利算法在解决指派问题的最大值问题的步骤:
1. 将数组分为两个部分,左半部分尽可能地小,右半部分尽可能地大。

2. 从右半部分开始,将一个元素与它的指派对象的最大值进行
比较。

如果两个元素之间的指派关系不符合要求,就将它们交换位置。

3. 接下来,从左边半部分开始,将一个元素与它的指派对象的最大值进行比较。

如果两个元素之间的指派关系不符合要求,就将它们交换位置。

4. 重复步骤2和步骤3,直到左半部分的最大值与右半部分的最大值相等。

5. 在最右半部分找到最大的元素,将它与左半部分的最大值交换。

6. 重复步骤1到步骤5,直到数组中的所有元素都被排序。

匈牙利算法的时间复杂度为O(nlogn),其中n为数组的长度。

在实际应用中,该算法通常用于小规模数据的排序,对于大规模数据的
排序则需要使用更高效的算法。

指派问题与匈⽛利解法指派问题概述：实际中，会遇到这样的问题，有n项不同的任务，需要n个⼈分别完成其中的1项，每个⼈完成任务的时间不⼀样。

于是就有⼀个问题，如何分配任务使得花费时间最少。

通俗来讲，就是n*n矩阵中，选取n个元素，每⾏每列各有1个元素，使得和最⼩。

如下图：指派问题性质：指派问题的最优解有这样⼀个性质，若从矩阵的⼀⾏(列)各元素中分别减去该⾏(列)的最⼩元素，得到归约矩阵，其最优解和原矩阵的最优解相同．匈⽛利法：12797989666717121491514661041071091.⾏归约：每⾏元素减去该⾏的最⼩元素502022300001057298004063652.列归约：每列元素减去该列的最⼩元素502022300001057298004063653.试指派：(1)找到未被画线的含0元素最少的⾏列，即，遍历所有未被画线的0元素，看下该0元素所在的⾏列⼀共有多少个0，最终选取最少个数的那个0元素。

(2)找到该⾏列中未被画线的0元素，这就是⼀个独⽴0元素。

对该0元素所在⾏和列画线。

50202230000105729800406365502022300001057298004063655020223000010572980040636550202230000105729800406365(3)暂时不看被线覆盖的元素，重复(1)(2)直到没有线可以画。

(4)根据(2)找到的0元素个数判断，找到n个独⽴0元素则Success，⼩于n个则Fail.（本例⼦中，n=5，可以看到，第⼀次试指派之后，独⽴0元素有4个，不符合）4.画盖0线：⽬标：做最少的直线数覆盖所有0元素，直线数就是独⽴0元素的个数。

注意：这跟3的线不同；不能⽤贪⼼法去画线，⽐如1 0 01 1 01 0 1若先画横的，则得画3条线，实际只需2条；若先画竖的，将矩阵转置后同理。

步骤3得出的独⽴0元素的位置50202230000105729800406365(1)对没有独⽴0元素的⾏打勾、(2)对打勾的⾏所含0元素的列打勾(3)对所有打勾的列中所含独⽴0元素的⾏打勾(4)重复(2)(3)直到没有不能再打勾(5)对打勾的列和没有打勾的⾏画画线，这就是最⼩盖0线。

匈牙利法解决人数与任务数不等的指派问题于凯重庆科技学院经济管理学院物流专业重庆沙坪坝区摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1，其次要求所需总时间最少，并且给出了该类问题的求解方法。

关键词：运筹学指派问题匈牙利算法系数矩阵解矩阵引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n 项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同；有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短，总费用最少，产生的总效益最佳。

我们把这类最优匹配问题称为指派问题或分配问题。

1.指派问题的解法——匈牙利法早在1955年库恩（w.w.ku.hn）就提出了指派问题的解法，该方法是以匈牙利数学家康尼格（koning）提出的一个关于矩阵中0元素的定理为基础，因此得名匈牙利法（The Hungonrian Method of Assignment）1.1匈牙利解法的基本原理和解题思路直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。

而指派问题的最优解又有这样的性质：若从系数矩阵C（ij）的一行（列）各元素都减去该行（列）的最小元素，得到新矩阵CB（ij），那么以CB（ij）为系数矩阵求得的最优解和原系数矩阵C（ij）求得的最优解相同。

由于经过初等变换得到的新矩阵CB（ij）中每行（列）的最小元素均为“○”，因此求原指派问题C（ij）的最优方案就等于在新矩阵CB（ij）中找出n个分布于不同行不同列的“○”元素（简称为“独立○元素”），这些独立○元素就是CB（ij）的最优解，同时与其对应的原系数矩阵的最优解。