数学建模婚配问题优秀论文.pdf

2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承 诺诺 书书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子邮件 网 上咨询等 与队外的任何人 包括指导教师 研究 讨论与赛题有关的问题 我们知道 抄袭别人的成果是违反竞赛规则的 如果引用别人的成果或其他公开的 资料 包括网上查到的资料 必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出 我们郑重承诺 严格遵守竞赛规则 以保证竞赛的公正 公平性 如有违反竞赛规 则的行为 我们将受到严肃处理 我们参赛选择的题号是 从 A B C D 中选择一项填写 A 我们的参赛报名号为 如果赛区设置报名号的话 24010010 所属学校 请填写完整的全名 黔南民族师范学院 参赛队员 打印并签名 1 李 宏 2 张书俊 3 陈龙万 指导教师或指导教师组负责人 打印并签名 谢治州 日期 2014 年 9 月 4 日 赛区评阅编号 由赛区组委会评阅前进行编号 2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号 由赛区组委会评阅前进行编号 赛区评阅记录 可供赛区评阅时使用 评 阅 人 评 分 备 注 全国统一编号 由赛区组委会送交全国前编号 全国评阅编号 由全国组委会评阅前进行编号 1 择偶问题的优化设计 摘 要 本文研究的是大龄青年男女择偶的最优化问题 通过对五项基本条件的 5 个等级进行量化 分别建立衡量男女双方心仪程度的满意度矩阵 再综合考虑男 女双方满意度的大小 以它们的平均值为刻画配对成功与否的度量标准 最后确 定择偶的最优化方案 即在已知对方的基本条件和基本要求的条件下 如何做出 选择才能在自己满意的前提下 使得牵手成功的概率最高 对于问题 1 确定一个可行的方案 使得在尽量满足个人要求的条件下 使 配对成功率尽可能的高 也即是寻求匹配度最高的配对方案 我们以匹配度之和 最大为目标函数 采用 0 1 规划模型求解最佳的配对方案 对于问题 2 考虑将 20 对青年男女抽象为具有 40 个顶点的带权二部图 二 部图的顶点表示 40 个男女青年 每一男青年到每一女青年都有一条带权的边 权由匹配度矩阵决定 我们采用求解二部图的最大完美对集的匈牙利算法求最优 解 使得全部配对成功的匹配度最大 对于问题 3 以男女青年的综合满意度最高 双方满意度的差的绝对值最小 为目标建立 0 1 规划模型 求解模型 得出的结论是男女青年在择偶时 在满足 个人条件下要尽可能选择对自己满意度较高且与自己的满意度差距不大的对象 这样才能使自己成功的可能性最大 对于问题 4 基于本文的研究结果 我们认为江苏卫视 非诚勿扰 节目的 编排设计有其不合理的地方 并对其影响男女嘉宾牵手成功的因素进行分析并给 出了改进方案 关键字关键字 择偶 0 1 规划 二部图 匈牙利算法 1 一 问题重述 目前 在许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注 某单位现有 20 对大龄青年男女 每个人的基本条件都不相同 如外貌 性格 气质 事业 财富等 每项条件通常可以分为五个等级 A B C D E 如外貌 性格 气质 事业可分为很好 好 较好 一般 差 财富可分为很多 多 较多 一般 少 每个人的择偶条件也不尽相同 即对每项基本条件的要求是不同的 该单位 的妇联组织拟根据他 她 们的年龄 基本条件和要求条件进行牵线搭桥 一般认为 大龄青年男女择偶的基本条件如下 1 男青年至多比女青年大 5 岁 或女青年至多比男青年大 2 岁 2 至少满足个人要求 5 项条件中的 2 项 才有可能配对成功 要求根据每个人的情况和要求 建立数学模型解决如下问题 1 给出可能的配对方案 使得在尽量满足个人要求的条件下 使配对成功 率尽可能的高 2 给出一种 20 对男女青年可同时配对的最佳方案 使得全部配对成功的可 能性最大 男女双方都相互了解了对方的条件和要求 3 假设 让每个人出一次选择 只有当男女双方相互选中对方时才认为配 对成功 每人只有一次选择机会 请你告诉 20 对男女青年都应该如何做出选择 使得自己的成功的可能性最大 按你的选择方案最多能配对成功多少对 4 针对你们组给出的模型 对江苏卫视 非诚勿扰 节目的编排设计是否 合理作出说明 如果不够理想提出改进方案 二 问题分析 男女择偶问题可看作匹配问题 即每位姑娘都结实 1 n n 位小伙子 每个 小伙子都结实 1 n n 位姑娘 在尽可能满足他们择偶要求的前提下为他们牵线 配对 使得最终的满意度最高 也即是使得最终的配对成功率最大 由于每个男 女青年的基本条件和基本要求都是已知的 而且双方彼此都是知道的 因此某个 青年男女在选择最佳配偶时 会综合考虑对方的基本条件是否满足自己的要求 择偶层次图如下 2 目标层 O 匹配方案 准则层 C 外貌 性格 气质 事业 财富 措施层 P P1 P2 P3 其中 每个男女青年 i p的某一基本条件 i k都有一个对应的标准A B C D E 本文中分别将其量化为 5 4 3 2 1 然后分别求出每一个男青年 i B与 每一女青年 j G的满意度 ij sm以及每一女青年 j G对每一男青年 i B的满意度 ij sf 这 里的满意度是指男青年 女青年 对女青年 男青年 符合自己要求条件的一个 量化指标 由于到某些男女青年的某些基本条件具有相似之处 我们分别对 20 位男青 年和20位女青年进行聚类 例如男女青年均分为6类时的结果分别如图1 图2 3 图 1 20 位男青年聚类图 图 2 20 位女青年聚类图 由聚类图可以清晰地看出聚类的结果 其意义在于若某一男青年 i B 女青 年 j G 对某一女青年 j G 男青年 i B 有好感 那么他 她 可能对与 j G i B属 于同一类的成员也有好感 这对于我们确定匹配方案以及对模型的检验具有一定的参考价值 2 1 对问题 1 的分析 217 4 3 71518 8142012 1 91113 5 6101619 0 0 002 0 004 0 006 0 008 0 01 0 012 0 014 0 016 1014 7152013 2 4181916 9 1 6 51112 8 317 0 002 0 004 0 006 0 008 0 01 0 012 0 014 0 016 0 018 0 02 4 问题 1 要求给出可能的配对方案 使得在尽量满足个人要求的条件下 使配 对成功率尽可能的高 也即是使男女双方最终的配对的概率尽可能的大 为此 在尽可能满足个人要求条件的同时力求 20 对青年男女配对后的满意度之和最大 2 2 对问题 2 的分析 对于问题 2 要使 20 对男女青年同时配对成功的可能性最大 考虑将 20 对 青年男女抽象为二分图的 点 最终的目的转化为求此二分图的最大对集 2 3 对问题 3 的分析 对于问题 3 让每个人做出一次选择 而且每个人只有一次选择的机会 因 此能否配对成功就取决于男女双方是否都选择了对方 关键性因素是男女双方对 对方的满意度的大小 例如 某一男青年 i B对某一女青年 j G的满意度较高 而 女青年 j G对男青年 i B的满意度则偏低 那么即使这位男青年 i B选择了女青年 j G 但是这位女青年不一定会选择这一男青年 反之亦然 因此 该问应该同时考虑 男女双方对对方的满意度 只有当双方的满意度都较高且满意度相差不大时才有 可能配对成功 三 模型假设 1 本文只考虑外貌 性格 气质 事业 财富以及年龄这 6 个因素作为每个 青年男女择偶的标准 除此之外不再考虑其他因素的影响 2 假设外貌 性格 气质 事业和财富 5 个因素没有权重的差异 即每个青 年男女在择偶时没有选择偏向 3 假设男青年比女青年大 5 岁以上或者女青年比男青年大 2 岁以上时 男女 双方的匹配度为 0 4 当男青年 女青年 的基本条件低于女青年 男青年 要求条件中的 2 项 时 男女双方的匹配度为 0 5 男女双方在择偶时 不受其他人为因素的干扰或者外部的环境所影响 5 四 符号说明 ij sm 男青年对女青年的满意度 ij sf 女青年对男青年的满意度 ii Bb或 第i号男青年 jj Gg或 第i号女青年 ij satis 量化后的要求条件以及基本条件的大小 ik f 第i个青年第k个基本条件的等级 ij match 男女青年的匹配度 五 模型的建立与求解 5 1 模型的准备 对题给条件进行数字化处理 由于每个人的基本条件都不相同 如外貌 性 格 气质 事业 财富等 每项条件通常可以分为五个等级 A B C D E 如 外貌 性格 气质 事业可分为很好 好 较好 一般 差 财富可分为很多 多 较多 一般 少 因此我们考虑将每个人的外貌 性格 气质 事业 财富 五项条件的 5 个等级 A B C D E 进行 评分 评分 原则是由高到低 依次记为 5 分 4 分 3 分 2 分 1 分 数字化后的男女青年基本条件以及要求 条件见表 1 表 2 6 表 1 量化后的男青年基本条件及要求条件 男 青 年 基 本 条 件 要 求 条 件 外貌 性格 气质 事业 财富 年龄 外貌 性格 气质 事业 财富 1 5 3 4 3 5 29 5 5 3 4 2 2 3 5 4 5 2 29 4 5 4 4 3 3 4 4 5 4 4 28 4 5 5 4 3 4 3 5 4 4 2 28 3 5 4 3 2 5 2 4 3 5 5 30 3 4 4 4 1 6 3 4 3 4 4 28 4 4 3 2 3 7 5 4 4 2 3 30 3 4 4 2 3 8 4 5 4 3 2 30 5 4 3 3 2 9 5 2 3 1 4 28 5 5 5 3 3 10 2 4 5 5 5 28 5 4 5 2 1 11 4 5 3 2 5 32 5 4 3 2 4 12 5 4 3 5 4 29 4 5 4 4 3 13 4 5 2 1 3 28 5 3 4 4 3 14 5 5 4 4 2 30 5 3 3 2 3 15 5 4 4 3 3 28 5 5 4 3 2 16 2 1 4 5 5 30 5 5 5 1 1 17 3 5 4 5 2 28 4 5 4 4 3 18 5 4 5 3 4 31 4 4 5 3 3 19 3 2 5 5 5 29 5 4 5 1 2 20 5 4 3 2 1 27 4 3 4 2 4 表 2 量化后的女青年的基本条件及要求条件 女 青 年 基 本 条 件 要 求 条 件 外貌 性格 气质 事业 财富 年龄 外貌 性格 气质 事业 财富 1 5 3 3 2 5 28 4 5 4 5 2 2 4 5 4 5 2 25 3 4 4 5 4 3 3 4 5 1 5 26 4 5 3 4 3 4 5 4 4 3 2 27 5 5 4 4 5 5 4 2 3 1 3 25 5 4 3 4 4 6 5 3 4 3 5 26 4 5 4 4 3 7 2 3 4 5 4 30 3 4 5 5 3 8 5 4 5 1 3 31 4 5 4 5 4 9 5 5 5 3 1 26 3 4 4 4 5 10 4 3 2 4 4 27 4 4 5 5 3 11 5 4 4 3 4 28 3 4 5 4 3 12 4 1 3 1 5 26 5 5 4 4 1 13 1 5 3 4 4 26 3 5 4 3 3 7 14 4 4 3 5 5 25 4 5 5 4 2 15 3 4 5 5 3 29 4 5 4 4 4 16 4 5 3 2 3 28 4 5 4 4 5 17 5 1 1 2 5 25 5 5 2 5 3 18 5 5 4 4 3 28 3 5 4 5 3 19 4 5 3 3 1 25 4 4 4 5 5 20 2 4 5 3 2 29 4 4 5 4 4 下面对影响配对成功的一些重要因素进行分析 1 年龄是决定配对是否成功的一个重要因素 首先对男女青年的年龄作简单的统计分析 得到男女青年的年龄频数分布 直方图 如图 3 图 3 男女青年年龄频数直方图 由此频数分布直方图可以很直观地看出男女青年各年龄的人数 根据题目要求 男青年至多比女青年大 5 岁或者女青年至多比男青年大 2 岁 可以得出 4 个基本约束条件 25 岁女青年不可能与大于 30 岁的女青年配对成功 即不可能与 31 岁 32 岁的男青年配对成功 故编号为 2 5 14 17 19 的女青年不可能与编号 为 11 18 的男青年配对成功 26 岁女青年不可能与大于 31 岁的女青年配对成功 即不可能与 32 岁的男青 26283032 0 1 2 3 4 5 6 7 8 男 青 年 年 龄 频 数 直 方 图 2426283032 0 0 5 1 1 5 2 2 5 3 3 5 4 4 5 5 女 青 年 年 龄 频 数 直 方 图 8 年配对成功 故编号为 3 6 9 12 13 的女青年不可能与编号为 11 的男青年配对成功 27 岁的男青年不可能与大于 29 岁的女青年配对成功 即不可能与 30 岁 31 岁的女青年配对成功 故编号为 20 的男青年不可能与编号为 7 8 女青 年配对成功 28 岁的男青年不可能与大于 30 岁的女青年配对成功 即不可能与 31 岁的女 青年配对成功 故编号为 3 4 6 9 10 13 15 17 的男青年不 可能与编号为 8 的女青年配对 除此之外 配对不再受年龄的约束和限制 2 要求至少满足 5 项条件中的 2 项 才有可能配对成功 为进一步衡量男女双方配对成功率的大小 现对男女双方对彼此的满意度定 义如下 1 0 5 n k satisxf j km i kf j km i k 其中x表示基本满意度 是指某一女青年 男青年 的基本条件满足某一男 青年 女青年 的要求条件的个数 k表示基本条件或评价指标 f j k表示第j个 青年的第k个基本条件的等级 m i k表示第i个青年的第k个要求条件的等 级 i j表示当前配对的男女双方 对满意度的定义可以这样理解 当某一方的某一个基本条件满足另一方相应 的要求条件时 记为 1 分 当有k个条件满足时 记其满意度的基本分为k分 由于当一方实际条件高于对方的期望条件时 则对方对他 她 的好感就会不同 程度的增加 因此 当某一方的基本条件高出对方的要求条件时 将对其满意度 进行 加分 加分 的原则是每高出一个级别 本题分为 1 2 3 4 5 五个级别 加 0 5 分 基于以上模型 现给出求解满意度的算法 Step1 分别记量化后的男青年基本条件和男青年要求条件为1 m i k和2 m i k 女 青年基本条件和女青年要求条件为1 fj k和2 fj k Step2 令 0sm i j 用于存储满意度矩阵 0c mij 用于记录满足条件的 个数 Step3 在年龄条件限制下 如果1 2 fj kmi k 1cm i jcm i j 并逐个比较 实现 sm i j的赋值 9 Step4 如果 2cm i j 0sm i j Step5 输出 sm i j 利用 MATLAB 编写程序 见附录 1 分别求出男青年对女青年的满意度 见 表 3 和女青年对男青年的满意度 见表 4 表 3 男对女的满意度 女青年 满意度 男青年 11 12 13 14 15 16 17 17 19 20 1 4 5 4 5 3 5 4 5 4 4 5 4 5 5 0 2 4 5 5 3 4 5 4 3 5 4 5 5 5 5 3 3 5 5 5 3 5 4 5 4 5 5 5 2 5 4 2 2 5 0 4 2 3 5 3 5 2 5 4 0 5 4 5 5 0 5 3 5 4 5 4 5 5 5 3 6 4 4 5 3 4 5 3 5 4 5 3 5 4 5 5 0 7 5 5 5 4 3 5 4 3 3 5 5 5 5 3 8 3 5 3 5 2 3 5 2 5 3 5 3 4 4 0 9 4 4 5 3 5 5 4 3 5 5 4 5 5 3 10 4 5 5 3 5 3 3 5 3 2 5 5 4 2 5 11 5 0 0 0 4 3 5 0 5 5 0 3 12 4 5 3 5 5 4 5 5 5 5 6 2 13 4 5 5 5 3 5 5 5 5 5 5 6 6 5 0 14 4 5 5 3 5 4 5 3 4 3 5 4 5 5 0 15 3 5 4 2 4 5 2 5 4 3 5 4 4 5 0 16 3 3 2 4 5 2 5 3 5 3 5 3 4 0 17 4 5 5 3 4 4 5 4 5 5 5 2 5 18 4 5 4 5 3 5 0 4 4 0 5 0 0 19 3 5 3 5 2 5 4 3 5 3 3 5 4 3 5 2 5 20 4 5 2 5 4 2 5 3 3 4 5 4 2 5 表 4 女对男的满意度 男青年 满意度 女青年 1 2 3 4 5 6 7 8 9 10 1 5 4 4 5 3 3 5 0 4 4 3 5 5 2 4 5 4 5 5 3 5 3 5 3 4 4 3 5 3 5 4 5 5 3 5 4 5 3 5 4 0 4 5 5 4 3 3 5 2 5 3 2 5 0 2 0 0 4 5 4 4 5 5 4 5 4 3 5 3 3 6 10 6 4 5 3 5 5 3 3 5 2 5 3 5 0 3 5 7 4 3 5 5 2 5 4 3 5 4 3 3 5 5 8 4 3 3 5 2 2 5 0 2 5 3 2 5 4 9 4 5 5 4 5 3 5 3 4 0 0 5 10 3 5 2 5 4 5 0 4 2 5 3 5 0 3 5 11 4 0 0 3 5 0 0 4 3 0 5 5 12 5 5 5 4 5 4 5 3 5 4 3 5 3 5 6 13 6 5 6 4 5 4 4 4 0 3 5 5 5 14 4 3 5 5 3 4 3 3 3 3 5 5 15 4 3 5 4 5 3 3 2 2 5 0 2 5 4 5 16 3 5 3 5 3 5 3 2 5 0 2 5 3 0 4 17 5 4 4 3 4 5 3 4 0 4 5 5 18 5 0 4 5 3 0 2 5 4 3 5 3 5 4 5 19 3 5 3 5 3 5 2 5 3 0 3 5 3 5 0 4 5 20 3 3 5 2 5 4 3 0 0 2 5 5 事实上 单独考虑男青年对女青年的满意度或者单独考虑女青年对男青年的 满意度都是没有意义的 男女配对是否成功取决于男女双方共同的意愿 为此 定义匹配度match的概念以衡量男女青年配对的成功率 2 sm i jsf i j match i j 匹配度即是取男女双方满意度的平均值 显然 匹配度越大 则男女配对成功的概率也 就越大 反之越小 上面已经求得男青年对女青年的满意度以及女青年对男青年的匹配度 由此可以很容易求得 20 对男女青年的匹配度 表 表 5 男女青年的匹配度 女青年 匹配度 男青年 11 12 13 14 15 16 17 18 19 20 1 4 5 4 4 25 4 75 4 5 4 3 75 5 5 3 5 1 5 2 4 25 4 3 25 4 5 4 3 25 4 5 5 3 5 1 5 3 4 4 25 3 25 4 75 3 75 4 3 75 4 75 3 75 1 25 4 4 3 25 2 25 5 4 3 75 4 4 75 3 75 1 75 5 5 25 5 2 5 6 5 25 4 75 4 75 6 25 4 5 3 5 6 5 5 4 25 4 5 6 5 5 4 6 5 2 25 7 6 4 5 4 5 5 25 5 5 4 4 25 6 5 4 75 3 5 8 5 3 5 4 5 4 5 3 75 3 25 5 5 3 75 2 5 9 3 75 2 25 3 5 4 75 4 2 75 4 4 5 3 5 2 5 10 5 25 2 5 4 75 4 75 5 3 75 3 75 5 75 4 3 75 11 11 5 5 0 0 0 4 75 3 5 0 5 75 0 3 75 12 4 4 3 25 5 4 4 25 4 25 5 25 4 1 13 4 75 2 75 4 5 25 5 25 4 4 6 3 25 1 5 14 5 75 4 5 5 75 5 4 5 3 75 6 4 75 2 5 15 4 25 2 3 25 4 5 3 75 3 25 3 5 5 3 25 1 75 16 4 25 3 5 4 5 25 4 25 4 4 5 4 75 4 2 25 17 4 25 4 3 25 4 25 4 4 3 75 5 25 3 75 1 25 18 4 75 3 75 4 0 4 5 3 75 0 5 25 0 1 5 19 4 75 3 5 4 25 5 25 5 3 75 4 25 5 25 3 5 3 75 20 5 25 3 75 3 75 5 25 4 3 5 3 5 5 5 4 25 3 5 5 2 问题 1 的建模与求解 引入变量 ij x 1 ij x 或0 作为决策变量 用以判断男青年 i B是否与女青年 j G 配对 若1 ij x 则 i B与 j G配对 否则 i B与 j G不配对 则此问题即是确定一个配 对方案 使得在尽量满足个人要求的条件下 使每一对的匹配度之和最大 11 max nn ijij ij m x ij m 表示匹配度矩阵 1 1 1 1 01 n ij i n ij j ij x stx x 或 用 LINGO 软件编写程序 见附录 2 求得最终的匹配结果如表 6 并求得这 样配对的匹配度之和为 93 25 表 6 问题 1 配对结果 男 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 女 G7 G18 G12 G2 G3 G19 G15 G8 G17 G13 男 B11 B12 B13 B14 B15 B16 B17 B18 B19 B20 女 G11 G16 G1 G6 G4 G14 G5 G9 G20 G10 5 3 问题 2 的建模与求解 此问要求给出一种 20 对男女青年可同时配对的最佳方案 使得全部配对成 功的可能性最大 可将其转化为求解二分图的最大权完全匹配问题并利用匈牙利 算法求得最佳匹配 12 这个问题的模型是 G是二分图 顶点集划分为 V GXY 11 nn XbbYgg 当且仅当男青年 i b与女青年 j g配对时 ij bgE G 求G中的最大对集 若 ij ME Ge eM i e与 j e无公共端点 ij 则 称M为图G中的一个对集 下面用匈牙利算法求解最大完美对集 即寻求男女青年的最佳配对 Step1 从G中任意取定一个初始对集M Step2 若M把X中的顶点皆许配 停止 M即完美对集 否则取X中未被M许 配的一顶点u 记 Su T Step3 若 N ST 停止 无完美对集 否则取 yN ST Step4 若y是被M许配的 设yzM SSz TTy 转 step3 否则 取可增广轨 P u y 令 MME PE PM 转 step2 利用 MATLAB 软件编写程序 附件 3 求得最终的匹配结果如表 并求得这 样配对的匹配度之和为 84 表 7 问题 2 配对结果 男 B5 B9 B14 B15 B17 B20 B3 B7 B10 B12 女 G4 G2 G8 G3 G1 G6 G12 G9 G13 G10 男 B13 B18 B1 B4 B8 B6 B16 B19 B2 B11 女 G14 G11 G19 G20 G17 G7 G5 G18 G16 G15 5 4 问题 3 的建模与求解 由于男女双方都相互了解了对方的条件和要求 只有当男女双方相互选中对 方时才认为配对成功 并且每个人只有一次选择的机会 因此 只有当男女双方 对彼此的满意度都较高且双方满意度相差不大时才有可能配对成功 在第 1 问的 基础上 应该充分考虑男女双反的满意度 在此 我们用男女双方的满意度之差 来刻画双方满意度的差距 以男女双方的满意度之和最高 满意度的差距最小为 目标建立模型如下 13 11 11 1 1 max min 1 1 2 1 1 2 10 1 2 nn ijij ij nn ijij ij n ij i n ij j ij zm x ysmsf xjn stxin xi jn 或 其中 ijij sm sf分别表示男青年对女青年的满意度和女青年对男青年的满意 度 ij m表示匹配度矩阵 1 ij x 表示男青年 i B与女青年 j G配对 若0 ij x 则不 配对 基于以上模型 寻找本题中 20 对男女青年的配对用 LINGO 软件编程 见附 件 4 求得 11 组最佳配对如下表 8 表 8 最佳配对 男 B13 B15 B7 B2 B7 B16 B12 B9 B1 B4 B14 女 G18 G14 G10 G2 G9 G19 G11 G15 G1 G16 17 现根据本题的模型