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

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

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

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

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

5、況用下表來描述.表3每個基站所能覆蓋的社區(qū)1234567891011121314151OOO2OOO3OOOO4OOOO5OOO6OOOOO7OOOO考慮到有的小區(qū)僅僅只有一個基站覆蓋,因此要想實現(xiàn)所有社區(qū)的全面覆蓋,有些基站是不能缺少的.例如,1號、3號、6號、11號、13號、14號社區(qū)均只可能有一個基站覆蓋,那么為這些社區(qū)效勞的基站是必不可少的.因此,基站1號、2號、4號、6號、7號必須要設.建設這些基站的費用9.5+7+14+13+11=54.5>50;此時,僅僅必須建設的基站的費用已經(jīng)不能滿足要求.因此,要想在實現(xiàn)不超過5000萬建設費用的情況下實現(xiàn)對所有社區(qū)的覆蓋是不可能的.針

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

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

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

9、將目標轉(zhuǎn)移到社區(qū)上,每個社區(qū)的被覆蓋情況只有兩種,要么被覆蓋要么不被覆蓋我們也引入0-1變量,即y=1,表示第j個社區(qū)被覆蓋0,表小第j個社區(qū)不被覆蓋1、2、3我們可以得到這樣就可防止了對同一社區(qū)人口的重復計算.本問題的目標是使得基站覆蓋的人口盡量多.根據(jù)表15目標函數(shù):max=j1PjYj由于考慮到1號、3號、6號、11號、13號、14號社區(qū)均只可能有一個基站覆蓋,這里我們讓Xi代替丫上(即第j個社區(qū)只被第i個基站覆蓋),那么目標函數(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);要求建設基站的費用不超過5000萬元故約束條件：(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)<=50;問題二：題中考慮到基站出現(xiàn)故障維修的時候可能會出現(xiàn)所覆蓋的社區(qū)信號中斷等問題,為此對通訊資費進行了調(diào)整,規(guī)定,僅有一個基站信號覆蓋的小區(qū)通訊資費按正常資費的68%攵取,有兩個或兩個以上基站信號覆蓋的小區(qū)的通訊資費按正常收取,為此,我們需要得到新的模型來進行求解,由于假設每個用戶的正常資費相同,所以68%T以用減少人口來求最優(yōu)值,與問題一類似,考慮到1號、3號、6號、11號、13號

11、、14號社區(qū)均只可能有一個基站覆蓋,這里我們讓xi代替丫上(即第j個社區(qū)只被第i個基站覆蓋),故問題二的目標函數(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);題目要求建設中繼站的費用不超過5000萬元故約束條件：(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)<=50;在此方案下,獲得的資費為：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建設情況不建設建設不建設建設不建設建設建設此方案所需費用為45百萬元,覆蓋人口為109.5千人問題二：根據(jù)附錄中的程序二利用LINGO求解得到最正確白方案如下表5所示:表5基站12345

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

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

15、基站最大覆蓋模型.以最大收益為目標函數(shù).新問題的規(guī)劃方法可以再上述模型為框架的根底上修改而得.7、參考文獻1,胡運權編著?運籌學教程?清華大學出版社2007.04第三版；2.蔣啟源編著?數(shù)學模型?高等教育出版社2003.08第三版；3,吳禮斌,李柏年數(shù)學實驗與建模M,北京：國防工業(yè)出版社,2007年；4 王兵團數(shù)學建*K根底M,北京：北京交通大學出版社,2004年；5 胡守信,李柏年基于MATLAB的數(shù)學試驗M,北京：科學出版社,2004年；6李明月移動通訊基站建設問題 :/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運行結(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運行結(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.