概率论在数模竞赛中的应用(共8页).doc

《概率论在数模竞赛中的应用(共8页).doc》由会员分享，可在线阅读，更多相关《概率论在数模竞赛中的应用(共8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上五、（2006年华东地区数学建模邀请赛第一题）乒乓赛问题A、B两乒乓球队进行一场五局三胜制的乒乓球赛，两队各派3名选手上场，并各有3种选手的出场顺序（分别记为和）。根据过去的比赛记录，可以预测出如果A队以次序出场而B队以次序出场，则打满5局A队可胜局。由此得矩阵如下：（1）根据矩阵能否看出哪一队的实力较强？（2）如果两队都采取稳妥的方案，比赛会出现什么结果？（3）如果你是A队的教练，你会采取何种出场顺序？ 首先要弄清楚：矩阵中的元素到底表示什么意思？是不是表示：如果A队以次序出场而B队以次序出场，A队在5局中可以百分之百保证一定会胜局？显然不是这个意思，比较合理的看法

2、，应该认为它只是对A队平均获胜局数的一个估计。当A队以次序出场、B队以次序出场时，设这时A队每一局比赛获胜的概率是一个不变的常数，并且假设各局是否获胜是相互独立的（实际上也许并不是这样，但是题目中给我们的信息太少，我们只能这样假设）。这样，5局比赛就是一个独立重复试验序列。 设是A队在5局比赛中获胜的局数，显然，服从二项分布，概率分布为， 。容易求得它的数学期望为 。 如果我们认为矩阵中元素给出的数据，不是完全确定的结果，而是估计A队在5局比赛中平均获胜的局数，则有 。这样，就可以得到的估计值 。对应于矩阵，我们可以得到这样一个矩阵 。要比较A，B两队实力的大小，可以比较两队在每一局比赛中获胜

3、的平均概率大小。矩阵中的9个元素，是在9种不同的出场次序下A队每局获胜的概率。假设这9种不同的出场次序出现的概率相同，都是，那么，根据全概率公式，就可以求出A队在每一局比赛中获胜的平均概率 ，这个概率超过了，也就是说，从每一局比赛来说，A队的实力比B队略微强一些。 以上是从每一局比赛获胜概率的大小来比较实力，但是，比赛实际上是五局三胜制，要在五局三胜制比赛中最后获胜，才是真正获胜。下面我们来计算在五局三胜制比赛中A队最后获胜的概率： A队最后获胜，可以分成下列几种情况：（1）A队连胜三局。这种情况的概率为 ；（2）在前三局中A队胜二局，最后A队又胜一局。这种情况的概率为 ；（3）在前四局中A队

4、胜二局，最后A队又胜一局。这种情况的概率为 ； 把这三种情况加起来，就得到在五局三胜制比赛中A队最后获胜的概率 。根据以上公式，从矩阵 出发，可以计算出这样一个矩阵 。矩阵中元素表示：当A队以次序出场、B队以次序出场时，在五局三胜制比赛中A队最后获胜的概率（也就是B队最后失败的概率）。 如果两队都随机排阵，9种出场次序出现的可能性相等，都是，根据全概率公式，就可以算出A队在五局三胜制比赛中最后获胜的平均概率 。 这个数字大于，同样也说明A队的实力比较强。 下面来看，如果两队都采取稳妥的方案，比赛会出现什么结果？ 什么是“稳妥的方案”？我们的理解是：所谓“稳妥的方案”，就是对自己的每一种出场次序

5、，都考虑最坏的情况，求出在最坏的情况下，我方失败的概率是多少，然后在各种出场次序中，选择一种最坏情况下失败概率最小的出场次序，作为我方的排阵方案。 从矩阵 （其中的元素，是A队获胜的概率，也是B队失败的概率）可以看出：对于B队来说，采用出场次序时，最坏情况是A队采用出场次序，B队失败概率为；采用出场次序时，最坏情况是A队采用出场次序或，B队失败概率为；采用出场次序时，最坏情况是A队采用出场次序或，B队失败概率为。3个失败概率中，为最小，所以，B队最稳妥的方案是采用出场次序。对于A队来说，采用出场次序时，最坏情况是B队采用出场次序，A队获胜概率为；采用出场次序时，最坏情况是B队采用出场次序，A队

6、获胜概率为；采用出场次序，最坏情况是B队采用出场次序，A队获胜概率为。3个获胜概率中，为最大，所以，A队最稳妥的方案是采用出场次序或。那么，A队到底采用还是呢？如果A队预料到B队一定会采用最稳妥的出场次序，那么，这时A队采用，获胜的概率只有，A队采用，获胜的概率就会有，当然，A队应该采用。但是，如果B队又预料到A队会采用，那么，B队就不会采用失败概率为的，而是应该采用失败概率更小（失败概率为）的。 如果A队又预料到B队会采用，A队又会改变出场次序。这样的推理，可以无穷无尽地进行下去。其实，这是一个博弈论（Game Theory）中的两人零和博弈（Zero-Sum Two-Person Game

7、）问题。A队可以采用的3种出场次序，是A队可以采用的3种策略；B队可以采用的3种出场次序，是B队可以采用的3种策略。矩阵是A队的得分矩阵，也是B队的失分矩阵（支付矩阵Payout Matrix）。 当博弈的双方都只采用一种固定的策略（称为纯策略）时，两人零和博弈问题要得到一个稳定的解，矩阵中必须有一个鞍点（Saddle Point），即在同一列中取到最大值、又在同一行中取到最小值的元素。在矩阵中找不到这样的鞍点，所以，这个问题不可能有一个稳定的纯策略解。但是，在这种情况下，可以考虑混合策略解。所谓混合策略，就是博弈双方不是固定采用一种纯策略，而是以某种概率混合采用各种策略。设A队以概率采用策略

8、。因为是概率，所以必须满足，。设是A队采用这种混合策略时，不管B队采用什么策略，A队的得分（最后获胜概率）能够保证的最小值。由全概率公式可知，当B队采用纯策略时，A队的得分（最后获胜概率）为 ， 。因为是A队的得分（最后获胜概率）能够保证的最小值，所以必须有 ， 。 容易看出，只要上述不等式成立，当B队以某种概率混合采用各种策略时，A队的得分同样也可以保证大于，所以不必另外再列式子了。 A队的目标，是要使得这个能够保证的最小得分达到最大，所以，整个问题就可以表示成一个线性规划问题：目标函数 约束条件 。 解这个线性规划问题，可以求得：A队采用策略的概率应该分别为，当A队采用这种混合策略时，A队

9、能够保证的获胜概率为 。 对于B队，也可以列出类似的线性规划问题，正好是上述A队问题的对偶问题。解这个对偶的线性规划问题，可以求得：B队采用策略的概率应该分别为，当B队采用这种混合策略时，B队能够保证的获胜概率为 。 混合策略是以一定的概率混合采用各种策略，但是实际上，在一次具体的比赛中，必须取定其中的一种策略，到底取那一种呢？这又是一个值得研究的问题。六、（2000年国际数模竞赛A题）空中交通管理一个空中交通管理员，负责管理一个空中区域。现在的问题是：（1）为了避免区域中飞机发生碰撞，管理员在什么情况下，必须对飞机的飞行进行干涉处理？（2）从管理员工作量的角度来看，怎样测量空中交通管理的复杂

10、度？这个复杂度与区域中飞机的架数是什么关系？ 解决问题（1）的关键是：已知两架飞机现在的位置、飞行的方向和速度，判断这两架飞机会不会碰撞。这是一个物体运动问题，实际上，可以化为一个几何问题来求解，是比较容易解决的。因为我们主要关心的是概率论在数模竞赛中的应用，这个几何问题的解法就不在此详细讨论了。解决问题（2）的关键是：怎样计算管理员的工作量？管理员的工作量与他管理空中交通的工作方式有关。设想管理员用下列方式管理这个区域的空中交通：每当一架飞机进入区域时，就计算一下它会不会与现在已经在区域内的任何一架飞机发生碰撞。如果会发生碰撞，就调整一次它的飞行路线。调整后，再计算它会不会发生碰撞。如果会发

11、生碰撞，再调整一次它的飞行路线。调整后，再计算它会不会发生碰撞。这样一直进行下去，直到这架飞机不会与区域内任何一架飞机发生碰撞为止。 管理员的工作量由下列两部分组成：（1）计算是否碰撞：设一共要计算次，每一次计算的工作量为。（2）调整飞行路线：设一共要调整次（从上面的流程图可以看出，调整总是要比计算少1次），每一次调整的工作量为。 所以，每一架飞机进入区域，管理员的工作量为 ，平均工作量，即工作量的数学期望为 。 设是一架飞机进入区域时，它与区域内任何一架飞机都不碰撞的概率。从上面的流程图可以看出，完成这架飞机的飞行路线管理工作，保证这架飞机与区域内任何一架飞机都不碰撞，只需要计算1次的概率为

12、 ，完成这架飞机的飞行路线管理工作，需要计算2次，调整1次的概率为 ，完成这架飞机的飞行路线管理工作，需要计算3次，调整2次的概率为 ，一般地，完成这架飞机的飞行路线管理工作，需要计算次，调整次的概率为 。 由此可见，所需计算次数服从几何分布，即有，它的数学期望。 设是一架飞机进入区域时，它与区域内的某一架飞机不碰撞的概率。概率可以通过随机模拟的方法求出，具体做法是：在区域边界上随机地取一个点，作为进入区域的飞机的位置，随机地确定这架飞机飞入区域的飞行路线。再在区域内部随机地取一个点，作为区域内的飞机的位置，随机地确定这架飞机的飞行路线。然后判断这两架飞机会不会碰撞（在问题（1）的解答中已经给

13、出了判断方法）。这作为一次模拟试验。重复多次做这样的模拟试验，计算出飞机不碰撞的频率（即不碰撞的试验次数与总的试验次数之比）。随着试验次数越来越多，不碰撞的频率会越来越接近不碰撞的概率，这样，就得到了的近似值。 设区域内共有架飞机，作为近似，设这些飞机是相互独立的。由于一架飞机进入区域时，它与区域内的某一架飞机不碰撞的概率为，所以，一架飞机进入区域时，它与区域内架飞机中的任何一架飞机都不碰撞的概率为。 这样，就有 。 同时，上式中的也与有关。是一架飞机进入区域时，判断它是否与区域内架飞机都不碰撞所需的计算工作量。设是一架飞机进入区域时，判断它是否与区域内某一架飞机碰撞所需的计算工作量。显然应该

14、有 。所以， 。这只是一架飞机进入区域时管理员的平均工作量。要考虑空中交通管理的复杂度，不能只考虑这一架飞机进入时管理员的平均工作量，还要考虑管理员整个一天的平均工作量。设是一天24小时内进入区域的飞机总数，显然，一天的工作量应该是一架飞机进入时的工作量的倍，即有 。但也与区域内的飞机数有关。设一天24小时中的每一时刻，区域内的飞机数都近似是一个常数。设是平均每架飞机进入区域后，在区域内飞行的时间（可以用随机模拟的方法，求出的近似值）。则有 。因此有 。 我们把“空中交通管理的复杂度”定义为“管理员一天的平均工作量”。于是有空中交通管理的复杂度管理员一天的平均工作量 。因为，所以式子中的。作为的函数，复杂度的图像为从图像可以看出，空中交通管理的复杂度随着飞机架数的增加而增大，一开始，复杂度增大的速度不是很快，但随着越来越大，复杂度增大的速度会越来越快。专心-专注-专业