人员分配问题的匈牙利算法.pptVIP

《ASP.NET 3.5网站开发从入门到精通》 5.2人员分配问题的匈牙利算法 5.2.1 匈牙利算法基本步骤 首先给出匈牙利算法的关键概念。在人员分配问题中，耗费矩阵是指工作所需要的时间，该矩阵的第i行第j列元素表示的是工人做工作所需要的时间或者所耗费的原料，即指派问题中的耗费数值。总耗费是指给定一种指派方案后，该方案总的耗费数值之和。因此，耗费矩阵就是匹配问题的权值矩阵，而总耗费就是给出的一个匹配方案所对应边的权值之和。 匈牙利算法的基本步骤： （1）将原耗费矩阵C的没行，每列各元素都减去该行的最小元素，使每行每列都至少出现一个0元素，以构成等价的耗费矩阵C 匈牙利算法基本步骤 （2）圈0元素。在C中未被直线通过的含0元素最少的行（或者列）中圈出一个0元素，通过这个0元素作一条竖（或横）线。重复此步，若这样能圈出不同行不同列的n个0元素，转第（4），否则转第（3）。 匈牙利算法基本步骤 （3）调整耗费矩阵。在C中没有被直线穿过的数集D中，找出最小的数d，D中所有数都减去d，C中两条直线相交处的数都加d。去掉直线，组成新的等价耗费矩阵仍叫C，返回（2）。 匈牙利算法基本步骤 （4）令被圈0元素对应位置的Xij=1，其余置位Xij=0，这是一种最优分配。最低总耗费是C中与Xij=1位置对应的各元素之和。 5.2.2 匈牙利算法的MATLAB实现 fc01.m fc02.m fc03.m 5.2.3 案例分析 例5-1 指派问题的矩阵为 案例分析 解 直接调入MATLAB程序进行求解即可。输入程序： b=[37.7 32.9 38.8 37 35.4;43.4 33.1 42.2 34.7 41.8;33.3 28.5 38.9 30.4 33.6;29.2 26.4 29.6 28.5 31.1;0 0 0 0 0]; [s t]=fc01(b) 输出结果： s = 2.0000 1.0000 43.4000 3.0000 3.0000 38.9000 1.0000 4.0000 37.0000 4.0000 5.0000 31.1000 5.0000 2.0000 0 t = 150.4000 案例分析 结果分析： s 矩阵保存指派问题求最大解时的指派方案及对应方案的权值。 t 为指派问题的最大解，也即最大费用。 案例分析 因此当要求该指派问题利益最大时可调用以上程序求解。该指派方案为： 案例分析 输入程序： [s1 t1]=fc01(b,1) 输出结果： s1 = 1.0000 5.0000 35.4000 2.0000 4.0000 34.7000 3.0000 2.0000 28.5000 4.0000 1.0000 29.2000 5.0000 3.0000 0 t1 = 127.8000 案例分析 结果分析： s 矩阵保存指派问题求最小解时的指派方案及对应方案的权值。 t 为指派问题的最小解，也即最小费用。 案例分析 例5-2 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这五个人是否都能得到聘书？最多几人能得到聘书，招聘后每人从事哪方面的翻译工作？ 　　解：我们可以利用网络图把它作为一个匹配问题来进行求解。 案例分析 则可得二部图如下： 案例分析 案例分析 首先构造指派矩阵如下： 案例分析 在matlab命令窗口输入： a=[1 0 0 1 1;0 0 1 0 1;1 0 0 1 1;1 0 0 1 1;1 1 1 0 0]; [t c]=fc01(a,1) 输出结果： t = 2 1 0 5 4 0 1 2 0 3 3 0 4 5 1 c = 1 案例分析 结果分析： 案例分析 有绿线相连的为对应的匹配，可见该二部图最大匹配数为4，事实上，最大匹配不唯一，如还存在如下匹配，也为最大匹配。 案例分析 但最大匹配的匹配数是唯一的。 则最多四人可得到聘书，有多种方案，挑选其中两种列表如下： 　　　　 案例分析 但事实上人人都希望得到聘书，不合理的分配会让人产生不公平感，一共有9种方案，哪一种方案都不能达到人人满意，必然有人会没有聘书，比如上表中丁没有聘书，而丁说“为什