《玫瑰有约问题.doc》由会员分享，可在线阅读，更多相关《玫瑰有约问题.doc（14页珍藏版）》请在三一文库上搜索。
1、关于玫瑰有约的数学模型 摘 要当今社会，城市大龄青年的婚姻问题已引起了广泛关注。针对这一现象，假设某单位有20对大龄青年男女，每个人的基本条件和择偶条件都各不相同。该单位的妇联组织拟根据他们的年龄、基本条件和要求条件牵线搭桥。本文根据每个人的基本条件和要求，建立数学模型帮助妇联解决这个问题。首先，我们定义了好感度、好感度增量和成功指数。好感度是男方（女方）对女方（男方）符合自己要求条件的一个量化指标，其中若不满足2个要求条件（包括只满足一个要求条件和完全不满足的情况）或年龄条件不符合（男青年至多比女青年大5岁，或女青年至多比男青年大2岁），我们定义此时的好感度为0；若只满足3个要求条件，好感度
2、为3；依次类推，若5个要求条件都满足，好感度为5。考虑到两个同样满足要求条件的对象，某个单项条件的突出可能会影响到最后的选择，所以我们又引入了好感度增量，即在好感度不为0的情况下，某个自身条件优于要求条件一个等级（如男青年要求外貌为B,而某女青年的外貌为A），好感度增量为0.5。而成功指数则是考量男女双方的配对成功率，具体算法为：成功指数=(好感度+好感度增量)（男对女）（好感度+好感度增量）（女对男）。建立矩阵（表示号男青年配对号女青年的成功指数）。用matlab处理数据得出矩阵。针对问题（一）要使配对成功率尽可能的高，也就是给出一种方案，使得20对男女的配对成功指数最高。我们把二十个青年男
3、女抽象化为40个结点得到一个带权二部图，其中Aj表示二十个男青年，Bj表示二十个女青年，而从男青年到女青年有一条带权边，权则由上面求得的成功指数矩阵M决定，然后，我们用最大二部图匹配算法（匈牙利算法）求出一个最大匹配的解，进而就可以用匈牙利算法对其求解。针对问题（二）求解出的匹配方案应使20对男女青年可以全部配对（即没有一对的成功指数为0），且配对成功率之和最高，抽象成数学问题即求解二分图的最大权完全匹配解。采用KM算法。针对问题（三）要使每个个体配对成功的可能性最大，要保证配对的男女青年的成功指数足够高，而且两者好感度（*）差值的绝对值不能太大，因此我们定义了两者好感度（*）差值的绝对值为差
4、异指数，规定成功指数应大于所有配对成功指数的平均值（成功指数为0的情况除外）；差异指数应小于差异指数均值的一半。1问题重述目前，许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注。某单位现有20对大龄青年男女，每个人的基本条件都不相同，如外貌、性格、气质、事业、财富等。每项条件由高到低可以分为五个等级A、B、C、D、E。每个人的择偶条件也不尽相同。该单位的妇联组织拟根据他(她)们的年龄、基本条件和要求条件进行牵线搭桥。一般认为，男青年至多比女青年大5岁，或女青年至多比男青年大2岁 ，并且要至少满足个人要求5项条件中的2项，才有可能配对成功。要求根据现有的20对大龄青年男女的年龄、基本条
5、件和要求条件等统计数据。建立数学模型，对以下三个问题做出解答： （1）给出可能的配对方案，使得在尽量满足个人要求的条件下，使配对成功率尽可能的高。（2） 给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大。（3）假设男女双方都相互了解了对方的条件和要求，让每个人出一次选择，只有当男女双方相互选中对方时才认为配对成功，每人只有一次选择机会。提出方案，告诉20对男女青年都应该如何做出选择，使得各自的成功的可能性最大？按你的选择方案最多能配对成功多少对？2模型假设与符号说明1问题假设（1）本文只以外貌、性格、气质、事业、财富这5个因素来衡量每个个体的基本条件和择偶的要求条件，不
6、考虑其他因素。（2）假设不满足某方要求条件的2项，配对成功的几率为0。（3）假设男女青年择偶不会受当时环境的影响。2符号说明表示号男青年的基本条件表示号男青年的要求条件表示号男青年对号女青年的好感度表示号男青年对号女青年的好感度增量表示号女青年的基本条件表示号女青年的要求条件表示号女青年对号男青年的好感度表示号女青年对号男青年的好感度增量表示号男青年配对号女青年的成功指数3 模型的建立和求解3.1条件量化处理对于每个人的外貌、性格、气质、事业、财富五项条件的5个等级A，B，C，D，E分别作量化处理为5，4，3，2，1。于是根据附录4可以得到男女青年的基本条件量化矩阵和要求条件量化矩阵。3.2建
7、立权值矩阵要引入权值指数，首先列出大多数人认可的权值指数应具有的性质：(1)如果男方的基本条件中满足女方要求条件的个数越多，则成功率越高，权值指数越大，反之亦然；(2)如果男方满足女方的条件个数一定，在这些满足的方面（男方的基本条件等级越高，则女方的好感度越高，成功率越高，权指数越大。根据以上基本性质，定义如下权值指数：好感度：好感度是男方（女方）对女方（男方）符合自己要求条件的一个量化指标，我们定义为：，其中若不满足2个要求条件（包括只满足一个要求条件和完全不满足的情况）或年龄条件不符合（男青年至多比女青年大5岁，或女青年至多比男青年大2岁），我们定义此时的好感度=0，若只满足3个要求条件，
8、好感度为3，依次类推，若5个要求条件都满足，好感度为5。于是我们得到：=（-） (传说中的0-1整数规划)好感度增量：考虑到两个同样满足要求条件的对象，某个单项条件的突出可能会影响到最后的选择，所以我们又引入了好感度增量，即在好感度不为0的情况下，某个自身条件优于要求条件一个等级（如男青年要求外貌为B,而某女青年的外貌为A），好感度增量增加0.5。于是我们得到：=0.5（-） 最终我们确定好感度（*）=好感度+好感度增量 成功指数：成功指数=(好感度（*）)（男对女）（好感度（*）（女对男）。建立矩阵（表示号男青年配对号女青年的成功指数）。 即是：通过matlab编程求解（程序见附录1），我们
9、得到关于成功指数的权值矩阵（表示号男青年配对号女青年的成功指数）。3.3 建立模型模型一 针对问题（一）要使配对成功率尽可能的高，也就是给出一种方案，使得20对男女的配对成功指数之和最高。我们把二十个青年男女抽象化为40个结点得到一个带权二部图，其中Aj表示二十个男青年，Bj表示二十个女青年，而从男青年到女青年有一条带权边，权则由上面求得的成功指数矩阵R决定，然后，用最大二部图匹配算法（匈牙利算法）求出一个最大匹配的解，进而就可以用匈牙利算法对其求解。匈牙利算法思想：匈牙利算法的主要思想是在每次增广的时候不是找一条增广路而是同时找几条点不相交的最短增广路，形成极大增广路集，随后可以沿着这几条增
10、广路同时进行增广。可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相等的长度，并且随着算法的进行最短增广路的长度是越来越长的，更进一步分析可以证明最多只需增广ceil(sqrt(n)次就可以得到最大匹配。具体操作如下：i）从中任意取定一个初始对集。（ii）若把中的顶点皆许配，停止，即完美匹配；否则取中未被许配的一顶点，记，。（iii）若，停止，无完美匹配；否则取。（iv）若是被许配的，设，转（iii）；否则，取可增广轨，令，转（ii）。于是建立如下模型：Maxst模型二针对问题（二）求解出的匹配方案应使20对男女青年可以全部配对，且配对成功率之和最高，抽象成数学问题即求解二分图的最
11、大权完全匹配。进而就可以用KM算法对其求解。KM算法思想：KM算法：（全称是Kuhn-Munkras,是这二个人在1957年提出来的），首先为每个点设立一个顶标Li，设vi,j-为（i,j）边的权，如果可以求得一个完美匹配，使得每条匹配边vi,，其余边。此时的解就是最优的，因为匹配边的权和=，其余任意解的权和都不可能比这个大。具体做法如下：（i）选定初始可行顶点标号，确定，在中选取一个对集。（ii）若中顶点皆被许配，停止，即的权最大的完美对集；否则，取中未被许配的顶点，令， 。(iii)若，转（iv）；若，取 ， ， ，。（iv）选中一顶点，若已被许配，且，则，转（iii）；否则，取中一个可增
12、广轨，令，转（ii）。其中是中的相邻顶点集。于是建立如下模型：max模型三针对问题3中指导男女青年做出选择，使成功的可能性最大，实际中一个男青年（）对一个女青年（）的好感度（*）最高，但对的好感度（*）不一定最高，即若选择，但不一定选择。因此，两人不一定配对成功。因此要使每个个体配对成功的可能性最大，要保证配对的男女青年的成功指数足够高，而且两者好感度（*）差值的绝对值不能太大。所以我们定义了两者好感度（*）差值的绝对值为差异指数，我们规定成功指数应大于所有配对成功指数的平均值（成功指数为0的情况除外）；差异指数应小于差异指数均值的一半。于是建立如下模型：max3.4模型的求解以题中所给数据为
13、例，得到权值矩阵R，然后代入模型（一）和模型（二）编程求得结果为：问题(1)男A1A2A3A4A5A6A7A8A9A10女B18B17B16B15B2B19B3B12B1B14男A11A12A13A14A15A16A17A18A19A20女B20B10B7B8B6B5B4B11B9B13问题(2)男A1A2A3A4A5A6A7A8A9A10女B14B7B8B18B10B13B1B5B20B2男A11A12A13A14A15A16A17A18A19A20女B3B19B15B6B11B17B16B12B9B4问题(3)男A1A2A3A5A6A7A8A9A10A11女B8B2B6B17B3B7B1B
14、18B19B11男A12A13A14A16A17A18A19女B9B13B16B12B14B15B103.5模型结果的分析评价模型的优缺点优点：我们定义了好感度，并定义了好感度增量进一步增加了好感度的可靠性，定义成功指数=男女双方好感度(*)之积，如果一方好感度偏高，另一方好感度偏低，两者相差较大，成功指数也不会很大，这反映成功指数的合理性。而且在模型中我们运用了匈牙利算法和KM算法使问题更加简单化，充分体现了熟练运用数学软件在我们运用数学思想解决实际问题中的重要性。缺点：在实际生活中，每个人的基本条件和择偶条件并不只包含外貌，性格，气质，事业和财富等这五个方面，实际情况也并不能够简单量化为1
15、-5，而且每个人择偶是对基本条件的各方面侧重也不同，所以我们的模型总体来说还是略显粗糙。但可以在特定的情况下给出比较有参考型的解决方案。模型的推广交友网站是可以运用本模型的网站，根据用户自身的资料再填写对对方的要求，根据“我的条件TA对我的要求”和“我对TA的要求TA的条件”这样的关系进行条件项的匹配。这是一种比较传统的匹配。在进行交友方面的匹配时，则根据用户的兴趣爱好来进行匹配，用户可以输入：杭州 周末 登山。这一系列的匹配关键字，可以匹配到同样有这方面爱好的朋友， 另外该模型还可以用于公司雇佣员工，不仅可以求解出员工和职位的匹配方案使公司的效益最大化。而且可以用于下岗职工再就业，提供最优方
16、案使就业的人数最大化。还可以用于确定高校招收研究生的方案等等。参考文献附 录附录1：求权值矩阵的源代码：M1=5343529;3545229;4454428;3544228;2435530;3434428;5442330;4543230;5231428;2455528;4532532;5435429;4521328;5544230;5443328;2145530;3545228;5453431;3255529;5432127;M2=55342;45443;45543;35432;34441;44323;34423;54332;55533;54521;54324;45443;53443;5332
17、3;55432;55511;45443;44533;54512;43424;F1=5332528;4545225;3451526;5443227;4231325;5343526;2345430;5451331;5553126;4324427;5443428;4131526;1534426;4435525;3455329;4532328;5112525;5544328;4533125;2453229;F2=45452;34454;45343;55445;54344;45443;34553;45454;34445;44553;34543;55441;35433;45542;45444;45445;
18、55253;35453;44455;44544;for i=1:20; for j=1:20; sM(i,j)=0; sF(j,i)=0; 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); en
19、d end end endend附录2：匈牙利算法：m=5;n=5;A=0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1; M(m,n)=0; for(i=1:m)for(j=1:n)if(A(i,j)M(i,j)=1;break;end;end %求初始匹配M if(M(i,j)break;end;end %获得仅含一条边的初始匹配M while(1) for(i=1:m)x(i)=0;end %将记录X中点的标号和标记* for(i=1:n)y(i)=0;end %将记录Y中点的标号和标记* for(i=1:m)pd=1; %寻找X中 M的
20、所有非饱和点 for(j=1:n)if(M(i,j)pd=0;end;end if(pd)x(i)=-n-1;end;end %将X中 M的所有非饱和点都给以标号0 和标记*, 程序中用n+1 表示0 标号, 标号为负数时表示标记* pd=0; while(1)xi=0; for(i=1:m)if(x(i)1)k=k-1; for(j=1:k)pdd=1; for(i=1:m)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)
21、k=1;j=yy(j); %yj 不是M的饱和点 while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j); %任取M的一个非饱和点 yj, 逆向返回 if(j=n+1)break;end %找到X中标号为0 的点时结束, 获得 M-增广路P k=k+1;end for(i=1:k)if(M(P(i,1),P(i,2)M(P(i,1),P(i,2)=0; %将匹配 M 在增广路 P 中出现的边去掉 else M(P(i,1),P(i,2)=1;end;end %将增广路P中没有在匹配 M中出现的边加入到匹配M中 break;end;end;end if(pd)brea
22、k;end;end %假如X中所有有标号的点都已去掉了标记*, 算法终止 M %显示最大匹配M, 程序结束附录3：KM算法：n=4;A=4 5 5 1 2 2 4 6 4 2 3 3 5 0 2 1; 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)=
23、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:j
24、st)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)
25、=1;break;end;end;end;end MaxZjpp=0; for(i=1:n)for(j=1:n)if(M(i,j)MaxZjpp=MaxZjpp+A(i,j);end;end;end M %显示最佳匹配M MaxZjpp %显示最佳匹配M的权, 程序结束附录5相关知识及名词解释匹配： 是一个无向图，是的若干条边的集合，若中任意两条边都没有共同的结点，则称是的一个匹配。最大匹配：如果对的匹配都有,就说是的一个最大匹配。即的所有匹配中，包含边数最多的匹配即为最大匹配。完全匹配：二分图的最大匹配包含的边数不会超过,若,则称是完全匹配。特别地，若果,则称是完美匹配。正则二分图一定存在完美匹配。最佳匹配：权和最大或最小的完全匹配就叫做最佳匹配。14