指派问题:匈牙利算法 |
您所在的位置:网站首页 › 指派匈牙利算法matlab代码 › 指派问题:匈牙利算法 |
匈牙利法的基本思路:对费用矩阵C的行和列减去某个常数,将C化为有n个位于不同行不同列的零元素,令这些零元素对应的变量取1,其余变量取0,即得到指派问题的最优解。 匈牙利法是基于指派问题的标准型的,标准型需满足以下3个条件: (1)目标函数求min; (2)效率矩阵为n阶方阵; (3)效率矩阵中所有元素Cij≥0,且为常数。 匈牙利法的计算步骤: (1)变换效率矩阵C,使每行每列至少有一个0,变换后的矩阵记为B 行变换:找出每行min值,该行各元素减去它;列变换:找出每列min值,该列各元素减去它;若某行/列已有0元素,则不用减。 (2) (3)如果○的个数少于n,则进行这一步。 对没有圈○的行打“√”;在已打“√”的行中,对×所在列打“√”;在已打“√”的列中,对圈○的行打“√”;重复2和3步骤,直到再也找不到可以打“√”的行/列为止;对没有打“√”的行画横线表示去掉这一行,对打“√”的列画横线表示去掉这一列,这样就得到能覆盖所有0的最小横线。 (4)变换矩阵B以增加0。 在未被直线覆盖的所有元素中找到min;然后在打“√”的所有行中减去这个min;而在打“√”的所有列中加上这个min,以保持原来0不变(为了消除负元素);得到新的系数矩阵C。 (5)返回步骤(2),直到得到n个0元素,即得到最优解。 指派问题的其他衍生问题: (1)求maxZ的指派问题 找出系数矩阵中的max,然后令系数矩阵变为max-系数矩阵各元素值,得到新系数矩阵,按照正常匈牙利法即可求到。 (2)人数与工作数不等的指派问题 工作<人数,增加虚拟工作;人数<工作,增加虚拟工人。 (3)一个人可做几件事的指派问题 例如:一个人可以做t件事。把这个人复制成有t个人,可以做t件事,每个人做事费用都一样。 (4)某人一定不能做某事的指派问题 求minZ,Cij取正无穷M;求maxZ,Cij取0。 例题: 版权声明:本文为博主原创文章,未经博主允许不得转载。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |