关于匈牙利解法的问题7 8 2 96 3 2 84 2 5 46 3 7 27 3 5 9 8 6 4 3

关于匈牙利解法的问题7 8 2 96 3 2 84 2 5 46 3 7 27 3 5 9 8 6 4 3
关于匈牙利解法的问题
7 8 2 9
6 3 2 8
4 2 5 4
6 3 7 2
7 3 5 9
8 6 4 3

关于匈牙利解法的问题7 8 2 96 3 2 84 2 5 46 3 7 27 3 5 9 8 6 4 3
一、变换为标准形式.添加虚拟2列.
7 8 2 9 0 0
6 3 2 8 0 0
4 2 5 4 0 0
6 3 7 2 0 0
7 3 5 9 0 0
8 6 4 3 0 0
二、变换系数矩阵.
1、先对各行元素分别减去本行中的最小元素,得
7 8 2 9 0 0
6 3 2 8 0 0
4 2 5 4 0 0
6 3 7 2 0 0
7 3 5 9 0 0
8 6 4 3 0 0
2、再对各列元素分别减去本列中最小元素,得
3 6 0 7 0 0
2 1 0 6 0 0
0 0 3 2 0 0
2 1 5 0 0 0
3 1 3 7 0 0
4 4 2 1 0 0
三、确定独立零元素.
1、对第1行的第1个零元素加圈,同时划去同行和同列的其他零元素.得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 0 0
0 0 3 2 0 0
2 1 5 0 0 0
3 1 3 7 0 0
4 4 2 1 0 0
2、对第2行的第2个零元素加圈,同时划去同行和同列的其他零元素,得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ
0 0 3 2 Φ 0
2 1 5 0 Φ 0
3 1 3 7 Φ 0
4 4 2 1 Φ 0
3、对第3行的第1个零元素加圈,同时划去同行和同列的其他零元素,得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ
◎ Φ 3 2 Φ Φ
2 1 5 0 Φ 0
3 1 3 7 Φ 0
4 4 2 1 Φ 0
4、对第4行的第1个零元素加圈,同时划去同行和同列的其他零元素,得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ
◎ Φ 3 2 Φ Φ
2 1 5 ◎ Φ Φ
3 1 3 7 Φ 0
4 4 2 1 Φ 0
5、对第5行的第2个零元素加圈,同时划去同行和同列的其他零元素,得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ
◎ Φ 3 2 Φ Φ
2 1 5 ◎ Φ Φ
3 1 3 7 Φ ◎
4 4 2 1 Φ Φ
此时得到了5个加圈的独立零元素,少于6个,因此不能确定最优指派方案.
四、确定能覆盖所有零元素的最少直线数目的直线集合.
1、对于没有加圈的行打勾.得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ
◎ Φ 3 2 Φ Φ
2 1 5 ◎ Φ Φ
3 1 3 7 Φ ◎
4 4 2 1 Φ Φ √
2、在已打勾的行中,对划去零元素所在的列打勾,得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ
◎ Φ 3 2 Φ Φ
2 1 5 ◎ Φ Φ
3 1 3 7 Φ ◎
4 4 2 1 Φ Φ √
√ √
3、在已打勾的列中,对加圈的零元素所在的行打勾,得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ √
◎ Φ 3 2 Φ Φ
2 1 5 ◎ Φ Φ
3 1 3 7 Φ ◎ √
4 4 2 1 Φ Φ √
√ √
4、在已打勾的行中,对划去零元素所在的列打勾,得
3 6 ◎ 7 Φ Φ
2 1 Φ 6 ◎ Φ √
◎ Φ 3 2 Φ Φ
2 1 5 ◎ Φ Φ
3 1 3 7 Φ ◎ √
4 4 2 1 Φ Φ √
√ √ √
5、在已打勾的列中,对加圈的零元素所在的行打勾,得
3 6 ◎ 7 Φ Φ √
2 1 Φ 6 ◎ Φ √
◎ Φ 3 2 Φ Φ
2 1 5 ◎ Φ Φ
3 1 3 7 Φ ◎ √
4 4 2 1 Φ Φ √
√ √ √
此时已不能再打勾.
6、对没打勾的行画一横线,对打勾的列画一垂线,得
3 6 ◎| 7 Φ| Φ| √
2 1 Φ| 6 ◎| Φ| √
◎ Φ 3| 2 Φ| Φ|
_________________
2 1 5 | ◎ Φ| Φ|
_________________
3 1 3 | 7 Φ| ◎| √
4 4 2 | 1 Φ| Φ| √
√ √ √
五、调整系数矩阵.
1、在未被直线覆盖的元素中,找出一个最小元素,即第2行第2列的1.
2、对未被直线覆盖的元素所在行中各元素都减去这一最小元素,得

2 5 -1| 6 -1| -1| √
1 0 -1| 5 -1| -1| √
◎ Φ 3| 2 Φ| Φ|
_________________
2 1 5 | ◎ Φ| Φ|
_________________
2 0 2 | 6 -1| -1| √
3 3 1 | 0 -1| -1| √
√ √ √
3、对出现负数的列,分别加上这一最小元素,得
2 5 0| 6 0| 0| √
1 0 0| 5 0| 0| √
◎ Φ 4| 2 1| 1|
_________________
2 1 6| ◎ 1| 1|
_________________
2 0 3 | 6 0| 0| √
3 3 2 | 0 0| 0| √
√ √ √
得新矩阵
2 5 0 6 0 0
1 0 0 5 0 0
0 0 4 2 1 1
2 1 6 0 1 1
2 0 3 6 0 0
3 3 2 0 0 0
返回步骤三,重新确定独立零元素.得
2 5 ◎ 6 Φ Φ
1 ◎ Φ 5 Φ Φ
◎ Φ 4 2 1 1
2 1 6 ◎ 1 1
2 Φ 3 6 ◎ Φ
3 3 2 0 Φ ◎
此时得到独立零元素个数为6,则已得出最优解矩阵
0 0 1 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
删去增加的虚拟列,得
0 0 1 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 0 0
0 0 0 0
此时有最小目标函数值：2+3+4+2=11