交通系统分析期末论文 GSM基站选址问题的求解.doc

交通系统分析期末论文 GSM基站选址问题的求解 摘要 本文旨在解决覆盖问题,类似于以前学习过的选址最优问题。首先想到的就是用0-1规划来做并依此设置目标函数以及约束函数，这里着重需要考虑的就是覆盖范围和资金之间的关系并依此得到最优的解决方案。同样这题也可以观察到这是个有限个组合，可以通过排列组合的方式进行求解。在这里对问题一我又选用用0-1规划来建立模型进而用lingo求出最优答案。通过两种模型的比较都得到了相似的解即：在2、4、6、7位置设中继站，0-1规划求的的答案为覆盖109千人，枚举法求的是覆盖109.5千人。(需要说明的是在进行模型二枚举法求解的时候在关于基站可能性的筛选过程中借鉴了网上的相关算法详见附录1) 对于问题二，通过利用问题一枚举法的应用进行求解，在这里需要对于资费进行考虑。由于只被一个中继站覆盖的社区和被两个或两个以上中继站覆盖的社区的资费不同，所以把社区分为三类：只能被一个中继站覆盖的社区，能被两个中继站覆盖的社区和能被三个中继站覆盖的社区，根据不同类型的社区进行相应的求解。（对于问题二需要说明的是这是建立在问题一枚举法的基础之上的）最后得出最优的答案为：85.35a百万元。（a为手机的使用率）关键词： 0-1规划 Lingo 枚举 排列组合 一、问题重述某手机运营商准备在一个目前尚未覆盖的区域开展业务，计划投资5000万元来建设中继站。该区域由15个社区组成，有7个位置可以建设中继站，每个中继站只能覆盖有限个社区。图1是该区域的示意图，每个社区简化为一个多边形，每个可以建设中继站的位置已用黑点标出。由于地理位置等各种条件的不同，每个位置建设中继站的费用也不同，且覆盖范围也不同。表1中列出了每个位置建设中继站的费用以及能够覆盖的社区，表2列出了每个社区的人口数。 表1 每个位置建设中继站的费用及所能覆盖的社区位置1234567费用（百万元）96.52014.5191310.5覆盖社区1,2,42,3,54,7,8,105,6,8,98,9,127,10,11,12,1512,13,14,15 表2 每个社区的人口数量社区123456789101112131415人口（千人）24136948121011614936问题一：在不超过5000万建设费用的情况下，在何处建设中继站，能够覆盖尽可能多的人口；问题二：考虑到中继站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取，有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取，针对于5000万元的预算，应该如何建设中继站，才能够使得资费的收入达到最大。 二、问题分析 在资金和备选地址确定的情况下，对手机中继站的选址问题进行求解和优化。 针对问题一，因为中继站只有建设和不建设两种情况，因此我们可以用0-1规划的思想建立模型。但由于同一个社区可能有多个中继站覆盖，如果覆盖同一社区的中继站都要建设时，那么中继站覆盖的人数就会被重复计算，所以在模型的建立中，必须要减去被重复计算的人数。 针对问题二，在中继站建设成本不超过5000万的基础上对于不同覆盖范围的小区采取不同的收费方式从而获得利益的最大化。其关键在于每一个小区由哪几个基站负责（见下表）。然后根据题目中所给的基本条件进行目标函数和约束函数的确定，进而求出最优解。最多可被覆盖的中继站数123社区1，3，6，11，13，142，4，5，7，9，10，158，12 三、模型假设1. 假设某社区处在某一中继站覆盖范围内,则该社区中的人口全部被该中继站覆盖。2. 假设只有一家移动运营商在此地开展业务，不考虑商家之间的竞争。3. 假设每个社区的人口保持不变。4. 假设每个中继站的位置只能建设一个中继站。5. 假设每个中继站的服务水平都保持一样。6. 假设假设每一个小区内移动通信客户所占总人口的比例相同。 四、符号说明符号含义i=1表示建立中继站，i=0表示不建立中继站第j个中继站覆盖的人数第i个中继站的建设费用第i个社区的人数Z表示重复计算的人数手机使用率S 总资费 五、模型建立与求解5.1问题一的求解5.1.1模型的建立考虑到计算覆盖人数会有重复的情况可以先确定初始目标函数： 其中或；接着可以考虑重复计算的人数可得到重复计算的人数为：Z=由上面可得到目标最终的目标函数为：约束条件为建设的费用不超过5000万元故可以得到约束函数为：5.1.2模型的求解利用lingo进行求解下面是部分代码和相关结果的截图： 有上表我们可以看到最优的解出现时，在中继站的建设位置2、4、6、7建设中继站能得到最优解此时最优解为109（千人）。即当X2=1、X4=1、X6=1、X7=0、X1=0、X3=0、X5=0时取最大值109.5.2.1模型的建立 利用枚举法的求解 由问题一的分析可知，可以建设三个或四个基站。若方案在不超过5000万建设费用的情况下还可以增加建设基站，则可以把此类方案排除在外，按此方法可排除26种。如果某种方案的总费用超过5000万我们也可以把其排除在外，此时排除24种方案。最后还剩下20种。根据第一次选择可以得到以下20种方案，按照题中所给的表1和表2可得各种方案覆盖的社区及总人数如表6所示：各种方案覆盖的社区及总人数建站位置建设费用M（百万元）覆盖社区覆盖人口W2，3，543.52，3，4，5，7,8,9,10,1286.51，3，5461,2,4,7,8,9,10,1266.54，5，742.55,6,8,9,12,13,14,15683，4，7444,5,6,7,8,9,10,12,13,14,1592.53，5，747.54,7,8,9,10,12,13,14,1579.53，5，649.55,6,7,8,9,10,11,12,15733，4，6464,5,6,7,8,9,10,11,12,1575.51，2，3，449.51,2,3,4,5,6,7,8,9,10791，2，3，648.51,2,3,4,5,7,8,10,12,13,14,15911，2，3，746.51,2,3,4,5,6,8,9,12,13,14,1597.52，5，6，748.52,3,5,7,8,9,10,11,12,13,14,15105.52，3，6，7502,3,4,5,7,8,10,11,12,13,14,15101.52，4，6，7452,3,5,6,7,8,9,10,11,12,13,14,15109.51，2，4，5481,2,3,4,5,6,8,9,1280.51，2，5，6471,2,3,4,5,7,8,9,10,11,12,15104.51，2，6，740.51,2,3,4,5,7,10,11,12,13,14,15911，2，4，643.51,2,3,4,5,6,7,8,9,10,11,12,1594.51，2，4，741.41,2,3,4,5,6,8,9,12,13,14,15931，2，5，7451,2,3,4,5,8,9,12,13,14,15891，4，6，747.51,2,4,5,6,7,8,9,10,11,12,13,14,15104.5从上表可以看出在2，4，6，7号位置建设基站时，覆盖人口最多，为109.5千人。同时建设基站的费用为4500万元，满足题目中建设费用不超过5000万的要求。通过对两模型的比分析我们可以看到二者的数据结果基本相同故我们可以确定求的的结果真实可靠。5.3问题二的求解由题意可知，仅有一个基站信号覆盖的小区人均通讯资费按正常资费的70%收取，而有两个或两个以上基站信号覆盖的小区人均的通讯资费按正常收取，为了简便起见，在程序中我们把手机使用率简化为1。5.2.1枚举法求解由题意可知，仅有一个基站信号覆盖的小区人均通讯资费按正常资费的68%收取，而有两个或两个以上基站信号覆盖的小区人均的通讯资费按正常收取。由表6各种方案覆盖的社区及总人数和总资费收入，如下表所示： 通讯资费表建站位置信号社区分布资费收入(百万元）总资费S（百万元）2，3，5单信号2,3,4,5,7,9,10,1274*0.764.3多信号812.5*1，3，5单信号1,2,7,9,10,1248*0.752.1多信号4,818.5*4，5，7单信号5,6,13,14,1531.5*0.763.31多信号8,9,1236.5*3，4，7单信号4,5,6,7,9,10,12,13,14,1580*0.766.9多信号812.5*3，5，7单信号4,7,9,10,13,14,1573*0.774.14多信号8,1226.5*3，5，6单信号4,9,11,1528*0.764.04*多信号7,8,10,1245*3，4，6单信号4,5,6,9,11,12,1544.5*0.761.26多信号7,8,1031*1，2，3，4单信号1,3,6,7,9,1047.5*0.763.8多信号2,4,5,831.5*1，2，3，6单信号1,3,5,8,11,12,1562.5*0.772.25多信号2,4,7,1028.5*1，2，3，7单信号1,3,5,7,8,10,12,13,14,1587.5*0.769.5多信号2,410*2，5，6，7单信号2,3,5,7,8,9,10,11,13,1485.5*0.778.14多信号12,1520*2，3，6，7单信号2,3,4,5,8,11,13,1463*0.781.34多信号7,10,12,1538.5*2，4，6，7单信号2,3,6,7,8,9,10,11,13,1480.5*0.785.35多信号5,12,1529*1，2，4，5单信号1,2,4,5,6,1258*0.761.94多信号8,922.5*1，2，5，6单信号1,3,4,5,7,8,9,10,11,1596.5*0.776.82多信号2,1218*1，2，6，7单信号1,3,4,5,7,10,11,13,1467*0.769.56多信号2,12,1524*1，2，4，6单信号1,3,4,6,7,8,9,10,11,12,1581.5*0.768.42多信号2,513*1，2，4，7单信号1,3,4,6,8,9,12,13,14,1580*0.767.4多信号2,513*1，2，5，7单信号1,3,4,5,8,9,13,14,1571*0.767.7多信号2,1218*1，4，6，7单信号1,2,4,5,6,7,8,9,10,11,13,1484.5*0.779.15多信号12,1520* 从表中可以看出，在2，4，6，7号位置建设基站时，资费的收入达到最大为85.35百万元（为手机使用率）。对于问题二，要求的是在满足基站建设成本不超过5000万元预算条件下，怎样建设基站，使得运营商的资费收入最高。根据题目中“仅有一个基站信号覆盖的小区人均通讯资费按正常资费的68%收取，而有两个或两个以上基站信号覆盖的小区人均的通讯资费按正常收取”的要求，我们运用了0-1规划和枚举法两种方法，0-1规划中对被重复覆盖的社区求布尔和，用lingo数学软件得出最大资费收益为S=85.35（百万元）。枚举法中我们写出关于资费收入的函数表达式S=（单信号地区的人数*70%+多信号地区的人数*1）*算出20种方案的每种方案的资费收入，然后比较得到最大收入的方案为在2，4，6，7号位置建设基站时，资费的收入达到最大，为83.74（百万元）（为手机使用率）。同样，两种解决方法所得结果一致，这说明了这几种模型的合理性。 七、模型评价模型的推广：0-1规划模型和线性规划模型可以解决本文中的移动中继站的选址问题。仔细分析就不难发现，这一解决问题的模型可以推广到其他服务性行业的选址中的方案的确定。模型的优点：1、在0-1 规划模型中，运用加减法规则，巧妙地解决了问题中关于人口可能会被重复计算的问题。2、用排除法解决问题的过程中，很好的利用了情况有限这一条件，使得整个模型确立以后，可以在具体实行中不断改进，根据题中所给的条件进行排除。模型的缺点：1、约束条件有点简单；2、运用的模型比较简单，只用到0-1规划模型和线性规划模型，没有运用更简便的模型求解。3、采用排除法中，计算过于繁琐，计算量很大，可能还有其它的方法一次能排除几个甚至几十个方案，使得在计算上花费不少时间。参考文献：1 王兵团，数学建模基础M，北京：北京交通大学出版社，2004 年2 胡运权，运筹学基础及应用，高等教育出版社，2004.043 薛秀谦，朱开永，运筹学M,徐州：中国矿业大学出版社，2002 年4 刘承平 数学建模方法 北京：高等教育出版社，2002【附录一】问题一中排除法c+程序实现：#include#includeusing namespace std;/*int pop16=0,2,4,13,6,9,4,8,12,10,11,6,14,9,3,6;/社区人数double val7=9,6.5,20,14,5,19,13,10.5;/(每个基站费用)int com76=1,2,4,0,0,0,2,3,5,0,0,0,5,6,8,9,0,0,8,9,12,0,0,0,7,10,11,12,15,0,12,13,14,15,0,0;/17号基站可以覆盖的社区数*/double a1(char q)double m;if(q=a)m=7;if(q=b)m=9.5;if(q=c)m=11;if(q=d)m=13;if(q=e)m=14;if(q=f)m=17.5;if(q=g)m=19;return m;int main()int count=0; char i,j,k,l; for(i=a;if;i+