天津大学数学建模选拔赛优秀论文

2011年天津大学大学生数学建模选拔竞赛 参赛说明 1. 数学建模选拔竞赛试共有两道（A、B），请选择你最熟悉的一道题目回答，不必做其他题目。 2. 请按规定的时间内上交试卷，过期无效。试卷要在用A4纸打印完成，手写无效。 3. 由于竞赛题目有一定的难度，因此不必做完上一个问题，才能回答下一个问题，而是需要完整地把解题的思想表达出来。 4. 由于题目难度不可能完全相同，评审中将向难度较大的题目倾斜，请参赛选手在选题时加以考虑。 5. 由于为选拔竞赛，在较好完成题目要求的前提下，提出好的问题并解答或针对所提问题做适当延伸，将考虑给预加分。 A题：基站选址问题 某移动电话运营商在一个目前尚未覆盖的区域开展业务。管理层计划投资1亿元来为此区域购置安装设备。调查表明，在此区域有7 个位置可以安设基站，每个基站只能覆盖一定数目的社区。图1是对此区域的示意图，其中将此区域划分未若干个社区，并标出了可以设置基站的位置。每个候选的位置都用黑点表示，并用数字标号，每个社区表示为一个多边形。多边形中的数字即此社区的序号。 图1：待覆盖区域地图 由于地理位置和拓扑结构的限制，每个位置建造基站的费用不同，且覆盖范围也不同。表1列出了每个基站位置能够覆盖的社区以及每个位置的建造费用。 表1：每个位置的建造费用（单位：百万元）和覆盖社区 位置 1 2 3 4 5 6 7 费用 18 13 40 35 38 26 21 覆盖社区 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                 1. 已知每个社区内的居民数目（见表2）。应在何处设置基站才能够使用给定的1亿元预算覆盖尽可能多的人口？ 表2：社区居民数（单位：千人） 社区 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 人口 2 4 13 6 9 4 8 12 10 11 6 14 9 3 6                                 2. 一位年青的工程师在研究了覆盖区域地图（图1）后发现，如果基站选择在位置1处，不仅能覆盖社区1、2、4，还应该能覆盖社区5的一部分。他发现，其他的基站位置也有类似的情况。在这种情况下，应如何确定基站的位置，在1亿元的经费预算内，使覆盖的人口尽可能多。 B题：房价问题 房价问题是当前政府和老百姓最关心的问题之一。在今年的全国人民代表大会上，温家宝总理在政府工作报告中指出：“促进房地产市场平稳健康发展。要坚决遏制部分城市房价过快上涨势头，满足人民群众的基本住房需求”是今年政府工作的任务之一。电视剧“蜗居”在全国热播，也说明老百姓对房价的关心。 你需要解决的如下问题： 1. 选择某一地区（如北京、上海、深圳），调查近些年（如2000年至2010年）房价变化情况，并根据你所调查的数据，预测下一阶段（如2011年或2012年）该地区房价的走势。 2. 房价的变化也会带来“二手房”房价和出租房租金的变化，请研究同一地区“二手房”房价、租金与房价之间的关系。 3. 近年来，国家出台了一系列抑制房价的政策（如购房贷款政策，房屋出售与出租的政策等）。请根据各项政策出台的时间，与房价的变化情况，这些政策对抑制或调控房价所起的作用。 4. 根据你所得到结果，针对当前年青人（特别是即将工作的大学生、研究生）给出你关于购房（新房或“二手房”）或租房的一些建议。 注意：上述问题的各项结论需要有数据、数学模型和计算结果的支持。 基站选址模型 [摘要] 本文主要讨论了移动通信基站的选址问题，考虑到开发商要在一亿元的资金下，使基站覆盖尽可能多的人口，我们建立了整数规划模型。该模型主要是在各基站的建筑成本低于上限值的约束条件下，求解各基站所覆盖的社区人口的最大值。在建模的过程中，我们遇到了有的基站覆盖的社区发生重叠的问题，为此，我们引入了矩阵的思想，将社区的是否被覆盖用一组新的0-1变量来表示，从而列出了一个直观、简洁的数学模型。在第二问中，我们通过讨论了基站不完全覆盖区域重叠问题后，自定义一个函数顺利的把它归入上问，保持了模型的连贯性和一致性。用隐枚举法并通过C语言编程，我们得到了模型的最优解。在结果的分析中，我们引入了性价比的概念从一个新的角度对问题进行了分析，并验证了结果的科学性。另外，我们又从电磁辐射的角度对问题进行了延伸，拓展了模型，使最后的选址既考虑了经济效益，又兼顾了环境及社会效益，更加合理。 本题的计算结果为，第一问最优方案是建设2、4、6、7基站，所需费用为95百万，覆盖109千人；第二问最优方案为2、4、6、7基站，所需费用为95百万，覆盖109.6千人。. 关键字： 基站选址  0-1规划  隐枚举法  电磁污染 一、问题重述： 某移动电话运营商计划在一个目前尚未覆盖的区域开展业务。管理层计划投资1亿元来为此区域购置安装设备。调查表明，在此区域有7 个位置可以安设基站，每个基站只能覆盖一定数目的社区。其中将此区域划分成15个社区，并标出了可以设置基站的位置。每个候选的位置都用黑点表示，并用数字标号，每个社区表示为一个多边形。多边形中的数字即此社区的序号。由于地理位置和拓扑结构的限制，每个位置建造基站的费用不同，且覆盖范围也不同。 问题1. 已知每个社区内的居民数目。应在何处设置基站才能够使用给定的1亿元预算覆盖尽可能多的人口？ 问题2. 一位年青的工程师在研究了覆盖区域地图后发现，如果基站选择在位置1处，不仅能覆盖社区1、2、4，还应该能覆盖社区5的一部分。他发现，其他的基站位置也有类似的情况。在这种情况下，应如何确定基站的位置，在1亿元的经费预算内，使覆盖的人口尽可能多。 二、问题假设： 1. 在相当一段时期内，每个社区内的居民数目保持恒定。 2. 人口在每个社区内，均匀分布。 3. 每个基站的覆盖范围大致辐射状圆形分布。 4. 建筑基站所花费的时间不大长，在这段时间内建站所需的费用基本不变。 三、符号说明： （注：下文如有用到其他符号，另行说明） 四、问题分析： 根据题意，该运营商为了要在尚未覆盖的区域内开展业务而计划修建若干个通讯基站，总的投资额为一亿元资金。在给定的七个位置上，为了科学地表示该位置基站的修筑与否，我们引入0-1变量 ， =1表示修筑i基站， =0则表示不修筑。另外，由于每个基站能同时服务若干个社区，如1位置基站能同时覆盖1，2，4三个社区，我们可以用另一个变量 ， 取值0或1来代表第i个基站是否覆盖到第j个社区。 表示第j个社区的总人口数，则所修筑的基站覆盖的社区与对应社区人口总数的乘积之和表示覆盖的总人口数。该模型是为了在总成本被限制在一亿元之内的条件下，使所建设的基站能覆盖到尽可能多的人口。 在建立模型的过程中，我们考虑到邻近基站所覆盖的社区有发生重叠的情况，这将导致部分社区的人口数在覆盖人口的统计中被重复计算，从而使最后计算出的覆盖总人口数偏大，模型与实际不符合。为了解决这个问题，我们引入了矩阵的思想，根据各个基站所覆盖的社区，以 为各个元素，建立一维行矩阵，将该系列矩阵与对应的 相乘后累加，若所得结果相应位置非零，则表示该社区人口已覆盖到，并且保证各个社区的人口在计算时不会出现重复。 五、模型建立： 从经济角度出发，电话运营商自然是希望在计划额定资金一亿元内，修筑的基站能覆盖到尽可能多社区的人口，从而获取最大的利益。因此，我们根据题意建立了总成本约束的条件下的整数规划模型。 用0-1变量 与修筑各基站所需费用 （百万）乘积的累加表示总费用 成本约束条件：  为了清晰直观的表示各个基站所覆盖的社区范围，我们为各个基站引入对应的系数矩阵 例如，第1个基站覆盖的社区为1，2，4，第2个基站覆盖社区为2，3，5，因此有 =[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 ] 定义矩阵  A=[ ]          (j=1,2,……,15) 令： 则组成A的各元素 表示某一方案下第j个社区被覆盖的程度： 若 =0， 则该社区未被覆盖; 若 1， 则该社区被完全覆盖。 为了筛选出全部所覆盖社区，并且避免重复计算的情况，我们引入了符号函数 故定义B=[ , )] 由题中所给表2，可以得出每个社区常住的居民人数 (千人)。 因此，方案所覆盖的总人口数可以简单的表示为： 故整个模型可写为 综上分析可知，这是一个典型的约束条件下的整数规划模型。 六、模型求解： 本模型可以归为整数规划问题中的0-1规划问题。目前0-1规划问题没有能够完全应用于任意类型的计算。我们知道线性规划问题的最优解能在其可行域边界上达到。而非线性规划问题最优解（如果存在）则可能在其可行域中任意点达到。而就本模型分析，这是一个一维模型，且数据量相对较小，所以我们选用了隐枚举法来解出模型的解。 在已知的总成本为一亿元内的限定条件下，使成本得到充分的利用，覆盖尽可能多的人口。由表1 表1：每个位置的建造费用（单位：百万元）和覆盖社区 位置 1 2 3 4 5 6 7 费用 18 13 40 35 38 26 21 覆盖社区 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                 可知，在一亿元条件内可建设3到4个基站，总共有 在一维模型中，可以利用程序，在这70种情况中快速的寻找到最合理的优化解，使 同时，我们也注意到在 的情况中，必须满足成本约束条件： 七、算法程序的主要步骤： Step1：在只建设三个基站的条件下，选定建设的基站为1,2,3，并计算出这种方案的总花费，倘若总花费低于一亿元，则计算出该方案覆盖的总人口数量m，假设m为覆盖人口数量的最大值。把方案序号值n赋为1。 Step2：按预先设定好的顺序循环，选取到下一个方案。 Step3：计算出这种方案的总花费，若总花费大于一亿元，则重复step2；若总花费小于等于一亿元，则计算出该方案的总覆盖人口，将之与m比较，若小于m，则重复step2；若大于m，则将这个方案的总覆盖人口数量赋值给m；并将该方案序号赋值给n。 Step4：当全部循环完成后，停止，根据方案序号值n，找到对应的基站建设方案，m为其对应的覆盖人口数量。 Step5：在建设4个基站的条件下，初始方案定为建设1,2,3,4基站，方法与上述步骤相同。 得出结果后，比较建设3个基站和建设4个基站所覆盖人口的最大值，得出该模型的最优结果。 通过隐枚举比较程序（程序略）可以快速得到答案： 建设2，4，6，7号基站，总共花费9500万，覆盖人口109千人。 八、第二问模型建立与分析： 经过实地调查与研究，工程师发现某些基站的覆盖范围并不是局限在邻近的几个社区，如1基站除完全覆盖1,2,4社区外还能覆盖5社区的一部分。因此，联系实际情况，我们做出了一些合理的假设：每个基站的信号传播呈近似辐射状圆形分布，并且每个社区内各处的人口密度相等。在这个假设的基础上结合所给的基站在社区位置分布图，我们可以大致建立个基站在未相邻社区内的不完全覆盖模型。 基站 覆盖情况 1 2 3 4 5 6 7 完全覆盖 不完全覆盖                 类似于问题一的分析，我们可以建立一个约束条件下的整数优化模型。 根据以上表格，建立反映基站社区覆盖范围的矩阵，       （0 1） 如 =[1  1  0  1  0.3  0  0  0.1  0  0  0  0  0  0  0 ]; =[0  1  1  0.1  1  0.4  0  0  0  0  0  0  0  0  0 ]; 令 A = [ ] 分以下三种情况： 1 =0      ，表示社区未被覆盖 2       ，表示社区被完全覆盖 3   ，表示社区被覆盖了一部分 但是我们仔细分析后发现，若根据已得到的数据建立最优方案，则可能会出现一个社区被两个或两格以上基站不完全覆盖，而两基站的不完全覆盖区域又发生重叠的情况。在用上述方法计算时会因为累加系数而导致结果偏大。下面我们重点分析覆盖区域重叠的问题。 由表格可知，总共有3种可能重叠的情况，即1基站和6基站都覆盖第8社区，2基站和5基站都覆盖了第6社区，1基站3基站和5基站都覆盖了第5社区，我们对此进行逐一分析。 根据问题一的模型和求解，我们能够计算出问题一条件下的最优方案为选择建造2、4、6、7基站，在此方案下送覆盖的总人口为109千人。而如果某些基站除完全覆盖的社区外，能不完全覆盖其他社区的一部分，那么在此条件下建立的最优方案得到的解不应小于109千人，基于该分析可以对覆盖重叠问题进行化简。 ①若方案中包含了1基站和6基站，则两站能分别覆盖8社区人口的10%和30%，设两区域重叠区域人口占8社区总人口为a(0＜a≤10%)，如果重叠的情况发生，则说明没有哪个基站能完全覆盖8社区，因而排除3、4、5基站，此时方案为1、2、6、7基站。 总成本S=18+13+26+21=78(百万元) 总人口N=117-26+(0.1+0.3-a×12)+0.4×10=99.8-12a＜109 因而此方案不是最优解 ②若方案中包含了2基站和5基站，要想在社区6发生重叠。则不能包含基站4，除2和5基站外其它只能在1、3、6、7基站中选择，若选择3基站则1亿元的费用将不足以再建造1、6、7基站，但此时覆盖人口并不是最大。若基站只在1、6、7中选择，则公邮3个方案，即2、5、1、6基站，2、5、1、7基站，2、5、6、7基站。经计算，3个方案均不是最优，因此排除这种可能。 ③若方案包含了1、3、5基站，要想在5区重叠，则不能包含基站2、4.此种情况下不能完全包含社区3，而社区3总人口为13千人，故该方案不是最优。 综上所述，该模型独立分析可不考虑覆盖重叠的情况，而只需对各个基站在社区的分布独立分析。 我们定义一种新的数学函数 fun(x)= 故，该问题的解为 模型表示成 九、问题二模型的求解： 根据上面的分析，及所建立的模型。可以将基站的不完全覆盖地区的人口计入到基站方案覆盖人口的总数当中去，在建立的模型中，全面的分析了基站不完全覆盖的影响，及不同基站间的不完全覆盖的重叠，所个结果更为精确。在解模过程中，定义一种函数运算，并将基站不完全覆盖地区的人口计入到总数当中，这种影响被视为一种系数而融合到模型当中，简化了计算过程。只需在原有的步骤当中，对各种基站建设方案按其不同的不完全覆盖添加一定的系数。在解模程序中，只需加入比较系数影响的逻辑，模型仍为一维模型，且数据量仍很小，故隐枚举法求解速度依旧很快。得出的解仍是建设2,4,6,7基站。只是在不完全覆盖的影响下，这种方案的覆盖总人口数有了增加。 问题二模型的求解结果 问题二模型求解结果 待定点位置 基站设置情况 0 1 0 1 0 1 1 覆盖人数 109.6千人 95百万元                 相比于问题一的模型，问题二模型在原有基础上考虑了基站不完全覆盖对覆盖总人口数的影响。对应问题一模型的最优化解，建设2,4,6,7基站，原本就已经完全覆盖了除1,4社区外的全部社区，所以，在问题二模型中，这种方案实际只增加了2号基站在4社区10%的不完全覆盖，只增加了0.6千人的覆盖人口数量。但它依然是问题二模型的最优化解。 十、模型的优缺点及改进： 1优点： 在模型的建立过程中，我们用了线性代数和整数规划的知识，简洁地对实际问题构造了一种数学模型。该模型可以用于一般基站选址的设计。在建模的过程中，我们充分的发挥了计算机的功能，行之有效地获得了最优解。另外，该模型的人为假设少，能比较准确地反映出实际情况，模型求解时充分考虑了准确性和科学性，引入了矩阵的思想方法，有创新性，使模型更加简洁、直观，可靠性好。 2不足： 在算法设计中，我们采用了隐枚举法。这是考虑到涉及的基站及社区数目较少，该法必定能找到最佳组合，且运算量也不大。但作为一般算法，若实际问题规模扩大，则运算量将会急剧增大。 3改进方向： 在实际问题中，基站选址问题考虑的因素将更多，模型将相当复杂。而本题仅考虑了固定位置的基站选择使覆盖尽可能多的人口。然而在实际中，我们也不能忽视地形、气候及周围环境的影响。另外，本模型仅仅考虑了总成本上限值的约束，而在现实生活中，开发商往往很重视经济效益，以期在覆盖到尽可能多的人口的前提下，尽量降低投入成本，此时，该模型将演变为一个多目标规划问题。 另一方面，在本题的选址规划中，忽略了基站“电磁辐射”对某一社区的人民群众及环境的影响。事实上，如果两个或两个以上基站的覆盖范围发生重叠，则在重叠的社区辐射量将会成倍地增大。这样不仅造成资源的浪费，还产生较为严重的电磁污染。因此，我们对已建立的模型进行优化。  我们引入参考因子 ，表示对电磁辐射的重视程度。 则： 模型为： 十一、模型优化思考： 在之前的建模过程中，我们发现不同基站的建造费用不同，覆盖人口数量也不同，同时，每个基站的性价比（即单位百万元的人口覆盖数量）也有区别。所以，我们试图从性价比角度建立模型，从而更直观迅速的找到符合条件的最优化解。 在一亿元的资金限定条件下，可知，当总花费相同时，所选方案的性价比越高，则方案覆盖的人口数量就越大。同时，在实际问题中，性价比也更有意义。据下表 表：每个建设基站覆盖人口和性价比 位置 1 2 3 4 5 6 7 费用 18 13 40 35 38 26 21 覆盖社区 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 覆盖人口数量 12 26 37 35 36 45 32 性价比 0.67 2 0.925 1 0.9474 1.7308 1.5238                 由上表可以清晰的看出不同基站性价比的区别。单就1,2俩个基站进行分析，1基站性价比低的太多，所以在花费比2基站还高的情况下其人口覆盖能力却不及2基站的50%。这是由不同地区的人口分布差异决定的。因此，就单个基站的情况，我们可以得出结论，建设性价比高的基站更容易完成覆盖尽可能多的人口的这个目标。所以，我们可以运用贪心算法，按照各个基站的性价比高低顺序依次建设，直至达到一亿元的资金上限。这样可以保证建设的基站都是高性价比的基站。 但是，倘若在多基站建设的情况下，由于不同基站间的重复地区覆盖，最后方案的总性价比将不会是各个基站性价比的简单加权运算。在之前求性价比的过程中，已经把地区的概念模糊了，所以，在分析不同基站的地区重复覆盖时就会比较困难，如果返回地区概念再寻找这种重复覆盖对性价比的影响就会使建造的模型比较复杂，并且也会使性价比概念的提出失去意义。 但是，我们仍然认为性价比的概念在这个模型的检验中是很有实际意义的。思考性价比的方式，在模型检验中可以作为一种比较有效的辅助方法。 就这道题而言，运用之前的问题一模型，可以求解出最优方案为建设2,4,6,7基站。倘若把性价比模型作为一种检验方法，不难发现，2,4,6,7，恰好是性价比最高的4个基站。然后，考虑到这4个基站间的覆盖地区的重叠，我们仍需检验方案总的性价比。经计算，可得出该方案的总性价比为1.147千人/百万。再观察选建的基站只有基站4的性价比为1，低于该总性价比值。因此只需再检验基站4的合理性。在已建造2,6,7,基站的基础上，可以列表比较其余基站对于方案覆盖总人口的影响。 表：其余基站对于方案覆盖总人口的影响 位置 1 3 4 5 费用 18 40 35 38 覆盖社区 1,4 4 ,8 6,8,9 8,9 覆盖人口数量 8 18 26 22           对照数据表，很容易发现，在已选2,6,7基站的情况下，选择建设4基站时，方案的覆盖人口最多。所以，可以得出结论：建设2,4,6,7基站的方案是符合题意的最优化解。 性价比的概念，在进行模型检验时，可以提升速度，并增加检验的准确性。 十二、参考文献 [1]朱道元等.数学建模案例精选.北京：科学出版社，2003 [2]谭浩强.C语言设计.北京：清华大学出版社，2005 [3]姜启源.数学模型.北京：高等教育出版社，1993 附录文件 文件一 问题一模型求解C++程序： #include "iostream.h" unsigned long chos;  //社区 int i,j,pop[15]={2,4,13,6,9,4,8,12,10,11,6,14,9,3,6}; int max=0,coo;  //coo为建造的社区对应为位所化的十进制数 unsigned char temp,tnum; int ptemp,ftemp,t=0; class soc  //基站类 { public: int fee; unsigned long cs;  //社区 }c[7]; int main() { c[0].fee=18;c[1].fee=13;c[2].fee=40;c[3].fee=35;c[4].fee=28;c[5].fee=26;c[6].fee=21; c[0].cs=11;c[1].cs=22;c[2].cs=712;c[3].cs=432;c[4].cs=2432;c[5].cs=20032;c[6].cs=30720;  //社区表示为位以后化成的十进制数 for(i=0;i<128;i++) { chos=0; tnum=0; temp=i; ftemp=0; for(j=0;j<7;j++) { if(temp&0x1==0x1) { tnum++; ftemp+=c[j].fee; } temp=temp>>1; } if((tnum==3||tnum==4) && ftemp<=100) { temp=i; for(j=0;j<7;j++) { if(temp & 1==1)chos|=c[j].cs; temp=temp>>1; }  ptemp=0; for(j=0;j<15;j++) ptemp+=pop[j]*( (chos>>j) & 1); if(ptemp>max) { max=ptemp; coo=i; } } } 文件二 问题二模型C++程序： include "iostream.h" int i,j,k,coo; float lmd[7][15]={{1,1,0.2,1,0.5,0,0,0.2},{0,1,1,0,1,0.5},{0,0,0,1,0.5,0,1,1,0,1,0,0.2},{0,0,0.5,0,1,1,0,1,1},{0,0,0,0,0,0,0,1,1,0.5,0,1},{0,0,0,0,0,0,1,0.4,0,1,1,1,0,0,1},{0,0,0,0,0,0,0,0,0.5,0,0,1,1,1,1}}; float max=0.0,lpop[15]={0},pop[15]={2,4,13,6,9,4,8,12,10,11,6,14,9,3,6};  //coo为建造的社区对应为位所化的十进制数 unsigned char temp,tnum; float ptemp,ftemp; void fuzhi(); class soc  //基站类 { public: int fee; unsigned long cs;  //社区 }c[7]; int main() { fuzhi(); for(i=0;i<128;i++) { tnum=0; temp=i; ftemp=0; for(j=0;j<15;j++)lpop[j]=0; for(j=0;j<7;j++) { if(temp&0x1==0x1) { tnum++; ftemp+=c[j].fee; } temp=temp>>1; } if((tnum==3||tnum==4) && ftemp<=100) { temp=i; for(j=0;j<7;j++) { if(temp & 1==1) { for(k=0;k<15;k++) if(lmd[j][k]>lpop[k])lpop[k]=lmd[j][k]; } temp=temp>>1; }  ptemp=0; for(j=0;j<15;j++) ptemp+=pop[j]* lpop[j] ; if(ptemp>max) { max=ptemp; coo=i; } } } cout<<"pop="<