决会议分组问题讲解.doc

会议分组问题 班级：12数学师范一班 姓名：杨东云 201215010144 杜秉琨 201215010130 浦倩 201215010139摘 要 本文针对会议分组这个实际问题，以运筹学最优分配为基础，采用编程完成了代表参加会议的分组方案。 针对问题（1），已知有名代表参加会议，要分个场次，每场会议中有个小组，先对数据进行了矩阵化处理，其中引入常值元素来区分不同地区的代表，为了达到尽可能使来自不同地区的代表能有见面交流机会的目的，以每组代表人数基本均衡、每个会议每个代表有且只能在一个小组内为约束条件，建立非线性整数变量规划模型，从而确立出最优的分组方案。 针对问题（2），考虑到模型中有变量相乘的形式，用计算大量数据的非线性模型运行时间较长，因此采用分部计算的形式来求解此模型，也就是一共有次会议，可以迭代次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，上一次已经会面的代表假设为同一地区，则这次计算常值系数，只计算未见面的代表会见面次数的最大值，迭代完毕之后将次结果综合考虑，便得到模型的最优方案。 针对问题（3），将问题（1）中的、、分别取做37、5、5，采用问题（1）所建立的模型以及问题（2）设计的算法，运行程序，但由于迭代次数过多，本文取、、分别为9、5、5，也即所给表格中前九个代表开5次会议，每次会议分五组，得到的分配结果如下： 第一组 第二组 第三组 第四组 第五组 第一次 1，7 2，9 3，6 4，8 5 第二次 4，9 1，5 7 2，6 3，8 第三次 4，6 7，9 1，8 2 3，5 第四次 2，5 6，8 3 4，7 1，9 第五次 2，8 3，7 1，6 5，9 4 关键词：分组；迭代；优化；非线性 1．问题的重述 目前，国内外许多重要会议都是以分组形式进行研讨，以便充分交流、沟通。一般地，一个由N名代表参加的会议，要分为M个场次，每场会议分为L个小组，并且要求每个小组的人数基本均衡。 问题1：请建立分组方案的数学模型，使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会。 问题2：设计求解上述分组模型的有效算法。 问题3：现有一个学术团体要举行由37位专家参加的学术研讨会，每个专家所在地区的信息见表1。会议分5场进行，每场会议又分5个小组，每个小组人数要基本均衡。请根据问题1所建立的模型以及问题2设计的算法，给出5场会议的每一场各个组中有哪些代表参加的安排方案。 2．问题的分析 对于问题一，已知有名代表参加会议，要分个场次，每场会议中有个小组，令表示第个人在第次会议中被分到第个组的可能，的值只能为1或者0，1表示第个人在第次会议中被分到第个组；0表示第个人在第次会议中没被分到第个组。再令表示第个代表和第个代表分到第组的可能，的值也只有1和0,1表示个代表和第个代表分到第组；0表示i个代表和第j个代表未分到第k组。再设一个时令系数，当和代表是同一个地方时，为0；当和代表不是同一个地方时，为1。是经过判断与相乘后得到的数值，用表示第个代表和第个代表五场会议相遇的次数，当相遇的次数为0时的数值为0，当相遇的次数不为0时，的数值是1，目标函数是所有的相加达到最大时才能尽可能让任意两个来自不同地区的代表之间都有见面交流的机会。 对于问题二，考虑到模型中有变量相乘的形式，用计算大量数据的非线性模型运行时间比较长，因此可以采用分部计算的形式来求解此模型，也就是一共有次会议，可以迭代次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，讲上一次已经会面的代表假设为同一地区，也就是如果第个代表和第个代表上一次会面，则这次计算时令系数，只计算未见面的代表会面次数的最大值，迭代完毕之后将次结果综合考虑，便得到模型的最优方案。 对于问题三，将问题（1）中的、、分别取做37、5、5，采用问题（1）所建立的模型以及问题（2）设计的算法，运行程序，但由于迭代次数过多，耗费时间过多，因此本文取、、分别为9、5、5，也即所给表格中前九个代表开5次会议，每次会议分五组，即检验一下程序的可用性。 3．符号说明 编号为的代表在第次会议中的第组中 分组矩阵 代表和代表分在同一组的可能 第次会议相遇矩阵 总的相遇矩阵 目标函数 常值 会议的场次数