青岛科技大学高密校区c题服务网点选址问题.doc

青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛 承 诺 书 我们仔细阅读了青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 所属学院（请填写完整的全名）： 青岛科技大学 高密校区 信息科学技术学院 参赛队员 1. 李继旭 信息科学技术学院 软件技术专科 2. 王明之 信息科学技术学院 软件技术专科 3. 王飞 信息科学技术学院 软件技术专科 (备注参赛队员书写格式：姓名+学院+专业+联系方式+学历层次) 指导教师或指导教师组负责人： 王军东 日期： 2013 年 5 月 1 日 ?青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛 评 阅 专 用 页 评阅记录： 评 阅 人 评 分 备 注 青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛 题 目 C题服务网点选址问题 摘 要 本文探讨了服务网点的选址及最短路径的问题，运用多种方法分别进行讨论。 针对问题一，本文采用四种方案。方案一：将各个两两相邻村庄求得最优中介点，划定区域范围，从范围中求得最终最优重心解，将各个重心再次求其重心，得到的坐标（3.38，5.95）则为所求的服务网点的位置。方案二：将每一个村庄到其它村庄最短路径距离的加权和求出， 利用中位点选址，得出加权和最小的数值，即为网点最优选址位置 ，坐标为（3.19，7.2），即网点建在第11个村庄。方案三：由于已知各自然村人口数量，我们可以将各自然村人口数量抽象为重量，运用重心法，建立重心法选址模型，进行求解，所得的坐标为（4.03,5.63）。方案四：已知每个村庄都还有一定的居民数，则将各居民点到服务中心的距离与其人数相乘后、再求和，作为我们的目标函数。当目标函数的值取最小时，所求网点的位置就是最佳的位置，坐标为（3.60,6.51）。 针对问题二，方法一：在问题一的基础上，同样采用中位点选址法，先求出每个村庄到其他村庄最短路径距离的加权和，选出最小的两个数值，即为两个网点最佳选址位置，得到的坐标分别为（5.70，5.00），（3.19，7.20）。方法二，由于各自然村人口扩大一倍，同样将人口数量抽象为重量，运用重心法，建立多重心法选址模型进行求解，所得坐标为（3.03,6.96），（7.11,1.33），即为两个网点最有选址位置 针对问题三 采用多阶段决策问题，根据问题二方案一求得的结果，用逆序递推方法逐步求出各段到中点最短路径，两两相比较，最小的结果即最优路段，多个规划方程求得多个最短路段即为主路径，主路径与其它相近的点组合的路段变为所求的最佳行走路线。 关键词：重心法，求重心的数学公式法，中位点选址法，标号法，雷利法则，Ramsey模型，动态规划。 问题重述 某乡镇由12各主要的自然村组成，每个自然村的位置（用平面坐标x,y表示，距离单位：km)和自然村的人口数（R)如下表所示。 1 2 3 4 5 6 7 8 9 10 11 12 X 0 8.20 0.50 5.70 0.77 2.87 4.43