Question

管理运筹学问题哦！ 关于匈牙利解法的问题

7 8 2 9
6 3 2 8
4 2 5 4
6 3 7 2
7 3 5 9
8 6 4 3
求详细答案谢谢~

Answer 1

一、变换为标准形式。添加虚拟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