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

本文綜合利用多種模型，在和備選地址確定的情況下，對(duì)中繼站的選址模型、0-1規(guī)劃模型，為以下問(wèn)題的解決作了準(zhǔn)備。0-1人口之和，即

M pjbjjLINGO結(jié)果，我們運(yùn)用軟件進(jìn)行編程求解。所需費(fèi)用50覆蓋中人口數(shù)獲得資費(fèi)85c本文運(yùn)用的兩種方法都有它們各自的優(yōu)點(diǎn)和不足，對(duì)于第法，我們采用舉法，我們會(huì)發(fā)現(xiàn)總共有27種情況，但因?yàn)閿?shù)據(jù)比較少，運(yùn)用LINGO軟件求解，程10%~90%區(qū)間覆蓋覆蓋總?cè)藬?shù)（千

總費(fèi)總費(fèi)用（百萬(wàn)

關(guān)鍵字：0-1規(guī) 回溯算 中繼 LINGO軟 軟一．問(wèn)題重某運(yùn)營(yíng)商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開展業(yè)務(wù)，計(jì)劃投資5000萬(wàn)元來(lái)157121137146827552493611234567費(fèi)用（元9 9人口（人2469486936問(wèn)題一：5000萬(wàn)建設(shè)費(fèi)用的情況下，在何處建設(shè)中繼站，能夠覆蓋盡可問(wèn)題二：考慮到中繼站出現(xiàn)故障維修的時(shí)候可能會(huì)出現(xiàn)所覆蓋的社區(qū)信號(hào)中斷等70%收取，有兩個(gè)或兩個(gè)以上中繼站信號(hào)覆蓋的小區(qū)的通訊資費(fèi)按正常收取，5000萬(wàn)元的預(yù)算，應(yīng)該如何建設(shè)中繼站，才能夠使得資費(fèi)的收入達(dá)到最大二．問(wèn)題分眾所周知 是通過(guò)在地面上建立了大量的無(wú)線中繼站來(lái)傳遞信號(hào),達(dá)到通話目的。若某 運(yùn)營(yíng)商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開展業(yè)務(wù)，則需要考慮中繼站覆蓋能力，即某中繼站覆蓋的那些社區(qū)以及社區(qū)的人數(shù)等問(wèn)題，在此基礎(chǔ)上建立中站網(wǎng)絡(luò)，最大程度上服務(wù)于小區(qū)的居民。根據(jù)題目條件，為了更好地分析問(wèn)題，我將對(duì)于小區(qū)的覆蓋情況用下表來(lái)描述。12345678967表有些中繼站是不能缺少的。例如，136111314號(hào)、2號(hào)、4號(hào)、6號(hào)、7號(hào)必須要設(shè)。建設(shè)這些中繼站的費(fèi)用建立0-1我們已經(jīng)知道了中繼站的建立不可能完所有的社區(qū)，只可能竟可能的建設(shè)其中的幾個(gè)中繼站，如果采用枚舉法，我們會(huì)發(fā)現(xiàn)總共有27種情況。發(fā)現(xiàn)數(shù)據(jù)有點(diǎn)大，即使采用進(jìn)行編程來(lái)遍歷滿二叉樹，所需的時(shí)間過(guò)長(zhǎng)，也可能發(fā)生誤差，再加上在總上的約束。這樣就會(huì)顯得又寫程序的運(yùn)行顯得多余，因此此約束條件上我們可以采用分支定界法來(lái)刪除部分的，再加上一些其他的約束，比如人數(shù)上的約束，又可以刪除一些這樣大大的增加了速度。具體的思想知數(shù)據(jù)進(jìn)行求解相關(guān)的信息，比如花費(fèi)的，所覆蓋的社區(qū)與人數(shù)。500070%收取，有兩個(gè)或兩個(gè)以上中繼數(shù)表達(dá)式。運(yùn)用數(shù)學(xué)軟件lingo最終把滿足條件的中繼站建設(shè)方案對(duì)應(yīng)的資費(fèi)收入三．模型假設(shè)及符號(hào)說(shuō)各社區(qū) 使用率相同每 使用者的通訊資費(fèi)相同1不考慮漫游等情況表述第i個(gè)中繼站的建設(shè)情況(其中i1,2,7)。當(dāng)ki1時(shí)，表示第i站要建設(shè);當(dāng)ki0時(shí)，表示第ijj1,2,15)。當(dāng)bj1j覆蓋到;當(dāng)bj0jpjj1,2,15表示第i個(gè)中繼站的建設(shè)費(fèi)用(其中i1,2,7rjj1,2,15)。當(dāng)rj0.7j個(gè)社區(qū)只被一個(gè)中繼站被覆蓋到;當(dāng)rj1j蓋到；當(dāng)rj0jc表示獲得的單位資費(fèi)（千元四．模型建立及求0—1型規(guī)設(shè)kii1,2,7表示7個(gè)中繼站)表述每一個(gè)中繼站的建設(shè)情況。引入0-1 k在此模型的建立過(guò)程中，由于同一個(gè)社區(qū)可能有多個(gè)中繼站覆蓋，如果覆蓋同一 本問(wèn)題的目標(biāo)是使得中繼站覆蓋的人口盡量多。根據(jù)表1，2，3標(biāo)函數(shù)：M pjbj7j7題目要求建設(shè)中繼站的費(fèi)用不超過(guò)5000ciki

M j1iiki

當(dāng) 時(shí)，b3k否則

否時(shí)當(dāng) 時(shí)，b6k否則 當(dāng)當(dāng)

時(shí)

當(dāng)70時(shí)

根據(jù)附錄中的程序利用LINGO1234567此方案所需費(fèi)用為44.5百萬(wàn)<50百萬(wàn)，覆蓋人口為109回溯算節(jié)點(diǎn)如圖所示就是I先我們節(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該節(jié)點(diǎn)為根的字?jǐn)?shù)的搜索，逐層向其回溯。否則進(jìn)入該，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄇ髥?wèn)題的所有解時(shí)，要回溯到根，且根節(jié)點(diǎn)的所有都已被搜索便才結(jié)束。思II101010101010當(dāng)在I層的時(shí)候往左端行駛檢驗(yàn)I層點(diǎn)是否滿足條件若滿足則同樣對(duì)II層進(jìn)行同樣的檢驗(yàn)，若不滿足則退回回I層往右端行駛，進(jìn)入第II層，接著就這樣逐步的搜索的條件：中繼站的建設(shè)費(fèi)用過(guò)5000萬(wàn)。一旦在搜索路徑上，發(fā)現(xiàn)中繼站的5000萬(wàn)，就立即停止對(duì)這一搜索路徑的進(jìn)一步搜索。定義數(shù)組每個(gè)社區(qū)的人數(shù)建設(shè)7個(gè)中繼站所需要的價(jià)錢：c96.52014.5191310.5];a=[110100000000000；011010000000000；00010011010000；000011011000000；000000011001000；00000010011101；000000000001111花費(fèi)的為 1234567（千萬(wàn)11110010211100001411000111601100117011000119010011100110001112345670—1型規(guī)題中考慮到中繼站出現(xiàn)故障維修的時(shí)候可能會(huì)出現(xiàn)所覆蓋的社區(qū)信號(hào)中斷等問(wèn)題，用減少人口來(lái)求最優(yōu)值，故問(wèn)題二的目標(biāo)函數(shù)為：M p7j7題目要求建設(shè)中繼站的費(fèi)用不超過(guò)5000ciki

M pj

ki0或根據(jù)程序二，利用LINGO1234567此方案所需要的費(fèi)用為44.5百萬(wàn)<50百萬(wàn)，獲得資費(fèi)85c千元（其中c為常數(shù)回溯算況，就終止此路徑的進(jìn)一步搜索，去尋求另外的搜索路徑。在迭代搜索模型中，終止搜索的條件為：搜索路徑在未達(dá)到最終解空間時(shí)，建設(shè)中繼站的費(fèi)用超過(guò)5000萬(wàn)元，或者搜索路徑到達(dá)了解空間。這樣可以將搜索路徑達(dá)到解空間的中繼站的建設(shè)情況，確定每個(gè)社區(qū)有幾個(gè)中繼站覆蓋，以便確定應(yīng)對(duì)社區(qū)用戶是按照正常收取資費(fèi)還是收取資費(fèi)的70%*0.7效人數(shù)。的的中繼站建設(shè)方案的確定。4.2.2定義數(shù)組每個(gè)社區(qū)的人數(shù)建設(shè)7個(gè)中繼站所需要的價(jià)錢：c96.52014.5191310.5];a=[110100000000000;011010000000000;000100110100000;00011011000000;000000011001000;000000100111001;000000000111花費(fèi)的為每進(jìn)入一個(gè)節(jié)點(diǎn)時(shí)都要進(jìn)行判斷總是否少于50即用約束條件ifl*c'<=50進(jìn)行60刷選出適合的數(shù)組后，得到相應(yīng)的花費(fèi)并存入數(shù)組loc1給予（千（萬(wàn)11110010211100013110001141001011501100116010101170100111800010111234567866的建設(shè)計(jì)劃,則具體1234567這時(shí)，要建設(shè)的中繼站有2號(hào)、4號(hào)、6號(hào)和7號(hào)。其中第一和第四區(qū)域沒(méi)有被任何中通信資費(fèi)按正常資費(fèi)收?。黄渌麉^(qū)域只有一個(gè)覆蓋，通信資費(fèi)按照正常資費(fèi)的在此種方案下，中繼站建設(shè)總費(fèi)用44.50(8.5（萬(wàn)五．結(jié)果分析及檢2,4,6,7，所需費(fèi)用44.5萬(wàn)元覆蓋人口109結(jié)果正確但方法一在編程上較簡(jiǎn)單方法二遍歷次數(shù)較少，但編程難度系數(shù)較高，需要一定的編程能力。覆蓋總?cè)藬?shù)（千47.3覆蓋總?cè)藬?shù)（千總費(fèi)總費(fèi)用（百萬(wàn) 百分六．優(yōu)化方LINGO缺點(diǎn)是放數(shù)據(jù)量更大時(shí)計(jì)算會(huì)比較復(fù)雜，所以可以考慮用編程求解，列出在問(wèn)題的延伸中，本文加入的約束條件，使得模型和求解更加的實(shí)用。中繼站的后01七．參考文2003.08[1].胡運(yùn)權(quán)編著《運(yùn)籌學(xué)》2007.04第三版2003.08 [3].上官士青辛浩然《數(shù)學(xué)建模通信選址問(wèn)題的lingo求解》機(jī)械電子2009,23:max=b1=@IF(k1+k2#eq#0,0,1);b2=@IF(k3+k1#eq#0,0,b3=@IF(k4+k2#eq#0,0,b4=@IF(k3+k6#eq#0,0,b5=@IF(k3+k4+k5#eq#0,0,b6=@IF(k4+k5#eq#0,0,b7=@IF(k3+k6#eq#0,0,b8=@IF(k5+k6+k7#eq#0,0,b9=@IF(k6+k7#eq#0,0,1);LocaloptimalsolutionObjectiveObjectiveExtendedsolver0TotalsolveriReduced----- Slackor Dual123456789（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,b3=@IF(k4+k2#gt#1,1,@IF(k4+k2#eq#1,0.7,b4=@IF(k3+k6#gt#1,1,@IF(k3+k6#eq#1,0.7,b5=@IF(k3+k4+k5#gt#1,1,@IF(k3+k4+k5#eq#1,0.7,b6=@IF(k4+k5#gt#1,1,@IF(k4+k5#eq#1,0.7,b7=@IF(k3+k6#gt#1,1,@IF(k3+k6#eq#1,0.7,b8=@IF(k5+k6+k7#gt#1,1,@IF(k5+k6+k7#eq#1,0.7,b9=@IF(k6+k7#gt#1,1,@IF(k6+k7#eq#1,0.7,0));LocaloptimalsolutionObjectiveObjectiveExtendedsolverTotalsolveriReduced-----SlackorDual123456789（functionc foriffori2=1:2iffori3=1:2iffori4=1:2iffori5=1:2iffori6=1:2ififl*c'<=50for

forj=1:15if

elseiffor

forj=1:15

ifsum(po)>=90

elsel(6)=1-elsel(5)=1-sign(l(5));elsel(4)=1-sign(l(4));elsel(3)=1-sign(l(3));elsel(2)=1-sign(l(2));elsel(1)=1-sign(l(1));（functionc=[9.0000 foriffori2=1:2iffori3=1:2iffori4=1:2iffori5=1:2iffori6=1:2ififl*c'<=50for

forj=1:15m(j)=sign(s(j)-sign(s(j))if

elseif

for

forj=1:15m(j)=sign(s(j)-sign(s(j)));

ifsum(po)>=70

elsel(6)=1-elsel(5)=1-sign(l(5));elsel(4)=1-sign(l(4));elsel(3)=1-sign(l(3));elsel(2)=1-sign(l(2));elsel(1)=1-sign(l(1));functionloc3=location3(t)c=[9.0000 foriffori2=1:2iffori3=1:2iffori4=1:2iffori5=1:2iffori6=1:2ififl*c'<=50&&l*c'>=40forj=1:7forj=1:15m(j)=sign(s(j)-sign(s(j))if

elseiffor