数学建模会议分组问题

1、会议分组问题摘要本文解决会议分组问题，即在会议次数以及参会人数确定的情况下求取不同地区之间最大的见面概率的会议安排方式，通过设置相应参数，逐步建立数学模型，并采用编程进行计算，并最终确定会议人员参加会议的分组方案。下面将分别对三个问题进行阐述： 问题1是已知有名代表参加会议，要分个场次，每场会议中有个小组，先对数据进行了矩阵化处理，其中引入常值元素来区分不同地区的代表，以l×n的矩阵表示每个人在某一场的出席情况，以此建立非线性整数变量规划模型。为了达到尽可能使来自不同地区的代表能有见面交流机会的目的，本文以每组代表人数基本均衡、每个会议每个代表有且只能在一个小组内为约束条件，根据m个

2、矩阵的加和等一系列运算的结果，得到m场会议之后与会人员的见面情况，从而进行优化，最终确立出最优的分组方案。针对问题2，本文通过建立分组矩阵、开会矩阵，制定约束条件，构造相遇矩阵以及构造异地代表是否见面函数，逐步建立最终的数学模型。但是用lingo计算大量数据的非线性模型运行时间太长，无法获得运算结果（超过5个小时），因此采用分部计算的形式来求解此模型，也就是一共有次会议，须经过多次迭代，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，上一次已经会面的代表假设为同一地区，则这次计算常值系数，只计算未见面的代表会见面次数的最大值，迭代完毕之后将次结果综合考虑，并最后得到模型的最优方

3、案。针对问题3，将问题1中的、分别取做8、5、5，采用问题（1）所建立的模型以及问题2设计的算法，运行程序，得到的分配结果如下：表2 会议的分组方案第一组第二组第三组第四组第五组第一次2、874、513、6第二次514、63、82、7第三次3、741、82、65第四次74、82、631、5第五次41、673、82关键词：会议分组；矩阵分析；迭代运算；整数规划；约束条件1、 问题的重述 会议分组是一个很实际的问题，目前国内外许多重要会议都是以分组形式进行研讨，以便充分交流、沟通。本文是将相应的参数进行了设置，参会代表n名，m个场次，每场会议l个小组，并且要求每个小组的人数基本均衡。本文要以使得尽

4、可能让任意两个来自不同地区的代表之间都有见面交流的机会为目的，建立数学模型，并设计求解上述分组模型的有效算法。同时，设置一些具体数值对已经建立的模型以及算法进行验算，即、分别取做37、5、5，根据问题1所建立的模型以及问题2设计的算法，给出5场会议的每一场各个组中具体有哪些代表参加的安排方案。二、问题假设1、每场次，每个专家都会参加，没有人缺席。2、每次会议对于专家的吸引力相同。3、每个会议每个代表有且只能在一个小组内。三、符号说明表一 符号说明在第次会议中的第组中第次会议分组矩阵和是否在第次会议分在同一组第次会议开会矩阵相遇矩阵所有会议中和是否相遇异地矩阵和是否来自同一地区会议的场次数代表总

5、数分组总数异地代表会面总数异地代表是否见面四、模型建立及求解模型建立第次会议的分组矩阵为其中的取值为0或1，表示代表在第次会议中的第组中，表示表示代表不在第次会议中的第组中，由于在每次会议中每个人只能被分到一个组内，则满足如下关系：又由于要求每组代表的人数尽量均匀，满足如下关系：构造第次会议开会矩阵在第次会议中，代表和代表分在同一组时，否则，为的单位阵。次会议中代表的会面情况可表示为其中的元素为表示代表和代表分在同一组的次数。构造相遇矩阵其中，表示代表和代表曾被分到一个组内，否则根据已知条件构造异地矩阵，其中表示代表和代表来自不同地区，否则。构造异地代表是否见面函数其中，表示不同地区的代表和曾

6、被分到一个组内，否则。使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会，综上建立的非线性整数变量规划模型为模型求解考虑到模型中有变量相乘的形式，用计算运行时间比较长，因此可以采用分部计算来求解模型。即就是一共有次会议，可以迭代次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新异地矩阵，将已经会面的代表和设为同一地区，只计算未见面的代表会面次数的最大值，迭代完毕之后将次结果综合考虑，便得到模型的最优方案。其计算过程如下：步骤1：设置初值步骤2：第一次迭代，计算第一次会议代表的会面情况，使得：且满足如下约束： 步骤3：重复步骤2，计算第二次会议代表的会面情况，以此类推，第次迭代

7、为由步骤3求得第次会议代表的会面情况步骤4：得出第个代表和第个代表的会面情况模型检验将、分别取做8、5、5，采运行程序下面以表格中前8个代表分为5个小组5次会议来说明模型的正确性。表2 会议的分组方案第一组第二组第三组第四组第五组第一次2、874、513、6第二次514、63、82、7第三次3、741、82、65第四次74、82、631、5第五次41、673、825、 结论本文综合考虑三个问题以及其内部数学关系，逐步深入地通过建立分组矩阵、开会矩阵，制定约束条件，构造相遇矩阵以及构造异地代表是否见面函数，逐步建立最终的数学模型。但是用lingo计算大量数据的非线性模型运行时间太长，无法获得运算

8、结果，因此采用分部计算的形式，逐步迭代来进行模型求解（程序均为自行编写，迭代的输出结果详见附录），故将问题1中的、（分别取做37、5、5）取为8、5、5，从而验证了算法的正确性，并得到最终的会议安排方案。参考文献1王沫然，matlab与科学计算，电子工业出版社，第三版2同济大学数学系，线性代数，高等教育出版社，第五版3附录lingo代码model:sets:peo/r1.r8/;meet/m1/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(

9、link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1

10、1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1;enddataendmodel:sets:peo/r1.r8/;meet/m2/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin

11、(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0

12、 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1;enddataendmodel:sets:peo/r1.r8/;meet/m3/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(

13、k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1

14、0 1 1 0 0 0 1 1 0 0 1 1 1 1 1;enddataendmodel:sets:peo/r1.r8/;meet/m4/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum

15、(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1;enddataendmod

16、el:sets:peo/r1.r8/;meet/m5/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(gro

17、up(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1;enddataend输出结果第一次迭代 local optimal solution found. object

18、ive value: 7.000000 objective bound: 7.000000 infeasibilities: 0.000000 extended solver steps: 12 total solver iterations: 695第二次迭代 local optimal solution found. objective value: 6.000000 objective bound: 6.000000 infeasibilities: 0.000000 extended solver steps: 11 total solver iterations: 785第三次迭代

19、local optimal solution found. objective value: 5.000000 objective bound: 5.000000 infeasibilities: 0.000000 extended solver steps: 7 total solver iterations: 545第四次迭代 local optimal solution found. objective value: 4.000000 objective bound: 4.000000 infeasibilities: 0.000000 extended solver steps: 8

20、total solver iterations: 916 第五次迭代 local optimal solution found. objective value: 5.000000 objective bound: 5.000000 infeasibilities: 0.000000 extended solver steps: 13 total solver iterations: 1049 variable value y( r1, r1) 0.000000 y( r1, r2) 0.000000 y( r1, r3) 0.000000 y( r1, r4) 0.000000 y( r1,

21、 r5) 0.000000 y( r1, r6) 1.000000 y( r1, r7) 0.000000 y( r1, r8) 0.000000 y( r2, r1) 0.000000 y( r2, r2) 0.000000 y( r2, r3) 0.000000 y( r2, r4) 0.000000 y( r2, r5) 1.000000 y( r2, r6) 0.000000 y( r2, r7) 0.000000 y( r2, r8) 0.000000 y( r3, r1) 0.000000 y( r3, r2) 0.000000 y( r3, r3) 0.000000 y( r3,

22、 r4) 0.000000 y( r3, r5) 0.000000 y( r3, r6) 0.000000 y( r3, r7) 0.000000 y( r3, r8) 0.000000 y( r4, r1) 0.000000 y( r4, r2) 0.000000 y( r4, r3) 0.000000 y( r4, r4) 0.000000 y( r4, r5) 0.000000 y( r4, r6) 0.000000 y( r4, r7) 0.000000 y( r4, r8) 0.000000 y( r5, r1) 0.000000 y( r5, r2) 1.000000 y( r5,

23、 r3) 0.000000 y( r5, r4) 0.000000 y( r5, r5) 0.000000 y( r5, r6) 0.000000 y( r5, r7) 0.000000 y( r5, r8) 0.000000 y( r6, r1) 1.000000 y( r6, r2) 0.000000 y( r6, r3) 0.000000 y( r6, r4) 0.000000 y( r6, r5) 0.000000 y( r6, r6) 0.000000 y( r6, r7) 0.000000 y( r6, r8) 0.000000 y( r7, r1) 0.000000 y( r7,

24、 r2) 0.000000 y( r7, r3) 0.000000 y( r7, r4) 0.000000 y( r7, r5) 0.000000 y( r7, r6) 0.000000 y( r7, r7) 0.000000 y( r7, r8) 0.000000 y( r8, r1) 0.000000 y( r8, r2) 0.000000 y( r8, r3) 0.000000 y( r8, r4) 0.000000 y( r8, r5) 0.000000 y( r8, r6) 0.000000 y( r8, r7) 0.000000 y( r8, r8) 1.000000 s( r1,

25、 r1) 0.000000 s( r1, r2) 0.000000 s( r1, r3) 0.000000 s( r1, r4) 0.000000 s( r1, r5) 0.000000 s( r1, r6) 1.000000 s( r1, r7) 1.000000 s( r1, r8) 0.000000 s( r2, r1) 0.000000 s( r2, r2) 0.000000 s( r2, r3) 0.000000 s( r2, r4) 0.000000 s( r2, r5) 1.000000 s( r2, r6) 0.000000 s( r2, r7) 0.000000 s( r2,

26、 r8) 0.000000 s( r3, r1) 0.000000 s( r3, r2) 0.000000 s( r3, r3) 0.000000 s( r3, r4) 0.000000 s( r3, r5) 1.000000 s( r3, r6) 0.000000 s( r3, r7) 0.000000 s( r3, r8) 0.000000 s( r4, r1) 0.000000 s( r4, r2) 0.000000 s( r4, r3) 0.000000 s( r4, r4) 0.000000 s( r4, r5) 0.000000 s( r4, r6) 0.000000 s( r4,

27、 r7) 1.000000 s( r4, r8) 0.000000 s( r5, r1) 0.000000 s( r5, r2) 1.000000 s( r5, r3) 1.000000 s( r5, r4) 0.000000 s( r5, r5) 0.000000 s( r5, r6) 0.000000 s( r5, r7) 0.000000 s( r5, r8) 1.000000 s( r6, r1) 1.000000 s( r6, r2) 0.000000 s( r6, r3) 0.000000 s( r6, r4) 0.000000 s( r6, r5) 0.000000 s( r6,

28、 r6) 0.000000 s( r6, r7) 0.000000 s( r6, r8) 1.000000 s( r7, r1) 1.000000 s( r7, r2) 0.000000 s( r7, r3) 0.000000 s( r7, r4) 1.000000 s( r7, r5) 0.000000 s( r7, r6) 0.000000 s( r7, r7) 0.000000 s( r7, r8) 1.000000 s( r8, r1) 0.000000 s( r8, r2) 0.000000 s( r8, r3) 0.000000 s( r8, r4) 0.000000 s( r8, r5) 1.000000 s( r8, r6) 1.000000 s( r8, r7) 1.000000 s( r8, r8) 1.000000 x( m5, r1, g1) 0.000000 x( m5, r1, g2) 1.000000 x( m5, r1, g3) 0.000000 x( m5, r1, g4) 0.000000 x( m5, r1, g5) 0.