数学建模结课作业论文题目：移动通讯基站建设问题备注：包括中间的一些表格没有染上颜色的也要写。

2013年5月25日移动通讯基站最优选址模型背景：移动基站的选址工作是基站前期建设至关重要的环节，它不仅关系到通信网络覆盖优化，还直接影响到工程投资效果、建设进度、后期维护、施工难度等方面。

基站选址中，通常情况下讲 “就高不就低”，是说尽量将基站选在地势较高的场地，以减少铁塔设计高度，达到节约工程投资的目的。

具体操作中应结合实际情况，不要走向极端 随着城市乡村经济建设的步伐加快，生活生产规划用地愈加紧缺，基站的可选择区域越来越小。

人们在工程建设中往往把一些原生的、根子上的不足推到工程设计上，设计人员也是无法解决的，采取避开建设不利地段是最根本的选择。

因此，在决策选址用地问题上，必须把基站通信安全放在首位。

在我国移动通信建设正处在新的一轮发展竞争的阶段，“村通工程”、“补点工程”、“季度工程” 时间紧，任务重。

这就要求工程管理、地质勘探、网络设计及土建设计人员，各执其责，密切配合。

综合分析基站建设各种因素，选择安全可靠，经济合理移动站址，为当地社会提供优质安全的通信网络。

摘 要本文综合利用多种模型，在资金和备选地址确定的情况下，对手机中继站的选址问题进行了求解和优化。

我们首先对题中所给的数据进行了整理和分析，引入了回溯模型、0-1规划模型，为以下问题的解决作了准备。

对于问题一，我们运用两种方法，并用不同的软件求解：方法一：我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即max ∑==151j j j b p M ，根据题目要求建立约束条件，并用数学软件LINGO很容易解得题目最优解；方法二：联系问题的性质，我们引入了回溯模型，采用迭代加深搜索的思想，可以在满足题目所给条件下搜索到一条到达解空间的路径。

然后，根据所有的路径对应的中继站的建设情况求解出相应的中继站覆盖的人口，然后经过比较即可求得最终结果。

对于问题二，我们同样运用以上两种方法，只是针对题目要求略微改变目标函数，并用不同的软件求得相同解，最优方案不变，和问题一相同。

关键字：0-1规划 回溯算法 中继站一． 问题重述某手机运营商准备在一个目前尚未覆盖的区域开展业务，计划投资5000万元来建设中继站。

该区域由15个社区组成，有7个位置可以建设中继站，每个中继站只能覆盖有限个社区。

图1是该区域的示意图，每个社区简化为一个多边形，每个可以建设中继站的位置已用黑点标出。

由于地理位置等各种条件的不同，每个位置建设中继站的费用也不同，且覆盖范围也不同。

表1中列出了每个位置建设中继站的费用以及能够覆盖的社区，表2列出了每个社区的人口数。

表1 每个位置建设中继站的费用及所能覆盖的社区表2 每个社区的人口数量问题一：在不超过5000万建设费用的情况下，在何处建设中继站，能够覆盖尽可能多的人口；问题二：考虑到中继站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取，有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取，针对于5000万元的预算，应该如何建设中继站，才能够使得资费的收入达到最大二．问题分析众所周知手机是通过在地面上建立了大量的无线中继站来传递信号,达到通话目的。

若某手机运营商准备在一个目前尚未覆盖的区域开展业务，则需要考虑中继站的覆盖能力，即某中继站覆盖的那些社区以及社区的人数等问题，在此基础上建立中继站网络，最大程度上服务于小区的居民。

小区的覆盖情况用下表来描述。

考虑到有的小区仅仅只有一个中继站覆盖，因此要想实现所有社区的全面覆盖，有些中继站是不能缺少的。

例如，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 规划模型，通过对题目条件和问题的挖掘，列写出规划模型中的目标函数和约束条件。

我们已经知道了中继站的建立不可能完全覆盖所有的社区，只可能竟可能的建设其中的几个中继站，在此约束条件上我们可以采用分支定界法来删除部分的枝叶，再加上一些其他的约束，比如人数上的约束，又可以删除一些枝叶这样大大的增加了速度。

具体的思想还要套用回溯法的思想，这样得到了中继站的建立规划，我们就可以根据相应的已知数据进行求解相关的信息，比如花费的资金，所覆盖的社区与人数。

针对问题二，在满足中继站建设成本不超过5000 万元的情况下，确定一个合理的中继站建设方案，使得运营商的资费收入最高。

我们也采用了两种方法：问题关键在于确定每一个社区用那几个社区覆盖，然后计算根据题目中的“仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取，有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取”的原则，可以列写出关于资费收入的函数表达式。

运用数学软件lingo最终把满足条件的中继站建设方案对应的资费收入进行比较，最终确定出最理想的中继站建设方案。

只要在问题一第二种方法程序的运行结果中得到社区的覆盖信息进行判断在求出总的资金。

既利用相应的有效人数与总费用的投入进行判断标准。

三．模型假设及符号说明3.1模型假设（1）若某社区处在某一中继站覆盖范围内,则该社区中的人口全部被该中继站覆盖；（2）各社区的手机使用率相同；（3）每位手机使用者的通讯资费相同；（4）该区域只存在这一种通信网络；（5）每个中继站覆盖且仅覆盖表1上所列出的覆盖区域；（6）通讯信号不受地形地貌,气候变化等因素影响；（7）社区人口保持不变；（8）不考虑手机漫游等情况；（9）每个中继站位置最多只建一个中继站。

四． 模型建立及求解4.1 问题一0—1 整型规划 4.1.1模型建立设i k (7,2,1 =i 表示7个中继站)表述每一个中继站的建设情况。

引入0-1变量，即⎩⎨⎧=个中继站不建设表示第个中继站要建设表示第i i k i ,0,1 k 在此模型的建立过程中，由于同一个社区可能有多个中继站覆盖，如果覆盖同一社区的中继站都要建设时，那么中继站覆盖的人口就会被重复计算。

故我们将目标转移到社区上，每个社区的被覆盖情况只有两种，要么被覆盖要么不被覆盖，我们也引入0-1变量，即⎩⎨⎧=个社区不被覆盖表示第个社区被覆盖表示第j j b j ,0,1 这样就可避免了对同一社区人口的重复计算。

本问题的目标是使得中继站覆盖的人口尽量多。

根据表1，2，3我们可以得到目标函数：∑==151j j j b p M题目要求建设中继站的费用不超过5000 万元，故约束条件：5071≤∑=i i i k c4.1.2 模型求解：可知模型为：max ∑==151j j j b p M⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧===+========++======+===+===++===+======+===+======+====≤∑=0;00;100;100;100;100;100;100;100;100;100;100;100;100;100;10;50151576141314137121276511116101063995488543776366455424431332222111171b b k k b b b b k b b k k k b b k bb k k b b k k b b k k k b b k k b b k b b k k b b k k b b k b b k k b b k kk c i i i i 否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当；否则时，当或回溯算法 4.1.3模型建立回溯模型可以系统的搜索一个问题的所有解或任一解，按深度优先策略，从根节点如图所示就是I 层出发搜索该模型可以搜索至解空间树的任一点时，先判断该首先我们节点是否包含问题的解。

如果肯定不包含，则跳过对以该节点为根的字数的搜索，逐层向其回溯。

否则进入该子树，继续按深度优先策略搜索。

回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索便才结束。

在回溯模型中，我们采用了迭代加深搜索的思想。

可以在满足题目所给条件下搜索到一条到达解空间的路径。

然后，根据所有的路径对应的中继站的建设情况求解出相应的中继站覆盖的人口，然后经过比较即可求得最终结果。

如图1）当在I层的时候往左端行驶检验I层点是否满足条件若满足则同样对II层进行同样的检验，若不满足则退回回I层往右端行驶，进入第II层，接着就这样逐步的搜索下去，知道最后的一层。

在这其中满足的条件是在搜索过程中，需要考虑终止搜索的条件：中继站的建设费用不能超过5000万。

一旦在搜索路径上，发现中继站的建设费用超过5000万，就立即停止对这一搜索路径的进一步搜索。

2）满足了这些条件后得到的数据再进行判断是否满足人数上的约束，若满足则这个就是符合条件的。

4.1.4 模型求解：1)数据准备：定义数组存储每个社区的人数：p=[2,4,13,6,9,4,8,12,10,11,6,14,9,3,6]；建设7个中继站所需要的价钱：c =[9 6.5 20 14.5 19 13 10.5];生成中继站的覆盖矩阵：aa=zeros(7,15);a(1,[1,2,4])=1;a(2,[2,3,5])=1;a(3,[4,7,8,10])=1;a(4,[5,6,8,9])=1;a(5,[8,9,12])=1;a(6,[7,10,11,12,15])=1;a(7,[12,13,14,15])=1;即如下面表示：a =[1 1 0 1 0 0 0 0 0 0 0 0 0 0 0；0 1 1 0 1 0 0 0 0 0 0 0 0 0 0；0 0 0 1 0 0 1 1 0 1 0 0 0 0 0；0 0 0 0 1 1 0 1 1 0 0 0 0 0 0；0 0 0 0 0 0 0 1 1 0 0 1 0 0 0；0 0 0 0 0 0 1 0 0 1 1 1 0 0 1；0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 ]花费的资金为：l*c'数组中的0-1表示的是中继站对社区的覆盖与否。

2)程序设计：定义location1函数来计算相关的数据，并且函数结果用数组来进行存储，包含各种情况的总资金，总覆盖人数。