匈牙利法

匈牙利法是一件大的事物若除去一件小的 事物 ，对这件事没有多大影响。1955年，库恩(W．W．Kuhn)利用匈牙利数学家康尼格(D．Konig)的关于矩阵中独立“0”元素的定理，提出了求解指派问题的一种方法，习惯上称之为匈牙利法。 （1）若从效率 矩阵 (cij)的行（或列）的各元素中分别减去该行（或列）的最小元素后得到一个新矩阵（bij）,则以（bij）为效率矩阵的指派问题与原问题有相同的最优解。 经过上述变换后，（bij）中的每行和每列都至少含有一个0元素，称位于不同行不同列的0元素为独立的0元素。 （2）若（bij）有n个独立的0元素，由此可得一个解矩阵，方法为在X中令对应于（bij）的0元素位置的元素为1，其它位置的元素为0，则X为 指派问题 的最优解。 （3）矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。 匈牙利法的算法步骤如下： (1)对指派问题的系数矩阵进行变换，使每行每列至少有一个元素为“0”． ①让系数矩阵的每行元素去减去该行的最小元素； ②再让系数矩阵的每列元素减去该列的最小元素。 (2)从第一行开始，若该行只有一个零元素，就对这个零元素加括号，对加括号的零元素所在的列画一条线覆盖该列，若该行没有零元素或者有两个以上零元素(已划去的不算在内)，则转下一行，依次进行到最后一行。 (3)从第一列开始，若该列只有一个零元素。就对这个零元素加括号(同样不、考虑已划去的零元素)。再对加括号的零元素所在行画一条直线覆盖该列。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。 (4)重复上述步骤(1)和(2)可能出现3种情况： ①效率矩阵每行都有加括号的零元素，只要对应这些元素令 就找到了最优解。 ②加括号的零元素个数少于m，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素加一个括号，然后对所有加括号的零元素所在行(或列)画一条直线，同样得到最优解。 ③矩阵中所有零元素或被划去，或加上括号．但加括号的零元素少于m，这时转入(5)． (5)按定理进行如下变换： ①从矩阵未被直线覆盖的数字中找出一个最小的k； ②当矩阵中的第i行有直线覆盖时，令Ui=0；无直线覆盖时。令Ui=K； ③当矩阵中的第j列有直线覆盖时，令Vj=-K；无直线覆盖时，令Vj=0； ④令原矩阵的每个元素Aij分别减去Ui和Vj． (6)回到(2)，反复进行，直到矩阵的每一行都有一个加括号的零元素为止。即找到最优分配方案。[1] 在实际的任务分配中，还可能出现人员（或设备）数与任务数不相等的情况，而且要求每个人员只先完成一件任务（在人员数少于任务数时），或者有些人员可暂不安排任务（在人员数多余任务数时），可称这样的问题为不平衡的指派问题，此时，可通过虚拟人员或虚拟任务使之转化为一般（平衡）的指派问题，即在原矩阵中增加一些行或者列，使之成为方阵，在极小型问题中所增加的元素应充分的大，如为原矩阵中最大的元素的值，而在极大型问题中增加的元素应足够的小。如可取零值。

匈牙利法师表上作业法的一种。匈牙利法是为解决所谓分配问题，指派问题等数学问题的方法。这类问题的一般性叙述为：有n个问题要分配给n个人去完成。第i个人完成第j项任务的成本为Cij。匈牙利法，是求解及小型优化方向为极小指派问题的一种方法，这种方法最初由w.w.kuhn提出，后经改进而形成，解法基于匈牙利数学家D.K?nig给出的一个定理而得名。

应用匈牙利法的注意事项：匈牙利法的计算过程不唯一，最终矩阵的形式也不唯一，但最终配置结果一定相同。根据查询相关公开信息显示：匈牙利法是一件大的事物若除去一件小的事物，对这件事没有多大影响，1955年，库恩(W．W．Kuhn)利用匈牙利数学家康尼格(D．Konig)的关于矩阵中独立0元素的定理，提出了求解指派问题的一种方法，习惯上称之为匈牙利法。

---