关于匈牙利解法的问题7 8 2 96 3 2 84 2 5 46 3 7 27 3 5 9 8 6 4 3
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/22 05:58:54
关于匈牙利解法的问题
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 9
6 3 2 8
4 2 5 4
6 3 7 2
7 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
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
有几种解法只用加法运算,你能想出几中解法?1 2 3 4 5 6 7 8 9 =99
一元一次方程的解法2/1[3/x-2/1(2/3x-1)]=12/x 9/1{7/1[5/1(5/x+2+4)+6]+8
二元一次方程组的解法 {2x-7y=8 {3x-8y-10=0 的解法,知道者请详细说明.不要瞎掰
加减法解二元一次方程具体解法,还有2X-3Y=5 2X-8Y=3的具体解法
二元一次方程组1、{x-3y=4 2x+7y=5的解法 2、{3x-4y=9 4x-5y=20的解法
X+7/X+1+X+8/X+2-X+9/X+3-X+10/X+4 的解法
高三数学题:关于3次方程的解法的问题
1×2×3……×50等于几?的简便解法!一定要有解法!
高数微积分 积分换元法计算 解法2的答案怎么转化为解法3或4的答案?
关于x,y的多项式(3a+2)乘x的平方+(9a+10b)xy-x+2y+7不含二次项,求3a-5b的值. 要解法思路
关于x,y的多项式(3a+2)乘x的平方+(9+10b)xy-x+2y+7不含二次项,求3a-5b的值.要解法思路
人教版的)1、工程问题2、调配问题3、行程问题4、相遇问题5、追及问题6、浓度问题7、百分比问题8、年龄问题9、航行问题