于同一类的成员也有好感。 这对于我们确定匹配方案以及对模型的检验具有一定的参考价值。
2.1 对问题 1 的分析
3
问题 1 要求给出可能的配对方案，使得在尽量满足个人要求的条件下，使配 对成功率尽可能的高，也即是使男女双方最终的配对的概率尽可能的大。为此， 在尽可能满足个人要求条件的同时力求 20 对青年男女配对后的满意度之和最大。 2.2 对问题 2 的分析 对于问题 2，要使 20 对男女青年同时配对成功的可能性最大。考虑将 20 对 青年男女抽象为二分图的“点”，最终的目的转化为求此二分图的最大对集。 2.3 对问题 3 的分析 对于问题 3，让每个人做出一次选择，而且每个人只有一次选择的机会。因 此能否配对成功就取决于男女双方是否都选择了对方， 关键性因素是男女双方对 对方的满意度的大小。例如，某一男青年 Bi 对某一女青年 G j 的满意度较高，而 女青年 G j 对男青年 Bi 的满意度则偏低，那么即使这位男青年 Bi 选择了女青年 G j ， 但是这位女青年不一定会选择这一男青年，反之亦然。因此，该问应该同时考虑 男女双方对对方的满意度， 只有当双方的满意度都较高且满意度相差不大时才有 可能配对成功。
关键字：择偶；0-1 规划；二部图；匈牙利算法
1
一、问题重述
目前，在许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注。 某单位现有 20 对大龄青年男女，每个人的基本条件都不相同，如外貌、性格、 气质、事业、财富等。每项条件通常可以分为五个等级 A、B、C、D、E，如外貌、
性格、气质、事业可分为很好、好、较好、一般、差；财富可分为很多、多、较多、一般、
6
14 15 16 17 18 19 20
4 3 4 5 5 4 2
4 4 5 1 5 5 4
3 5 3 1 4 3 5
5 5 2 2 4 3 3
5 3 3 5 3 1 2
25 29 28 25 28 25 29
4 4 4 5 3 4 4
5 5 5 5 5 4 4
5 4 4 2 4 4 5
4 4 4 5 5 5 4
2 4 5 3 3 5 4
下面对影响配对成功的一些重要因素进行分析： （1） 年龄是决定配对是否成功的一个重要因素 首先对男女青年的年龄作简单的统计分析， 得到男女青年的年龄频数分布 直方图（如图 3）
0.004
0.002
0
2
17
4
3
7
15
18
8
14
20
12
1
9
11
13
5
6
10
16
19
图 1. 20 位男青年聚类图
0.02 0.018 0.016 0.014 0.012 0.01 0.008 0.006 0.004 0.002
10
14
7
15
20
13
2
4
18
19
16
9
1
6
5
11
12
8
3
17
图 2. 20 位女青年聚类图 由聚类图可以清晰地看出聚类的结果，其意义在于若某一男青年 Bi （女青 年 G j ）对某一女青年 G j （男青年 Bi ）有好感，那么他（她）可能对与 G j ( Bi ) 属
二、问题分析
男女择偶问题可看作匹配问题。即每位姑娘都结实 n(n 1) 位小伙子，每个 小伙子都结实 n(n 1) 位姑娘，在尽可能满足他们择偶要求的前提下为他们牵线 配对，使得最终的满意度最高，也即是使得最终的配对成功率最大。由于每个男 女青年的基本条件和基本要求都是已知的，而且双方彼此都是知道的，因此某个 青年男女在选择最佳配偶时，会综合考虑对方的基本条件是否满足自己的要求。 择偶层次图如下
2013 高教社杯全国大学生数学建模竞赛
承
诺
书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。
表 2. 量化后的女青年的基本条件及要求条件
女 青 年 1 2 3 4 5 6 7 8 9 10 11 12 13 基 本 条 件 外貌 5 4 3 5 4 5 2 5 5 4 5 4 1 性格 3 5 4 4 2 3 3 4 5 3 4 1 5 气质 3 4 5 4 3 4 4 5 5 2 4 3 3 事业 2 5 1 3 1 3 5 1 3 4 3 1 4 财富 5 2 5 2 3 5 4 3 1 4 4 5 4 年龄 28 25 26 27 25 26 30 31 26 27 28 26 26 外貌 4 3 4 5 5 4 3 4 3 4 3 5 3 要 求 条 件 性格 5 4 5 5 4 5 4 5 4 4 4 5 5 气质 4 4 3 4 3 4 5 4 4 5 5 4 4 事业 5 5 4 4 4 4 5 5 4 5 4 4 3 财富 2 4 3 5 4 3 3 4 5 3 3 1 3
里的满意度是指男青年（女青年）对女青年（男青年）符合自己要求条件的一个
量化指标。 由于到某些男女青年的某些基本条件具有相似之处，我们分别对 20 位男青 年和 20 位女青年进行聚类， 例如男女青年均分为 6 类时的结果分别如图 1、 图 2。
2
0.016
0.014
0.012
0.01
0.008
0.006
1
目标层 O
匹配方案
准则层 C
外貌
性格
气质
事业

财富
措施层 P
……
P1
P2
P3
……
其中，每个男女青年 pi 的某一基本条件 ki 都有一个对应的标准 A 、 B 、 C 、
D 、 E ,本文中分别将其量化为 5、4、3、2、1。然后分别求出每一个男青年 Bi 与
每一女青年 G j 的满意度 smij 以及每一女青年 G j 对每一男青年 Bi 的满意度 sfij 。这
少。每个人的择偶条件也不尽相同，即对每项基本条件的要求是不同的。该单位 的妇联组织拟根据他(她)们的年龄、基本条件和要求条件进行牵线搭桥。 一般认为，大龄青年男女择偶的基本条件如下： 1．男青年至多比女青年大 5 岁，或女青年至多比男青年大 2 岁； 2．至少满足个人要求 5 项条件中的 2 项，才有可能配对成功。 要求根据每个人的情况和要求，建立数学模型解决如下问题： 1．给出可能的配对方案，使得在尽量满足个人要求的条件下，使配对成功 率尽可能的高。 2． 给出一种 20 对男女青年可同时配对的最佳方案， 使得全部配对成功的可 能性最大。男女双方都相互了解了对方的条件和要求 3．假设，让每个人出一次选择，只有当男女双方相互选中对方时才认为配 对成功， 每人只有一次选择机会。 请你告诉 20 对男女青年都应该如何做出选择， 使得自己的成功的可能性最大？按你的选择方案最多能配对成功多少对？ 4．针对你们组给出的模型，对江苏卫视《非诚勿扰》节目的编排设计是否 合理作出说明，如果不够理想提出改进方案。
5
表 1. 量化后的男青年基本条件及要求条件
男 青 年 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 基 本 条 件 外貌 5 3 4 3 2 3 5 4 5 2 4 5 4 5 5 2 3 5 3 5 性格 3 5 4 5 4 4 4 5 2 4 5 4 5 5 4 1 5 4 2 4 气质 4 4 5 4 3 3 4 4 3 5 3 3 2 4 4 4 4 5 5 3 事业 3 5 4 4 5 4 2 3 1 5 2 5 1 4 3 5 5 3 5 2 财富 5 2 4 2 5 4 3 2 4 5 5 4 3 2 3 5 2 4 5 1 年龄 29 29 28 28 30 28 30 30 28 28 32 29 28 30 28 30 28 31 29 27 外貌 5 4 4 3 3 4 3 5 5 5 5 4 5 5 5 5 4 4 5 4 要 求 条 件 性格 5 5 5 5 4 4 4 4 5 4 4 5 3 3 5 5 5 4 4 3 气质 3 4 5 4 4 3 4 3 5 5 3 4 4 3 4 5 4 5 5 4 事业 4 4 4 3 4 2 2 3 3 2 2 4 4 2 3 1 4 3 1 2 财富 2 3 3 2 1 3 3 2 3 1 4 3 3 3 2 1 3 3 2 4
4
四、符号说明
smij
sfij
Bi 或bi
男青年对女青年的满意度 女青年对男青年的满意度 第 i 号男青年 第 i 号女青年 量化后的要求条件以及基本条件的大小 第 i 个青年第 k 个基本条件的等级 男女青年的匹配度
G j 或g j
satisij
f ik
matchij
五、模型的建立与求解
5.1 模型的准备 对题给条件进行数字化处理，由于每个人的基本条件都不相同，如外貌、性 格、气质、事业、财富等。每项条件通常可以分为五个等级 A、B、C、D、E，如 外貌、性格、气质、事业可分为很好、好、较好、一般、差；财富可分为很多、 多、较多、一般、少。因此我们考虑将每个人的外貌、性格、气质、事业、财富 五项条件的 5 个等级 A、B、C、D、E 进行“评分”，“评分”原则是由高到低 依次记为 5 分、4 分、3 分、2 分、1 分。数字化后的男女青年基本条件以及要求 条件见表 1、表 2.
我们参赛选择的题号是（从 A/B/C/D 中选择一项填写） ：
A
我们的参赛报名号为（如果赛区设置报名号的话） ： 24010010 所属学校（请填写完整的全名） ： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 黔南民族师范学院 李 宏