摘要在手機普遍流行的今天，建設基站的問題分析對于運營商來說很有必要。本文針對現有的條件和題目的要求進行討論。在建設此模型中，核心運用到了0-1整數規劃模型，且運用lingo軟件求解。對于問題一： 我們引入0-1變量，建立目標函數：覆蓋人口最大數=所有被覆蓋的社區人口之和，即max=，根據題目要求建立約束條件，并用數學軟件LINGO對其模型求解，得到最優解。對于問題二： 同樣運用0-1整數規劃模型，建立目標函數時，此處假設每個用戶的正常資費相同，所以68%可以用減少人口來求最優值，故問題二的目標函數為：max=上述模型得到最優解結果如下：研究問題建中繼站位置所需費用最優值問題一2、4、6、745百萬覆蓋中人口數109.5千人問題二2、4、6、745百萬獲得資費83.74a關鍵字：基站; 0-1整數規劃；lingo軟件目錄1 問題的重述32 問題的分析43 模型的假設與符號的說明53.1模型的假設 53.2符號的說明 54 模型的建立及求解. 54.1模型的建立 54.2 模型的求解 65 模型結果的分析76 優化方向77 參考文獻88、附錄 91、 問題的重述某手機運營商準備在一個目前尚未覆蓋的區域開展業務，計劃投資5000萬元來建設基站。該區域由15個社區組成，有7個位置可以建設基站，每個基站只能覆蓋有限個社區。圖1是該區域的示意圖，每個社區簡化為一個多邊形，每個可以建設基站的位置已用黑點標出。由于地理位置等各種條件的不同，每個位置建設基站的費用也不同，且覆蓋范圍也不同。表1中列出了每個位置建設基站的費用以及能夠覆蓋的社區，表2列出了每個社區的人口數。圖1表1 每個位置建設基站的費用及所能覆蓋的社區位置1234567費用（百萬元）9.57191417.51311覆蓋社區1,2,42,3,54,7,8,105,6,8,98,9,127,10,11,12,1512,13,14,15 表2 每個社區的人口數量社區123456789101112131415人口（千人）24136947512.5101161493.56問題一：在不超過5000萬建設費用的情況下，在何處建設基站，能夠覆蓋盡可能多的人口；問題二：考慮到基站出現故障維修的時候可能會出現所覆蓋的社區信號中斷等問題，為此對通訊資費進行了調整，規定，僅有一個基站信號覆蓋的小區通訊資費按正常資費的68%收取，有兩個或兩個以上基站信號覆蓋的小區的通訊資費按正常收取，針對于5000萬元的預算，應該如何建設基站，才能夠使得資費的收入達到最大。2、 問題的分析 手機是通過在地面上建立了大量的無線基站來傳遞信號,達到通話目的。若某手機運營商準備在一個目前尚未覆蓋的區域開展業務，則需要考慮基站的覆蓋能力，即某基站覆蓋的那些社區以及社區的人數等問題，在此基礎上建立基站網絡，最大程度上服務于小區的居民。根據題目條件，為了更好地分析問題，我們將基站對于小區的覆蓋情況用下表來描述。表3每個基站所能覆蓋的社區1234567891011121314151OOO2OOO3OOOO4OOOO5OOO6OOOOO7OOOO考慮到有的小區僅僅只有一個基站覆蓋，因此要想實現所有社區的全面覆蓋，有些基站是不能缺少的。例如，1號、3號、6號、11號、13號、14號社區均只可能有一個基站覆蓋，那么為這些社區服務的基站是必不可少的。因此，基站1號、2號、4號、6號、7號必須要設。建設這些基站的費用9.5+7+14+13+11=54.550;此時，僅僅必須建設的基站的費用已經不能滿足要求。因此，要想在實現不超過5000萬建設費用的情況下實現對所有社區的覆蓋是不可能的。針對問題一： 建立0-1整數規劃，通過對題目條件和問題的挖掘，列寫出規模型中的目標函數和約束條件。運用數學軟件lingo求解，得到合理的基站建設方案。針對問題二： 在滿足基站建設成本不超過5000萬元的情況下，確定一個合理的基站建設方案，使得運營商的資費收入最高。 問題關鍵在于確定每一個社區用哪幾個社區覆蓋，然后計算根據題目中的“僅有一個基站信號覆蓋的小區通訊資費按正常資費的68%收取，有兩個或兩個以上基站信號覆蓋的小區的通訊資費按正常收取”的原則，可以列寫出關于資費收入的函數表達式。運用數學軟件lingo最終把滿足條件的基站建設方案解出，最終確定出最理想的基站建設方案。3、 模型的假設與符號的說明3.1模型的假設（1）若某社區處在某一基站覆蓋范圍內,則該社區中的人口全部被該基站覆蓋；（2）各社區的手機使用率相同；（3）每位手機使用者的通訊資費相同；（4）該區域只存在這一種通信網絡；（5）每個基站覆蓋且僅覆蓋圖1所列出的覆蓋區域；（6）通訊信號不受地形地貌,氣候變化等因素影響；（7）社區人口保持不變；（8）不考慮手機漫游等情況；（9）每個基站位置最多只建一個基站。3.2符號的說明 表示第i個基站建設情況（i=1,2,.7），當=1時，表示第i個基站要被建設； 當=0時表示第i個基站不要被建設 表示第j個社區被覆蓋情況（j=1,2,.15）,當=1時，表示第j個社區被覆蓋；當=0時表示第j個社區未被覆蓋 表示第j個社區的人口數（j=1,2,.15） 表示第i個基站被建設所需的費用(i=1,2,.7) 表示第j個社區被覆蓋情況（j=1,2,.15）,當j=i，表示第j個社區被多個基站覆蓋；當=0.68時，表示第j個社區被1個基站覆蓋；當=0時表示第j個社區未被覆蓋4、 模型的建立及求解4.1模型的建立問題一：設（i=1，2,.7表示7個中繼站)表述每一個基站的建設情況。引入0-1變量，即= 1,表示第i個基站要建立 0，表示第i個基站不建立在此模型的建立過程中，由于同一個社區可能有多個基站覆蓋，如果覆蓋同一社區的基站都要建設時，那么基站覆蓋的人口就會被重復計算。故我們將目標轉移到社區上，每個社區的被覆蓋情況只有兩種，要么被覆蓋要么不被覆蓋我們也引入0-1變量，即 = 1, 表示第j個社區被覆蓋 0，表示第j個社區不被覆蓋這樣就可避免了對同一社區人口的重復計算。 本問題的目標是使得基站覆蓋的人口盡量多。根據表1、2、3我們可以得到目標函數：max=由于考慮到1號、3號、6號、11號、13號、14號社區均只可能有一個基站覆蓋，這里我們讓代替（即第j個社區只被第i個基站覆蓋），則目標函數：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;問題二： 題中考慮到基站出現故障維修的時候可能會出現所覆蓋的社區信號中斷等問題，為此對通訊資費進行了調整，規定，僅有一個基站信號覆蓋的小區通訊資費按正常資費的68%收取，有兩個或兩個以上基站信號覆蓋的小區的通訊資費按正常收取，為此，我們需要得到新的模型來進行求解，因為假設每個用戶的正常資費相同，所以68%可以用減少人口來求最優值，與問題一類似，考慮到1號、3號、6號、11號、13號、14號社區均只可能有一個基站覆蓋，這里我們讓代替（即第j個社區只被第i個基站覆蓋），故問題二的目標函數為：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*(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); 4.2 模型的求解問題一：根據附錄中的程序一利用LINGO求解得到最佳的方案如下表4所示：表4基站1234567建設情況不建設建設不建設建設不建設建設建設此方案所需費用為45百萬元，覆蓋人口為109.5千人。問題二：根據附錄中的程序二利用LINGO求解得到最佳的方案如下表5所示：表5基站1234567建設情況不建設建設不建設建設不建設建設建設此方案所需要的費用為45百萬元，獲得資費83.74a(a為標準的資費常數)。5、結果分析對于問題一，要求在基站建設成本不超過50百萬元的情況下，確定一個合理的基站建設方案，使得覆蓋的人口盡可能的多。所以我們根據題意建立了0-1規劃模型，運用LONGO軟件對規劃模型求解，得到在2,4,6,7號位置建設基站時，覆蓋人口最多為109.5千人，同時建設基站的費用為45百萬元，滿足約束條件中的費用不超過50百萬的要求。對于問題二，要求的是在滿足基站建設成本不超過5000萬元預算條件下，怎樣建設基站，使得運營商的資費收入最高。根據題目中“僅有一個基站信號覆蓋的小區人均通訊資費按正常資費的68%收取，而有兩個或兩個以上站信號覆蓋的小區人均的通訊資費按正常收取”的要求，我們運用了0-1規劃方法，并且用lingo數學軟件得出最大資費收益為S=83.74a 。6、優化方向該模型巧妙的解決了相鄰信號站重復覆蓋的人口數的問題，使得LINGO求解方便，缺點是當數據量更大時計算會比較復雜，所以可以考慮用MATLAB編程求解，列出基站和小區的關系矩陣。并且考慮問題時我們只考慮了兩個重要的因素， 因此，對于本問題的延伸，可更改規劃目標，并加入更多的約束條件，如：通過研究得出地區信號覆蓋層數對信號質量的影響，繼而影響用戶數量及收費標準，在通過各種方法將對這些因素進行定量分析，建立合理的基站最大覆蓋模型。以最大收益為目標函數。新問題的規劃方法可以再上述模型為框架的基礎上修改而得。7、參考文獻1.胡運權 編著運籌學教程 清華大學出版社 2007.04第三版；2.蔣啟源 編著數學模型 高等教育出版社 2003.08第三版；3.吳禮斌，李柏年 數學實驗與建模 M，北京：國防工業出版社，2007年；4王兵團 數學建模基礎M，北京：北京交通大學出版社，2004年；5胡守信，李柏年 基于MATLAB的數學試驗M，北京：科學出版社，2004年；6李明月 移動通訊基站建設問題/view/72d9ab3c0066f5335a812111.html 2012.12.17/2015.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); 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運行結果：Local optimal solution found. Objective value: 109.5000 Extended solver steps: 3 Total solver iterations: 185 Variable Value Reduced Cost X1 0.000000 -2.000000 Y2 1.000000 0.000000 X2 1.000000 -13.00000 Y4 0.000000 0.000000 Y5 1.000000 0.000000 X4 1.000000 -4.000000 Y7 1.000000 0.000000 Y8 1.000000 0.000000 Y9 1.000000 0.000000 Y10 1.000000 0.000000 X6 1.000000 -6.000000 Y12 1.000000 0.000000 X7 1.000000 -12.50000 Y15 1.000000 0.000000 X3 0.000000 0.000000 X5 0.000000 0.000000 Row Slack or Surplus Dual Price1 109.5000 1.000000 2 5.000000 0.000000 3 0.000000 4.000000 4 0.000000 6.000000 5 0.000000 9.000000 6 0.000000 7.500000 7 0.000000 12.50000 8 0.000000 10.00000 9 0.000000 11.00000 10 0.000000 14.00000 11 0.000000 6.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.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(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(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運行結果： Local optimal solution found. Objective value: 109.5000 Extended solver steps: 0 Total solver iterations: 115 Variable Value Reduced Cost X1 0.000000 -2.000000 Y2 1.000000 0.000000 X2 1.000000 -13.00000 Y4 0.000000 0.000000 Y5 1.000000 0.000000 X4 1.000000 -4.000000 Y7 1.000000 0.000000 Y8 1.000000 0.000000 Y9 1.000000 0.000000 Y10 1.000000 0.000000 X6 1.000000 -6.000000 Y12 1.000000 0.000000 X7 1.000000 -12.50000 Y15 1.000000 0.000000 X3 0.000000 0.000000 X5 0.000000 0.000000 K1 0.000000 0.000000 K2 0.6800000 0.000000 K3 0.6800000 0.000000 K4 0.000000 0.000000 K5 1.000000 0.000000 K6 0.6800000 0.000000 K7 0.6800000 0.000000 K8 0.6800000 0.000000 K9 0.6800000 0.000000 K10 0.6800000 0.000000 K11 0.6800000 0.000000 K12 1.000000 0.000000 K13 0.6800000 0.000000 K14 0.6800000 0.000000 K15 1.000000 0.000000 S 83.74000 0.000000 Row Slack or Surplus Dual Price 1 109.5000 1.000000 2 5.000000 0.000000 3 0.000000 4.000000 4 0.000000 6.000000 5 0.000000 9.000000 6 0.000000 7.500000 7 0.000000 12.50000 8 0.000000 10.00000 9 0.000000 11.00000 10 0.00000