关于玫瑰有约的数学模型.docx
- 文档编号:13923024
- 上传时间:2023-06-19
- 格式:DOCX
- 页数:24
- 大小:81.11KB
关于玫瑰有约的数学模型.docx
《关于玫瑰有约的数学模型.docx》由会员分享,可在线阅读,更多相关《关于玫瑰有约的数学模型.docx(24页珍藏版)》请在冰点文库上搜索。
关于玫瑰有约的数学模型
关于玫瑰有约的数学模型
李威
(湖南科技学院数学与计算科学系湖南永州425100)
摘要:
现在城市大龄青年的婚姻问题收起了社会的广泛关注,针对这一社会现象,我们假设某单位有20对大龄青年男女,每个人的基本条件都不相同,并且每个人的择偶条件也不相同。
该单位的妇联组织拟根据他们的年龄,基本条件和要求条件牵线搭桥。
本文根据每个人的情况和要求,建立数学模型帮助妇联解决3个问题。
关键词:
数学模型;满意度;匈牙利算法;KM算法
Themathematicalmodelaboutmakinganappointmentforlife
Liwei
(DepartmentofMathematicsandComputationalScienceHunanUniversityofScienceandEngineering,Yongzhou,425100,Hunan)
Abstract:
Nowadays,theproblemoftheyoung’smarriagehasrousedmoreandmorepublic’sconcern.Accordingtothisphenomenon,weassumethattherearetwentypairsofagedpeopleinacompany,allofwhichhavedifferentbasicconditionandtheirdemanding。
TheWomen'sFederationofthiscompanywantstowire-pullforthemonthebasisoftheirage,basicconditionanddemand.Thispaper,accordingtoeveryone’sconditionanddemands,helpstheWomen'sFederationsolvingthisproblem.
Keywords:
mathematicalmodel;themeasurementofsatisfaction;Hungaryalgorithm;
KMalgorithm;
1.引言
现在在城市大龄青年的婚姻问题引起了社会的广泛关注,针对这一现象,我们给出20对青年男女的基本条件和择偶条件的抽样是真实可靠的。
首先,我们将所给的两个表格按年龄升序重新进行排列,分别编号为1,2,3……20。
并且将外貌、性格、气质、事业、财富五个方面的五个等级A、B、C、D、E分别赋值为5、4、3、2、1,这样我们就得到了男女青年的基本条件和要求条件的四个矩阵
;其次,我们定义了“满意度”的概念,利用图论(二部图)的方法解决这个问题。
在模型中,根据男青年的基本条件和女青年的要求条件构造度量矩阵(权值矩阵)A,男1号的基本条件和女1号的要求条件,比如在外貌方面,男1号满足女1号的要求则赋值为5-3+1,在事业方面,男1号不满足女1号的要求,则赋值为0,按照这个方法,如果满足条件则按公式(男青年基本条件值-女青年相应的要求条件+1)赋值,反之赋值为0,这样可以得到外貌,性格,气质,事业,财富五个方面的数值,并将这些数值相加得到
,最终得到权值矩阵T=(
)20
20,同理可得,女青年的基本条件和男青年的要求条件所构成的权值矩阵S=(
)20
20,那么男女青年配对的总权值矩阵(即为满意度矩阵)为R1=T+S,(因为
表示男i号的基本条件对j号的要求条件,
表示女j号的基本条件对男i号的要求条件,那么用
+
表示男i号对女j号的总权数即为他们之间的满意度):
再次,我们根据年龄的限制在矩阵R1中将不满足条件的赋0,得到矩阵R,利用匈牙利算法可得到问题
(1)的结果。
再在矩阵R中将大于2的数字赋1反之赋0,再利用KM算法可得问题
(2)的结果。
由于以上的模型在构造权值矩阵R时,男青年基本条件不满足女青年要求条件时赋值为0,实际上还存在男女青年的失望度,故在模型改进中针对失望度将模型中赋值为0的另外赋值为(女青年要求条件值–男青年相应的基本条件值)即考虑到可能单向面的满意度较大而另一方面的失望度也较大时同样不能配对成功,且在把模型无向化时是采用把每个结点分成两个结点的方法即把有向的平行边分成各自带自己权的无向边,同时在此模型中将初等模型中的五个等级A、B、C、D、E量化为9、7、5、3、1(由于模型中的赋值尺度比较粗糙),其余的步骤与模型相同,从而得到了模型改进。
2.问题的提出
目前,在许多城市大龄青年的婚姻问题已引起了妇联和社会团体组织的关注。
某单位现在有20对大龄青年男女,每个人的基本条件都不相同,如外貌、性格、气质、事业、财富等。
每项条件通常可以分为五个等级A、B、C、D、E,如外貌、性格、气质、事业可分为很好、好、较好、一般、差;财富可以分为很多、多、较多、一般、少。
每个人的择偶条件也不尽相同,即对每项基本条件的要求是不同的。
该单位的妇联组织拟根据他(她)们的年龄、基本条件和要求条件进行牵线搭桥。
下面给出20对大龄青年男女的年龄、基本条件和要求条件(如下表)。
一般认为,男青年至多比女青年的年龄大5岁,或女青年的年龄比男青
年的大2岁,并且要至少满足个人要求5项条件中的2项,才有可能配对成功。
本文根据每个人的情况要求,建立数学模型帮助妇联解决如下问题:
(1)给出可能的配对方案,使得在尽量满足个人要求的条件下,使得配对成功率尽可能的高。
(2)给出一种20对男女青年可同时配对的最佳方案,使得全部配对成功的可能性最大。
(3)假设男女双方都相互了解了对方的条件和要求,让每一个人出一次选择,只有当男女双方相互选中对方时才认为配对成功,每一个人只有一次选择机会。
怎样告诉20对男女青年都应该如何做出选择,使得自己的成功的可能性最大?
选择的方案最多能配对成功多少对?
男
青
年
基本条件
要求条件
外
貌
性格
气质
事业
财富
年
龄
外
貌
性格
气质
事业
财富
A
C
B
C
A
29
A
A
C
B
D
C
A
B
A
D
29
B
A
B
B
C
B
B
A
B
B
28
B
A
A
B
C
C
A
B
B
D
28
C
A
B
C
D
D
B
C
A
A
30
C
B
B
B
E
C
B
C
B
B
28
B
B
C
D
C
A
B
B
D
C
30
C
B
B
D
C
B
A
B
C
D
30
A
B
C
C
D
A
D
C
E
B
28
A
A
A
C
C
D
B
A
A
A
28
A
B
A
D
E
B
A
C
D
A
32
A
B
C
D
B
A
B
C
A
B
29
B
A
B
B
C
B
A
D
E
C
28
A
C
B
B
C
A
A
B
B
D
30
A
C
C
D
C
A
B
B
C
C
28
A
A
B
C
D
D
E
B
A
A
30
A
A
A
E
E
C
A
B
A
D
28
A
A
A
E
E
A
B
A
C
B
31
B
B
A
C
C
C
D
A
A
A
29
A
B
A
E
D
A
B
C
D
E
27
B
C
B
D
B
女
青
年
基本条件
要求条件
外貌
性格
气质
事业
财富
年龄
外貌
性格
气质
事业
财富
A
C
C
D
A
28
B
A
B
A
D
B
A
B
A
D
25
C
B
B
A
B
C
B
A
E
A
26
B
A
C
B
C
A
B
B
C
D
27
A
A
B
B
A
B
D
C
E
C
25
A
B
C
B
B
A
C
B
C
A
26
B
A
B
B
C
D
C
B
A
B
30
C
B
A
A
C
A
B
A
E
C
31
B
A
B
A
B
A
A
A
C
E
26
C
B
B
B
A
B
C
D
B
B
27
B
B
A
A
C
A
B
B
C
B
28
C
B
A
B
C
B
E
C
E
A
26
A
A
B
B
E
E
A
C
B
B
26
C
A
B
C
C
B
B
C
A
A
25
B
A
A
B
D
C
B
A
A
C
29
B
A
B
B
B
B
A
C
D
C
28
B
A
B
B
A
A
E
E
D
A
25
A
A
D
A
C
A
A
B
B
C
28
C
A
B
A
C
B
A
C
C
E
25
B
B
B
A
A
D
B
A
C
D
29
B
B
A
B
B
注:
表中的要求条件一般是指不低于所给的条件。
为了方便后面的计算,我们按年龄升序重新对上述两个表格进行排列并且编号:
男
青
年
基本条件
要求条件
外貌
性格
气质
事业
财富
年龄
外貌
性格
气质
事业
财富
1
A
B
C
D
E
27
B
C
B
D
B
2
B
B
A
B
B
28
B
A
A
B
C
3
C
A
B
B
D
28
C
A
B
C
D
4
C
B
C
B
B
28
B
B
C
D
C
5
A
D
C
E
B
28
A
A
A
C
C
6
D
B
A
A
A
28
A
B
A
D
E
7
B
A
D
E
C
28
A
C
B
B
C
8
A
B
B
C
C
28
A
A
B
C
D
9
C
A
B
A
D
28
B
A
B
B
C
10
A
C
B
C
A
29
A
A
C
B
D
11
C
A
B
A
D
29
B
A
B
B
C
12
A
B
C
A
B
29
B
A
B
B
C
13
C
D
A
A
A
29
A
B
A
E
D
14
D
B
C
A
A
30
C
B
B
B
E
15
A
B
B
D
C
30
C
B
B
D
C
16
B
A
B
C
D
30
A
B
C
C
D
17
A
A
B
B
D
30
A
C
C
D
C
18
D
E
B
A
A
30
A
A
A
E
E
19
A
B
A
C
B
31
B
B
A
C
C
20
B
A
C
D
A
32
A
B
C
D
B
女
青
年
基本条件
要求条件
外貌
性格
气质
事业
财富
年龄
外貌
性格
气质
事业
财富
1
B
A
B
A
D
25
C
B
B
A
B
2
B
D
C
E
C
25
A
B
C
A
B
3
B
B
C
A
A
25
B
A
A
B
D
4
A
E
E
D
A
25
A
A
D
A
C
5
B
A
C
C
E
25
B
B
B
A
A
6
C
B
A
E
A
26
B
A
C
B
C
7
A
C
B
C
A
26
B
A
B
B
C
8
A
A
A
C
E
26
C
B
B
B
A
9
B
E
C
E
A
26
A
A
B
B
E
10
E
A
C
B
B
26
C
A
B
C
C
11
A
B
B
C
D
27
A
A
B
B
A
12
B
C
D
B
B
27
B
B
A
A
C
13
A
C
C
D
A
28
B
A
B
A
D
14
A
B
B
C
B
28
C
B
A
B
C
15
B
A
C
D
C
28
B
A
B
B
A
16
A
A
B
B
C
28
C
A
B
A
C
17
C
B
A
A
C
29
B
A
B
B
B
18
D
B
A
C
D
29
B
B
A
B
B
19
D
C
B
A
B
30
C
B
A
A
C
20
A
B
A
E
C
31
B
A
B
A
B
注:
表格中的要求条件一般是指不低于所给条件
3.问题分析
该问题是现实生活中的实际问题,主要就是确定合理配对方案,使得在尽量满足个人要求条件下,使配对成功率尽可能的高。
由于每个人的基本条件和要求条件都是给定的,双方彼此是知道的,而且是相互之间有很大的差异,如果完全按照要求条件组合配对成功。
任意一对男女的配对可以看成一个随机事件,按某一概率可能配对成功,或不成功。
在这里双方的满意度主要反映出一个人对另一个人的客观和主观看法,因此,满意度的定义成为解决问题的一个关键。
所谓的“成功率”,就是男女双方最终配对的概率。
实际上,可以用他们相互之间的满意度来间接刻画。
相互的满意度越高,双方配对的成功率就越大。
对于问题
(1),要使配对成功率尽可能的高明,也就是给出一种方案,使得20对男女的配对后的满意度之和最高。
对于问题
(2),要使20对男女青年同时配对,使得全部同时成功的可能性(概率)最大。
对于问题(3),因为每人个只能选择一次,能不配对成功取决于双方是不是选中对方,即要看双方彼此的满意度如何。
实际中,假如一个男青年
(
)对一个女青年
(
)的满意度最高,但
对
的满意度不一定最高,即若
选择
,但
不一定选择
。
因此,
与
不一定配成对,反之亦然。
现在的问题是谁选谁,使配对成功的可能性最大呢?
这个问题实际上是男女双方在彼此基本了解的情况下,在保证自己一定满意的条件下做出自己的选择,也需要猜测对方会做出怎样的选择。
因此,这个问题可能转化为男女双方的对策问题,即转化为求男女双方的非零和对策的纳什平衡点的问题。
4.模型的假设与符号说明
4.1模型的假设
(1)题目所给出的男女青年的评价是客观真实的;
(2)每个人在选择双方的时候是理智的;
(3)男女青年不会受当时环境的影响。
4.2符号说明
K=1,2,3,4,5.分别表示外貌、性格、气质、事业、财富这5个条件;
(i=1,2……20)表示年龄升序排列后男青年编号;
(j=1,2……20)表示年龄升序排列后女青年编号;
(i=1,2……20,k=1,2,3,4,5)表示男青年在k方面的基本条件;
(i=1,2……20,k=1,2,3,4,5)表示男青年在k方面的要求;
(j=1,2……20,k=1,2,3,4,5)表示女青年在k方面的基本条件;
(j=1,2……20,k=1,2,3,4,5)表示女青年在k方面的要求;
表示男青年i对女青年j在k方面的满意度;
表示女青年j对男青年i在k方面的满意度;
表示男青年i与女青年j在k方面的满意度之和.
5.模型的建立和求解
5.1条件量化处理
对于每个人的外貌、性格、气质、事业、财富五项条件的5个等级A,B,C,D,E分别作量化处理为5,4,3,2,1。
于是根据上表可以得到男女青年的基本条件量化矩阵和要求条件量化矩阵(或称权值矩阵)以及满意度分量分别记为:
5.2满意度
现在,我们对满意度进行说明,要确定
对
的第K
项
条件的满意度。
先对年龄进行筛选,年龄为大于
或大于
的满意度为0;如果
基本条件
达不到
的要求
即
给它赋值为0值.否则,满意度记为刚好达到为1,超过一个等级加1。
即满意度为
。
这样就体现了,当一方实际条件高于对方期望(要求)条件时,则对方对他(她)的好感(相对于要求条件)就会增加,超过得越多,好感增加得越多。
5.3模型的建立
我们把二十个青年男女抽象化为40个结点得到一个带权二部图,其中Aj表示二十个男青年,Bj表示二十个女青年,而从男青年到女青年有一条带权边,权则由上面求得的满意度矩阵决定,然后,我们用最大二部图匹配算法(匈牙利算法)求出一个最大匹配的解;但是,一开始所求得的是一个有向图,因此我们必须把它无向化,至此对问题
(1)我们仅仅是采用把两结点间权值相加而转化为一个无向图,进而就可以用匈牙利算法对其求解了。
而对于问题
(2)则要采用图的完美匹配算法(KM算法)进行求解,从而使全部配对成功的可能性最大,对于问题(3),则同样采用匈牙利算法只是把权值改变即可,这里我们把结
点间有向边的权值同时大于2且满意度和不满意度差别不是很大时才有可能配对成功此时把它赋为1,而在不满足条件时则赋为0,从而得出能配对成功最多的方案。
下面对匈牙利算法和KM算法进行说明。
匈牙利算法的主要思想是在每次增广的时候不是找一条增广路而是同时找几条点不相交的最短增广路,形成极大增广路集,随后可以沿着这几条增广路同时进行增广。
可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相等的长度,并且随着算法的进行最短增广路的长度是越来越长的,更进一步分析可以证明最多只需增广ceil(sqrt(n))次就可以得到最大匹配(证明在这里略去)。
KM算法:
(全称是Kuhn-Munkras,是这二个人在1957年提出来的),首先为每个点设立一个顶标Li,设vi,j-为(i,j)边的权,如果可以求得一个完美匹配,使得每条匹配边vi,
,其余边
。
此时的解就是最优的,因为匹配边的权和=
,其余任意解的权和都不可能比这个大。
5.4模型的求解
以题中所给数据为例,我们用EXCEL处理后得到权值,然后编程求得结果为:
问题
(1)
男
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
女
B18
B17
B16
B15
B2
B19
B3
B12
B1
B14
男
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
女
B20
B10
B7
B8
B6
B5
B4
B11
B9
B13
问题
(2)
男
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
女
B11
B12
B19
B18
B8
B5
B3
B6
B2
B20
男
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
女
B1
B17
B7
B14
B15
B13
B16
B9
B4
B10
问题(3)
男
A1
A3
A5
A10
A12
A14
A15
A17
A18
A19
女
B15
B18
B19
B9
B2
B6
B4
B14
B11
B8
5.5模型修正
(1)对满意度的说明
首先要注意到两个事实:
其一,如果
基本条件
比
的要求条件
差得越多,则
对
的第K项条件的满意度
就越小,反之亦然。
也就是说,如果一方的实际条件比对方期望(要求)的条件差距越大,则对方对另一方失望就越大,即满意度就越小。
其二,如果
的基本条件
比
的要求条件
高,则
对
的第k项条件的满意度
(k)就会增加,但增加不会太多。
即当一方的实际条件高于对方期望(要求)的条件时,则对方对加一方的好感(相对要求条件)增加不会太大。
而在模型中只考虑了实际条件高于要求条件,好感会增加并考虑到实际条件低于要求条件时,失望会增加,即满意度会减小。
现在模型的基础上加以改进:
如果
的基本条件
达不到
的要求
,即
(
)时,给它赋值
它是一个负值,体现了当一方实际条件低于期望(要求)的条件时,则对方对他(她)失望(相对于要求条件)就会增加差距越大,失望度就越大,相应的满意度就越小。
显然,改进后成功的解决了上面所提出的问题,所以显得更加合理。
满意度矩阵中的各分量分别表示如下:
(2)模型的重新建立
首先,我们把量化的尺度改为1-9尺度把A,B,C,D,E五个等级分别量化为9、7、5、3、1,然后在给出的二部图转化为无向图时则把每个结点分为两个结点,从而问题转化为求40对结点的二部图的最大匹配和完美匹配问题了,对问题1和问题2用同样算法求解,而对于问题3则当满意度矩阵中的权大于零时赋为1而在小于零时则赋为0。
(3)以题中所给数据为例,我们用EXCEL处理后得到权值,然后编程求得结果为:
问题
(1)
男
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
女
B4
B18
B15
B20
B2
B5
B3
B13
B17
B9
男
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
女
B16
B10
B7
B1
B6
B19
B14
B11
B8
B12
问题
(2)
男
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
女
B2
B18
B6
B14
B19
B5
B3
B13
B11
B20
男
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
女
B1
B17
B7
B12
B15
B9
B16
B8
B4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关于 玫瑰 有约 数学模型
![提示](https://static.bingdoc.com/images/bang_tan.gif)