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

《数学建模最佳阵容问题附程序代码.doc》由会员分享，可在线阅读，更多相关《数学建模最佳阵容问题附程序代码.doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、- -最正确阵容问题摘要 本文针对女子体操团体赛中最正确出场阵容的问题。我们通过对赛程规定和数据的分析，合理的列出了目标函数和约束条件，特别对第二问的目标函数使用中心极限定理使目标函数简化。建立了以0-1整数规划为核心的数学模型，针对第一问分别使用贪心算法和0-1规划确定全能运发动。使用lingo对模型进展求解。最后很好的给出了不同情况下出场阵容的最正确方案，由概率知识可容易的求出夺冠概率0和得分期望224.6，有90%的把握可战胜平均成绩为222.7249的对手。得出下面的具体结果。总分全能运发动非全能运发动上下杠平衡木跳马体操问题一最悲观模型一212.21，2，5，67，104，84，83

2、，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最后，对模型进展了优缺点分析，并对模型提出了改进的方法。关键词 贪心算法 0-1规划 中心极限法 一、 问题分析 每个队至多允许10名运发动参赛，每个工程可以有6名选手参加，每个运发动只能四项全参加或只参加单项比赛这两类中的一类，参加单项比赛的每个运发动至多只能参加三个单项.每个队应有4人参加全能比赛，其

3、余运发动可参加单项比赛.问题一：1. 每个选手的各单项得分按最悲观估算，排出一个出场阵容，使该队团体总分尽可能高。2. 每个选手的各单项得分按均值估算，排出一个出场阵容，使该队团体总分尽可能高。需要先确定4个全能运发动，考虑使用贪心算法确定，然后再使用1个0-1变量进展0-1整型规划，使用lingo求解确定剩余6个人的出场阵容。但贪心算法只能找到局部最优解，于是考虑使用2个0-1变量也可用lingo进展求解，可以使结果更加优化。问题二：1.求出一个出场阵容使该队总分不少于236.2分的概率最大，以该阵容出战，其夺冠的前景如何，得分期望值又如何。2. 按以上阵容出战，它有90的把握战胜得分为多少

4、的对手。要使一个出场阵容夺冠的概率最大，也可使用问题一的0-1整型规划，但此时发现目标函数过于复杂，使用lingo无法实现。于是考虑对目标函数进展合理的化简，由于各场比赛之间可以看作是相互独立的事件服从正态分布，因此我们选择使用中心极限定理对目标函数进展简化，之后再使用lingo进展求解即可。此时的夺冠前景、得分期望，和它有90的把握战胜得分为多少的对手均可使用概率学知识进展求解。二、 符号说明第j个运发动在参加第i个工程的分数。为0，1变量，0代表第j个运发动不参加第i个工程，1代表第j个参加第i个工程。为0，1变量，0代表第j个运发动不是全能选手，1代表第j个运发动是全能选手。为第j个运发

5、动参加i的平均得分。代表每个工程，取值范围为1，2，3，4。代表每个选手，取值范围为1，2，3，4，5，6，7，8，9，10。代表第j个选手参加第i个工程的方差。三、 问题假设1假设所给的数据能代表选手的平常水平。2假设选手在比赛时各工程得分概率遵循测试水平。3假设选手没有特殊情况的发生，均能参加比赛。4前一项比赛成绩不影响后一项的成绩。5每个比赛之间相互独立。 四、模型与求解 1、问题一的模型及求解结果模型一：针对问题一可先使用贪心算法先确定4个全能选手，在得分最悲观估计和均值估计的前提下，使4项得分总和高的4个为全能选手，最后确定最悲观估计下4个全能选手为1，2，5，6；均值估计情况下4个

6、全能选手是5，8，9，10然后再对剩余6个人安排使用0-1整型规划，最终求解出最正确出场阵容。目标函数：约束条件：1每个工程至多有2人参加(i=1,2,3,4)2每个人至多参加3项 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

7、个参加全能运发动，但每个运发动四项之和差距并不大，得到的最正确出场阵容也只是局部最优解，可能不是全局最优解。为抑制这一缺点，我们考虑在模型二中使用2个0-1变量进展整型规划。目标函数：约束条件：1每个工程至多有6人参加(i=1,2,3,4)2每个人至多参加3项 j=1.103比赛需要有4个四项全能求解结果：悲观估计下的最正确阵容全能运发动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、 问题二

8、的模型及求解结果 求夺冠概率最大的阵容即求的最大值运用中心极限定理将随机变量转化为正态分布运用结论1得运用结论2得对于服从标准正态分布的随即变量Y，为增函数，所以可将求的最大值转化为求k的最小，即目标函数为求k的最小值.只需将第一问模型二在均值估计情况下目标函数改为即可得出结果所以夺冠的概率如果取每位队员的最好成绩然后选出的最正确队伍最好成绩为236.6分才能够夺冠。90的把握战胜怎样的对手即求的值标准化查标准正态分布表得 在求目标二的第一小问时在lingo程序中只需添加一条语句就可算出所以有90的把握战胜平均分不大于222.7249分的对手.求解结果：夺冠概率最大的阵容全能运发动3，5，9，

9、10非全能运发动上下杠6，7平衡木1，8跳马1，4体操6，8以该阵容出战夺冠的概率最大，夺冠的概率，得分的期望为224.6分，以上面阵容出战有90的把握战胜分数为222.7249分的对手。五、 模型的优缺点优点：模型很好的解决了阵容安排问题，使得在不同前提下，团体得分最高。可用于其它类似选择问题如场地的选择，车辆的安排等等的推广。模型综合考虑了各个队员的得分情况，先使用贪心算法和1个0-1矩阵，可以快速确定4个全能运发动。然后再巧妙的运用两个0-1矩阵，将各种约束用具体的式子表现出来，并建立了合理的0-1整数规划模型，在面对求解最大概率的时候，将其转换为下线最小值的求解问题，运用中心极限定理，

10、结合标准正态分布，思路清醒，让人理解透彻.另外，本解对问题的考察较全面，求解的结果具有精准性。缺点：由于Lingo的限制，只能得到一个最优解和一个最正确阵容。而事实上可能存在有最优解时，有不同的阵容。这样不有利于模型的推广，难以应付现实生活中的突发情况，可采用Matlab进展0-1规划求解。六、 模型的改进和推广可用于其它类似选择问题如场地的选择，车辆的安排，在NBA赛季的最正确阵容的选拔等等的推广。可采用Matlab进展0-1规划求解，这样可以在得到最优解的情况下，得到不同的方案，这样可以满足突发情况下的变动。附程序：先贪心算法：model:sets: xiangmu/A B C D/; d

11、uiyuan/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

12、,j):bin(f(i,j);end2个0-1变量：model:sets: xiangmu/A B C D/; 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个

13、人参加;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)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.49

14、99.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.0180.1440.0180.14250.1520.1580.0320.038;enddata!max=(

15、236.2-sum(links(i,j):f(i,j)*Q(i,j)/(sum(links(i,j):(f(i,j)*D(i,j)0.5);!Qmax=sum(links(i,j):S(i,j)*f(i,j)-1.28*(sum(links(i,j):(D(i,j)*f(i,j)0.5);Qmax=sum(links(i,j):f(i,j)*Q(i,j)-1.28*(sum(links(i,j):D(i,j)*f(i,j)(0.5);min=(236.2-sum(links(i,j):f(i,j)*Q(i,j)/(sum(links(i,j):D(i,j)*f(i,j)(0.5);E=sum(links(i,j):f(i,j)*Q(i,j);for(links(i,j):f(i,j)=Z(j);sum(xuanshou(j):Z(j)=4;for(xiangmu(i):sum(links(i,j):f(i,j)=6);for(xuanshou(j):sum(links(i,j):(1-Z(j)*f(i,j)=3);for(links(i,j):bin(f(i,j);for(xuanshou(j):bin(Z(j);end- word.zl-