移动通讯基站建设问题 结课

《移动通讯基站建设问题 结课》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

数学建模结课作业论文题目：移动通讯基站建设问题班级：材科112班姓名：贺文杰学号：201101524215班级：材科112班姓名：胡小磨学号：2011015242072013年5月25日23 移动通讯基站最优选址模型背景：移动基站的选址工作是基站前期建设至关重要的环节，它不仅关系到通信网络覆盖优化，还直接影响到工程投资效果、建设进度、后期维护、施工难度等方面。基站选址中，通常情况下讲 “就高不就低”，是说尽量将基站选在地势较高的场地，以减少铁塔设计高度，达到节约工程投资的目的。具体操作中应结合实际情况，不要走向极端          随着城市乡村经济建设的步伐加快，生活生产规划用地愈加紧缺，基站的可选择区域越来越小。人们在工程建设中往往把一些原生的、根子上的不足推到工程设计上，设计人员也是无法解决的，采取避开建设不利地段是最根本的选择。因此，在决策选址用地问题上，必须把基站通信安全放在首位。           在我国移动通信建设正处在新的一轮发展竞争的阶段，“村通工程”、“补点工程”、“季度工程” 时间紧，任务重。这就要求工程管理、地质勘探、网络设计及土建设计人员，各执其责，密切配合。综合分析基站建设各种因素，选择安全可靠，经济合理移动站址，为当地社会提供优质安全的通信网络。摘要本文综合利用多种模型，在资金和备选地址确定的情况下，对手机中继站的选址问题进行了求解和优化。我们首先对题中所给的数据进行了整理和分析，引入了回溯模型、0-1规划模型，为以下问题的解决作了准备。对于问题一，我们运用两种方法，并用不同的软件求解：v方法一：我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即，根据题目要求建立约束条件，并用数学软件LINGO很容易解得题目最优解；v方法二：联系问题的性质，我们引入了回溯模型，采用迭代加深搜索的思想，可以在满足题目所给条件下搜索到一条到达解空间的路径。然后，根据所有的路径对应的中继站的建设情况求解出相应的中继站覆盖的人口，然后经过比较即可求得最终结果，我们运用软件MATLAB进行编程求解。对于问题二，我们同样运用以上两种方法，只是针对题目要求略微改变目标函数，并用不同的软件求得相同解，最优方案不变，和问题一相同。求得的结果如下表：研究问题建中继站位置所需费用百万最优值问题一2，4，6，744.5覆盖中人口数109千人问题二2，4，6，744.5获得资费85c千元本文运用的两种方法都有它们各自的优点和不足，对于第一种方法，我们采用枚举法，我们会发现总共有种情况，但因为数据比较少，运用LINGO软件求解，程序简单；对于第二种方法，我们采用回溯算法，需要遍历的分支相对减少，但是程序相对较复杂，比较适合数据较多的模型。本文还对“仅有一个中继站信号覆盖的小区通讯资费按正常资费的10%~90%区间23 内的收取”做了讨论，得出了最优方案随百分比的改变的变化曲线图。关键字：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,13,123 12,154,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进行编程来遍历满二叉树，所需的时间过长，也可能发生误差，23 再加上在总资金上的约束。这样就会显得又写程序的运行显得多余，因此在此约束条件上我们可以采用分支定界法来删除部分的枝叶，再加上一些其他的约束，比如人数上的约束，又可以删除一些枝叶这样大大的增加了速度。具体的思想还要套用回溯法的思想，这样得到了中继站的建立规划，我们就可以根据相应的已知数据进行求解相关的信息，比如花费的资金，所覆盖的社区与人数。针对问题二，在满足中继站建设成本不超过5000万元的情况下，确定一个合理的中继站建设方案，使得运营商的资费收入最高。我们也采用了两种方法：Ø问题关键在于确定每一个社区用那几个社区覆盖，然后计算根据题目中的“仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取，有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取”的原则，可以列写出关于资费收入的函数表达式。运用数学软件lingo最终把满足条件的中继站建设方案对应的资费收入进行比较，最终确定出最理想的中继站建设方案。Ø只要在问题一第二种方法程序的运行结果中得到社区的覆盖信息进行判断在求出总的资金。既利用相应的有效人数与总费用的投入进行判断标准。一．模型假设及符号说明3.1模型假设（1）若某社区处在某一中继站覆盖范围内,则该社区中的人口全部被该中继站覆盖；（2）各社区的手机使用率相同；（3）每位手机使用者的通讯资费相同；（4）该区域只存在这一种通信网络；（5）每个中继站覆盖且仅覆盖表1上所列出的覆盖区域；（6）通讯信号不受地形地貌,气候变化等因素影响；（7）社区人口保持不变；（8）不考虑手机漫游等情况；（9）每个中继站位置最多只建一个中继站。3.2符号说明表述第个中继站的建设情况(其中)。当时，表示第个中继站要建设;当时，表示第个中继站不建设表述第个社区的覆盖情况(其中)。当时，表示第个社区被覆盖到;当时，表示第个社区不被覆盖到表示第个社区的人口数(其中)表示第个中继站的建设费用(其中)表示第个社区的覆盖情况(其中)。当时，表示第个社区只被一个中继站被覆盖到;当时，表示第个社区被一个以上中继站被覆23 盖到；当时，表示第个社区没被中继站被覆盖到表示获得的单位资费（千元）一．模型建立及求解4.1问题一Ø0—1整型规划4.1.1模型建立设(表示7个中继站)表述每一个中继站的建设情况。引入0-1变量，即在此模型的建立过程中，由于同一个社区可能有多个中继站覆盖，如果覆盖同一社区的中继站都要建设时，那么中继站覆盖的人口就会被重复计算。故我们将目标转移到社区上，每个社区的被覆盖情况只有两种，要么被覆盖要么不被覆盖，我们也引入0-1变量，即这样就可避免了对同一社区人口的重复计算。本问题的目标是使得中继站覆盖的人口尽量多。根据表1，2，3我们可以得到目标函数：题目要求建设中继站的费用不超过5000万元，故约束条件：4.1.2模型求解：可知模型为：23 根据附录中的程序利用LINGO求解得到最佳的方案如下表所示：中继站1234567建设情况不建设建设不建设建设不建设建设建设此方案所需费用为44.5百万<50百万，覆盖人口为109千人。Ø回溯算法4.1.3模型建立回溯模型可以系统的搜索一个问题的所有解或任一解，按深度优先策略，从根节点如图所示就是I层出发搜索该模型可以搜索至解空间树的任一点时，先判断该首先我们节点是否包含问题的解。如果肯定不包含，则跳过对以该节点为根的字数的搜索，逐层向其回溯。否则进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索便才结束。回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。在回溯模型中，我们采用了迭代加深搜索的思想。可以在满足题目所给条件下搜索到一条到达解空间的路径。然后，根据所有的路径对应的中继站的建设情况求解出相应的中继站覆盖的人口，然后经过比较即可求得最终结果。如图23 I1111110000001）当在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=[96.52014.5191310.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=[110100000000000；011010000000000；000100110100000；000011011000000；000000011001000；000000100111001；000000000001111]花费的资金为：l*c'数组中的0-1表示的是中继站对社区的覆盖与否。2)程序设计：定义location1函数来计算相关的数据，并且函数结果用数组来进行存储，包含各种情况的总资金，总覆盖人数。利用for循环从根节点进行搜索，用0-1变量来表示是否将该中继站进行建设，并且每进入一个节点时都要进行判断总资金是否少于50即用约束条件ifl*c'<=50进行判断；否则将t退回节点即转入else。23 在得到的所有数组中我们要根据总人数来进行刷选：这里我们限制最小的人数为90千人。这里还需要利用函数sign函数来确定社区的覆盖与否。继而可得到相应的总人覆盖。刷选出适合的数组后，得到相应的资金花费并存入数组loc1给予输出。3)模型结果：根据上面的程序我们可以得到以下的结果：方案中继站1中继站2中继站3中继站4中继站5中继站6中继站7人数（千）费用（百万）111100109148.5211100019746311010019240.5411000119139510010111044760110011101507011000195378010101110944．5901001111054910001100192451100010119238对于上面的数据，要求是尽可能的覆盖人数多，发现方案8覆盖的人数是最多的。并且对应所花费的费用是44.5百万在这里面也不是最大的因此是比较好的方案，则对于方案8相应的方案是：中继站1234567建设情况不建设建设不建设建设不建设建设建设则由上面的表格我们很明显的知道方案与方法一求得的完全相同。4.2问题二Ø0—1整型规划4.2．1模型建立题中考虑到中继站出现故障维修的时候可能会出现所覆盖的社区信号中断等问题，为此对通讯资费进行了调整，规定，仅有一个中继站信号覆盖的小区通讯资费按正常资费的70%收取，有两个或两个以上中继站信号覆盖的小区的通讯资费按正常收取，为此，我们需要得到新的模型来进行求解，因为假设每个用户的正常资费相同，所以70%可以用减少人口来求最优值，故问题二的目标函数为：题目要求建设中继站的费用不超过5000万元，故约束条件：4.2.2模型求解：可知模型为：23 根据程序二，利用LINGO求解得到最优的建立方案如下表所示：中继站1234567建设情况不建设建设不建设建设不建设建设建设此方案所需要的费用为44.5百万<50百万，获得资费85c千元（其中c为常数）。Ø回溯算法4.2.3模型建立：同样的是选择最优深度搜索，一旦在搜索路径上出现不满足限制约束条件的情况，就终止此路径的进一步搜索，去寻求另外的搜索路径。解决此问题中，关键在于那几个社区最终有几个中继站覆盖的确定，因为这一确定的结论将会影响到资费的收入。而且两者必须联系起来一起考虑。在迭代搜索模型中，终止搜索的条件为：搜索路径在未达到最终解空间时，建设中继站的费用超过5000万元，或者搜索路径到达了解空间。这样可以将搜索路径达到解空间的中继站的建设情况，确定每个社区有几个中继站覆盖，以便确定应对社区用户是按照正常收取资费还是收取资费的70%。在计算总资费的时候，我们用有效人数来进行表示，有效人数就是在只有一个中继站覆盖的社区：人数*0.7就是这个社区的有效人数。为此，可以将搜索路径上各中继站的建设情况全部列出。然后根据题目中的表一来确定为每一社区服务的中继站的个数。再算出有效地人数；还应考虑到投入和收入的关系问题，应尽量投入尽量少的钱，取得尽量多的收入。因此，我们在考虑资费收入时，把社区内移动用户数与建设中继站的投入的比值作为研究的最终目标量。这样，最终选择出资费收入高的搜索路径。从而解决了满足条件的收益最大的中继站建设方案的确定。4.2.2模型求解：1)数据准备：定义数组存储每个社区的人数：p=[2,4,13,6,9,4,8,12,10,11,6,14,9,3,6]；建设7个中继站所需要的价钱：c=[96.52014.5191310.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=[110100000000000;011010000000000;000100110100000;000011011000000;000000011001000;000000100111001;00000000001111]花费的资金为：l*c'数组中的0-1表示的是中继站对社区的覆盖与否。2)程序设计：定义location1函数来计算相关的数据，并且函数结果用数组来进行存储，包含各种情况的总资金，总覆盖人数。利用for循环从根节点进行搜索，用0-1变量来表示是否将该中继站进行建设，并且每进入一个节点时都要进行判断总资金是否少于50即用约束条件ifl*c'<=50进行判断；否则将t退回节点即转入else。23 在得到的所有数组中我们要根据总人数来进行刷选：这里我们限制最小的人数为60。这里还需要利用函数sign函数来确定社区的覆盖与否。接着总人数的确定中一个中继站覆盖的社区人数需要乘以0.7继而可得到相应的总人覆盖。刷选出适合的数组后，得到相应的资金花费并存入数组loc1给予。3)模型结果根据上面的程序我们可以得到以下的结果：方案中继站1中继站2中继站3中继站4中继站5中继站6中继站7有效人数（千）总费用（百万）1111001072.448.52111000170.9463110001170.9394100101178.8475011001182.450601010118544.57010011179.5498000101170.438并且可以得到相应的有效人数与总费用的比值为：方案12345678比值1.49281.54131.81791.67661.64801.91011.62241.8526由上面可以发现方案6的比值是最大的，很明显的可以择取方案6的建设计划,则具体的建设方案及其覆盖社区如下：中继站1234567建设情况不建设建设不建设建设不建设建设建设结果也与方法一的完全相同。这时，要建设的中继站有2号、4号、6号和7号。其中第一和第四区域没有被任何中继站覆盖，不产生资费收入；而第五、第十二、第十五区域被两个或两个以上的中继站覆盖，通信资费按正常资费收取；其他区域只有一个基站覆盖，通信资费按照正常资费的70%23 收取。在此种方案下，中继站建设总费用44.50(百万元)，有效人数为8.5（万）。一．结果分析及检验对于问题一，由两种方法建立模型求解的结果都相同，得到最佳的建站点2,4,6,7，所需费用44.5万元，覆盖人口109千人，结果正确，但方法一在编程上较简单，方法二遍历次数较少，但编程难度系数较高，需要一定的编程能力。对于问题二，两种方法也都能求出同样的结果，得到最佳的建站点2,4,6,7，所需费用47.3万元，获得资费为85c千元。由上图可以清晰看出，收取资费的百分比增大，再摸范围内覆盖总人数也随之增大，但不会全部覆盖。23 由上图可以看出，收取资费的百分比增大，获得的总费用呈分段函数，在一定区间内数值不发生改变。一．优化方向该模型巧妙的解决了相邻信号站重复覆盖的人口数的问题，使得在LINGO求解方便，缺点是放数据量更大时计算会比较复杂，所以可以考虑用MATLAB编程求解，列出基站和小区的关系矩阵。但是本文的缺点是考虑问题时我们只考虑了两个重要的因素，因此在问题的延伸中，本文加入更多的约束条件，使得模型和求解更加的实用。中继站的后续研究还可以从它建设时的各种技术因素、社会因素、安全因素等来考虑，在通过各种方法将对这些因素进行定量分析，建立合理的中继站最大覆盖模型。对于本问题的延伸，可更改规划目标，并加入更多的约束条件，如：通过研究得出地区信号覆盖层数对信号质量的影响，继而影响用户数量及收费标准，以最大收益为目标函数。新问题的规划方法可以再上述两个模型为框架的基础上修改而得。对于0、1规划类问题，利用电工学数字信号处理的方法也可以方便的解决，就本问题而言，其目标函数利用数字信号寄存器的工作逻辑十分相似，可尝试其他软件求解。二．参考文献[1].胡运权编著《运筹学教程》清华大学出版社2007.04第三版；[2].蒋启源编著《数学模型》高等教育出版社2003.08第三版；[3].上官士青辛浩然《数学建模通信基站选址问题的lingo求解》机械电子2009,23:92-93。[4]吴礼斌，李柏年，数学实验与建模[M]，北京：国防工业出版社，2007年；[5]王兵团，数学建模基础[M]，北京：北京交通大学出版社，2004年；[6]胡守信，李柏年，基于MATLAB的数学试验[M]，北京：科学出版社，2004年；程序一(问题一法一)：max=2*k1+4*b1+13*k2+6*b2+9*b3+4*k4+8*b4+12*b5+10*b6+11*b7+6*k6+14*b8+9*k7+3*k7+6*b9;23 9*k1+6.5*k2+20*k3+14.5*k4+19*k5+13*k6+10.5*k7<=50;b1=@IF(k1+k2#eq#0,0,1);b2=@IF(k3+k1#eq#0,0,1);b3=@IF(k4+k2#eq#0,0,1);b4=@IF(k3+k6#eq#0,0,1);b5=@IF(k3+k4+k5#eq#0,0,1);b6=@IF(k4+k5#eq#0,0,1);b7=@IF(k3+k6#eq#0,0,1);b8=@IF(k5+k6+k7#eq#0,0,1);b9=@IF(k6+k7#eq#0,0,1);@BIN(k1);@BIN(k2);@BIN(k3);@BIN(k4);@BIN(k5);@BIN(k6);@BIN(k7);endLocaloptimalsolutionfound.Objectivevalue:109.0000Objectivebound:109.0000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:67VariableValueReducedCostK10.000000-2.000000B11.0000000.000000K21.000000-13.00000B20.0000000.000000B31.0000000.000000K41.000000-4.000000B41.0000000.000000B51.0000000.000000B61.0000000.000000B71.0000000.000000K61.000000-6.000000B81.0000000.000000K71.000000-12.00000B91.0000000.000000K30.0000000.000000K50.0000000.00000023 RowSlackorSurplusDualPrice1109.00001.00000025.5000000.00000030.0000004.00000040.0000006.00000050.0000009.00000060.0000008.00000070.00000012.0000080.00000010.0000090.00000011.00000100.00000014.00000110.0000006.000000程序二：（问题二法一）max=2*k1*0.7+4*b1+13*k2*0.7+6*b2+9*b3+4*k4*0.7+8*b4+12*b5+10*b6+11*b7+6*k6*0.7+14*b8+9*k7*0.7+3*k7*0.7+6*b9;9*k1+6.5*k2+20*k3+14.5*k4+19*k5+13*k6+10.5*k7<=50;b1=@IF(k1+k2#gt#1,1,@IF(k1+k2#eq#1,0.7,0));b2=@IF(k3+k1#gt#1,1,@IF(k3+k1#eq#1,0.7,0));b3=@IF(k4+k2#gt#1,1,@IF(k4+k2#eq#1,0.7,0));b4=@IF(k3+k6#gt#1,1,@IF(k3+k6#eq#1,0.7,0));b5=@IF(k3+k4+k5#gt#1,1,@IF(k3+k4+k5#eq#1,0.7,0));b6=@IF(k4+k5#gt#1,1,@IF(k4+k5#eq#1,0.7,0));b7=@IF(k3+k6#gt#1,1,@IF(k3+k6#eq#1,0.7,0));b8=@IF(k5+k6+k7#gt#1,1,@IF(k5+k6+k7#eq#1,0.7,0));b9=@IF(k6+k7#gt#1,1,@IF(k6+k7#eq#1,0.7,0));@BIN(k1);@BIN(k2);@BIN(k3);@BIN(k4);@BIN(k5);@BIN(k6);@BIN(k7);endLocaloptimalsolutionfound.Objectivevalue:85.00000Objectivebound:85.00000Infeasibilities:0.000000Extendedsolversteps:10Totalsolveriterations:421VariableValueReducedCostK10.000000-1.40000023 B10.70000000.000000K21.000000-9.100000B20.0000000.000000B31.0000000.000000K41.000000-2.800000B40.70000000.000000B50.70000000.000000B60.70000000.000000B70.70000000.000000K61.000000-4.200000B81.0000000.000000K71.000000-8.400000B91.0000000.000000K30.0000000.000000K50.0000000.000000RowSlackorSurplusDualPrice185.000001.00000025.5000000.00000030.0000004.00000040.0000006.00000050.0000009.00000060.0000008.00000070.00000012.0000080.00000010.0000090.00000011.00000100.00000014.00000110.0000006.000000程序三：（问题一法二）functionloc1=location1(a)c=[9.00006.500020.000014.500019.000013.000010.5000];p=[2,4,13,6,9,4,8,12,10,11,6,14,9,3,6];i=1;a1=[1,0];a2=[1,0];a3=[1,0];a4=[1,0];a5=[1,0];a6=[1,0];fori1=1:2l=zeros(1,7);l(1)=a1(i1);ifl*c'<=5023 fori2=1:2l(2)=a2(i2);ifl*c'<=50fori3=1:2l(3)=a3(i3);ifl*c'<=50fori4=1:2l(4)=a4(i4);ifl*c'<=50fori5=1:2l(5)=a5(i5);ifl*c'<=50fori6=1:2l(6)=a6(i6);ifl*c'<=50l(7)=1;ifl*c'<=50forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:15s(j)=sign(s(j));endpo=p.*s;ifsum(po)>=90loc1(i,1:7)=l;loc1(i,8)=sum(po);loc1(i,9)=l*c';i=i+1;endelsel(7)=0;ifl*c'<=50forj=1:723 b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:15s(j)=sign(s(j));endpo=p.*s;ifsum(po)>=90loc1(i,1:7)=l;loc1(i,8)=sum(po);loc1(i,9)=l*c';i=i+1;endendendelsel(6)=1-sign(l(6));endendelsel(5)=1-sign(l(5));endendelsel(4)=1-sign(l(4));endendelsel(3)=1-sign(l(3));endendelsel(2)=1-sign(l(2));endendelsel(1)=1-sign(l(1));endend程序四：（问题二法二）functionloc2=location2(a)c=[9.00006.500020.000014.500019.000013.000010.5000];p=[2,4,13,6,9,4,8,12,10,11,6,14,9,3,6];i=1;m=zeros(1,15);d=zeros(1,15);23 a1=[1,0];a2=[1,0];a3=[1,0];a4=[1,0];a5=[1,0];a6=[1,0];fori1=1:2l=zeros(1,7);l(1)=a1(i1);ifl*c'<=50fori2=1:2l(2)=a2(i2);ifl*c'<=50fori3=1:2l(3)=a3(i3);ifl*c'<=50fori4=1:2l(4)=a4(i4);ifl*c'<=50fori5=1:2l(5)=a5(i5);ifl*c'<=50fori6=1:2l(6)=a6(i6);ifl*c'<=50l(7)=1;ifl*c'<=50forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:15m(j)=sign(s(j)-sign(s(j)));%超过两个覆盖的s(j)=sign(s(j));%有覆盖的d(j)=s(j)-m(j);%一个覆盖的end23 r=m+0.7*d;po=p.*r;ifsum(po)>=70loc2(i,1:7)=l;loc2(i,8)=sum(po);loc2(i,9)=l*c';i=i+1;endelsel(7)=0;ifl*c'<=50forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:15m(j)=sign(s(j)-sign(s(j)));%超过两个覆盖的s(j)=sign(s(j));%有覆盖的d(j)=s(j)-m(j);%一个覆盖的endr=m+0.7*d;po=p.*r;ifsum(po)>=70loc2(i,1:7)=l;loc2(i,8)=sum(po);loc2(i,9)=l*c';i=i+1;endendendelsel(6)=1-sign(l(6));endendelsel(5)=1-sign(l(5));endendelsel(4)=1-sign(l(4));23 endendelsel(3)=1-sign(l(3));endendelsel(2)=1-sign(l(2));endendelsel(1)=1-sign(l(1));endendend程序五（优化）functionloc3=location3(t)a=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;c=[9.00006.500020.000014.500019.000013.000010.5000];p=[2,4,13,6,9,4,8,12,10,11,6,14,9,3,6];i=1;m=zeros(1,15);d=zeros(1,15);a1=[1,0];a2=[1,0];a3=[1,0];a4=[1,0];a5=[1,0];a6=[1,0];fori1=1:2l=zeros(1,7);l(1)=a1(i1);ifl*c'<=50fori2=1:2l(2)=a2(i2);ifl*c'<=50fori3=1:2l(3)=a3(i3);ifl*c'<=50fori4=1:223 l(4)=a4(i4);ifl*c'<=50fori5=1:2l(5)=a5(i5);ifl*c'<=50fori6=1:2l(6)=a6(i6);ifl*c'<=50l(7)=1;ifl*c'<=50&&l*c'>=40forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:15m(j)=sign(s(j)-sign(s(j)));%超过两个覆盖的s(j)=sign(s(j));%有覆盖的d(j)=s(j)-m(j);%一个覆盖的endr=m+t*d;po=p.*r;ifsum(po)>=20loc3(i,1:7)=l;loc3(i,8)=sum(po);loc3(i,9)=l*c';i=i+1;endelsel(7)=0;ifl*c'<=50&&l*c'>=40forj=1:7b(j,:)=a(j,:)*l(j);ends=sum(b,1);forj=1:1523 m(j)=sign(s(j)-sign(s(j)));%超过两个覆盖的s(j)=sign(s(j));%有覆盖的d(j)=s(j)-m(j);%一个覆盖的endr=m+t*d;po=p.*r;ifsum(po)>=20loc3(i,1:7)=l;loc3(i,8)=sum(po);loc3(i,9)=l*c';i=i+1;endendendelsel(6)=1-sign(l(6));endendelsel(5)=1-sign(l(5));endendelsel(4)=1-sign(l(4));endendelsel(3)=1-sign(l(3));endendelsel(2)=1-sign(l(2));endendelsel(1)=1-sign(l(1));endendendfunctionf=f(t)23 b1=location3(t);f1=max(b1(:,8)./b1(:,9));t1=size(b1);t2=t1(1);fori1=1:t2iff1==b1(i1,8)/b1(i1,9)f(1)=b1(i1,9);f(2)=b1(i1,8);break;endendendk1=1;k2=0:0.01:1;fork3=0:0.01:1f1(k1,1:2)=f(k3);%第一列是总费用，第二列是总人数。k1=k1+1;end000023