数学建模最佳阵容问题附程序代码

最佳阵容问题摘要本文针对女子体操团体赛中最佳出场阵容的问题。我们通过对赛程规定和已知数据的分析，合理的列出了目标函数和约束条件，特别对第二问的目标函数使用中心极限定理使目标函数简化。建立了以0-1整数规划为核心的数学模型，针对第一问分别使用贪心算法和0-1规划确定全能运动员。使用lingo对模型进行求解。最后很好的给出了不同情况下出场阵容的最佳方案，由概率知识可容易的求出夺冠概率（0）和得分期望（224.6），有90%的把握可战胜平均成绩为222.7249的对手。得出下面的具体结果。最后，对模型进行了优缺点分析，并对模型提出了改进的方法。关键词贪心算法0-1规划中心极限法总分全能运动员非全能运动员高低杠平衡木跳马体操问题一最悲观模型一212.21，2，5，67，104，84，83，9模型二212.32，5，6，97，104，81，43，10均值模型一224.65，8，9，106，73，41，42，3模型二225.12，3，9，106，75，81，45，8问题二夺冠阵容3，5，9，106，71，81，46，8夺冠前景0得分期望224.690%战胜对手水平222.7249一、问题分析每个队至多允许10名运动员参赛，每个项目可以有6名选手参加，每个运动员只能四项全参加或只参加单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加三个单项.每个队应有4人参加全能比赛，其余运动员可参加单项比赛.问题一：1.每个选手的各单项得分按最悲观估算，排出一个出场阵容，使该队团体总分尽可能高。2.每个选手的各单项得分按均值估算，排出一个出场阵容，使该队团体总分尽可能高。需要先确定4个全能运动员，考虑使用贪心算法确定，然后再使用1个0-1变量进行0-1整型规划，使用lingo求解确定剩余6个人的出场阵容。但贪心算法只能找到局部最优解，于是考虑使用2个0-1变量也可用lingo进行求解，可以使结果更加优化。问题二：1.求出一个出场阵容使该队总分不少于236.2分的概率最大，以该阵容出战，其夺冠的前景如何，得分期望值又如何。2.按以上阵容出战，它有90％的把握战胜得分为多少的对手。要使一个出场阵容夺冠的概率最大，也可使用问题一的0-1整型规划，但此时发现目标函数过于复杂，使用lingo无法实现。于是考虑对目标函数进行合理的化简，由于各场比赛之间可以看作是相互独立的事件服从正态分布，因此我们选择使用中心极限定理对目标函数进行简化，之后再使用lingo进行求解即可。此时的夺冠前景、得分期望，和它有90％的把握战胜得分为多少的对手均可使用概率学知识进行求解。二、符号说明ijQ第j个运动员在参加第i个项目的分数。ijf为0，1变量，0代表第j个运动员不参加第i个项目，1代表第j个参加第i个项目。)(jZ为0，1变量，0代表第j个运动员不是全能选手，1代表第j个运动员是全能选手。aveijQ为第j个运动员参加i的平均得分。i代表每个项目，取值范围为1，2，3，4。j代表每个选手，取值范围为1，2，3，4，5，6，7，8，9，10。ijD代表第j个选手参加第i个项目的方差。三、问题假设（1）假设所给的数据能代表选手的平常水平。（2）假设选手在比赛时各项目得分概率遵循测试水平。（3）假设选手没有特殊情况的发生，均能参加比赛。（4）前一项比赛成绩不影响后一项的成绩。（5）每个比赛之间相互独立。四、模型与求解1、问题一的模型及求解结果模型一：针对问题一可先使用贪心算法先确定4个全能选手，在得分最悲观估计和均值估计的前提下，使4项得分总和高的4个为全能选手，最后确定最悲观估计下4个全能选手为1，2，5，6；均值估计情况下4个全能选手是5，8，9，10然后再对剩余6个人安排使用0-1整型规划，最终求解出最佳出场阵容。目标函数：ijijijfQ*max4161约束条件：（1）每个项目至多有2人参加261jijf(i=1,2,3,4)（2）每个人至多参加3项341iijf（j=1,2,3,4,5,6）求解结果：悲观估计下的最佳阵容全能运动员1，2，5，6非全能运动员高低杠7，10平衡木4，8跳马4，8体操3，9此时团体总得分为212.2分。均值估计下的最佳阵容全能运动员5，8，9，10非全能运动员高低杠6，7平衡木3，4跳马1，4体操2，3此时团体总得分为224.6分模型二：模型一先使用贪心算法然后使用1个0-1变量进行整型规划，对最佳出场阵容进行求解，这样虽然可以快速确定4个参加全能运动员，但每个运动员四项之和差距并不大，得到的最佳出场阵容也只是局部最优解，可能不是全局最优解。为克服这一缺点，我们考虑在模型二中使用2个0-1变量进行整型规划。目标函数：ijijijfQ*max41101约束条件：（1）每个项目至多有6人参加661jijf(i=1,2,3,4)（2）每个人至多参加3项3))(1(*41jZfiij（j=1..10）（3）比赛需要有4个四项全能10,,2,1,4101jZjj求解结果：悲观估计下的最佳阵容全能运动员2，5，6，9非全能运动员高低杠7，10平衡木4，8跳马1，4体操3，10此时的团体总得分为212.3分。均值估计下的最佳阵容全能运动员2，3，9，10非全能运动员高低杠6，7平衡木5，8跳马1，4体操5，8此时的团体总得分为225.1分。2、问题二的模型及求解结果nnnnnnfDfDfDfffDYDfEfEfEfffEYEfffYfff21212121212121,,,：结论：结论则令两两相互独立设随机变量求夺冠概率最大的阵容即求2.23641101ijijijQfPp的最大值41101ijijijQf＝总分随机变量运用中心极限定理将随机变量Σ转化为正态分布运用结论1得41101ijaveijijQfEΣ运用结论2得41101ijijijDfDΣ41101411012.236ijijijijaveijijDfQfDEPpΣΣΣ41101411012.2361ijijijijaveijijDfQfΦ41101411012.236ijijijijaveijijDfQfk＝令)(1kpΦ则对于服从标准正态分布)1,0(~N的随即变量Y，)(ffYPΦ为增函数，所以可将求)(1kpΦ的最大值转化为求k的最小，即目标函数为求k的最小值.只需将第一问模型二在均值估计情况下目标函数改为41101411012.236minijijijijaveijijDfQf即可得出结果7.918504mink所以夺冠的概率0)7.918504(1Φp如果取每位队员的最好成绩然后选出的最佳队伍最好成绩为236.6分才能够夺冠。90％的把握战胜怎样的对手即%90ΣP求的值标准化%90ΣΣΣΣΣDEDEP%901ΣΣΦDE查标准正态分布表得9.028.1Φ28.1ΣΣDEΣΣDE28.1在求目标二的第一小问时在lingo程序中只需添加一条语句就可算出222.724928.1ΣΣDE所以有90％的把握战胜平均分不大于222.7249分的对手.求解结果：夺冠概率最大的阵容全能运动员3，5，9，10非全能运动员高低杠6，7平衡木1，8跳马1，4体操6，8以该阵容出战夺冠的概率最大，夺冠的概率0)7.918504(1Φp，得分的期望为224.6分，以上面阵容出战有90％的把握战胜分数为222.7249分的对手。五、模型的优缺点优点：模型很好的解决了阵容安排问题，使得在不同前提下，团体得分最高。可用于其它类似选择问题如场地的选择，车辆的安排等等的推广。模型综合考虑了各个队员的得分情况，先使用贪心算法和1个0-1矩阵，可以快速确定4个全能运动员。然后再巧妙的运用两个0-1矩阵，将各种约束用具体的式子表现出来，并建立了合理的0-1整数规划模型，在面对求解最大概率的时候，将其转换为下线最小值的求解问题，运用中心极限定理，结合标准正态分布，思路清醒，让人理解透彻.另外，本解对问题的考察较全面，求解的结果具有精准性。缺点：由于Lingo的限制，只能得到一个最优解和一个最佳阵容。而事实上可能存在有最优解时，有不同的阵容。这样不有利于模型的推广，难以应付现实生活中的突发情况，可采用Matlab进行0-1规划求解。六、模型的改进和推广可用于其它类似选择问题如场地的选择，车辆的安排，在NBA赛季的最佳阵容的选拔等等的推广。可采用Matlab进行0-1规划求解，这样可以在得到最优解的情况下，得到不同的方案，这样可以满足突发情况下的变动。附程序：先贪心算法：model:sets:xiangmu/ABCD/;duiyuan/1..6/;canjia(xiangmu,duiyuan):Q,f;endsetsdata:!可以直接复制表格，但是在最后要有分号;Q=8.48.19.58.48.498.18.78.48.88.48.18.498.38.78.48.29.58.48.48.29.39.1;enddatamax=@sum(canjia(i,j):Q(i,j)*f(i,j));!每个项目最多2个人参加;@for(xiangmu(i):@sum(canjia(i,j):f(i,j))2);!每人至多参加3项;@for(duiyuan(j):@sum(canjia(i,j):f(i,j))3);@for(canjia(i,j):@bin(f(i,j)));end2个0-1变量：model:sets:xiangmu/ABCD/;duiyuan/1..10/:b;canjia(xiangmu,duiyuan):Q,f;endsetsdata:!可以直接复制表格，但是在最后要有分号;Q=8.49.38.48.18.49.49.58.48.498.48.48.18.798.78.48.88.48.19.18.48.498.38.58.38.78.48.28.78.99.58.49.48.48.48.29.39.1;enddatamax=@sum(canjia(i,j):Q(i,j)*f(i,j));!每个项目最多6个人参加;@for(xiangmu(i):@sum(canjia(i,j):f(i,j))6);!每人至多参加3项;@for(duiyuan(j):@sum(canjia(i,j):(1-b(j))*f(i,j))3);@for(canjia(i,j):f(i,j)b(j));@sum(duiyuan(j):b(j))=4;@for(canjia(i,j):@bin(f(i,j)));@for(duiyuan(j):@bin(b(j)));end第二问：model:sets:xiangmu/1..4/:;xuanshou/1..10/:Z;links(xiangmu,xuanshou):f,Q,D;endsetsdata:Q=9.259.699.19.259.79.899.259.4999.19.19.49.199.89.29.19.599.259.58.98.98.99.199.29.19.39.899.79.259.29.39.79.5;D=0.14250.0180.1440.1280.14250.0180.0180.1440.14250.0380.1440.080.1280.0880.0380.0880.1440.0840.1520.1280.0380.1440.14250.0380.0720.0320.0720.0880.1440.1280.0880.0380.0