指派问题的匈牙利法.docx

《指派问题的匈牙利法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、精品文档变换指派问题的匈牙利法1、使各行各列中都出现0元素，每行元素都减去该行的最小元素；每列元素中减去该列的最小元素。2、从只有一个0元素的行开始，给该行中的0元素加圈。然后划去◎所在列的其它0元素，记作?，依次进行到最后一行。从只有一个0元素的列开始（画?的不计在内），给该列中的0元素加圈；然后划去◎所在行的0元素，记作?，依次进行到最后一列。若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所在列中0元素的数目，选择性少的。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。3、对没有◎的行打“√”；对已打“√”的行中所有含?元素的列打“√”

2、；再对打有“√”的列中含◎元素的行打“√”。4、对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数。5、在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。6、再画圈，重复。匈牙利法的几种特殊情况1、最大化指派问题选择最大元素m,变换效率矩阵为bijmcij，最大化问题转化成最小化指派问题。2、人数和工作数不等增加虚拟的人或工作。3、一个人可以做几件工作把这“一个人”拆成（复制）成“几个人”去处理。。1欢迎下载精品文档欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习资料等等打造

3、全网一站式需求。2欢迎下载