数据决策：匈牙利解法指派问题

匈牙利解法是匈牙利数学家康尼克(D.konig)提出的,因此得名匈牙利解法(the Hungarian Method of Assignment)。

匈牙利解法的适用条件是:①问题求最小值,即目标函数要求为min;②人员数目与任务数目相等,即效率矩阵（cij）为n 阶方阵;③效率矩阵中所有元素非负,即cij≥0,且为常数。

匈牙利解法的理论依据是康尼克提出并证明的以下两个定理。

定理7.1 如果在指派问题的效率矩阵（cij）的每一行中分别减去(或加上)一个常数ui,在每一列中分别减去(或加上)一个常数vj,得到一个新的效率矩阵（bij）,则以（bij）为效率矩阵的指派问题与以（cij）为效率矩阵的指派问题具有相同的最优解。

定理7.2 若矩阵A 的元素可以分为零元素与非零元素两部分,则覆盖零元素的最少直线数等于位于不同行、不同列的零元素的最大个数。

匈牙利解法的基本步骤如下所述。

第一步:找出矩阵每行的最小元素,分别从各行中减去这个最小元素。

第二步:再找出矩阵每列的最小元素,分别从各列中减去这个最小元素。

第三步:经过上述两步变换后,矩阵的每行、每列至少都有了一个零元素,然后根据以下准则进行试指派,找出覆盖矩阵中所有零元素至少需要多少条直线。

①逐行检查:从第一行开始,若该行只有一个零元素,则用括号标记该零元素,划去与该零元素同在一列的其他零元素;若该行没有零元素或有两个以上零元素(已划去的不计在内),则转下一行,直到最后一行为止。

注意:括号的意义可以理解为该项任务已经分配给某人。如果该行只有一个零元素,说明只能有一个分配方案,划掉同列的其他零元素可理解为该任务已分配,此后不再考虑分配给他人。当该行有两个或更多的零元素时,不记括号,其理由是至少有两个分配方案,为使以后分配时具有一定的灵活性,故暂不分配。

②逐列检查:从第一列开始,若该列只有一个零元素,则用括号标记该零元素(同样不考虑已划去的零元素),再划去同行的其他零元素;若该列没有零元素或有两个以上零元素,则转下一列,并进行到最后一列。

③重复①、②两个步骤,可能会出现以下3种情况。

a.矩阵每行都有一个标记括号的零元素,显然,按照上述步骤得到的标记括号的零元素必然位于不同行、不同列,因此就得到了最优解。

b.有多于两行或两列存在两个以上零元素,这时可以从剩有零元素最少的行开始,比较这行零元素所在列中零元素的个数,选择零元素少的那列的零元素标记括号,划掉同行同列的其他零元素,然后重复上述步骤,直到所有零元素都做了标记。

c.矩阵中所有零元素都做了标记,或标记括号,或被划去,但标记括号的零元素个数小于m,这时就要找出能覆盖矩阵中所有零元素的最少直线的集合,步骤如下:

· 对没有括号的行打“√”;

· 对打“√”行上所有存在零元素的列打“√”;

· 再对打“√”列上有括号的行打“√”;

· 重复上两步,直到过程结束;

· 对没有打“√”的行划横线,对所有打“√”的列划垂线,这就得到覆盖矩阵所有零元素的最少直线数。(www.xing528.com)

第四步:当表中覆盖所有零元素的直线数小于m 时,得到的不是最优解,因此要继续对矩阵进行变换,其过程如下所述。

①从矩阵未被直线覆盖的所有元素中,找出最小元素;

②所有未被直线覆盖的元素都减去这个最小元素;

③覆盖线十字交叉处的元素都加上这个最小元素;

④只有一条直线覆盖的元素的值保持不变。

如此变换,可以得到新的效率矩阵。这一过程实际上运用了定理7.1,但变换后的效率矩阵将出现更多零元素,这样更易于标出m 个不同行、不同列的零元素。

第五步:去掉原来所有的标记,回到第三步,重新进行标记,直到得到最优解为止。

例7.8 甲、乙、丙、丁4个人要完成4项任务,规定每人只能分配一次任务,每项任务只能由一个人完成,每个人的工时如表7.20所示,如何分配任务可使总工时最少?

表7.20　每个人完成各项任务需要的工时

解 用匈牙利解法进行求解。第一步,通过行变换和列变换,得到新的效率矩阵,获得零元素:

第二步,最优性检验,逐行、逐列进行检查:

第三步,找出能覆盖矩阵中所有零元素的最少直线的集合:

第四步,非最优矩阵的变换。很显然,覆盖所有零元素的直线数是3,小于m=4,得到的不是最优解,因此,对矩阵进一步进行变换:

第五步,去掉原来所有的标记,重新进行最优性检验,直到得到最优解: