中心医院选址问题

中心医院选址问题

作者 曹彦杰 学号 200807011203 单位：中国石油大学胜利学院

信息与计算科学系 信息与计算科学专业08级2班

摘 要 运用Dijkstra法解决选址问题

一、问题提出

某地区打算建立一中心医院，已知某地区的交通网络如图,其中点代表居民小区，边代表公路，权值为小区间公路距离，为了使各个小区的居民看病最方便，即使离医院最远的小区居民就诊时所走的路程最近，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？

v1310

v34v55934v6

6510 v2v46v8v7二、基本方法

本算法是由E.W.Dijkstra于1959年提出的，可用于求解指定两点s和t间的最短路和指

vv定点s到其余各点的最短路。对于所有的wij优方程，即d(vi,vj)v?0，由动态规划的最优化原理可以得到最

,记

?min{d(vs,vj)?wij},对于i?Vwii?0；对于

i?j，若vij?E,记wij??。由于Dijkstra提出了在所有算出的最短路的权值中，

挑选最短的一个作为从s到该点的最小权值，这就使得本算法的运算量比动态规划算法有所减少，Dijkstra算法被公为目前求无负权网络最短路问题的最好方法。

具体做法是：对所有的点采用两种标号，即T标号和P标号，T标号即临时性标号,P标号为永久性标号。给i一个P标号，用标号即不再改变。给i一个T标号，用

vvP(vi)表示，vs到vi估计的最短路的上界，vi的T(vi)表示，是指vs到vi点估计的最短路的一个

v上界，是一种临时性标号。凡是没有得到P标号的点都是T标号。算法的每一步都把某一点的T标号变为P标号，当终点t得到P标号时，全部计算结束。对于p个顶点的图，最多经过p-1步计算，就可以得到从始点到各点的最短路。 计算步骤如下：

（1） 给始点i以P标号，

vvP(vi)?0，其余各点以T标号P(vi)??,i?1。

（2） 从上次P标号的点i出发，考虑与之相邻的所有的T标号点

vvj，

(vi,vj)?A，对vj的标号做以下运算比较：

点）。

（3） 比较以前过程中剩余的所有具有T标号的点，把最小的T括号中对应点

号改为P标号：

T(vi)?min{T(vj),p(vi)?wij}，（j为与i相邻的且为T标号的

vj的标

P(vj)?min[T(vj)]。

（4） 若所有的点均已为P标号，则计算停止，否则回到（2）步骤。

三、问题分析

从v1-v8八个代表居民小区的点中选择一个点vi（i=1,2…8）即一个小区建立中心医院，使得离vi距离最大的点到vi的距离最小。

四、模型假设

各居民点的居民到中心医院时选择路线都为最短路线。

五、符号说明

Aij 居民点vi到居民点vj的距离 Xij 居民点vi到居民点vj的最短距离

Zi 以居民点vi为出发点到各居民点的最短距离中的最大距离

Y 表示中Zi的最小值

六、模型建立

分别以v1-v8为出发点，用图论中的求最短路的算法（Dijkstra法）求个点到出发点的最短距离，选其最大值作为的Zi值，再在Zi中选取最小值，得出最终解。

七、模型求解

1. 以v1为出发点

i=0：令S0?{v1}，P（v1）=0,； i=1：（1）T（v2）=3，T（v3）=10，

（2）标号中T（v2）最小，令P（v2）=3，S1?{v1v2}；

i=2：（1）T（v3）=10，T（v4）= P（v2）+A24=3+5=8，

（2）标号中T（v4）最小，令P（v4）=8，S1?{v1v2v4}；

i=3：（1）T（v3）=10，T（v5）= P（v4）+A54=8+4=12，T（v7）= P（v4）+A47=8+10=18，

（2）标号中T（v3）最小，令P（v3）=10，S1?{v1v2v4v3}；

i=4：（1）T（v5）=12，T（v7）=18，

（2）标号中T（v5）最小，令P（v5）=12，S1?{v1v2v4v3v5}；

i=5：（1）T（v7）=min{18, P（v5）+A57=12+5=17}=17，T（v6）= P（v5）+A56=12+9=21， （2）标号中T（v7）最小，令P（v7）=17，S1?{v1v2v4v3v5v7}；

i=6：（1）T（v6）= min{21, P（v7）+A67=17+3=20}=20，T（v8）= P（v7）+A78=17+6=23, （2）标号中T（v6）最小，令P（v6）=20，S1?{v1v2v4v3v5v7v6}； i=7：（1）T（v8）= min{23, P（v6）+A68=20+4=24}=23,

（2）标号中T（v8）最小，令P（v8）=23，S1?{v1v2v4v3v5v7v6v8}； 所以Z1=Max{ P（vi）；i=1-8}=23；Y=23 2. 以v2为出发点

i=0：令S0?{v2}，P（v2）=0,； i=1：（1）T（v1）=3，T（v4）=5，

（2）标号中T（v1）最小，令P（v1）=3，S1?{v1v2}；

i=2：（1）T（v3）=13，T（v4）=5，

（2）标号中T（v4）最小，令P（v4）=5，S2?{v1v2v4}；

i=3：（1）T（v3）=11，T（v5）= 9，T（v7）=15，

（2）标号中T（v5）最小，令P（v5）=9，S3?{v1v2v4v5}； i=4：（1）T（v3）=11，T（v7）=14，T（v6）=18,

（2）标号中T（v3）最小，令P（v3）=11，S4?{v1v2v4v3v5}； i=5：（1）T（v7）=14，T（v6）= 18，

（2）标号中T（v7）最小，令P（v7）=14，S5?{v1v2v4v3v5v7}； i=6：（1）T（v6）= 17，T（v8）=20,

（2）标号中T（v6）最小，令P（v6）=17，S6?{v1v2v4v3v5v7v6}； i=7：（1）T（v8）=20,

（2）标号中T（v8）最小，令P（v8）=20，S7?{v1v2v4v3v5v7v6v8}； 所以Z2=Max{ P（vi）；i=1-8}=20；Y=Min{Z1Z2}= Min{23 20}=20 3. 以

v3为出发点

i=0：令S0?{v3}，P（v3）=0,； i=1：（1）T（v1）=10，T（v4）=6，

（2）标号中T（v4）最小，令P（v4）=6，S1?{v3v4}；

i=2：（1）T（v1）=10，T（v2）=11，T（v5）=10，T（v7）=16，

（2）标号中T（v1）最小，令P（v1）=10，P（v5）=10，S2?{v3v4v1v5}；

i=3：（1）T（v2）=11，T（v6）=19，T（v7）=15，

（2）标号中T（v2）最小，令P（v2）=11，S3?{v3v4v1v5v2}； i=4：（1）T（v6）=19，T（v7）=15,

（2）标号中T（v7）最小，令P（v7）=15，S4?{v3v4v1v5v2v7}； i=5：（1）T（v6）= 18，P（v8）=21

（2）标号中T（v6）最小，令P（v6）=18，S5?{v3v4v1v5v2v7v6}； i=6：（1）T（v8）=21,

（2）标号中T（v8）最小，令P（v8）=21，S6?{v3v4v1v5v2v7v6v8}； 所以Z3=Max{ P（vi）；i=1-8}=21；Y=Min{Z1Z2Z3}= Min{23 20 21}=20

4. 以v4为出发点

i=0：令S0?{v4}，P（v4）=0,；

i=1：（1）T（v2）=5，T（v3）=6，T（v5）=4，T（v7）=10，

本文来源：https://www.bwwdw.com/article/t3wg.html