《会议安排数学模型》由会员分享，可在线阅读，更多相关《会议安排数学模型（65页珍藏版）》请在金锄头文库上搜索。
1、多次分组会议安排的 数学模型,华东理工大学数学系 鲁习文,一、问题重述 二、假设条件 三、变量及符号说明 四、问题分析和模型建立 五、模型求解 六、调整算法 七、模型推广 八、模型优缺点,内容提纲,本文在仔细分析问题条件和要求的基础上，运用了运筹学、图论、矩阵理论和置换等方面的知识和技巧，建立了一个布尔规划模型。 由于本模型的目标函数是非线性的，并且模型中的变量较多，因此若我们用求解一般整数规划的方法去求解它是十分困难的。,摘要,在这里，我们给出了一个求解该模型的迭代算法：首先，我们使用贪婪算法求得问题的初始可行解；然后，我们利用局部优化的原理，反复迭代，逐步逼近最优解；最终，我们可得到一个满
2、意解。 我们认为，我们的算法相当好地解决了提出的问题。,对于有些委员可能临时缺席或者有些未被安排的人员出席会议的情况，我们也给出了一个调整算法。利用它，我们能够在原来的安排表的基础上，快速地得到新的安排方案。这种调整算法的优点在于它能够最少地改动安排方案来满足新的要求，从而更具有实际意义。,由于在前述的模型建立与求解的过程中，所使用的思想方法和技巧具有一般性，因此，模型很容易推广。我们针对题目的要求推广了模型，建立了一般会议安排模型。模型中的参数，例如参加会议的人数、与会者的类型数和参与的不同层次数均是可变的。该模型及算法均能够得出相当好的结果。,本模型有以下优点： (1)它相当成功地解决了提
3、出的问题,并能够迅速地求出一组相当优化的解。 (2)本模型具有普遍的意义，能针对不同情况，根据不同参数，得到令人满意的结果。 (3)在模型求解过程中,运用了大量的优化思想和数学技巧，相当好地解决了多变量非线性整数规划问题,具有较大的应用价值。,Problem B: Mix Well For Fruitful Discussions,Small group meeting for the discussion of important issues, particularly long-range planning, are gaining popularity. It is believed
4、that large groups discourage productive discussion and that a dominant personality will usually control and direct the discussion. Thus, in corporate board meetings the board will meet in small groups to discuss issues before meeting as a whole. These smaller groups still run the risk of control by
5、a dominant personality. In an attempt to reduce this dangue it is common to schedule several sessions with a diffent mix of people in each group.,Problem B: Mix Well For Fruitful Discussions,A meeting of An Tostal Corporation will be attended by 29 Board Members of which nine are in-house members (i
6、.e., corporate employees). The meeting is to be an all-day affair with three sessions scheduled for the morning and four for the afternoon. Each session will take 45 minutes, beginning on the hour from 9:00 A.M. to 4:00 P.M., with lunch scheduled at noon Each morning session will consist of six disc
7、ussion groups with each discussion group led by one of the corporations six senior officers. None of these officers are board members. Thus each senior officer will lead three different discussion groups. The senior officers will not be involved in the afternoon sessions and each of these sessions w
8、ill consist of only four different discussion groups.,Problem B: Mix Well For Fruitful Discussions,The president of the corporation wants a list of board-member assignments to discussion groups for each of the seven sessions. The assignments should achieve as much of a mix of the members as much as
9、possible. The ideal assignment would have each board member with each other board member in a discussion group the same number of times while minimizing common membership of groups for the different sessions. The assignments should also satisfy the following criteria: For the morning sessions, no bo
10、ard member should be in the same senior officers discussion group twice. No discussion group should contain a disproportionate number of in-house members.,Problem B: Mix Well For Fruitful Discussions,Give a list of assignments for members 1-9 and 10-29 and officers 1-6. Indicate how well the criteri
11、a in the previous paragraphs are met. Since it is possible that some board members will cancel at the last minute or that some not scheduled will show up, an algorithm that the secretary could use to adjust the assignments with an hours notice would be appreciated. It would be ideal if the algorithm
12、 could also be used to make assignments for future meetings involving different levels of participation for each type of attendee.,一、问题重述-1,在讨论重要问题时，特别是长远规划的问题，越来越流行的一种做法是召开小组会议人们相信全体会议会使讨论失去活力，而且权威人士通常将会控制和直接影响讨论这样，在举行全体会议之前，委员将以小组形式来讨论问题这些比较小的小组仍有被权威人士控制的危险为了减少这种危险，通常将会议安排为几个场次，每场次中每个开会小组由不同的人混合组成
13、,一、问题重述-2,Tostal公司将举行一个由29个委员参加的会议，其中有9个委员是公司成员 这次会议将开一整天，上午分三场，下午分四场，每场45分钟，开会时间从上午：到下午：，中午安排午餐 上午的每一场分个小组开会，每个小组有公司派出的名资深官员之一作组长这名资深官员中没有一个是与会委员，并且他们不参加下午的会议下午的每一场分为个小组开会,一、问题重述-3,公司负责人需要个开会时间场次的每一场各个组中，有哪些委员参加的安排表.这一会议安排应使所有委员尽可能相互交流理想的安排是：每个委员与其他委员在开会小组中都有相同的见面次数，并且对每个不同的开会场次，各个开会小组中曾在同一组的委员应尽可能
14、少 会议的安排也要满足下列两个要求： 上午的开会场次中，不能有一个委员参加过两次由同一个资深官员主持的小组会； 不允许同一个场次中的讨论小组的公司委员数不合比例,一、问题重述-4,请给出个公司委员（编号）非公司委员（编号）以及资深官员的一张安排表，并且说明是如何满足上述两个要求的 因为有些委员可能临时不能到会，或者有些未被安排的人员将出席会议，因此最好能设计一个算法，能够对将来不同参与类型的人参加和各种不同参与水平的会议进行安排则更好,二、假设条件,每种类型的与会者地位相同； 与会者坚决服从会议组织者的安排； 在整个会议进行过程中，不允许与会者变动,：决策向量；其元素 表示在第 场会议中，成员
15、 是否在第 组； ：分组矩阵； ：第 场会议的分组矩阵； ：相遇矩阵； ：第 场会议的相遇矩阵； ：总相遇矩阵： Qsum =,三、变量及符号说明,：目标函数，定义为 中0元素的个数； ：另一个目标函数，定义为矩阵T的范数平方 其中k是常数，表示平均重复相遇次数,四、问题分析和模型建立,1、预备知识 首先,我们必须先对分组作一个数学描述： 令与会者集合 ，我们将他们分为组 于是，我们能够得到一个矩阵： 其中,因为矩阵清楚地表达了分组情况，我们定义它为分组矩阵理想的情况是，通过分组矩阵所给出的信息，我们能得到另一个矩阵，用它来判断元素i和j是否曾在同一个小组中，这个新的矩阵为： 其中,其中,我们
16、定义它为相遇矩阵我们可以得到一个关于分组矩阵和相遇矩阵的基本定理 定理: 若为一个分组矩阵，则其对应的相遇矩阵为 (E为单位阵) 证明：显然对于每一位与会者来说，每次只能被分在某一个小组中，因此矩阵的每一行只有一个元素为1，其余均为考虑式子 ，可以很容易地得到该矩阵的元素为：,（）若 和 不同时为，就意味着 和 不在同一组中，那么 ； （）如果 和 同时为，就意味着 和 分在同一组中，那么 所以相遇矩阵 ,、约束条件,结合问题中的条件和要求，我们可以用变量 表示第i个人在第j场次会议中被分于第k组 其中i=129 代表29个参加会议的委员； i=19 代表个公司委员； i=1029 代表其余个非公司委员； j=17 代表个场次的会议； k=16 代表每个场次分个小组；,于是，对每一场次的分组来说，就一定存在一个分
