匈牙利法中试指派的标记法

徐玲，肖双喜

匈牙利法中试指派的标记法

徐玲，肖双喜

介绍匈牙利法的数学模型及基本步骤，对匈牙利法中试指派现有的改进方法进行了探讨，提出了新的改进方法——标记法。经验证，标记法是有效而简单易用的方法。

指派问题；匈牙利法；标记法

指派问题属于0-1整数规划问题，是一种特殊的线性规划问题，可以用求解线性规划的单纯形法求解，但是因为其变量过多，用单纯形法求解就显得非常复杂。库恩（W.W.Kuhn）运用匈牙利数学家康尼格(D.Konig)的一个定理“系数矩阵中独立0元素的最多个数与覆盖所有0元素的最少直线数相等”，于1955年提出了匈牙利方法［1］。匈牙利方法是求解指派问题的经典算法，但是其也存在一些不足，如计算过程比较复杂。国内学者也运用不同的思想给出了指派问题的一些解法，如叶微（2003）［2］、高兴佑（2008）［3］、贾春玉（2004）［4］等运用伏格尔法的基本思想提出了指派问题的伏格尔算法；高俊琦（2000）［5］提出了表上作业法；李苏北（2000）［6］提出了动态规划算法；孔繁利（2001）［7］提出了网络图算法，还有很多新的方法在不断地被提出。这些算法各有不同的优点，但也有其缺点，如有的算法比匈牙利法还要繁琐，有的算法不一定能得到最终的最优解。在这些求解指派问题的解法中，匈牙利方法仍然是大家推崇的最经典的解法。本文对匈牙利法中试指派过程给出了改进方法——标记法。

一、匈牙利法的方法介绍

（一）匈牙利法数学模型

该问题的一般提法是某单位有n项工作需要完成，现恰好有n个人可以完成这n项工作，由于每个人的专业水平不同，各自完成各项工作的成本为cij，要求一人只能完成一项工作，一项工作只能安排一人完成，如何安排使总的效率最高（或者所需的总费用最省）。……