数学建模课程设计——优化问题

1、摘要在手机普遍流行的今天，建设基站的问题分析对于运营商来说很有必要。本文针对现有的条件和题目的要求进行讨论。在建设此模型中，核心运用到了0-1整数规划模型，且运用lingo软件求解。对于问题一：我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即15max=j4py.,根据题目要求建立约束条件，并用数学软件LINGO对其模型求解，得到最优解。对于问题二：同样运用0-1整数规划模型，建立目标函数时，此处假设每个用户的正常资费相同，所以68%T以用减少人口来求最优值，故问题二的目标函数为：15max=Pjkj上述模型得到最优解结果如下:研究问题建中继站位置所需费用最优值问

2、题一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是该区域的示意图，每个社区简化为一个多边形，每个可以建设基站的位置已用

3、黑点标出。由于地理位置等各种条件的不同，每个位置建设基站的费用也不同，且覆盖范围也不同。表1中列出了每个位置建设基站的费用以及能够覆盖的社区，表2列出了每个社区的人口数。表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人口（千人）24136947.512.5101161493.56问题一：在不超过5000万建设费用的情况下，在何处建设基站，能够覆盖尽可能多的

4、人口；问题二：考虑到基站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个基站信号覆盖的小区通讯资费按正常资费的68%攵取，有两个或两个以上基站信号覆盖的小区的通讯资费按正常收取，针对于5000万元的预算，应该如何建设基站，才能够使得资费的收入达到最大。2、问题的分析手机是通过在地面上建立了大量的无线基站来传递信号，达到通话目的。若某手机运营商准备在一个目前尚未覆盖的区域开展业务，则需要考虑基站的覆盖能力，即某基站覆盖的那些社区以及社区的人数等问题，在此基础上建立基站网络，最大程度上服务于小区的居民。根据题目条件，为了更好地分析问题，我们将基站对于

5、小区的覆盖情况用下表来描述。表3每个基站所能覆盖的社区1234567891011121314151OOO2OOO3OOOO4OOOO5OOO6OOOOO7OOOO考虑到有的小区仅仅只有一个基站覆盖，因此要想实现所有社区的全面覆盖，有些基站是不能缺少的。例如，1号、3号、6号、11号、13号、14号社区均只可能有一个基站覆盖，那么为这些社区服务的基站是必不可少的。因此，基站1号、2号、4号、6号、7号必须要设。建设这些基站的费用9.5+7+14+13+11=54.550;此时，仅仅必须建设的基站的费用已经不能满足要求。因此，要想在实现不超过5000万建设费用的情况下实现对所有社区的覆盖是不可能的

6、。针对问题一：建立0-1整数规划，通过对题目条件和问题的挖掘，列写出规模型中的目标函数和约束条件。运用数学软件lingo求解，得到合理的基站建设方案。针对问题二：在满足基站建设成本不超过5000万元的情况下，确定一个合理的基站建设方案，使得运营商的资费收入最高。问题关键在于确定每一个社区用哪几个社区覆盖，然后计算根据题目中的“仅有一个基站信号覆盖的小区通讯资费按正常资费的68%攵取，有两个或两个以上基站信号覆盖的小区的通讯资费按正常收取”的原则，可以列写出关于资费收入的函数表达式。运用数学软件lingo最终把满足条件的基站建设方案解出，最终确定出最理想的基站建设方案3、模型的假设与符号的说明3

7、.1 模型的假设(1)若某社区处在某一基站覆盖范围内，则该社区中的人口全部被该基站覆盖;(2)各社区的手机使用率相同；(3)每位手机使用者的通讯资费相同；(4)该区域只存在这一种通信网络；(5)每个基站覆盖且仅覆盖图1所列出的覆盖区域；(6)通讯信号不受地形地貌，气候变化等因素影响；(7)社区人口保持不变；(8)不考虑手机漫游等情况；(9)每个基站位置最多只建一个基站。3.2 符号的说明表示第i个基站建设情况(i=1,2,.7)，当X=1时，表示第i个基站要被建设；当Xi=0时表示第i个基站不要被建设V、表示第j个社区被覆盖情况(j=1,2,.15)，当y1时，表示第j个社区被覆盖；当yr0时

8、表示第j个社区未被覆盖Pj表示第j个社区的人口数(j=1,2,.15kj表示第i个基站被建设所需的费用(i=1,2,.7)表示第j个社区被覆盖情况(j=1,2,.15)，当j=i,表示第j个社区被多个基站覆盖；当kj=0.68时，表示第j个社区被1个基站覆盖；当匕=0时表示第j个社区未被覆盖4、模型的建立及求解4.1模型的建立问题一：设Xi(i=1,2,.7表示7个中继站)表述每一个基站的建设情况。引入0-1变量，即Xi=r1,表示第i个基站要建立0,表示第i个基站不建立在此模型的建立过程中，由于同一个社区可能有多个基站覆盖，如果覆盖同一社区的基站都要建设时，那么基站覆盖的人口就会被重复计算。

9、故我们将目标转移到社区上，每个社区的被覆盖情况只有两种，要么被覆盖要么不被覆盖我们也引入0-1变量，即y=1,表示第j个社区被覆盖0,表小第j个社区不被覆盖1、2、3我们可以得到这样就可避免了对同一社区人口的重复计算。本问题的目标是使得基站覆盖的人口尽量多。根据表15目标函数:max=j1PjYj由于考虑到1号、3号、6号、11号、13号、14号社区均只可能有一个基站覆盖，这里我们让Xi代替丫上(即第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)+

10、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%T以用减少人口来求最优值，与问题一类似，考虑到1号、3号、6号、11号、13号、1

11、4号社区均只可能有一个基站覆盖，这里我们让xi代替丫上(即第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

12、)+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建设情况不建

13、设建设不建设建设不建设建设建设此方案所需要的费用为45百万元，获得资费83.74a（a为标准的资费常数）5、结果分析对于问题一，要求在基站建设成本不超过50百万元的情况下，确定一个合理的基站建设方案，使得覆盖的人口尽可能的多。所以我们根据题意建立了0-1规划模型，运用LONG酸件对规划模型求解，得到在2,4,6,7号位置建设基站时，覆盖人口最多为109.5千人，同时建设基站的费用为45百万元，满足约束条件中的费用不超过50百万的要求。对于问题二，要求的是在满足基站建设成本不超过5000万元预算条件下，怎样建设基站，使得运营商的资费收入最高。根据题目中“仅有一个基站信号覆盖的小区人均通讯资费按正

14、常资费的68%攵取，而有两个或两个以上站信号覆盖的小区人均的通讯资费按正常收取”的要求，我们运用了0-1规划方法，并且用lingo数学软件得出最大资费收益为S=83.74a。6、优化方向该模型巧妙的解决了相邻信号站重复覆盖的人口数的问题，使得LINGO求解方便，缺点是当数据量更大时计算会比较复杂，所以可以考虑用MATLA的程求解，列出基站和小区的关系矩阵。并且考虑问题时我们只考虑了两个重要的因素，因此，对于本问题的延伸，可更改规划目标，并加入更多的约束条件，如：通过研究得出地区信号覆盖层数对信号质量的影响，继而影响用户数量及收费标准，在通过各种方法将对这些因素进行定量分析，建立合理的基站最大覆

15、盖模型。以最大收益为目标函数。新问题的规划方法可以再上述模型为框架的基础上修改而得。7、参考文献1,胡运权编著运筹学教程清华大学出版社2007.04第三版；2.蒋启源编著数学模型高等教育出版社2003.08第三版；3,吴礼斌，李柏年数学实验与建模M,北京：国防工业出版社，2007年；4 王兵团数学建*K基础M,北京：北京交通大学出版社，2004年；5 胡守信，李柏年基于MATLAB的数学试验M,北京：科学出版社，2004年；6李明月移动通讯基站建设问题2012.12.17/2015.07.02附录:程序一：问题一model:max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)

16、+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#e

17、q#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运行结果：Localoptimalsolutionfound.Objectivevalue:109.5000Extendedsolversteps:3Totalsolveriterations:185VariableValueReducedCostX10.000000-2.000000Y21.0000000.000000X21.000000-13.00000Y40.0000000.000000Y51.0000000

18、.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.000000RowSlackorSurplusDualPrice1109.50001.00000025.0000000.00000030.0000004.00000040.0000006.0

19、0000050.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.5*x7+6*(y15);(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)=50;y

20、2=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);

21、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)+1

22、3*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运行结果：Localoptimalsolutionfound.Objectivevalue:Extendedsolversteps:Totalsolve

23、riterations:109.50000115VariableValueReducedCostX10.000000-2.000000Y21.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.000000

24、0.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.00