基于匈牙利算法的玫瑰有约问题.doc

PAGE PAGE 3 关于玫瑰有约的数学模型 摘 要 当今社会，城市大龄青年的婚姻问题已引起了广泛关注。针对这一现象，假设某单位有20对大龄青年男女，每个人的基本条件和择偶条件都各不相同。该单位的妇联组织拟根据他们的年龄、基本条件和要求条件牵线搭桥。本文根据每个人的基本条件和要求，建立数学模型帮助妇联解决这个问题。 首先，我们定义了好感度、好感度增量和成功指数。好感度是男方（女方）对女方（男方）符合自己要求条件的一个量化指标，其中若不满足2个要求条件（包括只满足一个要求条件和完全不满足的情况）或年龄条件不符合（男青年至多比女青年大5岁，或女青年至多比男青年大2岁），我们定义此时的好感度为0；若只满足3个要求条件，好感度为3；依次类推，若5个要求条件都满足，好感度为5。考虑到两个同样满足要求条件的对象，某个单项条件的突出可能会影响到最后的选择，所以我们又引入了好感度增量，即在好感度不为0的情况下，某个自身条件优于要求条件一个等级（如男青年要求外貌为B,而某女青年的外貌为A），好感度增量为0.5。而成功指数则是考量男女双方的配对成功率，具体算法为：成功指数=(好感度+好感度增量)（男对女）ⅹ（好感度+好感度增量）（女对男）。建立矩阵（表示号男青年配对号女青年的成功指数）。用matlab处理数据得出矩阵。 针对问题（一）要使配对成功率尽可能的高，也就是给出一种方案，使得20对男女的配对成功指数最高。我们把二十个青年男女抽象化为40个结点得到一个带权二部图，其中Aj表示二十个男青年，Bj表示二十个女青年，而从男青年到女青年有一条带权边，权则由上面求得的成功指数矩阵M决定，然后，我们用最大二部图匹配算法（匈牙利算法）求出一个最大匹配的解，进而就可以用匈牙利算法对其求解。 针对问题（二）求解出的匹配方案应使20对男女青年可以全部配对（即没有一对的成功指数为0），且配对成功率之和最高，抽象成数学问题即求解二分图的最大权完全匹配解。采用KM算法。 针对问题（三）要使每个个体配对成功的可能性最大，要保证配对的男女青年的成功指数足够高，而且两者好感度（*）差值的绝对值不能太大，因此我们定义了两者好感度（*）差值的绝对值为差异指数，规定成功指数应大于所有配对成功指数的平均值（成功指数为0的情况除外）；差异指数应小于差异指数均值的一半。 1问题重述 目前，许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注。某单位现有20对大龄青年男女，每个人的基本条件都不相同，如外貌、性格、气质、事业、财富等。每项条件由高到低可以分为五个等级A、B、C、D、E。每个人的择偶条件也不尽相同。该单位的妇联组织拟根据他(她)们的年龄、基本条件和要求条件进行牵线搭桥。一般认为，男青年至多比女青年大5岁，或女青年至多比男青年大2岁 ，并且要至少满足个人要求5项条件中的2项，才有可能配对成功。要求根据现有的20对大龄青年男女的年龄、基本条件和要求条件等统计数据。建立数学模型，对以下三个问题做出解答： （1）给出可能的配对方案，使得在尽量满足个人要求的条件下，使配对成功率尽可能的高。 （2） 给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大。 （3）假设男女双方都相互了解了对方的条件和要求，让每个人出一次选择，只有当男女双方相互选中对方时才认为配对成功，每人只有一次选择机会。提出方案，告诉20对男女青年都应该如何做出选择，使得各自的成功的可能性最大？按你的选择方案最多能配对成功多少对？ 2模型假设与符号说明 1．问题假设 （1）本文只以外貌、性格、气质、事业、财富这5个因素来衡量每个个体的基本条件和择偶的要求条件，不考虑其他因素。 （2）假设不满足某方要求条件的2项，配对成功的几率为0。 （3）假设男女青年择偶不会受当时环境的影响。 2．符号说明 ——表示号男青年的基本条件 ——表示号男青年的要求条件 ——表示号男青年对号女青年的好感度 ——表示号男青年对号女青年的好感度增量 ——表示号女青年的基本条件 ——表示号女青年的要求条件 ——表示号女青年对号男青年的好感度 ——表示号女青年对号男青年的好感度增量 ——表示号男青年配对号女青年的成功指数 3 模型的建立和求解 3.1条件量化处理 对于每个人的外貌、性格、气质、事业、财富五项条件的5个等级A，B，C，D，E分别作量化处理为5，4，3，2，1。于是根据附录4可以得到男女青年的基本条件量化矩阵和要求条件量化矩阵。 3.2建立权值矩阵 要引入权值指数，首先列出大多数人认可的权值指数应具有的性质： (1)如果男方的基本条件中满足女方要求条件的个数越多，则成功率越高，权值指数越大，反之亦然； (2)如果男方满足女方的条件个数一定，在这些满足的方面（男方的基本条件等级