玫瑰有约

基于玫瑰有约的数学模型摘要基于目前许多城市大齡青年的婚姻问题引起了社会的广泛关注这一现象，本文针对某单位20对大龄青年男女，建立0-1规划模型，解决了该单位的男女配对问题。对于第（1）问20对青年男女的最大匹配问题，本文首先构造了20对青年男女的基本条件矩阵和要求条件矩阵，再结合年龄限制和个人要求构造了满意度矩阵。接着引入了0-1变量，分别以配对成功的对数最多和20对青年男女的满意度之和最大为目标函数，以每人最多只能和一个人配对为约束，建立了基于匈牙利算法的0-1规划模型和基于KM算法的0-1规划模型。最后对这两个模型进行了比较，选择较优的模型二进行配对，并利用LINGO编程解得满意度总和为152，每对青年男女的平均满意度为7.6，并给出了该单位20对青年男女的配对方案如表2，得出了配对成功率为100%（即20对青年男女可同时配对成功）的结论。对于第（2）问，本文同样引入了0-1变量，以20对青年男女中满意度的最小值最大为目标函数，以每人恰好配对一次为约束，建立了基于KM算法的0-1规划模型，并利用LINGO编程解出了该单位20对青年男女同时配对成功的最佳方案如表3，且满意度最低的一对青年男女的满意度为7.5，并将其与第一问的结果7.6进行了比较，从而得出该方案的成功可能性最大的结论。

对于第（3）问，本文重新定义了配对成功的概念并给出了一个新的假设，引入0-1变量，以男女青年配对成功的对数最多作为目标函数，以每人最多跟一个人配对以及满意度的和与差都符合上述假设为约束条件，建立了0-1规划模型，并利用LINGO编程解出了20对青年男女的选择方案如表4。最后考虑实际中满意度的变化，本文对该方案作出修正，最终配对成功的对数为15对，修正后的最优方案如表5。最后本文对所建立的模型进行了评价和改进，并将其推广到其他领域。关键词：玫瑰有约二部图的最佳匹配0-1整数规划匈牙利算法KM算法一、问题重述与分析1.1问题重述目前在许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注。某单位现有20对大龄青年男女，每个人的基本条件都不相同，如外貌、性格、气质、事业、财富等。每项条件通常可以分为五个等级A、B、C、D、E，如外貌、性格、气质、事业可分为很好、好、较好、一般、差；财富可分为很多、多、较多、一般、少。每个人的择偶条件也不尽相同，即对每项基本条件的要求是不同的。该单位的妇联组织拟根据他(她)们的年龄、基本条件和要求条件进行牵线搭桥。下面给出20对大龄青年男女的年龄、基本条件和要求条件(如下表)。

一般认为，男青年至多比女青年大岁，或女青年至多比男青年大2岁，并且要至少满足个人要求5项条件中的2项，才有可能配对成功。请你根据每个人的情况和要求，建立数学模型帮助妇联解决如下问题：给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最假设男女双方都相互了解了对方的条件和要求，让每个人出一次选择，只有当男女双方相互选中对方时才认为配对成功，每人只有一次选择机会。请你告诉20女青年都应该如何做出选择，使得自己的成功的可能性最大？按你的选择方案最多能配对成功多少对？1.2问题分析本文要解决的是关于大龄青年男女配对的问题，若将20对青年男女分别看成二部40个点，则该问题转化为二部图的匹配问题，利用匈牙利算法和KM算法编程求解。在进行匹配的过程中，需要将这20对青年男女的基本条件和要求条件进行量化，再结合满意度分别建立他们的基本条件矩阵和要求条件矩阵，从而建立0-1整数规划模型，利用相关算法编程求解。1.2.1对问题（1）的分析对于问题（1）中的“成功率”，本文将其理解为20对青年男女最后配对成功的对数与总对数20的比值，这样就将问题（1）转化为一个二部图的最大匹配问题。考虑到年龄差距和满意度都要符合题目要求，本文分别选用匈牙利算法和KM算法求得两种方案，并进行比较选择更优的一个方案作为问题（1）的最终配对方案。

1.2.2对问题（2）的分析对于问题（2）中“成功的可能性最大”中的“可能性”，本文将其理解为“概率”，即本文认为只要20对青年男女中配对成功概率最小的一对的概率最大，那么20对青年男女的同时配对成功的平均概率就最大。1.2.3对问题（3）的分析问题（3）与前面两问的区别在于男女双方都相互了解对方的条件和要求，且每人只有一次选择机会，这样每个人就会选择和自己的条件相差不大的对象。要使自己配对成功的概率最大，那么每个人在选择对象时，既要求对方基本条件满足自己的要求条件，又要求自己的基本条件满足对方的要求条件，而且双方的满意度相差不能太大。二、模型假设（1）假设男女青年的择偶要求只包括外貌、性格、气质、事业、财富以及年龄这六项，不考虑其他因素；（2）假设已给出的男女青年的基本条件及要求真实可靠；（3）假设男女青年严格按照对方条件及自身要求来择偶，不受其他因素影响；（4）假设满足对方要求少于2项，则配对成功的可能性为0；（5）假设配对过程中五项条件的比重是均等的。三、基本符号说明符号说明个女青年ij个女青年的满意度ij个女青年对第i个男青年的满意度ij个女青年配对的满意度ij个女青年是否配对四、模型的建立与求解4.1模型准备4.1.1数据量化处理为了便于问题的分析和计算，本文将每个人的外貌、性格、气质、事业和财富等五分别用数字5、4、3、2、1表示。

4.1.2满意度的确定建立模型时本文引入满意度的概念，记为ij），用以表示第i个男青年（第个女青年（第i个男青年）的满意程度，可根据已知条件及要求来计算。个女青年的满意度为例，计算方法为：（1）分别计算各项条件的满意度。将第个女青年的各项条件与第i个男青年的各项要求分别比较，若女青年的条件刚好满足要求，则将该项的满意度加1；若女青年的条件超出要求，则在加1的基础上再加0.5倍的超出量（量化处理后的条件与要求的差值）；否则，该项的满意度为0；（2）将各项条件的满意度累加就是总体满意度；（3）若男青年的年龄比女青年大5岁以上，或小2岁以上，则满意度置为0；（4）如果女青年满足要求的条件不超过2项，满意度置为0。个女青年配对的满意度，由第i个男青年对第个女青年的满意度与第个女青年对第i个男青年的满意度之和来计算，即（4-1）4.2问题一的模型建立与求解4.2.1问题一的模型建立模型一：用匈牙利算法求解最大匹配问题假设双方的基本条件均满足对方要求条件的两项以上且年龄差符合要求，则双方配对成功。该问题要求配对成功率尽可能的高，即配对成功的男女青年对数尽可能多。由于双方的条件均满足对方要求的两项以上且满足年龄要求时入0-1变量ij，以配对成功的对数最多为目标函数，以每人最多只能和一个人配对为约束条件，建立基于匈牙利算法的0-1规划模型：（4-2）用匈牙利算法求解时，将二十对青年男女分别抽象化为二部图G 的两个顶点集的元 表示第i个男青年， 个男青年。

然后，用匈牙利算法求解，其步骤为：第一步：对效益矩阵进行变换，使每行每列都出现有0 元素。 （1）从权矩阵C 中每一行减去该行的最小元素； （2）再在所得矩阵中每一列减去该列的最小元素，所得矩阵记为D 元素置为1元素，非零元置为0 元素，记此矩阵为E 第三步：确立独立1元素组。 （1）在矩阵E 含有1 元素的各行中选择1 元素最少的行，比较该行中各1 元素所 元素的个数，选择1元素的个数最少的一列那个1 元素； 元素所在的行和列清零；（3）重复第二步和第三步，直到没有1 元素为止，即得到一个独立1 元素组。 第四步：判断是否为最大独立1 元素组。 （1）如果所得独立 元素组的个数等于矩阵的阶数），则已得到最优解，停止计算。 （2）如果所得独立 元素组，那么利用寻找可扩路的方法对其进行扩张，进行下一步。 第五步：利用寻找可扩路方法确定最大独立1 元素组 （1）做最少的直线覆盖矩阵D 的所有0 元素； （2）在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最 小元素，在没被直线覆盖的各列加上此最小元素，得到一个新的矩阵，返回第二步。 由以上步骤，最终所得的1 元素组中1 元素的横、纵坐标分别表示配对的男女青年， 此时的分配方案即为最优分配方案。

模型二：用KM 算法求解最优配对问题 模型一是基于“若双方的基本条件均满足对方要求条件的两项以上且年龄差符合要 求则双方配对成功”的假设而建立的一个简单模型。当此假设不成立时，该模型就不在 适用，为此本文建立了一个适用范围更加广泛的模型。 要满足配对成功率尽可能的高的要求，只需要求每对男女青年的满意度之和尽可能 高即可。同样引入0-1 变量 ij ，以所有人的配对满意度之和最大为目标函数，每个人最多只能和一个人配对为约束条件，建立基于KM算法的0-1 规划模型： （4-3）在匹配问题的模型中，将20 个男青年 和20个女青年 看做图G的两个顶点集， 每边加了权 ij 配对的满意度，用KM 算法求加权图G 上的权最大的完美 对集即为最优配对方案。具体步骤如下： 第一步：选定初始可行顶点标号l ，确定 中顶点皆被M许配，停止，M 中未被M许配的顶点u （4-7）第四步：选 已被M许配，且 中一个M可增广轨 （4-8）转至第二步，其中 的相邻顶点集。4.2.2 问题一的模型求解 （1）模型一的结果及结果分析 模型一的结果：借用匈牙利算法编写 程序求解，得到最优解为 20，即 20 对男女青年都 可以配对成功，具体的配对方案如表1 所示。

模型一的配对方案男青年 10女青年 10男青年 11 12 13 14 15 16 17 18 19 20 女青年 11 12 13 14 15 16 17 18 19 20 结果分析：根据结果可知，配对的成功率为 100%。虽然成功率已经达到最高，但该结果是建 立在“若双方的基本条件均满足对方要求条件的两项以上且年龄差符合要求则双方配对 成功”的假设成立的基础上实现的，适用范围小，误差较大。 （2）模型二的结果及结果分析 模型二的结果：借用KM算法编写 程序求解，可求得20 对男女青年配对满意度的总和最 大为152，每对青年男女的平均满意度为7.6，其配对方案如表2。 模型二的配对方案男青年 10女青年 1610 15 11 2012 18 男青年 11 12 13 14 15 16 17 18 19 20 女青年 1417 结果分析：当一方的基本条件恰好有两项满足对方的要求条件时，其满意度的值等于 据求解结果计算出每个人的平均满意度为3.8，该平均满意度大于题目所要求的满意度，故所求结果比较满意，该模型比较合理。 4.2.3 模型一与模型二的比较 根据模型一的结果显示，成功率达到100%，即20 对青年男女全部配对成功。

但该 模型的适用范围较小，误差较大。与模型一相比，模型二适用范围较大，更符合实际情 况，且所得结果为平均每人的满意度为3.8，比题目所要求的满意度2 高出了1.8。其结 果比较符合题意，是成功率最高的最优结果。 综上所述，模型二比模型一更优，本文选用模型二的方案作为大龄青年男女的最佳 配对方案。 4.3 问题二的模型建立与求解 4.3.1 问题二的模型建立 问题一中求得的方案可满足配对的总体成功率最高，但并不能保证 20 对男女青年 同时配对成功的可能性最大。为了满足这个要求，需重新建立模型，使得 20 对男女青 年配对成功的可能性中的最小值尽可能大。故引入 0-1 变量，以 20 对男女青年中满意 度的最小值最大为目标函数，以每人恰好配对一次为约束，建立0-1 规划模型： （4-9）模型说明： 由于满意度 ij 确定时，已充分考虑了年龄限制以及至少满足两项条件等要求，约束条件中无需赘述，只要保证 ij 为0-1变量，且男女青年只能进行一次配对即可。 4.3.2 问题二的模型求解 用LINGO 软件编程求解，可得当20 对男女青年同时配对成功的可能性最高时，满 意度最低的一对男女青年的满意率为7.5，最优配对方案如表3 所示。

问题二的配对方案男青年 10女青年 1812 17 16 1114 19 男青年 11 12 13 14 15 16 17 18 19 20 女青年 20 10当按照这种方案配对时，满意度最低的一对男女青年的满意度为 7.5，与问题一的 模型二所得平均每对男女青年的满意度为7.6 相比，相差不多，故此方案合理，可以确 保20 对男女青年都配对成功的可能性为最高。 4.4 问题三的模型建立与求解 4.4.1 问题三的模型建立 当男女双方都相互了解了对方的条件和要求，而做出选择时，就会倾向于选择符合 自己心意的人，但是实际中一个男青年 的满意度最高，而该女青年对男青年的满意度不一定最高，即若 。因此，两人不一定配对成功。因此要使成功的可能性大，应保证配对的男女青年的满意度足够高，且双 方对对方的满意程度相差不多。这里假设满意度高于6.5 且男女双方满意度不超过1 可视为配对成功。为了达到上述要求，以男女青年配对成功的对数最多作为目标函数，以满意度的和 与差都符合上述条件为约束，建立0-1 规划模型： （4-10）模型说明： （1）每对男女青年的满意度不小于6.5； （2）男女双方的满意度相差不能超过1； （3）每个人最多只能和一个人配对； 是0-1变量。

4.4.2 问题三的模型求解 用LINGO 软件编程求解，可知最多有20 对男女青年可配对成功。具体的配对方案 如表4 所示。 问题三的配对方案男青年 10女青年 11 1817 20 1519 男青年 11 12 13 14 15 16 17 18 19 20 女青年 1614 12 这种配对方案是在每对男女青年的满意度均高于6.5，且双方满意度只差小于1，所以该方案较为合理。 考虑到在满意度定义时，将单项不满足要求时的满意度置为了 0，而实际中满意度 会随着低于要求的程度而减小。故将满意度的定义重新调整为各项的条件与要求的差值 之和，再重新分析上述方案的合理性发现有5 对男女青年双方的满意程度差值过大（超 过了3），排除这5 对男女青年后，可得最优方案如表5 所示。 调整后的最优配对方案男青年 1012 14 女青年 11 1817 20 13 16男青年 15 16 17 18 19 女青年 14 12 10五、模型的评价与改进 5.1 模型的优点 （1）模型一是最大匹配问题，在约束条件内，使配对的对数尽可能的高，原理简 单易懂，适用于解决指派问题，是指派问题中比较高效、经典的算法。

（2）模型二，是完美匹配问题，提高了精确度。根据满意度重新进行配对，满意 度越高，越符合实际，从而提高配对成功率。 （3）本模型比较接近实际生活，使建立的模型真正运用到实际生活，充分体现了 熟练运用数学软件在我们运用数学思想解决实际问题中的重要性。 5.2 模型的缺点 （1）针对模型一，考虑到实际情况，当双方的各方面的条件差距比较大时成功率 明显不会很高，可能与实际存在一定误差。 （2）针对模型二，由于精确度的提高，时间复杂度在一定程度上有所增大，可能 在解决数据偏大的问题时带来一定困难。 （3）本文所建立的模型只考虑了年龄、外貌、性格、气质、事业、财富几个方面， 这几个方面的权重一样，实际中每个人所要求的权重是不一定一样；实际情况还可能考 虑的因素会更多，相应的权值会发生变化，结果随之变化。 5.3 满意度的改进 根据男青年与女青年各方面的条件和要求，计算出大家对各项的重视程度，运用统 计知识计算各方面的权重，使满意度在完美匹配的定义下得到改进，从而使得到的结果 更优化。 5.4 问题三的改进 原模型的条件在满意度中给出了各方面的差值限制和总体满意度的高度，如果把这 两个条件也当做目标函数，改成多目标优化问题，即差值限制、总体满意度的高度、配 对率最高，三者同时最优，从而使得到的方案最优。

其模型如下 （6-2）解多目标函数比较困难，可以采用权重的处理方式将三个目标转换成为一个目标， 如果对某个目标的结果不满意，可通过调整目标之间的比例重新进行优化，直到满意为 止，结果应该比原结果更合理。 六、模型的推广 本文所建立的模型可稍加改进运用到一些有关交友或找男女朋友的网站，进行电脑 配对，帮助会员找人，给会员一个参考值；本模型还可以运用各种任务分配性问题，比 如，某个公司有固定的员工，给出员工在一些方面的熟练度，根据熟练度可运用本模型 给出最合理方案，是公司效益最高。 七、参考文献 谢金星叶俊.数学模型(3 版).北京：高等教育出版社.2003. 王宏洲.数学建模优秀论文精选与点评(2005-2010).北京：清华大学出版社.2011. 刘卫国．程序设计与应用（第二版）．北京高等教育出版社.2006. 附录1：满意度的计算程序%满意度计算; %男青年的条件 M1=(´男青年的条件.xls´); M2=(´男青年的要求.xls´); F1=(´女青年的条件.xls´); F2=(´女青年的要求.xls´)； j=1:20;sM(i,j)=0; %第i个男青年对第j个女青年的满意度 sF(j,i)=0; %第j个女青年对第i个男青年的满意度 cm=0; %女青年达到男青年要求的项目数 cf=0; %男青年达到女青年要求的项目数 if(M1(i,6)=F1(j,6)-2) %年龄判断 F1(j,k)>=M2(i,k)cm=cm+1; sM(i,j)=sM(i,j)+1+0.5*(F1(j,k)-M2(i,k)); end M1(i,k)>=F2(j,k)cf=cf+1; sF(j,i)=sF(j,i)+1+0.5*(M1(i,k)-F2(j,k)); end (cm>=2&cf>=2)%判断是否至少有两项满足要求R(i,j)=sM(i,j)+sF(j,i);%男女青年满意度之和 end end end end end sMsF 附录2：KM算法程序 A=R;n=20; end%初始可行点标记L Gl(i,j)=1;else Gl(i,j)=0; end end end ii=0;jj=0; if(Gl(i,j))ii=i;jj=j;break; end end if(ii) break; end end %获得仅含Gl的一条边的初始匹配M M(ii,jj)=1; (1) k=0;break;end end break;end end break;end %获得最佳匹配M,算法终止 S(1)=i;jss=1;jst=0; %S={xi}, while(1)jsn=0; for(i=1:jss) if(Gl(S(i),j))jsn=jsn+1; NlS(jsn)=j; %NL(S)={v|uS,uvEL} for(k=1:jsn-1) if(NlS(k)==j) jsn=jsn-1; end end end end end if(jsn==jst) pd=1; %判断NL(S)=T? for(j=1:jsn) if(NlS(j)~=T(j)) pd=0;break; end end end if(jsn==jst&pd) al=Inf; %如果NL(S)=T,计算al, Inf为 for(i=1:jss) pd=1;for(k=1:jst) pd=0;break;end end if(pd&al>L(S(i),1)+L(j,2)-A(S(i),j)) end for(i=1:jss) end%调整可行点标记 for(j=1:jst) end%调整可行点标记 Gl(i,j)=1;else Gl(i,j)=0; end ii=0;jj=0; if(Gl(i,j))ii=i;jj=j;break; end end if(ii) break; end end %获得仅含Gl的一条边的初始匹配M M(ii,jj)=1; break; else %NL(S)T for(j=1:jsn) pd=1; %取yNL(S)\T for(k=1:jst) if(T(k)==NlS(j)) pd=0;break; end end if(pd) jj=j;break; end end pd=0; %判断y是否为M的饱和点 if(M(i,NlS(jj)))pd=1;ii=i;break; end end if(pd)jss=jss+1; S(jss)=ii; jst=jst+1; T(jst)=NlS(jj); else%获得Gl的一条M-增广路,调整匹配M for(k=1:jst) endif(jst==0) endM(S(k+1),NlS(jj))=1;break; end end end end =0; =+A(i,j);end end end %显示最佳匹配/40 %显示最佳匹配M的权,程序结束 附录3：匈牙利算法 m=20;n=20; A=(´.xls´); break;end; end %求初始匹配M break;end; end %获得仅含一条边的初始匹配M while(1) end%将记录X中点的标号和标记* end%将记录Y中点的标号和标记* for(i=1:m)pd=1; %寻找X中 M的所有非饱和点 if(M(i,j))pd=0;end; end if(pd)x(i)=-n-1; end; end M的所有非饱和点都给以标号0和标记*, 程序中用n+1 表示0 标号, 标号为负数时 表示标记* pd=0; while(1)xi=0; if(x(i)1)k=k-1; for(j=1:k)pdd=1; if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break; end; end %将yj在M中与之邻接的点xk xkyjM),给以标号j 和标记* if(pdd) break; end; end if(pdd)k=1;j=yy(j); %yj 不是M的饱和点 %任取M的一个非饱和点yj, 逆向返回 if(j==n+1) break; end %找到X中标号为0 的点时结束, 获得 M-增广路P k=k+1; end 中出现的边去掉else end;end %将增广路P中没有在匹配 M中出现的边加入到匹配M中 break; end; end; end if(pd) break; end; end %假如X中所有有标号的点都已去掉了标记*, 算法终止 %显示最大匹配M,程序结束