数学建模结课作业
论文题目：移动通讯基站建设问题
班级：服工102班 姓名：李明月
学号：201000714206
2012年 4月18日
移动通讯基站最优选址模型
背景：移动通讯设立基站服务广大手机用户，扩展自己的业务，增大自己的利润空间应该是无可厚非的。但他们在不同业主协商的情况下，将基站设立在居民的住宅楼上。毕竟居民楼应该属于广大业主，而移动基站所发出的辐射对小的居民身体健康是非常有害的，他们私自设立基站是有违《物权法》的。
据资料记载基站发出的辐射能够诱发癌症并加速人体的癌细胞增殖、造成儿童白血病；可导致孕妇发生自然流产和胎儿畸形、儿童智力残缺；影响人们的心血管系统，表现为心悸，失眠，部分女性经期紊乱，心动过缓，心搏血量减少，窦性心率不齐，白细胞减少，免疫功能下降等。如果装有心脏起搏器的病人处于高电磁辐射的环境中，会影响心脏起搏器的正常使用；对人们的视觉系统有不良影响引起视力下降，白内障等；导致植物神经和中枢神经系统失调、虚弱综合症和其他慢性辐射效应。主要反映是：头痛、头晕、疲劳、无力、过敏、衰弱、失眠、忧郁、神经紊乱及性功能疾病、胸痛及难以说清的不舒服感，在身体检查方面，发现手臂伸长时手指发颤等症。
所以规划移动通讯基站是个重要的问题。
内 容 摘 要
本文以移动通讯基站的投资成本与覆盖特性为背景，综合利用多种模型在资金和被选地址确定的情况下，对基站的选址问题进行了求解和优化。
针对问题一，我们首先对题中表1和表2所给的数据进行整理和分析，引入了0-1规划模型和排除法进行求解，在0-1规划模型中，运用布尔代数中的加法原则来避免同一社区的人口被重复计算，用lingo软件求得当在2，4，6，7号位置建设基站时，覆盖人口最多。在这种方案下，建设基站总费用为4500万元，覆盖了2，3，5，6，7，8，9，10，11，12，13，14，15社区，总人口为109.5千人。在排除法解决方法中，我们根据题目中的计划资产不超过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列出了每个社区的人口数。
表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 |
问题二：考虑到基站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个基站信号覆盖的小区人均通讯资费按正常资费的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 | 建设 |
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 | |
| 1，4，6，7 | 47.5 | 1,2,4,5,6,7,8,9,10,11,12,13,14,15 | 104.5 |
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百万元（为手机使用率）。
同时，我们对所求的结果进行分析还可得到基站建设方案示意图如下：
被一次覆盖 被多次覆盖 没有被覆盖
被选中的基站 没有被选中的基站
图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 | .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* |
六、模型结果的分析与检验
问题一中要求在基站建设成本不超过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< count=0; for(i='a';i<'e';i++) for(j=i+1;j<'f';j++) for(k=j+1;k<'g';k++) for(l=k+1;l<='g';l++) { count++; cout< return 0; } 运行结果为： 第 1种方案为2,1,7三个基站，总费用为M=27.5百万元 第 2种方案为2,1,6三个基站，总费用为M=29.5百万元 第 3种方案为2,1,4三个基站，总费用为M=30.5百万元 第 4种方案为2,1,5三个基站，总费用为M=34百万元 第 5种方案为2,1,3三个基站，总费用为M=35.5百万元 第 6种方案为2,7,6三个基站，总费用为M=31百万元 第 7种方案为2,7,4三个基站，总费用为M=32百万元 第 8种方案为2,7,5三个基站，总费用为M=35.5百万元 第 9种方案为2,7,3三个基站，总费用为M=37百万元 第 10种方案为2,6,4三个基站，总费用为M=34百万元 第 11种方案为2,6,5三个基站，总费用为M=37.5百万元 第 12种方案为2,6,3三个基站，总费用为M=39百万元 第 13种方案为2,4,5三个基站，总费用为M=38.5百万元 第 14种方案为2,4,3三个基站，总费用为M=40百万元 第 15种方案为2,5,3三个基站，总费用为M=43.5百万元 第 16种方案为1,7,6三个基站，总费用为M=33.5百万元 第 17种方案为1,7,4三个基站，总费用为M=34.5百万元 第 18种方案为1,7,5三个基站，总费用为M=38百万元 第 19种方案为1,7,3三个基站，总费用为M=39.5百万元 第 20种方案为1,6,4三个基站，总费用为M=36.5百万元 第 21种方案为1,6,5三个基站，总费用为M=40百万元 第 22种方案为1,6,3三个基站，总费用为M=41.5百万元 第 23种方案为1,4,5三个基站，总费用为M=41百万元 第 24种方案为1,4,3三个基站，总费用为M=42.5百万元 第 25种方案为1,5,3三个基站，总费用为M=46百万元 第 26种方案为7,6,4三个基站，总费用为M=38百万元 第 27种方案为7,6,5三个基站，总费用为M=41.5百万元 第 28种方案为7,6,3三个基站，总费用为M=43百万元 第 29种方案为7,4,5三个基站，总费用为M=42.5百万元 第 30种方案为7,4,3三个基站，总费用为M=44百万元 第 31种方案为7,5,3三个基站，总费用为M=47.5百万元 第 32种方案为6,4,5三个基站，总费用为M=44.5百万元 第 33种方案为6,4,3三个基站，总费用为M=46百万元 第 34种方案为6,5,3三个基站，总费用为M=49.5百万元 第 35种方案为4,5,3三个基站，总费用为M=50.5百万元 第 36 种方案为2,1,7,6四个基站，总费用为M=40.5百万元 第 37 种方案为2,1,7,4四个基站，总费用为M=41.5百万元 第 38 种方案为2,1,7,5四个基站，总费用为M=45百万元 第 39 种方案为2,1,7,3四个基站，总费用为M=46.5百万元 第 40 种方案为2,1,6,4四个基站，总费用为M=43.5百万元 第 41 种方案为2,1,6,5四个基站，总费用为M=47百万元 第 42 种方案为2,1,6,3四个基站，总费用为M=48.5百万元 第 43 种方案为2,1,4,5四个基站，总费用为M=48百万元 第 44 种方案为2,1,4,3四个基站，总费用为M=49.5百万元 第 45 种方案为2,1,5,3四个基站，总费用为M=53百万元 第 46 种方案为2,7,6,4四个基站，总费用为M=45百万元 第 47 种方案为2,7,6,5四个基站，总费用为M=48.5百万元 第 48 种方案为2,7,6,3四个基站，总费用为M=50百万元 第 49 种方案为2,7,4,5四个基站，总费用为M=49.5百万元 第 50 种方案为2,7,4,3四个基站，总费用为M=51百万元 第 51 种方案为2,7,5,3四个基站，总费用为M=54.5百万元 第 52 种方案为2,6,4,5四个基站，总费用为M=51.5百万元 第 53 种方案为2,6,4,3四个基站，总费用为M=53百万元 第 54 种方案为2,6,5,3四个基站，总费用为M=56.5百万元 第 55 种方案为2,4,5,3四个基站，总费用为M=57.5百万元 第 56 种方案为1,7,6,4四个基站，总费用为M=47.5百万元 第 57 种方案为1,7,6,5四个基站，总费用为M=51百万元 第 58 种方案为1,7,6,3四个基站，总费用为M=52.5百万元 第 59 种方案为1,7,4,5四个基站，总费用为M=52百万元 第 60 种方案为1,7,4,3四个基站，总费用为M=53.5百万元 第 61 种方案为1,7,5,3四个基站，总费用为M=57百万元 第 62 种方案为1,6,4,5四个基站，总费用为M=54百万元 第 63 种方案为1,6,4,3四个基站，总费用为M=55.5百万元 第 种方案为1,6,5,3四个基站，总费用为M=59百万元 第 65 种方案为1,4,5,3四个基站，总费用为M=60百万元 第 66 种方案为7,6,4,5四个基站，总费用为M=55.5百万元 第 67 种方案为7,6,4,3四个基站，总费用为M=57百万元 第 68 种方案为7,6,5,3四个基站，总费用为M=60.5百万元 第 69 种方案为7,4,5,3四个基站，总费用为M=61.5百万元 第 70 种方案为6,4,5,3四个基站，总费用为M=63.5百万元 Press any key to continue 【附录三】 问题二中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); 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); c1=@if(x1#eq#1,0.68,0); c2=@if(x1+x2#eq#1,0.68,1); c3=@if(x2#eq#1,0.68,1); c4=@if(x1+x3#eq#1,0.68,0); c5=@if(x4+x2#eq#1,0.68,1); c6=@if(x4#eq#1,0.68,1); c7=@if(x3+x6#eq#1,0.68,1); c8=@if(x3+x4+x5#eq#1,0.68,1); c9=@if(x4+x5#eq#1,0.68,1); c10=@if(x3+x6#eq#1,0.68,1); c11=@if(x6#eq#1,0.68,1); c12=@if(x5+x6+x7#eq#1,0.68,1); c13=@if(x7#eq#1,0.68,1); c14=@if(x7#eq#1,0.68,1); c15=@if(x6+x7#eq#1,0.68,1); s=2*x1*c1+4*(b1)*(c2)+13*x2*c3+6*(b2)*(c4)+9*(b3)*(c5)+4*x4*c6+7.5*(b4)*(c7)+12.5*(b5)*(c8)+10*(b6)*(c9)+11*(b7)*(c10)+6*x6*c11+14*(b8)*(c12)+9*x7*c13+3.5*x7*c13+6*(b9)*(c15); @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: 0 Total solver iterations: 112 Variable Value Reduced Cost X1 0.000000 -2.000000 X2 1.000000 -13.00000 X4 1.000000 -4.000000 X6 1.000000 -6.000000 X7 1.000000 -12.50000 X3 0.000000 0.000000 X5 0.000000 0.000000 B1 1.000000 0.000000 B2 0.000000 0.000000 B3 1.000000 0.000000 B4 1.000000 0.000000 B5 1.000000 0.000000 B6 1.000000 0.000000 B7 1.000000 0.000000 B8 1.000000 0.000000 B9 1.000000 0.000000 A 45.00000 0.000000 C1 0.000000 0.000000 C2 0.6800000 0.000000 C3 0.6800000 0.000000 C4 0.000000 0.000000 C5 1.000000 0.000000 C6 0.6800000 0.000000 C7 0.6800000 0.000000 C8 0.6800000 0.000000 C9 0.6800000 0.000000 C10 0.6800000 0.000000 C11 0.6800000 0.000000 C12 1.000000 0.000000 C13 0.6800000 0.000000 C14 0.6800000 0.000000 C15 1.000000 0.000000 S 83.74000 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 13 0.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 0.000000 0.000000 19 0.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 0.000000 0.000000 25 0.000000 0.000000 26 0.000000 0.000000 27 0.000000 0.000000 28 0.000000 0.000000
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
