运筹学,匈牙利法,求详细步骤解答,我不会啊
练习1:
1、对矩阵进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二;
2、检查矩阵二,若矩阵二各行各列均有0,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小值,得矩阵三;
注意:也可先进行列约减再进行行约减。
3、画“盖0”线,即画最少的线将矩阵三中的0全部覆盖,得矩阵四;
操作技巧:从含0最多的行或列开始画“盖0”线。
4、数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖0”线的数目小于矩阵的维数则进行数据转换。本题属于后者,则直接求最优解。对n维矩阵,找出不同行、不同列的n个0,对每个0的位置代表一对配置关系,具体步骤如下。
(1)先找只含有一个0的行(或列),将该行(或列)中的0打“√”。
(2)将带“√”的0所在行(或列)中的其他0打“×”
(3)重复第(1)步和第(2)步至结束。若所有行和列均含有多个0,则从0的数目最少的行或列中任选一个0打“√”。
练习2:(和练习1一样的解法)
1、对矩阵进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二;
2、检查矩阵二,若矩阵二各行各列均有0,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小值,得矩阵三;
注意:也可先进行列约减再进行行约减。
3、画“盖0”线,即画最少的线将矩阵三中的0全部覆盖,得矩阵四;
操作技巧:从含0最多的行或列开始画“盖0”线。
4、数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖0”线的数目小于矩阵的维数则进行数据转换。本题属于后者,则直接求最优解。对n维矩阵,找出不同行、不同列的n个0,对每个0的位置代表一对配置关系,具体步骤如下。
(1)先找只含有一个0的行(或列),将该行(或列)中的0打“√”。
(2)将带“√”的0所在行(或列)中的其他0打“×”
(3)重复第(1)步和第(2)步至结束。若所有行和列均含有多个0,则从0的数目最少的行或列中任选一个0打“√”。
参考资料来源:百度百科-匈牙利法
0 2 3 5
1 0 4 5
1 2 0 1
0 1 4 5
2.每列各元素减去本列最小元素
0 2 3 4
1 0 4 4
1 2 0 0
0 1 4 4
3.每行只有一个零元素画圈,相应的列的零划斜线
4.每列只有一个零元素画圈,相应的行的零划斜线
5.画圈的只有三个小于阶数4,在没有画圈行打√,打√行中划斜线列打√,打√行减去最小元素1,最后一行变成-1 0 3 3.为了不出现负数,在第一列每个元素加1
6.再回到第三步,直到每行每列只有一个零元素,把零元素的地方变成1,其他写零,0-1问题的解矩阵只能是0,1