选址问题数学模型摘要本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立 3 个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题针对问题 1：0-1 规划的穷举法模型。该模型首先采用改善的 Floyd-Warshall 算法计算出城市间最短路径矩阵见附录表一；然后，用 0-1 规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在 Q、W、M 社区，各社区居民缴费区域见表 7-1，居民与最近的缴费点之间平均距离的最小值 11.7118 百米。针对问题 2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的 Floyd 算法，运用 LINGO 软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是 2.5 千米。最后采用就近归组的搜索方法，逐步优化，最终得到最少需要设置 3个派出所，其所在位置有三种方案，分别是：(1)K 区，W 区，D 区；(2) K 区，W 区，R 区；(3)K 区，W 区，Q 区。最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择 K 区，W 区，Q 区，其各自管辖区域路线图如图 8-1。针对问题 3：建立了双目标最优化模型。首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径 Floyd 算法，并用 MATLAB 和 LINGO 软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为 11.8km、11km 和 12.5km，三组巡视的总路程达到 35.3km，路程均衡度为 12%,具体巡视路线安排见表 9-1 和图 9.2。关键词Floyd-Warshall 算法穷举法最小生成树最短路径1 问题重述1.1 问题背景这是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社111111111I11221W15211121212①19会和军事意义。1.2 问题的提出实际问题：某城市共有 24 个社区 A...
