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

会议分组问题摘要通过对问题的分析,我们确定运用优化的整数规划模型、矩阵理论和置换等方面的知识和技巧。通过矩阵将决策变量和所要求解的目标函数建立联系。在提出模型目标函数的过程中,首先我们提出了代表相遇次数的概念,用矩阵 Q 表示其任意两个代表的相遇次数,并利用矩阵的 Frobenius 范数控制了 Q中元素的大小及其均匀程度,得到目标函数 f(x) ,从而求解代表的相遇次数。第一个目标函数设定后, 基于 f(x) 在群体整体换组时不能起到控制作用的问题,决定使用共同成员概念: 即任意两组(可以属于不同场次)整个会议中的交集。利用矩阵A,对矩阵的 Frobenius 范数的运用使群体整体换组现象得到了有效的遏制,对与会者混合程度进行了控制。求解模型时,使用迭代算法,利用线性规划,在目标函数可行域范围内查找最优解可以利用MATLA B软件设计出计算可行初始解->随机产生一个可行解->局部优化->全局优化从而达到全局最优解的三步求解的方法,局部->全局的步骤解出了全局最优解, 简化运算步骤的同时提高了结果优化程度,降低对初值的依赖程度, 很好的达到了与会者需要充分混合的目的。基于算法的目标函数,因为在建立时具有一般性, 若需建立起优化全局的目标函数,只需对参数进行改变。这样一来模型的推广得到了算法上的支持,带来了极大的便利。我们此次建模得到了合适的人员分配结果,达到了建模的目的。关键词: 抽屉原理相遇矩阵共同成员 Frobenius 范数一、问题重述目前,国内外许多重要会议都是以分组形式进行研讨,以便充分交流、沟通。一般地,一个由 N名代表参加的会议,要分为 M个场次,每场会议分为 L个小组,并且要求每个小组的人数基本均衡。问题 1:请建立分组方案的数学模型,使得尽可能让任意两个来自不同地区的委员之间都有见面交流的机会。问题 2:设计求解上述分组模型的有效算法。问题 3 :现有一个学术团体要举行由 37 位专家参加的学术研讨会,每个专家所在地区的信息见表 1。会议分 5场进行,每场会议又分 5个小组,每个小组人数要基本均衡。请根据问题 1 所建立的模型以及问题 2 设计的算法,给出 5 场会议的每一场各个组中有哪些委员参加的安排方案。说明: 论文要附有求解问题 3 源程序的全部代码,并确保能够直接运行以检验结果的正确性。 37 位专家所在地区信息表专家 1234567 地区 BJ BJ BJ BJ SH SH SH 专家 8910 11121314 地区 HZ HZ TJ TJ CQ CQ CD 专家 15161718192021 地区 CD SY ZZ SZ XA 专家 22232425262728 地区 GZ WH QD JN XJ XZ XN 专家 29303132333435 地区 DL HF SJ CS HN NJ XM 专家 3637 地区 YC LZ 二、模型假设(1 )假设各场会议及各小组间是相互独立的; (2 )假设所有代表严格遵守派遣方案,不会改变制定的分配方案; (3 )假设来自不同地区的代表之间无其他差异; (4 )假设每场会议各组人数分配为 7,7,7,9,9 。注:对于假设( 4) ,我们可以运用初等模型中的公平分配得到,具体过程如下: 三、变量及符号说明和数学描述 1、变量符号说明(1) ijkx :0-1 决策变量,表示第 i位代表有否参加第 k场第 j组会议; (2)P :开会分组矩阵, 表示整次会议每场代表的分组安排,其中 kP 表示第 k场会议的分组矩阵,其行向量 jkP 表示第 k场会议第 j组的分组矩阵; (3)Q :相遇矩阵; (4) ( ) f x :目标函数一,用来控制代表相遇次数; (5) ( ) g x :目标函数二,用于控制不同场间组间共同成员个数; (6) ( ) F x :总的目标函数,综合考虑( ) f x 和( ) g x 的目标函数. 2、变量符号数学描述(1) ijk 1, j 0,. x ??????表示第i位代表参加第k场第组的会议否则(2)?? 1 2 = jk jk jk Njk P x x x ?,k表示第 k段会议,j表示第 j组,k=1,2, …,M, j=1,2, …,L,i=1,2, …,N . (3) 1k 11k 21k 1k 2 12k 22k 2k 1 k 2 k k x x x x x x = x x x N kN k M M NM MkPPPP ? ?? ?? ?? ?? ??