手機(jī)中繼站選址最優(yōu)方案

1、手機(jī)中繼站選址最優(yōu)方案摘要本文綜合利用多種模型，在資金和備選地址確定的情況下，對(duì)手機(jī)中繼站的選址問(wèn)題進(jìn)行了求解和優(yōu)化。我們首先對(duì)題中所給的數(shù)據(jù)進(jìn)行了整理和分析，引入了回溯模型、0-1規(guī)劃模型，為以下問(wèn)題的解決作了準(zhǔn)備。對(duì)于問(wèn)題一，我們運(yùn)用兩種方法，并用不同的軟件求解：方法一：我們引入0-1變量，建立目標(biāo)函數(shù)：覆蓋人口最大數(shù)=所有被覆蓋的社區(qū)人15口之和，即maxM=£Pjbj,根據(jù)題目要求建立約束條件，并用數(shù)學(xué)軟件LINGOj1很容易解得題目最優(yōu)解；方法二：聯(lián)系問(wèn)題的性質(zhì)，我們引入了回溯模型，采用迭代加深搜索的思想，可以在滿(mǎn)足題目所給條件下搜索到一條到達(dá)解空間的路徑。然后，根據(jù)所有的

2、路徑對(duì)應(yīng)的中繼站的建設(shè)情況求解出相應(yīng)的中繼站覆蓋的人口，然后經(jīng)過(guò)比較即可求得最終結(jié)果，我們運(yùn)用軟件MATLAB進(jìn)行編程求解。對(duì)于問(wèn)題二，我們同樣運(yùn)用以上兩種方法，只是針對(duì)題目要求略微改變目標(biāo)函數(shù)，并用不同的軟件求得相同解，最優(yōu)方案不變，和問(wèn)題一相同求得的結(jié)果如下表：研究問(wèn)題建中繼站位置所需費(fèi)用M50白力:最優(yōu)值問(wèn)題一2,4,6,744.5覆蓋中人口數(shù)10行人問(wèn)題二2,4,6,744.51獲得資費(fèi)85c千元本文運(yùn)用的兩種方法都有它們各自的優(yōu)點(diǎn)和不足，對(duì)于第一種方法，我們采用枚舉法，我們會(huì)發(fā)現(xiàn)總共有27種情況，但因?yàn)閿?shù)據(jù)比較少，運(yùn)用LINGO軟件求解，程序簡(jiǎn)單；對(duì)于第二種方法，我們采用回溯算法，需

3、要遍歷的分支相對(duì)減少，但是程序相對(duì)較復(fù)雜，比較適合數(shù)據(jù)較多的模型。本文還對(duì)“僅有一個(gè)中繼站信號(hào)覆蓋的小區(qū)通訊資費(fèi)按正常資費(fèi)的10%90%區(qū)間內(nèi)的收取”做了討論，得出了最優(yōu)方案隨百分比的改變的變化曲線(xiàn)圖。關(guān)鍵字：0-1規(guī)劃回溯算法中繼站LINGO軟件MATLAB軟件某手機(jī)運(yùn)營(yíng)商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開(kāi)展業(yè)務(wù)，計(jì)劃投資5000萬(wàn)元來(lái)建設(shè)中繼站。該區(qū)域由15個(gè)社區(qū)組成，有7個(gè)位置可以建設(shè)中繼站，每個(gè)中繼站只能覆蓋有限個(gè)社區(qū)。圖1是該區(qū)域的示意圖，每個(gè)社區(qū)簡(jiǎn)化為一個(gè)多邊形，每個(gè)可以建設(shè)中繼站的位置已用黑點(diǎn)標(biāo)出。由于地理位置等各種條件的不同，每個(gè)位置建設(shè)中繼站的費(fèi)用也不同，且覆蓋范圍也不同。表1中

4、列出了每個(gè)位置建設(shè)中繼站的費(fèi)用以及能夠覆蓋的社區(qū)，表2列出了每個(gè)社區(qū)的人口數(shù)。表1每個(gè)位置建設(shè)中繼站的費(fèi)用及所能覆蓋的社區(qū)1234567費(fèi)用（白力兀）96.52014.5191310.5覆蓋社區(qū)1,2,42,3,54,7,8,105,6,8,98,9,127,10,11,12,1512,13,14,15表2每個(gè)社區(qū)的人口數(shù)量社區(qū)123456789101112131415人口（千人）24136948121011614936問(wèn)題一：在不超過(guò)5000萬(wàn)建設(shè)費(fèi)用的情況下，在何處建設(shè)中繼站，能夠覆蓋盡可能多的人口；問(wèn)題二：考慮到中繼站出現(xiàn)故障維修的時(shí)候可能會(huì)出現(xiàn)所覆蓋的社區(qū)信號(hào)中斷等問(wèn)題，為此對(duì)通訊資費(fèi)

5、進(jìn)行了調(diào)整，規(guī)定，僅有一個(gè)中繼站信號(hào)覆蓋的小區(qū)通訊資費(fèi)按正常資費(fèi)的70%收取，有兩個(gè)或兩個(gè)以上中繼站信號(hào)覆蓋的小區(qū)的通訊資費(fèi)按正常收取，針對(duì)于5000萬(wàn)元的預(yù)算，應(yīng)該如何建設(shè)中繼站，才能夠使得資費(fèi)的收入達(dá)到最大二.問(wèn)題分析眾所周知手機(jī)是通過(guò)在地面上建立了大量的無(wú)線(xiàn)中繼站來(lái)傳遞信號(hào)，達(dá)到通話(huà)目向若某手機(jī)運(yùn)營(yíng)商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開(kāi)展業(yè)務(wù)，則需要考慮中繼站的覆蓋能力，即某中繼站覆蓋的那些社區(qū)以及社區(qū)的人數(shù)等問(wèn)題，在此基礎(chǔ)上建立中繼站網(wǎng)絡(luò)，最大程度上服務(wù)于小區(qū)的居民。根據(jù)題目條件，為了更好地分析問(wèn)題，我們將基站對(duì)于小區(qū)的覆蓋情況用下表來(lái)描述。中繼站社區(qū)12345678910111213141

6、51234567表3考慮到有的小區(qū)僅僅只有一個(gè)中繼站覆蓋，因此要想實(shí)現(xiàn)所有社區(qū)的全面覆蓋，有些中繼站是不能缺少的。例如，1號(hào)、3號(hào)、6號(hào)、11號(hào)、13號(hào)、14號(hào)社區(qū)均只可能有一個(gè)中繼站覆蓋，那么為這些社區(qū)服務(wù)的中繼站是必不可少的。因此，中繼站1號(hào)、2號(hào)、4號(hào)、6號(hào)、7號(hào)必須要設(shè)。建設(shè)這些中繼站的費(fèi)用9+6.5+14.5+13+10.5=53.5>50;此時(shí)，僅僅必須建設(shè)的中繼站的費(fèi)用已經(jīng)不能滿(mǎn)足要求。因此，要想在實(shí)現(xiàn)不超過(guò)5000萬(wàn)建設(shè)費(fèi)用的情況下實(shí)現(xiàn)對(duì)所有社區(qū)的覆蓋是不可能的。針對(duì)問(wèn)題一，我們采用了兩種方法：建立0-1規(guī)劃模型，通過(guò)對(duì)題目條件和問(wèn)題的挖掘，列寫(xiě)出規(guī)劃模型中的目標(biāo)函數(shù)和約

7、束條件。運(yùn)用數(shù)學(xué)軟件lingo求解，最終也得到了合理的中繼站建設(shè)方案。我們已經(jīng)知道了中繼站的建立不可能完全覆蓋所有的社區(qū)，只可能竟可能的建設(shè)具中的幾個(gè)中繼站，如果采用枚舉法，我們會(huì)發(fā)現(xiàn)總共有27種情況。發(fā)現(xiàn)數(shù)據(jù)有點(diǎn)大,即使采用MATLAB進(jìn)行編程來(lái)遍歷滿(mǎn)二叉樹(shù)，所需的時(shí)間過(guò)長(zhǎng)，也可能發(fā)生誤差，再加上在總資金上的約束。這樣就會(huì)顯得又寫(xiě)程序的運(yùn)行顯得多余，因此在此約束條件上我們可以采用分支定界法來(lái)刪除部分的枝葉，再加上一些其他的約束，比如人數(shù)上的約束，又可以刪除一些枝葉這樣大大的增加了速度。具體的思想還要套用回溯法的思想，這樣得到了中繼站的建立規(guī)劃，我們就可以根據(jù)相應(yīng)的已知數(shù)據(jù)進(jìn)行求解相關(guān)的信息，

8、比如花費(fèi)的資金，所覆蓋的社區(qū)與人數(shù)。針對(duì)問(wèn)題二，在滿(mǎn)足中繼站建設(shè)成本不超過(guò)5000萬(wàn)元的情況下，確定一個(gè)合理的中繼站建設(shè)方案，使得運(yùn)營(yíng)商的資費(fèi)收入最高。我們也采用了兩種方法：?jiǎn)栴}關(guān)鍵在于確定每一個(gè)社區(qū)用那幾個(gè)社區(qū)覆蓋，然后計(jì)算根據(jù)題目中的“僅有一個(gè)中繼站信號(hào)覆蓋的小區(qū)通訊資費(fèi)按正常資費(fèi)的70%攵取，有兩個(gè)或兩個(gè)以上中繼站信號(hào)覆蓋的小區(qū)的通訊資費(fèi)按正常收取”的原則，可以列寫(xiě)出關(guān)于資費(fèi)收入的函數(shù)表達(dá)式。運(yùn)用數(shù)學(xué)軟件lingo最終把滿(mǎn)足條件的中繼站建設(shè)方案對(duì)應(yīng)的資費(fèi)收入進(jìn)行比較，最終確定出最理想的中繼站建設(shè)方案。只要在問(wèn)題一第二種方法程序的運(yùn)行結(jié)果中得到社區(qū)的覆蓋信息進(jìn)行判斷在求出總的資金。既利用相

9、應(yīng)的有效人數(shù)與總費(fèi)用的投入進(jìn)行判斷標(biāo)準(zhǔn)。三.模型假設(shè)及符號(hào)說(shuō)明3.1 模型假設(shè)(1)若某社區(qū)處在某一中繼站覆蓋范圍內(nèi)，則該社區(qū)中的人口全部被該中繼站覆蓋;(2)各社區(qū)的手機(jī)使用率相同；(3)每位手機(jī)使用者的通訊資費(fèi)相同；(4)該區(qū)域只存在這一種通信網(wǎng)絡(luò)；(5)每個(gè)中繼站覆蓋且僅覆蓋表1上所列出的覆蓋區(qū)域；(6)通訊信號(hào)不受地形地貌，氣候變化等因素影響；(7)社區(qū)人口保持不變；(8)不考慮手機(jī)漫游等情況；(9)每個(gè)中繼站位置最多只建一個(gè)中繼站。3.2 符號(hào)說(shuō)明ki表述第i個(gè)中繼站的建設(shè)情況(其中i=1,2,7)。當(dāng)ki=1時(shí)，表示第i個(gè)中繼站要建設(shè)；當(dāng)ki=0時(shí)，表示第i個(gè)中繼站不建設(shè)bj表述第

10、j個(gè)社區(qū)的覆蓋情況(其中j=1,2,15)。當(dāng)bj=1時(shí)，表示第j個(gè)社區(qū)被覆蓋到；當(dāng)bj=0時(shí)，表示第j個(gè)社區(qū)/、被覆蓋到Pj表示第j個(gè)社區(qū)的人口數(shù)(其中j=1,2,15)G表示第i個(gè)中繼站的建設(shè)費(fèi)用(其中i=1,2，7)rj表示第j個(gè)社區(qū)的覆蓋情況(其中j=1,2，15)。當(dāng)口=0.7時(shí)，表示第j個(gè)社區(qū)只被一個(gè)中繼站被覆蓋到；當(dāng)口-1時(shí)，表示第j個(gè)社區(qū)被一個(gè)以上中繼站被覆蓋到；當(dāng)口=0時(shí)，表示第j個(gè)社區(qū)沒(méi)被中繼站被覆蓋到c表示獲得的單位資費(fèi)(千元)四.模型建立及求解問(wèn)題一01整型規(guī)劃模型建立設(shè)K(i=1,2,7表示7個(gè)中繼站)表述每一個(gè)中繼站的建設(shè)情況。引入0-1變量，即_J1,表示第i個(gè)中

11、繼站要建設(shè)ki=1。,表示第i個(gè)中繼站不建設(shè)k在此模型的建立過(guò)程中，由于同一個(gè)社區(qū)可能有多個(gè)中繼站覆蓋，如果覆蓋同一社區(qū)的中繼站都要建設(shè)時(shí)，那么中繼站覆蓋的人口就會(huì)被重復(fù)計(jì)算。故我們將目標(biāo)轉(zhuǎn)移到社區(qū)上，每個(gè)社區(qū)的被覆蓋情況只有兩種，要么被覆蓋要么不被覆蓋，我們也引入0-1變量，即._1,表示第j個(gè)社區(qū)被覆蓋j10,表示第j個(gè)社區(qū)不被覆蓋這樣就可避免了對(duì)同一社區(qū)人口的重復(fù)計(jì)算。本問(wèn)題的目標(biāo)是使得中繼站覆蓋的人口盡量多。根據(jù)表1,2,3我們可以得到目15標(biāo)函數(shù)：M='、pjbjjd7題目要求建設(shè)中繼站的費(fèi)用不超過(guò)5000萬(wàn)元，故約束條件：Zqki<50i1模型求解：15可知模型為：m

12、axM=、pjbjjw7工Ciki<50;im、ki=0或1;當(dāng)=0時(shí)，匕=0;否則b1=1;當(dāng)月+卜2=0時(shí)，b2=0；否則b2=1;當(dāng)卜2=0時(shí),b3=0；否則b3=1;當(dāng)k1+k3=0時(shí)，b4=0；否則b4=1;當(dāng)卜2十%=0時(shí)，b5=0；否則b5=1;當(dāng)k4=0時(shí),b6=0；否則b6=1;當(dāng)k3+k6=0時(shí),b7=0；否則b7=1;當(dāng)k3+k4+k5=0時(shí)，b8=0;否則b8=1;當(dāng)k4+k5=0時(shí)，b9=0；否則民=1;當(dāng)k3+k6=0時(shí)，匕0=0;否則b10=1;當(dāng)卜6=0時(shí)，跖=0;否則屈=1;當(dāng)k5+k6+k7=0時(shí)，b2=0；否則bi2=1;當(dāng)k7=0時(shí),匕3=b14=

13、0；否則b13=b14=1;、當(dāng)ke+k7=0時(shí)，b15=0;否則b15=0根據(jù)附錄中的程序利用LING或解得到最佳的方案如下表所示:中繼站1234567建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)此方案所需費(fèi)用為44.5百萬(wàn)<50百萬(wàn)，覆蓋人口為109千人回溯算法模型建立回溯模型可以系統(tǒng)的搜索一個(gè)問(wèn)題的所有解或任一解，按深度優(yōu)先策略，從根節(jié)點(diǎn)如圖所示就是I層出發(fā)搜索該模型可以搜索至解空間樹(shù)的任一點(diǎn)時(shí)，先判斷該首先我們節(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該節(jié)點(diǎn)為根的字?jǐn)?shù)的搜索,逐層向其回溯。否則進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄇ髥?wèn)題的所有解時(shí)，要回溯到根，且根節(jié)點(diǎn)的所

14、有子樹(shù)都已被搜索便才結(jié)束?；厮菟惴ㄒ步性囂椒?，它是一種系統(tǒng)地搜索問(wèn)題的解的方法?；厮菟惴ǖ幕舅枷胧牵簭囊粭l路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試。在回溯模型中，我們采用了迭代加深搜索的思想?？梢栽跐M(mǎn)足題目所給條件下搜索到一條到達(dá)解空間的路徑。然后，根據(jù)所有的路徑對(duì)應(yīng)的中繼站的建設(shè)情況求解出相應(yīng)的中繼站覆蓋的人口，然后經(jīng)過(guò)比較即可求得最終結(jié)果。如圖1)當(dāng)在I層的時(shí)候往左端行駛檢驗(yàn)I層點(diǎn)是否滿(mǎn)足條件若滿(mǎn)足則同樣對(duì)II層進(jìn)行同樣的檢驗(yàn)，若不滿(mǎn)足則退回回I層往右端行駛，進(jìn)入第II層，接著就這樣逐步的搜索下去，知道最后的一層。在這其中滿(mǎn)足的條件是在搜索過(guò)程中，需要考慮終止搜索的條件：中繼站的

15、建設(shè)費(fèi)用不能超過(guò)5000萬(wàn)。一旦在搜索路徑上，發(fā)現(xiàn)中繼站的建設(shè)費(fèi)用超過(guò)5000萬(wàn)，就立即停止對(duì)這一搜索路徑的進(jìn)一步搜索。2)滿(mǎn)足了這些條件后得到的數(shù)據(jù)再進(jìn)行判斷是否滿(mǎn)足人數(shù)上的約束，若滿(mǎn)足則這個(gè)就是符合條件的。模型求解：1)數(shù)據(jù)準(zhǔn)備：定義數(shù)組存儲(chǔ)每個(gè)社區(qū)的人數(shù)：p=2,4,13,6,9,4,8,12,10,11,6,14,9,3,6建設(shè)7個(gè)中繼站所需要的價(jià)錢(qián)：c=96.52014.5191310.5;生成中繼站的覆蓋矩陣：aa=zeros(7.15);a(1,1,2,4)=1;a(2,2,3,5)=1;a(3,4,7,8,10)=1;a(4,5,6,8,9)=1;a(5,8,9,12)=1;a

16、(6,7,10,11,12,15)=1;a(7,12,13,14,15)=1;即如下面表示：a=110100000000000011010000000000000100110100000000011011000000000000011001000000000100111001000000000001111花費(fèi)的資金為：l*c'數(shù)組中的0-1表示的是中繼站對(duì)社區(qū)的覆蓋與否。2)程序設(shè)計(jì)：定義location1函數(shù)來(lái)計(jì)算相關(guān)的數(shù)據(jù)，并且函數(shù)結(jié)果用數(shù)組來(lái)進(jìn)行存儲(chǔ)，包含各種情況的總資金，總覆蓋人數(shù)。利用for循環(huán)從根節(jié)點(diǎn)進(jìn)行搜索，用0-1變量來(lái)表示是否將該中繼站進(jìn)行建設(shè)，并且每進(jìn)入一個(gè)節(jié)點(diǎn)時(shí)都

17、要進(jìn)行判斷總資金是否少于50即用約束條件ifl*c'<=50進(jìn)行判斷；否則將t退回節(jié)點(diǎn)即轉(zhuǎn)入else在得到的所有數(shù)組中我們要根據(jù)總?cè)藬?shù)來(lái)進(jìn)行刷選：這里我們限制最小的人數(shù)為9仃人。這里還需要利用函數(shù)sign函數(shù)來(lái)確定社區(qū)的覆蓋與否。繼而可得到相應(yīng)的總?cè)烁采w。刷選出適合的數(shù)組后，得到相應(yīng)的資金花費(fèi)并存入數(shù)組loci給予輸出。3）模型結(jié)果：根據(jù)上面的程序我們可以得到以下的結(jié)果：方案中繼站1中繼站2中繼站3中繼站4中繼站5中繼站6中繼站7人數(shù)（千）費(fèi)用（白力）11p1001019148.5211100019746311010019240.5411000111913951001011104

18、4760：1101011:101507011000195378010101110944.590100111F1054910001100192451100010119238對(duì)于上面的數(shù)據(jù)，要求是盡可能的覆蓋人數(shù)多，發(fā)現(xiàn)方案8覆蓋的人數(shù)是最多的。并且對(duì)應(yīng)所花費(fèi)的費(fèi)用是44.5百萬(wàn)在這里面也不是最大的因此是比較好的方案，則對(duì)于方案8相應(yīng)的方案是：中繼站1234567建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)則由上面的表格我們很明顯的知道方案與方法一求得的完全相同4.2問(wèn)題二01整型規(guī)劃.1模型建立題中考慮到中繼站出現(xiàn)故障維修的時(shí)候可能會(huì)出現(xiàn)所覆蓋的社區(qū)信號(hào)中斷等問(wèn)題，為此對(duì)通訊資費(fèi)進(jìn)行了調(diào)整，規(guī)定，

19、僅有一個(gè)中繼站信號(hào)覆蓋的小區(qū)通訊資費(fèi)按正常資費(fèi)的70%收取，有兩個(gè)或兩個(gè)以上中繼站信號(hào)覆蓋的小區(qū)的通訊資費(fèi)按正常收取，為此，我們需要得到新的模型來(lái)進(jìn)行求解，因?yàn)榧僭O(shè)每個(gè)用戶(hù)的正常資費(fèi)相同，所以70%15可以用減少人口來(lái)求最優(yōu)值，故問(wèn)題二的目標(biāo)函數(shù)為：M=£pjrjjj7題目要求建設(shè)中繼站的費(fèi)用不超過(guò)5000萬(wàn)元，故約束條件：Zqki<50i14.2.2模型求解:15可知模型為：maxM八，PjPjj17£qk<50;i也ki=0或1根據(jù)程序二，利用LING或解得到最優(yōu)的建立方案如下表所示:中繼站1234567建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)此方案所需要

20、的費(fèi)用為44.5百萬(wàn)50百萬(wàn)，獲得資費(fèi)85c千元(其中c為常數(shù))回溯算法4.2.3模型建立：同樣的是選擇最優(yōu)深度搜索，一旦在搜索路徑上出現(xiàn)不滿(mǎn)足限制約束條件的情況，就終止此路徑的進(jìn)一步搜索，去尋求另外的搜索路徑。解決此問(wèn)題中，關(guān)鍵在于那幾個(gè)社區(qū)最終有幾個(gè)中繼站覆蓋的確定，因?yàn)檫@一確定的結(jié)論將會(huì)影響到資費(fèi)的收入。而且兩者必須聯(lián)系起來(lái)一起考慮。在迭代搜索模型中，終止搜索的條件為：搜索路徑在未達(dá)到最終解空間時(shí)，建設(shè)中繼站的費(fèi)用超過(guò)5000萬(wàn)元，或者搜索路徑到達(dá)了解空間。這樣可以將搜索路徑達(dá)到解空問(wèn)的中繼站的建設(shè)情況，確定每個(gè)社區(qū)有幾個(gè)中繼站覆蓋，以便確定應(yīng)對(duì)社區(qū)用戶(hù)是按照正常收取資費(fèi)還是收取資費(fèi)的7

21、0%。在計(jì)算總資費(fèi)的時(shí)候，我們用有效人數(shù)來(lái)進(jìn)行表示，有效人數(shù)就是在只有一個(gè)中繼站覆蓋的社區(qū)：人數(shù)*0.7就是這個(gè)社區(qū)的有效人數(shù)。為此，可以將搜索路徑上各中繼站的建設(shè)情況全部列出。然后根據(jù)題目中的表一來(lái)確定為每一社區(qū)服務(wù)的中繼站的個(gè)數(shù)。再算出有效地人數(shù)；還應(yīng)考慮到投入和收入的關(guān)系問(wèn)題，應(yīng)盡量投入盡量少的錢(qián)，取得盡量多的收入。因此，我們?cè)诳紤]資費(fèi)收入時(shí)，把社區(qū)內(nèi)移動(dòng)用戶(hù)數(shù)與建設(shè)中繼站的投入的比值作為研究的最終目標(biāo)量。這樣，最終選擇出資費(fèi)收入高的搜索路徑。從而解決了滿(mǎn)足條件的收益最大的中繼站建設(shè)方案的確定。4.2.2模型求解：1)數(shù)據(jù)準(zhǔn)備：定義數(shù)組存儲(chǔ)每個(gè)社區(qū)的人數(shù)：p=2,4,13,6,9,4,8

22、,12,10,11,6,14,9,3,6建設(shè)7個(gè)中繼站所需要的價(jià)錢(qián)：c=96.52014.5191310.5;生成中繼站的覆蓋矩陣：aa=zeros(7.15);a(1,1,2,4)=1;a(2,2,3,5)=1;a(3,4,7,8,10)=1;a(4,5,6,8,9)=1;a(5,8,9,12)=1;a(6,7,10,11,12,15)=1;a(7,12,13,14,15)=1即如下面表示：a=110100000000000;011010000000000;000100110100000;000011011000000;000000011001000;000000100111001;0000

23、0000001111花費(fèi)的資金為：l*c'數(shù)組中的0-1表示的是中繼站對(duì)社區(qū)的覆蓋與否。2)程序設(shè)計(jì)：定義location1函數(shù)來(lái)計(jì)算相關(guān)的數(shù)據(jù)，并且函數(shù)結(jié)果用數(shù)組來(lái)進(jìn)行存儲(chǔ)，包含各種情況的總資金，總覆蓋人數(shù)。利用for循環(huán)從根節(jié)點(diǎn)進(jìn)行搜索，用0-1變量來(lái)表示是否將該中繼站進(jìn)行建設(shè)，并且每進(jìn)入一個(gè)節(jié)點(diǎn)時(shí)都要進(jìn)行判斷總資金是否少于50即用約束條件ifl*c'<=50進(jìn)行判斷；否則將t退回節(jié)點(diǎn)即轉(zhuǎn)入else在得到的所有數(shù)組中我們要根據(jù)總?cè)藬?shù)來(lái)進(jìn)行刷選：這里我們限制最小的人數(shù)為60這里還需要利用函數(shù)sign函數(shù)來(lái)確定社區(qū)的覆蓋與否。接著總?cè)藬?shù)的確定中一個(gè)中繼站覆蓋的社區(qū)人數(shù)需要

24、乘以0.7繼而可得到相應(yīng)的總?cè)烁采w。刷選出適合的數(shù)組后，得到相應(yīng)的資金花費(fèi)并存入數(shù)組loci給予。3）模型結(jié)果根據(jù)上面的程序我們可以得到以下的結(jié)果：方案中繼站1中繼立”中繼站3中繼站4中繼立5中繼站6中繼站7后效人數(shù)（千）總費(fèi)用（白力）1111001072.448.52111000170.946311000r1170.9394100101178.8475011001182.4506101010r118544.57010011179.5498000101170.438并且可以得到相應(yīng)的有效人數(shù)與總費(fèi)用的比值為:力殺12345r678比值1.49281.54131.81791.67661.6480

25、1.91011.62241.8526由上面可以發(fā)現(xiàn)方案6的比值是最大的，很明顯的可以擇取方案6的建設(shè)計(jì)劃，則具體的建設(shè)方案及其覆蓋社區(qū)如下：中繼站1234567建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)結(jié)果也與方法一的完全相同。這時(shí)，要建設(shè)的中繼站有2號(hào)、4號(hào)、6號(hào)和7號(hào)。其中第一和第四區(qū)域沒(méi)有被任何中繼站覆蓋，不產(chǎn)生資費(fèi)收入；而第五、第十二、第十五區(qū)域被兩個(gè)或兩個(gè)以上的中繼站覆蓋，通信資費(fèi)按正常資費(fèi)收??；其他區(qū)域只有一個(gè)基站覆蓋，通信資費(fèi)按照正常資費(fèi)的70%收取。在此種方案下，中繼站建設(shè)總費(fèi)用44.50（百萬(wàn)元），有效人數(shù)為8.5（萬(wàn)）。五.結(jié)果分析及檢驗(yàn)對(duì)于問(wèn)題一，由兩種方法建立模型求解的

26、結(jié)果都相同，得到最佳的建站點(diǎn)2,4,6,7,所需費(fèi)用44.5萬(wàn)元，覆蓋人口109千人，結(jié)果正確，但方法一在編程上較簡(jiǎn)單，方法二遍歷次數(shù)較少，但編程難度系數(shù)較高，需要一定的編程能力。對(duì)于問(wèn)題二，兩種方法也都能求出同樣的結(jié)果，得到最佳的建站點(diǎn)2,4,6,7,所需費(fèi)用47.3萬(wàn)元，獲得資費(fèi)為85c千元。由上圖可以清晰看出，收取資費(fèi)的百分比增大，再摸范圍內(nèi)覆蓋總?cè)藬?shù)也隨之增大,但不會(huì)全部覆蓋。由上圖可以看出，收取資費(fèi)的百分比增大，獲得的總費(fèi)用呈分段函數(shù)，在一定區(qū)間內(nèi)數(shù)值不發(fā)生改變。六.優(yōu)化方向該模型巧妙的解決了相鄰信號(hào)站重復(fù)覆蓋的人口數(shù)的問(wèn)題，使得在LINGOS解方便，缺點(diǎn)是放數(shù)據(jù)量更大時(shí)計(jì)算會(huì)比較復(fù)

27、雜，所以可以考慮用MATLA編程求解，列出基站和小區(qū)的關(guān)系矩陣。但是本文的缺點(diǎn)是考慮問(wèn)題時(shí)我們只考慮了兩個(gè)重要的因素，因此在問(wèn)題的延伸中，本文加入更多的約束條件，使得模型和求解更加的實(shí)用。中繼站的后續(xù)研究還可以從它建設(shè)時(shí)的各種技術(shù)因素、社會(huì)因素、安全因素等來(lái)考慮，在通過(guò)各種方法將對(duì)這些因素進(jìn)行定量分析，建立合理的中繼站最大覆蓋模型。對(duì)于本問(wèn)題的延伸，可更改規(guī)劃目標(biāo)，并加入更多的約束條件，如：通過(guò)研究得出地區(qū)信號(hào)覆蓋層數(shù)對(duì)信號(hào)質(zhì)量的影響，繼而影響用戶(hù)數(shù)量及收費(fèi)標(biāo)準(zhǔn)，以最大收益為目標(biāo)函數(shù)。新問(wèn)題的規(guī)劃方法可以再上述兩個(gè)模型為框架的基礎(chǔ)上修改而得。對(duì)于0、1規(guī)劃類(lèi)問(wèn)題，利用電工學(xué)數(shù)字信號(hào)處理的方法也

28、可以方便的解決，就本問(wèn)題而言，其目標(biāo)函數(shù)利用數(shù)字信號(hào)寄存器的工作邏輯十分相似，可嘗試其他軟件求解。七.參考文獻(xiàn).胡運(yùn)權(quán)編著運(yùn)籌學(xué)教程清華大學(xué)出版社2007.04第三版；.蔣啟源編著數(shù)學(xué)模型高等教育出版社2003.08第三版；.上官士青辛浩然數(shù)學(xué)建模通信基站選址問(wèn)題的lingo求解機(jī)械電子2009,23:92-93。附錄：程序一(問(wèn)題一法一)：max=2*k1+4*b1+13*k2+6*b2+9*b3+4*k4+8*b4+12*b5+10*b6+11*b7+6*k6+14*b8+9*k7+3*k7+6*b9;9*k1+6.5*k2+20*k3+14.5*k4+19*k5+13*k6+10.5*k

29、7<=50;b1=IF(k1+k2#eq#0,0,1);b2=IF(k3+k1#eq#0,0,1);b3=IF(k4+k2#eq#0,0,1);b4=IF(k3+k6#eq#0,0,1);b5=IF(k3+k4+k5#eq#0,0,1);b6=IF(k4+k5#eq#0,0,1);b7=IF(k3+k6#eq#0,0,1);b8=IF(k5+k6+k7#eq#0,0,1);b9=IF(k6+k7#eq#0,0,1);BIN(k1);BIN(k2);BIN(k3);BIN(k4);BIN(k5);BIN(k6);BIN(k7);endLocaloptimalsolutionfound.Ob

30、jectivevalue:Objectivebound:Infeasibilities:Extendedsolversteps:Totalsolveriterations:109.0000109.00000.000000067VariableValueReducedCostK10.000000-2.000000B11.0000000.000000K21.000000-13.00000B20.0000000.000000B31.0000000.000000K41.000000-4.000000B41.0000000.000000B51.0000000.000000B61.0000000.0000

31、00B71.0000000.000000K61.000000-6.000000B81.0000000.000000K71.000000-12.00000B91.0000000.000000K30.0000000.000000K50.0000000.000000RowSlackorSurplusDualPrice1109.00001.00000025.5000000.00000030.0000004.00000040.0000006.00000050.0000009.00000060.0000008.00000070.00000012.0000080.00000010.0000090.00000

32、011.00000100.00000014.00000110.0000006.000000程序二：(問(wèn)題二法一)max=2*k1*0.7+4*b1+13*k2*0.7+6*b2+9*b3+4*k4*0.7+8*b4+12*b5+10*b6+11*b7+6*k6*0.7+14*b8+9*k7*0.7+3*k7*0.7+6*b9;9*k1+6.5*k2+20*k3+14.5*k4+19*k5+13*k6+10.5*k7<=50;b1=IF(k1+k2#gt#1,1,IF(k1+k2#eq#1,0.7,0);b2=IF(k3+k1#gt#1,1,IF(k3+k1#eq#1,0.7,0);b3=

33、IF(k4+k2#gt#1,1,IF(k4+k2#eq#1,0.7,0);b4=IF(k3+k6#gt#1,1,IF(k3+k6#eq#1,0.7,0);b5=IF(k3+k4+k5#gt#1,1,IF(k3+k4+k5#eq#1,0.7,0);b6=IF(k4+k5#gt#1,1,IF(k4+k5#eq#1,0.7,0);b7=IF(k3+k6#gt#1,1,IF(k3+k6#eq#1,0.7,0);b8=IF(k5+k6+k7#gt#1,1,IF(k5+k6+k7#eq#1,0.7,0);b9=IF(k6+k7#gt#1,1,IF(k6+k7#eq#1,0.7,0);BIN(k1);BIN

34、(k2);BIN(k3);BIN(k4);BIN(k5);BIN(k6);BIN(k7);endLocaloptimalsolutionfound.Objectivevalue:85.00000Objectivebound:85.00000Infeasibilities:0.000000Extendedsolversteps:10Totalsolveriterations:421VariableValueReducedCostK10.000000-1.400000B10.70000000.000000K21.000000-9.100000B20.0000000.000000B31.000000

35、0.000000K41.000000-2.800000B40.70000000.000000B50.70000000.000000B60.70000000.000000B70.70000000.000000K61.000000-4.200000B81.0000000.000000K71.000000-8.400000B91.0000000.000000K30.0000000.000000K50.0000000.000000RowSlackorSurplusDualPrice185.000001.00000025.5000000.00000030.0000004.00000040.0000006

36、.00000050.0000009.00000060.0000008.00000070.00000012.0000080.00000010.0000090.00000011.00000100.00000014.00000110.0000006.000000程序三：（問(wèn)題一法二）function10c1=location1(a)c=9.00006.500020.000014.500019.000013.000010.5000;p=2,4,13,6,9,4,8,12,10,11,6,14,9,3,6;i=1;a1=1,0;a2=1,0;a3=1,0;a4=1,0;a5=1,0;a6=1,0;for

37、i1=1:2l=zeros(1,7);l(1)=a1(i1);ifl*c'<=50fori2=1:2l(2)=a2(i2);ifl*c'<=50fori3=1:2l(3)=a3(i3);ifl*c'<=50fori4=1:2l(4)=a4(i4);ifl*c'<=50fori5=1:2l(5)=a5(i5);ifl*c'<=50fori6=1:2l(6)=a6(i6);ifl*c'<=50l(7)=1;ifl*c'<=50forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,

38、1);forj=1:15s(j)=sign(s(j);endpo=p.*s;ifsum(po)>=90loc1(i,1:7)=l;loc1(i,8)=sum(po);loc1(i,9)=l*c'i=i+1;endelsel(7)=0;ifl*c'<=50forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:15s(j)=sign(s(j);endpo=p.*s;ifsum(po)>=90loc1(i,1:7)=l;loc1(i,8)=sum(po);loc1(i,9)=l*c'i=i+1;endendendel

39、sel(6)=1-sign(l(6);endendelsel(5)=1-sign(l(5);endendelsel(4)=1-sign(l(4);endendelsel(3)=1-sign(l(3);endendelsel(2)=1-sign(l(2);endendelsel(1)=1-sign(l(1);endend程序四：(問(wèn)題二法二)function10c2=location2(a)c=9.00006.500020.000014.500019.000013.000010.5000;p=2,4,13,6,9,4,8,12,10,11,6,14,9,3,6;i=1;m=zeros(1,15)

40、;d=zeros(1,15);a1=1,0;a2=1,0;a3=1,0;a4=1,0;a5=1,0;a6=1,0;fori1=1:2l=zeros(1,7);l(1)=a1(i1);ifl*c'<=50fori2=1:2l(2)=a2(i2);ifl*c'<=50fori3=1:2l(3)=a3(i3);ifl*c'<=50fori4=1:2l(4)=a4(i4);ifl*c'<=50fori5=1:2l(5)=a5(i5);ifl*c'<=50fori6=1:2l(6)=a6(i6);ifl*c'<=50l(

41、7)=1;ifl*c'<=50forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:15%超過(guò)兩個(gè)覆蓋的%有覆蓋的%廠個(gè)覆蓋的m(j)=sign(s(j)-sign(s(j);s(j)=sign(s(j);d(j)=s(j)-m(j);endr=m+0.7*d;po=p.*r;ifsum(po)>=70loc2(i,1:7)=l;loc2(i,8)=sum(po);10c2(i,9)=l*c'i=i+1;endelsel(7)=0;ifl*c'<=50forj=1:7b(j,:)=a(j,:)*l(j);end

42、s=sum(b,1);%超過(guò)兩個(gè)覆蓋的%有覆蓋的%廠個(gè)覆蓋的forj=1:15m(j)=sign(s(j)-sign(s(j);s(j)=sign(s(j);d(j)=s(j)-m(j);endr=m+0.7*d;po=p.*r;ifsum(po)>=70loc2(i,1:7)=l;loc2(i,8)=sum(po);10c2(i,9)=l*c'i=i+1;endendendelsel(6)=1-sign(l(6);endendelsel(5)=1-sign(l(5);endendelsel(4)=1-sign(l(4);endendelsel(3)=1-sign(l(3);endendelsel(2)=1-sign(l(2);endendelsel(1)=1-sign(l(1);endendend程序五(優(yōu)化)functionloc3=location3(t)a=zeros(7,15);a(1,1,2,4)=1;a(2,2