匈牙利算法示例

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,匈牙利算法,经典问题,工作分配,一个公司有,n,个工作岗位空缺，每个岗位空缺需要有一定资格的人来填补。现在有,m,个人申请这,n,个工作。由于每个人工作能力不同，所以不同的人能胜任不同的工作。,现在已知每个人所能胜任的若干工作，,求这,m,个人最多可以填补几个工作岗位。,每个人只能做一份工作，每个工作岗位也只需要一个人,二分图,设,G=(V,R),是一个无向图。图的顶点集,V,可分割为两个互不相交的子集,X,和,Y,（子集内部没有边）,，图任何一条边的两个端点都分属不同的子集。则称图,G,为二分图。,用,n,个顶点,X=1,2,3,4,5,表示,n,个工作，用,m,个顶点,Y=A,B,C,D,E,F,表示,m,个工人。,1,2,3,4,5,A,B,C,D,E,F,1,2,3,4,5,A,B,C,D,E,F,二分图匹配,给定一个二分图,G,，在,G,的一个子图,M,中，,M,的边集,E,中的任意两条边都不依附于同一个顶点，则称,M,是一个匹配。在工作分配的问题中，我们给出一个可行的分配方案，就是一个匹配。,选择这样的边数最大的子集称为图的,最大匹配问题,如果这个匹配是最优的（可以填补的工作岗位最多），就是最大匹配。,1,2,3,4,5,A,B,C,D,E,F,1,2,3,4,5,A,B,C,D,E,F,1,2,3,4,5,A,B,C,D,E,F,1,2,3,4,5,A,B,C,D,E,F,2,3,4,5,A,B,D,E,1,2,3,4,5,A,B,D,E,1,2,3,4,5,A,B,C,D,E,匈牙利算法,增广路的定义,(,也称增广轨或交错轨,),：若,P,是图,G,中一条连通两个未匹配顶点的路径，并且属,M,的边和不属,M,的边,(,即已匹配和待匹配的边,),在,P,上交替出现，则称,P,为相对于,M,的一条增广路径。,由增广路的定义可以推出下述三个结论：,1,）,P,的路径长度必定为奇数，第一条边和最后一条边都不属于,M,。,2,）,P,经过取反操作可以得到一个更大的匹配,M,。,3,）,M,为,G,的最大匹配当且仅当不存在相对于,M,的增广路径。,A,B,C,D,5,E,F,A,B,C,D,5,E,F,匈牙利算法,A,B,C,D,5,E,F,A,B,C,D,5,E,F,(1),找到某一匹配,M,(2),找出一条增广路径,P,，通过取反操作获得更大的匹配,M,代替,M,(3),重复,(2),操作直到找不出增广路径为止,设有,n,个工作，要由,n,个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。,c,ij,表示第,i,个人做第,j,件事的费用,求总费用最低的指派方案。,i=1,2, ,n,j=1,2, ,n,分配问题及其,数学模型,有甲、乙、丙、丁、戊五位工人被指派去完成,A,、,B,、,C,、,D,、,E,五项任务，每个人完成任务所需的工时各不相同，见表。求应如何指派人员才能使得所用工时最少？,A,B,C,D,E,甲,12,7,9,7,9,乙,8,9,6,6,6,丙,7,17,12,14,9,丁,15,14,6,6,10,戊,4,10,7,10,9,任务,时间,人员,8,9,匈牙利算法的基本原理是基于以下两个定理,.,定理,1,设,C=(Cij)nn,是指派问题的效益矩阵，若将,C,中的任一行（或任一列）减去该行（或该列）中的最小元素，得到新的效率矩阵,C,，则,C,对应的新的指派问题与原指派问题有相同的最优解,.,定理,2,效率矩阵,C,中独立的,0,元素的最多个数等于覆盖所有,0,元素的最少直线数,.,当独立零元素的个数等于矩阵的阶数时就得到最优解,.,匈牙利法的解题步骤：,第一步：变换指派问题的系数矩阵（,c,ij,）为,(,b,ij,),，使在,(,b,ij,),的各行各列中都出现,0,元素，,即,(1),从（,c,ij,）的,每行元素都减去该行的最小元素；,(2),再从所得新系数矩阵的,每列元素中减去该列的最小元素。,-7,-6,-7,-6,-4,-0,-0,-0,-0,-0,第二步：进行试指派，以寻求最优解。,在,(,b,ij,),中找尽可能多的,独立,0,元素,，若能找出,n,个独立,0,元素，就以这,n,个独立,0,元素对应解矩阵,(,x,ij,),中的元素为,1,，其余为,0,，这就得到最优解。,找独立,0,元素，,常用的步骤为,：,(1),从,只有一个,0,元素的,行,(,列,),开始，给这个,0,元素加圈，记作,。然后划去,所在,列,(,行,),的其它,0,元素，记作,；这表示这列所代表的任务已指派完，不必再考虑别人了。,(2),给只有一个,0,元素的,列,(,行,),中的,0,元素加圈，记作,；然后划去,所在行的,0,元素，记作,(3),反复进行,(1),，,(2),两步，直到尽可能多的,0,元素都被圈出和划掉为止。,第三步；作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。,（1）对没有,的行打,（2）在已经打的行中所含有的0元素打号,（3）在已经打号的列中含,元素的行打；,（4）重复（2）（3）直到得不出打的行列为止,（5）对没有打的行画一横线，有打的列画一纵线，这就覆盖所有0元素的最少直线数。令这一直线数为l。若ln,说明必须再换当前的系数矩阵，才能找到n个独立的0元素，为此转到第四步；若l=n，而mn，应回到（2）（4）另行试探。,第四步；在没有被直线覆盖的部分中找出最小元素。然后在行打行每个元素减去这一最小元素，而在打列的每个元素都加上这一最小元素，以保证原来0元素不变。这样得到新系数矩阵。若得到n个独立的0元素，则已得到最优解，否则回到第三步。,上面矩阵有5个独立0元素，这就得到相应的最优解。,-2,-2,+2,或,解矩阵得到2个最优指派方案；（1）甲-B，乙-C，丙-E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C，戊-A。所需时间为minz=7+6+9+6+4=32,15,非标准型的指派问题：,匈牙利法的条件是：模型求最小值、效率,c,ij,0,。,当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，,1,、人数和事数不相等的指派问题：人少事情多，虚拟“人”，做各事的费用系数为,0,；人多事情少，虚拟“事”，各人做的费用系数为,0,。,2,、对于求极大化的问题，只要系数矩阵变换为,B,（,m-c,ij,）,nn,，仍可利用匈牙利算法进行求解。,3,、一个人可以做几件事情的指派问题：可以将该人化作相同的几个“人”来接受指派，费用一样。,4,、某事一定不能由某人做的指派问题，费用系数为“,M”,然后用匈牙利法来求解。,请各位老师和同学批评指导！,