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

会议分组问题
摘要
本文解决会议分组问题,即在会议次数以及参会人数确定的情况下求取不同地区之间最大的见面概率的会议安排方式,通过设置相应参数,逐步建立数学模型,并采用编程进行计算,并最终确定会议人员参加会议的分组方案。下面将分别对三个问题进行阐述:
问题1是已知有名代表参加会议,要分个场次,每场会议中有个小组,先对数据进行了矩阵化处理,其中引入常值元素来区分不同地区的代表,以L×N的矩阵表示每个人在某一场的出席情况,以此建立非线性整数变量规划模型。为了达到尽可能使来自不同地区的代表能有见面交流机会的目的,本文以每组代表人数基本均衡、每个会议每个代表有且只能在一个小组内为约束条件,根据M个矩阵的加和等一系列运算的结果,得到M场会议之后与会人员的见面情况,从而进行优化,最终确立出最优的分组方案。
针对问题2,本文通过建立分组矩阵、开会矩阵,制定约束条件,构造相遇矩阵以及构造异地代表是否见面函数,逐步建立最终的数学模型。但是用lingo计算大量数据的非线性模型运行时间太长,无法获得运算结果(超过5个小时),因此采用分部计算的形式来求解此模型,也就是一共有次会议,须经过多次迭代,每次迭代只计算一次会议的会面情况,每次迭代时更新目标函数的系数,上一次已经会面的代表假设为同一地区,则这次计算常值系数,只计算未见面的代表会见面次数的最大值,迭代完毕之后将次结果综合考虑,并最后得到模型的最优方案。
针对问题3,将问题1中的、、分别取做8、5、5,采用问题(1)所建立的模型以及问题2设计的算法,运行程序,得到的分配结果如下:
表2 会议的分组方案
第一组
第二组
第三组
第四组
第五组
第一次
2、8
7
4、5
1
3、6
第二次
5
1
4、6
3、8
2、7
第三次
3、7
4
1、8
2、6
5
第四次
7
4、8
2、6
3
1、5
第五次
4
1、6
7
3、8
2
关键词:会议分组;矩阵分析;迭代运算;整数规划;约束条件
问题的重述
会议分组是一个很实际的问题,目前国内外许多重要会议都是以分组形式进行研讨,以便充分交流、沟通。本文是将相应的参数进行了设置,参会代表N名,M个场次,每场会议L个小组,并且要求每个小组的人数基本均衡。本文要以使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会为目的,建立数学模型,并设计求解上述分组模型的有效算法。
同时,设置一些具体数值对已经建立的模型以及算法进行验算,即、、分别取做37、5、5,根据问题1所建立的模型以及问题2设计的算法,给出5场会议的每一场各个组中具体有哪些代表参加的安排方案。
二、问题假设
1、每场次,每个专家都会参加,没有人缺席。
2、每次会议对于专家的吸引力相同。
3、每个会议每个代表有且只能在一个小组内。
三、符号说明
表一符号说明
在第次会议中的第组中
第次会议分组矩阵
和是否在第次会议分在同一组
第次会议开会矩阵
相遇矩阵
所有会议中和是否相遇
异地矩阵
和是否来自同一地区
会议的场次数
代表总数
分组总数
异地代表会面总数
异地代表是否见面
四、模型建立及求解
模型建立
第次会议的分组矩阵为
其中的取值为0或1,表示代表在第次会议中的第组中,表示表示代表不在第次会议中的第组中,由于在每次会议中每个人只能被分到一个组内,则满足如下关系:
又由于要求每组代表的人数尽量均匀,满足如下关系:
构造第次会议开会矩阵
在第次会议中,代表和代表分在同一组时,,否则,为的单位阵。
次会议中代表的会面情况可表示为
其中的元素为
表示代表和代表分在同一组的次数。
构造相遇矩阵
其中,表示代表和代表曾被分到一个组内,否则
根据已知条件构造异地矩阵,其中表示代表和代表来自不同地区,否则。
构造异地代表是否见面函数
其中,表示不同地区的代表和曾被分到一个组内,否则。
使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会,综上建立的非线性整数变量规划模型为
模型求解
考虑到模型中有变量相乘的形式,用计算运行时间比较长,因此可以采用分部计算来求解模型。即就是一共有次会议,可以迭代次来计算,每次迭代只计算一次会议的会面情况,每次迭代时更新异地矩阵,将已经会面的代表和设为同一地区,,只计算未见面的代表会面次数的最大值,迭代完毕之后将次结果综合考虑,便得到模型的最优方案。其计算过程如下:
步骤1:设置初值
步骤2:第一次迭代,计算第一次会议代表的会面情况,使得:
且满足如下约束:

步骤3:
重复步骤2,计算第二次会议代表的会面情况,以此类推,第次迭代为
由步骤3求得第次会议代表的会面情况
步骤4:得出第