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

《基于匈牙利算法的玫瑰有约问题》由会员分享，可在线阅读，更多相关《基于匈牙利算法的玫瑰有约问题（14页珍藏版）》请在金锄头文库上搜索。

1、1 关于玫瑰有约的数学模型摘 要当今社会， 城市大龄青年的婚姻问题已引起了广泛关注。 针对这一现象， 假设某单位有 20 对大龄青年男女，每个人的基本条件和择偶条件都各不相同。该单位的妇联组织拟根据他们的年龄、 基本条件和要求条件牵线搭桥。 本文根据每个人的基本条件和要求，建立数学模型帮助妇联解决这个问题。首先，我们定义了好感度、好感度增量和成功指数。好感度是男方（女方）对女方 （男方） 符合自己要求条件的一个量化指标， 其中若不满足 2 个要求条件（包括只满足一个要求条件和完全不满足的情况） 或年龄条件不符合 （男青年至多比女青年大 5 岁，或女青年至多比男青年大 2 岁） ，我们定义此时的

2、好感度为0；若只满足 3 个要求条件，好感度为 3；依次类推，若 5 个要求条件都满足，好感度为 5。考虑到两个同样满足要求条件的对象，某个单项条件的突出可能会影响到最后的选择， 所以我们又引入了好感度增量， 即在好感度不为 0 的情况下，某个自身条件优于要求条件一个等级（如男青年要求外貌为 B,而某女青年的外貌为 A） ， 好感度增量为 0.5 。 而成功指数则是考量男女双方的配对成功率， 具体算法为：成功指数 =(好感度 +好感度增量 ) （男对女）（好感度 +好感度增量）（女对男） 。 建立矩阵 )20*20(M （ jim , 表示 i 号男青年配对 j 号女青年的成功指数） 。用 m

3、atlab 处理数据得出矩阵 )20*20(M 。针对问题（一）要使配对成功率尽可能的高，也就是给出一种方案，使得20 对男女的配对成功指数最高。 我们把二十个青年男女抽象化为 40 个结点得到一个带权二部图，其中 Aj 表示二十个男青年， Bj 表示二十个女青年，而从男青年到女青年有一条带权边， 权则由上面求得的成功指数矩阵 M决定， 然后， 我们用最大二部图匹配算法 （匈牙利算法） 求出一个最大匹配的解， 进而就可以用匈牙利算法对其求解。针对问题 （二） 求解出的匹配方案应使 20 对男女青年可以全部配对 （即没有一对的成功指数为 0） ，且配对成功率之和最高，抽象成数学问题即求解二分图的

4、最大权完全匹配解。采用 KM算法。针对问题（三）要使每个个体配对成功的可能性最大，要保证配对的男女青年的成功指数足够高，而且两者好感度（ * ）差值的绝对值不能太大，因此我们定义了两者好感度（ * ）差值的绝对值为差异指数，规定成功指数应大于所有配对成功指数的平均值（成功指数为 0 的情况除外） ；差异指数应小于差异指数均值的一半。2 1 问题重述目前，许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注。某单位现有 20 对大龄青年男女，每个人的基本条件都不相同，如外貌、性格、气质、事业、财富等。每项条件由高到低可以分为五个等级 A、 B、 C、 D、 E。每个人的择偶条件也不尽相同。

5、该单位的妇联组织拟根据他 (她 )们的年龄、基本条件和要求条件进行牵线搭桥。 一般认为， 男青年至多比女青年大 5 岁， 或女青年至多比男青年大 2 岁 ，并且要至少满足个人要求 5 项条件中的 2 项，才有可能配对成功。要求根据现有的 20 对大龄青年男女的年龄、基本条件和要求条件等统计数据。建立数学模型，对以下三个问题做出解答：（ 1）给出可能的配对方案，使得在尽量满足个人要求的条件下，使配对成功率尽可能的高。（ 2） 给出一种 20 对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大。（ 3）假设男女双方都相互了解了对方的条件和要求，让每个人出一次选择，只有当男女双方相互选中对

6、方时才认为配对成功， 每人只有一次选择机会。 提出方案，告诉 20 对男女青年都应该如何做出选择，使得各自的成功的可能性最大？按你的选择方案最多能配对成功多少对？2 模型假设与符号说明1 问题假设（ 1）本文只以外貌、性格、气质、事业、财富这 5 个因素来衡量每个个体的基本条件和择偶的要求条件，不考虑其他因素。（ 2）假设不满足某方要求条件的 2 项，配对成功的几率为 0。（ 3）假设男女青年择偶不会受当时环境的影响。2 符号说明jiM ,1 表示 i 号男青年的基本条件jiM ,2 表示 i 号男青年的要求条件jiM ,3 表示 i 号男青年对j 号女青年的好感度jiM , 表示 i 号男青

7、年对j 号女青年的好感度增量jiF ,1 表示 i 号女青年的基本条件jiF ,2 表示 i 号女青年的要求条件3 jiF ,3 表示 i 号女青年对j 号男青年的好感度jiF , 表示 i 号女青年对j 号男青年的好感度增量)20*20(R jir , 表示 i 号男青年配对j 号女青年的成功指数3 模型的建立和求解3.1 条件量化处理对于每个人的外貌、性格、气质、事业、财富五项条件的 5 个等级 A， B，C， D， E 分别作量化处理为 5， 4， 3， 2， 1。于是根据附录 4 可以得到男女青年的基本条件量化矩阵和要求条件量化矩阵。3.2 建立权值矩阵要引入权值指数，首先列出大多数人

8、认可的权值指数应具有的性质：(1) 如果男方的基本条件中满足女方要求条件的个数越多，则成功率越高，权值指数越大，反之亦然；(2) 如果男方满足女方的条件个数一定，在这些满足的方面（男方的基本条件等级越高，则女方的好感度越高，成功率越高，权指数越大。根据以上基本性质，定义如下权值指数：好感度：好感度是男方（女方）对女方（男方）符合自己要求条件的一个量化指标，我们定义为： jiM ,3 ，其中若不满足 2 个要求条件（包括只满足一个要求条件和完全不满足的情况） 或年龄条件不符合 （男青年至多比女青年大 5 岁， 或女青年至多比男青年大 2 岁） ， 我们定义此时的好感度 jiM ,3 =0， 若只

9、满足 3 个要求条件，好感度为 3，依次类推，若 5 个要求条件都满足，好感度为 5。于是我们得到：jiM ,3 =51（ jiF ,1 - jiM ,2 ）021121,jijijijiMFMF021021,jijijijiMFMF好感度增量：考虑到两个同样满足要求条件的对象， 某个单项条件的突出可能会影响到最4 后的选择， 所以我们又引入了好感度增量， 即在好感度不为 0 的情况下， 某个自身条件优于要求条件一个等级 （如男青年要求外貌为 B, 而某女青年的外貌为 A） ，好感度增量增加 0.5 。于是我们得到：jiM , =0.5（ jiF ,1 - jiM ,2 ） 021 , jij

10、i MF最终我们确定好感度（ * ） =好感度 +好感度增量成功指数：成功指数 =(好感度（ * ） ) （男对女）（好感度（ *） ） （女对男） 。建立矩阵 )20*20(R （ jir , 表示 i 号男青年配对 j 号女青年的成功指数） 。即是： )()( ),(),(),(),()*( ijijjijiji FFMMR通过 matlab 编程求解（程序见附录 1） ，我们得到关于成功指数的权值矩阵)20*20(R （ jir , 表示 i 号男青年配对j 号女青年的成功指数） 。3.3 建立模型模型一针对问题（一）要使配对成功率尽可能的高，也就是给出一种方案，使得20 对男女的配对成

11、功指数之和最高。 我们把二十个青年男女抽象化为 40 个结点得到一个带权二部图，其中 Aj 表示二十个男青年， Bj 表示二十个女青年，而从男青年到女青年有一条带权边，权则由上面求得的成功指数矩阵 R决定，然后，用最大二部图匹配算法 （匈牙利算法） 求出一个最大匹配的解， 进而就可以用匈牙利算法对其求解。匈牙利算法思想： 匈牙利算法的主要思想是在每次增广的时候不是找一条增广路而是同时找几条点不相交的最短增广路， 形成极大增广路集， 随后可以沿着这几条增广路同时进行增广。 可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相等的长度， 并且随着算法的进行最短增广路的长度是越来越长的，

12、更进一步分析可以证明最多只需增广 ceil(sqrt(n) 次就可以得到最大匹配。具体操作如下：i ）从 G 中任意取定一个初始对集 M 。（ ii ）若 M 把 X 中的顶点皆许配，停止， M 即完美匹配；否则取 X 中未被M 许配的一顶点 u ，记 uS ， T 。（ iii ）若 TSN )( ，停止，无完美匹配；否则取 TSNy )( 。（ iv ） 若 y 是被 M 许配的， 设 Myz ， zSS ， yTT ， 转 （ iii ） ；否则，取可增广轨 ),( yuP ，令 )()( MPEPEMM ，转（ ii ） 。5 于是建立如下模型：Max jininjji xR ,1 1

13、,st）（或或或njixnixnixjinijinjji,.,2,1,10),.,2,1(10),.,2,1(10,1,1,模型二针对问题 （二） 求解出的匹配方案应使 20 对男女青年可以全部配对， 且配对成功率之和最高， 抽象成数学问题即求解二分图的最大权完全匹配。 进而就可以用 KM算法对其求解。KM算法思想： KM算法： （全称是 Kuhn-Munkras, 是这二个人在 1957 年提出来的） ，首先为每个点设立一个顶标 Li ，设 vi,j- 为（ i,j ）边的权，如果可以求得一个完美匹配，使得每条匹配边 vi, i jj L L ，其余边 i jj L L 。此时的解就是最优的

14、，因为匹配边的权和 = iL ，其余任意解的权和都不可能比这个大。具体做法如下：（ i ）选定初始可行顶点标号 l ，确定 lG ，在 lG 中选取一个对集 M 。（ ii ） 若 X 中顶点皆被 M 许配， 停止， M 即 G 的权最大的完美对集； 否则，取 lG 中未被 M 许配的顶点 u ，令 uS ， T 。(iii) 若 TSN lG )( ，转（ iv ） ；若 TSN lG )( ，取)()()(min, xywylxlTySxl ，其它),(,)(,)()(vlTvvlSvvlvl ll，ll ， ll GG 。6 （ iv ） 选 TSN lG )( 中一顶点 y ， 若 y

15、 已被 M 许配， 且 Myx ， 则 zSS ， yTT ，转（ iii ） ；否则，取 lG 中一个 M 可增广轨 ),( yuP ，令)()( MPEPEMM ，转（ ii ） 。其中 )(SN lG 是 lG 中 S的相邻顶点集。于是建立如下模型：max jininjji xR ,1 1,）（或或或njixnixnixjinijinjji,.,2,1,10),.,2,1(10),.,2,1(10,1,1,模型三针对问题 3 中指导男女青年做出选择，使成功的可能性最大，实际中一个男青年 iM （ 1 20i ） 对一个女青年 jF （ 1 20j ）的好感度（ * ）最高，但 jF对 i

16、M 的好感度（ * ）不一定最高，即若 iM 选择 jF ，但 jF 不一定选择 iM 。因此，两人不一定配对成功。 因此要使每个个体配对成功的可能性最大， 要保证配对的男女青年的成功指数足够高，而且两者好感度（ * ）差值的绝对值不能太大。所以我们定义了两者好感度 （ * ） 差值的绝对值为差异指数， 我们规定成功指数应大于所有配对成功指数的平均值（成功指数为 0 的情况除外） ；差异指数应小于差异指数均值的一半。于是建立如下模型：max jininjx ,1 17 ）（或或或njixnixnixjinijinjji,.,2,1,10),.,2,1(10),.,2,1(10,1,1,3.4 模型的求解以题中所给数据为例，得到权值矩阵 R，然后代入模型（一）和模型（二）编程求得结果为：问题 (1) 男 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 女 B18 B1