概率论在数模竞赛中的应用-4

18五、（2006年华东地区数学建模邀请赛第一题）乒乓赛问题A、B两乒乓球队进行一场五局三胜制的乒乓球赛，两队各派3名选手上场，并各有3种选手的出场顺序（分别记为321,,和321,,）。根据过去的比赛记录，可以预测出如果A队以i次序出场而B队以j次序出场，则打满5局A队可胜jia局。由此得矩阵)(jiaR如下：135430412321321R（1）根据矩阵R能否看出哪一队的实力较强？（2）如果两队都采取稳妥的方案，比赛会出现什么结果？（3）如果你是A队的教练，你会采取何种出场顺序？首先要弄清楚：矩阵R中的元素jia到底表示什么意思？是不是表示：如果A队以i次序出场而B队以j次序出场，A队在5局中可以百分之百保证一定会胜jia局？显然不是这个意思，比较合理的看法，应该认为它只是对A队平均获胜局数的一个估计。当A队以i次序出场、B队以j次序出场时，设这时A队每一局比赛获胜的概率是一个不变的常数jip，并且假设各局是否获胜是相互独立的（实际上也许并不是这样，但是题目中给我们的信息太少，我们只能这样假设）。这样，5局比赛就是一个独立重复试验序列。设是A队在5局比赛中获胜的局数，显然，服从二项分布),5(jipb，概率分布为kjikjikppCkP55)1(}{，5,,1,0k。容易求得它的数学期望为jipE5。如果我们认为矩阵R中元素jia给出的数据，不是完全确定的结果，而是估计A队在5局比赛中平均获胜的局数，则有jiajipE5。这样，就可以得到jip的估计值55jijiaEp。19对应于矩阵)(jiaR135430412，我们可以得到这样一个矩阵)(jipP2.06.018.06.008.02.04.0。要比较A，B两队实力的大小，可以比较两队在每一局比赛中获胜的平均概率大小。矩阵)(jipP中的9个元素，是在9种不同的出场次序下A队每局获胜的概率。假设这9种不同的出场次序出现的概率相同，都是91，那么，根据全概率公式，就可以求出A队在每一局比赛中获胜的平均概率511111.096.492.06.018.06.008.02.04.0，这个概率超过了5.0，也就是说，从每一局比赛来说，A队的实力比B队略微强一些。以上是从每一局比赛获胜概率的大小来比较实力，但是，比赛实际上是五局三胜制，要在五局三胜制比赛中最后获胜，才是真正获胜。下面我们来计算在五局三胜制比赛中A队最后获胜的概率：A队最后获胜，可以分成下列几种情况：（1）A队连胜三局。这种情况的概率为3jip；（2）在前三局中A队胜二局，最后A队又胜一局。这种情况的概率为)1(3)1(3223jijijijijipppppC；（3）在前四局中A队胜二局，最后A队又胜一局。这种情况的概率为232224)1(6)1(jijijijijipppppC；把这三种情况加起来，就得到在五局三胜制比赛中A队最后获胜的概率jiq2333)1(6)1(3jijijijijippppp)]21(6)1(31[23jijijijipppp)61510(23jijijippp。根据以上公式，从矩阵)(jipP2.06.018.06.008.02.04.0出发，可以计算出这样一个矩阵05792.068256.0194208.068256.0094208.005792.031744.0)(jiqQ。矩阵Q中元素jiq表示：当A队以i次序出场、B队以j次序出场时，在五局三胜制20比赛中A队最后获胜的概率（也就是B队最后失败的概率）。如果两队都随机排阵，9种出场次序出现的可能性相等，都是91，根据全概率公式，就可以算出A队在五局三胜制比赛中最后获胜的平均概率905792.068256.0194208.068256.0094208.005792.031744.0520284.0。这个数字大于5.0，同样也说明A队的实力比较强。下面来看，如果两队都采取稳妥的方案，比赛会出现什么结果？什么是“稳妥的方案”？我们的理解是：所谓“稳妥的方案”，就是对自己的每一种出场次序，都考虑最坏的情况，求出在最坏的情况下，我方失败的概率是多少，然后在各种出场次序中，选择一种最坏情况下失败概率最小的出场次序，作为我方的排阵方案。从矩阵05792.068256.0194208.068256.0094208.005792.031744.0)(321321jiqQ（其中的元素jiq，是A队获胜的概率，也是B队失败的概率）可以看出：对于B队来说，采用出场次序1时，最坏情况是A队采用出场次序3，B队失败概率为1；采用出场次序2时，最坏情况是A队采用出场次序2或3，B队失败概率为68256.0；采用出场次序3时，最坏情况是A队采用出场次序1或2，B队失败概率为94208.0。3个失败概率中，68256.0为最小，所以，B队最稳妥的方案是采用出场次序2。对于A队来说，采用出场次序1时，最坏情况是B队采用出场次序2，A队获胜概率为05792.0；采用出场次序2时，最坏情况是B队采用出场次序1，A队获胜概率为0；采用出场次序3，最坏情况是B队采用出场次序3，A队获胜概率为05792.0。3个获胜概率中，05792.0为最大，所以，A队最稳妥的方案是采用出场次序1或3。那么，A队到底采用1还是3呢？如果A队预料到B队一定会采用最稳妥的出场次序2，那么，这时A队采用1，获胜的概率只有05792.0，A队采用3，获胜的概率就会有68256.0，当然，A队应该采用3。但是，如果B队又预料到A队会采用3，那么，B队就不会采用失败概率为68256.0的2，而是应该采用失败概率更小（失败概率为05792.0）的3。21如果A队又预料到B队会采用3，A队又会改变出场次序。……。这样的推理，可以无穷无尽地进行下去。其实，这是一个博弈论（GameTheory）中的两人零和博弈（Zero-SumTwo-PersonGame）问题。A队可以采用的3种出场次序321,,，是A队可以采用的3种策略；B队可以采用的3种出场次序321,,，是B队可以采用的3种策略。矩阵)(jiqQ是A队的得分矩阵，也是B队的失分矩阵（支付矩阵PayoutMatrix）。当博弈的双方都只采用一种固定的策略（称为纯策略）时，两人零和博弈问题要得到一个稳定的解，矩阵)(jiqQ中必须有一个鞍点（SaddlePoint），即在同一列中取到最大值、又在同一行中取到最小值的元素。在矩阵)(jiqQ中找不到这样的鞍点，所以，这个问题不可能有一个稳定的纯策略解。但是，在这种情况下，可以考虑混合策略解。所谓混合策略，就是博弈双方不是固定采用一种纯策略，而是以某种概率混合采用各种策略。设A队以概率321,,xxx采用策略321,,。因为321,,xxx是概率，所以必须满足1321xxx，01x，02x，03x。设z是A队采用这种混合策略时，不管B队采用什么策略，A队的得分（最后获胜概率）能够保证的最小值。由全概率公式可知，当B队采用纯策略j时，A队的得分（最后获胜概率）为332211xqxqxqjjj，3,2,1j。因为z是A队的得分（最后获胜概率）能够保证的最小值，所以必须有332211xqxqxqjjjz，3,2,1j。容易看出，只要上述不等式成立，当B队以某种概率混合采用各种策略时，A队的得分同样也可以保证大于z，所以不必另外再列式子了。A队的目标，是要使得这个能够保证的最小得分达到最大，所以，整个问题就可以表示成一个线性规划问题：目标函数zmax约束条件0,0,01321321333223113332222112331221111xxxxxxzxqxqxqzxqxqxqzxqxqxq。解这个线性规划问题，可以求得：A队采用策略321,,的概率应该分别为235987.01x，303772.02x，460241.03x，22当A队采用这种混合策略时，A队能够保证的获胜概率为535135.0z。对于B队，也可以列出类似的线性规划问题，正好是上述A队问题的对偶问题。解这个对偶的线性规划问题，可以求得：B队采用策略321,,的概率应该分别为378901.01y，192556.02y，428543.03y，当B队采用这种混合策略时，B队能够保证的获胜概率为464865.0z。混合策略是以一定的概率混合采用各种策略，但是实际上，在一次具体的比赛中，必须取定其中的一种策略，到底取那一种呢？这又是一个值得研究的问题。六、（2000年国际数模竞赛A题）空中交通管理一个空中交通管理员，负责管理一个空中区域。现在的问题是：（1）为了避免区域中飞机发生碰撞，管理员在什么情况下，必须对飞机的飞行进行干涉处理？（2）从管理员工作量的角度来看，怎样测量空中交通管理的复杂度？这个复杂度与区域中飞机的架数是什么关系？解决问题（1）的关键是：已知两架飞机现在的位置、飞行的方向和速度，判断这两架飞机会不会碰撞。这是一个物体运动问题，实际上，可以化为一个几何问题来求解，是比较容易解决的。因为我们主要关心的是概率论在数模竞赛中的应用，这个几何问题的解法就不在此详细讨论了。解决问题（2）的关键是：怎样计算管理员的工作量？管理员的工作量与他管理空中交通的工作方式有关。设想管理员用下列方式管理这个区域的空中交通：每当一架飞机进入区域时，就计算一下它会不会与现在已经在区域内的任何一架飞机发生碰撞。如果会发生碰撞，就调整一次它的飞行路线。调整后，再计算它会不会发生碰撞。如果会发生碰撞，再调整一次它的飞行路线。调整后，再计算它会不会发生碰撞。……。这样一直进行下去，直到这架飞机不会与区域内任何一架飞机发生碰撞为止。23管理员的工作量由下列两部分组成：（1）计算是否碰撞：设一共要计算次，每一次计算的工作量为1W。（2）调整飞行路线：设一共要调整1次（从上面的流程图可以看出，调整总是要比计算少1次），每一次调整的工作量为2W。所以，每一架飞机进入区域，管理员的工作量为22121)()1(，平均工作量，即工作量W的数学期望为221)(WEWWEW。设p是一架飞机进入区域时，它与区域内任何一架飞机都不碰撞的概率。从上面的流程图可以看出，完成这架飞机的飞行路线管理工作，保证这架飞机与区域内任何一架飞机都不碰撞，只需要计算1次的概率为pP}1{，完成这架飞机的飞行路线管理工作，需要计算2次，调整1次的概率为ppP)1(}2{，完成这架飞机的飞行路线管理工作，需要计算3次，调整2次的概率为ppP2)1(}3{，……，一般地，完成这架飞机的飞行路线管理工作，需要计算k次，调整1k次的概率为ppkPk1)1(}{。由此可见，所需计算次数服从几何分布，即有～)(pg，它的数学期望pE1。设0p是一架飞机进入区域时，它与区域内的某一架飞机不碰撞的概率。概率0p可以通过随机模拟的方法求出，具体做法是：在区域边界上随机地取一个点，作为进入区域的飞机的位置，随机地确定这架飞机飞入区域的飞行路线。再在区域内部随机地取一个点，作为区域内的飞机的位置，随机地确定这架飞机的飞行路线。然后判断这两架飞机会不会碰撞（在问题（1）的解答中已经给出了判断方法）。这作为一次模拟试验。重复多次做这样的模拟试验，计算出飞机不碰撞的频率（即不碰撞的试验次数与总的试验次数之比）。随着试验次数越来越多，不碰撞的频率会越来越接近不碰撞的概率0p，这样，就得到了0p的近似值。设区域内共有N架飞机，作为近似，设这些飞机是相互独立的。由于一架飞机