手机中继站选址最优方案
摘 要
本文综合利用多种模型,在资金和备选地址确定的情况下,对手机中继站的选址问题进行了求解和优化。我们首先对题中所给的数据进行了整理和分析,引入了回溯模型、0-1规划模型,为以下问题的解决作了准备。
对于问题一,我们运用两种方法,并用不同的软件求解:
? 方法一:我们引入0-1变量,建立目标函数:覆盖人口最大数=所有被覆盖的社区人
口之和,即maxM??pjbj,根据题目要求建立约束条件,并用数学软件LINGO
j?115很容易解得题目最优解;
? 方法二:联系问题的性质,我们引入了回溯模型,采用迭代加深搜索的思想,可以
在满足题目所给条件下搜索到一条到达解空间的路径。然后,根据所有的路径对应的中继站的建设情况求解出相应的中继站覆盖的人口,然后经过比较即可求得最终结果,我们运用软件MATLAB进行编程求解。
对于问题二,我们同样运用以上两种方法,只是针对题目要求略微改变目标函数,并用不同的软件求得相同解,最优方案不变,和问题一相同。 求得的结果如下表: 研究问题 问题一 问题二 建中继站位置 2,4,6,7 2,4,6,7 所需费用?50百万 44.5 44.5 最优值 覆盖中人口数109千人 获得资费85c千元 本文运用的两种方法都有它们各自的优点和不足,对于第一种方法,我们采用枚举法,我们会发现总共有27种情况,但因为数据比较少,运用LINGO软件求解,程序简单;对于第二种方法,我们采用回溯算法,需要遍历的分支相对减少,但是程序相对较复杂,比较适合数据较多的模型。
本文还对“仅有一个中继站信号覆盖的小区通讯资费按正常资费的10%~90%区间内的收取”做了讨论,得出了最优方案随百分比的改变的变化曲线图。
1101009044.544.444.344.2覆盖总人数(千)总费用(百万)8070605044.14443.943.843.7403043.600.10.20.30.40.50.6百分比0.70.80.9143.500.10.20.30.40.50.6百分比0.70.80.91
关键字:0-1规划 回溯算法 中继站 LINGO软件 MATLAB软件
1
一. 问题重述
某手机运营商准备在一个目前尚未覆盖的区域开展业务,计划投资5000万元来建设中继站。该区域由15个社区组成,有7个位置可以建设中继站,每个中继站只能覆盖有限个社区。图1是该区域的示意图,每个社区简化为一个多边形,每个可以建设中继站的位置已用黑点标出。由于地理位置等各种条件的不同,每个位置建设中继站的费用也不同,且覆盖范围也不同。表1中列出了每个位置建设中继站的费用以及能够覆盖的社区,表2列出了每个社区的人口数。
1143710811615212554691371423图1 表1 每个位置建设中继站的费用及所能覆盖的社区
位置 费用(百万元) 覆盖社区 1 9 1,2,4 2 6.5 2,3,5 3 20 4,7,8,10 4 14.5 5,6,8,9 5 19 8,9,12 12,15 表2 每个社区的人口数量
社区 1 2 4 3 13 4 6 5 9 6 4 7 8 8 12 9 10 10 11 11 6 12 13 14 9 14 3 15 6 4,15 6 13 7,10,11,7 10.5 12,13,1人口(千人) 2 问题一:在不超过5000万建设费用的情况下,在何处建设中继站,能够覆盖尽可能多的人口;
问题二:考虑到中继站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题,为此对通讯资费进行了调整,规定,仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取,有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取,针对于5000万元的预算,应该如何建设中继站,才能够使得资费的收入达到最大
二. 问题分析
2
众所周知手机是通过在地面上建立了大量的无线中继站来传递信号,达到通话目的。若某手机运营商准备在一个目前尚未覆盖的区域开展业务,则需要考虑中继站的覆盖能力,即某中继站覆盖的那些社区以及社区的人数等问题,在此基础上建立中继站网络,最大程度上服务于小区的居民。根据题目条件,为了更好地分析问题,我们将基站对于小区的覆盖情况用下表来描述。 中继站 社区 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 表3 考虑到有的小区仅仅只有一个中继站覆盖,因此要想实现所有社区的全面覆盖,有些中继站是不能缺少的。例如,1 号、3 号、6 号、11 号、13 号、14 号社区均只可能有一个中继站覆盖,那么为这些社区服务的中继站是必不可少的。因此,中继站1 号、2 号、4 号、6号、7 号必须要设。建设这些中继站的费用9+6.5+14.5+13+10.5=53.5>50;此时,仅仅必须建设的中继站的费用已经不能满足要求。因此,要想在实现不超过5000万建设费用的情况下实现对所有社区的覆盖是不可能的。 针对问题一,我们采用了两种方法:
? 建立0-1 规划模型,通过对题目条件和问题的挖掘,列写出规划模型中的目标函数
和约束条件。运用数学软件lingo求解,最终也得到了合理的中继站建设方案。 ? 我们已经知道了中继站的建立不可能完全覆盖所有的社区,只可能竟可能的建设其
中的几个中继站,如果采用枚举法,我们会发现总共有27种情况。发现数据有点大,即使采用MATLAB进行编程来遍历满二叉树,所需的时间过长,也可能发生误差,再加上在总资金上的约束。这样就会显得又写程序的运行显得多余,因此在此约束条件上我们可以采用分支定界法来删除部分的枝叶,再加上一些其他的约束,比如人数上的约束,又可以删除一些枝叶这样大大的增加了速度。具体的思想还要套用回溯法的思想,这样得到了中继站的建立规划,我们就可以根据相应的已知数据进行求解相关的信息,比如花费的资金,所覆盖的社区与人数。
针对问题二,在满足中继站建设成本不超过5000 万元的情况下,确定一个合理的中继站建设方案,使得运营商的资费收入最高。我们也采用了两种方法:
? 问题关键在于确定每一个社区用那几个社区覆盖,然后计算根据题目中的“仅有一
个中继站信号覆盖的小区通讯资费按正常资费的70%收取,有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取”的原则,可以列写出关于资费收入的函数表达式。运用数学软件lingo最终把满足条件的中继站建设方案对应的资费收入进行比较,最终确定出最理想的中继站建设方案。
? 只要在问题一第二种方法程序的运行结果中得到社区的覆盖信息进行判断在求出总
的资金。既利用相应的有效人数与总费用的投入进行判断标准。
3
三. 模型假设及符号说明
3.1模型假设
(1)若某社区处在某一中继站覆盖范围内,则该社区中的人口全部被该中继站覆盖; (2)各社区的手机使用率相同;
(3)每位手机使用者的通讯资费相同; (4)该区域只存在这一种通信网络;
(5)每个中继站覆盖且仅覆盖表1上所列出的覆盖区域; (6)通讯信号不受地形地貌,气候变化等因素影响; (7)社区人口保持不变; (8)不考虑手机漫游等情况;
(9)每个中继站位置最多只建一个中继站。 3.2符号说明 ki 表述第i个中继站的建设情况(其中i?1,2,?7)。当ki?1时,表示第i个中继站要建设;当ki?0时,表示第i个中继站不建设 bj 表述第j个社区的覆盖情况(其中j?1,2,?15)。当bj?1时,表示第j个社区被覆盖到;当bj?0时,表示第j个社区不被覆盖到 pj ci 表示第j个社区的人口数(其中j?1,2,?15) 表示第i个中继站的建设费用(其中i?1,2,?7) 表示第j个社区的覆盖情况(其中j?1,2,?15)。当rj?0.7时,表示第j个社区只被一个中继站被覆盖到;当rj?1时,表示第j个社区被一个以上中继站被覆盖到;当rj?0时,表示第j个社区没被中继站被覆盖到 rj c 表示获得的单位资费(千元) 四. 模型建立及求解
4.1 问题一
? 0—1 整型规划 4.1.1模型建立
设ki(i?1,2,?7表示7个中继站)表述每一个中继站的建设情况。引入0-1变量,即
1,表示第i个中继站要建设ki???0,表示第i个中继站不建设 ? k在此模型的建立过程中,由于同一个社区可能有多个中继站覆盖,如果覆盖同一社区的中继站都要建设时,那么中继站覆盖的人口就会被重复计算。故我们将目标转移
4
相关推荐: