手机中继站选址最优方案.doc

手机中继站选址最优方案
http://wenku.baidu.com/view/ff575f2b3169a4517723a30c.html
摘要
本文综合利用多种模型，在资金和备选地址确定的情况下，对手机中继站的选址问题进行了求解和优化。我们首先对题中所给的数据进行了整理和分析，引入了回溯模型、0-1规划模型，为以下问题的解决作了准备。
对于问题一，我们运用两种方法，并用不同的软件求解：
方法一：我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即，根据题目要求建立约束条件，并用数学软件LINGO很容易解得题目最优解；
方法二：联系问题的性质，我们引入了回溯模型，采用迭代加深搜索的思想，可以在满足题目所给条件下搜索到一条到达解空间的路径。然后，根据所有的路径对应的中继站的建设情况求解出相应的中继站覆盖的人口，然后经过比较即可求得最终结果，我们运用软件MATLAB进行编程求解。
对于问题二，我们同样运用以上两种方法，只是针对题目要求略微改变目标函数，并用不同的软件求得相同解，最优方案不变，和问题一相同。
求得的结果如下表：
研究问题建中继站位置所需费用百万最优值问题一2，4，6，744.5覆盖中人口数109千人问题二2，4，6，744.5获得资费85c千元本文运用的两种方法都有它们各自的优点和不足，对于第一种方法，我们采用枚举法，我们会发现总共有种情况，但因为数据比较少，运用LINGO软件求解，程序简单；对于第二种方法，我们采用回溯算法，需要遍历的分支相对减少，但是程序相对较复杂，比较适合数据较多的模型。
本文还对“仅有一个中继站信号覆盖的小区通讯资费按正常资费的10%~90%区间内的收取”做了讨论，得出了最优方案随百分比的改变的变化曲线图。

关键字：0-1规划回溯算法中继站LINGO软件MATLAB软件
问题重述
某手机运营商准备在一个目前尚未覆盖的区域开展业务，计划投资5000万元来建设中继站。该区域由15个社区组成，有7个位置可以建设中继站，每个中继站只能覆盖有限个社区。图1是该区域的示意图，每个社区简化为一个多边形，每个可以建设中继站的位置已用黑点标出。由于地理位置等各种条件的不同，每个位置建设中继站的费用也不同，且覆盖范围也不同。表1中列出了每个位置建设中继站的费用以及能够覆盖的社区，表2列出了每个社区的人口数。
图1

表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万元的预算，应该如何建设中继站，才能够使得资费的收入达到最大
问题分析
众所周知手机是通过在地面上建立了大量的无线中继站来传递信号,达到通话目的。若某手机运营商准备在一个目前尚未覆盖的区域开展业务，则需要考虑中继站的覆盖能力，即某中继站覆盖的那些社区以及社区的人数等问题，在此基础上建立中继站网络，最大程度上服务于小区的居民。根据题目条件，为了更好地分析问题，我们将基站对于小区的覆盖情况用下表来描述。

中继站
社区1234567891011121314151234567表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求解，最终也得到了合理的中继站建设方案。
我们已经知道了中继站的建立不可能完全覆盖所有的社区，只可能竟可能的建设其中的几个中继站，如果采用枚举法，我们会发现总共有种情况。发现数据有点大，即使采用MATLAB进行编程来遍历满二叉树，所