会议安排数学模型-课件

多次分组会议安排的数学模型

一、问题重述二、假设条件三、变量及符号说明四、问题分析和模型建立五、模型求解六、调整算法七、模型推广八、模型优缺点内容提纲

本文在仔细分析问题条件和要求的基础上，运用了运筹学、图论、矩阵理论和置换等方面的知识和技巧，建立了一个布尔规划模型。

由于本模型的目标函数是非线性的，并且模型中的变量较多，因此若我们用求解一般整数规划的方法去求解它是十分困难的。会议安排数学模型会议安排数学模型在这里，我们给出了一个求解该模型的迭代算法：首先，我们使用贪婪算法求得问题的初始可行解；然后，我们利用局部优化的原理，反复迭代，逐步逼近最优解；最终，我们可得到一个满意解。我们认为，我们的算法相当好地解决了提出的问题。对于有些委员可能临时缺席或者有些未被安排的人员出席会议的情况，我们也给出了一个调整算法。利用它，我们能够在原来的安排表的基础上，快速地得到新的安排方案。这种调整算法的优点在于它能够最少地改动安排方案来满足新的要求，从而更具有实际意义。会议安排数学模型由于在前述的模型建立与求解的过程中，所使用的思想方法和技巧具有一般性，因此，模型很容易推广。我们针对题目的要求推广了模型，建立了一般会议安排模型。模型中的参数，例如参加会议的人数、与会者的类型数和参与的不同层次数均是可变的。该模型及算法均能够得出相当好的结果。本模型有以下优点：

(1)它相当成功地解决了提出的问题,并能够迅速地求出一组相当优化的解。

(2)本模型具有普遍的意义，能针对不同情况，根据不同参数，得到令人满意的结果。

(3)在模型求解过程中,运用了大量的优化思想和数学技巧，相当好地解决了多变量非线性整数规划问题,具有较大的应用价值。

会议安排数学模型Smallgroupmeetingforthediscussionofimportantissues,particularlylong-rangeplanning,aregainingpopularity.Itisbelievedthatlargegroupsdiscourageproductivediscussionandthatadominantpersonalitywillusuallycontrolanddirectthediscussion.Thus,incorporateboardmeetingstheboardwillmeetinsmallgroupstodiscussissuesbeforemeetingasawhole.Thesesmallergroupsstillruntheriskofcontrolbyadominantpersonality.Inanattempttoreducethisdangueitiscommontoscheduleseveralsessionswithadiffentmixofpeopleineachgroup.会议安排数学模型AmeetingofAnTostalCorporationwillbeattendedby29BoardMembersofwhichninearein-housemembers(i.e.,corporateemployees).Themeetingistobeanall-dayaffairwiththreesessionsscheduledforthemorningandfourfortheafternoon.Eachsessionwilltake45minutes,beginningonthehourfrom9:00A.M.to4:00P.M.,withlunchscheduledatnoonEachmorningsessionwillconsistofsixdiscussiongroupswitheachdiscussiongroupledbyoneofthecorporation’ssixseniorofficers.Noneoftheseofficersareboardmembers.Thuseachseniorofficerwillleadthreedifferentdiscussiongroups.Theseniorofficerswillnotbeinvolvedintheafternoonsessionsandeachofthesesessionswillconsistofonlyfourdifferentdiscussiongroups.会议安排数学模型Thepresidentofthecorporationwantsalistofboard-memberassignmentstodiscussiongroupsforeachofthesevensessions.Theassignmentsshouldachieveasmuchofamixofthemembersasmuchaspossible.Theidealassignmentwouldhaveeachboardmemberwitheachotherboardmemberinadiscussiongroupthesamenumberoftimeswhileminimizingcommonmembershipofgroupsforthedifferentsessions.Theassignmentsshouldalsosatisfythefollowingcriteria:Forthemorningsessions,noboardmembershouldbeinthesameseniorofficer’sdiscussiongrouptwice.Nodiscussiongroupshouldcontainadisproportionatenumberofin-housemembers.

会议安排数学模型Givealistofassignmentsformembers1-9and10-29andofficers1-6.Indicatehowwellthecriteriainthepreviousparagraphsaremet.Sinceitispossiblethatsomeboardmemberswillcancelatthelastminuteorthatsomenotscheduledwillshowup,analgorithmthatthesecretarycouldusetoadjusttheassignmentswithanhour’snoticewouldbeappreciated.Itwouldbeidealifthealgorithmcouldalsobeusedtomakeassignmentsforfuturemeetingsinvolvingdifferentlevelsofparticipationforeachtypeofattendee.会议安排数学模型在讨论重要问题时，特别是长远规划的问题，越来越流行的一种做法是召开小组会议．人们相信全体会议会使讨论失去活力，而且权威人士通常将会控制和直接影响讨论．这样，在举行全体会议之前，委员将以小组形式来讨论问题．这些比较小的小组仍有被权威人士控制的危险．为了减少这种危险，通常将会议安排为几个场次，每场次中每个开会小组由不同的人混合组成．会议安排数学模型Tostal公司将举行一个由29个委员参加的会议，其中有9个委员是公司成员．这次会议将开一整天，上午分三场，下午分四场，每场45分钟，开会时间从上午９：００到下午４：００，中午安排午餐．上午的每一场分６个小组开会，每个小组有公司派出的６名资深官员之一作组长．这６名资深官员中没有一个是与会委员，并且他们不参加下午的会议．下午的每一场分为４个小组开会．会议安排数学模型公司负责人需要７个开会时间场次的每一场各个组中，有哪些委员参加的安排表.这一会议安排应使所有委员尽可能相互交流．理想的安排是：每个委员与其他委员在开会小组中都有相同的见面次数，并且对每个不同的开会场次，各个开会小组中曾在同一组的委员应尽可能少．会议的安排也要满足下列两个要求：上午的开会场次中，不能有一个委员参加过两次由同一个资深官员主持的小组会；不允许同一个场次中的讨论小组的公司委员数不合比例．会议安排数学模型请给出９个公司委员（编号１—９）非公司委员（编号１０—２９）以及资深官员的一张安排表，并且说明是如何满足上述两个要求的．因为有些委员可能临时不能到会，或者有些未被安排的人员将出席会议，因此最好能设计一个算法，能够对将来不同参与类型的人参加和各种不同参与水平的会议进行安排则更好．会议安排数学模型每种类型的与会者地位相同；与会者坚决服从会议组织者的安排；在整个会议进行过程中，不允许与会者变动

：决策向量；其元素表示在第场会议中，成员是否在第组；：分组矩阵；：第场会议的分组矩阵；：相遇矩阵；：第场会议的相遇矩阵；：总相遇矩阵：Qsum=会议安排数学模型会议安排数学模型

：目标函数，定义为中0元素的个数；：另一个目标函数，定义为矩阵T的范数平方

其中k是常数，表示平均重复相遇次数．

会议安排数学模型1、预备知识首先,我们必须先对分组作一个数学描述：令与会者集合，我们将他们分为ｎ组．于是，我们能够得到一个矩阵：

其中会议安排数学模型因为矩阵Ｐ清楚地表达了分组情况，我们定义它为分组矩阵．理想的情况是，通过分组矩阵所给出的信息，我们能得到另一个矩阵，用它来判断元素ｓi和ｓj是否曾在同一个小组中，这个新的矩阵为：其中其中会议安排数学模型我们定义它为相遇矩阵．我们可以得到一个关于分组矩阵和相遇矩阵的基本定理．定理:若为一个分组矩阵，则其对应的相遇矩阵为

(E为单位阵)．证明：显然对于每一位与会者来说，每次只能被分在某一个小组中，因此矩阵的每一行只有一个元素为1，其余均为０．考虑式子，可以很容易地得到该矩阵的元素为：

（１）若和不同时为１，就意味着和不在同一组中，那么；（２）如果和同时为１，就意味着和分在同一组中，那么．所以相遇矩阵．会议安排数学模型结合问题中的条件和要求，我们可以用变量表示第i个人在第j场次会议中被分于第k组．其中i=1~29代表29个参加会议的委员；

i=1~9代表９个公司委员；

i=10~29代表其余２０个非公司委员；

j=1~7代表７个场次的会议；

k=1~6代表每个场次分６个小组；

于是，对每一场次的分组来说，就一定存在一个分组矩阵再根据问题的条件和要求，我们得到下列约束条件：

(1)在每一次分组中，每人只能分在一组中：

(2)每次分组时,每组中的公司委员数应当合比例：

(3)上午阶段的每场会议，６个小组每一个都要有一名资深官员主持，每个参加会议的委员都不能与任一名资深官员重复见面：会议安排数学模型

(j=1~7)代表了７次分组的分组矩阵，那么我们如何才能判断７次分组的效果是好还是坏呢？对于这个问题，我们可以参考问题的要求，问题要求模型给出的分组方案应使所有与会委员混合得最好，并且在每个场次中在保证委员们尽可能地相互认识的基础上，使委员们重复见面的次数尽量平均，我们先考虑一个极端情况：29个委员分在一个组中．这样，充分混合的目标是最好的满足了，但是，重复见面的次数也达到了最大．因此，当分组数小或者各组人数不均衡时，开会场次越多，与会这重复见面的次数就越大．同时，我们还必须注意避免人数太多影响讨论的效果，或者被权威人士所影响和操纵．在模型的建立和求解过程中，我们只考虑29个委员均分为6组或4组的情况．我们认为，在这样的划分前提下所得到分组方案，其重复见面次数总和应达到最小．对于这个结论，我们无法给出严格的数学推导．但考虑到实际生活中的绝大多数情况，我们认为均分是最有实际意义的．所以，我们将参加上午会议的29个委员分为５、５、５、５、５、４，共６组；下午的分为７、７、７、８，共４组．

会议安排数学模型那么，我们如何用数学语言来描述或评判７次分组的好坏？对于第j次分组来说，有分组矩阵Pi，又存在相遇矩阵Qi．７次分组后，委员1~~29相互见面的总次数可通过以下公式来计算：其中矩阵称为分组的总的相识矩阵

考虑到充分交流和任意两个会员重复见面次数尽量相同这两个目标，我们认为在总的相识矩阵中０元素的个数必须达到最小．理想的状态是，除了主对角线上元素为０之外，中别的元素均为相同（即任意两个与会成员之间见面次数相同）．根据均匀分组的原则，我们可以得到这样的安排为与会者提供了次相互见面的机会．另一方面，只需要次相互见面的机会就可以使29个与会成员两两相遇了．因此，任意两个与会成员平均能有1.31次机会见面．会议安排数学模型令k=532/406=1.31

会议安排数学模型其中

我们认为达到最小时，任意两个成员重复见面次数达到尽量平均这个目标得以实现．而当达到最小时，充分见面这个目标也得以最好地满足，这同时也表明了成员之间的充分交流４、建立模型

我们得到如下的模型：

根据前面的讨论，我们有

会议安排数学模型因为模型的目标函数是充分相识的前提下保证成员间两两重复见面次数平均，所以我们的目标有两个：Min和Min。事实上，目标函数表明了成员之间没有相互见面的程度，越小，相互见面的程度就越高，而之所以引入的原因在于保证任意两个成员重复见面的次数尽量平均。这是一个标准的整数规划和多目标规划的问题。我们要做的就是如何对它进行求解。会议安排数学模型1、分析我们试图为这个模型提出一个一般的算法，并根据这个算法为模型找出一组最优解来。由于在模型建立过程中，所有的变量被定义为只能取０或１，我们首先想到的是整数规划的方法。而根据上述模型，这是一个标准的多目标0-1整数规划问题，目前还缺乏切实可行的算法可以找出最优解来，能够证明，这是一个ＮＰ完全问题。如果我们使用穷举法来搜索最优解的话，变量个数为986个，循环次数也将达到６986次。这对于我们的电脑是一个巨大的挑战，甚至连奔腾级的计算机也无法进行如此大规模的运算，穷举法是不可行的。我们首先要指出的是本模型的最优解是客观存在的。我们的想法是先找出一个满足所有条件的初始可行解，然后在这组解的基础上，逐步迭代，使这组解不断逼近最优解。最后，我们便可以得到一组近似最优解了。（1）迭代我们先通过贪婪算法找到一组初始可行解，然后我们运用坐标轮换法固定其中六组向量（每一组向量均代表一个场次的分组情况），调整剩下的那一组向量使目标函数和减少.

会议安排数学模型第一步，我们调整代表第七场次分组情况的向量组使目标函数减小，下一步，我们再调整代表第六场次分组情况的向量组是目标函数值减小，不断重复该过程，我们便可以获得一组近似最优解了。同时，目标函数也逼近最小值。因为目标函数有两个，我们使用的是多目标规划级别优先的策略：在达到最小的条件下使也尽可能小。首先我们利用进行迭代，直到它不再减小为止。然后在不变的基础上利用迭代，使得它也尽可能小。由于和的值都在不断减小，且都有界，根据单调有界数列必收敛的原理，最后我们可以得到一组近似最优解。会议安排数学模型（2）置换我们将不在同一组中的两个成员交换位置。如果这种交换使得目标函数减小，则交换是可接受的，否则，交换被拒绝。不断重复这样的过程，目标函数也就不断减小了

（3）初始解我们利用贪婪算法获得一组初始可行解。在每一个阶段，该算法将29个成员依次插入到各个组中去。在插入之前，算法将结合当前的分组情况，根据限制条件和目标函数找出一个最佳位置供该成员插入。会议安排数学模型A：得到一组初始可行解（1）令；（””代表会议的不同场次；“”则代表各个成员的序号．）；（2）；（3）；（4）如果，就必须考虑每一个委员不得与资深官员重复见面的限制条件。（5）如果，就必须考虑到公司委员被均分的条件。会议安排数学模型（6）设每一个资深官员见过的与会成员的总数保持平衡。（7）计算目标函数和，找出一个最佳位置使成员插入后目标函数和尽可能小。（8）当有多个组可选择时，选择序号较小的组。（9）如果，回到步骤(3)，否则转到步骤(10)。（10）如果，回到步骤(2)，否则转到算法B。

步骤(6)是为了保证一种均衡。事实上，我们所得到的这个安排方案无论是在整个会议期间还是在每一阶段都保持了均衡，而以下的置换算法不会破坏此方案的均衡性。这个初始解为今后得到更好的解奠定了基础。会议安排数学模型B：通过迭代算法优化初始解得到最优解

（1）;（2）输入初始可行解；（3）调整分组矩阵，在保证不变的基础上交换满足下列条件的每一对成员的位置：两个成员必须是同一类型的参与者（同为公司委员或同为非公司委员）；他们必须在不同的组中；他们在上午的三次分组中不得与资深官员重复见面；目标函数的值在交换后必须减小。

会议安排数学模型（4）交换每一对满足下列条件的成员：两个成员必须是同一类型的参与者（同为公司成员或同为非公司成员）；他们必须在不同的组中；他们在上午的三次分组中不得与资深官员重复见面；目标函数的值保持不变，目标函数的值在交换后必须减小。（5）；（6）若，则回到步骤(3)；（7）若一轮循环后（）没有一个交换被接受便退出，否则以当前解为初始解转回到步骤(2)。会议安排数学模型通过贪婪算法，我们得到如下的方案：表1．上午分配表

会议安排数学模型表2.下午分配表

=209且=28.25会议安排数学模型通过迭代算法得到另一组分配方案：表3.上午分配表

表4.下午分配表会议安排数学模型表5.两组方案比较表会议安排数学模型从上面的表格中，我们可以很容易的得到一些结论。通过贪婪算所得到的初始解满足所有均衡条件，这意味着这个解也具有某种程度优化。而最后通过迭代法得到的解不仅保持了初始解的均衡性，而且也使目标函数和得以优化。我们认为我们所得到的解满足了问题中的两个要求：我们的解不仅使0（相互不见面）的个数降低到26，还使得3（最多相互见面3次）的个数减少至25。

在下面，我们给出了最佳会议安排表表6。在表中，以“A”开头的标号代表资深官员，以“B”开头的标号代表公司内部职员。以“C”开头的标号代表普通职员。

会议安排数学模型表6.会议安排最佳安排表表6.会议安排最佳安排表（续）会议安排数学模型现在，我们考虑在最后一刻，一些计划参加的委员未能参加和一些未计划参加的委员将出席会议。如我们以上所说，此模型是很容易推广的。一个简单的方法是将与会委员重新编号，然后按我们的算法解决这个新问题，但在真正的生活中，我们不希望对已安排好的会议进行太大的改变。因此，我们给出了另一个策略来对此进行调整。会议安排数学模型第一种情况：当在最后一刻，一些未计划参加的委员将出席会议。我们仅考虑如何将这些额外的会员安排到以前已确定的安排中去，而不改变以前的安排，我们使用一种与贪婪算法类似的方法去解决这个新问题，这些额外的会员将被一个一个的安排，对每一个额外的会员我们按照限制条件——保持安排的平衡和使与会者最大可能的相见，为其在每一场次中找到一个最合适的讨论组。

会议安排数学模型第二种情况：当在最后一刻，一些计划参加的委员未能参加。我们考虑从原定的安排中找出一个同一类型的与会会员，这个会员的缺席将导致最好的混合，也就是他的缺席将使目标函数值更大的降低，然后，我们让他去代替那个不能出席的会员，而他以前的会议安排将被取消，如此，我们每次取消一个与会者。最后，我们将解决这个问题，当然，我们总是保持安排的平衡。第三种情况：当前两种情况同时发生时，我们可以转化为第一第二种情况来处理。会议安排数学模型表7.三种算法计算结果比较调整算法与前述算法计算结果比较见表7，在表中使用的标号ni代表在矩阵中元素i(i=1,2,3,4,5)的个数。

会议安排数学模型

应该说，我们的迭代算法和调整算法都是令人满意的。看上去，由调整算法得到的结果应当和由迭代算法得到的结果同样的好，在几种情况下（例如：八个公司内部委员参加的会议），由调整算法得到的结果略微优于由迭代算法得到的结果。这说明在我们的模型求解中仍存在误差，还需要改进。会议安排数学模型在建模和求解过程中，我们对参数没有特殊的要求，如：会员的总数、会议的场次、会员的类型和参与的层次。因为我们的模型有很大可推广性，我们可以给出一个更一般情况下的模型。现在，让我们考虑在未来的会议中的安排。在这个会议中，我们假定：有d类会员，整个会议被分成w个阶段，第i个阶段有Si个场次且每个场次由Gi个讨论组组成，安排也应满足以下要求：

1.在每个场次中，每一个会员仅能被安排到一个组中。

2.第个场次中，类型的会员要在每个场次中平衡的分布。

3.整个的安排情况也要保持平衡。