數(shù)學(xué)建模課程設(shè)計(jì)——優(yōu)化問題

1、摘要在 普遍流行的今天,建設(shè)基站的問題分析對(duì)于運(yùn)營商來說很有必要.本文針對(duì)現(xiàn)有的條件和題目的要求進(jìn)行討論.在建設(shè)此模型中,核心運(yùn)用到了0-1整數(shù)規(guī)劃模型,且運(yùn)用lingo軟件求解.對(duì)于問題一：我們引入0-1變量,建立目標(biāo)函數(shù)：覆蓋人口最大數(shù)=所有被覆蓋的社區(qū)人口之和,即15max=j4py.,根據(jù)題目要求建立約束條件,并用數(shù)學(xué)軟件LINGO對(duì)其模型求解,得到最優(yōu)解.對(duì)于問題二：同樣運(yùn)用0-1整數(shù)規(guī)劃模型,建立目標(biāo)函數(shù)時(shí),此處假設(shè)每個(gè)用戶的正常資費(fèi)相同,所以68%T以用減少人口來求最優(yōu)值,故問題二的目標(biāo)函數(shù)為：15max=Pjkj上述模型得到最優(yōu)解結(jié)果如下:研究問題建中繼站位置所需費(fèi)用最優(yōu)值問題

2、一2、4、6、745白力覆蓋中人口數(shù)109.5千人問題二2、4、6、745白力獲得資費(fèi)83.74a關(guān)鍵字：基站;0-1整數(shù)規(guī)劃；lingo軟件目錄1問題的重述32問題的分析43模型的假設(shè)與符號(hào)的說明53.1 模型的假設(shè)53.2 符號(hào)的說明54模型的建立及求解54.1 模型的建立54.2 模型的求解65模型結(jié)果的分析76優(yōu)化方向77參考文獻(xiàn)88、附錄91、問題的重述某 運(yùn)營商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開展業(yè)務(wù),方案投資5000萬元來建設(shè)基站.該區(qū)域由15個(gè)社區(qū)組成,有7個(gè)位置可以建設(shè)基站,每個(gè)基站只能覆蓋有限個(gè)社區(qū).圖1是該區(qū)域的示意圖,每個(gè)社區(qū)簡化為一個(gè)多邊形,每個(gè)可以建設(shè)基站的位置已用黑點(diǎn)

3、標(biāo)出.由于地理位置等各種條件的不同,每個(gè)位置建設(shè)基站的費(fèi)用也不同,且覆蓋范圍也不同.表1中列出了每個(gè)位置建設(shè)基站的費(fèi)用以及能夠覆蓋的社區(qū),表2列出了每個(gè)社區(qū)的人口數(shù).表1每個(gè)位置建設(shè)基站的費(fèi)用及所能覆蓋的社區(qū)1234567費(fèi)用白力兀9.57191417.51311覆蓋社區(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人口千人24136947.512.5101161493.56問題一：在不超過5000萬建設(shè)費(fèi)用的情況下,在何處建設(shè)基站,能夠覆蓋盡可能多的人口；問題二

4、：考慮到基站出現(xiàn)故障維修的時(shí)候可能會(huì)出現(xiàn)所覆蓋的社區(qū)信號(hào)中斷等問題,為此對(duì)通訊資費(fèi)進(jìn)行了調(diào)整,規(guī)定,僅有一個(gè)基站信號(hào)覆蓋的小區(qū)通訊資費(fèi)按正常資費(fèi)的68%攵取,有兩個(gè)或兩個(gè)以上基站信號(hào)覆蓋的小區(qū)的通訊資費(fèi)按正常收取,針對(duì)于5000萬元的預(yù)算,應(yīng)該如何建設(shè)基站,才能夠使得資費(fèi)的收入到達(dá)最大.2、問題的分析 是通過在地面上建立了大量的無線基站來傳遞信號(hào),到達(dá)通話目的.假設(shè)某 運(yùn)營商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開展業(yè)務(wù),那么需要考慮基站的覆蓋水平,即某基站覆蓋的那些社區(qū)以及社區(qū)的人數(shù)等問題,在此根底上建立基站網(wǎng)絡(luò),最大程度上效勞于小區(qū)的居民.根據(jù)題目條件,為了更好地分析問題,我們將基站對(duì)于小區(qū)的覆蓋情

5、況用下表來描述.表3每個(gè)基站所能覆蓋的社區(qū)1234567891011121314151OOO2OOO3OOOO4OOOO5OOO6OOOOO7OOOO考慮到有的小區(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ū)效勞的基站是必不可少的.因此,基站1號(hào)、2號(hào)、4號(hào)、6號(hào)、7號(hào)必須要設(shè).建設(shè)這些基站的費(fèi)用9.5+7+14+13+11=54.5>50;此時(shí),僅僅必須建設(shè)的基站的費(fèi)用已經(jīng)不能滿足要求.因此,要想在實(shí)現(xiàn)不超過5000萬建設(shè)費(fèi)用的情況下實(shí)現(xiàn)對(duì)所有社區(qū)的覆蓋是不可能的.針

6、對(duì)問題一：建立0-1整數(shù)規(guī)劃,通過對(duì)題目條件和問題的挖掘,列寫出規(guī)模型中的目標(biāo)函數(shù)和約束條件.運(yùn)用數(shù)學(xué)軟件lingo求解,得到合理的基站建設(shè)方案.針對(duì)問題二：在滿足基站建設(shè)本錢不超過5000萬元的情況下,確定一個(gè)合理的基站建設(shè)方案,使得運(yùn)營商的資費(fèi)收入最高.問題關(guān)鍵在于確定每一個(gè)社區(qū)用哪幾個(gè)社區(qū)覆蓋,然后計(jì)算根據(jù)題目中的“僅有一個(gè)基站信號(hào)覆蓋的小區(qū)通訊資費(fèi)按正常資費(fèi)的68%攵取,有兩個(gè)或兩個(gè)以上基站信號(hào)覆蓋的小區(qū)的通訊資費(fèi)按正常收取的原那么,可以列寫出關(guān)于資費(fèi)收入的函數(shù)表達(dá)式.運(yùn)用數(shù)學(xué)軟件lingo最終把滿足條件的基站建設(shè)方案解出,最終確定出最理想的基站建設(shè)方案3、模型的假設(shè)與符號(hào)的說明3.1

7、 模型的假設(shè)(1)假設(shè)某社區(qū)處在某一基站覆蓋范圍內(nèi),那么該社區(qū)中的人口全部被該基站覆蓋;(2)各社區(qū)的 使用率相同；(3)每位 使用者的通訊資費(fèi)相同；(4)該區(qū)域只存在這一種通信網(wǎng)絡(luò)；(5)每個(gè)基站覆蓋且僅覆蓋圖1所列出的覆蓋區(qū)域；(6)通訊信號(hào)不受地形地貌,氣候變化等因素影響；(7)社區(qū)人口保持不變；(8)不考慮 漫游等情況；(9)每個(gè)基站位置最多只建一個(gè)基站.3.2 符號(hào)的說明表示第i個(gè)基站建設(shè)情況(i=1,2,.7),當(dāng)X=1時(shí),表示第i個(gè)基站要被建設(shè)；當(dāng)Xi=0時(shí)表示第i個(gè)基站不要被建設(shè)V、表示第j個(gè)社區(qū)被覆蓋情況(j=1,2,.15),當(dāng)y1時(shí),表示第j個(gè)社區(qū)被覆蓋；當(dāng)yr0時(shí)表示第

8、j個(gè)社區(qū)未被覆蓋Pj表示第j個(gè)社區(qū)的人口數(shù)(j=1,2,.15kj表示第i個(gè)基站被建設(shè)所需的費(fèi)用(i=1,2,.7)表示第j個(gè)社區(qū)被覆蓋情況(j=1,2,.15),當(dāng)j=i,表示第j個(gè)社區(qū)被多個(gè)基站覆蓋；當(dāng)kj=0.68時(shí),表示第j個(gè)社區(qū)被1個(gè)基站覆蓋；當(dāng)匕=0時(shí)表示第j個(gè)社區(qū)未被覆蓋4、模型的建立及求解4.1模型的建立問題一：設(shè)Xi(i=1,2,.7表示7個(gè)中繼站)表述每一個(gè)基站的建設(shè)情況.引入0-1變量,即Xi=r1,表示第i個(gè)基站要建立0,表示第i個(gè)基站不建立在此模型的建立過程中,由于同一個(gè)社區(qū)可能有多個(gè)基站覆蓋,如果覆蓋同一社區(qū)的基站都要建設(shè)時(shí),那么基站覆蓋的人口就會(huì)被重復(fù)計(jì)算.故我們

9、將目標(biāo)轉(zhuǎn)移到社區(qū)上,每個(gè)社區(qū)的被覆蓋情況只有兩種,要么被覆蓋要么不被覆蓋我們也引入0-1變量,即y=1,表示第j個(gè)社區(qū)被覆蓋0,表小第j個(gè)社區(qū)不被覆蓋1、2、3我們可以得到這樣就可防止了對(duì)同一社區(qū)人口的重復(fù)計(jì)算.本問題的目標(biāo)是使得基站覆蓋的人口盡量多.根據(jù)表15目標(biāo)函數(shù):max=j1PjYj由于考慮到1號(hào)、3號(hào)、6號(hào)、11號(hào)、13號(hào)、14號(hào)社區(qū)均只可能有一個(gè)基站覆蓋,這里我們讓Xi代替丫上(即第j個(gè)社區(qū)只被第i個(gè)基站覆蓋),那么目標(biāo)函數(shù)：max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*

10、x6+14*(y12)+9*x7+3.5*x7+6*(y15);要求建設(shè)基站的費(fèi)用不超過5000萬元故約束條件：(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)<=50;問題二：題中考慮到基站出現(xiàn)故障維修的時(shí)候可能會(huì)出現(xiàn)所覆蓋的社區(qū)信號(hào)中斷等問題,為此對(duì)通訊資費(fèi)進(jìn)行了調(diào)整,規(guī)定,僅有一個(gè)基站信號(hào)覆蓋的小區(qū)通訊資費(fèi)按正常資費(fèi)的68%攵取,有兩個(gè)或兩個(gè)以上基站信號(hào)覆蓋的小區(qū)的通訊資費(fèi)按正常收取,為此,我們需要得到新的模型來進(jìn)行求解,由于假設(shè)每個(gè)用戶的正常資費(fèi)相同,所以68%T以用減少人口來求最優(yōu)值,與問題一類似,考慮到1號(hào)、3號(hào)、6號(hào)、11號(hào)、13號(hào)

11、、14號(hào)社區(qū)均只可能有一個(gè)基站覆蓋,這里我們讓xi代替丫上(即第j個(gè)社區(qū)只被第i個(gè)基站覆蓋),故問題二的目標(biāo)函數(shù)為max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*x6+14*(y12)+9*x7+3.5*x7+6*(y15);題目要求建設(shè)中繼站的費(fèi)用不超過5000萬元故約束條件：(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)<=50;在此方案下,獲得的資費(fèi)為：S=2*x1*(k1)+4*(y2)*(k2)+13*x2*(k3)+6*(y

12、4)*(k4)+9*(y5)*(k5)+4*x4*(k6)+7.5*(y7)*(k7)+12.5*(y8)*(k8)+10*(y9)*(k9)+11*(y10)*(k10)+6*x6*(k11)+14*(y12)*(k12)+9*x7*(k13)+3.5*x7*(k13)+6*(y15)*(k15);4.2模型的求解問題一：根據(jù)附錄中的程序一利用LINGO求解得到最正確白方案如下表4所示:表4基站1234567建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)此方案所需費(fèi)用為45百萬元,覆蓋人口為109.5千人問題二：根據(jù)附錄中的程序二利用LINGO求解得到最正確白方案如下表5所示:表5基站12345

13、67建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)此方案所需要的費(fèi)用為45百萬元,獲得資費(fèi)83.74aa為標(biāo)準(zhǔn)的資費(fèi)常數(shù)5、結(jié)果分析對(duì)于問題一,要求在基站建設(shè)本錢不超過50百萬元的情況下,確定一個(gè)合理的基站建設(shè)方案,使得覆蓋的人口盡可能的多.所以我們根據(jù)題意建立了0-1規(guī)劃模型,運(yùn)用LONG酸件對(duì)規(guī)劃模型求解,得到在2,4,6,7號(hào)位置建設(shè)基站時(shí),覆蓋人口最多為109.5千人,同時(shí)建設(shè)基站的費(fèi)用為45百萬元,滿足約束條件中的費(fèi)用不超過50百萬的要求.對(duì)于問題二,要求的是在滿足基站建設(shè)本錢不超過5000萬元預(yù)算條件下,怎樣建設(shè)基站,使得運(yùn)營商的資費(fèi)收入最高.根據(jù)題目中“僅有一個(gè)基站信號(hào)覆蓋的小區(qū)人均

14、通訊資費(fèi)按正常資費(fèi)的68%攵取,而有兩個(gè)或兩個(gè)以上站信號(hào)覆蓋的小區(qū)人均的通訊資費(fèi)按正常收取的要求,我們運(yùn)用了0-1規(guī)劃方法,并且用lingo數(shù)學(xué)軟件得出最大資費(fèi)收益為S=83.74a.6、優(yōu)化方向該模型巧妙的解決了相鄰信號(hào)站重復(fù)覆蓋的人口數(shù)的問題,使得LINGO求解方便,缺點(diǎn)是當(dāng)數(shù)據(jù)量更大時(shí)計(jì)算會(huì)比擬復(fù)雜,所以可以考慮用MATLA的程求解,列出基站和小區(qū)的關(guān)系矩陣.并且考慮問題時(shí)我們只考慮了兩個(gè)重要的因素,因此,對(duì)于本問題的延伸,可更改規(guī)劃目標(biāo),并參加更多的約束條件,如：通過研究得出地區(qū)信號(hào)覆蓋層數(shù)對(duì)信號(hào)質(zhì)量的影響,繼而影響用戶數(shù)量及收費(fèi)標(biāo)準(zhǔn),在通過各種方法將對(duì)這些因素進(jìn)行定量分析,建立合理的

15、基站最大覆蓋模型.以最大收益為目標(biāo)函數(shù).新問題的規(guī)劃方法可以再上述模型為框架的根底上修改而得.7、參考文獻(xiàn)1,胡運(yùn)權(quán)編著?運(yùn)籌學(xué)教程?清華大學(xué)出版社2007.04第三版；2.蔣啟源編著?數(shù)學(xué)模型?高等教育出版社2003.08第三版；3,吳禮斌,李柏年數(shù)學(xué)實(shí)驗(yàn)與建模M,北京：國防工業(yè)出版社,2007年；4 王兵團(tuán)數(shù)學(xué)建*K根底M,北京：北京交通大學(xué)出版社,2004年；5 胡守信,李柏年基于MATLAB的數(shù)學(xué)試驗(yàn)M,北京：科學(xué)出版社,2004年；6李明月移動(dòng)通訊基站建設(shè)問題 :/wenku.baidu /view/72d9ab3c0066f5335a812111.html2021.12.17/20

16、21.07.02附錄:程序一：問題一model:max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*x6+14*(y12)+9*x7+3.5*x7+6*(y15);(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)<=50;Y2=if(x1+x2#eq#0,0,1);Y4=if(x1+x3#eq#0,0,1);Y5=if(x2+x4#eq#0,0,1);Y7=if(x3+x6#eq#0,0,1);Y8=if(x3+x4+x5#eq#0,0,1)

17、;Y9=if(x4+x5#eq#0,0,1);Y10=if(x3+x6#eq#0,0,1);Y12=if(x5+x6+x7#eq#0,0,1);Y15=if(x6+x7#eq#0,0,1);bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);end運(yùn)行結(jié)果：Localoptimalsolutionfound.Objectivevalue:109.5000Extendedsolversteps:3Totalsolveriterations:185VariableValueReducedCostX10.000000-2.000000Y21

18、.0000000.000000X21.000000-13.00000Y40.0000000.000000Y51.0000000.000000X41.000000-4.000000Y71.0000000.000000Y81.0000000.000000Y91.0000000.000000Y101.0000000.000000X61.000000-6.000000Y121.0000000.000000X71.000000-12.50000Y151.0000000.000000X30.0000000.000000X50.0000000.000000RowSlackorSurplusDualPrice

19、1109.50001.00000025.0000000.00000030.0000004.00000040.0000006.00000050.0000009.00000060.0000007.50000070.00000012.5000080.00000010.0000090.00000011.00000100.00000014.00000110.0000006.000000程序二：問題二model:max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*x6+14*(y12)+9*x7+3.

20、5*x7+6*(y15);(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)<=50;y2=if(x1+x2#eq#0,0,1);y4=if(x1+x3#eq#0,0,1);y5=if(x2+x4#eq#0,0,1);y7=if(x3+x6#eq#0,0,1);y8=if(x3+x4+x5#eq#0,0,1);y9=if(x4+x5#eq#0,0,1);y10=if(x3+x6#eq#0,0,1);y12=if(x5+x6+x7#eq#0,0,1);y15=if(x6+x7#eq#0,0,1);k1=if(x1#eq#1,0.68,0);k2=if

21、(x1+x2#eq#1,0.68,1);k3=if(x2#eq#1,0.68,1);k4=if(x1+x3#eq#1,0.68,0);k5=if(x4+x2#eq#1,0.68,1);k6=if(x4#eq#1,0.68,1);k7=if(x3+x6#eq#1,0.68,1);k8=if(x3+x4+x5#eq#1,0.68,1);k9=if(x4+x5#eq#1,0.68,1);k10=if(x3+x6#eq#1,0.68,1);k11=if(x6#eq#1,0.68,1);k12=if(x5+x6+x7#eq#1,0.68,1);k13=if(x7#eq#1,0.68,1);k14=if(

22、x7#eq#1,0.68,1);k15=if(x6+x7#eq#1,0.68,1);s=2*x1*(k1)+4*(y2)*(k2)+13*x2*(k3)+6*(y4)*(k4)+9*(y5)*(k5)+4*x4*(k6)+7.5*(y7)*(k7)+12.5*(y8)*(k8)+10*(y9)*(k9)+11*(y10)*(k10)+6*x6*(k11)+14*(y12)*(k12)+9*x7*(k13)+3.5*x7*(k13)+6*(y15)*(k15);bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);end運(yùn)行結(jié)果：Loca

23、loptimalsolutionfound.Objectivevalue:Extendedsolversteps:Totalsolveriterations:109.50000115VariableValueReducedCostX10.000000-2.000000Y21.0000000.000000X21.000000-13.00000Y40.0000000.000000Y51.0000000.000000X41.000000-4.000000Y71.0000000.000000Y81.0000000.000000Y91.0000000.000000Y101.0000000.000000X

24、61.000000-6.000000Y121.0000000.000000X71.000000-12.50000Y151.0000000.000000X30.0000000.000000X50.0000000.000000K10.0000000.000000K20.68000000.000000K30.68000000.000000K40.0000000.000000K51.0000000.000000K60.68000000.000000K70.68000000.000000K80.68000000.000000K90.68000000.000000K100.68000000.000000K11K12K13K14K15SRow1234567891011121314151617181920212223242526270.68000001.0000000.68000000.68000001.00000083.740000.0000000.0000000.0000000.0000000.0000000.000000SlackorSurplusDualPrice109.50005.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.