匹配理论及其应用.doc

匹配理论及其应用专业：信息与计算科学 姓名：李玉财 指导老师：邓凯摘 要 利用组合图论的方法将企业招聘问题转化为求赋权平衡二分图的最大权完美匹配问题,再利用KM算法得到它的解，产生最优匹配，也即最优招聘,在此过程中最大限度的考虑了每项考核内容的权重，利用层次分析方法得到权重向量,利用模糊综合评价方法得到隶属度矩阵，两者相乘得到综合隶属度，结合每个应聘人员每项考核成绩，得到最后的综合评分，企业按照这个总分择优录取。关键词 层次分析方法，模糊综合评价，最佳匹配，KM算法ABSTRACTUsing combination graph theory takes recruitment problems of companies as maximal weight perfect matching problems on weighted bipartite graph. Then, make out the result by KM algorithm, which is the optimum matching or employee. In this procedure, the weights of each assessment will be fully taken into consideration. By AHP, we get weight vector and by Fuzzy Comprehensive Evaluation Method, membership matrix. By multiplying those two results, we can get comprehensive membership. Finally, regarding the results of each examination, work out a comprehensive mark according to which the company enrolls the best by selection.Key Words：AHP Fuzzy comprehensive evaluation Best match KM algorithm1 绪论企业招聘作为企业人力资本获取和积累的一个主要渠道，是企业人力资本投资的重要方式之一，对企业的绩效产生直接的关系，在一次大型招聘会中，每个企业在招聘时，都希望得到有潜力的人员，每个企业对投递简历的每个应聘人员进行考核，以此为依据录用人员，从而出现多家企业竞争同一个人的情况，为了平衡各企业之间人才分配，又能使每个企业都尽可能得到自己满意的人才。需要在企业和应聘人员之间进行匹配，用KM求其最大匹配或者完美匹配。本文把层次分析方法和模糊综合评价方法相结合得到权矩阵。用层次分析方法建立应聘人员的评优模型，得到权向量，用模糊综合评价方法建立评价集、评价集、权重集以及隶属度矩阵，其中对于隶属度矩阵是运用抽样调查的方法得到的。然后两者结合得到综合隶属度，最后根据每个应聘人员的每项考核成绩与综合隶属度对应相乘得到每个应聘人员的综合得分，也就是权矩阵，最后利用KM算法得到其最优匹配，产生最优招聘。2 问题的提出及基本假设某大型大型招聘会企业公开向社会招聘人才，首先通过公开考试，根据考核的内容包括德、智、体、技能、实践等五个综合素质，各单位按照考试成绩的高低决定是否录用，最终出现某应聘人员对于多个单位的成绩是一样的，为了平衡各企业之间人才分配，使企业最大满意，于是就要求企业和应聘人员之间达到最优匹配，从而产生最优招聘。基本假设如下:(1)成绩高的人员优先录取。(2)每个用人单位只招收一个人，如果某用人单位招收多人，则按照多个用人单位来计算。(3)每个企业对应聘人员的考核内容及评分参考标准是一样的，录用标准也一样。3基本概念和理论基础3.1基本概念13.1.1 二分图：，且中任意二顶不相邻，中任意二顶不相邻，则称为二分图。3.1.2正负反矩阵： ，则称为正负反矩阵。3.1.3 匹配：是图的边子集，且中任意二边在中不相邻，则称是中的一个匹配；中的每条边的两个端点称为在中相配；中每边的端点称为被许配；中每个顶点都被许配时，称为的一个完备匹配；中边数最多的匹配称为的最大匹配。31.4 可增广轨：设是图中的一个匹配，中的一条轨上，与未 被许配，但上的边交替地不在中出现与在中出现，则称为的可增广轨。3.2理论基础AHP2是一种定量与定性相结合的评价方法，在判断目标结构复杂且缺乏必要的数据情况下，能把其他方法难以量化的评价因素通过两两比较加以量化，把复杂的评价因素构建为层次结构，有效确定多因素指标的相对重要程度，进而进行评价。AHP2在进行总体评价时但缺乏统一的、具体的指标量化方法，模糊综合评价3是综合考虑受多种因素影响的事物或系统对其进行总的评价，且评价具有模糊性。模糊综合评价，根据被调查应聘人员的评价意见获得隶属度矩阵，计算综合隶属度和综合得分，即可得应聘人员的综合排名。在构造正负反矩阵时，为了能用它的对应于最大特征根的特征向量作为被比较因素的权向量，Saaty2给出了如下检验方法：其中为一致性指标，为随机一致性指标，可以有查表的出，为最大特征根，为正负反矩阵的阶。如果满足此方法，则这个矩阵最大特征根对应的特征向量可以用作权向量。组合权向量的计算方法：在层次分析方法中，若共有层，则第层对第层（设只有一个因素）的组合权向量满足其中是以第层对第层的权向量为列向量组成的矩阵，于是最下层（第层）对最上层的组合权向量为在运用模糊综合评价3时，建立影响评价对象的个因素组成的因素集然后，建立由个评价结果组成的评价集再对个因素分配的权值，建立权重集，即表示为权向量式中为对第个因素的加权值，一般规定为对第个因素的单因素模糊评价为上的模糊子集然后建立隶属度矩阵为最后算出隶属度于是应聘人员的综合得分， 为评语集的数值化结果。在问题的解决中,匈牙利算法1和KM算法1起了很重要的作用:其匈牙利算法解决了求二部图中求饱和的匹配问题; KM算法在匈牙利算法基础上利用顶点标号法解决了在赋权完全二部图中寻找最大权完美匹配问题。匈牙利算法： 设是连通的二分图，在中任取初始匹配。 若把中顶皆许配，止，即为的最大匹配；否则取中未被许配的顶，令，。 若，止，中无完备匹配；否则取。 若被许配，设，转；否则取可增广轨，令，转。KM算法：选定初始正常顶标，构作图，在中取初始匹配。若中顶皆被许配，止，即为所求的最佳匹配；否则取中未被许配的顶，令，。若，转，若，取，。 选中一顶，若已被匹配，且，则，转；否则，取中一个可增广轨，令，转。如果应聘人员数大于用人单位数，而求二分图存在完美匹配要求二分图的二分顶点数相同.根据组合图论的方法4,扩充赋权二分图为,方法如下:在中增加个新顶点,并将中每个顶点均与中每个顶点相连,且规定其权值均为,得赋权完全二部图,其中，定理4赋权二分图的每个最大权最大匹配恰对应于其扩充赋权完全二部图的最大权完美匹配,且这两个匹配权和相同。4模型的建立，演算过程及结果4.1模型实现，建立层次结构模型5应聘人员评优包括德、智、体、技能以及实践等五个方面，依照层次分析法，建立了递阶层次结构，如图4.2确定单一准则下各指标的相对权重依据Saaty2 的标度法，对应图准则 ，层的判断矩阵。计算出矩阵的最大特征根及其所对应的特征向量。特征向量能否作为权重，需要通过一致性检验来确定。对矩阵的一致性指标查得随机一致性指标一致性比率所以矩阵的一致性是可以接受的。采用同样的方法可得到层对层的相对权重，把写成矩阵的形式如下其中代表没有数据，代表层第项元素对应层第项元素的相对权重。同样进行一致性检验，结果一致性可以接受。确定各指标对目标层的合成权重。是层对层的相对权重，是层对层的相对权重，将中的第一个值和中第一行各元素相乘；将中的第二个值和中第二行各元素相乘；依次下去最终得到层各元素对于总目标的合成权共有个值详见表。同样对层指标合成权重进行检验，满足整体一致性要求。4.3模糊综合评价3依据上述所建模型，因素集根据各指标包含的具体评价要求，取评语集。通过调查对指标进行评价，评价意见整理后得到隶属度矩阵综合隶属度得到即被评价的应聘人员是好的可能性为是较好的可能性为，一般的可能性为，差的可能性为，较差的可能性为。选取个应聘人员的成绩做一个分数矩阵，矩阵每一行代表一个应聘人员各项考核成绩。由转置得每个应聘人员的总得分同样的方法也可以得到别的企业想对于这些应聘人员的总分，将其组成一个得综合总得分分矩阵，即为权矩阵把应聘人员和单位构造二分图，其权矩阵为二分图边上的权。利用KM算法求得最大匹配：取正常初始顶标：够作，粗实线是上最大匹配如图，无完备匹配，其顶标需要修改。取未被许配的顶，令，取，未被许配，因此取中一个可增广轨，令，转，此时中的顶皆被许配，止。即：为最佳匹配如图。最大权值为，也可以利用MATLAB程序运行，输入数据得到如下运行结果：其中为匹配矩阵，匹配矩阵中的代表与相匹配，最优匹配权值，显然符合。4.4结果讨论由结果可知：第一家企业要第五个应聘人员，第二家企业要第九个应聘人员，等等，从结果不难看出，企业和应聘人员之间得到了最优的匹配。如果企业的数量和应聘人数不等，则根据定理可得其最优匹配。5模型的评价和推广本文建立的企业招聘人员的模型,是基于求赋权二分图最大权完美匹配的KM的算法的模型,具有坚实的理论基础,它综合了每个应聘每项考核内容的权重，且适合于计算机编程运算,并适合于处理多个顶点,多边数二分图模型,有极强的适用性.此模型也可推广到各种评优的系统中,因而有很好的推广性。参考文献1王树禾.图论.北京:科学出版社,2009.2。2姜启源，谢金星，叶俊.数学模型.北京：高等教育出版社，2003.83李士勇.工程模糊数学及应用.哈尔滨：哈尔滨工业大学出版社，2004.84刘春杨.公务员招聘的数学模型. 第21卷第6期.5程海燕.基于AHP和模糊综合评价的学生评优模型的研究.中国科技信息2010年第9期.附 录function Matrix MaxWeight = KMAB( B )n=size(B,2);LMax=zeros(n,2);Matrix=zeros(n,n);LMax(:,1)=max(B,2);for(i=1:n) for(j=1:n) if(LMax(i,1)+LMax(j,2)=B(i,j) H(i,j)=1; else H(i,j)=0; end endendii=1;jj=min(find(H(1,:)=1);Matrix(ii,jj)=1;Szeros=zeros(1,n);Tzeros=Szeros;NISzeros=Szeros;while (1) for(i=1:n) k=1; for(j=1:n) if(Matrix(i,j) k=0; break; end end if(k) break; end end if(k=0) break; end Szeros(1)=i;js=1;jt=0; while(1) jn=0; for(i=1:js) for(j=1:n) if(H(Szeros(i),j) jn=jn+1; NISzeros(jn)=j; for(k=1:jn-1) if(NISzeros(k)=j) jn=jn-1; end end end endendif(jn=jt) pp=1; for(j=1:jn) if(NISzeros(j)=Tzeros(j) pp=0;break; end endendif(jn=jt&pp) a=Inf; for(i=1:js) for(j=1:n) pp=1; for(k=1:jt) if(Tzeros(k)=j) pp=0;break; end end if(pp&aLMax(Szeros(i),1)+LMax(j,2)-B(Szeros(i),j) a=LMax(Szeros(i),1)+LMax(j,2)-B(Szeros(i),j); end end end for(i=1:js) LMax(Szeros(i),1)=LMax(Szeros(i),1)-a; end for(j=1:jt) LMax(Tzeros(j),2)=LMax(Tzeros(j),2)+a; end for(i=1:n) for(j=1:n) if(LMax(i,1)+LMax(j,2)=B(i,j) H(i,j)=1; else H(i,j)=0; end Matrix(i,j)=0;k=0; end end ii=0;jj=0; for(i=1:n) for(j=1:n) if(H(i,j) ii=i; jj=j; break; end end if(ii) break; endendMatrix(ii,jj)=1;break;else for(j=1:jn) pp=1; for(k=1:jt) if(Tzeros(k)=NISzeros(j) pp=0;break; end end