第一次论文.docx
《第一次论文.docx》由会员分享，可在线阅读，更多相关《第一次论文.docx（30页珍藏版）》请在冰点文库上搜索。
第一次论文
玫瑰有约模型
摘要
现在许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注。
所以对婚姻配问题进行建模分析是非常必要的。
我们对某单位的20对大龄青年男女根据条件的不相同，如外貌、性格、气质、事业、财富进行了配对。
资料个人收集整理，勿做商业用途
问题一：
尽量满足个人要求的条件下，使配对成功率尽可能的高，相当于我们设定的条件下使满意度尽可能的高。
我们就用0，1整数规划，分别建立男女5项基本要求和条件的矩阵求和，所得矩阵就是权值矩阵，再根据我们的条件不满足的就归一化为-
，利用匈牙利算法求出最大匹配，资料个人收集整理，勿做商业用途
问题二：
只需对问题一的最后一步权值矩阵运用KM算法球最佳匹配就得到20对男女青年同时配对的最佳方案，而且全部配对成功的可能性最大。
资料个人收集整理，勿做商业用途
问题一，二模型的改进：
A、B、C、D、E，5个等级赋予一定的权值，心理学家认为赋予９、７、５、３、１是比较合理的，再将男对女和女对男的权值矩阵进行对应元素相除得到满意度矩阵，还是利用匈牙利算法和ＫＭ算法进行选择。
问题一的配对率达到了90%,共18对。
问题二配对更加合理。
资料个人收集整理，勿做商业用途
问题三：
男女双方都相互了解了对方的条件和要求，让每个人出一次选择，只有当男女双方相互选中对方时才认为配对成功，就是要男女互相选着的可能性最大，，我们运用决策论方法选着与自己基本要求最接近的，经过配对筛选得到两种配对方案都是7对，配对率是35％。
资料个人收集整理，勿做商业用途
关键字：
模糊数学最大匹配最佳匹配匈牙利算法KM算法决策论
一．问题重述
目前，在许多城市大齡青年的婚姻问题已引起了妇联和社会团体组织的关注。
某单位现有20对大龄青年男女，每个人的基本条件都不相同，如外貌、性格、气质、事业、财富等。
每项条件通常可以分为五个等级A、B、C、D、E，如外貌、性格、气质、事业可分为很好、好、较好、一般、差；财富可分为很多、多、较多、一般、少。
每个人的择偶条件也不尽相同，即对每项基本条件的要求是不同的。
该单位的妇联组织拟根据他（她）们的年龄、基本条件和要求条件进行牵线搭桥。
下面给出20对大龄青年男女的年龄、基本条件和要求条件（如下表）。
一般认为，男青年至多比女青年大5岁，或女青年至多比男青年大2岁，并且要至少满足个人要求5项条件中的2项，才有可能配对成功。
请你根据每个人的情况和要求，建立数学模型帮助妇联解决如下问题：
资料个人收集整理，勿做商业用途
（1）给出可能的配对方案，使得在尽量满足个人要求的条件下，使配对成功率尽可能的高。
（2）给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大。
（3）假设男女双方都相互了解了对方的条件和要求，让每个人出一次选择，只有当男女双方相互选中对方时才认为配对成功，每人只有一次选择机会。
请你告诉20对男女青年都应该如何做出选择，使得自己的成功的可能性最大？
按你的选择方案最多能配对成功多少对？
资料个人收集整理，勿做商业用途
二．问题分析
该问题十分贴近我们的日常生活，是人们普遍关心的问题。
因此，对其进行研究是十分有必要的。
这三个问题的核心都是要求我们如何构造配对方案。
资料个人收集整理，勿做商业用途
对于问题
（一）,在尽量满足个人要求的条件下，要使配对成功率尽可能的高，也就是要我们给出一种方案，把满意度很低的配对的先剔除掉，然后再给出最大匹配，使男女配对的满意度之和最大。
资料个人收集整理，勿做商业用途
对于问题
（二），要使20对男女全部同时配对，并使全部同时成功的可能性最大，就是要我们给出一种方案，使得20对男女配对的满意度之和最大。
资料个人收集整理，勿做商业用途
对于问题（三），要求我们制定出一种方案，并告诉这20对男女（使其成功可能性最大）。
能不能成功取决于双方是否都选取了对方，这就是要看双方各自对对方的满意度之差。
我们取满意度之差的绝对值，这样，问题就转化为求绝对值最小的配对。
资料个人收集整理，勿做商业用途
三．模型假设与符号说明
1.模型假设
（1）男女双方各自的选择是理性的；
（2）各配对双方是否成功不受其他配对影响，且他们之间没有先后顺序；
（3）男女双方的自身条件与要求条件短时间不会改变；
（4）双方在做出选择之前，是不知道对方的选择情况的；
2.符号说明
K=1,2,3,4,5.分别表示外貌、性格、气质、事业、财富这5个条件；
（i=1,2……20）表示第i个男青年编的年龄；
（j=1,2……20）表示第j个女青年编的年龄；
（i=1,2……20,j=1,2……20）表示第i个男青年（或第j个女青年）对第j个女青年（或第i个男青年）的条件的满意个数；资料个人收集整理，勿做商业用途
（i=1,2……20，k=1,2,3,4,5）表示第i个男青年（或第j个女青年）在k方面的基本条件；
（j=1,2……20，k=1,2,3,4,5）表示第j个女青年（或第j个男青年）在k方面的要求条件；
，
表示第i个男青年（或第j个女青年）在k方面对第j个女青年（或第i个男青年）的满意或不满意；
表示男青年与女青年的相互满意度；
，
表示第i个男青年（或第j个女青年）在k方面对第j个女青年（或第i个男青年）的满意度；
表示第i个男青年与第j个女青年的相互满意度之差；
四．模型分析与求解
问题
（一）：
男女双方对对方的满意程度可以用满足对方条件的个数来表示，代表对对方满意的概率，当男女双方都对对方满意时，表示配对成功。
我们用使成功概率之和最大的配对方案来近似代表成功率最大的方案。
资料个人收集整理，勿做商业用途
1.条件量化处理：
对于每个人的外貌、性格、气质、事业、财富五项条件的5个等级A,B,C,D,E,分别用模糊书数学的量化处理，分别处理为“A”=5，“B”=4，“C”=3，“D”=2，“E”=1。
于是可以把原来的两个表格处理为如下两个表格（暂不考虑年龄）：
资料个人收集整理，勿做商业用途
表一：
男
基本条件
要求条件
青
年
外貌
性格
气质
事业
财富
外貌
性格
气质
事业
财富
B1
5
3
4
3
5
5
5
3
4
2
B2
3
5
4
5
2
4
5
4
4
3
B3
4
4
5
4
4
4
5
5
4
3
B4
3
5
4
4
2
3
5
4
3
2
B5
2
4
3
5
5
3
4
4
4
1
B6
3
4
3
4
4
4
4
3
2
3
B7
5
4
4
2
3
3
4
4
2
3
B8
4
5
4
3
2
5
4
3
3
2
B9
5
2
3
1
4
5
5
5
3
3
B10
2
4
5
5
5
5
4
5
2
1
B11
4
5
3
2
5
5
4
3
2
4
B12
5
4
3
5
4
4
5
4
4
3
B13
4
5
2
1
3
5
3
4
4
3
B14
5
5
4
4
2
5
3
3
2
3
B15
5
4
4
3
3
5
5
4
3
2
B16
2
1
4
5
5
5
5
5
1
1
B17
3
5
4
5
2
4
5
4
4
3
B18
5
4
5
3
4
4
4
5
3
3
B19
3
2
5
5
5
5
4
5
1
2
B20
5
4
3
2
1
4
3
4
2
4
表二：
女
基本条件
要求条件
青
年
外貌
性格
气质
事业
财富
外貌
性格
气质
事业
财富
G1
4
5
4
5
2
3
4
4
5
4
G2
4
2
3
1
3
5
4
3
5
4
G3
4
4
3
5
5
4
5
5
4
2
G4
5
1
1
2
5
5
5
2
5
3
G5
4
5
3
3
1
4
4
4
5
5
G6
3
4
5
1
5
4
5
3
4
3
G7
5
3
4
3
5
4
5
4
4
3
G8
5
5
5
3
1
3
4
4
4
5
G9
4
1
3
1
5
5
5
4
4
1
G10
1
5
3
4
4
3
5
4
3
3
G11
5
4
4
3
2
5
5
4
4
5
G12
4
3
2
4
4
4
4
5
5
3
G13
5
3
3
2
5
4
5
4
5
2
G14
5
4
4
3
4
3
4
5
4
3
G15
4
5
3
2
3
4
5
4
4
5
G16
5
5
4
4
3
3
5
4
5
3
G17
3
4
5
5
3
4
5
4
4
4
G18
2
4
5
3
2
4
4
5
4
4
G19
2
3
4
5
4
3
4
5
5
3
G20
5
4
5
1
3
4
5
4
5
4
根据上面两个表，我们可以引入0-1变量（1表示满意，0表示不满意），从而建立如下关系函数：
①，
②，
③，
④，
⑤，
方程⑤的说明：
这个方程首先是年龄条件的剔除处理，我们认为j满足i的条件个数j
可代表j对i满意的概率大小。
当男女双方都对对方满意时，我们认为这对男女配对成功。
根据无关事件概率方程P（AB）=P（A）*P（B）,我们可以用男女对对方满意度的乘积来作为男女互相满意度，这个值的大小可近似代表男女双方配对成功的概率大小。
资料个人收集整理，勿做商业用途
现在我们分别由
、
、
、
、
构造矩阵
、
、
、
、
。
根据匹配的知识，我们把问题
（一）转换为二元图匹配中的最大匹配问题求解，而二元图G的最大匹配的图如下：
该图上面20个点分别为20个不同男青年的代表符号，而下面20个点分别为20个不同女青年的代表符号。
在这里，我们把满意度作为权值进行图论计算。
资料个人收集整理，勿做商业用途
现在我们采用把两结点间的权值相加而转化为一个无向图，进而就可以用匈牙利算法对其求解，得出如下配对方案：
资料个人收集整理，勿做商业用途
B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
G13
G18
G15
G4
G2
G11
G3
G14
G17
G9
B11
B12
B13
B14
B15
B16
B17
B18
B19
B20
G16
G5
G7
G1
G6
G19
G12
G20
G8
G10
问题
（二）：
本题要求使20对配对全部成功的可能性最大，其实质是求出一种完美匹配。
由上一问的关系方程①、②、③、④、⑤，我们采用图论中的KM算法求解，得出如下配对方案：
资料个人收集整理，勿做商业用途
B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
G13
G18
G14
G4
G19
G11
G3
G15
G17
G20
B11
B12
B13
B14
B15
B16
B17
B18
B19
B20
G16
G5
G7
G1
G6
G9
G2
G10
G8
G12
对该模型的评价：
该模型虽然比较粗糙，但是能简单直观的反应男女之间的配对问题，而在问题中我们采用了图论中的匈牙利算法（问题一）和KM（问题二）算法计算出最大匹配和完美匹配使问题更加简单化。
但是细节上存在两点不足：
不足之一，对单项的满足度没有加以区分，例如男对女要求外貌是C（3）,有两个女青年外貌分别为B（4），A（5）在模型中就没有差别;不足之二，模型中只考虑了实际条件高于要求条件好感度增加，并没有考虑到实际条件低于要求条件时，失望会增加，即满意度减小。
资料个人收集整理，勿做商业用途
对已建模型进行改进：
心理学家认为对A，B，C，D,E赋值9，7，5，3，1比较科学。
，
，
，
现在，我们可以用到模型一的匈牙利算法得到问题
（一）的改进模型结果和用KM算法得到问题
（二）的改进模型结果。
结果如下：
资料个人收集整理，勿做商业用途
问题一：
B1
B3
B4
B5
B6
B7
B8
B9
B10
B11
G8
G17
G6
G1
G15
G18
G3
G12
G16
G7
B12
B14
B15
B16
B17
B18
B19
B20
G9
G20
G13
G14
G11
G10
G4
G2
问题二：
B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
G3
G4
G17
G6
G12
G15
G18
G8
G10
G1
B11
B12
B13
B14
B15
B16
B17
B18
B19
B20
G20
G11
G19
G9
G13
G14
G5
G16
G7
G2
问题（三）：
要使每个个体配对成功的可能性最大，我们认为要保证配对的男女青年的成功指数足够高，相互满意度之差越小就越容易成功配对。
因此，本问题就转化为下列方程的最小值问题。
资料个人收集整理，勿做商业用途
，
现在，用
来构造矩阵
。
然后，我们用matlab对其行和列取其最小值，然后取交集，得到如下结果：
B1
B2
B12
B15
B16
B18
B20
G2
G10
G15
G13
G12
G18
G17
或
B1
B12
B15
B16
B17
B18
B20
G2
G15
G13
G12
G10
G18
G17
改进后的模型评价：
本模型比较准确地解决了男女之间的配对问题，然而个人择偶标准还会随时间和社会环境不断变化。
如果再能在模型的改进中考虑到这些问题，结果会更加漂亮。
资料个人收集整理，勿做商业用途
五．参考文献
[1]《数学建模与数学实验》赵静等编著高等教育出版社
[2]《运筹学》钱颂迪等编著清华大学出版社
[2]《线性代数》同济大学数学系编著高等教育出版社
六．参考网站
[1]
七．附件
匈牙利算法：
function[Matching,Cost]=Hungarian（Perf）
%
%[MATCHING,COST]=Hungarian_New（WEIGHTS）
%
%AfunctionforfindingaminimumedgeweightmatchinggivenaMxNEdge资料个人收集整理，勿做商业用途
%weightmatrixWEIGHTSusingtheHungarianAlgorithm.资料个人收集整理，勿做商业用途
%
%AnedgeweightofInfindicatesthatthepairofverticesgivenbyits资料个人收集整理，勿做商业用途
%positionhavenoadjacentedge.
%
%MATCHINGreturnaMxNmatrixwithonesintheplaceofthematchingsand资料个人收集整理，勿做商业用途
%zeroselsewhere.
%
%COSTreturnsthecostoftheminimummatching
%Writtenby:
AlexMelin30June2006
%InitializeVariables
Matching=zeros（size（Perf））;
%CondensethePerformanceMatrixbyremovinganyunconnectedverticesto资料个人收集整理，勿做商业用途
%increasethespeedofthealgorithm
%Findthenumberineachcolumnthatareconnected资料个人收集整理，勿做商业用途
num_y=sum（~isinf（Perf）,1）;
%Findthenumberineachrowthatareconnected
num_x=sum（~isinf（Perf）,2）;
%Findthecolumns（vertices）androws（vertices）thatareisolated资料个人收集整理，勿做商业用途
x_con=find（num_x~=0）;
y_con=find（num_y~=0）;
%AssembleCondensedPerformanceMatrix
P_size=max（length（x_con）,length（y_con））;
P_cond=zeros（P_size）;
P_cond（1:
length（x_con）,1:
length（y_con））=Perf（x_con,y_con）;资料个人收集整理，勿做商业用途
ifisempty（P_cond）
Cost=0;
return
end
%Ensurethataperfectmatchingexists
%CalculateaformoftheEdgeMatrix
Edge=P_cond;
Edge（P_cond~=Inf）=0;
%Findthedeficiency（CNUM）intheEdgeMatrix
cnum=min_line_cover（Edge）;
%Projectadditionalverticesandedgessothataperfectmatching资料个人收集整理，勿做商业用途
%exists
Pmax=max（max（P_cond（P_cond~=Inf）））;
P_size=length（P_cond）+cnum;
P_cond=ones（P_size）*Pmax;
P_cond（1:
length（x_con）,1:
length（y_con））=Perf（x_con,y_con）;资料个人收集整理，勿做商业用途
%*************************************************
%MAINPROGRAM:
CONTROLSWHICHSTEPISEXECUTED
%*************************************************
exit_flag=1;
stepnum=1;
whileexit_flag
switchstepnum
case1
[P_cond,stepnum]=step1（P_cond）;
case2
[r_cov,c_cov,M,stepnum]=step2（P_cond）;
case3
[c_cov,stepnum]=step3（M,P_size）;
case4
[M,r_cov,c_cov,Z_r,Z_c,stepnum]=step4（P_cond,r_cov,c_cov,M）;资料个人收集整理，勿做商业用途
case5
[M,r_cov,c_cov,stepnum]=step5（M,Z_r,Z_c,r_cov,c_cov）;资料个人收集整理，勿做商业用途
case6
[P_cond,stepnum]=step6（P_cond,r_cov,c_cov）;
case7
exit_flag=0;
end
end
%Removeallthevirtualsatellitesandtargetsanduncondensethe资料个人收集整理，勿做商业用途
%Matchingtothesizeoftheoriginalperformancematrix.资料个人收集整理，勿做商业用途
Matching（x_con,y_con）=M（1:
length（x_con）,1:
length（y_con））;资料个人收集整理，勿做商业用途
Cost=sum（sum（Perf（Matching==1）））;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%资料个人收集整理，勿做商业用途
%STEP1:
Findthesmallestnumberofzerosineachrow资料个人收集整理，勿做商业用途
%andsubtractthatminimumfromitsrow
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%资料个人收集整理，勿做商业用途
function[P_cond,stepnum]=step1（P_cond）
P_size=length（P_cond）;
%Loopthroughteachrow
forii=1:
P_size
rmin=min（P_cond（ii,:
））;
P_cond（ii,:
）=P_cond（ii,:
）-rmin;
end
stepnum=2;
%**************************************************************************资料个人收集整理，勿做商业用途
%STEP2:
FindazeroinP_cond.Iftherearenostarredzerosinits资料个人收集整理，勿做商业用途
%columnorrowstartthezero.Repeatforeachzero资料个人收集整理，勿做商业用途
%***
升级会员 