文档介绍：-
. z
第五章整数规划
§1 整数规划的数学模型及特点
要求一局部或全部决策变量必须取整数值得规划问的特殊性质，有效地减少计算量。1955年，库恩〔〕提出了匈牙利法。
-
. z
定理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。就可找到指派问题的一个最优解。
-
. z
就上例中
*〔1〕=，
就是一个最优解。同理
*〔2〕=
也是一个最优解。
但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。
定理2 效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
我们不证它，说一下意思：
例3：矩阵
C1=，C2=，C3=
分别用最少直线去覆盖各自矩阵中的零元素：
C1=， C2=， C3=
可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4，4，5。
匈牙利法求解步骤：
我们以例题来说明指派问题如何求解：
例4 给定效率矩阵
C=
-
. z
求解该指派问题。
解：ⅰ〕变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。
min
列变换
行变换
7
9
4
2
C==
Min 0 0 4 2
这样得到的新矩阵中，每行每列都必然出现零元素。
ⅱ〕用圈0法求出新矩阵中独立零元素。
〔1〕进展行检验
对进展逐行检验，对每行只有一个未标记的零元素时，用○记号将该零元素圈起。然后将被圈起的零元素所在的列的其它未标记的零元素用记号×划去。如中第2行、第3行都只有一个未标记的零元素，用○分别将它们圈起。然后用×划去第1列其它未被标记的零元素〔第2列没有〕，见
=
在第i行只有一个零元素=0时，表示第i人干第j件工作效率最好。因此优先指派第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j项工作不再指派其它人去干〔即使其它人干该项工作也相对有最好的效率〕。
重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。
此题中第1行此时也只有1个未被标记的零元素。因此圈起中第1行第4列的零元素，然后用×划去第4列中未被标记的零元素。这是第4行也只有一个未被标记的零元素，再用○圈起，见
=
〔2〕进展列检验