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

答卷编号（参赛学校填写）：答卷编号（竞赛组委会填写）：论文题目：F题:会议分组问题组别：本科生参赛学校：东北电力大学报名序号：参赛队员信息(必填)：姓名专业班级及学号联系电话参赛队员1张鹏宁电自1011班100929023715043269112参赛队员2张学阳数学101班100930013215043259842参赛队员3张慧琴电自1011班100518012915143284582答卷编号（竞赛组委会填写）：评阅情况（省赛评阅专家填写）：省赛评阅1：省赛评阅2：省赛评阅3：省赛评阅4：省赛评阅5：1会议分组问题摘要本文针对会议分组这个实际问题，以运筹学最优分配为基础，采用Lingo编程完成了代表参加会议的分组方案。针对问题（1），已知有N名代表参加会议，要分M个场次，每场会议中有L个小组，先对数据进行了矩阵化处理，其中引入常值元素ijs来区分不同地区的代表，为了达到尽可能使来自不同地区的代表能有见面交流机会的目的，以每组代表人数基本均衡、每个会议每个代表有且只能在一个小组内为约束条件，建立非线性整数10变量规划模型，从而确立出最优的分组方案。针对问题（2），考虑到模型中有变量相乘的形式，用Lingo计算大量数据的非线性模型运行时间较长，因此采用分部计算的形式来求解此模型，也就是一共有M次会议，可以迭代G次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，上一次已经会面的代表假设为同一地区，则这次计算常值系数0ijs，只计算未见面的代表会见面次数的最大值，迭代完毕之后将M次结果综合考虑，便得到模型的最优方案。针对问题（3），将问题（1）中的N、M、L分别取做37、5、5，采用问题（1）所建立的模型以及问题（2）设计的算法，运行Lingo程序，但由于迭代次数过多，本文取N、M、L分别为9、5、5，也即所给表格中前九个代表开5次会议，每次会议分五组，得到的分配结果如下：第一组第二组第三组第四组第五组第一次1，72，93，64，85第二次4，91，572，63，8第三次4，67，91，823，5第四次2，56，834，71，9第五次2，83，71，65，94关键词：分组；迭代；优化；非线性21．问题的重述目前，国内外许多重要会议都是以分组形式进行研讨，以便充分交流、沟通。一般地，一个由N名代表参加的会议，要分为M个场次，每场会议分为L个小组，并且要求每个小组的人数基本均衡。问题1：请建立分组方案的数学模型，使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会。问题2：设计求解上述分组模型的有效算法。问题3：现有一个学术团体要举行由37位专家参加的学术研讨会，每个专家所在地区的信息见表1。会议分5场进行，每场会议又分5个小组，每个小组人数要基本均衡。请根据问题1所建立的模型以及问题2设计的算法，给出5场会议的每一场各个组中有哪些代表参加的安排方案。2．问题的分析对于问题一，已知有N名代表参加会议，要分M个场次，每场会议中有L个小组，令iklx表示第i个人在第k次会议中被分到第l个组的可能，iklx的值只能为1或者0，1表示第i个人在第k次会议中被分到第l个组；0表示第i个人在第k次会议中没被分到第l个组。再令ijkb表示第i个代表和第j个代表分到第k组的可能，ijkb的值也只有1和0,1表示i个代表和第j个代表分到第k组；0表示i个代表和第j个代表未分到第k组。再设一个时令系数ijs，当i和j代表是同一个地方时，ijs为0；当i和j代表不是同一个地方时，ijs为1。ijkb是经过判断与ijs相乘后得到的数值，用ijy表示第i个代表和第j个代表五场会议相遇的次数，当相遇的次数为0时ijy的数值为0，当相遇的次数不为0时，ijy的数值是1，目标函数是所有的ijy相加达到最大时才能尽可能让任意两个来自不同地区的代表之间都有见面交流的机会。对于问题二，考虑到模型中有变量相乘的形式，用Lingo计算大量数据的非线性模型运行时间比较长，因此可以采用分部计算的形式来求解此模型，也就是一共有M次会议，可以迭代M次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，讲上一次已经会面的代表假设为同一地区，也就是如果第i个代表和第j个代表上一次会面，则这次计算时令系数0ijs，只计算未见面的代表会面次数的最大值，迭代完毕之后将M次结果综合考虑，便得到模型的最优方案。对于问题三，将问题（1）中的N、M、L分别取做37、5、5，采用问题（1）所建立的模型以及问题（2）设计的算法，运行Lingo程序，但由于迭代次数过多，耗费时间过多，因此本文取N、M、L分别为9、5、5，也即所给表格中前九个代表开5次会议，每次会议分五组，即检验一下程序的可用性。33．符号说明ilkx编号为i的代表在第k次会议中的第l组中kA分组矩阵ilkb代表i和代表j分在同一组的可能kB第k次会议相遇矩阵B总的相遇矩阵Z目标函数ijs常值M会议的场次数L分组总数N代表总数k会议的次序ijz代表i和j是否会过面4．模型的建立与求解4．1问题1的模型建立与求解表1第k次会议的安排情况代表小组12……L1kx11kx12……Lkx12kx21kx22……Lkx2NkNx1kNx2……NLkx4如上表所示为第k次会议的安排情况，L为分组总数，N为代表总数，其中ilkx的取值为0或1，1ilkx表示编号为i的代表在第k次会议中的第l组中，0ilkx表示编号为i的代表不在第k次会议中的第l组中，由于在每次会议中每个人只能被分到一个组内，则满足如下关系),,2,1(11NixLlilk第k次会议的分组矩阵为LNilkkxA),,2,1(Mk又由于要求每组代表的人数尽量均匀，因此还满足如下关系11LNxLNNiilk令IAABTkkk其中kB为NN的对称阵，kB的元素为Mljlkilkijkxxb1),,2,1,(jiNji且在第k次会议中，代表i和代表j分在同一组时ilkb的值为1，否则为0，I为NN的单位阵。M次会议中代表的会面情况可表示为MkkBB1其中B的元素为Mkijkijbb1表示代表i和代表j分在同一组的次数。设地区异同矩阵为S，其元素1ijs表示代表i和代表j来自不同地区，否则0ijs。令0,00,1ijijijbby1ijy表示代表i和代表j曾被分到一个组内，否则0ijy令ijijijysz1ijz表示不同地区的代表i和j曾被分到一个组内，否则0ijz目标函数为：5NiNjijzZ11max使得尽可能让任意两个来自不同地区的代表之间都有见面交流的机会，综上建立的非线性整数10变量规划模型为NiNjijzZ11maxLlMkNjizsyxyszyxxLNxLNxijijijilkijijijMkLlijjlkilkNiilkLlilk,,2,1,,,2,1,,,2,1,10,,,111111或其中ijs由题意定的常值。4．2问题2的模型建立与求解考虑到模型中有变量相乘的形式，用Lingo计算大量数据的非线性模型运行时间比较长，因此可以采用分部计算的形式来求解此模型，也就是一共有M次会议，可以迭代M次来计算，每次迭代只计算一次会议的会面情况，每次迭代时更新目标函数的系数，讲上一次已经会面的代表假设为同一地区，也就是如果第i个代表和第j个代表上一次会面，则这次计算时令系数0ijs，只计算未见面的代表会面次数的最大值，迭代完毕之后将M次结果综合考虑，便得到模型的最优方案。其计算过程如下：步骤1：设置初值ijijss)1(（ijs是问题一中的系数，1ijs表示第i个代表和第j个代表不在同一地区）。步骤2：第一次迭代，计算第一次会议代表的会面情况)1(ijy，且满足如下约束)max(),2,1,(1)2,1(111)1()1(111)1(1111NiNjijijLsjsilijNiilLjilysNjixxyLNxLNNix步骤3：6)1()1()2(ijijijyss重复步骤2，计算第二次会议代表的会面情况)2(ijy，以此类推，第m次迭代为)1()1()(mijmijmijyss由步骤2求得第m次会议代表的会面情况)(mijy，且满足约束)max(),2,1,(1)2,1(111)()(1)(11NiNjmijmijLljlmilmmijNiilmLjilmysNjixxyLNxLNNix第M次迭代为)1()1()(MijMijMijyss由步骤二求得第M次会议代表的会面情况)(Mijy，满足的约束同上。步骤四：得出第i个代表和第j个代表的会面情况MttijijyY1)()2,1,(Nji其中0ijY表示第i个代表和第j个代表会过面，每步迭代求解得到的ilkx就是第i个代表第k次会议中的分组情况，1ilkx表示编号为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为7000011111111111111110001111110001111110001111111110000111110000111110000111110000S经计算得到的结果为矩阵C000041156132132654410005612150004236610001453325410000136240000261350000542630000C会议的分组方案为：表2会议的分组方案第一组第二组第三组第四组第五组第一次1，72，93，64，85第二次4，91，572，63，8第三次4，67，91，823，5第四次2，56，834，71，9第五次2，83，71，65，94用图形直观的表示为如下：194328图1代表的见面交流图图中两个数字之间的连线表示两个标号的代表已经见面交流过了，通过上图可直观看出任意两个代表之间没有重复的线并且同一地区的代表不在一个小组内开会，从而不同地区的两个代表尽可能多的见面交流。5．模型结果的分析与检验5次会议通过5次迭代，分别计算出每次会议代表会面的情况，其中矩阵S为初始矩阵，1ijs表示参加会议的代表ji,不在同一地区，S为对称矩阵，考虑问题方便只考虑上对角阵，在第一次会议中，9个代表分在5个小组内，经过计算，第二个矩阵C中数值是2的位置表示两个代表分在同一组，2的位置有4个，说明至多有4个代表分在同一组，且数值为2的位置没有出现在矩阵S中数值为0的位置，这与事实相符。第二次会议中，依旧是9个代表分在5个小组内，结果是数值为3的位置是两个代表分在同一组，数值为3的位置依然是4个，且不会出现在数值为2的位置，因为数值为2的位置表示两个代表已经见过面，以此类推，相应的数字和其位置如矩阵C所示，数字不会重复，且数值均为4，说明是要求的结果，由此可证明模型是正确的。6．模型的推广与改进方向1）由于在计算过程中目标函数的矩阵是对称的，计算整体的矩阵迭代的次数会更多，会花费更长的时间，而且计算结果还需除以2，因此可以更改目标函数如下111maxNiNijijzZ即只需计算矩阵的上对角阵，便得到最终的结果。2）模型是非线性的，直接