数学建模lingo程序解决会议分组问题

答卷编号（参赛学校填写）：

答卷编号（竞赛组委会填写）：

论文题目： F题: 会议分组问题

组 别： 本科生

参赛学校： 东北电力大学

报名序号：

参赛队员信息(必填)：

参赛队员1 参赛队员2 参赛队员3

姓 名 张鹏宁 张学阳 张慧琴 专业班级及学号 电自1011班1009290237 数学101班1009300132 电自1011班1005180129 联系电话 15043269112 15043259842 15143284582

答卷编号（竞赛组委会填写）：

省赛评阅1：省赛评阅2：省赛评阅3：省赛评阅4：省赛评阅5：

评阅情况（省赛评阅专家填写）：

会议分组问题

摘 要

本文针对会议分组这个实际问题，以运筹学最优分配为基础，采用Lingo编程完成了代表参加会议的分组方案。

针对问题（1），已知有N名代表参加会议，要分M个场次，每场会议中有L个小组，先对数据进行了矩阵化处理，其中引入常值元素sij来区分不同地区的代表，为了达到尽可能使来自不同地区的代表能有见面交流机会的目的，以每组代表人数基本均衡、每个会议每个代表有且只能在一个小组内为约束条件，建立非线性整数0?1变量规划模型，从而确立出最优的分组方案。

针对问题（2），考虑到模型中有变量相乘的形式，用Lingo计算大量数据的非线性模型运行时间较长，因此采用分部计算的形式来求解此模型，也就是一共有M次会议，可以迭代G次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，上一次已经会面的代表假设为同一地区，则这次计算常值系数sij?0，只计算未见面的代表会见面次数的最大值，迭代完毕之后将M次结果综合考虑，便得到模型的最优方案。

针对问题（3），将问题（1）中的N、M、L分别取做37、5、5，采用问题（1）所建立的模型以及问题（2）设计的算法，运行Lingo程序，但由于迭代次数过多，本文取N、M、L分别为9、5、5，也即所给表格中前九个代表开5次会议，每次会议分五组，得到的分配结果如下：

第一次 第二次 第三次 第四次 第五次

第一组 1，7 4，9 4，6 2，5 2，8 第二组 2，9 1，5 7，9 6，8 3，7 第三组 3，6 7 1，8 3 1，6 第四组 4，8 2，6 2 4，7 5，9 第五组 5 3，8 3，5 1，9 4 关键词：分组；迭代；优化；非线性

1

1．问题的重述

目前，国内外许多重要会议都是以分组形式进行研讨，以便充分交流、沟通。一般地，一个由N名代表参加的会议，要分为M个场次，每场会议分为L个小组，并且要求每个小组的人数基本均衡。

问题1：请建立分组方案的数学模型，使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会。

问题2：设计求解上述分组模型的有效算法。

问题3：现有一个学术团体要举行由37位专家参加的学术研讨会，每个专家所在地区的信息见表1。会议分5场进行，每场会议又分5个小组，每个小组人数要基本均衡。请根据问题1所建立的模型以及问题2设计的算法，给出5场会议的每一场各个组中有哪些代表参加的安排方案。

2．问题的分析

对于问题一，已知有N名代表参加会议，要分M个场次，每场会议中有L个小组，令xikl表示第i个人在第k次会议中被分到第l个组的可能，xikl的值只能为1或者0，1表示第i个人在第k次会议中被分到第l个组；0表示第i个人在第k次会议中没被分到第l个组。再令bijk表示第i个代表和第j个代表分到第k组的可能，bijk的值也只有1和0,1表示i个代表和第j个代表分到第k组；0表示i个代表和第j个代表未分到第k组。再设一个时令系数sij，当i和j代表是同一个地方时，sij为0；当i和j代表不是同一个地方时，sij为1。bijk是经过判断与sij相乘后得到的数值，用yij表示第i个代表和第j个代表五场会议相遇的次数，当相遇的次数为0时yij的数值为0，当相遇的次数不为0时，yij的数值是1，目标函数是所有的yij相加达到最大时才能尽可能让任意两个来自不同地区的代表之间都有见面交流的机会。

对于问题二，考虑到模型中有变量相乘的形式，用Lingo计算大量数据的非线性模型运行时间比较长，因此可以采用分部计算的形式来求解此模型，也就是一共有M次会议，可以迭代M次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，讲上一次已经会面的代表假设为同一地区，也就是如果第i个代表和第j个代表上一次会面，则这次计算时令系数sij?0，只计算未见面的代表会面次数的最大值，迭代完毕之后将M次结果综合考虑，便得到模型的最优方案。

对于问题三，将问题（1）中的N、M、L分别取做37、5、5，采用问题（1）所建立的模型以及问题（2）设计的算法，运行Lingo程序，但由于迭代次数过多，耗费时间过多，因此本文取N、M、L分别为9、5、5，也即所给表格中前九个代表开5次会议，每次会议分五组，即检验一下程序的可用性。

2

3．符号说明

xilk Ak bilk Bk 编号为i的代表在第k次会议中的第l组中 分组矩阵 代表i和代表j分在同一组的可能 第k次会议相遇矩阵 总的相遇矩阵 目标函数 常值 会议的场次数 分组总数 代表总数 会议的次序 代表i和j是否会过面 B Z sij M L N k zij 4．模型的建立与求解

4．1 问题1的模型建立与求解

表1 第k次会议的安排情况

代表 小组 1 2 …… L 1 2 ? N x11k x21k ? x12k x22k ? …… …… ? x1Lk x2Lk ? xN1k xN2k …… xNLk 3

如上表所示为第k次会议的安排情况，L为分组总数，N为代表总数，其中

xilk的取值为0或1，xilk?1表示编号为i的代表在第k次会议中的第l组中，

xilk?0表示编号为i的代表不在第k次会议中的第l组中，由于在每次会议中每个人只能被分到一个组内，则满足如下关系

?xl?1Lilk?1(i?1,2,?,N)

第k次会议的分组矩阵为

Ak??xilk?N?L (k?1,2,?,M)

又由于要求每组代表的人数尽量均匀，因此还满足如下关系

?N?N?N??x??1 ?ilk?????L?i?1?L?令

TBk?AkAk?I

其中Bk为N?N的对称阵，Bk的元素为

bijk??xilk?xjlk (i,j?1,2,?,N且i?j)

l?1M在第k次会议中，代表i和代表j分在同一组时bilk的值为1，否则为0，I为N?N的单位阵。

M次会议中代表的会面情况可表示为

B??Bk

k?1M其中B的元素为

bij??bijk

k?1M表示代表i和代表j分在同一组的次数。

设地区异同矩阵为S，其元素sij?1表示代表i和代表j来自不同地区，否则

sij?0。 令

??1,bij?0 yij????0,bij?0yij?1表示代表i和代表j曾被分到一个组内，否则yij?0

令

zij?sij?yij

zij?1表示不同地区的代表i和j曾被分到一个组内，否则zij?0 目标函数为：

4

maxZ???ziji?1j?1NN

使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会，综上建立的非线性整数0?1变量规划模型为

maxZ???ziji?1j?1NN

?L??xilk?1?l?1??N?N?N??x?????ilk???1?L???L?i?1?ML ?xilk?xjlk?yij???k?1l?1??zij?sij?yij?x,y,s,z?0或1?ilkijijij??i,j?1,2,?,N,k?1,2,?,M,l?1,2,?,L其中sij由题意定的常值。 4．2 问题2的模型建立与求解

考虑到模型中有变量相乘的形式，用Lingo计算大量数据的非线性模型运行

时间比较长，因此可以采用分部计算的形式来求解此模型，也就是一共有M次会议，可以迭代M次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，讲上一次已经会面的代表假设为同一地区，也就是如果第i个代表和第j个代表上一次会面，则这次计算时令系数sij?0，只计算未见面的代表会面次数的最大值，迭代完毕之后将M次结果综合考虑，便得到模型的最优方案。其计算过程如下：

(1)步骤1：设置初值sij?sij（sij是问题一中的系数，sij?1表示第i个代表和第j个代表不在同一地区）。

(1)步骤2：第一次迭代，计算第一次会议代表的会面情况yij，且满足如下约束

?L??xil1?1(i?1,2?N)?j?1??N?N?N??x?????il1???1??L?i?1?L??L?y(1)?x?x(i,j?1,2?,N)

il1js1?ij?s?1?NN(1)(1)?max(sij?yij)???i?1j?1?步骤3：

5

(2)(1)(1) sij?sij?yij(2)重复步骤2，计算第二次会议代表的会面情况yij，以此类推，第m次迭代为

(m)(m?1)(m?1) sij?sij?yij(m)由步骤2求得第m次会议代表的会面情况yij，且满足约束

?L??xilm?1(i?1,2?N)?j?1??N?N?N??x?????ilm???1??L?i?1?L? ?L?y(m)?x?x(i,j?1,2?,N)?ilmjlm?ijl?1?NN(m)(m)?max(sij?yij)???i?1j?1?第M次迭代为

(M)(M?1)(M?1) sij?sij?yij(M)由步骤二求得第M次会议代表的会面情况yij，满足的约束同上。

步骤四：得出第i个代表和第j个代表的会面情况

(t)(i,j?1,2?N) Yij??yijt?1M其中Yij?0表示第i个代表和第j个代表会过面，每步迭代求解得到的xilk就是第

i个代表第k次会议中的分组情况，xilk?1表示编号为i的代表在第k次会议中的

第l组中。

4．3 问题3的模型建立与求解

将问题（1）中的N、M、L分别取做37、5、5，采用问题（1）所建立的模型以及问题（2）设计的算法，运行Lingo程序，但由于迭代次数过多，本文取N、M、L分别为9、5、5，也即表格中前9个代表开5次会，每次会议分为5个小组，下面以表格中前9个代表分为5个小组5次会议来说明模型的正确性。其中常值矩阵S为

6

?0?0??0??0S??1??1?1?1???100011111?00011111??00011111??00011111?11100011?

?11100011?11100011?11111100??11111100??经计算得到的结果为矩阵C

?0?0??0??0C??3??6?2?4???500036245?00053162??00042631??00014523?54100016?

?32400051?16500014?63215100??21361400??表2 会议的分组方案 会议的分组方案为： 第一次 第二次 第三次 第四次 第五次 第一组 1，7 4，9 4，6 2，5 2，8 第二组 2，9 1，5 7，9 6，8 3，7 第三组 3，6 7 1，8 3 1，6 第四组 4，8 2，6 2 4，7 5，9 第五组 5 3，8 3，5 1，9 4 用图形直观的表示为如下： 1 9

2 3 4 7

8 7 6 图1 代表的见面交流图

5 图中两个数字之间的连线表示两个标号的代表已经见面交流过了，通过上图可直观看出任意两个代表之间没有重复的线并且同一地区的代表不在一个小组内开会，从而不同地区的两个代表尽可能多的见面交流。

5．模型结果的分析与检验

5次会议通过5次迭代，分别计算出每次会议代表会面的情况，其中矩阵S为初始矩阵，sij?1表示参加会议的代表i,j不在同一地区，S为对称矩阵，考虑问题方便只考虑上对角阵，在第一次会议中，9个代表分在5个小组内，经过计算，第二个矩阵C中数值是2的位置表示两个代表分在同一组，2的位置有4个，说明至多有4个代表分在同一组，且数值为2的位置没有出现在矩阵S中数值为0的位置，这与事实相符。

第二次会议中，依旧是9个代表分在5个小组内，结果是数值为3的位置是两个代表分在同一组，数值为3的位置依然是4个，且不会出现在数值为2的位置，因为数值为2的位置表示两个代表已经见过面，以此类推，相应的数字和其位置如矩阵C所示，数字不会重复，且数值均为4，说明是要求的结果，由此可证明模型是正确的。

6．模型的推广与改进方向

1）由于在计算过程中目标函数的矩阵是对称的，计算整体的矩阵迭代的次数会更多，会花费更长的时间，而且计算结果还需除以2，因此可以更改目标函数如下

maxZ???zij

i?1j?i?1N?1N即只需计算矩阵的上对角阵，便得到最终的结果。

2）模型是非线性的，直接计算迭代次数会过多，花费的时间也较长，因此我们可以通过先计算一次会议的会面情况，将会过面的代表当做是同一地区的代表处理，通过更新sij的值来计算下一次会面的情况，在解决问题二中用到了此方法。

7．模型的优缺点

8

优点：

（1）本算法能尽量使来自不同地区的代表会面。

（2）运用了非线性代数求解的方法和Lingo编程，使得处理得到的结果达到最优。 缺点：

人数过多且迭代次数多，导致算法的运行时间大大延长。

参考文献

[1] 姜启源．数学模型（第三版）[M]．北京：高等教育出版社，1999．

[2] 韩中庚．数学建模方法及其应用（第二版）[M]．北京：高等教育出版社，2009． [3] 茆诗松．概率论与数理统计（第二版）．北京：高等教育出版社，2011． [4] 何晓群．多元统计分析（第二版）．北京，中国人民出版社，2010．

9

附 录

附录一 问题三的Lingo源程序

model: sets: peo/r1..r37/; meet/m1..m5/; group/g1..g5/; link(peo,peo):y,s;

encount(meet,peo,group):x; endsets

max=@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))>=7)); @for(meet(I):

@for(group(K):@sum(peo(J):x(I,J,K))<=8)); @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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

10

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1; enddata End

11

本文来源：https://www.bwwdw.com/article/oif2.html