用Matlab分析玫瑰有约论文.docVIP

数学软件实习论文基于0-1型整数规划的玫瑰有约问题系 别信息与计算科学专 业信息与计算科学学 号7070302姓 名李文毅指导教师姜玉山 张重阳2009年5月12日 信息与计算科学系数学软件实习（论文） 第 I 页基于0-1型整数规划的玫瑰有约问题摘 要在一个“剩男剩女”风行的时代，婚姻介绍所为征婚男女青年牵线搭桥显得尤为重要。本文首先根据男女青年的基本条件和择偶要求条件运用层次分析法中关于条件等级差的度量标准分别对其设计了量化方案，然后应用两线性空间向量夹角模型建立男女青年之间的好感程度相互满意度，最后根据问题要求建立0-1整数规划模型，应用匈牙利算法通过MATLAB软件得出最佳配对方案。关键词：剩男剩女，MATLAB，匈牙利算法，0-1整数规划 信息与计算科学系数学软件实习（论文） 第 11 页1 绪 论1.1 研究背景我们穷尽一生的时光去寻觅自己的另一半。这个过程难免孤独和寂寞，也难免失望和痛苦，也许会很漫长，甚至特别漫长，但是，我们本是雌雄同体的，自我复原是一种本能。另一半能修复我们身上和心上所有的缺口，两个孤单的灵魂最终合二为一。 这就是柏拉图关于爱情的一个浪漫并充满了神话色彩的著名假设。“情剩”这个有些尴尬和自嘲的群体正在不断壮大，并且普遍存在于现代都市。一股单身潮无可避免地在各大城市急速蔓延。2006年5月26日，中国经济网以头条报道了“情剩”这个标题，2006年8月社科类书籍剩男剩女出版。那时候的数据显示：2005年北京剩女数达30万；上海43万数年以后，这样庞大的数字已经以几何数在增加。2008年末，有关“剩男剩女”的爱情喜剧电影集中地上映。马俪文执导的桃花运率先上映，张建亚的爱呼2：爱情左右、徐克的女人不坏紧随其后，后来的冯小刚的非诚勿扰则将“情剩”风推向了高潮。相亲，一度被看作是“ 旧时代”的产物再一次在21世纪的“剩男剩女”中流行起来，各种相亲方式相继上演，多元化发展。“替子征婚”、“网络征婚”、“电视征婚”其中，互联网上的征婚成为E时代“剩男剩女”最便捷和最受欢迎的方式。一个庞大的网络婚恋市场的形成很能说明这真的是一个“情剩”风行的时代。然而每个男女青年的择偶条件也不尽相同，即对每项基本条件的要求是不相同的。于是各种类似于婚姻介绍所的机构根据他（她）们的年龄、基本条件和要求条件进行牵线搭桥。1.2 研究的意义和目的本文模拟婚姻介绍所，为征婚男女青年巧搭鹊桥，促进他们喜结良缘，同时也为一些男女性比例失调的单位或社区的独身者提供了社交的机会，为在自己的生活范围内难以找到理想意中人的独身者提供了更大的选择范围，这在一定程度上有利于提高人们的婚姻满意度，从而加强家庭的稳定。1.3论文研究思路和框架1、本论文的研究思路。针对目前许多城市出现“剩男剩女”的现象，本文为征婚男女牵线搭桥，首先根据层次分析法中关于条件等级差的度量标准对他们的基本条件和要求条件进行量化，分别得出他们的基本条件向量和要求条件向量，然后应用两线性空间向量夹角模型建立男女青年相互满意度，根据0-1整数规划建立数学模型，通过MATLAB软件得出最佳配对方案。2、论文框架。第一部分绪论，主要对论文的研究背景、研究目的和意义及论文的研究思路和方法进行阐述。第二部分是介绍0-1型整数线性规划数学模型，并介绍0-1型整数线性规划MATLAB指令及指派问题中的匈牙利方法的基本思想和匈牙利算法的基本步骤。第三部分首先对问题进行分析，然后对男女青年的基本条件和要求条件进行量化处理，建立数学模型，通过MATLAB软件得出男女青年的最佳匹配。20-1型整数线性规划在线性规划中，有一类问题要求最优解中全部或部分决策变量的取值必须满足整数条件，这类问题称为整数规划问题。当所有变量都要求是整数时，称为纯整数规划；如果只有一部分变量要求取整，则称为混合整数规划。整数规划中还有一类特殊的问题，要求所有变量只能取0或1，该类型的整数规划称为0-1规划。0-1型整数线性规划，它的变量仅取值0或1。它的提法如下：其中我们称此时的决策变量为0-1变量，或称为二进制变量。下面将介绍0-1型整数线性规划MATLAB指令以及指派问题中的匈牙利方法。2.10-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，如果没有不等式约束，可用替代A和b表示缺省，如果没有等式约束，可用替代Aeq和beq表示缺省；用x,Fval代替上述各命令行中左边的x，则可得到最优解处的函数值Fval. 同时可以用help bintprog查阅有关该命令的详细信息。2.2指派问题中的匈牙利方法“匈牙利方法1” 最早是由匈牙利数学家康尼格(D.Konig)用来求矩阵中零元素的个数的一种方法，由此他证明了“矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数”。1955年由库恩（W.W.Kuhn）在求解著名的指派问题时，引用了这一结论，并对具体算法做了改进，仍然称为“匈牙利方法”。1、匈牙利方法的基本思想：由于每个问题都有一个相应的效益矩阵，可以通过初等变换修改效益矩阵的行或列的元素，使得在每一行或每一列中至少有一个零元素，直到在不同行、不同列中至少有一个零元素，从而得到与这些零元素相对应的一个完全分配方案，这个方案是原问题的一个最优分配方案。2、匈牙利方法的基本步骤：根据指派问题的最优性，“若从效益矩阵的一行（或列）各元素分别减去该行（或列）的最小元素，得到新矩阵，那么以D为效益矩阵所对应问题的最优解与原问题的最优解相同”。此时求最优解的问题可以转化为求效益矩阵的最大1元素组的问题。下面给出一般的匈牙利方法的计算步骤：第一步：对效益矩阵进行变换，使每行每列都出现有0元素。1）从效益矩阵C中每一行减去该行的最小元素；2）再在所得矩阵中每一列减去该列的最小元素，所得矩阵记为。第二步：将矩阵D中0元素置为1元素，非零元置为0元素，记此矩阵为E。第三步：确立独立1元素组。1）在矩阵E含有1元素的各行中选择1元素最少的行，比较该行中各1元素所在的列中1元素的个数，选择1元素的个数最少的一列那个1元素；2）将所选的1元素所在的行和列清零；3）重复第二步和第三步，直到没有1元素为止，即得到一个独立1元素组。第四步：判断是否为最大独立1元素组。1）如果所得独立1元素组是原效益矩阵的最大独立1元素组（即1元素组的个数等于矩阵的阶数），则已得到最优解，停止计算。2）如果所得独立1元素组还不是原效益矩阵的最大独立1元素组，那么利用寻找可扩路的方法对其进行扩张，进行下一步。第五步：利用寻找可扩路方法确定最大独立1元素组1）做最少的直线覆盖矩阵D的所有0元素；2）在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最小元素，在没被直线覆盖的各列加上此最小元素，得到一个新的矩阵，返回第二步。3玫瑰有约问题3.1 问题的分析该问题是现实生活中的实际问题，主要就是确定合理配对方案，使得在尽量满足个人要求的条件下，使配对成功率尽可能高。一对青年男女能否配对成功，主要取决于相互之间的好感的程度“满意度”，单方面的高满意度也不一定能配对成功。在这里双方的满意度主要反映出一个人对另一个人的客观和主观的看法。所谓的“成功率”，就是男女双方最终配对成功的概率。实际上。可以利用他们相互之间的满意度来间接刻画。相互的满意度越高，双方配对成功的概率就越大。要使配对成功率尽可能的高，也就是给出一种方案，使得5对男女的配对的满意度之和最高。表3.1 男青年的基本条件和要求条件男 青年基本条件要求条件外貌性格气质事业财富年龄外貌性格气质事业财富ACBCA29AACBDCABAD29BABBCABBDC30CBBDCDBAAA32ACBBCBABAD28ABACE表3.2 女青年的基本条件和要求条件女青年基本条件要求条件外貌性格气质事业财富年龄外貌性格气质事业财富BABCD29CBBABCBAEA30ABCBBDBCBA27BCDBBAAACE31AEEDABCADC28CABCC3.2 模型的假设与符号说明1、模型的假设（1）题目所给出的男女青年的评价是客观真实的；（2）每个人在选择对方时都是理智的；（3）五项条件在选择对方时所起的作用是均等的。2、符号的约定和分别表示男青年与女青年；表示第i个男青年与第j个女青年配对时取值为1，否则取值为0；和分别表示的要求条件量化向量与的基本条件量化向量；表示男青年与女青年的相互满意度。3.3 模型的准备1、条件的量化处理对于每个人的外貌、性格、气质、事业和财富五项条件的五个等级A，B，C，D和E分别作量化处理，根据层次分析中关于条件等级差的度量标准2，对A，B，C，D和E分别赋权值9，7，5，3，1。于是得到每个青年男女青年的基本条件量化向量和要求条件量化向量。2、满意度的确定（1）对单项条件的满意度确定对的第k（1i, j5,1k5）项条件的满意度。在这引进两线性空间向量夹角最小模型：在线性空间中，两个非零向量和的夹角按如下定义： （3.1）式中是向量和的内积，分别是向量和的范数。从几何意义上来说，夹角越小，表明其中一个向量在另一个向量上的投影越大，即两个向量越接近。按（3.1）式可以求出的要求条件量化向量与的基本条件量化向量之间的夹角，称为满意参数7，满意参数越小，表明的基本条件与的要求条件越趋于一致。%Matlab程序：function f=fun(x,y)model_2a=(sum(x.2)1/2;model_2b=(sum(y.2)1/2;f=acos(sum(x.*y)/(model_2a)*(model_2b);（2）相互满意度男青年与女青年的相互满意度定义为经过计算可得到男女青年相互之间的满意度：3.4 模型的建立与求解根据问题的要求，要使得在尽量满足个人要求的条件下，使配对成功率尽可能的高。我们可以用5对男女青年的相互满意度指标之和来刻画总的配对成功的成功率，于是我们将问题归结为所有5对男女青年如何配对使得有最大值，即问题的模型为，这是一个0-1型整数规划问题，根据匈牙利算法利用MATLAB编程求解可得最优配对方案如表3-3最优值（总满意度）为z=8.9484。%其MATLAB程序如下：function z,ans=fenpei(marix)%/ %输入效率矩阵 marix 为方阵; %若效率矩阵中有 M,则用一充分大的数代替; %输出z为最优解，ans为 最优分配矩阵；%/a=marix;b=a;%确定矩阵维数s=size(a);%确定矩阵行最小值，进行行减ml=min(a);for i=1:s a(i,:)=a(i,:)-ml(i);end%确定矩阵列最小值，进行列减mr=min(a);for j=1:s a(:,j)=a(:,j)-mr(j);end% start workingnum=0;while(num=s) %终止条件是“（0）”的个数与矩阵的维数相同 %index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0 index=ones(s); index=a&index; index=index; %flag用以标记划线位，flag=0 表示未被划线， %flag=1 表示有划线过，flag=2 表示为两直线交点 %ans用以记录 a 中“（0）”的位置 %循环后重新初始化flag,ans flag = zeros(s); ans = zeros(s); %一次循环划线全过程，终止条件是所有的零元素均被直线覆盖， %即在flag0位,index=0 while(sum(sum(index) %按行找出“（0）”所在位置，并对“（0）”所在列划线， %即设置flag,同时修改index,将结果填入ans for i=1:s t=0; l=0; for j=1:s if(flag(i,j)=0&index(i,j)=1) l=l+1; t=j; end end if(l=1) flag(:,t)=flag(:,t)+1; index(:,t)=0; ans(i,t)=1; end end %按列找出“（0）”所在位置，并对“（0）”所在行划线， %即设置flag,同时修改index,将结果填入ans for j=1:s t=0; r=0; for i=1:s if(flag(i,j)=0&index(i,j)=1) r=r+1; t=i; end end if(r=1) flag(t,:)=flag(t,:)+1; index(t,:)=0; ans(t,j)=1; end end end %对 while(sum(sum(index) %处理过程 %计数器：计算ans中1的个数，用num表示 num=sum(sum(ans); % 判断是否可以终止，若可以则跳出循环 if(s=num) break; end %否则，进行下一步处理 %确定未被划线的最小元素，用m表示 m=max(max(a); for i=1:s for j=1:s if(flag(i,j)=0) if(a(i,j)m) m=a(i,j); end end end end %未被划线，即flag=0处减去m；线交点，即flag=2处加上m for i=1:s for j=1:s if(flag(i,j)=0) a(i,j)=a(i,j)-m; end if(flag(i,j)=2) a(i,j)=a(i,j)+m; end end endend %对while(num=s) %计算最优（min）值zm=ans.*b;z=0;z=sum(sum(zm);程序运行如下：表3.3最优配对方案男女结 论本文主要研究了婚姻中男女配对的量化方案，将定性化的问题应用层次分析法、整数线性规划的理论转化为定量研究。首先