用Matlab分析玫瑰有约论文

1、个人资料整理仅限学习使用数学软件实习论文基于 0-1 型整数规划的玫瑰有约问题系别信息与计算科学专业信息与计算科学学号7070302姓名李文毅指导教师姜玉山 张重阳2009 年 5月 12 日9/14个人资料整理仅限学习使用基于 0-1 型整数规划的玫瑰有约问题摘要在一个 “剩男剩女 ”风行的时代，婚姻介绍所为征婚男女青年牵线搭桥显得尤为重要。本文首先根据男女青年的基本条件和择偶要求条件运用层次分析法中关于条件等级差的度量标准分别对其设计了量化方案，然后应用两线性空间向量夹角模型建立男女青年之间的好感程度相互满意度，最后根据问题要求建立0-1 整数规划模型，应用匈牙利算法通过MATLAB 软件

2、得出最佳配对方案。b5E2RGbCAP关键词 ：剩男剩女， MATLAB ，匈牙利算法， 0-1 整数规划I/14个人资料整理仅限学习使用1 绪 论1.1 研究背景我们穷尽一生的时光去寻觅自己的另一半。这个过程难免孤独和寂寞，也难免失望和痛苦，也许会很漫长，甚至特别漫长，但是，我们本是雌雄同体的，自我复原是一种本能。另一半能修复我们身上和心上所有的缺口，两个孤单的灵魂最终合二为一。 这就是柏拉图关于爱情的一个浪漫并充满了神话色彩的著名假设。“情剩 ”这个有些尴尬和自嘲的群体正在不断壮大，并且普遍存在于现代都市。一股单身潮无可避免地在各大城市急速蔓延。2006 年 5 月 26 日，中国经济网以

3、头条报道了“情剩 ”这个标题， 2006 年 8 月社科类书籍剩男剩女出版。那时候的数据显示：2005 年北京剩女数达 30 万；上海43 万数年以后，这样庞大的数字已经以几何数在增加。2008年末，有关 “剩男剩女 ”的爱情喜剧电影集中地上映。马俪文执导的桃花运率先上映，张建亚的爱呼 2：爱情左右、徐克的女人不坏紧随其后，后来的冯小刚的非诚勿扰则将 “情剩 ”风推向了高潮。相亲，一度被看作是“旧时代 ”的产物再一次在 21 世纪的 “剩男剩女 ”中流行起来，各种相亲方式相继上演，多元化发展。“替子征婚”、“网络征婚 ”、 “电视征婚 ” 其中，互联网上的征婚成为E 时代 “剩男剩女 ”最便捷

4、和最受欢迎的方式。一个庞大的网络婚恋市场的形成很能说明这真的是一个“情剩 ”风行的时代。然而每个男女青年的择偶条件也不尽相同，即对每项基本条件的要求是不相同的。于是各种类似于婚姻介绍所的机构根据他<她）们的年龄、基本条件和要求条件进行牵线搭桥。p1EanqFDPw1.2 研究的意义和目的本文模拟婚姻介绍所，为征婚男女青年巧搭鹊桥，促进他们喜结良缘，同时也为一些男女性比例失调的单位或社区的独身者提供了社交的机会，为在自己的生活范围内难以找到理想意中人的独身者提供了更大的选择范围，这在一定程度上有利于提高人们的婚姻满意度，从而加强家庭的稳定。DXDiTa9E3d1.3论文研究思路和框架1、本

5、论文的研究思路。针对目前许多城市出现“剩男剩女 ”的现象，本文为征婚男女牵线搭桥，首先根据层次分析法中关于条件等级差的度量标准对他们的基本条件和要求条件进行量化，分别得出他们的基本条件向量和要求条件向量，然后应用两线性空间向量夹角模型建立1/14个人资料整理仅限学习使用男女青年相互满意度，根据0-1 整数规划建立数学模型，通过MATLAB 软件得出最佳配对方案。 RTCrpUDGiT2、论文框架。第一部分绪论，主要对论文的研究背景、研究目的和意义及论文的研究思路和方法进行阐述。第二部分是介绍0-1 型整数线性规划数学模型，并介绍0-1 型整数线性规划MATLAB 指令及指派问题中的匈牙利方法的

6、基本思想和匈牙利算法的基本步骤。5PCzVD7HxA第三部分首先对问题进行分析，然后对男女青年的基本条件和要求条件进行量化处理，建立数学模型，通过MATLAB 软件得出男女青年的最佳匹配。jLBHrnAILg2 0-1 型整数线性规划在线性规划中，有一类问题要求最优解中全部或部分决策变量的取值必须满足整数条件，这类问题称为整数规划问题。当所有变量都要求是整数时，称为纯整数规划；如果只有一部分变量要求取整，则称为混合整数规划。整数规划中还有一类特殊的问题，要求所有变量只能取 0 或 1，该类型的整数规划称为 0-1 规划。 xHAQX74J0X0-1 型整数线性规划，它的变量仅取值0 或 1。它

7、的提法如下：其中我们称此时的决策变量为 0-1 变量，或称为二进制变量。下面将介绍 0-1 型整数线性规划 MATLAB 指令以及指派问题中的匈牙利方法。 LDAYtRyKfE 2.1 0-1 型整数线性规划 MATLAB 指令X=bintprog(f,A,b>求解 0-1 型整数线性规划，用法类似于linprogX= bintprog(f,A,b,Aeq,beq> 求解下面线性规划：x分量取值 0或 1X= bintprog(f,A,b,Aeq,beq ，x0>指定迭代初值 x0，如果没有不等式约束，可用 替2/14个人资料整理仅限学习使用代 A 和 b 表示缺省，如果没有

8、等式约束，可用 替代 Aeq 和 beq 表示缺省；用 x,Fval 代替上述各命令行中左边的 x，则可得到最优解处的函数值 Fval.Zzz6ZB2Ltk同时可以用 help bintprog 查阅有关该命令的详细信息。2.2指派问题中的匈牙利方法“匈牙利方法 1 ”最早是由匈牙利数学家康尼格(D.Konig> 用来求矩阵中零元素的个数的一种方法，由此他证明了“矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数 ”。1955 年由库恩）在求解著名的指派问题时，引用了这一结论，并对具体算法做了改进，仍然称为“匈牙利方法 ”。dvzfvkwMI11、匈牙利方法的基本思想：由于每个问

9、题都有一个相应的效益矩阵，可以通过初等变换修改效益矩阵的行或列的元素，使得在每一行或每一列中至少有一个零元素，直到在不同行、不同列中至少有一个零元素，从而得到与这些零元素相对应的一个完全分配方案，这个方案是原问题的一个最优分配方案。rqyn14ZNXI2、匈牙利方法的基本步骤：根据指派问题的最优性，“若从效益矩阵的一行 <或列）各元素分别减去该行<或列）的最小元素，得到新矩阵，那么以 D 为效益矩阵所对应问题的最优解与原问题的最优解相同 ”。此时求最优解的问题可以转化为求效益矩阵的最大 1 元素组的问题。下面给出一般的匈牙利方法的计算步骤： EmxvxOtOco第一步：对效益矩阵进

10、行变换，使每行每列都出现有0 元素。1）从效益矩阵 C 中每一行减去该行的最小元素；2）再在所得矩阵中每一列减去该列的最小元素，所得矩阵记为。第二步：将矩阵D 中 0 元素置为 1 元素，非零元置为0 元素，记此矩阵为E。第三步：确立独立1 元素组。1）在矩阵 E 含有 1 元素的各行中选择1 元素最少的行，比较该行中各1 元素所在的列中 1 元素的个数，选择1 元素的个数最少的一列那个1 元素； SixE2yXPq52）将所选的 1 元素所在的行和列清零；3）重复第二步和第三步，直到没有1 元素为止，即得到一个独立1 元素组。第四步：判断是否为最大独立1 元素组。1）如果所得独立1 元素组是

11、原效益矩阵的最大独立1 元素组 <即 1 元素组的个数3/14个人资料整理仅限学习使用等于矩阵的阶数），则已得到最优解，停止计算。6ewMyirQFL2）如果所得独立1 元素组还不是原效益矩阵的最大独立1 元素组，那么利用寻找可扩路的方法对其进行扩张，进行下一步。kavU42VRUs第五步：利用寻找可扩路方法确定最大独立1 元素组1）做最少的直线覆盖矩阵D 的所有 0 元素；2）在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最小元素，在没被直线覆盖的各列加上此最小元素，得到一个新的矩阵，返回第二步。y6v3ALoS893 玫瑰有约问题3.1 问题的分析该问题是现实生活中

12、的实际问题，主要就是确定合理配对方案，使得在尽量满足个人要求的条件下，使配对成功率尽可能高。一对青年男女能否配对成功，主要取决于相互之间的好感的程度“满意度 ”，单方面的高满意度也不一定能配对成功。在这里双方的满意度主要反映出一个人对另一个人的客观和主观的看法。M2ub6vSTnP所谓的 “成功率 ”，就是男女双方最终配对成功的概率。实际上。可以利用他们相互之间的满意度来间接刻画。相互的满意度越高，双方配对成功的概率就越大。0YujCfmUCw要使配对成功率尽可能的高，也就是给出一种方案，使得5 对男女的配对的满意度之和最高。表 3.1 男青年的基本条件和要求条件男基本条件要求条件青年外貌性格

13、气质事业财富年龄外貌性格气质事业财富ACBCA29AACBDCABAD29BABBCABBDC30CBBDCDBAAA32ACBBCBABAD28ABACE表 3.2 女青年的基本条件和要求条件女青基本条件要求条件年外貌性格气质事业财富年龄外貌性格气质事业财富BABCD29CBBAB4/14个人资料整理仅限学习使用CBAEA30ABCBBDBCBA27BCDBBAAACE31AEEDABCADC28CABCC3.2 模型的假设与符号说明1、模型的假设<1）题目所给出的男女青年的评价是客观真实的；<2）每个人在选择对方时都是理智的；<3）五项条件在选择对方时所起的作用是均等的。

14、2、符号的约定和分别表示男青年与女青年；表示第 i 个男青年与第j 个女青年配对时取值为 1，否则取值为0；和分别表示的要求条件量化向量与的基本条件量化向量；表示男青年与女青年的相互满意度。 eUts8ZQVRd3.3 模型的准备1、条件的量化处理对于每个人的外貌、性格、气质、事业和财富五项条件的五个等级A，B，C，D和 E 分别作量化处理，根据层次分析中关于条件等级差的度量标准2 ，对 A ，B，C，D 和 E 分别赋权值 9， 7， 5， 3， 1。于是得到每个青年男女青年的基本条件量化向量和要求条件量化向量。sQsAEJkW5T2、满意度的确定<1）对单项条件的满意度确定对的第 k

15、<1 i, j）项条件的满意度。在这引进两线性空间向量5,1 k 5夹角最小模型：在线性空间中，两个非零向量和的夹角按如下定义：<3.1）5/14个人资料整理仅限学习使用式中是向量和的内积，分别是向量和的范数。从几何意义上来说，夹角越小，表明其中一个向量在另一个向量上的投影越大，即两个向量越接近。 GMsIasNXkA按 <3.1）式可以求出的要求条件量化向量与的基本条件量化向量之间的夹角，称为满意参数7 ，满意参数越小，表明的基本条件与的要求条件越趋于一致。 TIrRGchYzg%Matlab 程序：function f=fun(x,y>model_2a=(sum(x

16、.2>>1/2。model_2b=(sum(y.2>>1/2。f=acos(sum(x.*y>/(model_2a>*(model_2b>>> 。<2）相互满意度男青年与女青年的相互满意度定义为经过计算可得到男女青年相互之间的满意度：3.4 模型的建立与求解根据问题的要求，要使得在尽量满足个人要求的条件下，使配对成功率尽可能的高。我们可以用5 对男女青年的相互满意度指标之和来刻画总的配对成功的成功率，于是我们将问题归结为所有5 对男女青年如何配对使得有最大值，即问题的模型为7EqZcWLZNX，6/14个人资料整理仅限学习使用这是一个

17、 0-1 型整数规划问题，根据匈牙利算法利用MATLAB 编程求解可得最优配对方案如表 3-3 最优值 <总满意度）为 z=8.9484。lzq7IGf02E %其 MATLAB 程序如下：function z,ans=fenpei(marix>%/zvpgeqJ1hk%输入效率矩阵 marix 为方阵。%若效率矩阵中有M, 则用一充分大的数代替。%输出 z 为最优解， ans为 最优分配矩阵；%/NrpoJac3v1a=marix。b=a。%确定矩阵维数s=size(a>。%确定矩阵行最小值，进行行减ml=min(a'> 。for i=1:sa(i,:>

18、=a(i,:>-ml(i> 。end%确定矩阵列最小值，进行列减mr=min(a>。for j=1:sa(:,j>=a(:,j>-mr(j> 。end% start working num=0。while(num=s> %终止条件是 “ <0） ”的个数与矩阵的维数相同7/14个人资料整理仅限学习使用%index用 以 标 记 矩 阵 中 的 零 元 素 ， 若a(i,j>=0 ， 则index(i,j>=1, 否 则index(i,j>=0 1nowfTG4KIindex=ones(s>。index=a&inde

19、x。index=index。%flag 用以标记划线位， flag=0 表示未被划线，%flag=1 表示有划线过， flag=2 表示为两直线交点%ans用以记录 a 中“ <0）”的位置%循环后重新初始化flag,ansflag = zeros(s>。ans = zeros(s>。%一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，%即在 flag>0 位,index=0while(sum(sum(index>>>%按行找出 “ <0）”所在位置，并对 “ <0）”所在列划线，%即设置 flag,同时修改 index,将结果填入

20、ansfor i=1:st=0。l=0。for j=1:sif(flag(i,j>=0&&index(i,j>=1>l=l+1。t=j。endendif(l=1>flag(:,t>=flag(:,t>+1 。index(:,t>=0。ans(i,t>=1。end8/14个人资料整理仅限学习使用end%按列找出 “ <0）”所在位置，并对 “ <0）”所在行划线，%即设置 flag,同时修改 index,将结果填入 ansfor j=1:st=0。r=0。for i=1:sif(flag(i,j>=0&&a

21、mp;index(i,j>=1>r=r+1。t=i。endendif(r=1>flag(t,:>=flag(t,:>+1 。index(t,:>=0。ans(t,j>=1。endendend %对 while(sum(sum(index>>>%处理过程%计数器：计算 ans中 1 的个数，用 num 表示num=sum(sum(ans>>。% 判断是否可以终止，若可以则跳出循环if(s=num>break。end%否则，进行下一步处理%确定未被划线的最小元素，用m 表示m=max(max(a>>。for

22、i=1:sfor j=1:s9/14个人资料整理仅限学习使用if(flag(i,j>=0>if(a(i,j><m>m=a(i,j>。endendendend%未被划线，即 flag=0 处减去 m；线交点，即 flag=2 处加上 mfor i=1:sfor j=1:sif(flag(i,j>=0>a(i,j>=a(i,j>-m 。endif(flag(i,j>=2>a(i,j>=a(i,j>+m。endendendend %对 while(num=s>%计算最优 <min）值zm=ans.*b。z=0。z=sum(sum(zm>>。程序运行如下：表 3.3 最优配对方案10/14个人资料整理仅限学习使用男女结论本文主要研究了婚姻中男女配对的量化方案，将定性化的问题应用层次分析法、整数线性规划的理论转化为定量研究。首先依据层次分析法中关于条件等级差的度量标准对各位男女青年的基本条件和要求条件进行量