运筹学,匈牙利法,求详细步骤解答,我不会啊

 我来答
12star
2019-06-14 · TA获得超过1820个赞
知道答主
回答量:0
采纳率:100%
帮助的人:0
展开全部

练习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打“√”。

参考资料来源:百度百科-匈牙利法

什什and么么
2014-07-07 · TA获得超过190个赞
知道答主
回答量:68
采纳率:100%
帮助的人:15万
展开全部
1.每行各元素减去本行最小的数
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
本回答被提问者采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式