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

摘要在手機(jī)普遍流行的今天，建設(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ū)人口之和，即max=，根據(jù)題目要求建立約束條件，并用數(shù)學(xué)軟件LINGO對(duì)其模型求解，得到最優(yōu)解。對(duì)于問題二： 同樣運(yùn)用0-1整數(shù)規(guī)劃模型，建立目標(biāo)函數(shù)時(shí)，此處假設(shè)每個(gè)用戶的正常資費(fèi)相同，所以68%可以用減少人口來求最優(yōu)值，故問題二的目標(biāo)函數(shù)為：max=上述模型得到最優(yōu)解結(jié)果如下：研究問題建中繼站位置所需費(fèi)用最優(yōu)值問題一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、 問題的重述某手機(jī)運(yùn)營商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開展業(yè)務(wù)，計(jì)劃投資5000萬元來建設(shè)基站。該區(qū)域由15個(gè)社區(qū)組成，有7個(gè)位置可以建設(shè)基站，每個(gè)基站只能覆蓋有限個(gè)社區(qū)。圖1是該區(qū)域的示意圖，每個(gè)社區(qū)簡化為一個(gè)多邊形，每個(gè)可以建設(shè)基站的位置已用黑點(diǎn)標(biāo)出。由于地理位置等各種條件的不同，每個(gè)位置建設(shè)基站的費(fèi)用也不同，且覆蓋范圍也不同。表1中列出了每個(gè)位置建設(shè)基站的費(fèi)用以及能夠覆蓋的社區(qū)，表2列出了每個(gè)社區(qū)的人口數(shù)。圖1表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人口（千人）24136947512.5101161493.56問題一：在不超過5000萬建設(shè)費(fèi)用的情況下，在何處建設(shè)基站，能夠覆蓋盡可能多的人口；問題二：考慮到基站出現(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、 問題的分析 手機(jī)是通過在地面上建立了大量的無線基站來傳遞信號(hào),達(dá)到通話目的。若某手機(jī)運(yùn)營商準(zhǔn)備在一個(gè)目前尚未覆蓋的區(qū)域開展業(yè)務(wù)，則需要考慮基站的覆蓋能力，即某基站覆蓋的那些社區(qū)以及社區(qū)的人數(shù)等問題，在此基礎(chǔ)上建立基站網(wǎng)絡(luò)，最大程度上服務(wù)于小區(qū)的居民。根據(jù)題目條件，為了更好地分析問題，我們將基站對(duì)于小區(qū)的覆蓋情況用下表來描述。表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ū)服務(wù)的基站是必不可少的。因此，基站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.550;此時(shí)，僅僅必須建設(shè)的基站的費(fèi)用已經(jīng)不能滿足要求。因此，要想在實(shí)現(xiàn)不超過5000萬建設(shè)費(fèi)用的情況下實(shí)現(xiàn)對(duì)所有社區(qū)的覆蓋是不可能的。針對(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模型的假設(shè)（1）若某社區(qū)處在某一基站覆蓋范圍內(nèi),則該社區(qū)中的人口全部被該基站覆蓋；（2）各社區(qū)的手機(jī)使用率相同；（3）每位手機(jī)使用者的通訊資費(fèi)相同；（4）該區(qū)域只存在這一種通信網(wǎng)絡(luò)；（5）每個(gè)基站覆蓋且僅覆蓋圖1所列出的覆蓋區(qū)域；（6）通訊信號(hào)不受地形地貌,氣候變化等因素影響；（7）社區(qū)人口保持不變；（8）不考慮手機(jī)漫游等情況；（9）每個(gè)基站位置最多只建一個(gè)基站。3.2符號(hào)的說明 表示第i個(gè)基站建設(shè)情況（i=1,2,.7），當(dāng)=1時(shí)，表示第i個(gè)基站要被建設(shè)； 當(dāng)=0時(shí)表示第i個(gè)基站不要被建設(shè) 表示第j個(gè)社區(qū)被覆蓋情況（j=1,2,.15）,當(dāng)=1時(shí)，表示第j個(gè)社區(qū)被覆蓋；當(dāng)=0時(shí)表示第j個(gè)社區(qū)未被覆蓋 表示第j個(gè)社區(qū)的人口數(shù)（j=1,2,.15） 表示第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)=0.68時(shí)，表示第j個(gè)社區(qū)被1個(gè)基站覆蓋；當(dāng)=0時(shí)表示第j個(gè)社區(qū)未被覆蓋4、 模型的建立及求解4.1模型的建立問題一：設(shè)（i=1，2,.7表示7個(gè)中繼站)表述每一個(gè)基站的建設(shè)情況。引入0-1變量，即= 1,表示第i個(gè)基站要建立 0，表示第i個(gè)基站不建立在此模型的建立過程中，由于同一個(gè)社區(qū)可能有多個(gè)基站覆蓋，如果覆蓋同一社區(qū)的基站都要建設(shè)時(shí)，那么基站覆蓋的人口就會(huì)被重復(fù)計(jì)算。故我們將目標(biāo)轉(zhuǎn)移到社區(qū)上，每個(gè)社區(qū)的被覆蓋情況只有兩種，要么被覆蓋要么不被覆蓋我們也引入0-1變量，即 = 1, 表示第j個(gè)社區(qū)被覆蓋 0，表示第j個(gè)社區(qū)不被覆蓋這樣就可避免了對(duì)同一社區(qū)人口的重復(fù)計(jì)算。 本問題的目標(biāo)是使得基站覆蓋的人口盡量多。根據(jù)表1、2、3我們可以得到目標(biāo)函數(shù)：max=由于考慮到1號(hào)、3號(hào)、6號(hào)、11號(hào)、13號(hào)、14號(hào)社區(qū)均只可能有一個(gè)基站覆蓋，這里我們讓代替（即第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;問題二： 題中考慮到基站出現(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)行求解，因?yàn)榧僭O(shè)每個(gè)用戶的正常資費(fèi)相同，所以68%可以用減少人口來求最優(yōu)值，與問題一類似，考慮到1號(hào)、3號(hào)、6號(hào)、11號(hào)、13號(hào)、14號(hào)社區(qū)均只可能有一個(gè)基站覆蓋，這里我們讓代替（即第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*(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建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)此方案所需費(fèi)用為45百萬元，覆蓋人口為109.5千人。問題二：根據(jù)附錄中的程序二利用LINGO求解得到最佳的方案如下表5所示：表5基站1234567建設(shè)情況不建設(shè)建設(shè)不建設(shè)建設(shè)不建設(shè)建設(shè)建設(shè)此方案所需要的費(fèi)用為45百萬元，獲得資費(fèi)83.74a(a為標(biāo)準(zhǔn)的資費(fèi)常數(shù))。5、結(jié)果分析對(duì)于問題一，要求在基站建設(shè)成本不超過50百萬元的情況下，確定一個(gè)合理的基站建設(shè)方案，使得覆蓋的人口盡可能的多。所以我們根據(jù)題意建立了0-1規(guī)劃模型，運(yùn)用LONGO軟件對(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ū)人均通訊資費(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ù)雜，所以可以考慮用MATLAB編程求解，列出基站和小區(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)行定量分析，建立合理的基站最大覆蓋模型。以最大收益為目標(biāo)函數(shù)。新問題的規(guī)劃方法可以再上述模型為框架的基礎(chǔ)上修改而得。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é)建模基礎(chǔ)M，北京：北京交通大學(xué)出版社，2004年；5胡守信，李柏年 基于MATLAB的數(shù)學(xué)試驗(yàn)M，北京：科學(xué)出版社，2004年；6李明月 移動(dòng)通訊基站建設(shè)問題/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運(yùn)行結(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運(yùn)行結(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