2004研究生数学建模竞赛优秀论文A题

目录1问题的描述及简化2问题的分析3模型的建立4模型的求解4.1问题一求解4.1.1簇1着色方案4.1.2簇2着色方案4.2问题二求解4.2.1簇1着色方案4.2.2簇2着色方案5问题三讨论5.1圆锥轴线旋转方案5.2黄球定位概率的定义和计算6参考文献1问题的描述及简化本题是黄球的发现与定位问题，其中被探测的黄球到红球和蓝球的距离之和小于常数40，那么对一对红，蓝球而言，能检测到的空间范围是以该红，蓝球所在位置为焦点，长轴长为40的旋转椭球体。对底面的所有红，蓝球，任意一对红，蓝球，只要其距离小于40，都可以形成一个探测椭球体，所有的红蓝球在一起就构成了一个探测椭球阵，现在就是要设计红，蓝球的个数及位置，使得椭球阵至少能够覆盖圆柱内的所有点。首先将问题进行简化，我们给出以下假设：1．红、蓝球探测角速度可以忽略不计；2．红、蓝、黄球的体积可以忽略不计；3．红、蓝球的探测波束为一直线；在做了以上假设后可以将该问题用几何描述为：有一个半径为50m，高为10m的圆柱体，该柱体与一个椭球阵相交，这个椭球阵内的椭球满足长轴长度小于等于20m，椭球的焦点在圆柱体的底面，且关于焦点连线旋转对称，每个椭球有一个焦点被图成红色、另一个焦点被图成蓝色，当同色焦点重合时可示为一个焦点，那么此时若保证黄球在圆柱体内任意位置都可能被检测到，也即要求该椭圆阵能够至少一次无缝覆盖圆柱体，同样，若保证黄球在圆柱体内任意位置都可能被定位，也即要求该椭圆阵能够至少三次无缝覆盖圆柱体。2问题的分析定理一：椭圆阵能够无缝覆盖圆柱体一次的充要条件是：椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱顶面一次。证明：必要性：假设A点为圆柱柱顶上的任意一点，那么A点肯定包含在某个椭球内，假设该椭球的两个焦点分别是、，则A点肯定满足，过A点做圆柱地面的垂线交于B点，取线上任意一点，如图所示，则有因此有：图1定理1证明示意图此时，可以得出点亦在以、为焦点的椭球内。即只要点在范围之内，那么连线上任意一点都在范围之内，不难得出结论：假如椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱柱顶，那么也一定能够包含整个圆柱体。充分性：因为椭球阵能包含整个圆柱体，因此其在圆柱柱顶的交面必能包含圆柱顶面。推论：椭圆阵能够无缝覆盖圆柱体次的充要条件是：椭球阵在圆柱柱顶的交面能够无缝覆盖圆柱顶面次。定理二：与圆柱体底面平行且高度为（，其中为椭球的短轴长度）的平面与椭球的切面一定是个椭圆，并且其长短轴与椭球长短轴成比例，该比例系数为。证明：假设椭球的表达式为：那么高为的平面与它的交平面为：从该表达式中不难看出，该切面是个椭圆，且其长、短轴与椭球长短轴成比例，该比例系数为。根据定理一及其推论，我们可以将题目转化如何设计如何对焦点的位置进行设计并着色，使得其能用尽量少的红蓝焦点数目来获得能够次无缝覆盖顶圆的问题。3模型的建立由于移动通信中的系统设计问题已经被研究的很成熟了，因此对本题目焦点位置的设计及着色问题我们可以借鉴移动通信中的基站位置及频率配置的设计方案来解决。首先我们对移动通信中的基站位置及频率配置的设计思路做一个简单的描述如下：早期的移动通信其容量需求较低，采用的是大区制移动通信系统，该大区包含了所有频率，以达到该区内容量最高。但当总容量需求增加时，它就不能通过增加频率以达到增加容量需求的目的。因此需要找到一种系统结构满足随着容量需求的增长，其基站的数目可能会增加，从而提高额外的容量，但不会增加额外的功率。当前的移动通信系统设计中采用了蜂窝的概念，其思想是用许多蜂窝（正六边形）来覆盖整个区域，将基站放置在正六边形的中心或者顶点，并用频率复用的策略来解决频率配置问题。在这里为了更好的理解频率复用的含义，我们引入簇的概念。在蜂窝系统的设计中共同使用全部可用频率的N个小区称为一簇，如图2所示，形成一簇至少需要三个频率，称N为簇的大小。N的值体现了移动台或基站可以承受的干扰。从设计观点来看N取可能的最小值是最好的，目的是为了获得某一给定覆盖范围上的最大容量。蜂窝系统中定义频率复用因子为1/N，因为一个簇中的每个小区都只分配给系统中所有可用信道的1/N。图2蜂窝频率复用基本思想图解（标有相同字母的小区使用相同的频率）。小区簇的外围轮廓用粗线描过，本例中簇的大小N=7，频率复用因子为1/7。下表给出了这两种设计问题的名词关系：表1名词对应关系表本题的系统设计只被次覆盖的区域面积被多过次覆盖的区域面积焦点只要求被1次覆盖（双频）：红色、蓝色只要求被3次覆盖（四频）：红色、红色、红色、蓝色移动通信中的系统设计容量干扰基站频率或蓝色、蓝色、蓝色、红色一个焦点所配置颜色的数目功率（注：计算频率的准则是当左右焦点重合时，次覆盖需要的最少焦点个数）参照蜂窝网的设计思路，对本题我们给出以下设计方案：第一种情况当圆柱顶面小于红蓝焦点重合形成的球面时，进行次覆盖所需要的焦点个数为对应的频率个数，见表1。其位置都在圆柱底面的圆心位置。（参照早期大区制移动通信网的设计）值得说明的是，这里给出了设计指导原则，对于1次覆盖的问题，1对焦点重合的红、蓝球可以发现黄球。对于3次覆盖问题，考虑到实际中三种同色球的焦点不便于完全重合，否则无法形成3个方位来完成空间定位，对此可适当微调3个同色球焦点，使它们相互错开即可。如3个同色球位于等边三角形顶点上，1个异色球位于中心点上。第二种情况当圆柱顶面大于红蓝焦点重合形成的球面时，参照现代移动蜂窝网的设计思想，我们给出以下步骤：第一步：将圆柱顶面所在平面用蜂窝小区分割，焦点放在小区中心。第二步：将分割得到的小区内的焦点用最小簇着色。第三步：求出满足顶圆刚好被次覆盖时的小区半径，从而确定小区大小。第四步：根据使焦点数目最少的原则，确定顶圆在蜂窝区内的圆心。最少球数的搜索步骤：(1)初始化蜂窝区域成单个小区（正六边形）；基准圆：半径R0，圆心与单个小区重合；(2)若整个蜂窝区域能完全覆盖圆周，则转向（3），否则小区均匀向四周扩张一层，继续执行（2）；(3)计算蜂窝区域内所有的红，蓝球对形成的探测椭球阵与圆柱顶面的相交面的最大内切圆半径Rmax，显然有；(4)圆心在方向上向外移动，知道蜂窝区域不能完全覆盖圆周，最大移动，统计蜂窝区域中完全不在基准圆内的小区个数；(5)寻找（4）中小区个数的最大值，及其对应的球个数，用总球数减去该球数即得到最少球数目。第五步：若有焦点在顶圆外的情况，则通过边际处理将焦点移至顶圆内部，其中如何处理可以参照蜂窝移动通信中的边际处理方式。对于本题我们采用如下边际处理方式：(6)首先把不在圆内的红蓝球顺着它们到圆心的方向移动到圆周上，观察是否完成3次覆盖，如果完成了3次覆盖，则结束；(7)如果没有完成，则没有完成的区域一定分布在圆周附近，我们把这种区域称为缝隙，按照我们放置红蓝球的规则，缝隙一定是关于某些轴对称；(8)把缝隙两边的圆周上(9)的红蓝球向着缝隙方向移动一定的角度，观察是否能完成3次覆盖(10)如果有某些角度能完成3次覆盖，则结束，给出角度的范围(11)如果没有角度能完成3次覆盖，则必须增加红蓝球的数目本题需要移动的角度范围在（1.5,2.5）度之间。4模型的求解由于红蓝焦点重合时在顶面形成的球面半径是m，小于50m的圆柱顶圆半径，因此方案中的第一种情况可以不用考虑，下面仅针对第二种情况进行讨论。4.1问题一求解一次覆盖时最少的颜色方案是2个，即蓝、红两色，那么它组成最小簇的数目是3，其配色方案如下所示：图3分簇方案示意图（记左边的为簇1，右边的为簇2）不同的簇可以得到不同的着色方案，现在我们分情况讨论。4.1.1簇1着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：图4簇1着色方案示意图记为小区半径，为圆柱的高。由于该簇的对称形，故若满足三角区域被无缝覆盖一次也能保证所形成的簇能够被无缝覆盖，从图中不难看出若满足被一次覆盖则必须满足椭圆1与椭圆4交点在椭圆2椭圆3内，根据他们的对称性也即满足原点在椭圆4之内，此时有：解得：对本题，，，此时即刚好覆盖时满足根据模型建立中的方案设计步骤，对圆心进行搜索，并对边际进行处理后，得到的焦点数目为19个，配置分布图如下：①③②图5满足至少一次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图图中，①，②，③号球的颜色红，蓝皆可。则红球最少为7个，最多为12个，蓝球亦然。4.1.2簇2着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：图6簇1着色方案示意图记为小区半径，为圆柱的高，为椭圆1的半焦距。由于该簇的对称性，只需要满足对图中所示三角区至少无缝覆盖一次就可以了，这个区域在该簇内至少需要、、、这四个焦点组成的椭球在顶平面的交面来覆盖，分别记为椭圆1、椭圆2和椭圆3。若要使椭圆1、椭圆2和椭圆3能将三角区无缝覆盖，则必须保证椭圆1与轴的交点在椭圆2、3之内。由于椭圆2、3是关于y轴对称的，因此只需要保证在椭圆3之内。在图中建立的坐标系中，的坐标为椭圆1的方程为根据以上分析则需要满足以下不等式：时上式成立，此时：。则能刚好满足无缝覆盖一次，此时所成的椭球经过无球区在顶端投影的中心点，且该点为椭球在顶端投影所得椭圆的短轴顶点，因此得到方程：此时解得。根据模型建立中的方案设计步骤，对圆心进行搜索，并对边际进行处理后，得到的焦点数目为24个，配置分布图如下：图7满足至少三次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图两种方案比较可以得出此时使用簇1进行着色时，使用的焦点数目较少为19个。但由图可见，此时圆的半径还可以增大，即可以覆盖更大的区域，计算得半径约为51.96。当半径为51.96时，用簇I着色，圆面不能完全被覆盖，需要再增加焦点，按最小球数搜索算法得到至少需要23个焦点。表2问题一求解结果4.2问题二求解着色方案簇1簇2小区半径14.5024焦点个数191024问题二实际上是如何设计焦点位置及着色方案使其能以最少数目三次无缝覆盖顶圆，我们同样可以用模型建立中提到的方案来解决这个问题。由表1可以知道三次覆盖时最少的颜色方案是红色、红色、红色、蓝色或蓝色、蓝色、蓝色、红色，那么他们能组成最小簇的方案有两种，个数分别是4或12，如图所示：图8分簇方案示意图（记左边的为簇1，右边的为簇2）4.2.1簇1着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：图9簇1着色方案示意图记为小区半径，为圆柱的高。由于该簇的对称形，需要满足原心在椭圆4内：即解得：，取。按照与问题1中设计的搜索圆心及边际处理后得到以下焦点配置图：图10簇1配置方案下满足至少三次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图4.2.2簇2着色方案分析该着色方案下圆内一簇中的覆盖情况如下图所示：图11簇2着色方案示意图由图中可以看出若对图中所示区域进行三次覆盖，至少需要椭圆1和椭圆2的交点在椭圆6之内，在如图所示的坐标系中，假设的坐标为，则有以下方程组：解得，，按照与问题1中设计的搜索圆心及边际处理后得到以下焦点配置图：图12簇2配置方案下满足至少三次无缝覆盖时的焦点分布及配色方案图和覆盖的灰度图此时共有34个焦点。其中红球为16个，蓝球为18个，或者红球为18个，蓝球为16个。到此将第二问的结果列成表为，从表中可以看出是采用簇1进行配置需要37个焦点，采用簇2进行配置需要34个。表问题二求解结果着色方案小区半径焦点个数簇1簇211.37649.611833734图13小圆柱等效示意图当考虑到小区以波束扫描，且黄球被看成球时，对底面上的球以圆锥扫描时，如图13所示，轴AB不需要扫描到圆边上就可以覆盖到整个圆，所以等效为区域圆半径缩小为；同时由于黄球的直径，轴AB不需要射到顶面就可以检测到顶面的球，所以等效为圆柱体高度缩小为。也即等效为焦点以直线在变小了的也即假如不将黄球看为质点而且红、蓝球以圆锥而不是直线进行扫描时，可以等效为焦点都以直线在变小了的圆柱体扫描，在该圆柱体内的黄球都可以看成质点，只要焦点所形成的椭球阵能够无缝覆盖变小了的圆柱，那么一定能够在以圆锥扫描的原圆柱体内扫描到任意一个位置的半径为0.02m的黄球此时将第二问转化为：怎样对焦点进行分布和配色能使在、的圆柱体内内的任何位置的黄球有可能被发现。此时根据定理一可将问题描述为如何设计焦点位置和着色方案来三次无缝覆盖顶圆区域的问题，那么我们同样可以采用问题一中所采用的处理方案。5问题三讨论5.1圆锥轴线旋转方案由定理1的推论可知，若底面的红，蓝球能够对处于顶面任意位置的黄球定位，则对圆柱体内的任意位置黄球都能够定位，则只要黄球进入圆柱体内，按照问题2中的解，可以在不增加红，蓝球的数量，也不改变它们的位置的情况下，总可能对黄球定位。根据图10和图12中的灰度图，将顶面分成若干个连续的封闭区域，每个区域灰度相同（也即被满足定位条件的红，蓝球对数相同），对每个区域，总存在至少三对同样的红，蓝球对，对该区域上任意一点定位。现对每个区域向底面作投影，得到相应的区域投影体，这些投影体将圆柱体作了无缝覆盖。对某一区域内点定位的红，蓝球对，肯定能对相应投影体内的任意点定位，这样圆柱体内的任意点都可能被定位，则只要黄球进入到圆柱体内，就有可能被定位。要提高定位的概率，必须使得红，蓝球对探测完整个圆柱体所用的时间最小。要完成定位，至少需要3对红，蓝球对，需要4－6个球，对于定位对数为3的区域，由哪几个球定位是确定的，对对数大于3的区域，由哪些球定位可以进行一定的选择，对每一个球，其可以定位某几个区域进行定位，但不能同时对多个区域定位，对完全不同的红，蓝球对，可以同时对不同的区域定位。我们把灰度相同而且相互连通的园内区域看作一项工作，把一个红球或一个篮球看作一个工人。各个球的圆锥轴的旋转方案可以转换成以下问题：有n项工作由m个工人来完成，目标：求最小完成时间。限制条件：每项工作由4－6工人的固定组合完成；每个工人可和他人组合完成一项或多项工作；一个工人不可同时进行多项工作；部分工作必须由某些特定的组合完成；部分工作可有多种组合中的一种完成；完全不同的组合可以同时进行不同的工作；这是一个多约束的最佳生产调度问题。从R＝11.3764的3次覆盖方案的灰度图中，我们可以看到，工作的数目相当多，而且工作区域的形状和面积都极不相同。完成一项工作的时间也各不相同，求解会相当困难。而且，最优解对应的旋转方案也必定相当复杂，不方便应用于实际的场合。为了简化问题，我们考虑4个球一组（一红三蓝或者一蓝三红）星型放置，3次覆盖一个正六边形。要求球放置在正六边形的中心，而且3个椭圆正好3次覆盖正六边形。解方程得到R＝9.61183m，需要的总球数为43个，其中蓝球个数最少为18个。这样，我们把工作的区域变为规则的六边形（圆的边缘为六边形的一部分），工作的数目大为减少，变为和工人一样多。而且能完成某一项工作的工人也只能是一该工作区域为中心的一组或者两组。一组工人完成该项工作的时间也是一样的（在圆的边缘处会适当减少）。那么我们的目标简化为对工人组的分配次数最少。最后得到工人的分配（即红篮球的圆锥轴的旋转方案）也会相当简单，某个工人的工作的最大区域为以它自己为中心的7个六边形。经过计算机搜索，我们得出的最少分配次数为N＝6。考虑一组工人完成某项工作所需要的时间：为了简化问题，我们把4个圆锥在高度为h的层上的形成的3次覆盖的区域近似为一个圆，半径为。把六边形（边长为R）分割成平行的带状，每个带的宽度为2r，我们依次扫描带状区域。为了计算方便，我们把六边形的工作区域近似为一个同等面积的正方形，边长为，则带状相对与圆柱底面圆心的最大张角为扫描一个工作区的时间为。。随着层高的降低，一组工人完成该项工作的时间越来越大。如下图：当高度h＝10m时，时间t=169.11s。当高度h＝0.1m时，时间t=间为Nt。s。则扫描这个高度层需要的总时把4个圆锥在空间上相交形成的区域近似为一个半径为r的球，那么每次只能扫描一个高度为2r的圆柱体。我们把整个圆柱体分为多个高度为2r的小圆柱。则扫描整个圆柱所需要的时间为其中，H＝10m，m，带入上式中，可得总扫描时间T＝秒。黄球在圆柱体内运动的最长路径为，约为100.5m。则在圆柱体内运行的时间为98.5~670s内。整个扫描时间比这个时间大2～3个数量级。总的扫描时间之所以这么大，主要是因为当h比较小的时候，4个圆锥形成的3次覆盖的区域球的半径特别小，导致在这个小圆柱体内的扫描时间急剧增大。为了减少低层的扫描时间，我们可以调整红篮球的配对原则，使得3次覆盖的区域球的半径变大。在低层，能覆盖同一区域的红篮球对有很多，应该选择那些圆锥轴线方向尽量倾斜的红蓝球对，使