玫瑰有约.doc

基于玫瑰有约的数学模型摘要基于目前许多城市大齡青年的婚姻问题引起了社会的广泛关注这一现象，本文针对某单位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对大龄青年男女的年龄、基本条件和要求条件(如下表)。一般认为，男青年至多比女青年大5岁，或女青年至多比男青年大2岁，并且要至少满足个人要求5项条件中的2项，才有可能配对成功。请你根据每个人的情况和要求，建立数学模型帮助妇联解决如下问题：(1) 给出可能的配对方案，使得在尽量满足个人要求的条件下，使配对成功率尽可能的高。(2) 给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大。(3) 假设男女双方都相互了解了对方的条件和要求，让每个人出一次选择，只有当男女双方相互选中对方时才认为配对成功，每人只有一次选择机会。请你告诉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）假设配对过程中五项条件的比重是均等的。三、基本符号说明符号说明第个男青年第个女青年第个男青年对第个女青年的满意度第个女青年对第个男青年的满意度第个男青年与第个女青年配对的满意度第个男青年与第个女青年是否配对四、模型的建立与求解4.1 模型准备4.1.1 数据量化处理为了便于问题的分析和计算，本文将每个人的外貌、性格、气质、事业和财富等五项条件的五个等级A、B、C、D、E分别用数字5、4、3、2、1表示。4.1.2 满意度的确定建立模型时本文引入满意度的概念，记为（），用以表示第个男青年（第个女青年）对第个女青年（第个男青年）的满意程度，可根据已知条件及要求来计算。以第个男青年对第个女青年的满意度为例，计算方法为：（1）分别计算各项条件的满意度。将第个女青年的各项条件与第个男青年的各项要求分别比较，若女青年的条件刚好满足要求，则将该项的满意度加1；若女青年的条件超出要求，则在加1的基础上再加0.5倍的超出量（量化处理后的条件与要求的差值）；否则，该项的满意度为0；（2）将各项条件的满意度累加就是总体满意度；（3）若男青年的年龄比女青年大5岁以上，或小2岁以上，则满意度置为0；（4）如果女青年满足要求的条件不超过2项，满意度置为0。（5）第个男青年与第个女青年配对的满意度，由第个男青年对第个女青年的满意度与第个女青年对第个男青年的满意度之和来计算，即 （4-1）4.2 问题一的模型建立与求解4.2.1 问题一的模型建立模型一：用匈牙利算法求解最大匹配问题假设双方的基本条件均满足对方要求条件的两项以上且年龄差符合要求，则双方配对成功。该问题要求配对成功率尽可能的高，即配对成功的男女青年对数尽可能多。由于双方的条件均满足对方要求的两项以上且满足年龄要求时，否则，故引入0-1变量，以配对成功的对数最多为目标函数，以每人最多只能和一个人配对为约束条件，建立基于匈牙利算法的0-1规划模型： （4-2）用匈牙利算法求解时，将二十对青年男女分别抽象化为二部图的两个顶点集的元素，作为各条边的权值，就得到一个带权二部图。其中，表示第个男青年，表示第个男青年。然后，用匈牙利算法求解，其步骤为：第一步：对效益矩阵进行变换，使每行每列都出现有0元素。（1）从权矩阵中每一行减去该行的最小元素；（2）再在所得矩阵中每一列减去该列的最小元素，所得矩阵记为 。第二步：将矩阵中0元素置为1元素，非零元置为0元素，记此矩阵为。第三步：确立独立1元素组。（1）在矩阵E含有1元素的各行中选择1元素最少的行，比较该行中各1元素所在的列中1元素的个数，选择1元素的个数最少的一列那个1元素；（2）将所选的1元素所在的行和列清零；（3）重复第二步和第三步，直到没有1元素为止，即得到一个独立1元素组。第四步：判断是否为最大独立1元素组。（1）如果所得独立1元素组是权矩阵的最大独立1元素组（即1元素组的个数等于矩阵的阶数），则已得到最优解，停止计算。（2）如果所得独立1元素组还不是权矩阵的最大独立1元素组，那么利用寻找可扩路的方法对其进行扩张，进行下一步。第五步：利用寻找可扩路方法确定最大独立1元素组（1）做最少的直线覆盖矩阵的所有0元素；（2）在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最小元素，在没被直线覆盖的各列加上此最小元素，得到一个新的矩阵，返回第二步。由以上步骤，最终所得的1元素组中1元素的横、纵坐标分别表示配对的男女青年，此时的分配方案即为最优分配方案。模型二：用KM算法求解最优配对问题模型一是基于“若双方的基本条件均满足对方要求条件的两项以上且年龄差符合要求则双方配对成功”的假设而建立的一个简单模型。当此假设不成立时，该模型就不在适用，为此本文建立了一个适用范围更加广泛的模型。要满足配对成功率尽可能的高的要求，只需要求每对男女青年的满意度之和尽可能高即可。同样引入0-1变量，以所有人的配对满意度之和最大为目标函数，每个人最多只能和一个人配对为约束条件，建立基于KM算法的0-1规划模型： （4-3）在匹配问题的模型中，将20个男青年和20个女青年看做图的两个顶点集，每边加了权，表示和配对的满意度，用KM算法求加权图上的权最大的完美对集即为最优配对方案。具体步骤如下：第一步：选定初始可行顶点标号，确定，在中选取一个对集。第二步：若中顶点皆被许配，停止，即的权最大的完美对集；否则，取中未被许配的顶点，令，。第三步：若，转至第四步；若，则： （4-4） （4-5） （4-6） （4-7）第四步：选中一顶点，若已被许配，且，则，转至第三步；否则，取中一个可增广轨，令 （4-8）转至第二步，其中是中的相邻顶点集。4.2.2 问题一的模型求解（1）模型一的结果及结果分析 模型一的结果：借用匈牙利算法编写MATLAB程序求解，得到最优解为20，即20对男女青年都可以配对成功，具体的配对方案如表1所示。表1 模型一的配对方案男青年12345678910女青年12345679810男青年11121314151617181920女青年11121314151617181920 结果分析：根据结果可知，配对的成功率为100%。虽然成功率已经达到最高，但该结果是建立在“若双方的基本条件均满足对方要求条件的两项以上且年龄差符合要求则双方配对成功”的假设成立的基础上实现的，适用范围小，误差较大。（2）模型二的结果及结果分析 模型二的结果：借用KM算法编写MATLAB程序求解，可求得20对男女青年配对满意度的总和最大为152，每对青年男女的平均满意度为7.6，其配对方案如表2。表2 模型二的配对方案男青年12345678910女青年54161015116201218男青年11121314151617181920女青年31971417198132 结果分析：当一方的基本条件恰好有两项满足对方的要求条件时，其满意度的值等于2。而根据求解结果计算出每个人的平均满意度为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）模型说明：由于满意度确定时，已充分考虑了年龄限制以及至少满足两项条件等要求，约束条件中无需赘述，只要保证为0-1变量，且男女青年只能进行一次配对即可。4.3.2问题二的模型求解用LINGO软件编程求解，可得当20对男女青年同时配对成功的可能性最高时，满意度最低的一对男女青年的满意率为7.5，最优配对方案如表3所示。表3 问题二的配对方案男青年12345678910女青年81812171694111419男青年11121314151617181920女青年20313621715510当按照这种方案配对时，满意度最低的一对男女青年的满意度为7.5，与问题一的模型二所得平均每对男女青年的满意度为7.6相比，相差不多，故此方案合理，可以确保20对男女青年都配对成功的可能性为最高。4.4 问题三的模型建立与求解4.4.1 问题三的模型建立当男女双方都相互了解了对方的条件和要求，而做出选择时，就会倾向于选择符合自己心意的人，但是实际中一个男青年对一个女青年的满意度最高，而该女青年对男青年的满意度不一定最高，即若选择，但不一定选择。因此，两人不一定配对成功。因此要使成功的可能性大，应保证配对的男女青年的满意度足够高，且双方对对方的满意程度相差不多。这里假设满意度高于6.5且男女双方满意度不超过1时，可视为配对成功。为了达到上述要求，以男女青年配对成功的对数最多作为目标函数，以满意度的和与差都符合上述条件为约束，建立0-1规划模型： （4-10）模型说明：（1）每对男女青年的满意度不小于6.5；（2）男女双方的满意度相差不能超过1；（3）每个人最多只能和一个人配对；（4）是0-1变量。4.4.2 问题三的模型求解用LINGO软件编程求解，可知最多有20对男女青年可配对成功。具体的配对方案如表4所示。表4 问题三的配对方案男青年12345678910女青年11918172051311519男青年11121314151617181920女青年87616141224103这种配对方案是在每对男女青年的满意度均高于6.5，且双方满意度只差小于1，所以该方案较为合理。考虑到在满意度定义时，将单项不满足要求时的满意度置为了0，而实际中满意度会随着低于要求的程度而减小。故将满意度的定义重新调整为各项的条件与要求的差值之和，再重新分析上述方案的合理性发现有5对男女青年双方的满意程度差值过大（超过了3），排除这5对男女青年后，可得最优方案如表5所示。表5 调整后的最优配对方案男青年1234578101214女青年11918172013119716男青年1516171819女青年14122410五、模型的评价与改进5.1 模型的优点（1）模型一是最大匹配问题，在约束条件内，使配对的对数尽可能的高，原理简单易懂，适用于解决指派问题，是指派问题中比较高效、经典的算法。（2）模型二，是完美匹配问题，提高了精确度。根据满意度重新进行配对，满意度越高，越符合实际，从而提高配对成功率。（3）本模型比较接近实际生活，使建立的模型真正运用到实际生活，充分体现了熟练运用数学软件在我们运用数学思想解决实际问题中的重要性。5.2 模型的缺点（1）针对模型一，考虑到实际情况，当双方的各方面的条件差距比较大时成功率明显不会很高，可能与实际存在一定误差。（2）针对模型二，由于精确度的提高，时间复杂度在一定程度上有所增大，可能在解决数据偏大的问题时带来一定困难。（3）本文所建立的模型只考虑了年龄、外貌、性格、气质、事业、财富几个方面，这几个方面的权重一样，实际中每个人所要求的权重是不一定一样；实际情况还可能考虑的因素会更多，相应的权值会发生变化，结果随之变化。5.3 满意度的改进根据男青年与女青年各方面的条件和要求，计算出大家对各项的重视程度，运用统计知识计算各方面的权重，使满意度在完美匹配的定义下得到改进，从而使得到的结果更优化。5.4 问题三的改进原模型的条件在满意度中给出了各方面的差值限制和总体满意度的高度，如果把这两个条件也当做目标函数，改成多目标优化问题，即差值限制、总体满意度的高度、配对率最高，三者同时最优，从而使得到的方案最优。其模型如下 （6-1） （6-2）解多目标函数比较困难，可以采用权重的处理方式将三个目标转换成为一个目标，如果对某个目标的结果不满意，可通过调整目标之间的比例重新进行优化，直到满意为止，结果应该比原结果更合理。六、模型的推广本文所建立的模型可稍加改进运用到一些有关交友或找男女朋友的网站，进行电脑配对，帮助会员找人，给会员一个参考值；本模型还可以运用各种任务分配性问题，比如，某个公司有固定的员工，给出员工在一些方面的熟练度，根据熟练度可运用本模型给出最合理方案，是公司效益最高。七、参考文献1 姜启源 谢金星 叶俊.数学模型(3版).北京：高等教育出版社.2003. 2 李学文 李炳照 王宏洲.数学建模优秀论文精选与点评(2005-2010).北京：清华大学出版社.2011.3 宣明.数学建模与数学实验.J杭州：浙江大学出版社.2010.4 刘卫国MATLAB程序设计与应用（第二版）北京高等教育出版社.2006.附 录附录1：满意度的计算程序%满意度计算; %男青年的条件M1=slread(男青年的条件.xls);M2=slread(男青年的要求.xls);F1=slread(女青年的条件.xls);F2=slread(女青年的要求.xls)；for i=1:20; for 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) %年龄判断 for k=1:5; if 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 if 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 if (cm=2&cf=2)%判断是否至少有两项满足要求 R(i,j)=sM(i,j)+sF(j,i);%男女青年满意度之和 end end end endendRsMsF附录2：KM算法程序A=R;n=20;for(i=1:n) L(i,1)=0;L(i,2)=0;end for(i=1:n) for(j=1:n) if(L(i,1)L(S(i),1)+L(j,2)-A(S(i),j) al=L(S(i),1)+L(j,2)-A(S(i),j); end end end for(i=1:jss) L(S(i),1)=L(S(i),1)-al; end %调整可行点标记 for(j=1:jst) L(T(j),2)=L(T(j),2)+al; end %调整可行点标记 for(i=1:n) for(j=1:n) %生成子图GL if(L(i,1)+L(j,2)=A(i,j) Gl(i,j)=1; else Gl(i,j)=0; end M(i,j)=0;k=0; end end ii=0;jj=0; for(i=1:n) for(j=1:n) 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的饱和点 for(i=1:n) 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); %S=Sx, T=Ty else %获得Gl的一条M-增广路,调整匹配M for(k=1:jst) M(S(k),T(k)=1; M(S(k+1),T(k)=0; end if(jst=0) k=0; end M(S(k+1),NlS(jj)=1;break; end end endendMaxZjpp=0; for(i=1:n) for(j=1:n) if(M(i,j) MaxZjpp=MaxZjpp+A(i,j); end endendM %显示最佳匹配M MaxZjpp/40