基于最佳阵容问题

基于最佳阵容问题的0-1整数规划摘要本文研究的是体操比赛最佳阵容的问题，采用0-1整数规划，根据运动员不同的得分情况，得到相应的目标函数，结合问题的约束条件建立模型，运用Lingo软件求解得出结果。对于问题一，在最悲观估计的前提下，可得到每个运动员的最悲观得分表，由此建立模型1，得到最高总分为212.3分；在均值得分情况下，可得到每个运动员的均值得分表，由此建立模型2，得到最高总得分为225.1分；两种情况下的最佳阵容安排如下表（1-10表示运动员的编号）：全能选手单项选手高低杠平衡木跳马自由体操模型12、5、6、97、104、81、41、10模型22、3、9、106、75、81、45、8对于问题二，在总分不低于236.2分的情况下，运用概率论知识建立模型3，解得夺冠阵容安排如下：全能选手为：3、8、9、10；单项选手：高低杠：6、7，平衡木：1、5，跳马：1、4，自由体操：5、7。此时夺冠的前景为：；得分前景为：224.5；有90%的把握战胜总分少于222.5分的对手。 在当今这个更注重团体比赛的时代，对出场阵容的安排是团队获胜的一个重要因素，因而本文的模型具有较好的实用性和通用性。关键词：0-1整数规划 Lingo软件 正态分布 中心极限定理一 问题重述 一场由四个项目（高低杠、平衡木、跳马、自由体操）组成的女子体操团体赛，赛程规定为：（1）每个队至多允许10名运动员参赛，（2）每一个项目可以有6名选手参加，（3）每个运动员只能参加全能比赛（四项全参加）与单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加三个单项，（4）每个队应有4人参加全能比赛，其余运动员参加单项比赛,（5）每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者。现某代表队的教练已经对其所带领的10名运动员参加各个项目的成绩进行了大量测试，并得到4个稳定的各项得分及概率分布表，见附表1。问题:1、每个选手的各单项得分按最悲观估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高；每个选手的各单项得分按均值估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高。2、若对以往的资料及近期各种信息进行分析得到：本次夺冠的团体总分估计为不少于236.2分，该队为了夺冠应排出怎样的阵容，以该阵容出战，其夺冠的前景如何，得分前景（即期望值）又如何，它有90的把握战胜怎样水平的对手。二 问题分析最佳阵容即团体总分最高，要使总得分最高，必须尽可能多的参加项目，因此每个项目需有6名运动员参加，其中4名为全能比赛者。1. 对于问题一的分析：a) 在每个选手的各单项得分按最悲观估算的前提下，排出出场阵容使该团体总分尽可能高。最悲观估算即先取每个运动员各项成绩的最低分，组成最悲观得分表，见下表1(将各个项目进行编号：1高低杠，2平衡木，3跳马，4自由体操)。表1 最悲观得分表1234567891018.49.38.48.18.49.49.58.48.4928.48.48.18.798.78.48.88.48.139.18.48.498.38.58.38.78.48.248.78.99.58.49.48.48.48.29.39.1b) 在每个选手的各单项得分按均值估算的前提下，排出出场阵容使该团体总分尽可能高。各单项得分按均值估算得均值得分表，见下表2。表2 均值得分表1234567891019.259.699.19.259.79.899.259.42999.19.19.49.199.89.29.139.599.259.58.98.98.99.199.249.19.39.899.79.259.29.39.79.52. 对于问题二的分析：运用概率论知识：独立性，中心极限定理，正态分布等将问题进行简化，根据问题要求，得出符合条件的目标函数，再结合约束条件，采用0-1整数规划，建立最优化模型，再运用Lingo软件对其进行最优化求解，其中每个运动员的每项成绩的方差得分表见下表3。表3 方差得分表1234567891010.20250.03500.35000.30000.20250.03500.03500.35000.20250.072520.35000.14000.30000.21000.07250.21000.35000.35000.29000.300030.07250.35000.20250.07500.14000.06000.14000.21000.35000.299840.21000.07250.03500.35000.03500.20250.34000.37500.06000.0725c) 运用概率论知识：独立性、中心极限定理、正态分布等，采用0-1整数规划，根据运动员不同的得分情况写出目标函数，结合比赛的约束条件，建立最优化模型，运用Lingo软件求得结果。三 模型假设1. 每个运动员在比赛中不会超长发挥或发挥失常，即数据真实有效；2. 在比赛中所有的仪器设备都正常工作，不会影响成绩记录；3. 比赛中的每位裁判都是公平公正的，不会影响比赛结果；4. 运动员的心理素质较好，每场比赛都相互独立。四 符号说明表4 符号说明符号 含义 10名运动员的编号 编号1,2,3,4依次对应为高低杠、平衡木、跳马、自由体操 第个运动员参加第个项目 第个运动员参加第个项目的比赛的最悲观得分 第个运动员参加第个项目的比赛的均值得分 第个运动员参加全能比赛 第个运动员参加第个项目的比赛得分方差 第个运动员参加第个项目的比赛得分 总分不少于236.2的概率 有90%的把握战胜的对手的分数五 模型的建立与求解5.1 问题一的模型与求解1. 最悲观估计的模型建立模型1：为了便于编程求解，现使用0-1规划来进行模型求解，特引入两个0-1变量，分别为： ； ；且此时每个运动员的成绩见最悲观得分表（表1）。目标函数： 约束条件：a) 4人参加全能比赛： b) 每个项目至多6人参加： c) 对于参加单项比赛的人，每人至多参加3个单项： 2. 均值估计的模型建立模型2：目标函数： 约束条件同模型13. 模型求解a) 按最悲观估计的求解结果运用Lingo软件求解得：总得分为212.3分，此时最佳阵容矩阵见下表5。表5 最悲观估计下的最佳阵容表1234567891010100111011201011101103110111001040110110011b) 按均值估计的模型求解结果此时的模型与最悲观估计的模型一样，其中每个运动员的成绩见均值得分表（表2）。运用Lingo软件求得：总得分为225.1分，此时最佳阵容矩阵见下表6。 表6 按均值估计的最佳阵容表12345678910101100110112011010011131111000011401101001115.2问题二的模型与求解1. 夺冠模型的建立要满足问题二夺冠的条件，可转化为求解总分不少于236.2的概率的最大值，即，令。由于每场比赛相互独立，可由独立同分布中心极限定理得： ，要使 p最大，即求的最小值。模型建立如下：运用Lingo软件求解得：目标值为5.，此时最佳阵容矩阵表见下表7。表7 夺冠最佳阵容表1234567891010010011111210101001113101100011140010101111由此可求得以此阵容出战的夺冠前景：，根据每个运动员的期望得分表（表2），可算得此时的得分前景为224.5。查正太分布表可知： ，若有90%的把握战胜总分为的对手，则即，此时求得，因此以夺冠阵容出战有90%的把握战胜总分低于222.5分的对手。六 模型分析与推广1. 模型分析模型综合考虑各个队员的得分情况及概率，根据问题的限制条件，给出合理的0-1整数规划的数学模型。在求解最大概率中，运用独立性、正态分布等，进行概率估算，并结合0-1整数规划进行合理的模型求解。该模型针对复杂的阵容选择问题，从排列组合的大量数据中跳出，运用0-1整数规划，将问题简化成简单的最优化问题，同时运用概率论将估算问题与最优化模型相结合，计算简便，思路清晰，易于理解。2. 模型推广该模型不仅能够很好的解决运动员出场最优阵容的安排问题，还能推广到生活中许多方面.例如生产人员的安排，证券、股票的投资，各种股票的价格等同于题中运动员的得分，股票收益的风险等同于本题中队员得分的概率，购买力等同于本题中参赛运