基于0-1规划的移动通讯基站最优选址模型

基于0-1规划的移动通讯基站最优选址模型 摘 要 本文以移动通讯基站的投资成本与覆盖特性为背景，综合利用多种模型在资金和被选地址确定的情况下，对基站的选址问题进行了求解和优化。 针对问题一，我们首先对题中表1和表2所给的数据进行整理和 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，引入了0-1规划模型和排除法进行求解，在0-1规划模型中，运用布尔代数中的加法原则来避免同一社区的人口被重复计算，用lingo软件求得当在2，4，6，7号位置建设基站时，覆盖人口最多。在这种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 下，建设基站总费用为45(百万元)，覆盖了2，3，5，6，7，8，9，10，11，12，13，14，15社区，总人口为109.5千人。在排除法解决 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 中，我们根据题目中的 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 资产不超过5000万元的条件下覆盖人口尽可能多的要求，通过程序输出建设三个和四个中继站的所有可能的情况，经过比较排除后，对剩下的20种可供选择的方案，依题意求出对应的建设费用M、覆盖社区、覆盖人口W。经过比较，得出投资4500万元，在2，4，6，7这四个位置建站可以覆盖除1和4以外的所有社区，总覆盖109.5千人的最优方案。这两种求解方法分别从不同的角度解决问题，得出了相同的建设方案。两种方法之间相互检验，论证了它们的合理性，这也是我们模型的一大特色。 在问题二中，我们仍然引用0-1规划模型，只是对其稍加改进。这里用布尔代数中的加法原则来避免同一社区的总通讯资费被重复计算。用lingo软件求得在2，4，6，7号位置建设基站时，资费的收入达到最大，为83.74 百万元（ 为手机使用率）。同时绘制了基站建设方案示意图（如图2所示）。然后我们运用枚举法把各种方案覆盖的社区及总人数和总资费收入一一列出（如表7所示），经过计算和比较最终得出了和0-1规划中同样的结果。从而证明了0-1规划模型所求结果的正确性。 最后，我们对模型的优缺点进行了分析，并对模型的改进和推广方向作了进一步探讨。 本文充分利用了lingo语言和C语言的特性，进行综合编程，对大量数据做了相应处理，使得算法易于实现，计算量减少，从而能够更加科学的得出最优方案。 关键词：0-1规划 LINGO 布尔加法 一、问题的重述 随着移动通信技术的发展，普通民众对于通讯需求的逐步提高，使得移动通信不断拓展它的业务，而移动通信工具的信号发出是通过基站接力传输的。某手机运营商计划投资5000万在一个尚未覆盖的区域开展业务，建设基站。该区域有15个社区，有7个位置可以建设基站每个基站只能覆盖有限个社区。由于地理位置等各种条件的不同，每个位置建设的基站的费用几覆盖范围也不相同。下面给出了社区分布及中继站建设点，表1给出了每个位置建设基站的费用以及能够覆盖的社区，表2列出了每个社区的人口数。 SHAPE \* MERGEFORMAT 表1 每个位置建设基站的费用及所能覆盖的社区 位置 1 2 3 4 5 6 7 费用（百万元） 9.5 7 19 14 17.5 13 11 覆盖社区 1,2,4 2,3,5 4,7,8,10 5,6,8,9 8,9,12 7,10,11,12,15 12,13, 14,15 表2 每个社区的人口数量 社区 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 人口（千人） 2 4 13 6 9 4 7.5 12.5 10 11 6 14 9 3.5 6 问题一：在建设费用不超过5000万的前提条件下，在7个位置中何处建设基站，能够使覆盖的人口尽可能的多； 问题二：考虑到基站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个基站信号覆盖的小区人均通讯资费按正常资费的68%收取，而有两个或两个以上基站信号覆盖的小区人均的通讯资费按正常收取，在建设费用不超过5000万的情况下，应该在7个位置中如何建设基站，才能够使得手机运营商得到最大的资费收入。 二、问题的分析 对于问题一，我们要求的的是在建设费用不超过5000万的前提条件下，在7个位置中何处建设基站，能够使覆盖的人口尽可能的多。，于是我们引进了0-1整数规划模型和排除法两个模型。在0-1整数规划模型中，以覆盖的人口尽可能的多为目标函数，以建设费用不超过5000万为约束条件建立模型，并用lingo软件求解，得到满足题目条件的基站。在排除法中，我们先对所给数据进行分析，用C++编程输出70种满足题目约束条件的方案。通过排除、比较最终可以得到了符合条件得建站位置。 对于问题二，同样是一个规划方案，只不过目标函数为得到最大的资费收入。此时可以对问题一中lingo程序稍加修改即可。为了验证结果的正确性，可以使用枚举法列出满足条件的基站建设方案覆盖的社区和总资费收入。最后把满足条件的基站建设方案对应的资费收入进行比较，从而确定出最理想的建站方案。 三、模型的假设与符号说明 3.1. 模型的假设 1、各社区人口总量不变； 2、假设各社区内移动通信客户所占该社区总人口比例即手机使用率 相同； 3、若某社区处在某一基站覆盖范围，则该社区中的手机用户能全部被该机站覆盖； 4、通讯信号不受地形地貌、气候变化等因素影响； 5、每个中继站位置不会重复建设基站； 6、忽略由于基站之间的相互干扰所造成的对服务质量的影响； 7、假设正常资费是稳定的，仅与小区覆盖次数有关，不随时间与使用人口的数量而改变； 8、假设每一个小区内平均每一千人的政策资费在有两个或两个以上中继站信号覆盖情况下相等，且设时间为常数，每千人的通讯资费是1，在有一个中继站信号覆盖的社区通讯费按每一千人0.68收取。 3.2. 符号说明 ：每一个基站的建设情况（ 表示第i个基站需要建设， 表示第i个基站不需要建设）； ：手机使用率（ ） M：基站的建设总成本 W：在某种建设方案下，基站覆盖的等效人口 S：某种建设方案下，资费收入 四、模型的准备 根据题目中表1和表2的信息，为了更好地分析问题，我们将基站对于小区的覆盖情况用表3描述： 表3 基站对于小区的覆盖情况 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 √ √ √ 2 √ √ √ 3 √ √ √ √ 4 √ √ √ √ 5 √ √ √ 6 √ √ √ √ √ 7 √ √ √ √ 说明：表中的“√”表示基站可覆盖相对应的社区， 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 空表示基站和社区没有对应关系。 然后根据上面表3，我们可以得到所有社区对应的基站的位置情况，如表4所示： 表4 所有社区对应的基站的位置情况 社区 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 对应的基站个数 1 2 1 2 2 1 2 3 2 2 1 3 1 1 2 对应的基站位置 1 1，2 2 1，3 2，4 4 3，6 3，4，5 4，5 3，6 6 5，6，7 7 7 6，7 五、模型的建立和求解 5.1 问题一模型 5.1.1 基于0-1规划的求解模型 对于基站，只有建设和不建设两种情况，因此，可用0-1规划的思想建立模型。设 为每一个基站的建设情况，则有： 其中 表示第i个基站需要建设， 表示第i个基站不需要建设。 由于同一社区，有可能有多个基站覆盖，如果覆盖同一社区的基站都需要建设时，那么有的社区的人口就会被重复计算。所以我们可以用布尔代数的思想来避免这种情况。 在布尔代数中， （ 是布尔代数中的加法）。其中 可以表示为当同一个社区被两个或两个以上的基站覆盖时，该社区的权值为1，这样就避免了社区的人口会被重复计算的情况。 本问题要求在建设费用不超过5000万的前提条件下基站覆盖的人口尽可能的多，根据题目所给的表格1和表格2可将目标函数表述如下： ········（1） 约束条件为：建设基站的费用不超过5000万元的预算，式子如下： ········（2） 考虑到基站需要建设与否，我们有 ················（3） 我们用lingo软件对其求解（相关程序及运行结果见附录一），最终求解得到最佳的建设方案如表5所示： 表5 0-1规划模型求解得到的基站建设方案 基站号 建设情况 1 不建设 2 建设 3 不建设 4 建设 5 不建设 6 建设 7 建设 由上表可知，当在2，4，6，7号位置建设基站时，覆盖人口最多。在这种方案下，建设基站总费用为7+14+13+11=45(百万元)，覆盖2，3，5，6，7，8，9，10，11，12，13，14，15社区，总人口为109.5千人。 5.1.2 基于排除法的求解模型 由问题一的分析可知，可以建设三个或四个基站。我们用C++程序（相关程序及运行结果见附录二）可以输出建设三个或四个基站的所有70种可能的方案。若方案在不超过5000万建设费用的情况下还可以增加建设基站，则可以把此类方案排除在外，按此方法可排除26种。如果某种方案的总费用超过5000万我们也可以把其排除在外，此时排除24种方案。最后还剩下20种。 根据第一次选择可以得到以下20种方案，按照题中所给的表1和表2可得各种方案覆盖的社区及总人数如表6所示： 表6 各种方案覆盖的社区及总人数 建站位置 建设费用M（百万元） 覆盖社区 覆盖人口W 2，3，5 43.5 2，3，4，5，7,8,9,10,12 86.5 1，3，5 46 1,2,4,7,8,9,10,12 66.5 4，5，7 42.5 5,6,8,9,12,13,14,15 68 3，4，7 44 4,5,6,7,8,9,10,12,13,14,15 92.5 3，5，7 47.5 4,7,8,9,10,12,13,14,15 79.5 3，5，6 49.5 5,6,7,8,9,10,11,12,15 73 3，4，6 46 4,5,6,7,8,9,10,11,12,15 75.5 1，2，3，4 49.5 1,2,3,4,5,6,7,8,9,10 79 1，2，3，6 48.5 1,2,3,4,5,7,8,10,12,13,14,15 91 1，2，3，7 46.5 1,2,3,4,5,6,8,9,12,13,14,15 97.5 2，5，6，7 48.5 2,3,5,7,8,9,10,11,12,13,14,15 105.5 2，3，6，7 50 2,3,4,5,7,8,10,11,12,13,14,15 101.5 2，4，6，7 45 2,3,5,6,7,8,9,10,11,12,13,14,15 109.5 1，2，4，5 48 1,2,3,4,5,6,8,9,12 80.5 1，2，5，6 47 1,2,3,4,5,7,8,9,10,11,12,15 104.5 1，2，6，7 40.5 1,2,3,4,5,7,10,11,12,13,14,15 91 1，2，4，6 43.5 1,2,3,4,5,6,7,8,9,10,11,12,15 94.5 1，2，4，7 41.4 1,2,3,4,5,6,8,9,12,13,14,15 93 1，2，5，7 45 1,2,3,4,5,8,9,12,13,14,15 89 1，4，6，7 47.5 1,2,4,5,6,7,8,9,10,11,12,13,14,15 104.5 从上表可以看出在2，4，6，7号位置建设基站时，覆盖人口最多，为109.5千人。同时建设基站的费用为4500万元，满足题目中建设费用不超过5000万的要求。 5.2 问题二模型 5.2.1 基于0-1规划的求解模型 由题意可知，仅有一个基站信号覆盖的小区人均通讯资费按正常资费的68%收取，而有两个或两个以上基站信号覆盖的小区人均的通讯资费按正常收取，在附录一中的lingo程序中我们又一次用到布尔代数，对没有被覆盖的社区，我们不对其收费；对被覆盖一次的的社区，考虑到基站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，按正常资费的68%收取。例如：程序中出现c2=@if(x1+x2#eq#1,0.68,1)就是对布尔代数的具体体现。具体实现的lingo程序及运行结果见附录三。为了简便起见，在程序中我们把手机使用率 简化为1。 通过分析lingo程序的运行结果，很显然我们可以得出在2，4，6，7号位置建设基站时，资费的收入达到最大为83.74* 百万元（ 为手机使用率）。 同时，我们对所求的结果进行分析还可得到基站建设方案示意图如下： SHAPE \* MERGEFORMAT 被一次覆盖 被多次覆盖 没有被覆盖 被选中的基站 没有被选中的基站 图2 基站建设方案示意图 5.2.2枚举法求解 由题意可知，仅有一个基站信号覆盖的小区人均通讯资费按正常资费的68%收取，而有两个或两个以上基站信号覆盖的小区人均的通讯资费按正常收取。由表6各种方案覆盖的社区及总人数和总资费收入，如下表所示： 表7 通讯资费表 建站位置 信号 社区分布 资费收入(百万元） 总资费S（百万元） 2，3，5 单信号 2,3,4,5,7,9,10,12 74* *0.68 62.82* 多信号 8 12.5* 1，3，5 单信号 1,2,7,9,10,12 48* *0.68 51.14* 多信号 4,8 18.5* 4，5，7 单信号 5,6,13,14,15 31.5* *0.68 62.68* 多信号 8,9,12 36.5* 3，4，7 单信号 4,5,6,7,9,10,12,13,14,15 80* *0.68 66.9* 多信号 8 12.5* 3，5，7 单信号 4,7,9,10,13,14,15 73* *0.68 74.14* 多信号 8,12 26.5* 3，5，6 单信号 4,9,11,15 28* *0.68 64.04* 多信号 7,8,10,12 45* 3，4，6 单信号 4,5,6,9,11,12,15 44.5* *0.68 61.26* 多信号 7,8,10 31* 1，2，3，4 单信号 1,3,6,7,9,10 47.5* *0.68 63.8* 多信号 2,4,5,8 31.5* 1，2，3，6 单信号 1,3,5,8,11,12,15 62.5* *0.68 71* 多信号 2,4,7,10 28.5* 1，2，3，7 单信号 1,3,5,7,8,10,12,13,14,15 87.5* *0.68 69.5* 多信号 2,4 10* 2，5，6，7 单信号 2,3,5,7,8,9,10,11,13,14 85.5* *0.68 78.14* 多信号 12,15 20* 2，3，6，7 单信号 2,3,4,5,8,11,13,14 63* *0.68 81.34* 多信号 7,10,12,15 38.5* 2，4，6，7 单信号 2,3,6,7,8,9,10,11,13,14 80.5* *0.68 83.74* 多信号 5,12,15 29* 1，2，4，5 单信号 1,2,4,5,6,12 58* *0.68 61.94* 多信号 8,9 22.5* 1，2，5，6 单信号 1,3,4,5,7,8,9,10,11,15 96.5* *0.68 76.82* 多信号 2,12 18* 1，2，6，7 单信号 1,3,4,5,7,10,11,13,14 67* *0.68 69.56* 多信号 2,12,15 24* 1，2，4，6 单信号 1,3,4,6,7,8,9,10,11,12,15 81.5* *0.68 68.42* 多信号 2,5 13* 1，2，4，7 单信号 1,3,4,6,8,9,12,13,14,15 80* *0.68 67.4* 多信号 2,5 13* 1，2，5，7 单信号 1,3,4,5,8,9,13,14,15 71* *0.68 66.28* 多信号 2,12 18* 1，4，6，7 单信号 1,2,4,5,6,7,8,9,10,11,13,14 84.5* *0.68 70.46* 多信号 12,15 20* 从表中可以看出，在2，4，6，7号位置建设基站时，资费的收入达到最大为83.74* 百万元（ 为手机使用率）。 六、模型结果的分析与检验 问题一中要求在基站建设成本不超过5000万元的情况下，确定一个合理的基站建设方案，使得覆盖的人口尽可能的多。针对该问题，我们建立了两个模型，分别从不同角度求解出了基站的最佳建设方案。其中在0-1规划模型中，运用lingo软件对规划模型求解得出在2，4，6，7号位置建设基站时，覆盖人口最多，为109.5千人，同时建设基站的费用为4500万元，满足题目中建设费用不超过5000万的要求的结论。而在排除法中，通过对题中所给的表1和表2的分析，对建设基站所有可能的方案进行排除，最后剩下20种可供选择的方案，依次求出它们的建设费用、覆盖社区、覆盖人口如表6所示。经过比较我们认为投资4500万元，在2，4，6，7这四个位置建基站可以覆盖除1和4外的全部社区，总覆盖人数达109.5千人。 由上面的两个模型的结果来看，我们得到两种相同的基站建设方案，这说明了我们求解模型的方法是可靠的，结果是可信的。保证了求解结果的准确性。 对于问题二，要求的是在满足基站建设成本不超过5000万元预算条件下，怎样建设基站，使得运营商的资费收入最高。根据题目中“仅有一个基站信号覆盖的小区人均通讯资费按正常资费的68%收取，而有两个或两个以上基站信号覆盖的小区人均的通讯资费按正常收取”的要求，我们运用了0-1规划和枚举法两种方法，0-1规划中对被重复覆盖的社区求布尔和，用lingo数学软件得出最大资费收益为S=83.74 （百万元）。枚举法中我们写出关于资费收入的函数表达式S=（单信号地区的人数*68%+多信号地区的人数*1）* 算出20种方案的每种方案的资费收入，然后比较得到最大收入的方案为在2，4，6，7号位置建设基站时，资费的收入达到最大，为83.74 （百万元）（ 为手机使用率）。同样，两种解决方法所得结果一致，这说明了这几种模型的合理性。 七、模型的改进与推广方向 7.1 模型的改进 在模型的建立中，不仅要从收益最大一方面来考虑，因为移动通讯行业是一项长期的行业，暂时的优质服务、优惠活动，可以无形的为运营商起到广告宣传作用，这样可以给移动运营商带来潜在的收益。 问题二中可以用迭代搜索法试图尝试所有可能的深度限制，一旦在搜索路径上出现不满足限制约束条件的情况，就终止此路径的进一步搜索，去寻求另外的搜索路径。中止搜索的条件为：搜索路径未达到最终解空间时，建设基站费用已超过5000万元，或者搜索路径达到了解空间。这样就可以根据搜索路径达到了解空间的基站的建设情况，确定每个社区有几个基站覆盖，以便确定应该对社区用户是按照正常资费收取还是按正常资费的68%收取。 另外，还应考虑投资和收入的关系问题，应投入尽量少的钱获得尽量多的收益。因此，我们再考虑资费收入的同时，把社区内移动用户数与建设基站的投资的比值作为研究的最终目标量。 7.2 模型的推广 本文中，0-1规划模型能够很好的解决本文中的移动通讯基站的选址问题。我们也可以将其推广到大面积区域的规划，比如从一个区域推广到多个区域或是一个市、一个省的情形。另外，这一解决问题的模型也可以推广到其他服务性行业的选址中的方案的确定。比如说，物流中心的选址就可以用0-1规划模型来解决。只是此时需要考虑的因素，需要列出的约束条件，和目标函数都有所不同。 八、模型的优缺点 8.1 模型的优点 1、在0-1规划模型中，我们采用了布尔代数中的加法规则，巧妙的解决了问题中关于人口可能会被重复计算的问题。 2、文中对于同一问题分别采用了两种不同方案，从不同的角度分析问题，最终得到了相同的建设方案。而且两种方案也起到了相互验证的效果。 3、用排除法解决问题的过程中，很好的利用了情况有限这一条件，使得整个模型确立以后，我们可以在具体实行中不断改进，根据题中所给的条件进行排除。 8.2 模型的缺点 1、0-1规划模型的约束条件有点简单。 2、采用排除法中，计算过于繁琐，计算量很大，可能还有其它的方法一次能排除几个甚至几十个方案，使得在计算上花费不少时间。 参考文献 [1] 姜启源 数学模型[M].北京：高等教育出版社，2003. [2] 李志林 欧宜贵 数学建模及典型案例分析 北京：化学工业出版社，2006 [3] 郑秋生 C/C++程序设计教程——面向过程程序设计 北京：机械工业出版社，2002 [4] 刘承平 数学建模方法 北京：高等教育出版社，2002 附录 【附录一】 问题一中0-1规划lingo程序实现： model: max=2*x1+4*(b1)+13*x2+6*(b2)+9*(b3)+4*x4+7.5*(b4)+12.5*(b5)+10*(b6)+11*(b7)+6*x6+14*(b8)+9*x7+3.5*x7+6*(b9);!12*x1+26*x2+37*x3+35.5*x4+36.5*x5+44.5*x6+32.5*x7; a-(9.6*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)=0; a<=50; b1=@if(x1+x2#eq#0,0,1); b2=@if(x1+x3#eq#0,0,1); b3=@if(x2+x4#eq#0,0,1); b4=@if(x3+x6#eq#0,0,1); b5=@if(x3+x4+x5#eq#0,0,1); b6=@if(x4+x5#eq#0,0,1); b7=@if(x3+x6#eq#0,0,1); b8=@if(x5+x6+x7#eq#0,0,1); b9=@if(x6+x7#eq#0,0,1); @BIN(x1); @BIN(x2); @BIN(x3); @BIN(x4); @BIN(x5); @BIN(x6); @BIN(x7); end 运行结果为： Local optimal solution found. Objective value: 109.5000 Extended solver steps: 3 Total solver iterations: 186 Variable Value Reduced Cost X1 0.000000 -2.000000 B1 1.000000 0.000000 X2 1.000000 -13.00000 B2 0.000000 0.000000 B3 1.000000 0.000000 X4 1.000000 -4.000000 B4 1.000000 0.000000 B5 1.000000 0.000000 B6 1.000000 0.000000 B7 1.000000 0.000000 X6 1.000000 -6.000000 B8 1.000000 0.000000 X7 1.000000 -12.50000 B9 1.000000 0.000000 A 45.00000 0.000000 X3 0.000000 0.000000 X5 0.000000 0.000000 Row Slack or Surplus Dual Price 1 109.5000 1.000000 2 0.000000 0.000000 3 5.000000 0.000000 4 0.000000 4.000000 5 0.000000 6.000000 6 0.000000 9.000000 7 0.000000 7.500000 8 0.000000 12.50000 9 0.000000 10.00000 10 0.000000 11.00000 11 0.000000 14.00000 12 0.000000 6.000000 【附录二】 问题一中排除法c++程序实现： #include #include using namespace std; /*int pop[16]={0,2,4,13,6,9,4,8,12,10,11,6,14,9,3,6};//社区人数 double val[7]={9,6.5,20,14,5,19,13,10.5};//(每个基站费用) int com[7][6]={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};//1~7号基站可以覆盖的社区数*/ 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';i<'f';i++) for(j=i+1;j<'g';j++) for(k=j+1;k<='g';k++) { count++; cout<