《会议安排数学模型PPT精品文档》由会员分享，可在线阅读，更多相关《会议安排数学模型PPT精品文档（66页珍藏版）》请在金锄头文库上搜索。
1、华东理工大学EastChinaUniversityofScienceAndTechnology多次分组会议安排的多次分组会议安排的数学模型数学模型华东理工大学数学系华东理工大学数学系 鲁习文鲁习文一、问题重述一、问题重述二、假设条件二、假设条件三、变量及符号说明三、变量及符号说明四、问题分析和模型建立四、问题分析和模型建立五五、模型求解、模型求解六六、调整算法、调整算法七七、模型推广、模型推广八八、模型优缺点、模型优缺点内容提纲内容提纲 l本文在仔细分析问题条件和要求的基础上，运用本文在仔细分析问题条件和要求的基础上，运用了运筹学、图论、矩阵理论和置换等方面的知识了运筹学、图论、矩阵理论和置换
2、等方面的知识和技巧，建立了一个布尔规划模型。和技巧，建立了一个布尔规划模型。 l由于本模型的目标函数是非线性的，并且模型中由于本模型的目标函数是非线性的，并且模型中的变量较多，因此若我们用求解一般整数规划的的变量较多，因此若我们用求解一般整数规划的方法去求解它是十分困难的。方法去求解它是十分困难的。摘要摘要l在这里，我们给出了一个求解该模型的迭代算法：在这里，我们给出了一个求解该模型的迭代算法：首先，我们使用贪婪算法求得问题的初始可行解；首先，我们使用贪婪算法求得问题的初始可行解；然后，我们利用局部优化的原理，反复迭代，逐然后，我们利用局部优化的原理，反复迭代，逐步逼近最优解；最终，我们可得到
3、一个满意解。步逼近最优解；最终，我们可得到一个满意解。l我们认为，我们的算法相当好地解决了提出的问我们认为，我们的算法相当好地解决了提出的问题。题。l对于有些委员可能临时缺席或者有些未被安排的对于有些委员可能临时缺席或者有些未被安排的人员出席会议的情况，我们也给出了一个调整算人员出席会议的情况，我们也给出了一个调整算法。利用它，我们能够在原来的安排表的基础上，法。利用它，我们能够在原来的安排表的基础上，快速地得到新的安排方案。这种调整算法的优点快速地得到新的安排方案。这种调整算法的优点在于它能够最少地改动安排方案来满足新的要求，在于它能够最少地改动安排方案来满足新的要求，从而更具有实际意义。从
4、而更具有实际意义。l由于在前述的模型建立与求解的过程中，所使用由于在前述的模型建立与求解的过程中，所使用的思想方法和技巧具有一般性，因此，模型很容的思想方法和技巧具有一般性，因此，模型很容易推广。我们针对题目的要求推广了模型，建立易推广。我们针对题目的要求推广了模型，建立了一般会议安排模型。模型中的参数，例如参加了一般会议安排模型。模型中的参数，例如参加会议的人数、与会者的类型数和参与的不同层次会议的人数、与会者的类型数和参与的不同层次数均是可变的。该模型及算法均能够得出相当好数均是可变的。该模型及算法均能够得出相当好的结果。的结果。本模型有以下优点：l(1)它相当成功地解决了提出的问题,并能
5、够迅速地求出一组相当优化的解。l(2)本模型具有普遍的意义，能针对不同情况，根据不同参数，得到令人满意的结果。l(3)在模型求解过程中,运用了大量的优化思想和数学技巧，相当好地解决了多变量非线性整数规划问题,具有较大的应用价值。 Problem B: Mix Well For Fruitful DiscussionslSmallgroupmeetingforthediscussionofimportantissues,particularlylong-rangeplanning,aregainingpopularity.lItisbelievedthatlargegroupsdiscourag
6、eproductivediscussionandthatadominantpersonalitywillusuallycontrolanddirectthediscussion.lThus,incorporateboardmeetingstheboardwillmeetinsmallgroupstodiscussissuesbeforemeetingasawhole.lThesesmallergroupsstillruntheriskofcontrolbyadominantpersonality.lInanattempttoreducethisdangueitiscommontoschedul
7、eseveralsessionswithadiffentmixofpeopleineachgroup.Problem B: Mix Well For Fruitful DiscussionslAmeetingofAnTostalCorporationwillbeattendedby29BoardMembersofwhichninearein-housemembers(i.e.,corporateemployees).lThemeetingistobeanall-dayaffairwiththreesessionsscheduledforthemorningandfourfortheaftern
8、oon.Eachsessionwilltake45minutes,beginningonthehourfrom9:00A.M.to4:00P.M.,withlunchscheduledatnoonlEachmorningsessionwillconsistofsixdiscussiongroupswitheachdiscussiongroupledbyoneofthecorporationssixseniorofficers.Noneoftheseofficersareboardmembers.Thuseachseniorofficerwillleadthreedifferentdiscuss
9、iongroups.Theseniorofficerswillnotbeinvolvedintheafternoonsessionsandeachofthesesessionswillconsistofonlyfourdifferentdiscussiongroups.Problem B: Mix Well For Fruitful DiscussionslThepresidentofthecorporationwantsalistofboard-memberassignmentstodiscussiongroupsforeachofthesevensessions.Theassignment
10、sshouldachieveasmuchofamixofthemembersasmuchaspossible.Theidealassignmentwouldhaveeachboardmemberwitheachotherboardmemberinadiscussiongroupthesamenumberoftimeswhileminimizingcommonmembershipofgroupsforthedifferentsessions.lTheassignmentsshouldalsosatisfythefollowingcriteria:1.Forthemorningsessions,n
11、oboardmembershouldbeinthesameseniorofficersdiscussiongrouptwice.2.Nodiscussiongroupshouldcontainadisproportionatenumberofin-housemembers.Problem B: Mix Well For Fruitful DiscussionslGivealistofassignmentsformembers1-9and10-29andofficers1-6.Indicatehowwellthecriteriainthepreviousparagraphsaremet.lSin
12、ceitispossiblethatsomeboardmemberswillcancelatthelastminuteorthatsomenotscheduledwillshowup,analgorithmthatthesecretarycouldusetoadjusttheassignmentswithanhoursnoticewouldbeappreciated.lItwouldbeidealifthealgorithmcouldalsobeusedtomakeassignmentsforfuturemeetingsinvolvingdifferentlevelsofparticipati
13、onforeachtypeofattendee.一、问题重述-1在讨论重要问题时，特别是长远规划的问题，越来越流行在讨论重要问题时，特别是长远规划的问题，越来越流行的一种做法是召开小组会议人们相信全体会议会使讨论的一种做法是召开小组会议人们相信全体会议会使讨论失去活力，而且权威人士通常将会控制和直接影响讨论失去活力，而且权威人士通常将会控制和直接影响讨论这样，在举行全体会议之前，委员将以小组形式来讨论问这样，在举行全体会议之前，委员将以小组形式来讨论问题这些比较小的小组仍有被权威人士控制的危险为了题这些比较小的小组仍有被权威人士控制的危险为了减少这种危险，通常将会议安排为几个场次，每场次中每减
14、少这种危险，通常将会议安排为几个场次，每场次中每个开会小组由不同的人混合组成个开会小组由不同的人混合组成一、问题重述-2Tostal公司将举行一个由公司将举行一个由29个委员参加的会议，其中有个委员参加的会议，其中有9个委员是公司成员个委员是公司成员这次会议将开一整天，上午分三场，下午分四场，每场这次会议将开一整天，上午分三场，下午分四场，每场45分钟，开会时间从上午：到下午：，中午安分钟，开会时间从上午：到下午：，中午安排午餐排午餐上午的每一场分个小组开会，每个小组有公司派出的上午的每一场分个小组开会，每个小组有公司派出的名资深官员之一作组长这名资深官员中没有一个是与名资深官员之一作组长这名
15、资深官员中没有一个是与会委员，并且他们不参加下午的会议下午的每一场分为会委员，并且他们不参加下午的会议下午的每一场分为个小组开会个小组开会一、问题重述-3l公司负责人需要个开会时间场次的每一场各个组中，公司负责人需要个开会时间场次的每一场各个组中，有哪些委员参加的安排表有哪些委员参加的安排表.这一会议安排应使所有委员尽这一会议安排应使所有委员尽可能相互交流理想的安排是：每个委员与其他委员在可能相互交流理想的安排是：每个委员与其他委员在开会小组中都有相同的见面次数，并且对每个不同的开开会小组中都有相同的见面次数，并且对每个不同的开会场次，各个开会小组中曾在同一组的委员应尽可能少会场次，各个开会小
16、组中曾在同一组的委员应尽可能少l会议的安排也要满足下列两个要求：会议的安排也要满足下列两个要求：1.上午的开会场次中，不能有一个委员参加过两次由同一上午的开会场次中，不能有一个委员参加过两次由同一个资深官员主持的小组会；个资深官员主持的小组会；2.不允许同一个场次中的讨论小组的公司委员数不合比例不允许同一个场次中的讨论小组的公司委员数不合比例一、问题重述-4l请给出个公司委员（编号请给出个公司委员（编号）非公司委员）非公司委员（编号（编号）以及资深官员的一张安排表，）以及资深官员的一张安排表，并且说明是如何满足上述两个要求的并且说明是如何满足上述两个要求的l因为有些委员可能临时不能到会，或者有
17、些未被因为有些委员可能临时不能到会，或者有些未被安排的人员将出席会议，因此最好能设计一个算安排的人员将出席会议，因此最好能设计一个算法，能够对将来不同参与类型的人参加和各种不法，能够对将来不同参与类型的人参加和各种不同参与水平的会议进行安排则更好同参与水平的会议进行安排则更好二、假设条件1.每种类型的与会者地位相同；2.与会者坚决服从会议组织者的安排；3.在整个会议进行过程中，不允许与会者变动l：决策向量；其元素表示在第场会议中，成员是否在第组；l：分组矩阵；l：第场会议的分组矩阵；l：相遇矩阵；l：第场会议的相遇矩阵；l：总相遇矩阵：Qsum=三、变量及符号说明l：目标函数，定义为中0元素的
18、个数；l：另一个目标函数，定义为矩阵T的范数平方其中k是常数，表示平均重复相遇次数 四、问题分析和模型建立l1、预备知识首先,我们必须先对分组作一个数学描述：令与会者集合，我们将他们分为组于是，我们能够得到一个矩阵：其中l因为矩阵清楚地表达了分组情况，我们定义它为分组矩阵理想的情况是，通过分组矩阵所给出的信息，我们能得到另一个矩阵，用它来判断元素i和j是否曾在同一个小组中，这个新的矩阵为： 其中 其中 l我们定义它为相遇矩阵我们可以得到一个关于分组矩阵和相遇矩阵的基本定理l定理:若为一个分组矩阵，则其对应的相遇矩阵为(E为单位阵)l证明：显然对于每一位与会者来说，每次只能被分在某一个小组中，因
19、此矩阵的每一行只有一个元素为1，其余均为考虑式子，可以很容易地得到该矩阵的元素为： （）若和不同时为，就意味着和不在同一组中，那么；（）如果和同时为，就意味着和分在同一组中，那么所以相遇矩阵、约束条件结合问题中的条件和要求，我们可以用变量表示第i个人在第j场次会议中被分于第k组其中i=129代表29个参加会议的委员；i=19代表个公司委员；i=1029代表其余个非公司委员；j=17代表个场次的会议；k=16代表每个场次分个小组； 于是，对每一场次的分组来说，就一定存在一个分组矩阵再根据问题的条件和要求，我们得到下列约束条件：(1)在每一次分组中，每人只能分在一组中： (2)每次分组时,每组中的
20、公司委员数应当合比例：(3)上午阶段的每场会议，个小组每一个都要有一名资深官员主持，每个参加会议的委员都不能与任一名资深官员重复见面：、目标函数 (j=17)代表了次分组的分组矩阵，那么我们如何才能判断次分组的效果是好还是坏呢？对于这个问题，我们可以参考问题的要求，问题要求模型给出的分组方案应使所有与会委员混合得最好，并且在每个场次中在保证委员们尽可能地相互认识的基础上，使委员们重复见面的次数尽量平均，我们先考虑一个极端情况：29个委员分在一个组中这样，充分混合的目标是最好的满足了，但是，重复见面的次数也达到了最大因此，当分组数小或者各组人数不均衡时，开会场次越多，与会这重复见面的次数就越大
21、同时，我们还必须注意避免人数太多影响讨论的效果，或者被权威人士所影响和操纵在模型的建立和求解过程中，我们只考虑29个委员均分为6组或4组的情况我们认为，在这样的划分前提下所得到分组方案，其重复见面次数总和应达到最小对于这个结论，我们无法给出严格的数学推导但考虑到实际生活中的绝大多数情况，我们认为均分是最有实际意义的所以，我们将参加上午会议的29个委员分为、，共组；下午的分为、，共组 那么，我们如何用数学语言来描述或评判次分组的好坏？对于第j次分组来说，有分组矩阵Pi，又存在相遇矩阵Qi次分组后，委员129相互见面的总次数可通过以下公式来计算：其中矩阵称为分组的总的相识矩阵 l考虑到充分交流和任
22、意两个会员重复见面次数尽量相同这两个目标，我们认为在总的相识矩阵中元素的个数必须达到最小理想的状态是，除了主对角线上元素为之外，中别的元素均为相同（即任意两个与会成员之间见面次数相同）l根据均匀分组的原则，我们可以得到这样的安排为与会者提供了次相互见面的机会另一方面，只需要次相互见面的机会就可以使29个与会成员两两相遇了因此，任意两个与会成员平均能有1.31次机会见面令令 k=532/406=1.31 其中其中 我们认为达到最小时，任意两个成员重复见面次数达到尽量平均这个目标得以实现而当达到最小时，充分见面这个目标也得以最好地满足，这同时也表明了成员之间的充分交流、建立模型、建立模型我们得到如
23、下的模型： 根据前面的讨论，我们有根据前面的讨论，我们有 l因为模型的目标函数是充分相识的前提下保证成员间两两重复见面次数平均，所以我们的目标有两个：Min和Min。事实上，目标函数表明了成员之间没有相互见面的程度，越小，相互见面的程度就越高，而之所以引入的原因在于保证任意两个成员重复见面的次数尽量平均。l这是一个标准的整数规划和多目标规划的问题。我们要做的就是如何对它进行求解。五五、模型求解、模型求解1、分析、分析我们试图为这个模型提出一个一般的算法，并根据这个算法为模型找出一组最优解来。由于在模型建立过程中，所有的变量被定义为只能取或，我们首先想到的是整数规划的方法。而根据上述模型，这是一
24、个标准的多目标0-1整数规划问题，目前还缺乏切实可行的算法可以找出最优解来，能够证明，这是一个完全问题。如果我们使用穷举法来搜索最优解的话，变量个数为986个，循环次数也将达到986次。这对于我们的电脑是一个巨大的挑战，甚至连奔腾级的计算机也无法进行如此大规模的运算，穷举法是不可行的。我们首先要指出的是本模型的最优解是客观存在的。我们的想法是先找出一个满足所有条件的初始可行解，然后在这组解的基础上，逐步迭代，使这组解不断逼近最优解。最后，我们便可以得到一组近似最优解了。（1）迭代我们先通过贪婪算法找到一组初始可行解，然后我们运用坐标轮换法固定其中六组向量（每一组向量均代表一个场次的分组情况），
25、调整剩下的那一组向量使目标函数和减少.l第一步，我们调整代表第七场次分组情况的向量组使目标函数减小，下一步，我们再调整代表第六场次分组情况的向量组是目标函数值减小，不断重复该过程，我们便可以获得一组近似最优解了。l同时，目标函数也逼近最小值。因为目标函数有两个，我们使用的是多目标规划级别优先的策略：在达到最小的条件下使也尽可能小。首先我们利用进行迭代，直到它不再减小为止。然后在不变的基础上利用迭代，使得它也尽可能小。由于和的值都在不断减小，且都有界，根据单调有界数列必收敛的原理，最后我们可以得到一组近似最优解。（2）置换我们将不在同一组中的两个成员交换位置。如果这种交换使得目标函数减小，则交换
26、是可接受的，否则，交换被拒绝。不断重复这样的过程，目标函数也就不断减小了 （3）初始解我们利用贪婪算法获得一组初始可行解。在每一个阶段，该算法将29个成员依次插入到各个组中去。在插入之前，算法将结合当前的分组情况，根据限制条件和目标函数找出一个最佳位置供该成员插入。2、算法步骤、算法步骤A：得到一组初始可行解：得到一组初始可行解（1）令；（”代表会议的不同场次；“”则代表各个成员的序号）；（2）；（3）；（4）如果，就必须考虑每一个委员不得与资深官员重复见面的限制条件。（5）如果，就必须考虑到公司委员被均分的条件。（6）设每一个资深官员见过的与会成员的总数保持平衡。（7）计算目标函数和，找出一
27、个最佳位置使成员插入后目标函数和尽可能小。（8）当有多个组可选择时，选择序号较小的组。（9）如果，回到步骤(3)，否则转到步骤(10)。（10）如果，回到步骤(2)，否则转到算法B。l步骤(6)是为了保证一种均衡。事实上，我们所得到的这个安排方案无论是在整个会议期间还是在每一阶段都保持了均衡，而以下的置换算法不会破坏此方案的均衡性。这个初始解为今后得到更好的解奠定了基础。B：通过迭代算法优化初始解得到最优解：通过迭代算法优化初始解得到最优解 （1）;（2）输入初始可行解；（3）调整分组矩阵，在保证不变的基础上交换满足下列条件的每一对成员的位置：两个成员必须是同一类型的参与者（同为公司委员或同为
28、非公司委员）；他们必须在不同的组中；他们在上午的三次分组中不得与资深官员重复见面；目标函数的值在交换后必须减小。 （4）交换每一对满足下列条件的成员：两个成员必须是同一类型的参与者（同为公司成员或同为非公司成员）；他们必须在不同的组中；他们在上午的三次分组中不得与资深官员重复见面；目标函数的值保持不变，目标函数的值在交换后必须减小。（5）；（6）若，则回到步骤(3)；（7）若一轮循环后（）没有一个交换被接受便退出，否则以当前解为初始解转回到步骤(2)。3、结论、结论l通过贪婪算法，我们得到如下的方案：表1上午分配表 表2.下午分配表 =209且=28.25l通过迭代算法得到另一组分配方案：表3
29、.上午分配表 表4.下午分配表表5.两组方案比较表l从上面的表格中，我们可以很容易的得到一些结论。通过贪婪算所得到的初始解满足所有均衡条件，这意味着这个解也具有某种程度优化。而最后通过迭代法得到的解不仅保持了初始解的均衡性，而且也使目标函数和得以优化。l我们认为我们所得到的解满足了问题中的两个要求：我们的解不仅使0（相互不见面）的个数降低到26，还使得3（最多相互见面3次）的个数减少至25。l 在下面，我们给出了最佳会议安排表表6。在表中，以“A”开头的标号代表资深官员，以“B”开头的标号代表公司内部职员。以“C”开头的标号代表普通职员。 表表6.会议安排最佳安排表会议安排最佳安排表表6.会议
30、安排最佳安排表（续）六六、调整算法、调整算法 l现在，我们考虑在最后一刻，一些计划参加的委员未能参加和一些未计划参加的委员将出席会议。l如我们以上所说，此模型是很容易推广的。一个简单的方法是将与会委员重新编号，然后按我们的算法解决这个新问题，但在真正的生活中，我们不希望对已安排好的会议进行太大的改变。因此，我们给出了另一个策略来对此进行调整。l第一种情况：当在最后一刻，一些未计划参加第一种情况：当在最后一刻，一些未计划参加的委员将出席会议的委员将出席会议。l我们仅考虑如何将这些额外的会员安排到以前已确定的安排中去，而不改变以前的安排，我们使用一种与贪婪算法类似的方法去解决这个新问题，这些额外的
31、会员将被一个一个的安排，对每一个额外的会员我们按照限制条件保持安排的平衡和使与会者最大可能的相见，为其在每一场次中找到一个最合适的讨论组。 l第二种情况：当在最后一刻，一些计划参加的委第二种情况：当在最后一刻，一些计划参加的委员未能参加。员未能参加。l我们考虑从原定的安排中找出一个同一类型的与会会员，这个会员的缺席将导致最好的混合，也就是他的缺席将使目标函数值更大的降低，然后，我们让他去代替那个不能出席的会员，而他以前的会议安排将被取消，如此，我们每次取消一个与会者。最后，我们将解决这个问题，当然，我们总是保持安排的平衡。l第三种情况：当前两种情况同时发生时，我们可第三种情况：当前两种情况同时
32、发生时，我们可以转化为第一第二种情况来处理。以转化为第一第二种情况来处理。 表表7.三种算法计算结果比较三种算法计算结果比较调整算法与前述算法计算结果比较见表7，在表中使用的标号ni代表在矩阵中元素i (i=1,2,3,4,5)的个数。l 应该说，我们的迭代算法和调整算法都是令人满意的。看上去，由调整算法得到的结果应当和由迭代算法得到的结果同样的好，在几种情况下（例如：八个公司内部委员参加的会议），由调整算法得到的结果略微优于由迭代算法得到的结果。这说明在我们的模型求解中仍存在误差，还需要改进。七七、模型推广、模型推广l在建模和求解过程中，我们对参数没有特殊的要求，如：会员的总数、会议的场次、
33、会员的类型和参与的层次。因为我们的模型有很大可推广性，我们可以给出一个更一般情况下的模型。l现在，让我们考虑在未来的会议中的安排。在这个会议中，我们假定：有d类会员，整个会议被分成w个阶段，第i个阶段有Si个场次且每个场次由Gi个讨论组组成，安排也应满足以下要求：1.在每个场次中，每一个会员仅能被安排到一个组中。2.第个场次中，类型的会员要在每个场次中平衡的分布。3.整个的安排情况也要保持平衡。4.在第r阶段中，L类型的会员不允许超过c次与资深官员相见。l假定第种类型的会员有bi个，那么总的会员数为。我们将其从1到m进行编号。例如：第k类型的第i个会员的编号为。整个会议包括个阶段，第阶段有个场
34、次记，其代表全部场次之和我们假定在第个阶段每个场次都将会员划分为个讨论组l现在我们如下定义决策变量，表示第i个人在第j场次会议中被分于第k组我们能定义两个矩阵和去描述每个场次的安排情况定义：矩阵Qj表示在第场次中会员之间相互的见面情况矩阵Qsum表示在整个会议中会员之间相互见面次数的总和。l令l一般的模型表示如下l约束条件（1）确保了在每一个场次中每一个会员仅能安排在一个讨论组中l约束条件（2）确保了类型的会员在第场次中被均衡的划分l约束条件（3）使整个会议安排保持均衡l约束条件（4）保证了第类与会者在第阶段不得与资深官员见面超过c次l类似的我们也可以利用上面提到的算法来解这个推广的模型八八、
35、模型优缺点、模型优缺点l本模型具有相当好的实用性，提出的算法具有较低的时间复杂度。我们用C语言对贪婪算法和迭代算法进行编程，在一台奔腾100的电脑上总的运行时间不超过5分钟。这表明，当与会人数不太多的情况下，本模型能快速地给出一份会议安排表来。同时，得到的会议安排极大地逼近了最优解，也很好地满足了问题中的两个要求。l本模型具有可推广性。我们能对不同数量的参与者，不同的分组数目，不同的参与者类型及其参与者不同的参与程度轻易地建立和求解模型。在上面模型推广中，模型被推广到更一般的情况l对于与会人员的临时变化，我们给出了两种不同的调整策略。一种是对所有的与会成员重新编号，然后根据我们的算法重新排定方案；另一种则是在原方案的基础上进行调整，通过尽量小的变动得到的新的方案，后者更具有现实意义。l在求解模型的过程中，我们运用了诸如迭代、置换、局部优化等数学技巧。由于我们解决的是多变量非线性整数规划问题，模型的求解方法具有极大的现实和借鉴意义。l模型的缺点在于我们得到的最优解与实际最优解之间存在着一定的误差。通过仔细分析，我们认为误差产生的原因有二：一是有时无法减小到最小值；二是目标函数可能还有更好的形式。我们相信，当更好地解决了这两个问题之后，我们所得到的解能更加逼近最优解。若有不当之处，请指正，谢谢！66
