最佳阵容问题(完整版).doc

最佳阵容问题 朱春秋，林英勇，杨苗摘要在当今这个更注重团体比赛的时代，对团队出场阵容的安排是团队获胜的一个非常重要因素。根据参赛项目选拔人数和参赛选手成绩等诸多限制因素建立约束条件；根据题目问题可建立目标函数，在此基础上得到模型一.所以从本质上说，最佳阵容问题属于0-1规划问题。最后运用Lingo数学软件对模型一求解得到最优结果。问题一：运用Excel软件，处理得出每个队员各单项得分最低情况（表1.1）和期望值情况（表1.3）.在这些情况下，用Lingo数学软件对模型一求解，找出相应的最佳阵容，求得每个选手的各单项得分按最悲观估算，最佳出场阵容团队得分为212.3；每个选手的各单项得分按最均值估算，最佳出场阵容团队得分为224.7。问题二：在模型一中加入一个变量后，计算结果复杂.根据问题一的结果，知道可以从每个选手各个单项得分最大分值着手，算得该前提下团队总分最大分值为236.5，所以选取236.2、236.3、236.4、236.5四个分值讨论.在模型一的基础上加入总分分别等于这四个分值的约束条件，运用Lingo数学软件求出最佳阵容，分析知阵容八（表2.10）的分值最高且得分概率最大并得出了该团队夺冠前景，得分前景等相关问题的解。关键词：最佳阵容问题、0-1规划、最优解一 问题重述有一场由四个项目（高低杠、平衡木、跳马、自由体操）组成的女子体操团体赛，赛程规定：每个队至多允许 10 名运动员参赛，每一个项目可以有 6 名选手参加。每个选手参赛的成绩评分从高到低依次为： 10 ； 9.9 ； 9.8 ； ； 0.1 ； 0 。每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者。此外，还规定每个运动员只能参加全能比赛（四项全参加）与单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加三项单项。每个队应有 4 人参加全能比赛，其余运动员参加单项比赛。现某代表队的教练已经对其所带领的 10 名运动员参加各个项目的成绩进行了大量测试，教练发现每个运动员在每个单项上的成绩稳定在 4 个得分上（见下表），她们得到这些成绩的相应概率也由统计得出（见表中第二个数据。例如： 8.4 0.15 表示取得 8.4 分的概率为 0.15 ）。试解答以下问题（运动员各项目得分及概率分布见附表）：附表：运动员各项目得分及概率分布表1 （高低杠）2 （平衡木）3 （跳马）4 （自由体操）18.40.158.40.109.10.108.70.109.00.508.80.209.30.108.90.209.20.259.00.609.50.609.10.609.40.10100.109.80.209.90.1029.30.108.40.158.40.108.90.109.50.109.00.508.80.209.10.109.60.609.20.259.00.609.30.609.80.209.40.10100.109.60.2038.40.108.10.108.40.159.50.108.80.209.10.509.00.509.70.109.00.609.30.309.20.259.80.60100.109.50.109.40.10100.2048.10.108.70.109.00.108.40.109.10.508.90.209.40.108.80.209.30.309.10.609.50.509.00.609.50.109.90.109.70.30100.1058.40.159.00.108.30.109.40.109.00.509.20.108.70.109.60.109.20.259.40.608.90.609.70.609.40.109.70.209.30.209.90.2069.40.108.70.108.50.108.40.159.60.108.90.208.70.109.00.509.70.609.10.608.90.509.20.259.90.209.90.109.10.309.40.1079.50.108.40.108.30.108.40.109.70.108.80.208.70.108.80.109.80.609.00.608.90.609.20.60100.20100.109.30.209.80.2088.40.108.80.058.70.108.20.108.80.209.20.058.90.209.30.509.00.609.80.509.10.609.50.30100.10100.409.90.109.80.1098.40.158.40.108.40.109.30.109.00.508.80.108.80.209.50.109.20.259.20.609.00.609.70.509.40.109.80.20100.109.90.30109.00.108.10.108.20.109.10.109.20.109.10.509.20.509.30.109.40.609.30.309.40.309.50.609.70.209.50.109.60.109.80.201 、每个选手的各单项得分按最悲观估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高；每个选手的各单项得分按均值估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高。2 、若对以往的资料及近期各种信息进行分析得到：本次夺冠的团体总分估计为不少于 236.2 分，该队为了夺冠应排出怎样的阵容？以该阵容出战，其夺冠前景如何？得分前景（即期望值）又如何？它有 90 的把握战胜怎样水平的对手？二、 问题分析本论文所讨论的是一个关于最佳阵容的问题。最佳阵容问题是一类带有复杂约束条件的优化与规划类问题。在当今这个更注重团体比赛的时代，对团队出场阵容的安排是团队获胜的一个重要因素，在团队参赛中，不仅要注重团队整体质量的提高，更加要注重如何合理的利用现有队员在各项目中的优劣来获得最高的总分。本案例的主要矛盾是队员已有成绩的限制和参赛时的要求与获得团队参赛最高分的矛盾。对本案例处理的难点是参赛时的要求，参赛队员的4个成绩稳定值与相应概率的限制等诸多因素，针对各目标问题分别建立模型。 按照上述思路提出目标函数，要建立各个约束条件，要找到众多变量之间的数量关系。因而，对约束条件和问题做出分析都是解决问题的关键。由于队员的安排不可能为小数，所以最佳阵容问题属于整数规划中的0-1规划问题。我们分两步来进行分析。首先对问题所给条件进行分析。此比赛共有4个项目，每个参赛队至多有10名运动员参赛，也就是说参赛人数，同时每个项目可以有6名选手参加，由于每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者，所以每个队的教练在每个项目中都会派出6名运动员参赛。此外，还规定每个运动员只能参加全能比赛与单项比赛这两类中的一类；每个队应有4人参加全能比赛，也就是说每个队有且仅有4人参加全能比赛，其余运动员参加单项比赛。由题中还可知道每项各选手的评分精确到小数点后一位。再对问题进行分析。第一问（1）每个选手的各单项得分按最悲观估算，这个最悲观就是在每个参赛选手各单项最差的成绩下进行计算。第一问（2）每个选手的各单项得分按均值估算即按每个参赛选手各单项得分的期望值作为所要求的数据进行计算。第二问（1）本次夺冠的团体总分估计不少于236.2分，为了夺冠应为该队排出怎样的阵容，这里我们可理解为在该队团体总分不少于236.2的情况下，为该队排出一个阵容，使该队的夺冠概率最大。第二问（2）中的夺冠前景即指夺冠的概率。第二问（3）得分前景即该阵容各选手得分的期望值的总分。第二问（3）就是在求该阵容有90%的把握战胜多少总分数的对手。三、模型基本假设1. 假设每位参赛选手在比赛时技能水平发挥正常，不会出现感冒，胃病，比赛中途受伤，怯场，临时退出等现象；2. 假设运动员在比赛中能正常发挥水平，不受天气等其它因素影响；3. 假设每个项目有6名选手参加，有4名选手参加全能比赛；4. 假设在比赛中每位裁判都是公平、公正的，各个项目的评分规则公平、公正、完善；5. 虽然平时教练所测得每位运动员每单项的结果并不一定只有表中所给的四组数，但我们可以假设教练所进行的大量测试得出的结果精确无误，即我们按该值进行计算最后得出的结果误差可以忽略不计。四、符号说明符号说明i选手号（=1、2、3、4、5、6、7、8、9、10）j项目名（=1，2，3，4；分别记为高低杠，平衡木，跳马，自由体操）N表示各队参赛的人数是个0-1变量，若选择队员参加项比赛，记=1,否则,记=0.是个0-1变量，若队员参加全能比赛，记=1，否则，记=0.表示队员在项目中得分最差的情况表示队员在项目中的期望值表示第个项目的第个分值第个项目对应的第个值的概率表示队员在项目中得分最高的情况.五、模型的建立和求解5.1问题一的模型建立和求解对于问题一我们根据参赛要求，引入0-1变量, 、 由条件：“每个队应有4人参加全能比赛”即每个队参加全能比赛的人有且仅有4名，得约束条件： 、由条件：“参加单项比赛的每个运动员至多只能参加三项单项”即不参加全能比赛的运动员最多只能参加3三个单项，得约束条件：（=1,2,3,4,5,6,7,8,9,10） 、由条件：“参加全能比赛的选手要四项全参加”，得约束条件：（=1,2, 3,4,5,6,7,8,9,10） 、由条件：“每个项目可以有6名选手参加”即每个项目的参赛选手不能超过6名，得约束条件： (=1，2，3，4) 5.1.1问题一(1)的模型建立和求解对问题一（1）要求每个队员的各单项得分按最悲观估算的前提下，根据前面的分析我们将最悲观理解为参赛选手在各单项得分最差的情况。首先把表1经Excel软件处理得出每个队员各单项得分最低情况下的表1.1。最悲观估算（得分最低的情况下）数据表(表1.1) 项目队员1（高低杠）2（平衡木）3（跳马）4（自由体操）18.48.49.18.729.38.48.48.938.48.18.49.548.18.798.458.498.39.469.48.78.58.479.58.48.38.488.48.88.78.298.48.48.49.31098.18.29.1当运队员入选项目时，表示她在该项目得分最低的分数，否则。于是各队员在各单项得分按得分最低的分值估算时，该队团体总分可表示为，这就是在这种最悲观情况下该问题的目标函数，这种情况下这个问题的0-1规划模型可写作：Maxs.t. ; （=1,2,3,4,5,6,7,8,9,10） ; （=1,2,3,4,5,6,7,8,9,10） ; (=1，2，3，4) ; （=1,2,3,4,5,6,7,8,9,10）（=1,2,3,4）.在这种最悲观情况下，将表1.1数据代入这一模型.对于这种问题的模型的求解我们可以运用数学软件Lindo来运行，所以我们这里用数学软件来进行求解。求解得到结果为：,即：，（=2,5,6,9； =1,2,3,4）；此外，还有13=34=42=43=71=82=101=104=1.即表示队员2，5，6，9参加全能比赛，此外还有队员1参加了项目3（跳马）的比赛，队员3参加了项目4（自由体操）的比赛，队员4参加了项目2（平衡木）和项目3（跳马）的比赛，队员7参加了项目1（高低杠）的比赛，队员8参加了项目2（平衡木）的比赛，队员10参加了项目1（高低杠）和项目4（自由体操）的比赛.以此阵容出赛能使该团队在每个选手的各单项得分按得分最低的分值估算的前提下总分最高，总分是：212.3分.（见表1.1.1）问题一（1）最优阵容及得分表1.1.1队员1（高低杠）2（平衡木）3（跳马）4自由体操）总得分19.1212.329.38.48.48.939.548.79.058.49.08.39.469.48.78.58.479.588.898.48.48.49.3109.09.15.1.2 问题一（2）模型的建立与求解对问题一（2）要求在每个队员的各单项得分按均值估算的前提下，这里我们把均值理解为期望值.首先用Excel软件对表1进行处理得出每个队员各单项得分的期望值情况下的表1.3。均值（期望值）估算数据表(表1.3) 项目队员1（高低杠）2（平衡木）3（跳马）4（自由体操）1999.59.129.6999.3399.199.849.19.19.59599.48.99.769.79.18.9979.898.99.2899.89.19.3999.299.7109.49.19.29.5当运队员入选项目时，表示她在该项目得分的期望值，否则.于是各队员在各单项目得分按均值估算时，该队团体总分可表示为，这就是在均值情况下该问题的目标函数，这种情况下这个问题的0-1规划模型可写作：Maxs.t. ; （=1,2,3,4,5,6,7,8,9,10） ; （=1,2,3,4,5,6,7,8,9,10） ; (=1，2，3，4) ; （=1,2,3,4,5,6,7,8,9,10）（=1,2,3,4）.在每个队员的各单项得分按均值估算的前提下，将表1.2数据代入这一模型，用数学软件Lindo来进行求解。求解得到结果为：,即：，（=2,8,9,10； =1,2,3,4）；此外，还有。即表示队员2，8，9，10参加全能比赛，此外还有队员1参加了项目3（跳马）的比赛，队员3参加了项目4（自由体操）的比赛，队员4参加了项目2（平衡木）和项目3（跳马）的比赛，队员5参加了项目2（平衡木）和项目4（自由体操）的比赛，队员6参加了项目1（高低杠）的比赛，队员7参加了项目1（高低杠）的比赛.以此阵容出赛能使该团队在每个选手的各单项得分按得分均值估算的前提下总分最高，总分是：224.7分。（见表1.2.1）问题一（2）的最优阵容及得分表1.2.1队员1（高低杠）2（平衡木）3（跳马）4（自由体操）总得分19.5224.729.69.09.09.339.849.19.559.49.769.779.889.09.89.19.399.09.29.09.7109.49.19.29.55.2问题二的模型建立和求解5.2.1问题二（1）的分析与求解首先把表1 经Excel软件处理得出每个选手各单项得分最高情况下的表2.1.得分最高的情况表(表2.1) 项目队员1（高低杠）2（平衡木）3（跳马）4（自由体操）19.4109.89.929.89.4109.63109.59.41049.59.99.71059.49.79.39.969.99.99.19.4710109.39.8810109.99.899.49.8109.9109.7109.69.8当运队员入选项目时，表示她在该项目得分最高的分数，否则。于是各队员在各单项得分按得分最高的分值估算时，该队团体总分可表示为，这就是在这种情况下该问题的目标函数，这种情况下这个问题的0-1规划模型可写作：Maxs.t. ； （=1,2,3,4,5,6,7,8,9,10） ； （=1,2,3,4,5,6,7,8,9,10） ； (=1，2，3，4) ； （=1,2,3,4,5,6,7,8,9,10）（=1,2,3,4）在这种情况下，将表1. 2数据代入这一模型.同样我们这里用数学软件Lindo来进行求解。求解得到结果为：,即：，（=1,4,7,8 =1,2,3,4）；此外，还有。即表示队员1，4，7，8参加全能比赛，此外还有队员2参加了项目3（跳马）的比赛，队员3参加了项目1（高低杠）和项目4（自由体操）的比赛，队员5参加了项目4（自由体操）的比赛，队员6参加了项目1（高低杠）和项目2（平衡木）的比赛，队员9参加了项目2（平衡木）和项目3（跳马）的比赛.以此阵容出赛能使该团队在每个选手的各单项得分按得分最高的分值估算的前提下总分最高，总分是：236.5分。得出团体总分最大的分值后，因为每项各选手的评分精确到小数点后一位.所以我们就在236.2236.5之间分别取236.2，236.3，236.4，236.5这四个数值讨论，首先把总分是这四个数值的所有阵容找出。同样我们还是用Lindo软件计算，只是把上面那个模型的约束条件中加入总分等于236.2或236.3或236.4或236.5这几个分值.当团队总分为236.2时模型为：Maxs.t. ； （=1,2,3,4,5,6,7,8,9,10）； （=1,2,3,4,5,6,7,8,9,10）； (=1，2，3，4) ； =236.2 （=1,2,3,4,5,6,7,8,9,10）（=1,2,3,4）.将表1. 2数据代入这一模型.同样我们这里用数学软件Lindo来进行求解。求解得到结果为：,即：，（=2,4,7,8 =1,2,3,4）；此外，还有.即表示队员2，4，7，8参加全能比赛，此外还有队员1参加了项目2（平衡木）和项目3（跳马）的比赛，队员3参加了项目1（高低杠）和项目4（自由体操）的比赛，队员5参加了项目4（自由体操）的比赛，队员6参加了项目1（高低杠）和项目2（平衡木）的比赛，队员9参加了项目3（跳马）的比赛.以此阵容出赛就有可能得出总分：236.2分.此外多运行两次还可得出阵容：队员1，3，4，8参加全能比赛，此外还有队员2参加了项目1（高低杠）和项目3（跳马）的比赛，队员6参加了项目2（平衡木）的比赛，队员7参加了项目1（高低杠）和项目2（平衡木）和项目4（自由体操）的比赛，队员9参加了项目3（跳马）和项目4（自由体操）的比赛。同样可得到每个选手各单项得分按最高分估算时，团体总分为236.3的阵容，即队员1，3，4，8参加全能比赛，此外还有队员2参加了项目1（高低杠）和项目3（跳马）的比赛，队员5参加了项目4（自由体操）的比赛，队员6参加了项目2（平衡木）的比赛，队员7参加了项目1（高低杠）和项目2（平衡木）的比赛，队员9参加了项目3（跳马）和项目4（自由体操）的比赛；或队员1，4，7，8参加全能比赛，此外还有队员2参加了项目3（跳马）的比赛，队员3参加了项目1（高低杠）和项目4（自由体操）的比赛，队员5参加了项目2（平衡木）的比赛，队员6参加了项目1（高低杠）和项目2（平衡木）的比赛，队员9参加了项目3（跳马）和项目4（自由体操）的比赛。团体总分为236.4的阵容，队员1，4，7，8参加全能比赛，此外还有队员2参加了项目3（跳马）的比赛，队员3参加了项目1（高低杠）和项目4（自由体操）的比赛，队员5参加了项目4（自由体操）的比赛，队员6参加了项目1（高低杠）和项目2（平衡木）的比赛，队员9参加了项目2（平衡木）和项目3（跳马）的比赛.或队员4，7，8，9参加全能比赛，此外还有队员1参加了项目2（平衡木）和项目3（跳马）和项目4（自由体操）的比赛，队员2参加了项目3（跳马）的比赛，队员3参加了项目1（高低杠）的比赛，队员5参加了项目4（自由体操）的比赛，队员6参加了项目1（高低杠）和项目2（平衡木）的比赛.或队员1，4，8，9参加全能比赛，此外还有队员2参加了项目3（跳马）的比赛，队员3参加了项目1（高低杠）和项目4（自由体操）的比赛，队员5参加了项目4（自由体操）的比赛，队员6参加了项目2（平衡木）的比赛，队员7参加了项目1（高低杠）和项目2（平衡木）的比赛，队员10参加了项目3（跳马）的比赛。团体总分为236.5的阵容，即队员4，7，8，9参加全能比赛，此外还有队员1参加了项目2（平衡木）和项目3（跳马）的比赛，队员2参加了项目3（跳马）的比赛，队员3参加了项目1（高低杠）和项目4（自由体操）的比赛，队员5参加了项目4（自由体操）的比赛，队员6参加了项目1（高低杠）和项目2（平衡木）的比赛。 总结分析： 团体总分大于等于236.2的共有8个阵容。1、阵容一问题2（1）阵容一参赛表2.1.1项目参赛队员总分1247836236.2224781632478194247835阵容一概率分布图 12、阵容二问题2（1）阵容二参赛表2.1.2项目参赛队员总分1134827236.2213486731348294134879 阵容二概率分布图23、阵容三问题2（1）阵容三参赛表2.1.3项目参赛队员总分1134827236.3213486731348294134859阵容三概率分布图34、阵容四问题2（1）阵容四参赛表2.1.4项目参赛队员总分1147836236.3214785631478294147839 阵容四概率分布图45、阵容五问题2（1）阵容五参赛表2.1.5项目参赛队员总分1147836236.4214786931478294147835阵容五概率分布图56、阵容六问题2（1）阵容六参赛表2.1.6项目参赛队员总分1749836236.4274981637498124749815阵容六概率分布图67、 阵容七 问题2（1）阵容七参赛表2.1.7项目参赛队员总分1149837236.42149876314981024149835阵容七概率分布图78、阵容八问题2（1）阵容八参赛表2.1.8项目参赛队员总分1749836236.5274981637498124749835阵容八概率分布图8 分析上列阵容的得分和概率分布情况可知，阵容八的分值最高且得分概率最大，所以阵容八为最佳阵容。该队为了夺冠应排出的阵容就是阵容八。5.2.2 问题二（2）的分析与求解分析阵容八的图表，可得出有：得分概率为0.1的几率：（13/24）*100%=54%；得分概率为0.2的几率：（8/24）*100%=33%；得分概率为0.3的几率：（2/24）*100%=8%；得分概率为0.4的几率：（1/24）*100%=4%.所以其夺冠前景为：54%*0.1+33%*0.2+8%*0.3+4%*0.4=16%5.2.3 问题二（3）的分析与求解要得出阵容八的得分前景即参赛选手各单项得分期望值的总分。首先把阵容八的参赛选手各单项得分的期望值算出。经Excel软件处理得出参赛选手各单项得分按期望值估算下的总分。（见表2.11）阵容八的期望得分表（表