文档介绍：指派问题(含非标准指派问题)
2
第五章整数规划
§1 整数规划的数学模型及特点
要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。
其模型为：
Max(或min)z=
0，=0分别称为独立零元素。｛=0，=0，=0，=0｝也是一个独立零元素组，而｛=0，=0，=0，=0｝就不是一个独立零元素组，因为=0与=0这两个零元素位于同一列中。
根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的=1，其余的=0。就可找到指派问题的一个最优解。
就上例中
X（1）= ，
就是一个最优解。同理
9
X（2）=
也是一个最优解。
但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。
定理2 效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
我们不证它，说一下意思：
例3：已知矩阵
C1= ，C2= ，C3=
分别用最少直线去覆盖各自矩阵中的零元素：
C1= ， C2= ， C3=
10
可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4，4，5。
匈牙利法求解步骤：
我们以例题来说明指派问题如何求解：
例4 给定效率矩阵
C=
求解该指派问题。
解：ⅰ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。
min

列变换
行变换
7
9
4
2
C=
11
=
Min 0 0 4 2
这样得到的新矩阵中，每行每列都必然出现零元素。
ⅱ）用圈0法求出新矩阵中独立零元素。
（1）进行行检验
对进行逐行检验，对每行只有一个未标记的零元素时，用○记号将该零元素圈起。然后将被圈起的零元素所在的列的其它未标记的零元素用记号×划去。如中第2行、第3行都只有一个未标记的零元素，用○分别将它们圈起。然后用×划去第1列其它未被标记的零元素（第2列没有），见
=
在第i行只有一个零元素=0时，表示第i人干第j件工作效率最好。因此优先指派第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j项工作不再指派其它人去干（即使其它人干该项工作也相对有最好的效率）。
13
重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。
本题中第1行此时也只有1个未被标记的零元素。因此圈起中第1行第4列的零元素，然后用×划去第4列中未被标记的零元素。这是第4行也只有一个未被标记的零元素，再用○圈起，见
=
（2）进行列检验
与进行行检验相似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素，用记号○将该元素圈起，然后技改元素所在行的其他未被标记的零元素打×。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。
这时可能出现以下三种情况：
每一行均有圈0出现，圈0的个数m恰好等于n,即m=n.
存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。
13
不存在未被标记过的零元素，当圈0的个数m< n.
ⅲ) 进行试指派
若情况出现，则可进行试指派：令圈0为止的决策变量取值为1，其他决策变量取值均为零，得到一个最优指派方案，停止计算。
上例中得到后，出现了情况，可令=1，=1，=1，=1，其余=0。即为最优指派。
若情况出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记○，即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列检验，可能出现情况或，出现情况则由上述得到一最优指派，停止计算。
若情况出现，则要转入下一步。
ⅳ）：做最少直线覆盖当前所有零元素。
我们还以例12来说明过程：
已知例12指派问题的系数矩阵为：

14
先对各行元素分别减去本行的最小元素，然后对各列也如此，即
列变换
行变换
C =
此时，中各行各列都已出现零元素。
为了确定中的独立零元素，对加圈，即