多次分组会议安排的最佳混合方案

多次分组会议安排的最佳混合方案多次分组会议安排的最佳混合方案孙玺菁(数学与信息学院数学与应用数学专业00级本3班)摘要针对文1中的多次分组会议安排问题，采用加权系数将多目标函数归结为单一的目标函数，同时采用分组矩阵作为决策变量，大量减少了模型中的决策变量的个数，根据约束条件设计算法求出该模型的一个初始可行解。通过置换初始解相应的行向量与列向量的位置，得到该初始可行解的一个邻近解，进而得到该初始可行解的一个邻域。采用模拟退火算法，在全局范围内对Metropolis算法进行迭代，最终可以得到该模型的一个较为满意的解。关键词：分组矩阵；相遇矩阵；组合优化；模拟退火算法；Metropolis过程1 引言在讨论重要问题的时候，特别是长远规划的问题，越来越流行的一种做法是召开小组会议，人们相信全体会议会使讨论失去活力，而且权威人士通常将会控制和直接影响讨论。这样，在举行全体会议之前，委员将以小组的形式来讨论问题。这些比较小的小组仍有被权威人士控制的危险。为了减少这种危险，通常将会议安排为几个场次，每场次中每个开会小组由不同的人混合组成。Tostal公司将兴趣行一个有29个委员参加的会议，其中9个委员是公司成员。这次会议将开一整天，上午分三场，下午分四场，每场45分钟，开会时间从上午9：00到下午4：00，中午安排午餐，上午的每一场分六个小组开会，每个小组由公司派的六名资深官员之一做组长，这六名资深官员中没有一个是与会委员，并且他们不参加下午的会议，下午每场次分为四个小组开会。会议的安排要满足以下的两个要求：(1)上午的开会场次中，不能有一个委员两次参加由同一个资深官员主持的小组会议。(2)不允许同一个场次中的讨论小组的公司委员数不合比例。请给出9个公司委员(编号1-9)非公司委员(编号20-29)以及资深官员的一张安排表，并且说明是如何满足上述的两个要求的1。2 模型分析2.1 假设条件(1)每种类型的与会委员的地位是相同的。(2)与会委员坚决服从会议组织者的安排，不存在因人员的主观因素影响分组的情况。(3)会议一旦开始，在结束之前与会委员不允许变动。(4)各小组与会人数平均，即上午六组的人数为：5,5，5,5，5,4；下午四组的人数为：7,7，7,8提出假设(4)的依据4问题要求模型给出的分组方案应使与会委员混合的最好，并且在每个场次中保证委员们应在尽可能相互认识的基础上重复见面的次数尽可能平均并且尽量的小。假设每个委员与其他委员在开会小组中都有相同的见面次数，同时第场会议中第个小组的人数为在本组会议中任意一个人在该小组所见的人数为，因而该小组个人所见的人数之和为，则对全天所有的场次所有的小组会议来说，所有成员所见人数总和为若全天会议结束后每一个委员和其他任何一个委员见面的次数均为次，则全天所有成员所见人数之和又可以写成。则有等式成立整理得由Cauchy不等式：当时，“=”成立。在本式中，所以即在实际中，的取值越小越好，因此当小组间人数相差的人数越小时，的取值越小，而各组会议人数平均分配时相差最小，即上午5,5，5,5，5,4；下午7,7，7,8。将上述数据带入，得到由此可得，委员之间要充分见面，他们任意两个人见面的次数介于1和2之间。2.2 变量及符号说明X：决策变量，其中元素表示在第j场会议中，委员I在第k组。P：分组矩阵，表示第j场会议的分组矩阵。Q：相遇矩阵，表示第j场会议的相遇矩阵。：总的相遇矩阵，。的转换形式。：目标函数，定义为中除了主对角线上的元素外，零元素的个数。即任意两个与会委员没有见面的次数。：目标函数，定义为的Frobenius范数的平方。：每个委员与其他委员的相同的见面次数。2.3 对于分组和相遇的数学描述12.3.1 分组矩阵和相遇矩阵Def令与会委员集合为，将全部的委员分为组，定义分组矩阵为其中定义相遇矩阵为其中2.3.2 分组矩阵和相遇矩阵的关系定理TH若P为分组矩阵，则其对应的相遇矩阵为单位矩阵。证明 对每次只能分在一个组中，即P的每一行中只有一个元素为1，其余的元素全部为0。由矩阵可得(1)若与不同时为1，即与不同在组，则(2)若与同时为1，即与同在组，则满足相遇矩阵的定义。所以。2.4 约束条件1首先，定义变量表示第个人在第场次的会议中分在第组，则其中表示9个公司的委员，表示20个非公司的委员。表示全天开了7场次的会议。表示上午的三个场次的会议中，每个场次的会议中，分为6个小组，表示下午的四个场次的会议中，每个场次的会议分为4个小组。对于每个场次的分组来说，都有分组矩阵和相遇矩阵，其中其中或者4。由题目给定的要求，可以得到如下的限制条件(1)每一次分组中，每个与会委员唯一的分在一组即(2)每次分组时，每组中的公司委员应成比例，按照各小组人数均分的原则，有(3)各小组的人数平均分配，有(4)上午的每个场次的会议中，6个小组各有一名资深官员主持，每个与会委员不能与任何一个资深官员重复见面，对下午的会议没有这个要求，则 (5)只能取0或者1。2.5 目标函数7次分组会议完成以后，委员1-29之间相互见面的次数可由如下的公式表示为总的相遇矩阵。其中2.5.1 目标函数的给出要考虑到与会委员之间的充分交流，要尽量保证每个与会委员之间都有见面的机会，即在中除了主对角线上的元素外，0元素的个数应当尽可能的少，先对进行处理，得到。令得到则目标函数I为最小。2.5.2 目标函数的给出考虑到任意两个委员重复见面的次数应尽可能的相同，通过可以放大不同委员与其他的委员见面次数上的单个差异，的取值越大，放大的程度就越大。不仅考虑到了单个差异的灵敏性，而且也考虑到了相见次数的全面性因素。在本模型中，取定这正是矩阵的Frobenius范数，即。因此得到目标函数为。2.5.3 总目标函数的得到与处于不同的标准，考虑到两个目标函数有着不同的优先级和数量级，对两个目标函数加以不同的权系数，于是得到总的目标函数为，其中为权系数，取。3 模型的建立综合上述分析，可以得到如下的模型目标函数约束条件 只能0或者14 模型的求解4.1 寻找问题的可行解空间对于模型中的每个决策变量只能0或者1，因此可以看作是多目标0-1整数规划问题，其变量的个数多达个，倘若使用穷兴趣法进行搜索，奔4的计算机完成如此大规模的运算也是非常困难的。考虑到模型中决策变量的特点，采用每一场次会议的分组矩阵作为变量，决策变量的个数将会大大降低，减少到7个。该模型可以看作是组合优化的问题。组合优化问题是在给定的约束条件下，求目标函数的最优值(在本模型中为求目标函数的最小值)的问题。组合优化问题的一个实例可以表示为一个对偶，其中解空间为可行解集，目标函数是一个映射，定义为。设是组合优化问题的一个实例，则一个邻域结构是一个映射，其中是S的幂集合，即S的所有解集的集合，其含义是对每个解，有一个解的集合这些解在某种意义上是邻近的，称为的邻域，每个称为的一个邻近解。在求解本模型的过程中，一种可行的思路就是在一个给定的初解的基础上，得到目标函数的初值，然后在该解的邻域内找到一个邻近解，当的时候，用替换，重复替换，最终可以得到一个全局最优解2。考虑到分组矩阵的每一行中只能有一个元素为1，其余的元素全部为0，对于第一场和第四场的分组矩阵来说显然这是满足约束条件的，9个公司的委员成比例分配，29个委员在开会小组中人数均分，在上午的开会场次中，要求每一位委员与任何一位资深官员不能重复见面，即任何一个委员，不能在上午的会议中重复出现在一个组中，设计算法将29个委员依次手稿到各组中，在插入之前算法将结合当前的分组情况，根据约束条件找出一个满足约束条件的列下标最小的位置供该成员插入。如此，可以得到一个满足的(程序见附录中的程序1)。对于下午的四个场次的会议则没有这个要求，即每位委员可以重复出现在不同场次的同一个组中，对于的前9行重新排列，10-29行重新排列，就可以得到满足条件的不同场次的分组矩阵(程序见附录中程序1)。对于初解来说，任意同时变换的前9行，10-29行中任意行的位置，就可以得到一个满足约束条件的邻近解和该初始解的邻域。4.2 利用模拟退火算法求得全局最优解模拟退火算法(SA)属于一种通用的随即搜索算法。其基本的思想来源泉于固体的退火过程，是求解大规模组合优化问题的承受机性方法，以优化问题的求解与物理退火过程的相似性为基础，利用Metropolis算法，适当的控制温度的下降过程，实现模拟退火从而达到求解全局优化问题的目的3。模拟退火算法的基本原理如下23(1)给定初始状态X，选择合适的退火策略，(如温度下降的规律给定初始温度以足够高的值。(2)在X的邻域内选择，并计算(其中F(X)为目标函数)。(3)若则接受为下一次模拟的初始状态，否则算接受新点的概率，产生0,1区间上均匀分布的伪随即数若则接受新点做下一次模拟的初始状态，否则仍取原点作为下一次模拟的初始状态。(4)重复(2)，(3)步，直至系统达到平衡状态(实际上是重复到预先给定的状态即可)。(5)按第一步给定的退火策略下降，重复(2)-(4)步，直至或某一预定的低温。其中(1)-(3)步即为Metropolis过程。当系统温度足够低时，就认为达到了全局最优状态。在模拟退火的优化算法中，降温的方式对算法有很大的影响，如果温度下降的过快，可能丢失极值点，如果温度下降的过慢，算法的收敛速度大大降低。在理论上温度的下降不应快于但是在实际应用的过程中一般用公式其中降温系数。得到如下的结果(程序见附录程序4)。上午的安排方案第一组第二组第三组第四组第五组第六组第一场511,17,23,29612,18,243,915,21,27410,16,22,281,713,19,252,814,20,26第二场822,24,25,26227,28,295,614,17,18719,20,21,232,310,11,121,413,15,16第三场721,27,28310,22,23,261,213,19,20817,18,24,254,514,15,166,911,12,29下午的安排方案第一组第二组第三组第四组第四场4,812,15,20,22,26,291,511,14,19,21,282,6，913,17,24,253,710,16,18,23,27第五场4,6，914,19,22,26,291,712,13,20,21,283,811,16,18,23,252,510,15,17,24,27第六场3,510,13,20,21,271,612,14,19,23,262,811,16,18,24,28,294,7，915,17,22,25第七场3,610,13,17,24,261,512,15,20,21,252,7，914,18,23,28,294,811,16,19,22,27此程序用时5分种左右，其中互相见面次数的统计如下相互见面次数012345模拟退火算法941551064182见面次数大部分集中在1次和2次。5 模型的推广在建立模型的过程中，对于参数没有特殊的要求，如会员的总数，会议的场次，会员的类型，参与的层次，所以此模型有很大的推广性，可以给出一个更为一般情况的模型。考虑如下情况的会议安排，在本届会议中，有类会员，整修会议被分成个阶段，在第个阶段中有个场次，且每一个场次又个小组组成。会议满足如下的安排要求：(1) 在每一个场次中，每一个会员仅能被安排在一个小组中。(2)在任意的场次中，类型的会员要在每个小组中平衡的分布。(3)整修安排情况要保持平衡。(4)在第个阶段中，L类型的会员不得超过a次于资深官员见面。假定第种类型的会员有个，会员的总数为，对其从1到进行编号，第个类型的第个会员的编号为整个会议包括各阶段，第个阶段有个场次，记，代表总共的开会场次，在第个阶段的每个场次中有个讨论小组，则得到如下定义的决策变量：依照前文的思想可以建立更为一般的模型，运用前文给出的算法，即可求解。参考文献1施政。杨辉。曹瀚。多次分组会议的最佳混合方案。数学的实践与认识。1997年27(4)：335-3472刘则毅。数学计算技术与Matlab解法(第一版)。北京：科学出版社，2001：335-3373杨浩。模型与算法(第一版)。北京：北方交通大学出版社，2002：208-2164唐洪。任晓峰。杨挺。多次分组会议的最佳混合方案。中国数模网。An Assignment Model for Fruitful DiscussionSun Xijing(Class 3, Grade 2000,School of Math.and Information) In order to solve a practical giving a list of assignment for meeting. This text adopts weighting coefficient to sum up multiobjective function as injective object function and makes discussion matrix as decision variable to decrease the number of decision variable. It designs algorithm basing on constrain condition to work out one initial basic feasible solution of this model, and then get another close solution by transforming the row rectors and the column vectors so that it can get the close field of the initral solution. This text uses the SA algorithm and get a better solution by iterating Metrololis algorithm in global.Keywords: discussion marix; meet matrix; combinatorial optimization; Simulated Annealing algorith; Metropolis process附录程序1 求初解clc,clearA1=eye(6,6);A2=eye(4,4);B1=A1(1:5,:);B2=A2(1,);X1=A1;A1;A1;A1;B1;X4=A2;A2;A2;A2;A2;A2;A2;B2;%以下程序用于求解X2，X3中1-9个决策变量P1=X1;t=0;While t2X=zeros(29,6);c11=zeros(1,6);c1=zeros(1,6);count=0;for m=1:9tag11=0;for n=1:6if P1(m,n)=0if c11(n)2&tag11=0&count3X(m,n)=1;tag11=1;c11(n)=c11(n)+1;c1(n)=c1(n)+1;if c11(n)=2count=count+1;endelseif c11(n)1&tag11=0X(m,n)=1;tag11=1;c11(n)=c11(n)+1;c1(n)=c1(n)+1;endendendend%以下程序用于调整X3中前9行中不满足条件的决策变量ift=1a=sum(X(1:9,:);for m=1:9if a(m)=0b=m;break;endendY=X(1:9,:);for m=1:9kk=0;c=P1(b,:)+Y(m,:);for n=1:6if c(n)=2kk=1;breakendendif kk=0X(b,:)=Y(m,:);X(m,:)=Y(b,:);for n=1:6if P1(m,n)=0X(m,n)=1;breakendendbreakendendend%以下程序用于求解X2，X3中20-29个决策变量for m=10:29tag12=0;for n=1:6if P1(m,n)=0if c1(n)5&tag12=0X(m,n)=1;tag12=1;c1(n)=c1(n)+1;elseX(m,n)=0;endelseX(m,n)=0;endendend%以下程序用于调整X3中20-29个不满足条件的决策变量if t=1Y=Xfor m=10:29if P1(m,6)=0X(m,:)=Y(29,:);X(29,:)=Y(m,:);X(m,6)=1;breakendendendif t=0X2=X;elseX3=X;endP1=P1+X;t=t+1;end%以下程序用以求得满足约束条件的X5，X6，X7；t=0;while ttffor k=1:ky=randperm(9);for m=1:9X11(m,:)=X1(y(m),:);X22(m,:)=X2(y(m),:);X33(m,:)=X3(y(m),:);endz=randperm(20);z=z+9*ones(1,20);for m=10:29X11(m,:)=X1(z(m-9),:);X22(m,:)=X2(z(m-9),:);X33(m,:)=X3(z(m-9),:);endp=randperm(6);for m=1:6X11(:,m)=X1(:,p(m);X22(:,m)=X2(:,p(m);X33(:,m)=X3(:,p(m);endA2=eye(4,4);C4=randperm1(A2);B4=C4(1,:);C5=randperm1(A2);B5=C5(1,:);C6=randperm1(A2);B6=C6(1,:);C7=randperm1(A2);B7=C7(1,:);X44=randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2);B4;X55=randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2);B5;X66=randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2);B6;X77=randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2); randperm1(A2);B7;ff=F(X11,X22,X33,X44,X55,X66,X77);if