基站選址問題

基站選址問題摘要:本文采用集合的合并運算解決第一問。將實際問題轉(zhuǎn)化為0-1規(guī)劃問題，然后使用lingo進(jìn)行求解。在第一問中，選中2,4,6,7點為設(shè)置基站點，此時覆蓋的人數(shù)為109千人，占總?cè)藬?shù)的93.16%，建設(shè)費用為95百萬元。在第二問中，擴大了基站點的覆蓋范圍，這個問題仍然為集合合并運算，增加了新的邏輯運算后，就可以將新的覆蓋區(qū)域添加到模型中。求解后，基站的選擇點仍然為2,4,6,7。此時的覆蓋人數(shù)為111.8千人，占總?cè)藬?shù)的95.56%，覆蓋人數(shù)比模型一增長了2.57%（摘要可以再增加一些東西，你看著來吧）關(guān)鍵詞基站選址選址問題集合合并問題重述這個我不寫了，問題的重述就是寫讀了題后，你對問題的理解，這個不是問題分析。只是重新復(fù)述一下問題，但是切忌照抄原題，這是不允許的。一定要寫讀題后對問題的理解全文結(jié)構(gòu)我已經(jīng)做好了，不知道你那里能不能看到那些headings,我用的是office2010，不知道你能不能看到，但是這個結(jié)構(gòu)基本可以不動了，直接填東西就可以了。正文是小四，標(biāo)題是四號。二、 問題分析這部分寫問題分析，你先看一下后面的模型建立部分，明白了模型建立后就可以寫這問題分析了。只要點到了咱們的模型中的主要思想就可以了。具體建模過程在模型建立與求解部分寫，不用寫得太詳細(xì)。后面還有一個參考文獻(xiàn)沒有寫，你來寫吧。到這里主要需要你來添加的部分就沒有了，然后你來改一下后面的內(nèi)容吧。添加一些東西，或者修改一下語言。隨便怎么樣都可以。這次的文檔內(nèi)容比較少，這三個題都比較麻煩，只有第二題還容易點。畢竟是初賽嘛，可以馬虎一點。結(jié)構(gòu)也比較簡單，等到復(fù)賽的時候再好好做題。這道題就先這樣吧。第一問是肯定沒有任何問題的，第二問可能有點牽強，但是，如果包含的區(qū)域多了，那個邏輯就太復(fù)雜了，我已經(jīng)受不了了。三、 基本假設(shè)每一個社區(qū)內(nèi)的人均勻分布題中給出的數(shù)據(jù)中一個基站包含社區(qū)的時候是完全包含，不會只包含一部分在第二問中，可以假設(shè)基站的覆蓋范圍為一個近似的圓四、 符號說明Sj為第i個點是否安裝基站，的取值為0或1，0為不設(shè)置基站，1為設(shè)置基站q為第i個社區(qū)的人數(shù)為第i個基站的建設(shè)費用P-為每個基站覆蓋的總?cè)藬?shù)五、 模型建立與求解5.1問題一5.1.1模型的建立在這個模型中使用了集合運算性質(zhì)。三個集合的合并運算定義為Comp(A,B,C)=AUBUC—(AnB+AnC+BnC)+AnBnC?；镜母采w范圍類似集合的并集運算。在這里聲明了一些變量。Sj為第i個地點是否安裝基站，Sj的取值為0或1,0代表不設(shè)置基站，1代表設(shè)置基站。q為第i個社區(qū)的人數(shù)。rnt為第i個基站的建設(shè)費用。所以當(dāng)選定要安置基站的位置后，相應(yīng)的基站建設(shè)費用就可以確定。而基站的建設(shè)費用不大于1億元，也就是100百萬元。所以有約束條件:m.s.<100(1)i=1可以設(shè)每個基站覆蓋的人口數(shù)量為久，則按照前面定義的集合合并運算的性質(zhì)。在問題中給出的數(shù)據(jù)可以知道，最多為三個基站的覆蓋范圍重合。通過集合合并運算就可以將兩個基站共同覆蓋的人口只計算一遍。例如，對于社區(qū)i,如果同時被基站j，k覆蓋，那么就可以用這樣的數(shù)學(xué)式子表示SjS/z。這個是兩個覆蓋區(qū)域重疊的項，如果Sj,同時為1,則代表應(yīng)當(dāng)刪除這個社區(qū)，以使得這個社區(qū)內(nèi)的人數(shù)只被計算了一次。所以，按照合并運算以及題中表格內(nèi)的數(shù)據(jù)可以寫出目標(biāo)函數(shù)。被覆蓋的人口為：max= p.s.i=1—(S1S2C2+S1S3C4+$2$4°5+S3S4C8+S3S5C8+^3S6(C7+C10)+S4S5(C8+C9)+S5S6C12+S5S7C12+^6^7("12+C15))+$3$4$5°8+S5S6S7C12(2)5.1.2模型的求解根據(jù)5.1.1中設(shè)計的模型，將模型輸入Lingo中進(jìn)行求解。公式(2)為目標(biāo)函數(shù)，公式⑴為約束條件，而且所有的應(yīng)該取值0或1。所以這是一個0-1規(guī)劃。Lingo經(jīng)過89次迭代后求的最后的結(jié)果。迭代過程非?？?。求得的結(jié)果總結(jié)如下：模型一求解結(jié)果

待定點位置Si$2$3S455$657基站設(shè)置情況0101011覆蓋人數(shù)109千人建設(shè)費用95百萬兀人口覆蓋率93.16%表1模型一的求解結(jié)果從求解結(jié)果中可以看出應(yīng)當(dāng)在位置S2，S4,S6，從求解結(jié)果中可以看出應(yīng)當(dāng)在位置S2，S4,S6，S7處設(shè)置基站，這樣就可以在1億元的預(yù)算內(nèi)使得人口覆蓋率達(dá)到了93.162%。從這里可以看出，這種設(shè)置方案還是比較好的，可以使絕大部分區(qū)域被覆蓋進(jìn)來。為了更清楚明白的看到覆蓋情況，下圖給出了采用表1的基站設(shè)置方案的效果。i?61C'2C5214136圖1覆蓋后的效果圖從圖1中可以看出，只有1,4沒有被覆蓋。而其他區(qū)域已經(jīng)完全被覆蓋。所以覆蓋效果還是很好的。事實上，由于1和4中的人口數(shù)量相對較少，即便1和4的區(qū)域比較大，這個模型依舊將1和4區(qū)域拋棄掉。圖中深色的部分為同時被兩個基站覆蓋的情況，其中社區(qū)5被基站2和4同時覆蓋，社區(qū)12和15被基站6和7同時覆蓋。重復(fù)覆蓋的區(qū)域總體不是很多。但是很容易看出，在這個問題中，基站的覆蓋范圍過于理想化。比如基站2還可以覆蓋社區(qū)1,4的一小部分，但是使用題目中的數(shù)據(jù)是沒有辦法考慮那部分范圍的。對于其他的各站也有類似的情況，也就是說，人口覆蓋率應(yīng)該更高。5.2問題二5.2.1模型二的建立題目第二問需要考慮表格中給出的每個基站設(shè)置點的覆蓋范圍以外的范圍。所以，在建立這個模型之前首先要對社區(qū)基站圖進(jìn)行定性的分析。由于每個基站的造價不同，覆蓋范圍也不同，無法給出統(tǒng)一的覆蓋范圍。但是，對于基站的覆蓋范圍是可以看作一個近似的圓的。所以，對照已知的覆蓋范圍，按照基站的覆蓋范圍大致是一個圓的特點，可以推斷出每個基站新的覆蓋范圍。以及各基站間重復(fù)的覆蓋區(qū)域。依照以上新的區(qū)域，就可以對原來的模型進(jìn)行改進(jìn)，從而使問題的結(jié)果得到優(yōu)化。下面是對社區(qū)基站圖的分析，以尋找更詳細(xì)的基站覆蓋區(qū)域。由于這些數(shù)據(jù)不能精確測量，所有的嘗試都是有很大誤差的。所以，在這里我們采用了推測的方法。這個推測方法是基于基站的覆蓋范圍近似為一個圓的特點進(jìn)行的。按照這個特點新增的覆蓋區(qū)域為(以下只列出了新增的區(qū)域)：待定點位置S1S2S3S4S5S7新增的區(qū)域0.8c50.4c*0.5c口0.4C40.1C60.4c50.3Ci2c10O'3—0.4c8按照模型一中的集合運算方法將新增區(qū)域增加到模型中去。由于，增加了一些區(qū)域，使得集合運算變得更加復(fù)雜。作為約束條件的一億元建設(shè)費用沒有改變。所以，這個約束條件是沒有變化的，可以直接列出：<100(1)i.1那么在模型中唯一改變的就是目標(biāo)函數(shù)，由于覆蓋區(qū)域變化，所以目標(biāo)函數(shù)將變得比較復(fù)雜。在這里定義一種運算符V,這個運算符代表或運算，也就是說S"0或仁所以對于新增的區(qū)域，由于只占小區(qū)的一部分，當(dāng)包含這個小區(qū)的基站被選中時，那么這個新增區(qū)域的人數(shù)就不能計入總?cè)藬?shù)中。比如，當(dāng)選中基站i時，i包含一個新增區(qū)域d而此時如果同時選中了基站j或基站k等剩余基站中的任一個(基站j和k等都包含整個社區(qū)c,c中包含d)，那么這個新增區(qū)域d將不計入總?cè)藬?shù)中。用數(shù)學(xué)表達(dá)是否需要刪除新增區(qū)域的式子就是(sjvskV.^)s.do如果這個式子不為零，那么就應(yīng)該將這個式子從》1p.s.中減掉。根據(jù)上面的分析，我們可以將目標(biāo)函數(shù)改進(jìn)。由于新增區(qū)域后，目標(biāo)函數(shù)變得比較復(fù)雜，在這里不再給出詳細(xì)的公式，只給出數(shù)學(xué)模型，這里^依然是每個基站覆蓋的人口數(shù)，其中包含新增的區(qū)域。下面給出目標(biāo)函數(shù)：

maxi=lmaxi=l1S2C2+SF3C4+S2S4C5+S3S4C8+S3S5C8+S3S6C?+Ci。)4$5C8+C9)+S5S6C12+S5S7S2+油Ci?+C]5))+S3S4S5C8S5SS5S6S7C12.vsfcV^)s.dn3)5.2.2模型二的求解根據(jù)上面的分析，以及列出的模型。在原來的模型的基礎(chǔ)上修改程序。將新的邏輯部分加入到程序當(dāng)中。經(jīng)過173次迭代得到結(jié)果，計算速度仍然是很快的。最后的結(jié)果整理到如下的表格中：模型二求解結(jié)果待定點位置s?S3S45556$7基站設(shè)置情況0101011覆蓋人數(shù)111.8千人建設(shè)費用95百萬兀人口覆蓋率95.56%表2模型二的求解結(jié)果從表2中可以看出，覆蓋人數(shù)比之前增加了一些，覆蓋率達(dá)到了95.56%。覆蓋人數(shù)增長了2.57%。而建設(shè)費用和基站的建設(shè)位置均沒有改變。說明對人數(shù)的增加的影響主要集中在基站2的覆蓋范圍擴大。從圖1中也可以看出，只有社區(qū)1和4沒有覆蓋，而離社區(qū)比較近的基站為3和2，由于基站3的建設(shè)費用極其昂貴，所以模型直接就將3放棄掉了，而基站2的范圍擴大后，自然會增大覆蓋人數(shù)。六、 模型改進(jìn)在模型二中采用了估計的方法找到擴展區(qū)域。但是這種方法的誤差比較大。而事實上這本身是一個理想數(shù)學(xué)問題，所以沒有辦法精確計算。但是可以考慮采用圖像處理的方法，找到每一個基站點的半徑。對于圖像上的所