李承耕 刘波

【摘要】针对指派问题中最小化问题的匈牙利解法，通过最大元素法来处理最大化指派问题.

【关键词】指派问题；匈牙利法；最小元素；最大元素

【中图分类号】0223

【文献标识码】獳オ

1.指派问题的数学模型

求解n个资源分配到n个任务的活动中，为使得总成本最小，如何完成对资源的分配.

设C﹊j为分配资源i到j任务所消耗的成本，则：

玀inz=А苙[]i=1ИА苙[]j=1c﹊j獂﹊j.其中x﹊j=0 i资源不给 j活动，

1 i资源分给 j活动，お﹊=1,2,…,n,j=1,2,…，n.

А苙[]i=1x﹊j=1(j=1,2,…，n) А苙[]j=1x﹊j=1(i=1,2,…，n)

2.匈牙利法处理指派问题的基本步骤

（1)使指派问题的系数矩阵在各行各列都出现0元素.①从系数矩阵的每行都减去该行的最小元素.②再从系数矩阵的每列减去该列的最小元素.

(2）若效率矩阵的行列数为n,想办法找到n个不同行，不同列的0元素，即n个独立的0元素，用最少的直线将所有的0元素划去，若直线数量刚好等于n个，则n个独立的0元素就找到，否则就转入下一步.

(3）在直线没有划去的元素中，选一个最小的，在没有划去的元素的各行中均减去这个最小元素，为保持原来的0元素不变，在0元素对应的列中加上该元素.

3.最大化问题的两种处理方法

（1）将最大化问题转化为最小化问题，设原来的效益矩阵为C=(C﹊j)，我们可以作一个新的效益矩阵C′=M-C﹊j，这里M比C中的最大元素要大，则C′的最小指派即为C的最大指派.

（2）直接在每行或每列中减去该行列的最大元素，然后在效益矩阵中找到n个独立的0元素，这里的0元素即是最大元素，注意n个独立的0元素所在位置是处在不同行、不同列的位置，一旦……