数学建模课程设计-优化问题.doc

摘要在手机普遍流行的今天，建设基站的问题分析对于运营商来说很有必要。本文针对现有的条件和题目的要求进行讨论。在建设此模型中，核心运用到了0-1整数规划模型，且运用lingo软件求解。对于问题一： 我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即max=，根据题目要求建立约束条件，并用数学软件LINGO对其模型求解，得到最优解。对于问题二： 同样运用0-1整数规划模型，建立目标函数时，此处假设每个用户的正常资费相同，所以68%可以用减少人口来求最优值，故问题二的目标函数为：max=上述模型得到最优解结果如下：研究问题建中继站位置所需费用最优值问题一2、4、6、745百万覆盖中人口数109.5千人问题二2、4、6、745百万获得资费83.74a关键字：基站; 0-1整数规划；lingo软件目录1 问题的重述32 问题的分析43 模型的假设与符号的说明53.1模型的假设 53.2符号的说明 54 模型的建立及求解. 54.1模型的建立 54.2 模型的求解 65 模型结果的分析76 优化方向77 参考文献88、附录 91、 问题的重述某手机运营商准备在一个目前尚未覆盖的区域开展业务，计划投资5000万元来建设基站。该区域由15个社区组成，有7个位置可以建设基站，每个基站只能覆盖有限个社区。图1是该区域的示意图，每个社区简化为一个多边形，每个可以建设基站的位置已用黑点标出。由于地理位置等各种条件的不同，每个位置建设基站的费用也不同，且覆盖范围也不同。表1中列出了每个位置建设基站的费用以及能够覆盖的社区，表2列出了每个社区的人口数。图1表1 每个位置建设基站的费用及所能覆盖的社区位置1234567费用（百万元）9.57191417.51311覆盖社区1,2,42,3,54,7,8,105,6,8,98,9,127,10,11,12,1512,13,14,15 表2 每个社区的人口数量社区123456789101112131415人口（千人）24136947512.5101161493.56问题一：在不超过5000万建设费用的情况下，在何处建设基站，能够覆盖尽可能多的人口；问题二：考虑到基站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个基站信号覆盖的小区通讯资费按正常资费的68%收取，有两个或两个以上基站信号覆盖的小区的通讯资费按正常收取，针对于5000万元的预算，应该如何建设基站，才能够使得资费的收入达到最大。2、 问题的分析 手机是通过在地面上建立了大量的无线基站来传递信号,达到通话目的。若某手机运营商准备在一个目前尚未覆盖的区域开展业务，则需要考虑基站的覆盖能力，即某基站覆盖的那些社区以及社区的人数等问题，在此基础上建立基站网络，最大程度上服务于小区的居民。根据题目条件，为了更好地分析问题，我们将基站对于小区的覆盖情况用下表来描述。表3每个基站所能覆盖的社区1234567891011121314151OOO2OOO3OOOO4OOOO5OOO6OOOOO7OOOO考虑到有的小区仅仅只有一个基站覆盖，因此要想实现所有社区的全面覆盖，有些基站是不能缺少的。例如，1号、3号、6号、11号、13号、14号社区均只可能有一个基站覆盖，那么为这些社区服务的基站是必不可少的。因此，基站1号、2号、4号、6号、7号必须要设。建设这些基站的费用9.5+7+14+13+11=54.550;此时，仅仅必须建设的基站的费用已经不能满足要求。因此，要想在实现不超过5000万建设费用的情况下实现对所有社区的覆盖是不可能的。针对问题一： 建立0-1整数规划，通过对题目条件和问题的挖掘，列写出规模型中的目标函数和约束条件。运用数学软件lingo求解，得到合理的基站建设方案。针对问题二： 在满足基站建设成本不超过5000万元的情况下，确定一个合理的基站建设方案，使得运营商的资费收入最高。 问题关键在于确定每一个社区用哪几个社区覆盖，然后计算根据题目中的“仅有一个基站信号覆盖的小区通讯资费按正常资费的68%收取，有两个或两个以上基站信号覆盖的小区的通讯资费按正常收取”的原则，可以列写出关于资费收入的函数表达式。运用数学软件lingo最终把满足条件的基站建设方案解出，最终确定出最理想的基站建设方案。3、 模型的假设与符号的说明3.1模型的假设（1）若某社区处在某一基站覆盖范围内,则该社区中的人口全部被该基站覆盖；（2）各社区的手机使用率相同；（3）每位手机使用者的通讯资费相同；（4）该区域只存在这一种通信网络；（5）每个基站覆盖且仅覆盖图1所列出的覆盖区域；（6）通讯信号不受地形地貌,气候变化等因素影响；（7）社区人口保持不变；（8）不考虑手机漫游等情况；（9）每个基站位置最多只建一个基站。3.2符号的说明 表示第i个基站建设情况（i=1,2,.7），当=1时，表示第i个基站要被建设； 当=0时表示第i个基站不要被建设 表示第j个社区被覆盖情况（j=1,2,.15）,当=1时，表示第j个社区被覆盖；当=0时表示第j个社区未被覆盖 表示第j个社区的人口数（j=1,2,.15） 表示第i个基站被建设所需的费用(i=1,2,.7) 表示第j个社区被覆盖情况（j=1,2,.15）,当j=i，表示第j个社区被多个基站覆盖；当=0.68时，表示第j个社区被1个基站覆盖；当=0时表示第j个社区未被覆盖4、 模型的建立及求解4.1模型的建立问题一：设（i=1，2,.7表示7个中继站)表述每一个基站的建设情况。引入0-1变量，即= 1,表示第i个基站要建立 0，表示第i个基站不建立在此模型的建立过程中，由于同一个社区可能有多个基站覆盖，如果覆盖同一社区的基站都要建设时，那么基站覆盖的人口就会被重复计算。故我们将目标转移到社区上，每个社区的被覆盖情况只有两种，要么被覆盖要么不被覆盖我们也引入0-1变量，即 = 1, 表示第j个社区被覆盖 0，表示第j个社区不被覆盖这样就可避免了对同一社区人口的重复计算。 本问题的目标是使得基站覆盖的人口尽量多。根据表1、2、3我们可以得到目标函数：max=由于考虑到1号、3号、6号、11号、13号、14号社区均只可能有一个基站覆盖，这里我们让代替（即第j个社区只被第i个基站覆盖），则目标函数：max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*x6+14*(y12)+9*x7+3.5*x7+6*(y15);要求建设基站的费用不超过5000万元故约束条件： (9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)=50;问题二： 题中考虑到基站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个基站信号覆盖的小区通讯资费按正常资费的68%收取，有两个或两个以上基站信号覆盖的小区的通讯资费按正常收取，为此，我们需要得到新的模型来进行求解，因为假设每个用户的正常资费相同，所以68%可以用减少人口来求最优值，与问题一类似，考虑到1号、3号、6号、11号、13号、14号社区均只可能有一个基站覆盖，这里我们让代替（即第j个社区只被第i个基站覆盖），故问题二的目标函数为：max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*x6+14*(y12)+9*x7+3.5*x7+6*(y15); 题目要求建设中继站的费用不超过5000万元故约束条件：(9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)=50; 在此方案下，获得的资费为：s=2*x1*(k1)+4*(y2)*(k2)+13*x2*(k3)+6*(y4)*(k4)+9*(y5)*(k5)+4*x4*(k6)+7.5*(y7)*(k7)+12.5*(y8)*(k8)+10*(y9)*(k9)+11*(y10)*(k10)+6*x6*(k11)+14*(y12)*(k12)+9*x7*(k13)+3.5*x7*(k13)+6*(y15)*(k15); 4.2 模型的求解问题一：根据附录中的程序一利用LINGO求解得到最佳的方案如下表4所示：表4基站1234567建设情况不建设建设不建设建设不建设建设建设此方案所需费用为45百万元，覆盖人口为109.5千人。问题二：根据附录中的程序二利用LINGO求解得到最佳的方案如下表5所示：表5基站1234567建设情况不建设建设不建设建设不建设建设建设此方案所需要的费用为45百万元，获得资费83.74a(a为标准的资费常数)。5、结果分析对于问题一，要求在基站建设成本不超过50百万元的情况下，确定一个合理的基站建设方案，使得覆盖的人口尽可能的多。所以我们根据题意建立了0-1规划模型，运用LONGO软件对规划模型求解，得到在2,4,6,7号位置建设基站时，覆盖人口最多为109.5千人，同时建设基站的费用为45百万元，满足约束条件中的费用不超过50百万的要求。对于问题二，要求的是在满足基站建设成本不超过5000万元预算条件下，怎样建设基站，使得运营商的资费收入最高。根据题目中“仅有一个基站信号覆盖的小区人均通讯资费按正常资费的68%收取，而有两个或两个以上站信号覆盖的小区人均的通讯资费按正常收取”的要求，我们运用了0-1规划方法，并且用lingo数学软件得出最大资费收益为S=83.74a 。6、优化方向该模型巧妙的解决了相邻信号站重复覆盖的人口数的问题，使得LINGO求解方便，缺点是当数据量更大时计算会比较复杂，所以可以考虑用MATLAB编程求解，列出基站和小区的关系矩阵。并且考虑问题时我们只考虑了两个重要的因素， 因此，对于本问题的延伸，可更改规划目标，并加入更多的约束条件，如：通过研究得出地区信号覆盖层数对信号质量的影响，继而影响用户数量及收费标准，在通过各种方法将对这些因素进行定量分析，建立合理的基站最大覆盖模型。以最大收益为目标函数。新问题的规划方法可以再上述模型为框架的基础上修改而得。7、参考文献1.胡运权 编著运筹学教程 清华大学出版社 2007.04第三版；2.蒋启源 编著数学模型 高等教育出版社 2003.08第三版；3.吴礼斌，李柏年 数学实验与建模 M，北京：国防工业出版社，2007年；4王兵团 数学建模基础M，北京：北京交通大学出版社，2004年；5胡守信，李柏年 基于MATLAB的数学试验M，北京：科学出版社，2004年；6李明月 移动通讯基站建设问题/view/72d9ab3c0066f5335a812111.html 2012.12.17/2015.07.02附录：程序一：问题一model: max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*x6+14*(y12)+9*x7+3.5*x7+6*(y15); (9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)=50; Y2=if(x1+x2#eq#0,0,1); Y4=if(x1+x3#eq#0,0,1); Y5=if(x2+x4#eq#0,0,1); Y7=if(x3+x6#eq#0,0,1); Y8=if(x3+x4+x5#eq#0,0,1); Y9=if(x4+x5#eq#0,0,1); Y10=if(x3+x6#eq#0,0,1); Y12=if(x5+x6+x7#eq#0,0,1); Y15=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: 185 Variable Value Reduced Cost X1 0.000000 -2.000000 Y2 1.000000 0.000000 X2 1.000000 -13.00000 Y4 0.000000 0.000000 Y5 1.000000 0.000000 X4 1.000000 -4.000000 Y7 1.000000 0.000000 Y8 1.000000 0.000000 Y9 1.000000 0.000000 Y10 1.000000 0.000000 X6 1.000000 -6.000000 Y12 1.000000 0.000000 X7 1.000000 -12.50000 Y15 1.000000 0.000000 X3 0.000000 0.000000 X5 0.000000 0.000000 Row Slack or Surplus Dual Price1 109.5000 1.000000 2 5.000000 0.000000 3 0.000000 4.000000 4 0.000000 6.000000 5 0.000000 9.000000 6 0.000000 7.500000 7 0.000000 12.50000 8 0.000000 10.00000 9 0.000000 11.00000 10 0.000000 14.00000 11 0.000000 6.000000程序二：问题二model: max=2*x1+4*(y2)+13*x2+6*(y4)+9*(y5)+4*x4+7.5*(y7)+12.5*(y8)+10*(y9)+11*(y10)+6*x6+14*(y12)+9*x7+3.5*x7+6*(y15); (9.5*x1+7*x2+19*x3+14*x4+17.5*x5+13*x6+11*x7)=50; y2=if(x1+x2#eq#0,0,1); y4=if(x1+x3#eq#0,0,1); y5=if(x2+x4#eq#0,0,1); y7=if(x3+x6#eq#0,0,1); y8=if(x3+x4+x5#eq#0,0,1); y9=if(x4+x5#eq#0,0,1); y10=if(x3+x6#eq#0,0,1); y12=if(x5+x6+x7#eq#0,0,1); y15=if(x6+x7#eq#0,0,1); k1=if(x1#eq#1,0.68,0); k2=if(x1+x2#eq#1,0.68,1); k3=if(x2#eq#1,0.68,1); k4=if(x1+x3#eq#1,0.68,0); k5=if(x4+x2#eq#1,0.68,1); k6=if(x4#eq#1,0.68,1); k7=if(x3+x6#eq#1,0.68,1); k8=if(x3+x4+x5#eq#1,0.68,1); k9=if(x4+x5#eq#1,0.68,1); k10=if(x3+x6#eq#1,0.68,1); k11=if(x6#eq#1,0.68,1); k12=if(x5+x6+x7#eq#1,0.68,1); k13=if(x7#eq#1,0.68,1); k14=if(x7#eq#1,0.68,1); k15=if(x6+x7#eq#1,0.68,1); s=2*x1*(k1)+4*(y2)*(k2)+13*x2*(k3)+6*(y4)*(k4)+9*(y5)*(k5)+4*x4*(k6)+7.5*(y7)*(k7)+12.5*(y8)*(k8)+10*(y9)*(k9)+11*(y10)*(k10)+6*x6*(k11)+14*(y12)*(k12)+9*x7*(k13)+3.5*x7*(k13)+6*(y15)*(k15); 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: 115 Variable Value Reduced Cost X1 0.000000 -2.000000 Y2 1.000000 0.000000 X2 1.000000 -13.00000 Y4 0.000000 0.000000 Y5 1.000000 0.000000 X4 1.000000 -4.000000 Y7 1.000000 0.000000 Y8 1.000000 0.000000 Y9 1.000000 0.000000 Y10 1.000000 0.000000 X6 1.000000 -6.000000 Y12 1.000000 0.000000 X7 1.000000 -12.50000 Y15 1.000000 0.000000 X3 0.000000 0.000000 X5 0.000000 0.000000 K1 0.000000 0.000000 K2 0.6800000 0.000000 K3 0.6800000 0.000000 K4 0.000000 0.000000 K5 1.000000 0.000000 K6 0.6800000 0.000000 K7 0.6800000 0.000000 K8 0.6800000 0.000000 K9 0.6800000 0.000000 K10 0.6800000 0.000000 K11 0.6800000 0.000000 K12 1.000000 0.000000 K13 0.6800000 0.000000 K14 0.6800000 0.000000 K15 1.000000 0.000000 S 83.74000 0.000000 Row Slack or Surplus Dual Price 1 109.5000 1.000000 2 5.000000 0.000000 3 0.000000 4.000000 4 0.000000 6.000000 5 0.000000 9.000000 6 0.000000 7.500000 7 0.000000 12.50000 8 0.000000 10.00000 9 0.000000 11.00000 10 0.00000