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

会议分组问题
摘要
通过对问题的分析,我们确定运用优化的整数规划模型、矩阵理论和置换等方面的知识和技巧。通过矩阵将决策变量和所要求解的目标函数建立联系。
在提出模型目标函数的过程中,首先我们提出了代表相遇次数的概念,用矩阵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位专家所在地区信息表
专家
1
2
3
4
5
6
7
地区
BJ
BJ
BJ
BJ
SH
SH
SH
专家
8
9
10
11
12
13
14
地区
HZ
HZ
TJ
TJ
CQ
CQ
CD
专家
15
16
17
18
19
20
21
地区
CD
SY
HA
CC
ZZ
SZ
XA
专家
22
23
24
25
26
27
28
地区
GZ
WH
QD
JN
XJ
XZ
XN
专家
29
30
31
32
33
34
35
地区
DL
HF
SJ
CS
HN
NJ
XM
专家
36
37
地区
YC
LZ
二、模型假设
(1)假设各场会议及各小组间是相互独立的;
(2)假设所有代表严格遵守派遣方案,不会改变制定的分配方案;
(3)假设来自不同地区的代表之间无其他差异;
(4)假设每场会议各组人数分配为7,7,7,9,9。
注:对于假设(4),我们可以运用初等模型中的公平分配得到,具体过程如下:
三、变量及符号说明和数学描述
1、变量符号说明
:0-1决策变量,表示第i位代表有否参加第k场第j组会议;
:开会分组矩阵,表示整次会议每场代表的分组安排,其中表示第k场会议的分组矩阵,其行向量表示第k场会议第j组的分组矩阵;
:相遇矩阵;
:目标函数一,用来控制代表相遇次数;
:目标函数二,用于控制不同场间组间共同成员个数;
:总的目标函数,综合考虑和的目标函数.
2、变量符号数学描述
(1)
(2),k表示第k段会议,j表示第j组,k=1,2,…,M,j=1,2,…,L,i=1,2,…,N.
(3)
(4)
(5)
四、模型建立
通过使用(0-1)整数规划来建立该问题的模型。题目要求每个小组的人数基本均衡,使得尽可能让任意两个来自不同地区的委员之间都有见面交流的机会。从这两个要求出发,分别从相遇代表次数和共同成员数目两个角度建立了两个目标函数。再加上题设要求以及模型假设得到的约束条件,完成本模型的建立。具体过程以及模型如下所示。
题目要求分组名单安排计划属于分派问题,常用0-1变量表示分派的决策变量,根据本题的特点现在把分派问题视为抽屉问题。每场会议配给L个抽屉,每组分一个,每个
抽屉分为N个空格(第1至第N号),每位代表的