合理分派与会成员的数学模型

2010 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2010 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1合理分派与会成员的数学模型摘要 本文在合理的假设之下，给出了两种可行的分配方案（方案和方案） ，解决了关于多次合理分派与会成员的问题。按照问题的要求，确定了均衡分派原则和分配比例原则及相应的权值。方案是按照均衡分派原则给出了各会议小组的分配方案，计算机模拟结果表明，这种分派方案是稳定的，实际中叶很容易实现和调整。方案是按照分配比例原则，将内部（在职）董事和外部董事按一定比例进行分派，从而给出了合理的分派方案。并且，这种分派方案在我们日常生活中有着广泛的应用。利用计算机模拟证明了在参加会议的人数很多，而分组数又相对较少的时候，应用这种方案非常理想。如果通过适当调整，则这种分派方案又可以应用于许多不类型的分组会议的情况。最后，对有些董事在会议开始的最后一刻因故不能参见会议，或有些不在会议计划名单上的成员要来参加会议的情况，都作了十分详细的讨论，并对可能出项的上述两种情况给出了简单易行的调整方案。更进一步，对这几种方案的优缺点进行了分析。实际中希望综合运用这几种分派方案，得到令人满意的效果。21问题的重述为了讨论重大问题，特别是像制定长远规划的问题，召开小组讨论会正变得越来越普遍。一般认为，由多人参加的大会很难取得建设性的成果，甚至讨论结果容易被某一位占支配地位的人控制或操纵。因此，在公司召开董事会议时，应首先召集全体董事召开一些讨论有关事务的小组会议，这些较小规模的分组会议仍然有被某一位占支配地位的人控制的危险。为降低这种危险，常用的办法是安排每个小组开几次会，每次会有不同的人参加。AnTostal 公司的会议，参加者为 29 为公司董事会成员，其中 9 位是在职董事（即公司的雇员） 。会议要开一天，每个小组商务开三段，下午开四段，每段会议开 45分钟，从上午 9:00 到下午 4:00 没整点开始开会，中午 12:00 午餐。上午的每段会议都有 6 个小组讨论会，每个小组讨论会都由公司的一位资深高级职员来支持讨论，这些资深高级职员都不是董事会的成员。因此，每位资深高级职员都要主持三个不同的小组讨论会。这些资深高级职员不参加下午的讨论会，而且下午的每段会议只有 4 个不同的小组讨论会。公司董事长需要一份由公司董事参加的 7 段分组会议的每个小组的分配名单。这份搭配名单要尽可能多地把董事均匀搭配。理想的搭配应是任意两位董事同时参加一个小组讨论会的次数相同，一次同时，要使在不同时段的小组会中同在一起开过会的董事总数达到最小。名单中的搭配还应满足下列两个准则：（1） 在上午的讨论会上，不允许一位董事参加由同一位资深高级职员主持的两次会议；（2） 每个分组讨论会都应将在职董事均匀分配到各小组中。给出一份 19 号在职董事、1029 号董事、16 号公司资深高级职员的分组搭配名单，说明该名单在多大程度上满足里前面提出的各种要求和规则，因为有的董事可能在最后一分钟宣布不参加会议，也可能不在名单上的董事将出席会议。一次，一个能使秘书在会前一小时接到参会与否的同时情况下，来调整搭配分组的算法肯定会得到赞赏。如果算法还能用于不同水平的与会者与参加后面会议中的每一类与会者搭配的话，就更理想了。2模型的假设与符号说明2.1模型的假设（1）各场会议之间及各个小组之间是相对独立的；（2）所有的高级职员和董事会成员都严格遵守派遣方案；（3）若能满足每位董事出席会议的次数都相等，则模型被一位是最理想的；（4）6 为资深高级职员之间无差异，同样 9 位在职董事之间、20 位外部董事之间也无差异。2.2符号的说明O= 表示 6 位资深高级职员 （i=1,2，6）的集合；,21io ioM= 表示所有董事会成员 (i=1,2，29)的集合；9,imimI（9）= 表示在职董事会成员 (i=1,2，9)的集合；,i i3E（20）= =M-I（9）表示外部董事成员 (i=10,11，29)的集合；2,10imimG 表示在一次分组会议中第 n 组与会成员的集合；n 6G 表示分组会议的第 n 组经第 次分派（每次分派一名成员）后的会议成k k员集合；表示董事会第 i 位成员与第 j 位成员分在同一组的次数 ；ija jiji,29,1表示两位董事会成员分在同一组时所赋予的权重；kw表示资深高级职员 与董事会成员 (j=1,2，29)在此之前是否同组ijb6,21iojm的指标，即当属于同一组时取值为 1，否则取值为 0；R = 表示在 中在职董事的数量；ki 9IGi kiG表示理事会两位内部成员在同一个讨论组中达到 i 次的对数；2/ih表示第 i 组中内部董事数与外部董事数之比.it3.模型的分析该问题需要我们对于安排不同的分组会议给出合理的分派方案，以有效降低会议被某一个人员支配控制的风险，从而确保讨论的充分性。由上述假设易知，每位资深高级职员或董事会成员被分派到人一组的可能性事一样的，同时，他们中的任何让人都不能根据其医院选择会议讨论组。根据问题要求，我们总结出两个分派原则：（1） 均衡分派原则：尽可能使得各讨论组成员人数相等。（2） 分派比例原则：各会议讨论组在职董事和外部董事的比例大致相等。于是，设想给出下面的两种分派方案：方案. 如果公司总裁希望使个讨论组的人数尽可能相等，则建议采用这个方案。显然，这个问题绝对理想的结果是不存在的，但可以按如下方法使得结果尽可能达到理想状态：每场上午的分组会议共分为 6 组，一个组由 4 位董事成员租场，其他 5 个组每组由 5 位董事成员组成。其中 3 个组每组有 2 位在职董事，而另外 3 个组每组只有 1 位在职董事。具体对于每个组成员的分派都是随机的。方案. 在实际中的很多情况下，不同类型与会者的比例是非常重要的，基于这一点，我们提出方案.由均衡分派原则，每组中在职董事和尾部董事的比例应该近似相等，即应大致为 9/20=0.45,.由所给数据和题目要求可知，不存在恰好比例为 9/20 的分派方案，但可以从以下结果中挑选最接近的方案.上午： ;5:2,:,4:2,:1,2:,:1 653 tttttt或者 424下午： ;7:3,5:2,4:,:2431 tttt4.模型和建立4.1 模型：第一种分派方案第一步.上午第一场会议的分派方案.首先，随即地把 29 位董事会成员大致均匀地分成6 组，其中一个组由 4 位成员组成，其他 5 个组每组有 5 位成员.然后，随即地将集合O 中的 6 位资深高级职员分配到每一个组中，分别记为 （i=1,2，6）.从而完成了iG第一场会议的分派.第二步.上午第二场会议的分派方案.首先，随机任取一个 ，将其分到 中，即OoiiG（i=1,2，6） ，从而使每个组 都由一位资深高级职员 （i=1,2，6）作iiGoi i为主持.然后，按下面的方法分派董事会成员：（1） 先为每一组 分派第一个董事会成员.对于任一个 .若i 1jm291jM=0，则令 .否则，随机选择另一个 ，直到1ijb11jm2j并令,02ij，i=1,2,，6.1mG这样，就为每一个组分派了第一位董事会成员.（2） 假设已为每一个组分派了 k-1 位董事会成员，即52,121 kmGjkjjki 已确定.要分派第 k 位董事会成员给 ，即确定i= ki,1jkki.随机选择一个 ,16kijkGMm计算 的值，根据 或 分别考虑.ijkb0ijkb1ijk 如果 则考虑一下两种情况：,ij情况 1.若 即为在职董事会成员，并确定 （ ）,则令集合9Imjk1kiR2（a）若 2，则令集合1iR.,121jkjjjki mG5（b）若 =2，选择另外一位董事会成员1kiR,9)(16IGMmkijk直到 且 2 为止，则令集合,0kijb1ki.,121kjjjjki m情况 2.如果 即为外部董事会成员，记,9ImjkC= 619,0ijkjij IGMb为所有候选的外部董事会成员的集合，对于每个 C,计算jq( )= ,j)(cijmwia在集合 C 中求出使得 q( )= 的 ,并且令集合jknjcqi jk= ， ， .Gi)(j1jk1jk如果 =1,则可以选择另一位董事会成员bkijm M- G ,kj61i)(k直到 b =0,同样适用上述方法，也能确定集合 G .ij )(kiG = G ，i=1,2,，6,i)5(i从而得到第二场会议的分派结果.第三步.类似上述方法分派上午第三场会议的分组结果.第四步.下午分组会议的分派方案安排：随即任意选择 , , , M,作为下午的第一位成员.mj1j2j3j4重复上面的第二步和第三步，注意在这里在职董事成员四个组的分配比例为 2:2:2:3.这样,就可以得到下午每场会议的分派方案.4.2模型 II：第二种分派方案根据上面分析,我们采用下面的分派方案将会得到最佳的比例,即有最理想的均衡性.在上午每一场讨论会议的六个组中,取在职董事会成员与外部成员的比例分别为(A):1:2,1:2，1:2，2:4，2:5 和 2:5;或者(B) 1:2,1:2，1:3,2:4,2:4 和 2:5;在下午的会议四个组中,二者的比例均为 2:4,2:4,2:5 和 3:7.6上午会议的分派方案 首先考虑在职董事与外部董事的比例为 1:2,1：2,1:2,2:4,2:4和 2:5 的情况.将 6 名资深高级职员随机地分派到六个组中去.按照如下的方法分派各讨论组的第一位成员:从 9 位在职董事成员中随机选取 mI(9),如果 b =0,则令 G = m ；否则，另取 I(9)（j j ）,并且 b =0,则1j1ij )1(ij j2122ij令 G = m .)(i2j将剩余的三位在职董事成员随机分配到任意三个组中，就可以得到 G .)2(i用模型 I 中第二步的方法进行分派，我们给每个组分派两位外部董事会成员.将剩下的 E(20)中的 8 位成员，依照 2:3:3 的比例分配到包含两位在职董事的三个组中去，并保证 R =2。)4(i按照上面步骤，我们就可以得到上午三场会议的分组方案.对于在职董事与外部董事的比例为 1:2,1:2，1:3,2:5，2:4,2:4 的情况,上述方法仍适用.只需注意在步骤(4)中,将剩余 8 位外部董事中的 7 位依照 2:2:3 的比例分派到使 R =1 的组中去即可.)4(i下午会议的分派方案 在这里取在职董事会成员与外部董事会成员的比例分别为2:4,2:4,2:5,3:7.(1)随机选取 4 位在职董事会成员, , , I(9),mj1j2j3j4并令 G = m ，再选取)(i1jm , m ,m ,m I(9)- G ,1j2j3j4j41i)(使 w( )最小，同时令aijG =m ,m ,1 j ,j 9,且 j j ，i=1,2,3,4.)2(iijiji ii最后，将 I(9)中最后剩下的一位在职董事会成员分派到能使 w( )最小得那一aij组中去.（2）同样应用模型 I 中的第二步方法，将使 R =3 或者 1 的组作适当的调整使恰)3(i好为 R =2.)3(i（3）将剩余 6 位外部董事会成员用模型 I 中第二步的方法较均匀地分派到四个讨论组中去.5. 模型的求解结果利用计算机模拟求解可以得到两个模型的求解结果，即分组讨论会的分派方案.7方案 I.对于权值 w(0)=0,w(1)=1,w(2)=3,w(3)=6,w(4)=40,w(5)=100.具体的分组方案如下表 3-1 所示.方案 II. w(0)=0,w(1)=1,w(2)=3,w(3)=6,w(4)=40,w(5)=100.(A)上午分组比例 1:2,1:2,2;4,2:5,2:5;下午分组比例 2:4,2:4,2:5,3:7.具体分组方案如下表 3-2 所示.表 3-1 方案的分组结果 1GO9m1419m2629m212027331 24284GO4m71m1516m5562723第一场会议分组 628131851GO6m1352m2724218463172325294GO2m917m08m5810416第二场会议分组 63519211GO7m87m214m221619 233595184GO3m1214m2527m51368第三场会议分组 646102029第四场会 1G2m44m15m3882G5m710m123m19206m3689 45议分组 413161782791G3m85m20m3621491321325102479第五场会议分组 4G6m74m168m1258m11810250237 1482233G4m513m72m57第六场会议分组 42691626911013472G3m72m21m289346881327m第七场会议分组 4159156205表 32 方案的分组方式（A）的分组结果 1G1O3m61217m22529224538368m33914194G4O7m520552101第一场会议分组 661816m242791G1O1m71319m212428m223956733610234G4O8m97557202第二场会议分组 669117m131921m1GO10m2312931937m204GO20m192172m5 069第三场会议分组 61161G2m72m10109692m387816第四场会议分组 4Gm72m2451909m1691913m2120203G2m3183m3第五场会议分组 46727m212m12451910第六场会 G3m9420m4519213103G1m71521m4议分组 452020m112172Gm1997m521032020 m1715m第七场会议分组 4616152（B）上午分组比例 1:2.，1:2,1:3,2:4,2:5,2:5；下午分组比例 2:4,2:4,2:5,3:7.具体分组结果如表 3-3 所示.表 3-3 方案的分组方式（B）的分组结果 1G1O4m51318m232628m2291493375204G4O1m8116m24275536275第一场会议分组 662101291G1O3m952m2722610233382184G4O2m5420m2529551713191428m第二场会议分组 66417261GO1m5第三场会议分组 23231920m21724m113GO2m181519m254344285613136GO8m702m2691421217102975892417m3Gm52319m155第四场会议分组 41618204728419211520m256G3m4102m37592182第五场会议分组 41716118G2m52m20247m3412131351524201681924第六场会议分组 4Gm21718m18139235192112171823m16253Gm34m24第七场会议分组 4641611296.模型的检验与分析方案由计算机模拟的结果显示：12（ =0，1，5）的变化对 /2 有一定的影响，但对期望 E=)(kih和方差 D= 几乎没有影响。例如：如果对于权值702891iihiiE702)(928=3， 则计算结果为,)(,)()( 80)5(,4,63E1.310，D0.445。,4,34765210 hhhh如果对于权值 则计算结果,50)(,3)4(,2)3(,)2(,1),0)( 为 E1.306，D0.442。09,79 76543210 上面的结果表明方案的稳定性令人满意。通过大量的计算机模拟可以发现： 都比较接近 0， 也较小，而76543,hh， 稍大，这也表明按现在题目的要求方案是理想的。而当与会者的人数较多，但1h2分组数量较小时，该方案就不是十分理想了。方案.通过 1000 次的计算机仿真，我们发现 的变化对 /2 几乎没有影响。)(kih如果对于权值 ，则计算结果为,1)(,0)(805,4)(,6)3(,980，E1.40，D0.75。0483,26751hhh如果对于权值 则计算结果,1)5(,)(,3)(,)2(,),)( 为 E1.41，D0.74。,0, 76543210 这足以说明这个方案是稳定的，也是理想的。方案在社会活动中有广泛的应用，适当的修改方案中的派遣方式，就可以使之适用于各种不同类型的会议分组问题。如果与会者数目较大而分组数量较小，该方案较方案理想。7模型的进一步讨论如果出现了某些人临时不能到会，或者事先，没有预约的人来参加会议的情况，则可以采用下面的方法来调整会议的分组。1 一个理事会成员 因故不能出席分组会议iiGm0方案.若 且 =0，则从 =2）中随机选取)9(0Ii )9(0Iii)9(IGj，将其安排到 中。否则，即 =1，则无需调整。)(0IGmjii 0mii若 且 =2，则从 中随机选取20Ei 0ImGii 1Ij13，将其安排到 中。否则就=无需调整。200EGmjjiG方案.若 ，且 ，使 ,则任意选取一个 ，90Ii 0iim209it 20EGmii将其安排到使 的组 中。或者任取 安排到 中。2jtj 0IGjji若 ，则可作类似调整。0Emi2 出现了一个事先没有预约的成员（用 表示）来参加会议rm方案.若 是董事会内部成员，则将其安排到 中，使得r iG=1。同时，我们将