2013数学建模会议分组问题

会议分组问题摘要通过对问题的分析，我们确定运用优化的整数规划模型、矩阵理论和置换等方面的知识和技巧。通过矩阵将决策变量和所要求解的目标函数建立联系。在提出模型目标函数的过程中，首先我们提出了代表相遇次数的概念，用矩阵Q表示其任意两个代表的相遇次数，并利用矩阵的Frobenius范数控制了Q中元素的大小及其均匀程度，得到目标函数f(x)，从而求解代表的相遇次数。第一个目标函数设定后，基于f(x)在群体整体换组时不能起到控制作用的问题,决定使用共同成员概念：即任意两组（可以属于不同场次）整个会议中的交集。利用矩阵A，对矩阵的Frobenius范数的运用使群体整体换组现象得到了有效的遏制，对与会者混合程度进行了控制。求解模型时，使用迭代算法，利用线性规划，在目标函数可行域范围内查找最优解可以利用MATLAB软件设计出计算可行初始解-随机产生一个可行解-局部优化-全局优化从而达到全局最优解的三步求解的方法，局部-全局的步骤解出了全局最优解，简化运算步骤的同时提高了结果优化程度，降低对初值的依赖程度，很好的达到了与会者需要充分混合的目的。基于算法的目标函数，因为在建立时具有一般性，若需建立起优化全局的目标函数，只需对参数进行改变。这样一来模型的推广得到了算法上的支持，带来了极大的便利。我们此次建模得到了合适的人员分配结果，达到了建模的目的。关键词：抽屉原理相遇矩阵共同成员Frobenius范数一、问题重述目前，国内外许多重要会议都是以分组形式进行研讨，以便充分交流、沟通。一般地，一个由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）ijkx：0-1决策变量,表示第i位代表有否参加第k场第j组会议；（2）P：开会分组矩阵，表示整次会议每场代表的分组安排，其中kP表示第k场会议的分组矩阵，其行向量jkP表示第k场会议第j组的分组矩阵；（3）Q：相遇矩阵；（4）()fx：目标函数一，用来控制代表相遇次数；（5）()gx：目标函数二，用于控制不同场间组间共同成员个数；（6）()Fx：总的目标函数，综合考虑()fx和()gx的目标函数.2、变量符号数学描述（1）ijk1,j0,.x表示第i位代表参加第k场第组的会议否则（2）12=jkjkjkNjkPxxx，k表示第k段会议，j表示第j组，k=1,2,…,M，j=1,2,…,L,i=1,2,…,N.(3)1k11k21k1k212k22k2k1k2kkxxxxxx=xxxNkNkMMNMMkPPPP(4)111121MLLLMPPPPPPPP（5）1212TTTTLLPPQPPPPPP四、模型建立通过使用（0-1）整数规划来建立该问题的模型。题目要求每个小组的人数基本均衡，使得尽可能让任意两个来自不同地区的委员之间都有见面交流的机会。从这两个要求出发，分别从相遇代表次数和共同成员数目两个角度建立了两个目标函数。再加上题设要求以及模型假设得到的约束条件，完成本模型的建立。具体过程以及模型如下所示。题目要求分组名单安排计划属于分派问题，常用0-1变量表示分派的决策变量，根据本题的特点现在把分派问题视为抽屉问题。每场会议配给L个抽屉，每组分一个，每个抽屉分为N个空格（第1至第N号），每位代表的编号放入空格。如果空格处有对应的编号则ijkx就是1，如果没有就是0.即ijk1,kji,1,2,...,,1,2,...,,1,2,...,0,xiNjLkM第场第组第个空格有编号否则根据以上的分法我们可以用由ijkx组成的矩阵来表示开会时代表分布的具体情况。令12=jkjkjkNjkPxxx，这表示第k场第j组的与会代表的分布情况。每场会的具体安排由矩阵排列如下：1k11k21k1k212k22k2k1k2kkxxxxxx=xxxNkNkMMNMMkPPPP1、建立目标函数基于计算过程中会遇到一个行向量与自己的转置相乘情况，运算的结果不仅对于我们的模型中无效，还会对计算情况有着较大的影响，我们先规定在计算中0,0,1,2,...,,1,2,...,.TTjkjkjkjkPPPPjLkM根据要求每个小组的人数基本均衡，使得尽可能让任意两个来自不同地区的委员之间都有见面交流的机会，分两部分来描述：1、会议安排应使任意两个代表在整个会议中见面的次数平均2、不同场会议在同一小组中一起开会的代表最少，最好代表之间都可以见面。1、为了控制在不同场会议在同一小组中一起开会的代表数目并控制任意两个代表在整个会议中见面的次数，随机抽取两位代表，解出彼此在同组同时开会见面的次数见面次数采用0-1决策变量ijkx来表示：11LMsjktjkjkxx表示第s号代表与第t号代表在M场会议中相遇的总次数.基于运算方便的目的，列出两个代表相遇的矩阵Q如下：12121122=++TTTTTTTLLLstNNLPPQPPPPPPPPPPPqP其中11.LMstsjktjkjkqxx计算出全部stq的和，求解得所有代表的相遇次数，考虑到代表彼此相遇的单个差异的不明显性，我们把lstq放大，再对lstq进行求和，设l值等于2，使用矩阵Q的Frobenius范数达到放大stq之间的差异的目的，既考虑到了全局相遇次数的同时也考虑到了单个相遇次数的差异，第一个目标函数建立如下：11lLLststfxq2、对于()fx，其弱点有：当同一批人分别处于两场会议的某两组时，且在接下来的会议中会完全打乱分配，并尽可能弥补开始相遇次数增大的缺陷，保持成员见面的次数个别差异很小时，使用()fx不能充分控制住。因此这就需要我们再建立了一个目标函数来克服此弱点。对于整个会议中任意抽取出的两个讨论组，称在这两个讨论组中都出现的代表称为这两个组的共同成员。第k场第i组与第t场第j组的共同成员个数为TikjtPP.我们用矩阵来排列这些数：11111111111111111111111111111111111121312TTTTLMLMTTTTLLLLMLMTTTTMLMMMMLMTTTTLMLMLLMMLMLMTTTTMLMPPPPPPPPPPPPPPPPAPPPPPPPPPPPPPPPPPPPPPPPP21222323132333123TTTTMTTTTMTTTTLLLLMPPPPPPPPPPPPPPPPPPPPPPPPA是一个2LM的矩阵，其中A的对角线上的方块TkkPP是第k段会议段内各组的共同成员，其非对角线上的元素一定为0，而其对角线上的元素在上文中已经提到为无效量，故不计算A对角线方块TkkPP中的元素，k=1,2,…,M.A中每个元素为整个会议中任意两组（可以分别属于不同段）的共同成员个数。如果出现上一段提出的问题，那么A中元素的大小（除去对角线方块,1,2,...,TkkPPkM中的元素）将会出现明显的不平均。如果让A中对角线方块,1,2,...,TkkPPkM以外所有元素的尽可能平均的话，那么会议中任一组与任何该组所属的段以外的组的共同成员数量将会均匀分布。于是，成员间自发组成的小组总在同一个讨论组中出现的现象将会得到遏制，与会成员将会尽可能平均分配。类似上一个目标函数，为了达到描述A中元素的平均程度的目的，可以使用矩阵A的Frobenius范数。在此情况下，可以再次建立一个目标函数：2=TikjtktgxPP)()()(21xgxfxF其中2121,,1为权系数），为总的目标函数。2、约束条件利用已知题目条件设出相应的模型约束条件：（1）在每一场会议中每个代表只能分入一个组里11=111,1,2,...,.LjkNjPkM（2）易知不同组间开会代表应该尽量相等，才可以使得相见的次数尽可能少，所以1,2,...,,1,2,,.TjkjkNppjLkML（3）在具体计算时()fx，相遇代表次数须在一个范围，即Mmq.（4）类似地我们对()gx考虑，共同成员个数也要在一个有意义的范围内，即TikjtPP.＜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