匈牙利算法示例

1、匈牙利算法经典问题工作分配n一个公司有n个工作岗位空缺，每个岗位空缺需要有一定资格的人来填补。现在有m个人申请这n个工作。由于每个人工作能力不同，所以不同的人能胜任不同的工作。n现在已知每个人所能胜任的若干工作，求这m个人最多可以填补几个工作岗位。n每个人只能做一份工作，每个工作岗位也只需要一个人二分图n设G=(V,R)是一个无向图。图的顶点集V可分割为两个互不相交的子集X和Y（子集内部没有边） ，图任何一条边的两个端点都分属不同的子集。则称图G为二分图。n用n个顶点X=1,2,3,4,5表示n个工作，用m个顶点Y=A,B,C,D,E,F表示m个工人。12345ABCDEF1,2,3,4,5A

2、,B,C,D,E,F二分图匹配n给定一个二分图G，在G的一个子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个匹配。在工作分配的问题中，我们给出一个可行的分配方案，就是一个匹配。n选择这样的边数最大的子集称为图的最大匹配问题最大匹配问题如果这个匹配是最优的（可以填补的工作岗位最多），就是最大匹配。12345ABCDEF12345ABCDEF12345ABCDEF12345ABCDEF2345ABDE12345ABDE12345ABCDE匈牙利算法n增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P

3、上交替出现，则称P为相对于M的一条增广路径。n由增广路的定义可以推出下述三个结论：n1）P的路径长度必定为奇数，第一条边和最后一条边都不属于M。n2）P经过取反操作可以得到一个更大的匹配M。n3）M为G的最大匹配当且仅当不存在相对于M的增广路径。ABCD5EFABCD5EF匈牙利算法ABCD5EFABCD5EF(1)找到某一匹配M(2)找出一条增广路径P，通过取反操作获得更大的匹配M代替M(3)重复(2)操作直到找不出增广路径为止 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。 jiijijxc

4、Zmin1.21inijiixxxxt si=1,2, ,n121njijjjxxxxj=1,2, ,nnjnixij, 2 , 1;, 2 , 11 , 0分配问题及其分配问题及其数学模型数学模型 有甲、乙、丙、丁、戊五有甲、乙、丙、丁、戊五位工人被指派去完成位工人被指派去完成A、B 、 C 、 D 、 E五项任务，每五项任务，每个人完成任务所需的工时个人完成任务所需的工时各不相同，见表。求应如各不相同，见表。求应如何指派人员才能使得所用何指派人员才能使得所用工时最少？工时最少？ABCDE甲127979乙89666丙71712149丁15146610戊4107109任务时间人员8n 9n匈牙

5、利算法的基本原理是基于以下两个定理匈牙利算法的基本原理是基于以下两个定理. n定理定理1 设C=(Cij)nn是指派问题的效益矩阵，若将C中的任一行（或任一列）减去该行（或该列）中的最小元素，得到新的效率矩阵C，则C对应的新的指派问题与原指派问题有相同的最优解. n定理定理2 效率矩阵C中独立的0元素的最多个数等于覆盖所有0元素的最少直线数. 当独立零元素的个数等于矩阵的阶数时就得到最优解.匈牙利法的解题步骤：匈牙利法的解题步骤：n 第一步：变换指派问题的系数矩阵（第一步：变换指派问题的系数矩阵（cij）为）为(bij)，使在，使在(bij)的各行各列中都出现的各行各列中都出现0元素，元素，即

6、即n (1) 从（从（cij）的）的每行元素都减去该行的最小每行元素都减去该行的最小元素；元素；n (2) 再从所得新系数矩阵的再从所得新系数矩阵的每列元素中减去每列元素中减去该列的最小元素。该列的最小元素。()ijc12 7979896667 17 12 14 915 14 66 104 10 7 10 9502 0 2230 0 00 10 5 72980 0 4063 6 5-7-6-7-6-4-0-0502 0 2230 0 00 10 5 72980 0 4063 6 5-0 -0-0 第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。 在在(bij)中找尽可能多的

7、中找尽可能多的独立独立0元素元素，若能找出，若能找出n个个独立独立0元素，就以这元素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的中的元素为元素为1，其余为，其余为0，这就得到最优解。，这就得到最优解。找独立找独立0元素，元素，常用的步骤为常用的步骤为： (1)从从只有一个只有一个0元素的元素的行行(列列)开始，给这个开始，给这个0元素加圈，记作元素加圈，记作 。然后划。然后划去去 所在所在列列(行行)的其它的其它0元素，记作元素，记作 ；这表示这列所代表的任务已指派完，；这表示这列所代表的任务已指派完，不必再考虑别人了。不必再考虑别人了。 (2)给只有一个给只有一个0元素

8、的元素的列列(行行)中的中的0元素加圈，记作元素加圈，记作；然后划去；然后划去 所在所在行的行的0元素，记作元素，记作 (3)反复进行反复进行(1)，(2)两步，直到尽可能多的两步，直到尽可能多的0元素都被圈出和划掉为止。元素都被圈出和划掉为止。50202230000 1057298004063655636489275103222550202230000 105729800406365 第三步；作最少的直线覆盖所有第三步；作最少的直线覆盖所有0元素，以确元素，以确定该系数矩阵中能找到最多的独立元素数。定该系数矩阵中能找到最多的独立元素数。（1）对没有）对没有的行打的行打（2）在已经打）在已经打

9、的行中所含有的的行中所含有的0元素打元素打号号（3）在已经打）在已经打号的列中含号的列中含元元素的行打素的行打；（4）重复（）重复（2）（）（3）直到得不出）直到得不出打打的行列为止的行列为止（5）对没有打）对没有打的行画一横线，的行画一横线，有打有打的列画一纵线，这就覆盖所的列画一纵线，这就覆盖所有有0元素的最少直线数。令这一直元素的最少直线数。令这一直线数为线数为l。若。若ln,说明必须再换当说明必须再换当前的系数矩阵，才能找到前的系数矩阵，才能找到n个独立个独立的的0元素，为此转到第四步；若元素，为此转到第四步；若l=n，而，而mn，应回到（，应回到（2）（）（4）另行试探。另行试探。5

10、0202230000105729800406365 第四步；在没有被直线覆盖的部分中找出最小元素。第四步；在没有被直线覆盖的部分中找出最小元素。然后在行打然后在行打行每个元素减去这一最小元素，而在打行每个元素减去这一最小元素，而在打列的每个元素都加上这一最小元素，以保证原来列的每个元素都加上这一最小元素，以保证原来0元元素不变。这样得到新系数矩阵。若得到素不变。这样得到新系数矩阵。若得到n个独立的个独立的0元素，则已得到最优解，否则回到第三步。元素，则已得到最优解，否则回到第三步。34144811538342273414481153834227上面矩阵有上面矩阵有5个独立个独立0元素，这就得到

11、相应的最优解。元素，这就得到相应的最优解。50202230000105729800406365 -2-2+200001010001000000100000100000100100100000100000010或解矩阵得到解矩阵得到2个最优指派方案；（个最优指派方案；（1）甲）甲-B，乙，乙-C，丙丙-E，丁，丁-D,戊戊-A；（；（2）甲）甲-B，乙，乙-D，丙，丙-E,丁丁-C，戊戊-A。所需时间为。所需时间为minz=7+6+9+6+4=3215非标准型的指派问题：匈牙利法的条件是：模型求最小值、效率匈牙利法的条件是：模型求最小值、效率cij0。当遇到各种非标准形式的指派问题时，处理方法是先将当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，其转化为标准形式，1、人数和事数不相等的指派问题：人少事情多，虚拟、人数和事数不相等的指派问题：人少事情多，虚拟“人人”，做各事的费用系数为，做各事的费用系数为0；人多事情少，虚拟；人多事情少，虚拟“事事”，各人做的费用系数为，各人做的费用系数为0。2、对于求极大化的问题，只要系数矩阵变换为、对于求极大化的问题，只要系数矩阵变换为B（m-cij）nn，仍可利用匈牙利算法进行求