玫瑰有约问题的综合模型
- 格式：pdf
- 大小：331.50 KB
- 文档页数：20
1
得自己的成功的可能性最大，并最多能配对成功多少队。如果“心动男（女）生”都有 第二志愿，那又如何选择。
二、问题分析
本文题根据初步分析,认为应该用图论的知识解决。首先我们考虑了对外貌、性格、 气质、成绩、数模等方面的权重确定，用模糊综合的方法进行了解决。 对于第一题满意度,我们要求整体的满意度最高,即不用考虑配对的成功率,主要统 计男\女在各个方面的权重,以及要求条件满足的情况， 对满足条件越多和等级越高的对 方满意度越高，并根据二分图最优匹配方式进行解决使得总体的满意度达到最大。 对于第二题配对的成功率最高,这时就要考虑相亲组合的相对满意度,也就是说不 能只考虑单个个体.考虑了年龄、数模等级等制约条件，将双方的满意度综合考虑成功 率，确定成功率计算方法后，可将问题化为与问题一类似的问题进行解决。
每一列即为该列单因素评判结果，所以对于 5 个评判因素的评判决策矩阵为：
3
0 .5 0.45 R B 0 .3 0 0
0.35 0.15 0 .4 0.15
0 0 0
0.45 0.25 0 0.35 0.25 0.3 0 .1 0 .5 0.25
0 0 0 .1 0.15 0 0 0 0 0 0 0 0 0.067
0.2 0.467 0 .4 0 .6 RG 0.267 0.6 0.333 0.6 0.133 0.267
0.333 0 0.133 0.067 0 .4
0.133
接着根据评判等级 V，我们赋予各等级的分值为 5、4、3、2、1，所以，我们得到 加权向量： 1 4 1 2 1 A 3 15 5 15 15 最后，由评判决策矩阵 R 以及加权向量 A，我们就能得到各个评判因素的综合权重 评判结果 C，男女生分别为： C B A RB 0.2900 0.2867 0.2700 0.1900 0.1700 CG A RG 0.2578 0.3067 0.2756 0.2844 0.2177 5.2.权值矩阵的建立 要引入权值指数，首先列出大多数人认可的权值指数应具有的性质： (1)如果男方的基本条件中满足女方要求条件的个数越多，则成功率越高，权值指 数越大，反之亦然； (2)如果男方满足女方的条件个数一定，在这些满足的方面（男方的基本条件等级 越高，则女方的好感度越高，成功率越高，权指数越大。 根据以上基本性质，定义如下权值指数： 好感度： 满意度是男方（女方）对女方（男方）符合自己要求条件的一个量化指标，我们定 M 3i , j 义为： ，其中若不满足 2 个要求条件（包括只满足一个要求条件和完全不满足的 情况） 或年龄条件不符合 （男青年至多比女青年大 5 岁， 或女青年至多比男青年大 2 岁） ， M 3i , j 我们定义此时的好感度 =0，若只满足 3 个要求条件，好感度为 3，依次类推，若 5 个要求条件都满足，好感度为 5。于是我们得到： M 3i , j = （ F1i , j - M 2i , j ）
U = {外貌，性格，气质，成绩，数模获奖} 所有的评判等级 v 为： v = {优秀，良好，中等，及格，不及格} 根据对 35 名同学的统计，能得到以下表格： 表 1：男女生的单因素评判结果表
男生对女生 A B C D E 女生对男生 A B C D E 外貌 0.5 0.35 0.15 0 0 外貌 0.2 0.467 0.333 0 0 性格 0.45 0.4 0.15 0 0 性格 0.6 0.4 0 0ቤተ መጻሕፍቲ ባይዱ0 气质 0.3 0.45 0.25 0 0 气质 0.267 0.6 0.133 0 0 成绩 0 0.35 0.25 0.3 0.1 成绩 0.333 0.6 0.067 0 0 数模获奖 0 0.1 0.5 0.25 0.15 数模获奖 0.133 0.267 0.4 0.133 0.067
图 1：二分图 5.3.2 匈牙利算法求最佳匹配 对于上述的匹配问题，我们可以用匈牙利算法来求解最佳结果。 匈牙利算法思想： 匈牙利算法的主要思想是在每次增广的时候不是找一条增广路而 是同时找几条点不相交的最短增广路，形成极大增广路集，随后可以沿着这几条增广路 同时进行增广。 可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相 等的长度，并且随着算法的进行最短增广路的长度是越来越长的，更进一步分析可以证 明最多只需增广 ceil(sqrt(n))次就可以得到最大匹配。具体操作如下： i）从 G 中任意取定一个初始对集 M 。 （ii）若 M 把 X 中的顶点皆许配，停止， M 即完美匹配；否则取 X 中未被 M 许 配的一顶点 u ，记 S {u} ， T 。 （iii）若 N ( S ) T ，停止，无完美匹配；否则取 y N ( S ) T 。 （iv）若 y 是被 M 许配的，设 yz M ， S S {z} ，T T { y} ，转（iii） ；否则， 取可增广轨 P (u, y ) ，令 M ( M E ( P)) ( E ( P) M ) ，转（ii） 。 考虑了年龄因素， 将男生年龄大于女生 4 岁后或女生年龄大于男生 3 岁的满意度定 位 0。
M i , j =0.2（ F1i , j - M 2 i , j ） F1i , j M 2 i , j 0
最终我们确定满意度（*）=好感度+好感度增量 5.3 满意度的最佳匹配模型 5.3.1 二分图模型的建立 二分图是图论中的一种特殊模型。 设 G (V , E ) 是一个无向图，如果顶点 V 可分割 为两个互不相交的子集 ( A, B ) ， 并且图中的每条边 (i, j ) 所关联的两个顶点 i 和 j 分别属于 这两个不同的顶点集( i A , j B )，则图 G 为一个二分图。如下所示：
四、符号说明
U v A M 1i , j M 2i, j M 3i , j M i , j F1i , j F 2i, j F 3i , j Fi , j R( 20*20 )
所有评判因素组成的集合 所有评语等级所组成的集合。 权数分配 表示 i 号男青年的基本条件 表示 i 号男青年的要求条件 表示 i 号男青年对 j 号女青年的好感度 表示 i 号男青年对 j 号女青年的好感度增量 表示 i 号女青年的基本条件 表示 i 号女青年的要求条件 表示 i 号女青年对 j 号男青年的好感度 表示 i 号女青年对 j 号男青年的好感度增量 ri , j 表示 i 号男青年配对 j 号女青年的成功 指数
三、模型假设
为了模型建立的方便,我们提出了以下几条基本假设: 1、假设每个同学都按照自己的要求条件择偶，不存在一见钟情等意外情况。 2、假设每个同学的条件衡量都是客观的，不会随意改变. 3、假设大家的择偶标准在不存在其它的因素，如家庭经济条件等 4、假设大家的选择都是理性的，符合成功率的衡量标准 5、假设大家的择偶标准都趋于一个平均水平，不存在特殊情况
玫瑰有约问题的综合模型 摘要
随着社会发展，青年男女的价值观各不相同，大学生的择偶标准趋于多样化，大学 生恋爱比例情况堪忧。本文主要选取了外貌、性格、气质、学习成绩、数模获奖、年龄 等几个普遍的影响因素来考虑男女生的恋爱择偶模型。 男女生的恋爱模型可以以图论为 基础背景，我们主要运用了二分图法来进行解决问题。 针对问题一，直接认为确定权重有失准确，而且男女生对这 5 个方面的需求不完全 相同，我们用模糊综合的方法通过统计男女生对 5 个方面的要求等级来确定决策矩阵， 并将 A、B、C、D、E 这 5 个等级赋值为 5，4，3，2，1；分别得出了男女生对异性在外 貌、性格、气质、学习成绩、数模获奖这五因素各自看重程度的权重。之后根据被评价 人的基本条件和择偶者要求条件的相对差距，其中不符合择偶者要求的单因素条件以 0 处理，符合择偶者要求标准的单因素条件记为 1，符合且高于择偶者标准情况下，则每 高一个等级单项分值增加 0.2，另外，考虑到年龄因素，男生大于女生 4 岁或女生大于 男生 3 岁的数据记为 0，以此为基础来计算男女生在对方心中的满意度。 考虑数据的复杂度，我们对满意度采用匈牙利算法，每次增广的时候同时找几条点 不相交的最短增广路，形成极大增广路集，可以证明最多只需增广有限次就可以得到最 大匹配，即得到使整体满意度最高的配对方式。 针对问题二，我们要考虑双方的相互满意度，根据权值指数的定义，以满意度之积 来定义成功率；之后将问题化为与问题一类似的问题，用匈牙利算法进行处理，得到使 他们整体成功率最高的配对方式。 最终我们从匹配结果中可以得出， 男生 B9、 B12、 B15、 B16、B19 这五位同学未匹配成功。 对于心动男生和心动女生的选择，要考虑每个个体自身的条件和自己的要求，我们 考虑了四个备选因素：最符合自己条件得女生、何自身条件相近的女生以及刚好达到自 己要求，运用层次法构造每个个体的判断举证的判断矩阵，进行综合分析判断出最适合 自己的女生做为第一志愿同；理可得到第二志愿。可以对每个个体进行有个性的志愿选 择指导，以使得自己配对成功率最大。至于最多成功配对的队数我们考虑用二分图的最 大匹配模型得到解决 关键词：模糊综合评价 匈牙利算法 层次分析法 配对问题 二分图
五、模型的建立与求解
2
5.1 基于模糊综合的权重确定 5.1.1 单层次模糊综合评判模型 给定两个有限论域 U=｛u1，u2，…，um｝ (1) V=｛v1，v2，…，vn｝ (2) (1)式中，U 代表所有的评判因素所组成的集合；(2)式中，V 代表所有的评语等级 所组成的集合。 如果着眼于第 i(i=1， 2， …， m)个评判因素 ui， 其单因素评判结果为 Ri=[ri1， ri2， …， rin]，则 m 个评判因素的评判决策矩阵为 R1 r11 r12 r1 n R r r r2 n R 2 21 22 （3） Rm rm1 rm 2 rmn 就是 U 到 V 上的一个模糊关系。 如果对各评判因数的权数分配为： A a1,a2 , , a m （显然， A 是论域 U 上的一， 个模糊子集，且 0 ai 1, ai 1 ）则应用模糊变换的合成运算，可以得到论域 V 上的
得自己的成功的可能性最大，并最多能配对成功多少队。如果“心动男（女）生”都有 第二志愿，那又如何选择。
二、问题分析
本文题根据初步分析,认为应该用图论的知识解决。首先我们考虑了对外貌、性格、 气质、成绩、数模等方面的权重确定，用模糊综合的方法进行了解决。 对于第一题满意度,我们要求整体的满意度最高,即不用考虑配对的成功率,主要统 计男\女在各个方面的权重,以及要求条件满足的情况， 对满足条件越多和等级越高的对 方满意度越高，并根据二分图最优匹配方式进行解决使得总体的满意度达到最大。 对于第二题配对的成功率最高,这时就要考虑相亲组合的相对满意度,也就是说不 能只考虑单个个体.考虑了年龄、数模等级等制约条件，将双方的满意度综合考虑成功 率，确定成功率计算方法后，可将问题化为与问题一类似的问题进行解决。
每一列即为该列单因素评判结果，所以对于 5 个评判因素的评判决策矩阵为：
3
0 .5 0.45 R B 0 .3 0 0
0.35 0.15 0 .4 0.15
0 0 0
0.45 0.25 0 0.35 0.25 0.3 0 .1 0 .5 0.25
0 0 0 .1 0.15 0 0 0 0 0 0 0 0 0.067
0.2 0.467 0 .4 0 .6 RG 0.267 0.6 0.333 0.6 0.133 0.267
0.333 0 0.133 0.067 0 .4
0.133
接着根据评判等级 V，我们赋予各等级的分值为 5、4、3、2、1，所以，我们得到 加权向量： 1 4 1 2 1 A 3 15 5 15 15 最后，由评判决策矩阵 R 以及加权向量 A，我们就能得到各个评判因素的综合权重 评判结果 C，男女生分别为： C B A RB 0.2900 0.2867 0.2700 0.1900 0.1700 CG A RG 0.2578 0.3067 0.2756 0.2844 0.2177 5.2.权值矩阵的建立 要引入权值指数，首先列出大多数人认可的权值指数应具有的性质： (1)如果男方的基本条件中满足女方要求条件的个数越多，则成功率越高，权值指 数越大，反之亦然； (2)如果男方满足女方的条件个数一定，在这些满足的方面（男方的基本条件等级 越高，则女方的好感度越高，成功率越高，权指数越大。 根据以上基本性质，定义如下权值指数： 好感度： 满意度是男方（女方）对女方（男方）符合自己要求条件的一个量化指标，我们定 M 3i , j 义为： ，其中若不满足 2 个要求条件（包括只满足一个要求条件和完全不满足的 情况） 或年龄条件不符合 （男青年至多比女青年大 5 岁， 或女青年至多比男青年大 2 岁） ， M 3i , j 我们定义此时的好感度 =0，若只满足 3 个要求条件，好感度为 3，依次类推，若 5 个要求条件都满足，好感度为 5。于是我们得到： M 3i , j = （ F1i , j - M 2i , j ）
U = {外貌，性格，气质，成绩，数模获奖} 所有的评判等级 v 为： v = {优秀，良好，中等，及格，不及格} 根据对 35 名同学的统计，能得到以下表格： 表 1：男女生的单因素评判结果表
男生对女生 A B C D E 女生对男生 A B C D E 外貌 0.5 0.35 0.15 0 0 外貌 0.2 0.467 0.333 0 0 性格 0.45 0.4 0.15 0 0 性格 0.6 0.4 0 0ቤተ መጻሕፍቲ ባይዱ0 气质 0.3 0.45 0.25 0 0 气质 0.267 0.6 0.133 0 0 成绩 0 0.35 0.25 0.3 0.1 成绩 0.333 0.6 0.067 0 0 数模获奖 0 0.1 0.5 0.25 0.15 数模获奖 0.133 0.267 0.4 0.133 0.067
图 1：二分图 5.3.2 匈牙利算法求最佳匹配 对于上述的匹配问题，我们可以用匈牙利算法来求解最佳结果。 匈牙利算法思想： 匈牙利算法的主要思想是在每次增广的时候不是找一条增广路而 是同时找几条点不相交的最短增广路，形成极大增广路集，随后可以沿着这几条增广路 同时进行增广。 可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相 等的长度，并且随着算法的进行最短增广路的长度是越来越长的，更进一步分析可以证 明最多只需增广 ceil(sqrt(n))次就可以得到最大匹配。具体操作如下： i）从 G 中任意取定一个初始对集 M 。 （ii）若 M 把 X 中的顶点皆许配，停止， M 即完美匹配；否则取 X 中未被 M 许 配的一顶点 u ，记 S {u} ， T 。 （iii）若 N ( S ) T ，停止，无完美匹配；否则取 y N ( S ) T 。 （iv）若 y 是被 M 许配的，设 yz M ， S S {z} ，T T { y} ，转（iii） ；否则， 取可增广轨 P (u, y ) ，令 M ( M E ( P)) ( E ( P) M ) ，转（ii） 。 考虑了年龄因素， 将男生年龄大于女生 4 岁后或女生年龄大于男生 3 岁的满意度定 位 0。
M i , j =0.2（ F1i , j - M 2 i , j ） F1i , j M 2 i , j 0
最终我们确定满意度（*）=好感度+好感度增量 5.3 满意度的最佳匹配模型 5.3.1 二分图模型的建立 二分图是图论中的一种特殊模型。 设 G (V , E ) 是一个无向图，如果顶点 V 可分割 为两个互不相交的子集 ( A, B ) ， 并且图中的每条边 (i, j ) 所关联的两个顶点 i 和 j 分别属于 这两个不同的顶点集( i A , j B )，则图 G 为一个二分图。如下所示：
四、符号说明
U v A M 1i , j M 2i, j M 3i , j M i , j F1i , j F 2i, j F 3i , j Fi , j R( 20*20 )
所有评判因素组成的集合 所有评语等级所组成的集合。 权数分配 表示 i 号男青年的基本条件 表示 i 号男青年的要求条件 表示 i 号男青年对 j 号女青年的好感度 表示 i 号男青年对 j 号女青年的好感度增量 表示 i 号女青年的基本条件 表示 i 号女青年的要求条件 表示 i 号女青年对 j 号男青年的好感度 表示 i 号女青年对 j 号男青年的好感度增量 ri , j 表示 i 号男青年配对 j 号女青年的成功 指数
三、模型假设
为了模型建立的方便,我们提出了以下几条基本假设: 1、假设每个同学都按照自己的要求条件择偶，不存在一见钟情等意外情况。 2、假设每个同学的条件衡量都是客观的，不会随意改变. 3、假设大家的择偶标准在不存在其它的因素，如家庭经济条件等 4、假设大家的选择都是理性的，符合成功率的衡量标准 5、假设大家的择偶标准都趋于一个平均水平，不存在特殊情况
玫瑰有约问题的综合模型 摘要
随着社会发展，青年男女的价值观各不相同，大学生的择偶标准趋于多样化，大学 生恋爱比例情况堪忧。本文主要选取了外貌、性格、气质、学习成绩、数模获奖、年龄 等几个普遍的影响因素来考虑男女生的恋爱择偶模型。 男女生的恋爱模型可以以图论为 基础背景，我们主要运用了二分图法来进行解决问题。 针对问题一，直接认为确定权重有失准确，而且男女生对这 5 个方面的需求不完全 相同，我们用模糊综合的方法通过统计男女生对 5 个方面的要求等级来确定决策矩阵， 并将 A、B、C、D、E 这 5 个等级赋值为 5，4，3，2，1；分别得出了男女生对异性在外 貌、性格、气质、学习成绩、数模获奖这五因素各自看重程度的权重。之后根据被评价 人的基本条件和择偶者要求条件的相对差距，其中不符合择偶者要求的单因素条件以 0 处理，符合择偶者要求标准的单因素条件记为 1，符合且高于择偶者标准情况下，则每 高一个等级单项分值增加 0.2，另外，考虑到年龄因素，男生大于女生 4 岁或女生大于 男生 3 岁的数据记为 0，以此为基础来计算男女生在对方心中的满意度。 考虑数据的复杂度，我们对满意度采用匈牙利算法，每次增广的时候同时找几条点 不相交的最短增广路，形成极大增广路集，可以证明最多只需增广有限次就可以得到最 大匹配，即得到使整体满意度最高的配对方式。 针对问题二，我们要考虑双方的相互满意度，根据权值指数的定义，以满意度之积 来定义成功率；之后将问题化为与问题一类似的问题，用匈牙利算法进行处理，得到使 他们整体成功率最高的配对方式。 最终我们从匹配结果中可以得出， 男生 B9、 B12、 B15、 B16、B19 这五位同学未匹配成功。 对于心动男生和心动女生的选择，要考虑每个个体自身的条件和自己的要求，我们 考虑了四个备选因素：最符合自己条件得女生、何自身条件相近的女生以及刚好达到自 己要求，运用层次法构造每个个体的判断举证的判断矩阵，进行综合分析判断出最适合 自己的女生做为第一志愿同；理可得到第二志愿。可以对每个个体进行有个性的志愿选 择指导，以使得自己配对成功率最大。至于最多成功配对的队数我们考虑用二分图的最 大匹配模型得到解决 关键词：模糊综合评价 匈牙利算法 层次分析法 配对问题 二分图
五、模型的建立与求解
2
5.1 基于模糊综合的权重确定 5.1.1 单层次模糊综合评判模型 给定两个有限论域 U=｛u1，u2，…，um｝ (1) V=｛v1，v2，…，vn｝ (2) (1)式中，U 代表所有的评判因素所组成的集合；(2)式中，V 代表所有的评语等级 所组成的集合。 如果着眼于第 i(i=1， 2， …， m)个评判因素 ui， 其单因素评判结果为 Ri=[ri1， ri2， …， rin]，则 m 个评判因素的评判决策矩阵为 R1 r11 r12 r1 n R r r r2 n R 2 21 22 （3） Rm rm1 rm 2 rmn 就是 U 到 V 上的一个模糊关系。 如果对各评判因数的权数分配为： A a1,a2 , , a m （显然， A 是论域 U 上的一， 个模糊子集，且 0 ai 1, ai 1 ）则应用模糊变换的合成运算，可以得到论域 V 上的
