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

摘要在手機普遍流行的今天，建設基站的問題分析對于運營商來說很有必要。本文針對現(xiàn)有的條件和題目的要求進行討論。在建設此模型中，核心運用到了0-1整數(shù)規(guī)劃模型，且運用lingo軟件求解。對于問題一： 我們引入0-1變量，建立目標函數(shù)：覆蓋人口最大數(shù)=所有被覆蓋的社區(qū)人口之和，即max=，根據(jù)題目要求建立約束條件，并用數(shù)學軟件LINGO對其模型求解，得到最優(yōu)解。對于問題二： 同樣運用0-1整數(shù)規(guī)劃模型，建立目標函數(shù)時，此處假設每個用戶的正常資費相同，所以68%可以用減少人口來求最優(yōu)值，故問題二的目標函數(shù)為：max=上述模型得到最優(yōu)解結(jié)果如下：研究問題建中繼站位置所需費用最優(yōu)值問題一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ū)簡化為一個多邊形，每個可以建設基站的位置已用黑點標出。由于地理位置等各種條件的不同，每個位置建設基站的費用也不同，且覆蓋范圍也不同。表1中列出了每個位置建設基站的費用以及能夠覆蓋的社區(qū)，表2列出了每個社區(qū)的人口數(shù)。圖1表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人口（千人）24136947512.5101161493.56問題一：在不超過5000萬建設費用的情況下，在何處建設基站，能夠覆蓋盡可能多的人口；問題二：考慮到基站出現(xiàn)故障維修的時候可能會出現(xiàn)所覆蓋的社區(qū)信號中斷等問題，為此對通訊資費進行了調(diào)整，規(guī)定，僅有一個基站信號覆蓋的小區(qū)通訊資費按正常資費的68%收取，有兩個或兩個以上基站信號覆蓋的小區(qū)的通訊資費按正常收取，針對于5000萬元的預算，應該如何建設基站，才能夠使得資費的收入達到最大。2、 問題的分析 手機是通過在地面上建立了大量的無線基站來傳遞信號,達到通話目的。若某手機運營商準備在一個目前尚未覆蓋的區(qū)域開展業(yè)務，則需要考慮基站的覆蓋能力，即某基站覆蓋的那些社區(qū)以及社區(qū)的人數(shù)等問題，在此基礎上建立基站網(wǎng)絡，最大程度上服務于小區(qū)的居民。根據(jù)題目條件，為了更好地分析問題，我們將基站對于小區(qū)的覆蓋情況用下表來描述。表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.550;此時，僅僅必須建設的基站的費用已經(jīng)不能滿足要求。因此，要想在實現(xiàn)不超過5000萬建設費用的情況下實現(xiàn)對所有社區(qū)的覆蓋是不可能的。針對問題一： 建立0-1整數(shù)規(guī)劃，通過對題目條件和問題的挖掘，列寫出規(guī)模型中的目標函數(shù)和約束條件。運用數(shù)學軟件lingo求解，得到合理的基站建設方案。針對問題二： 在滿足基站建設成本不超過5000萬元的情況下，確定一個合理的基站建設方案，使得運營商的資費收入最高。 問題關鍵在于確定每一個社區(qū)用哪幾個社區(qū)覆蓋，然后計算根據(jù)題目中的“僅有一個基站信號覆蓋的小區(qū)通訊資費按正常資費的68%收取，有兩個或兩個以上基站信號覆蓋的小區(qū)的通訊資費按正常收取”的原則，可以列寫出關于資費收入的函數(shù)表達式。運用數(shù)學軟件lingo最終把滿足條件的基站建設方案解出，最終確定出最理想的基站建設方案。3、 模型的假設與符號的說明3.1模型的假設（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），當=1時，表示第i個基站要被建設； 當=0時表示第i個基站不要被建設 表示第j個社區(qū)被覆蓋情況（j=1,2,.15）,當=1時，表示第j個社區(qū)被覆蓋；當=0時表示第j個社區(qū)未被覆蓋 表示第j個社區(qū)的人口數(shù)（j=1,2,.15） 表示第i個基站被建設所需的費用(i=1,2,.7) 表示第j個社區(qū)被覆蓋情況（j=1,2,.15）,當j=i，表示第j個社區(qū)被多個基站覆蓋；當=0.68時，表示第j個社區(qū)被1個基站覆蓋；當=0時表示第j個社區(qū)未被覆蓋4、 模型的建立及求解4.1模型的建立問題一：設（i=1，2,.7表示7個中繼站)表述每一個基站的建設情況。引入0-1變量，即= 1,表示第i個基站要建立 0，表示第i個基站不建立在此模型的建立過程中，由于同一個社區(qū)可能有多個基站覆蓋，如果覆蓋同一社區(qū)的基站都要建設時，那么基站覆蓋的人口就會被重復計算。故我們將目標轉(zhuǎn)移到社區(qū)上，每個社區(qū)的被覆蓋情況只有兩種，要么被覆蓋要么不被覆蓋我們也引入0-1變量，即 = 1, 表示第j個社區(qū)被覆蓋 0，表示第j個社區(qū)不被覆蓋這樣就可避免了對同一社區(qū)人口的重復計算。 本問題的目標是使得基站覆蓋的人口盡量多。根據(jù)表1、2、3我們可以得到目標函數(shù)：max=由于考慮到1號、3號、6號、11號、13號、14號社區(qū)均只可能有一個基站覆蓋，這里我們讓代替（即第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;問題二： 題中考慮到基站出現(xiàn)故障維修的時候可能會出現(xiàn)所覆蓋的社區(qū)信號中斷等問題，為此對通訊資費進行了調(diào)整，規(guī)定，僅有一個基站信號覆蓋的小區(qū)通訊資費按正常資費的68%收取，有兩個或兩個以上基站信號覆蓋的小區(qū)的通訊資費按正常收取，為此，我們需要得到新的模型來進行求解，因為假設每個用戶的正常資費相同，所以68%可以用減少人口來求最優(yōu)值，與問題一類似，考慮到1號、3號、6號、11號、13號、14號社區(qū)均只可能有一個基站覆蓋，這里我們讓代替（即第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*(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 模型的求解問題一：根據(jù)附錄中的程序一利用LINGO求解得到最佳的方案如下表4所示：表4基站1234567建設情況不建設建設不建設建設不建設建設建設此方案所需費用為45百萬元，覆蓋人口為109.5千人。問題二：根據(jù)附錄中的程序二利用LINGO求解得到最佳的方案如下表5所示：表5基站1234567建設情況不建設建設不建設建設不建設建設建設此方案所需要的費用為45百萬元，獲得資費83.74a(a為標準的資費常數(shù))。5、結(jié)果分析對于問題一，要求在基站建設成本不超過50百萬元的情況下，確定一個合理的基站建設方案，使得覆蓋的人口盡可能的多。所以我們根據(jù)題意建立了0-1規(guī)劃模型，運用LONGO軟件對規(guī)劃模型求解，得到在2,4,6,7號位置建設基站時，覆蓋人口最多為109.5千人，同時建設基站的費用為45百萬元，滿足約束條件中的費用不超過50百萬的要求。對于問題二，要求的是在滿足基站建設成本不超過5000萬元預算條件下，怎樣建設基站，使得運營商的資費收入最高。根據(jù)題目中“僅有一個基站信號覆蓋的小區(qū)人均通訊資費按正常資費的68%收取，而有兩個或兩個以上站信號覆蓋的小區(qū)人均的通訊資費按正常收取”的要求，我們運用了0-1規(guī)劃方法，并且用lingo數(shù)學軟件得出最大資費收益為S=83.74a 。6、優(yōu)化方向該模型巧妙的解決了相鄰信號站重復覆蓋的人口數(shù)的問題，使得LINGO求解方便，缺點是當數(shù)據(jù)量更大時計算會比較復雜，所以可以考慮用MATLAB編程求解，列出基站和小區(qū)的關系矩陣。并且考慮問題時我們只考慮了兩個重要的因素， 因此，對于本問題的延伸，可更改規(guī)劃目標，并加入更多的約束條件，如：通過研究得出地區(qū)信號覆蓋層數(shù)對信號質(zhì)量的影響，繼而影響用戶數(shù)量及收費標準，在通過各種方法將對這些因素進行定量分析，建立合理的基站最大覆蓋模型。以最大收益為目標函數(shù)。新問題的規(guī)劃方法可以再上述模型為框架的基礎上修改而得。7、參考文獻1.胡運權(quán) 編著運籌學教程 清華大學出版社 2007.04第三版；2.蔣啟源 編著數(shù)學模型 高等教育出版社 2003.08第三版；3.吳禮斌，李柏年 數(shù)學實驗與建模 M，北京：國防工業(yè)出版社，2007年；4王兵團 數(shù)學建?；AM，北京：北京交通大學出版社，2004年；5胡守信，李柏年 基于MATLAB的數(shù)學試驗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運行結(jié)果：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運行結(jié)果： 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