消防队选址

消防队建设规划

摘要

本题为规划问题，由于各乡镇均申请在各自所在地建设新消防队，新建消防队数目有限，县镇府应考虑全局最优，本文根据不同的条件及需求，建立模型，进行全局规划，完善的解决了问题。

问题一：

针对问题一，在乡镇中选择最优地址建立另一个消防队，（1）我们选择floyd算法（附录1），用matlab求出任意两个乡（镇）或村之间的最短距离；（2）构建消防站集合，利用mindistance函数（附录2）求出从消防站集合到各乡镇、村的最短距离和集合，其中最小值即为最短距离，对应的序列号即为消防站最优建立地点。我们求得发生火灾就近动用一个消防队的情况下新建消防队的最佳地址为j乡（镇）。

问题二：

问题二的最优解依然为使消防站集合到各地距离和最短，但是问题二提出各地发生火警的概率不同，且区分大小火，由于大火需要调动两个消防站，所以问题的解需要对路程进行加权，同时需要考虑的是在发生大火时，距离为两个消防站到火灾地点的距离和，再进行加权，（1）根据题目算出各地在火势不同的情况下调动消防队的概率；（2）用得出的概率对在每个乡镇村建立的消防队在各处发生两种火灾时所走的最短路程进行加权，最短距离依然为最优解，该点即为建立消防队的最佳地址。解得到的最优选址地点依然为j镇。

问题三：

由于问题二我们已经进行了完整的编程，其基础思想是进行概率加权。只是

在本题中，我们需要考虑在发生大火时在三个消防队中调用就近的两个来进行灭

火，延用问题一的基本思想；依次取两个待定消防点与县府（o点）到每个点的最短距离做比较，总是取三者中较短两个的距离然后依次相加，得出在任意两个乡镇村建立消防队时，每一个点发生火灾调用两个消防队所要走的最短路程，再在这些最短距离中选取最小数值，即每一个地点发生火灾就近动用两个消防队的最短路程。然后我们再用问题二的思想，用每一处发生各种火灾的概率对其进行加权，就可得在任意一处发生两种火情的情况下消防队到达该点总的最短路程。然后在问题二程序的基础上做出一些改动，即可用matlab实现本题的思路，得出结论序号为g、k的乡镇为最合适的消防队建址。

问题四：

问题四要求建立最少的消防站覆盖全县，我们选择集合覆盖模型来确定在满足所有需求点的前提下，需增加消防站的最少数目。用lingo软件（程序见附录5）算出新建消防站点为e，f，k，q四个乡镇可满足新建最少的消防站点并确保消防队能在三十分钟内赶到火灾现场。

关键词：选址，floyd算法，概率加权，集合覆盖模型，0-1覆盖矩阵

一、问题重述