指派问题的匈牙利解法
指派问题的匈牙利解法
1、
把各行元素分别减去本行元素的最小值;然后在此基础上再把
每列元素减去本列中的最小值。
4 8 7 15 12
7 9 17 14 106 9 12 8 7
6 7 14 6 10
6 9 12 10 60 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 4
0 2 3 4 0
此时每行及每列中肯定都有0元素了。
2、 确定独立零元素,并作标记。
(1)、首先逐行判断是否有含有独立0元素的行,如果有,则按行继续处理;如没有,则要逐列判断是否有含有独立0元素的列,若有,则按列继续处理。若既没有含有独立0元素的行,也没有含有独立0元素的列,则仍然按行继续处理。
(2)在按行处理时,若某行有独立0元素,把该0元素标记为a,把该0所在的列中的其余0元素标记为b;否则,暂时越过本行,处理后面的行。把所有含有独立0元素的行处理完毕后,再回来处理含有2个以及2个以上的0元素的行:任选一个0做a标记,再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b。
(3)在按列处理时,若某列有独立0元素,把该0元素标记为a,把该0所在的行中的其余0元素标记为b;否则,暂时越过本列,处理后面的列。把所有含有独立0元素的列处理完毕后,再回来处理含有2个以及2个以上的0元素的列:任选一个0做a标记,再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b。 (4)、重复上述过程,即得到独立零元素(标记a的“0”)
0b 3 0a 11 8
0a 1 7 7 3
0b 2 3 2 1
0b 0a 5 0b 4
0b 2 3 4 0a
3、 若独立零元素等于矩阵阶数,则已经得到最优解,若小于矩阵阶数,则继续以下步骤:
(1)、对没有标记a的行作标记c (2)、在已作标记c的行中,对标记b所在列作标记c (3)、在已作标记c的列中,对标记a 所在的行作标记c (4)、对没有标记c的行划线,对有标记c的列划线
1773 \ 2321 \
\
4、 在未被直线覆盖的所有元素中找出一个最小元素(Xmin),未被直线覆盖的行(或列)
中所有元素都减去这个数。(注:若未被直线覆盖部分是行数
//
/
01100
30102
06253
116104
820 40
5、 这样必然出现负元素,所以对负元素所在列(或行)中各元素都加上这一最小元素(Xmin)
以消除负数。这样,再返回步骤2,确定独立零元素个数。 重复上述操作,直到找出最优解。
0 3 8
/ 6 6 20
1 2 1 0/ 1 0 54 / 1 2 3 4
特殊问题:
1、
若人数和工作数不等,则用“0
”来补全空位
2、 若一个人可作几件事,则可化为相同的“几个人”来接受指派,费用系数相同。