2013数学建模会议分组问题.doc

会议分组问题摘要通过对问题的分析，我们确定运用优化的整数规划模型、矩阵理论和置换等方面的知识和技巧。通过矩阵将决策变量和所要求解的目标函数建立联系。在提出模型目标函数的过程中，首先我们提出了代表相遇次数的概念，用矩阵Q表示其任意两个代表的相遇次数，并利用矩阵的Frobenius范数控制了Q中元素的大小及其均匀程度，得到目标函数f(x)，从而求解代表的相遇次数。第一个目标函数设定后，基于f(x)在群体整体换组时不能起到控制作用的问题,决定使用共同成员概念：即任意两组（可以属于不同场次）整个会议中的交集。利用矩阵A，对矩阵的Frobenius范数的运用使群体整体换组现象得到了有效的遏制，对与会者混合程度进行了控制。求解模型时，使用迭代算法，利用线性规划，在目标函数可行域范围内查找最优解可以利用MATLAB软件设计出计算可行初始解-随机产生一个可行解-局部优化-全局优化从而达到全局最优解的三步求解的方法，局部-全局的步骤解出了全局最优解，简化运算步骤的同时提高了结果优化程度，降低对初值的依赖程度，很好的达到了与会者需要充分混合的目的。基于算法的目标函数，因为在建立时具有一般性，若需建立起优化全局的目标函数，只需对参数进行改变。这样一来模型的推广得到了算法上的支持，带来了极大的便利。我们此次建模得到了合适的人员分配结果，达到了建模的目的。关键词：抽屉原理 相遇矩阵 共同成员 Frobenius范数1、 问题重述目前，国内外许多重要会议都是以分组形式进行研讨，以便充分交流、沟通。一般地，一个由N名代表参加的会议，要分为M个场次，每场会议分为L个小组，并且要求每个小组的人数基本均衡。问题1：请建立分组方案的数学模型，使得尽可能让任意两个来自不同地区的委员之间都有见面交流的机会。问题2：设计求解上述分组模型的有效算法。问题3：现有一个学术团体要举行由37位专家参加的学术研讨会，每个专家所在地区的信息见表1。会议分5场进行，每场会议又分5个小组，每个小组人数要基本均衡。请根据问题1所建立的模型以及问题2设计的算法，给出5场会议的每一场各个组中有哪些委员参加的安排方案。说明：论文要附有求解问题3源程序的全部代码，并确保能够直接运行以检验结果的正确性。37位专家所在地区信息表专家1234567地区BJBJBJBJSHSHSH专家891011121314地区HZHZTJTJCQCQCD专家15161718192021地区CDSYHACCZZSZXA专家22232425262728地区GZWHQDJNXJXZXN专家29303132333435地区DLHFSJCSHNNJXM专家3637地区YCLZ二、模型假设（1）假设各场会议及各小组间是相互独立的；（2）假设所有代表严格遵守派遣方案，不会改变制定的分配方案；（3）假设来自不同地区的代表之间无其他差异；（4）假设每场会议各组人数分配为7,7,7,9,9。注：对于假设（4），我们可以运用初等模型中的公平分配得到，具体过程如下：三、变量及符号说明和数学描述1、变量符号说明（1） ：0-1决策变量,表示第i位代表有否参加第k场第j组会议；（2） ：开会分组矩阵，表示整次会议每场代表的分组安排，其中表示第k场会议的分组矩阵，其行向量表示第k场会议第j组的分组矩阵；（3） ：相遇矩阵；（4） ：目标函数一，用来控制代表相遇次数；（5） ：目标函数二，用于控制不同场间组间共同成员个数；（6） ：总的目标函数，综合考虑和的目标函数.2、变量符号数学描述（1）（2），k表示第k段会议，j表示第j组，k=1,2,M，j=1,2,L,i=1,2,N.(3)(4)（5）四、模型建立通过使用（0-1）整数规划来建立该问题的模型。题目要求每个小组的人数基本均衡，使得尽可能让任意两个来自不同地区的委员之间都有见面交流的机会。从这两个要求出发，分别从相遇代表次数和共同成员数目两个角度建立了两个目标函数。再加上题设要求以及模型假设得到的约束条件，完成本模型的建立。具体过程以及模型如下所示。题目要求分组名单安排计划属于分派问题，常用0-1变量表示分派的决策变量，根据本题的特点现在把分派问题视为抽屉问题。每场会议配给L个抽屉，每组分一个，每个抽屉分为N个空格（第1至第N号），每位代表的编号放入空格。如果空格处有对应的编号则就是1，如果没有就是0.即根据以上的分法我们可以用由组成的矩阵来表示开会时代表分布的具体情况。令，这表示第k场第j组的与会代表的分布情况。每场会的具体安排由矩阵排列如下：1、建立目标函数基于计算过程中会遇到一个行向量与自己的转置相乘情况，运算的结果不仅对于我们的模型中无效，还会对计算情况有着较大的影响，我们先规定在计算中根据要求每个小组的人数基本均衡，使得尽可能让任意两个来自不同地区的委员之间都有见面交流的机会，分两部分来描述：1、会议安排应使任意两个代表在整个会议中见面的次数平均2、不同场会议在同一小组中一起开会的代表最少，最好代表之间都可以见面。1、为了控制在不同场会议在同一小组中一起开会的代表数目并控制任意两个代表在整个会议中见面的次数，随机抽取两位代表，解出彼此在同组同时开会见面的次数见面次数采用0-1决策变量来表示：表示第s号代表与第t号代表在M场会议中相遇的总次数.基于运算方便的目的，列出两个代表相遇的矩阵Q如下：其中 计算出全部的和，求解得所有代表的相遇次数，考虑到代表彼此相遇的单个差异的不明显性，我们把放大，再对进行求和，设值等于2，使用矩阵的Frobenius范数达到放大之间的差异的目的，既考虑到了全局相遇次数的同时也考虑到了单个相遇次数的差异，第一个目标函数建立如下：2、 对于，其弱点有：当同一批人分别处于两场会议的某两组时，且在接下来的会议中会完全打乱分配，并尽可能弥补开始相遇次数增大的缺陷，保持成员见面的次数个别差异很小时，使用不能充分控制住。因此这就需要我们再建立了一个目标函数来克服此弱点。对于整个会议中任意抽取出的两个讨论组，称在这两个讨论组中都出现的代表称为这两个组的共同成员。第k场第i组与第t场第j组的共同成员个数为. 我们用矩阵来排列这些数：A是一个的矩阵，其中A的对角线上的方块是第k段会议段内各组的共同成员，其非对角线上的元素一定为0，而其对角线上的元素在上文中已经提到为无效量，故不计算A对角线方块中的元素，k=1,2,M.A中每个元素为整个会议中任意两组（可以分别属于不同段）的共同成员个数。如果出现上一段提出的问题，那么A中元素的大小（除去对角线方块中的元素）将会出现明显的不平均。如果让A中对角线方块以外所有元素的尽可能平均的话，那么会议中任一组与任何该组所属的段以外的组的共同成员数量将会均匀分布。于是，成员间自发组成的小组总在同一个讨论组中出现的现象将会得到遏制，与会成员将会尽可能平均分配。类似上一个目标函数，为了达到描述中元素的平均程度的目的，可以使用矩阵的Frobenius范数。在此情况下，可以再次建立一个目标函数： 其中为权系数），为总的目标函数。2、约束条件利用已知题目条件设出相应的模型约束条件：（1） 在每一场会议中每个代表只能分入一个组里（2） 易知不同组间开会代表应该尽量相等，才可以使得相见的次数尽可能少，所以（3） 在具体计算时，相遇代表次数须在一个范围，即.（4） 类似地我们对考虑，共同成员个数也要在一个有意义的范围内，即.M-1.五、模型的求解1、详细求解方案使用MATLAB对该模型求解。模型变量总数为N，对于每个变量来说，取值范围为0-1，如果N取值较大时，求解大规模的数据时若使用穷举法，会使总的计算步骤较复杂。在可行方法中，采用迭代法：可行初始解求解-可行解的随机一个解-局部优化-全局优化从而得到全局最优解的四步求解的方法，简化计算步骤。使用线性规划方法可以对模型进行求解，显然，最优解的求解必须限定在目标函数可行域范围内。（1）初始解的计算在对可行初始值的计算时，基于一场会议中一人只能出席一组会议的情况，在人员的充分混合方面就暂不考虑，于是一组固定的可行初始解便被计算出来了。（2）对局部可行解优化我们只考虑其中的几场会议，在有限步的循环之后，将见面次数高的人数降低。通过对见面次数的进一步集中，达到使会议中见面次数频繁的人员减少或者保持不变的目的，此过程中初始解应该随机变换，于是一组更优的可行解便被计算出来，优化了局部变换效果。（3）全局优化局部优化得出的可行解X集合为一个最优解的域，考虑每场会议的人员安排的时候，应限定在约束条件下，使用随机变换的方法，可以解出符合条件的可行解X，基于对目标函数F(X)和F(X)的大小判断，在F(X)较小的情况下进行迭代，算出最优解。具体流程图如下：局部优化可行解全局优化得到最优解随机产生一组可行解固定初始解具体MATLAB程序见附录1，具体运行结果见附录2以下是通过优化后对问题三统计所得的一组结果：第一组第二组第三组第四组第五组第六组第七组第一段1、6、8、22、297、14、21、28、3513、15、20、27、344、11、18、25、323、10、17、24、315、12、19、26、332、9、16、23、30第二段2、3、13、14、351、11、12、22、3210、26、29、30、317、8、21、23、345、6、16、19、209、24、25、27、284、15、17、18、33第三段4、10、12、17、245、13、30、31、3411、25、28、32、339、16、20、26、271、2、15、18、217、8、22、23、293、6、14、19、35第四段1、4、6、9、14、24、25、313、7、11、16、17、21、28、29、338、10、15、18、19、23、27、32、342、5、12、13、20、22、26、30、35第五段2、5、9、14、17、23、28、32、341、7、10、15、19、24、26、314、8、11、16、20、21、27、29、353、6、12、13、18、22、25、30、33第六段4、5、10、16、17、21、25、32、342、8、11、13、18、23、26、31、331、7、12、14、19、24、27、293、6、9、15、20、22、28、30、31第七段2、8、11、19、24、27、30、334、5、12、15、18、21、25、31、351、6、10、13、20、23、28、29、34、3、7、9、14、16、17、22、26、32六、模型检验（1） 检验公共成员数目：计算出公共成员的最大数4，出现的次数为14次可见公共成员是一个很理想的数据，满足充分交叉混合的第二个函数要求说明本次分组是合理的分组。（2） 对成员间的相遇次数进行检验：以下是这次安排的成员相遇次数结果：相遇次数012345计算机运行结果1362341695450根据以上的结果分析，此次分组是相当理想的，大部分相见次数都在0次、1次和2次，没有人相遇四次以上，且只有5个人相遇4次，对于这样的分组在很大程度上已经满足要求。总结：通过以上分析我们可知本次安排符合我们提出的模型假设，故对于此次安排是符合要求的。七、模型的优点与缺点我们的模型优点有：第一，我们的模型具有明显的整体性，变量已被控制到最小的7个矩阵。第二，模型运用比较灵活，可以适用于开会董事人数是任意的，开会的组数是任意的，模型推广很方便。第三，程序的运算时间短每次运行只需要50秒左右。第四，模型对初值要求不高，因为在程序运行前我们先通过一段局部最优解的计算，得到相对满意的初值，然后再进行全局的最优解的查找。模型的缺点有如下两个方面：第一，模型的运算完全通过矩阵运算，这需要对矩阵运算比较了解的人，才会比较快看懂模型的运算。第二，模型在运算过程中有涉及到概率问题，所以在第一次运行程序时可能得到的结果并不是很优，需要进行多次运算，比较结果可以得到最优化值。八、模型推广我们的模型以及求解过程对董事的总人数、在职董事所占的比例、分组组数、会议的段数以及参与董事的层次均没有特别的要求，因此，我们的模型可以推广到用于多种分配要求的会议分配。根据模型建立起来的程序的初始解计算方法具有一般性，其思路是上午、下午各指定一段人员的安排方法，再搜索出满足要求的其他段的人员安排方法，这个初始解的人员混合不均匀，需要从它的邻域内搜索出满足条件的更优解，通过局部优化算法和全局优化算法可以找出满足条件的更优解。此算法的目标函数建立同样具有一般性，只要改变参数，就可以建立起优化全局的目标函数 通过结果可以得到我们的模型可以适用于m个董事，分n组，k段的开会安排，模型教灵活模型的推广程度较好。九、参考文献1 施政. 杨辉. 曹瀚. 多次分组会议的最佳混合方案. 数学的实践与认识. 27(4)：335-347. 1997年2 姜启源. 会议分组安排. 数学中国社区网/mcm/faq.php?from=notice&action=grouppermission. 2010.5.043 孙玺菁. 多次分组会议安排的最佳混合方案. /?AllSho w1-%CA%FD%C4%A3%CD%F804/. 2010.5.08十、附录附录1%求初始可行解clc,clearA1=eye(7,7); X1=A1;A1;A1;A1;A1; P1=X1;t=0;while t2X=zeros(37,5);c11=zeros(1,5);c1=zeros(1,5);count=0;for m=1:15tag15=0;for n=1:5if P1(m,n)=0if c11(n)2&tag15=0&count4X(m,n)=1;tag15=1;c15(n)=c15(n)+1;c1(n)=c1(n)+1;if c15(n)=2count=count+1;endelseif c15(n)1&tag15=0X(m,n)=1;tag15=1;c15(n)=c15(n)+1;c1(n)=c1(n)+1;endendendendfor m=16:37tag16=0;for n=1:7if P1(m,n)=0if c1(n)7&tag16=0X(m,n)=1;tag16=1;c1(n)=c1(n)+1;elseX(m,n)=0;endelseX(m,n)=0;endendendif t=1|t=0Y=X for m=16:37if P1(m,7)=0X(m,:)=Y(37,:);X(37,:)=Y(m,:);X(m,5)=1;breakendendendif t=0X2=X;elseX3=X;endP1=P1+X;t=t+1;endif t=0X5=Y;elseif t=1endX2(37,5)=0;X2(37,5)=1;X3(37,5)=1;save chujie X1 X2 X3 X4 X5%求解局部优化的可行解load jieQ1=X1*X1-eye(37,37);Q2=X2*X2-eye(37,37);Q3=X3*X3-eye(37,37);Q4=X4*X4-eye(37,37);Q5=X5*X5-eye(37,37);Q6=Q1+Q2+Q3+Q5;Q=Q6+Q4; QQ=ones(37);for A=1:7 for t=0:5 if t=0 X=X4 end if t=1 X=X5 end for w=1:30 for n=1:4 M=QQ(1,:); for m=1:37 if X(m,n)=1 for i=1:37 if Q(m,i)3&n4)|(m3&j4)|(itffor k=1:ky=randperm(15);for m=1:15X11(m,:)=X1(y(m),:);X22(m,:)=X2(y(m),:);X33(m,:)=X3(y(m),:);endz=randperm(24);z=z+16*ones(1,24);for m=12:35X11(m,:)=X1(z(m-16),:);X22(m,:)=X2(z(m-16),:);X33(m,:)=X3(z(m-16),:);endp=randperm(5);for m=1:5X11(:,m)=X1(:,p(m);X22(:,m)=X2(:,p(m);X33(:,m)=X3(:,p(m);endif fffX1=X11;X2=X22;X3=X33;X4=X44;X5=X55;f=ffendt=0.87*t;endendtoc;l=tocX1,X2,X3,X4,X5save jie X1 X2 X3 X4 X5 %将结果保留在jie中 %求解相遇次数load zhiQ1=X1*X1-eye(37,37);Q2=X2*X2-eye(37,37);Q3=X3*X3-eye(37,37);Q4=X4*X4-eye(37,37);Q5=X5*X5-eye(37,37);Q_sum=Q1+Q2+Q3+Q4+Q5;Q_sum1=Q_sum+eye(37,37);M=Q_sum1=zeros(37,37);count=sum(sum(M);count0=0;count1=0;count2=0;count3=0;count4=0;count5=0;for m=1:37for n=1:37if Q_sum(m,n)=0count0=count0+1;elseif Q_sum(m,n)=1count1=count1+1;elseif Q_sum(m,n)=2count2=count2+1;elseif Q_sum(m,n)=3count3=count3+1;elseif Q_sum(m,n)=4count4=count4+1;elseif Q_sum(m,n)=5count5=count5+1;endend(count0-29)/2,count1/2,count2/2,count3/2,count4/2,count5/2附录3X1 = 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0X2 = 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0X3 = 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1X4 = 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1X5 = 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0X6 = 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0