用匈牙利算法解决相亲类型问题的数学模型.doc

关于玫瑰有约的数学模型摘要：现在城市大龄青年的婚姻问题收起了社会的广泛关注，针对这一社会现象，我们假设某单位有20对大龄青年男女，每个人的基本条件都不相同，并且每个人的择偶条件也不相同。该单位的妇联组织拟根据他们的年龄，基本条件和要求条件牵线搭桥。本文根据每个人的情况和要求，建立数学模型帮助妇联解决3个问题。关键词：数学模型；满意度；匈牙利算法；KM算法The mathematical model about making an appointment for life Li wei(Department of Mathematics and Computational Science Hunan University of Science and Engineering,Yongzhou,425100,Hunan）Abstract: Nowadays, the problem of the youngs marriage has roused more and more publics concern. According to this phenomenon, we assume that there are twenty pairs of aged people in a company, all of which have different basic condition and their demanding。The Womens Federation of this company wants to wire-pull for them on the basis of their age, basic condition and demand. This paper, according to everyones condition and demands, helps the Womens Federation solving this problem.Key words: mathematical model; the measurement of satisfaction; Hungary algorithm; KM algorithm; 1.引言现在在城市大龄青年的婚姻问题引起了社会的广泛关注，针对这一现象，我们给出20对青年男女的基本条件和择偶条件的抽样是真实可靠的。首先，我们将所给的两个表格按年龄升序重新进行排列，分别编号为1，2，320。并且将外貌、性格、气质、事业、财富五个方面的五个等级A、B、C、D、E分别赋值为5、4、3、2、1，这样我们就得到了男女青年的基本条件和要求条件的四个矩阵；其次，我们定义了“满意度”的概念，利用图论（二部图）的方法解决这个问题。 在模型中，根据男青年的基本条件和女青年的要求条件构造度量矩阵（权值矩阵）A，男1号的基本条件和女1号的要求条件，比如在外貌方面，男1号满足女1号的要求则赋值为5-3+1，在事业方面，男1号不满足女1号的要求，则赋值为0，按照这个方法，如果满足条件则按公式（男青年基本条件值-女青年相应的要求条件+1）赋值，反之赋值为0，这样可以得到外貌，性格，气质，事业，财富五个方面的数值，并将这些数值相加得到，最终得到权值矩阵T=（）2020，同理可得，女青年的基本条件和男青年的要求条件所构成的权值矩阵S=()2020，那么男女青年配对的总权值矩阵（即为满意度矩阵）为R1=T+S，（因为表示男i号的基本条件对j号的要求条件，表示女j号的基本条件对男i号的要求条件，那么用+ 表示男i号对女j号的总权数即为他们之间的满意度）：再次，我们根据年龄的限制在矩阵R1中将不满足条件的赋0，得到矩阵R，利用匈牙利算法可得到问题（1）的结果。再在矩阵R中将大于2的数字赋1反之赋0，再利用KM算法可得问题（2）的结果。 由于以上的模型在构造权值矩阵R时，男青年基本条件不满足女青年要求条件时赋值为0，实际上还存在男女青年的失望度，故在模型改进中针对失望度将模型中赋值为0的另外赋值为（女青年要求条件值男青年相应的基本条件值）即考虑到可能单向面的满意度较大而另一方面的失望度也较大时同样不能配对成功，且在把模型无向化时是采用把每个结点分成两个结点的方法即把有向的平行边分成各自带自己权的无向边，同时在此模型中将初等模型中的五个等级A、B、C、D、E量化为9、7、5、3、1（由于模型中的赋值尺度比较粗糙），其余的步骤与模型相同，从而得到了模型改进。2.问题的提出目前，在许多城市大龄青年的婚姻问题已引起了妇联和社会团体组织的关注。某单位现在有20对大龄青年男女，每个人的基本条件都不相同，如外貌、性格、气质、事业、财富等。每项条件通常可以分为五个等级A、B、C、D、E，如外貌、性格、气质、事业可分为很好、好、较好、一般、差；财富可以分为很多、多、较多、一般、少。每个人的择偶条件也不尽相同，即对每项基本条件的要求是不同的。该单位的妇联组织拟根据他（她）们的年龄、基本条件和要求条件进行牵线搭桥。下面给出20对大龄青年男女的年龄、基本条件和要求条件（如下表）。一般认为，男青年至多比女青年的年龄大5岁，或女青年的年龄比男青年的大2岁，并且要至少满足个人要求5项条件中的2项，才有可能配对成功。本文根据每个人的情况要求，建立数学模型帮助妇联解决如下问题：(1)给出可能的配对方案，使得在尽量满足个人要求的条件下，使得配对成功率尽可能的高。(2)给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大。(3)假设男女双方都相互了解了对方的条件和要求，让每一个人出一次选择，只有当男女双方相互选中对方时才认为配对成功，每一个人只有一次选择机会。怎样告诉20对男女青年都应该如何做出选择，使得自己的成功的可能性最大？选择的方案最多能配对成功多少对？男青年 基本条件要求条件外貌 性格 气质 事业 财富年龄外貌性格气质事业财富ACBCA29AACBDCABAD29BABBCBBABB28BAABCCABBD28CABCDDBCAA30CBBBECBCBB28BBCDCABBDC30CBBDCBABCD30ABCCDADCEB28AAACCDBAAA28ABADEBACDA32ABCDBABCAB29BABBCBADEC28ACBBCAABBD30ACCDCABBCC28AABCDDEBAA30AAAEECABAD28AAAEEABACB31BBACCCDAAA29ABAEDABCDE27BCBDB女青年基 本 条 件要 求 条 件 外貌 性格 气质 事业财富 年龄 外貌 性格 气质 事业 财富ACCDA28BABADBABAD25CBBABCBAEA26BACBCABBCD27AABBABDCEC25ABCBBACBCA26BABBCDCBAB30CBAACABAEC31BABABAAACE26CBBBABCDBB27BBAACABBCB28CBABCBECEA26AABBEEACBB26CABCCBBCAA25BAABDCBAAC29BABBBBACDC28BABBAAEEDA25AADACAABBC28CABACBACCE25BBBAADBACD29BBABB注：表中的要求条件一般是指不低于所给的条件。为了方便后面的计算，我们按年龄升序重新对上述两个表格进行排列并且编号：男青年基 本 条 件要 求 条 件 外貌 性格 气质 事业财富 年龄 外貌 性格 气质 事业 财富1ABCDE27BCBDB2BBABB28BAABC3CABBD28CABCD4CBCBB28BBCDC5ADCEB28AAACC6DBAAA28ABADE7BADEC28ACBBC8ABBCC28AABCD9CABAD28BABBC10ACBCA29AACBD11CABAD29BABBC12ABCAB29BABBC13CDAAA29ABAED14DBCAA30CBBBE15ABBDC30CBBDC16BABCD30ABCCD17AABBD30ACCDC18DEBAA30AAAEE19ABACB31BBACC20BACDA32ABCDB女青年基 本 条 件要 求 条 件 外貌 性格 气质 事业财富 年龄 外貌 性格 气质 事业 财富1BABAD25CBBAB2BDCEC25ABCAB3BBCAA25BAABD4AEEDA25AADAC5BACCE25BBBAA6CBAEA26BACBC7ACBCA26BABBC8AAACE26CBBBA9BECEA26AABBE10EACBB26CABCC11ABBCD27AABBA12BCDBB27BBAAC13ACCDA28BABAD14ABBCB28CBABC15BACDC28BABBA16AABBC28CABAC17CBAAC29BABBB18DBACD29BBABB19DCBAB30CBAAC20ABAEC31BABAB注：表格中的要求条件一般是指不低于所给条件3.问题分析 该问题是现实生活中的实际问题，主要就是确定合理配对方案，使得在尽量满足个人要求条件下，使配对成功率尽可能的高。由于每个人的基本条件和要求条件都是给定的，双方彼此是知道的，而且是相互之间有很大的差异，如果完全按照要求条件组合配对成功。任意一对男女的配对可以看成一个随机事件，按某一概率可能配对成功，或不成功。在这里双方的满意度主要反映出一个人对另一个人的客观和主观看法，因此，满意度的定义成为解决问题的一个关键。所谓的“成功率”，就是男女双方最终配对的概率。实际上，可以用他们相互之间的满意度来间接刻画。相互的满意度越高，双方配对的成功率就越大。对于问题（1），要使配对成功率尽可能的高明，也就是给出一种方案，使得20对男女的配对后的满意度之和最高。对于问题（2），要使20对男女青年同时配对，使得全部同时成功的可能性（概率）最大。对于问题（3），因为每人个只能选择一次，能不配对成功取决于双方是不是选中对方，即要看双方彼此的满意度如何。实际中，假如一个男青年（）对一个女青年（）的满意度最高，但对的满意度不一定最高，即若选择，但不一定选择。因此，与不一定配成对，反之亦然。现在的问题是谁选谁，使配对成功的可能性最大呢？这个问题实际上是男女双方在彼此基本了解的情况下，在保证自己一定满意的条件下做出自己的选择，也需要猜测对方会做出怎样的选择。因此，这个问题可能转化为男女双方的对策问题，即转化为求男女双方的非零和对策的纳什平衡点的问题。4. 模型的假设与符号说明41模型的假设 (1)题目所给出的男女青年的评价是客观真实的;(2)每个人在选择双方的时候是理智的; (3)男女青年不会受当时环境的影响。42符号说明K=1,2,3,4,5.分别表示外貌、性格、气质、事业、财富这5个条件；(i=1,2 20)表示年龄升序排列后男青年编号；（j=1,2 20）表示年龄升序排列后女青年编号；( i=1,2 20,k=1,2,3,4,5)表示男青年在k方面的基本条件； ( i=1,2 20,k=1,2,3,4,5)表示男青年在k方面的要求； ( j=1,2 20,k=1,2,3,4,5)表示女青年在k方面的基本条件；( j=1,2 20,k=1,2,3,4,5)表示女青年在k方面的要求；表示男青年i对女青年j在k方面的满意度；表示女青年j对男青年i在k方面的满意度；表示男青年i与女青年j在k方面的满意度之和.5模型的建立和求解5.1条件量化处理 对于每个人的外貌、性格、气质、事业、财富五项条件的5个等级A，B，C，D，E分别作量化处理为5，4，3，2，1。于是根据上表可以得到男女青年的基本条件量化矩阵和要求条件量化矩阵（或称权值矩阵）以及满意度分量分别记为：5.2 满意度现在，我们对满意度进行说明，要确定对的第K项条件的满意度。先对年龄进行筛选，年龄为大于或大于的满意度为0；如果基本条件达不到的要求即,给它赋值为0值.否则，满意度记为刚好达到为1，超过一个等级加1。即满意度为。这样就体现了，当一方实际条件高于对方期望（要求）条件时，则对方对他（她）的好感（相对于要求条件）就会增加，超过得越多，好感增加得越多。5.3模型的建立 我们把二十个青年男女抽象化为40个结点得到一个带权二部图，其中Aj表示二十个男青年，Bj表示二十个女青年，而从男青年到女青年有一条带权边，权则由上面求得的满意度矩阵决定，然后，我们用最大二部图匹配算法（匈牙利算法）求出一个最大匹配的解；但是，一开始所求得的是一个有向图，因此我们必须把它无向化，至此对问题（1）我们仅仅是采用把两结点间权值相加而转化为一个无向图，进而就可以用匈牙利算法对其求解了。而对于问题（2）则要采用图的完美匹配算法（KM算法）进行求解，从而使全部配对成功的可能性最大，对于问题（3），则同样采用匈牙利算法只是把权值改变即可，这里我们把结点间有向边的权值同时大于2且满意度和不满意度差别不是很大时才有可能配对成功此时把它赋为1，而在不满足条件时则赋为0,从而得出能配对成功最多的方案。下面对匈牙利算法和KM算法进行说明。匈牙利算法的主要思想是在每次增广的时候不是找一条增广路而是同时找几条点不相交的最短增广路，形成极大增广路集，随后可以沿着这几条增广路同时进行增广。可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相等的长度，并且随着算法的进行最短增广路的长度是越来越长的，更进一步分析可以证明最多只需增广ceil(sqrt(n)次就可以得到最大匹配（证明在这里略去）。KM算法：（全称是Kuhn-Munkras,是这二个人在1957年提出来的），首先为每个点设立一个顶标Li，设vi,j-为（i,j）边的权，如果可以求得一个完美匹配，使得每条匹配边vi,，其余边。此时的解就是最优的，因为匹配边的权和=，其余任意解的权和都不可能比这个大。5.4模型的求解以题中所给数据为例，我们用EXCEL处理后得到权值，然后编程求得结果为：问题(1)男A1A2A3A4A5A6A7A8A9A10女B18B17B16B15B2B19B3B12B1B14男A11A12A13A14A15A16A17A18A19A20女B20B10B7B8B6B5B4B11B9B13问题(2)男A1A2A3A4A5A6A7A8A9A10女B11B12B19B18B8B5B3B6B2B20男A11A12A13A14A15A16A17A18A19A20女B1B17B7B14B15B13B16B9B4B10问题(3)男A1A3A5A10A12A14A15A17A18A19女B15B18B19B9B2B6B4B14B11B85.5模型修正（1）对满意度的说明首先要注意到两个事实：其一，如果基本条件比的要求条件差得越多，则对的第K项条件的满意度就越小，反之亦然。也就是说，如果一方的实际条件比对方期望（要求）的条件差距越大，则对方对另一方失望就越大，即满意度就越小。其二，如果的基本条件比的要求条件高，则对的第k项条件的满意度（k）就会增加，但增加不会太多。即当一方的实际条件高于对方期望（要求）的条件时，则对方对加一方的好感（相对要求条件）增加不会太大。而在模型中只考虑了实际条件高于要求条件，好感会增加并考虑到实际条件低于要求条件时，失望会增加，即满意度会减小。现在模型的基础上加以改进：如果的基本条件达不到的要求，即（）时，给它赋值它是一个负值，体现了当一方实际条件低于期望（要求）的条件时，则对方对他（她）失望（相对于要求条件）就会增加差距越大，失望度就越大，相应的满意度就越小。显然，改进后成功的解决了上面所提出的问题，所以显得更加合理。满意度矩阵中的各分量分别表示如下：(2) 模型的重新建立 首先,我们把量化的尺度改为1-9尺度把A,B,C,D,E五个等级分别量化为9、7、5、3、1，然后在给出的二部图转化为无向图时则把每个结点分为两个结点，从而问题转化为求40对结点的二部图的最大匹配和完美匹配问题了，对问题1和问题2用同样算法求解，而对于问题3则当满意度矩阵中的权大于零时赋为1而在小于零时则赋为0。（3）以题中所给数据为例，我们用EXCEL处理后得到权值，然后编程求得结果为：问题(1)男A1A2A3A4A5A6A7A8A9A10女B4B18B15B20B2B5B3B13B17B9男A11A12A13A14A15A16A17A18A19A20女B16B10B7B1B6B19B14B11B8B12问题(2)男A1A2A3A4A5A6A7A8A9A10女B2B18B6B14B19B5B3B13B11B20男A11A12A13A14A15A16A17A18A19A20女B1B17B7B12B15B9B16B8B4B10问题(3)男A1A3A5A10A12A14A15A17A18A19女B15B18B19B9B2B6B4B14B11B86. 模型结果的分析 从所得的结果分析可知，模型改进后所得到的结果比改进前所得到的结果更加合理，对问题1是为了要尽量满足个人要求的条件使配对成功率更高，即要使得二部图中的边的权值相对来说是比较大的，而对问题2则是要全部配对成功的可能性最高，即是要使得所得到的完美配对图的权值之和最大即使得要20对同进配对的可能性最大的方案。而对问题3则要在男女双方都满意的前提下并且是双方都选择了双方。则从我们得到的结果可知模型改进后得到的结果比模型要更优。7. 模型的优缺点 对于两个模型，改进前的模型显然比改进后的模型粗糙得多，但是运行起来相对简单，而且在模型中我们运用了匈牙利算法使问题更加简单化，充分体现了熟练运用数学软件在我们运用数学思想解决实际问题中的重要性。而在改进后的模型中，我们利用图论的思想，运用匈牙利算法（二部图的最大匹配算法）和KM算法（二部图的完美匹配算法），并且将原精度提高，采用1-9尺度，使得问题的解答更加精确，但是由于算法太复杂，在计算机计算方面显得比较吃力，运行也相对难以实现一点。在社会上各人的择偶标准不同，所以他们在选择对象的侧重点也会不同，比方说；有的人会特别注重外表，然而有的人特别注重对方的事业和个人的气质等等。而我们在两个模型中，只是简单的将五个方面的五个等级分别赋值为几个数值，不能体现个人的侧重点。同时，我们在模型中假设了对各人的抽样是真实可靠的，然而各人的择偶标准还会随时间不断改变，所以假设不一定会长久成立，若在模型的改进方向上再注意这些问题，结果会更接近现实。参考文献1韩中庚.数学建模方法及其应用M.北京:高等教育出版社，2005.5.2边馥萍,侯文华,梁冯珍.数学模型方法与算法M.北京:高等教育出版社,2005.4.3姜启源,谢金星.数学模型(第三版)M.北京:高等教育出版社,2003.8.4吴乃陵,况迎辉.C+程序设计(第二版)M.北京:高等教育出版社,2006.3.5 Bczdek J, Pal S. Fuzzy Models for Pattern Recognition M. Piscataway: IEEE Press, 1992. 6 zdek J. Pattern Recognition with KM Algorithm M. New York: PlenumBe Press, 1981. 致谢 本文的选题得到了林依勤老师的指导，从撰写到完稿都得到了曾立波老师的悉心指导，在此，对曾立波老师和林依勤老师的帮助表示衷心的感谢。另外本文的完成还得到了罗光辉同学和李鹏同学的帮助，在此也对他们表示衷心的感谢。附 录匈牙利算法#include #include #include using namespace std; bool mark1100,mark2100; int list100; int n,m,edge,num;c ectorvector v; bool dfs(int to) register int i,point,s = listto; for(i=0;ivs.size();i+) point = vsi; if(!mark2point) continue; mark2point = false; if(listpoint=-1 | dfs(point) listpoint = s; return true; return false; void Solve() int i,j,point; bool flog = false; memset(mark1,true,sizeof(mark1); memset(list,-1,sizeof(list); num=0; for(i=0;in;i+) for(j=0;jvi.size();j+) if(listvij = -1) mark1i = false; listvij = i; num+; if(i=0) flog = true; break; for(i=0;in;i+) if(mark1i) if(!vi.empty() memset(mark2,true,sizeof(mark2); for(j=0;jvi.size();j+) point = vij; if(!mark2point) continue; mark2point = false; if(listpoint = -1 | dfs(point) listpoint = i; num+; break; mark1i = false; if(flog | list0 != -1) cout num-1 endl; else cout num n) if(n = 0)break; v.clear(); v.resize(n); cin m edge; for(i=0;i j s d; vs.push_back(d); Solve(); return 0; KM算法：#include #include #include using namespace std; const int size = 160; const int INF = 100000000; / 相对无穷大 bool mapsizesize; / 二分图的相等子图, mapij = true 代表Xi与Yj有边 bool xckdsize, yckdsize; / 标记在一次DFS中，Xi与Yi是否在交错树上 int matchsize; / 保存匹配信息，其中i为Y中的顶点标号，matchi为X中顶点标号 bool DFS(int, const int); void KM_Perfect_Match(const int n, const int edgesize) int i, j; int lxsize, lysize; / KM算法中Xi与Yi的标号 for(i = 0; i n; i+) lxi = -INF; lyi = 0; for(j = 0; j n; j+) lxi = max(lxi, edgeij); bool perfec