文档介绍：精品范文模板可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
撰写人：___________日期：___________
(6)
(9)
(12)
(8)
(7)
1
A4
(6)
(7)
(14)
(6)
(10)
1
A5
(6)
(9)
(12)
(10)
(6)
1
所选的公司数
1
1
1
1
1
5
当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。
匈牙利解法原理：
虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。1955年，库恩（）提出了匈牙利法。
定理1：设指派问题的效率矩阵为C= ，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可正可负），得到新的效率矩阵，则以为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.
证明：设式（）～（）为原指派问题。现在C矩阵的第k行个元素东减去同一常数t,
==+=+
=+-t=-t·1=Z-t
因此有
Min =min(Z-t)=minZ-t
而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。
推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。
证明：结论是显然的。只要反复运用定理1便可得证。
当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵中必然出现一些零元素。设=0，从第i行来看，它表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，这个0表示第j项工作以第i人来干效率(相对)最高。
精品范文模板可修改删除

免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。
例2: 已知
C=
则｛=0，=0，=0，=0｝是一个独立零元素组，=0，=0，=0，=0分别称为独立零元素。｛=0，=0，=0，=0｝也是一个独立零元素组，而｛=0，=0，=0，=0｝就不是一个独立零元素组，因为=0与=0这两个零元素位于同一列中。
根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的=1，其余的=0。就可找到指派问题的一个最优解。
就上例中
X（1）= ，
就是一个最优解。同理
X（2）=
也是一个最优解。
但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。
定理2 效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
我们不证它，说一下意思：
例3：已知矩阵
C1= ，C2= ，C3=
精品范文模板可修改删除

免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
分别用最少直线去覆盖各自矩阵中的零元素：
C1= ， C2= ， C3=
可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4，4，5。
匈牙利法求解步骤：
我们以例题来说明指派问题如何求解：
例4 给定效率矩阵
C=
求解该指派问题。
解：ⅰ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。
min

列变换
行变换
7
9
4
2
C= =
Min 0 0 4 2
这样得到的新矩阵中，每行每列都必然出现零元素。
ⅱ）用圈0法求出新矩阵中独立零元素。
（1）进行行检验
对进行逐行检验