2015-1-A紧急医疗救护站设置问题1-8500.pdf

北京理工大学数学建模论文

题目 紧急医疗救护站设置问题

摘要

紧急医疗救护站的选址应在考虑救护车车程及覆盖人口的基础上，结合备选地地理位置以及交通状况，优化后得出合理的选址方案。

本文根据图论的相关理论，将某县交通图抽象为一张无向图。在确立53个村镇点的基础上利用道路距离信息，结合Floyd算法计算各点间的最小距离，在和距离约束条件20公里进行比较后，构建一个53×53的0-1覆盖矩阵。将人口全覆盖的要求转化为求解0-1矩阵的最小覆盖集，利用Greedy算法编写求解程序，输出相应的选址地点并进行验证。最后得出当备选地为所有村镇时，仅需9个点即可实现全覆盖，其中一种可行的9点覆盖方案为选址在｛D，26，21，Q，I，G，F，E，A｝点。

当选址条件限制在乡镇时，找出为实现全覆盖而必须选择的地点作为“确定点”，并以“确定点”为中心，在20公里范围内搜寻出其覆盖区域，以覆盖区域最小重叠为原则搜寻下一“中心点”，遍历得出选址在｛D，A，Q，O，N，J，I，G，F，E｝的一种10点覆盖方案。

在初始车辆数有限的条件下，将0-1矩阵的权重替换为各地人口总数，采用程序有限步运行，求解出额定个数选址地点，并求和确定覆盖人口总数。当初始车辆为10辆时，已求解出的两种方案均满足要求。当初始车辆数为7时，将程序运行7步后得出选址在｛D，O，30，9，N，J，A｝可以覆盖48个点，覆盖人口总数为29.46万，覆盖率为96.88%。

最后，对得出的方案进行分析，考虑地理位置和方案实际运行情况，对减少选址重叠区域的选址点提出建议，优化结论。

本文结合理论计算结果和实际选址情况，对不同要求下的紧急医疗救护站设置提供了多套方案，有效的解决题目问题，切实可行。

关键词

选址问题 Floyd算法 Greedy算法 最小覆盖集 递归算法 最小距离问题

北京理工大学数学建模论文

一、问题重述

在经济社会中，如何提升效率以达到节约时间、增加效益已成为人们日益关注的重点。在公众卫生领域，尤其是医疗资源相对匮乏的乡镇，可以通过增设紧急医疗救护站的方式，使得全县任何地方有病人时救护车可以短时间内到达现场，从而尽可能满足全县人民的急诊转运需求。

在紧急救护站的选址设计问题中，应考虑救护车到达全县各地的时间。保证救护车20分钟内可以到达各地的基础上，结合实际情况，在不同的初始条件下进行分析讨论： 1、假定救护车数量充足，以覆盖全县村镇为基本要求，尽可能通过优化选址来减少紧急救护站的设立。并对各村庄及乡镇均可建立和仅能在乡镇建立的两种情况进行讨论，给予不同的选址方案。

2、在救护车数量有限的情况下，结合各个村镇的实际人口情况进行分析，以覆盖尽可能多的人口为要求进行选址。在10辆车和7辆车两种不同的初始条件下给予不同的方案，并就每种方案满足的人口覆盖情况进行说明。

二、问题分析

2.1 问题一：以覆盖全部人口为目标的选址分析

首先，在村镇均可建立紧急救护站的条件下，把53个点之间的位置关系抽象成一张无向图，并在各点距离关系的基础上构造出一个53×53的矩阵进行分析。采用Floyd算法求出个点间最小距离矩阵后，和20公里这个条件进行比较，通过运算将其变形为0-1矩阵，利用Greedy算法编写程序求解出其覆盖集，并转化为相应的选址点得出结论。

当条件限制在仅能在乡镇选址时，仅需对18个点进行选址。此时在为满足全覆盖而必须选址的“确定点”基础上，利用递归算法进行分析，得出相应的方案。 2.2 问题二：以满足覆盖尽可能多的人口为目标的选址分析

和问题一类似，仍然利用矩阵进行讨论。由于第一问已经将20分钟车程这一约束条件转化为0-1矩阵，故本问仅需在该矩阵的基础上将其权重修改为各地人数，以满足覆盖尽可能多人口的条件。

对于初始车辆数为10和为7的两种情况，先和问题一计算出的车辆数进行分析比较，若全覆盖的车辆数少于所给初始车辆数，则可以直接采用之前的方案实现题目要求。若车辆数不能满足全覆盖的条件，则通过调整求解最小覆盖集程序的运行次数，找出额定个对应点。并结合各地人口分布情况，计算出人口覆盖总数，从而得出结论。

北京理工大学数学建模论文

三、基本假设

1、各村镇之间的路况良好，救护车出诊时在20分钟内可以行驶20公里。

2、在各紧急救护站未重叠的救护范围内，同一时间同一救护站最多仅有一例病例需要救护。

3、邻县村可以通过救护车，但不在救护站的选址考虑范围和医疗救助范围之内。 4、救护车救援过程中不会发生故障。

四、符号说明

五、模型的建立及求解

5.1 最小覆盖集模型 5.1.1 模型说明

由问题分析可知，救护站的设置方案要尽量满足下列两点要求：

1、在全县范围任何地方有病人时，救护车能够在20分钟内到达救援地点，也就是救护站的救援半径为20公里。

2、救护站的设置数量最少。

由此考虑将全县地图抽象为图论模型，并按照下述步骤求解： 1、建立53 53的矩阵来表明交通图上每两点之间的距离关系。

2、利用Floyd算法求解出每个点和其他点之间的最小距离，并填入矩阵相应位置。 3、和20公里进行比较，通过矩阵的运算将其转化为0-1矩阵。

4、利用Greedy算法，每一次取得与其他点关联最多的局部最优解，得到全局最优

北京理工大学数学建模论文

解。

5、记录输出结果，即为一个可行的选址方案。 5.1.2 模型建立

第一步：

构建53 53的矩阵A，其中位于矩阵第i行第j列的元素记为A（i,j）。 其中记1-18点表示乡镇A-R,19-53点表示村庄1-35。

(1) 由于行列的位置关系是相互的，所以可知此矩阵对角线元素均为0，其余元素以对角线为轴对称分布，表示的是交通图上点与点最直观的位置和距离关系。 第二步：

采用Floyd算法，求解出每个点和其他点之间的最小距离。 算法如下：

① 首先确定寻找最短到达距离的两点i和j，初始时刻两点最短到达距离满足：

Lmin(i,j)=L(i,j) （2）

② 在i和j两点间依次插入k、l、m三点，如果存在关系：

Lmin(i,j) L(i,k) L(k,l) L(l,m) L(m,j) （3） 则令：

（4）

因为图上没有三段以上路程加起来在20公里以内的，故可以认为符合条件的起点终点之间至多有3个点，故此处用三点插入进行遍历。

③ 反复重复操作②，直至k、l、m均遍历完所有的点，重复该操作共计53 53 53次。

④ 回到操作①重新开始，直至所有不同的L(i,j)均经历过操作②，重复操作①共计53 53次。

⑤ 由此得到最小距离矩阵X：

X Lmin（i,j）|i 1,2， ，53，j 1,2， ，53）}

（5） 第三步：

构造如下矩阵：

20　…　…　…　20 20　… 20　… 20 Y …　…　20　…　…

20　… 20　…　20 20　…　…　…　20 （6） Y为所有元素均为20的53 53矩阵，将X和其进行做差运算，得出0-1矩阵Z：

(7)

第四步：

为寻找出Z矩阵的最小覆盖集，也即其全局最优解，利用Greedy算法寻找出每一

北京理工大学数学建模论文

次的局部最优解，逐步修改矩阵直到输出最小覆盖集。

算法如下：

①由Z矩阵的来源可知，若Z(i,j) 0，说明实际二 …… 此处隐藏：8437字，全部文档内容请下载后查看。喜欢就下载吧 ……