2004研究生數(shù)學(xué)建模競賽優(yōu)秀論文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圓錐軸線旋轉(zhuǎn)方案5.2黃球定位概率的定義和計算6參考文獻(xiàn)1問題的描述及簡化本題是黃球的發(fā)現(xiàn)與定位問題，其中被探測的黃球到紅球和藍(lán)球的距離之和小于常數(shù)40，那么對一對紅，藍(lán)球而言，能檢測到的空間范圍是以該紅，藍(lán)球所在位置為焦點，長軸長為40的旋轉(zhuǎn)橢球體。對底面的所有紅，藍(lán)球，任意一對紅，藍(lán)球，只要其距離小于40，都可以形成一個探測橢球體，所有的紅藍(lán)球在一起就構(gòu)成了一個探測橢球陣，現(xiàn)在就是要設(shè)計紅，藍(lán)球的個數(shù)及位置，使得橢球陣至少能夠覆蓋圓柱內(nèi)的所有點。首先將問題進(jìn)行簡化，我們給出以下假設(shè)：1．紅、藍(lán)球探測角速度可以忽略不計；2．紅、藍(lán)、黃球的體積可以忽略不計；3．紅、藍(lán)球的探測波束為一直線；在做了以上假設(shè)后可以將該問題用幾何描述為：有一個半徑為50m，高為10m的圓柱體，該柱體與一個橢球陣相交，這個橢球陣內(nèi)的橢球滿足長軸長度小于等于20m，橢球的焦點在圓柱體的底面，且關(guān)于焦點連線旋轉(zhuǎn)對稱，每個橢球有一個焦點被圖成紅色、另一個焦點被圖成藍(lán)色，當(dāng)同色焦點重合時可示為一個焦點，那么此時若保證黃球在圓柱體內(nèi)任意位置都可能被檢測到，也即要求該橢圓陣能夠至少一次無縫覆蓋圓柱體，同樣，若保證黃球在圓柱體內(nèi)任意位置都可能被定位，也即要求該橢圓陣能夠至少三次無縫覆蓋圓柱體。2問題的分析定理一：橢圓陣能夠無縫覆蓋圓柱體一次的充要條件是：橢球陣在圓柱柱頂?shù)慕幻婺軌驘o縫覆蓋圓柱頂面一次。證明：必要性：假設(shè)A點為圓柱柱頂上的任意一點，那么A點肯定包含在某個橢球內(nèi)，假設(shè)該橢球的兩個焦點分別是、，則A點肯定滿足，過A點做圓柱地面的垂線交于B點，取線上任意一點，如圖所示，則有因此有：圖1定理1證明示意圖此時，可以得出點亦在以、為焦點的橢球內(nèi)。即只要點在范圍之內(nèi)，那么連線上任意一點都在范圍之內(nèi)，不難得出結(jié)論：假如橢球陣在圓柱柱頂?shù)慕幻婺軌驘o縫覆蓋圓柱柱頂，那么也一定能夠包含整個圓柱體。充分性：因為橢球陣能包含整個圓柱體，因此其在圓柱柱頂?shù)慕幻姹啬馨瑘A柱頂面。推論：橢圓陣能夠無縫覆蓋圓柱體次的充要條件是：橢球陣在圓柱柱頂?shù)慕幻婺軌驘o縫覆蓋圓柱頂面次。定理二：與圓柱體底面平行且高度為（，其中為橢球的短軸長度）的平面與橢球的切面一定是個橢圓，并且其長短軸與橢球長短軸成比例，該比例系數(shù)為。證明：假設(shè)橢球的表達(dá)式為：那么高為的平面與它的交平面為：從該表達(dá)式中不難看出，該切面是個橢圓，且其長、短軸與橢球長短軸成比例，該比例系數(shù)為。根據(jù)定理一及其推論，我們可以將題目轉(zhuǎn)化如何設(shè)計如何對焦點的位置進(jìn)行設(shè)計并著色，使得其能用盡量少的紅藍(lán)焦點數(shù)目來獲得能夠次無縫覆蓋頂圓的問題。3模型的建立由于移動通信中的系統(tǒng)設(shè)計問題已經(jīng)被研究的很成熟了，因此對本題目焦點位置的設(shè)計及著色問題我們可以借鑒移動通信中的基站位置及頻率配置的設(shè)計方案來解決。首先我們對移動通信中的基站位置及頻率配置的設(shè)計思路做一個簡單的描述如下：早期的移動通信其容量需求較低，采用的是大區(qū)制移動通信系統(tǒng)，該大區(qū)包含了所有頻率，以達(dá)到該區(qū)內(nèi)容量最高。但當(dāng)總?cè)萘啃枨笤黾訒r，它就不能通過增加頻率以達(dá)到增加容量需求的目的。因此需要找到一種系統(tǒng)結(jié)構(gòu)滿足隨著容量需求的增長，其基站的數(shù)目可能會增加，從而提高額外的容量，但不會增加額外的功率。當(dāng)前的移動通信系統(tǒng)設(shè)計中采用了蜂窩的概念，其思想是用許多蜂窩（正六邊形）來覆蓋整個區(qū)域，將基站放置在正六邊形的中心或者頂點，并用頻率復(fù)用的策略來解決頻率配置問題。在這里為了更好的理解頻率復(fù)用的含義，我們引入簇的概念。在蜂窩系統(tǒng)的設(shè)計中共同使用全部可用頻率的N個小區(qū)稱為一簇，如圖2所示，形成一簇至少需要三個頻率，稱N為簇的大小。N的值體現(xiàn)了移動臺或基站可以承受的干擾。從設(shè)計觀點來看N取可能的最小值是最好的，目的是為了獲得某一給定覆蓋范圍上的最大容量。蜂窩系統(tǒng)中定義頻率復(fù)用因子為1/N，因為一個簇中的每個小區(qū)都只分配給系統(tǒng)中所有可用信道的1/N。圖2蜂窩頻率復(fù)用基本思想圖解（標(biāo)有相同字母的小區(qū)使用相同的頻率）。小區(qū)簇的外圍輪廓用粗線描過，本例中簇的大小N=7，頻率復(fù)用因子為1/7。下表給出了這兩種設(shè)計問題的名詞關(guān)系：表1名詞對應(yīng)關(guān)系表本題的系統(tǒng)設(shè)計只被次覆蓋的區(qū)域面積被多過次覆蓋的區(qū)域面積焦點只要求被1次覆蓋（雙頻）：紅色、藍(lán)色只要求被3次覆蓋（四頻）：紅色、紅色、紅色、藍(lán)色移動通信中的系統(tǒng)設(shè)計容量干擾基站頻率或藍(lán)色、藍(lán)色、藍(lán)色、紅色一個焦點所配置顏色的數(shù)目功率（注：計算頻率的準(zhǔn)則是當(dāng)左右焦點重合時，次覆蓋需要的最少焦點個數(shù)）參照蜂窩網(wǎng)的設(shè)計思路，對本題我們給出以下設(shè)計方案：第一種情況當(dāng)圓柱頂面小于紅藍(lán)焦點重合形成的球面時，進(jìn)行次覆蓋所需要的焦點個數(shù)為對應(yīng)的頻率個數(shù)，見表1。其位置都在圓柱底面的圓心位置。（參照早期大區(qū)制移動通信網(wǎng)的設(shè)計）值得說明的是，這里給出了設(shè)計指導(dǎo)原則，對于1次覆蓋的問題，1對焦點重合的紅、藍(lán)球可以發(fā)現(xiàn)黃球。對于3次覆蓋問題，考慮到實際中三種同色球的焦點不便于完全重合，否則無法形成3個方位來完成空間定位，對此可適當(dāng)微調(diào)3個同色球焦點，使它們相互錯開即可。如3個同色球位于等邊三角形頂點上，1個異色球位于中心點上。第二種情況當(dāng)圓柱頂面大于紅藍(lán)焦點重合形成的球面時，參照現(xiàn)代移動蜂窩網(wǎng)的設(shè)計思想，我們給出以下步驟：第一步：將圓柱頂面所在平面用蜂窩小區(qū)分割，焦點放在小區(qū)中心。第二步：將分割得到的小區(qū)內(nèi)的焦點用最小簇著色。第三步：求出滿足頂圓剛好被次覆蓋時的小區(qū)半徑，從而確定小區(qū)大小。第四步：根據(jù)使焦點數(shù)目最少的原則，確定頂圓在蜂窩區(qū)內(nèi)的圓心。最少球數(shù)的搜索步驟：(1)初始化蜂窩區(qū)域成單個小區(qū)（正六邊形）；基準(zhǔn)圓：半徑R0，圓心與單個小區(qū)重合；(2)若整個蜂窩區(qū)域能完全覆蓋圓周，則轉(zhuǎn)向（3），否則小區(qū)均勻向四周擴(kuò)張一層，繼續(xù)執(zhí)行（2）；(3)計算蜂窩區(qū)域內(nèi)所有的紅，藍(lán)球?qū)π纬傻奶綔y橢球陣與圓柱頂面的相交面的最大內(nèi)切圓半徑Rmax，顯然有；(4)圓心在方向上向外移動，知道蜂窩區(qū)域不能完全覆蓋圓周，最大移動，統(tǒng)計蜂窩區(qū)域中完全不在基準(zhǔn)圓內(nèi)的小區(qū)個數(shù)；(5)尋找（4）中小區(qū)個數(shù)的最大值，及其對應(yīng)的球個數(shù)，用總球數(shù)減去該球數(shù)即得到最少球數(shù)目。第五步：若有焦點在頂圓外的情況，則通過邊際處理將焦點移至頂圓內(nèi)部，其中如何處理可以參照蜂窩移動通信中的邊際處理方式。對于本題我們采用如下邊際處理方式：(6)首先把不在圓內(nèi)的紅藍(lán)球順著它們到圓心的方向移動到圓周上，觀察是否完成3次覆蓋，如果完成了3次覆蓋，則結(jié)束；(7)如果沒有完成，則沒有完成的區(qū)域一定分布在圓周附近，我們把這種區(qū)域稱為縫隙，按照我們放置紅藍(lán)球的規(guī)則，縫隙一定是關(guān)于某些軸對稱；(8)把縫隙兩邊的圓周上(9)的紅藍(lán)球向著縫隙方向移動一定的角度，觀察是否能完成3次覆蓋(10)如果有某些角度能完成3次覆蓋，則結(jié)束，給出角度的范圍(11)如果沒有角度能完成3次覆蓋，則必須增加紅藍(lán)球的數(shù)目本題需要移動的角度范圍在（1.5,2.5）度之間。4模型的求解由于紅藍(lán)焦點重合時在頂面形成的球面半徑是m，小于50m的圓柱頂圓半徑，因此方案中的第一種情況可以不用考慮，下面僅針對第二種情況進(jìn)行討論。4.1問題一求解一次覆蓋時最少的顏色方案是2個，即藍(lán)、紅兩色，那么它組成最小簇的數(shù)目是3，其配色方案如下所示：圖3分簇方案示意圖（記左邊的為簇1，右邊的為簇2）不同的簇可以得到不同的著色方案，現(xiàn)在我們分情況討論。4.1.1簇1著色方案分析該著色方案下圓內(nèi)一簇中的覆蓋情況如下圖所示：圖4簇1著色方案示意圖記為小區(qū)半徑，為圓柱的高。由于該簇的對稱形，故若滿足三角區(qū)域被無縫覆蓋一次也能保證所形成的簇能夠被無縫覆蓋，從圖中不難看出若滿足被一次覆蓋則必須滿足橢圓1與橢圓4交點在橢圓2橢圓3內(nèi)，根據(jù)他們的對稱性也即滿足原點在橢圓4之內(nèi)，此時有：解得：對本題，，，此時即剛好覆蓋時滿足根據(jù)模型建立中的方案設(shè)計步驟，對圓心進(jìn)行搜索，并對邊際進(jìn)行處理后，得到的焦點數(shù)目為19個，配置分布圖如下：①③②圖5滿足至少一次無縫覆蓋時的焦點分布及配色方案圖和覆蓋的灰度圖圖中，①，②，③號球的顏色紅，藍(lán)皆可。則紅球最少為7個，最多為12個，藍(lán)球亦然。4.1.2簇2著色方案分析該著色方案下圓內(nèi)一簇中的覆蓋情況如下圖所示：圖6簇1著色方案示意圖記為小區(qū)半徑，為圓柱的高，為橢圓1的半焦距。由于該簇的對稱性，只需要滿足對圖中所示三角區(qū)至少無縫覆蓋一次就可以了，這個區(qū)域在該簇內(nèi)至少需要、、、這四個焦點組成的橢球在頂平面的交面來覆蓋，分別記為橢圓1、橢圓2和橢圓3。若要使橢圓1、橢圓2和橢圓3能將三角區(qū)無縫覆蓋，則必須保證橢圓1與軸的交點在橢圓2、3之內(nèi)。由于橢圓2、3是關(guān)于y軸對稱的，因此只需要保證在橢圓3之內(nèi)。在圖中建立的坐標(biāo)系中，的坐標(biāo)為橢圓1的方程為根據(jù)以上分析則需要滿足以下不等式：時上式成立，此時：。則能剛好滿足無縫覆蓋一次，此時所成的橢球經(jīng)過無球區(qū)在頂端投影的中心點，且該點為橢球在頂端投影所得橢圓的短軸頂點，因此得到方程：此時解得。根據(jù)模型建立中的方案設(shè)計步驟，對圓心進(jìn)行搜索，并對邊際進(jìn)行處理后，得到的焦點數(shù)目為24個，配置分布圖如下：圖7滿足至少三次無縫覆蓋時的焦點分布及配色方案圖和覆蓋的灰度圖兩種方案比較可以得出此時使用簇1進(jìn)行著色時，使用的焦點數(shù)目較少為19個。但由圖可見，此時圓的半徑還可以增大，即可以覆蓋更大的區(qū)域，計算得半徑約為51.96。當(dāng)半徑為51.96時，用簇I著色，圓面不能完全被覆蓋，需要再增加焦點，按最小球數(shù)搜索算法得到至少需要23個焦點。表2問題一求解結(jié)果4.2問題二求解著色方案簇1簇2小區(qū)半徑14.5024焦點個數(shù)191024問題二實際上是如何設(shè)計焦點位置及著色方案使其能以最少數(shù)目三次無縫覆蓋頂圓，我們同樣可以用模型建立中提到的方案來解決這個問題。由表1可以知道三次覆蓋時最少的顏色方案是紅色、紅色、紅色、藍(lán)色或藍(lán)色、藍(lán)色、藍(lán)色、紅色，那么他們能組成最小簇的方案有兩種，個數(shù)分別是4或12，如圖所示：圖8分簇方案示意圖（記左邊的為簇1，右邊的為簇2）4.2.1簇1著色方案分析該著色方案下圓內(nèi)一簇中的覆蓋情況如下圖所示：圖9簇1著色方案示意圖記為小區(qū)半徑，為圓柱的高。由于該簇的對稱形，需要滿足原心在橢圓4內(nèi)：即解得：，取。按照與問題1中設(shè)計的搜索圓心及邊際處理后得到以下焦點配置圖：圖10簇1配置方案下滿足至少三次無縫覆蓋時的焦點分布及配色方案圖和覆蓋的灰度圖4.2.2簇2著色方案分析該著色方案下圓內(nèi)一簇中的覆蓋情況如下圖所示：圖11簇2著色方案示意圖由圖中可以看出若對圖中所示區(qū)域進(jìn)行三次覆蓋，至少需要橢圓1和橢圓2的交點在橢圓6之內(nèi)，在如圖所示的坐標(biāo)系中，假設(shè)的坐標(biāo)為，則有以下方程組：解得，，按照與問題1中設(shè)計的搜索圓心及邊際處理后得到以下焦點配置圖：圖12簇2配置方案下滿足至少三次無縫覆蓋時的焦點分布及配色方案圖和覆蓋的灰度圖此時共有34個焦點。其中紅球為16個，藍(lán)球為18個，或者紅球為18個，藍(lán)球為16個。到此將第二問的結(jié)果列成表為，從表中可以看出是采用簇1進(jìn)行配置需要37個焦點，采用簇2進(jìn)行配置需要34個。表問題二求解結(jié)果著色方案小區(qū)半徑焦點個數(shù)簇1簇211.37649.611833734圖13小圓柱等效示意圖當(dāng)考慮到小區(qū)以波束掃描，且黃球被看成球時，對底面上的球以圓錐掃描時，如圖13所示，軸AB不需要掃描到圓邊上就可以覆蓋到整個圓，所以等效為區(qū)域圓半徑縮小為；同時由于黃球的直徑，軸AB不需要射到頂面就可以檢測到頂面的球，所以等效為圓柱體高度縮小為。也即等效為焦點以直線在變小了的也即假如不將黃球看為質(zhì)點而且紅、藍(lán)球以圓錐而不是直線進(jìn)行掃描時，可以等效為焦點都以直線在變小了的圓柱體掃描，在該圓柱體內(nèi)的黃球都可以看成質(zhì)點，只要焦點所形成的橢球陣能夠無縫覆蓋變小了的圓柱，那么一定能夠在以圓錐掃描的原圓柱體內(nèi)掃描到任意一個位置的半徑為0.02m的黃球此時將第二問轉(zhuǎn)化為：怎樣對焦點進(jìn)行分布和配色能使在、的圓柱體內(nèi)內(nèi)的任何位置的黃球有可能被發(fā)現(xiàn)。此時根據(jù)定理一可將問題描述為如何設(shè)計焦點位置和著色方案來三次無縫覆蓋頂圓區(qū)域的問題，那么我們同樣可以采用問題一中所采用的處理方案。5問題三討論5.1圓錐軸線旋轉(zhuǎn)方案由定理1的推論可知，若底面的紅，藍(lán)球能夠?qū)μ幱陧斆嫒我馕恢玫狞S球定位，則對圓柱體內(nèi)的任意位置黃球都能夠定位，則只要黃球進(jìn)入圓柱體內(nèi)，按照問題2中的解，可以在不增加紅，藍(lán)球的數(shù)量，也不改變它們的位置的情況下，總可能對黃球定位。根據(jù)圖10和圖12中的灰度圖，將頂面分成若干個連續(xù)的封閉區(qū)域，每個區(qū)域灰度相同（也即被滿足定位條件的紅，藍(lán)球?qū)?shù)相同），對每個區(qū)域，總存在至少三對同樣的紅，藍(lán)球?qū)?，對該區(qū)域上任意一點定位?，F(xiàn)對每個區(qū)域向底面作投影，得到相應(yīng)的區(qū)域投影體，這些投影體將圓柱體作了無縫覆蓋。對某一區(qū)域內(nèi)點定位的紅，藍(lán)球?qū)?，肯定能對相?yīng)投影體內(nèi)的任意點定位，這樣圓柱體內(nèi)的任意點都可能被定位，則只要黃球進(jìn)入到圓柱體內(nèi)，就有可能被定位。要提高定位的概率，必須使得紅，藍(lán)球?qū)μ綔y完整個圓柱體所用的時間最小。要完成定位，至少需要3對紅，藍(lán)球?qū)?，需?－6個球，對于定位對數(shù)為3的區(qū)域，由哪幾個球定位是確定的，對對數(shù)大于3的區(qū)域，由哪些球定位可以進(jìn)行一定的選擇，對每一個球，其可以定位某幾個區(qū)域進(jìn)行定位，但不能同時對多個區(qū)域定位，對完全不同的紅，藍(lán)球?qū)?，可以同時對不同的區(qū)域定位。我們把灰度相同而且相互連通的園內(nèi)區(qū)域看作一項工作，把一個紅球或一個籃球看作一個工人。各個球的圓錐軸的旋轉(zhuǎn)方案可以轉(zhuǎn)換成以下問題：有n項工作由m個工人來完成，目標(biāo)：求最小完成時間。限制條件：每項工作由4－6工人的固定組合完成；每個工人可和他人組合完成一項或多項工作；一個工人不可同時進(jìn)行多項工作；部分工作必須由某些特定的組合完成；部分工作可有多種組合中的一種完成；完全不同的組合可以同時進(jìn)行不同的工作；這是一個多約束的最佳生產(chǎn)調(diào)度問題。從R＝11.3764的3次覆蓋方案的灰度圖中，我們可以看到，工作的數(shù)目相當(dāng)多，而且工作區(qū)域的形狀和面積都極不相同。完成一項工作的時間也各不相同，求解會相當(dāng)困難。而且，最優(yōu)解對應(yīng)的旋轉(zhuǎn)方案也必定相當(dāng)復(fù)雜，不方便應(yīng)用于實際的場合。為了簡化問題，我們考慮4個球一組（一紅三藍(lán)或者一藍(lán)三紅）星型放置，3次覆蓋一個正六邊形。要求球放置在正六邊形的中心，而且3個橢圓正好3次覆蓋正六邊形。解方程得到R＝9.61183m，需要的總球數(shù)為43個，其中藍(lán)球個數(shù)最少為18個。這樣，我們把工作的區(qū)域變?yōu)橐?guī)則的六邊形（圓的邊緣為六邊形的一部分），工作的數(shù)目大為減少，變?yōu)楹凸と艘粯佣?。而且能完成某一項工作的工人也只能是一該工作區(qū)域為中心的一組或者兩組。一組工人完成該項工作的時間也是一樣的（在圓的邊緣處會適當(dāng)減少）。那么我們的目標(biāo)簡化為對工人組的分配次數(shù)最少。最后得到工人的分配（即紅籃球的圓錐軸的旋轉(zhuǎn)方案）也會相當(dāng)簡單，某個工人的工作的最大區(qū)域為以它自己為中心的7個六邊形。經(jīng)過計算機(jī)搜索，我們得出的最少分配次數(shù)為N＝6?？紤]一組工人完成某項工作所需要的時間：為了簡化問題，我們把4個圓錐在高度為h的層上的形成的3次覆蓋的區(qū)域近似為一個圓，半徑為。把六邊形（邊長為R）分割成平行的帶狀，每個帶的寬度為2r，我們依次掃描帶狀區(qū)域。為了計算方便，我們把六邊形的工作區(qū)域近似為一個同等面積的正方形，邊長為，則帶狀相對與圓柱底面圓心的最大張角為掃描一個工作區(qū)的時間為。。隨著層高的降低，一組工人完成該項工作的時間越來越大。如下圖：當(dāng)高度h＝10m時，時間t=169.11s。當(dāng)高度h＝0.1m時，時間t=間為Nt。s。則掃描這個高度層需要的總時把4個圓錐在空間上相交形成的區(qū)域近似為一個半徑為r的球，那么每次只能掃描一個高度為2r的圓柱體。我們把整個圓柱體分為多個高度為2r的小圓柱。則掃描整個圓柱所需要的時間為其中，H＝10m，m，帶入上式中，可得總掃描時間T＝秒。黃球在圓柱體內(nèi)運動的最長路徑為，約為100.5m。則在圓柱體內(nèi)運行的時間為98.5~670s內(nèi)。整個掃描時間比這個時間大2～3個數(shù)量級?？偟膾呙钑r間之所以這么大，主要是因為當(dāng)h比較小的時候，4個圓錐形成的3次覆蓋的區(qū)域球的半徑特別小，導(dǎo)致在這個小圓柱體內(nèi)的掃描時間急劇增大。為了減少低層的掃描時間，我們可以調(diào)整紅籃球的配對原則，使得3次覆蓋的區(qū)域球的半徑變大。在低層，能覆蓋同一區(qū)域的紅籃球?qū)τ泻芏?，?yīng)該選擇那些圓錐軸線方向盡量傾斜的紅藍(lán)球?qū)?，?/p>