中心医院选址问题摘要本篇论文对选址问题进行了较为全面的介绍。
内容包括中心医院选址的模型及其建立。
针对中心医院选址的一般要求,,结合中心医院选址实例，运用所建立的混合整数规划模型确定中心医院选址最佳方案运用Floyd法解决选址问题关键字：运筹学；选址；中心医院一、提出问题图论是数学的一个分支, 它以图为研究对象.图论中的图是由若干给定的点及连接两边所构成的图形, 用连接两点的边表示相应两个事物间具有某种特定关系。
在社区医院的选址问题中, 点表示社区主要居民小区, 而其间的连线(边)则表示小区距离。
图论中的最短路径算法包括指定的顶点对之间的最短路径算法和全部顶点间的最短路径算法.前者可用具体患者就医路径的合理化决策分析, 而后者很适合于社区医院的选址, 使得整个社区患者总的就医路径最短。
二、问题分析题中要求在该地区的交通网络图中，从1v -8v 代表八个居民小区的点中选择一个点i v （i=1,2…8）即一个小区建立中心医院，使得离i v 距离最大的点到i v 的距离最小。
三、模型假设1.假设医院与居民点的距离为直线距离2不考虑各小区的实际尺度，简化为点处理四、符号说明A ij 居民点i v 到居民点j v 的距离 X ij 居民点i v 到居民点j v 的最短距离Z i 以居民点i v 为出发点到各居民点的最短距离中的最大距离Y表示中Z i 的最小值1v 2v 45v 6v 78v 103五、建立模型分别以v-8v为出发点，用图论中的求最短路的算法（Dijkstra法）1求个点到出发点的最短距离，选其最大值作为的Z i值，再在Z i中选取最小值，得出最终解。
六、模型求解1. 以v为出发点1i=0：令=S{1v}，P（1v）=0,；i=1：（a）T（v）=3，T（3v）=10，2（b）标号中T（v）最小，令P（2v）=3，=1S{1v2v}；2i=2：（a）T（v）=10，T（4v）= P（2v）+24A=3+5=8，3（b）标号中T（v）最小，令P（4v）=8，=1S{1v2v4v}；4i=3：（a）T（v）=10，T（5v）= P（4v）+54A=8+4=12，T（7v）3= P（v）+47A=8+10=18，4（b）标号中T（v）最小，令P（3v）=10，=1S{1v2v4v3v}；3i=4：（a）T（v）=12，T（7v）=18，5（b）标号中T（v）最小，令P（5v）=12，=1S{1v2v4v3v5v}；5i=5：（a）T（v）=min{18, P（5v）+57A=12+5=17}=17，T（6v）=7P（v）+56A=12+9=21，5（b）标号中T（v）最小，令P（7v）=17，=1S{1v2v4v3v5v7v}；7i=6：（a）T（v）= min{21, P（7v）+67A=17+3=20}=20，T（8v）=6P （7v ）+78A =17+6=23,（b ）标号中T （6v ）最小，令P （6v ）=20，=1S {1v 2v 4v 3v 5v 7v 6v }； i=7：（a ）T （8v ）= min{23, P （6v ）+68A =20+4=24}=23,（b ）标号中T （8v ）最小，令P （8v ）=23，=1S {1v 2v 4v 3v 5v 7v 6v 8v }； 所以1Z =Max{ P （i v ）；i=1-8}=23；Y=232. 以2v 为出发点i=0：令=0S {2v }，P （2v ）=0,； i=1：（a ）T （1v ）=3，T （4v ）=5，（b ）标号中T （1v ）最小，令P （1v ）=3，=1S {1v 2v }；i=2：（a ）T （3v ）=13，T （4v ）=5，（b ）标号中T （4v ）最小，令P （4v ）=5，=2S {1v 2v 4v }；i=3：（a ）T （3v ）=11，T （5v ）= 9，T （7v ）=15，（b ）标号中T （5v ）最小，令P （5v ）=9，=3S {1v 2v 4v 5v }； i=4：（a ）T （3v ）=11，T （7v ）=14，T （6v ）=18,（b ）标号中T （3v ）最小，令P （3v ）=11，=4S {1v 2v 4v 3v 5v }； i=5：（a ）T （7v ）=14，T （6v ）= 18，（b ）标号中T （7v ）最小，令P （7v ）=14，=5S {1v 2v 4v 3v 5v 7v }； i=6：（a ）T （6v ）= 17，T （8v ）=20,（b ）标号中T （6v ）最小，令P （6v ）=17，=6S {1v 2v 4v 3v 5v 7v 6v }； i=7：（a ）T （8v ）=20,（b ）标号中T （8v ）最小，令P （8v ）=20，=7S {1v 2v 4v 3v 5v 7v 6v 8v }； 所以2Z =Max{ P （i v ）；i=1-8}=20；Y=Min{1Z 2Z }= Min{23 20}=203. 以v为出发点3i=0：令=S{3v}，P（3v）=0,；i=1：（a）T（v）=10，T（4v）=6，1（b）标号中T（v）最小，令P（4v）=6，=1S{3v4v}；4i=2：（a）T（v）=10，T（2v）=11，T（5v）=10，T（7v）=16，1（b）标号中T（v）最小，令P（1v）=10，P（5v）=10，1S{3v4v1v5v}；=2i=3：（a）T（v）=11，T（6v）=19，T（7v）=15，2（b）标号中T（v）最小，令P（2v）=11，=3S{3v4v1v5v2v}；2i=4：（a）T（v）=19，T（7v）=15,6（b）标号中T（v）最小，令P（7v）=15，=4S{3v4v1v5v2v7v}；7i=5：（a）T（v）= 18，P（8v）=216（b）标号中T（v）最小，令P（6v）=18，=5S{3v4v1v5v2v7v6v}；6i=6：（a）T（v）=21,8（b）标号中T（v）最小，令P（8v）=21，=6S{3v4v1v5v2v7v6v8v}；8所以Z=Max{ P（i v）；i=1-8}=21；Y=Min{1Z2Z3Z}= Min{23 20321}=204. 以v为出发点4i=0：令=S{4v}，P（4v）=0,；i=1：（a）T（v）=5，T（3v）=6，T（5v）=4，T（7v）=10，2（b ）标号中T （5v ）最小，令P （5v ）=4，=1S {4v 5v }；i=2：（a ）T （2v ）=5，T （3v ）=6， T （7v ）=9，T （6v ）= 13，（b ）标号中T （2v ）最小，令P （2v ）=5，=2S {4v 5v 2v }；i=3：（a ）T （7v ）=9，T （6v ）= 13，T （3v ）=6，T （1v ）=8，（b ）标号中T （3v ）最小，令P （3v ）=6，=3S {4v 5v 2v 3v }； i=4：（a ）T （7v ）=9，T （6v ）= 13， T （1v ）=8，（b ）标号中T （1v ）最小，令P （1v ）=8，=4S {4v 5v 2v 3v 1v }； i=5：（a ）T （7v ）=9，T （6v ）= 13，（b ）标号中T （7v ）最小，令P （7v ）=9，=5S {4v 5v 2v 3v 1v 7v }； i=6：（a ）T （6v ）= 12，T （8v ）=25,（b ）标号中T （6v ）最小，令P （6v ）=12，=6S {1v 2v 4v 3v 5v 7v 6v }； i=7：（a ）T （8v ）=15,（b ）标号中T （8v ）最小，令P （8v ）=15，=7S {1v 2v 4v 3v 5v 7v 6v 8v }； 所以4Z =Max{ P （i v ）；i=1-8}=15；Y=Min{1Z 2Z 3Z 4Z }= Min{23 20 21 15}=155. 以5v 为出发点i=0：令=0S {5v }，P （5v ）=0,；i=1：（a ）T （4v ）=4，T （6v ）=9， T （7v ）=4，（b ）标号中T （4v ）最小，令P （4v ）=4，=1S {4v 5v }；i=2：（a ）T （2v ）=9，T （3v ）=10， T （7v ）=5，T （6v ）= 9，（b ）标号中T （7v ）最小，令P （7v ）=5，=2S {4v 5v 7v }；i=3：（a ）T （8v ）=11，T （6v ）= 8，T （3v ）=10，T （2v ）=9，（b ）标号中T （6v ）最小，令P （6v ）=8，=3S {4v 5v 7v 6v }； i=4：（a ）T （8v ）=11， T （3v ）=10，T （2v ）=9，（b ）标号中T （2v ）最小，令P （2v ）=9，=4S {4v 5v 7v 6v 2v }； i=5：（a ）T （8v ）=11， T （3v ）=10，T （1v ）=12（b ）标号中T （3v ）最小，令P （3v ）=10，=5S {4v 5v 7v 6v 2v 3v }； i=6：（a ）T （1v ）= 12，T （8v ）=11,（b ）标号中T （8v ）最小，令P （8v ）=11，=6S {4v 5v 7v 6v 2v 3v 8v }； i=7：（a ）T （1v ）= 12，（b ）标号中T （1v ）最小，令P （1v ）=12，=7S {4v 5v 7v 6v 2v 3v 8v 1v }； 所以5Z =Max{ P （i v ）；i=1-8}=12；Y=Min{1Z 2Z 3Z 4Z 5Z }= Min{23 20 21 15 12}=126. 以6v 为出发点i=0：令=0S {6v }，P （6v ）=0,；i=1：（a ）T （8v ）=4， T （5v ）=9，T （7v ）=3，（b ）标号中T （7v ）最小，令P （7v ）=3，=1S {6v 7v }；i=2：（a ）T （8v ）=4， T （5v ）=8，T （4v ）=13，（b ）标号中T （8v ）最小，令P （8v ）=4，=2S {6v 7v 8v }；i=3：（a ）T （5v ）=8，T （4v ）=13，（b ）标号中T （5v ）最小，令P （5v ）=8，=3S {6v 7v 8v 5v }； i=4：（a ）T （4v ）=12，（b ）标号中T （4v ）最小，令P （4v ）=8，=4S {6v 7v 8v 5v 4v }；i=5：（a ）T （3v ）=18，T （2v ）= 17，（b ）标号中T （2v ）最小，令P （2v ）=17，=5S {6v 7v 8v 5v 4v 2v }； 因为6Z =Max{ P （i v ）；i=1-8} ≥P （2v ）=17>12 所以Y=Min{1Z 2Z 3Z 4Z 5Z 6Z }=12 7. 以7v 为出发点i=0：令=0S {7v }，P （7v ）=0,；i=1：（a ）T （8v ）=6， T （5v ）=5，T （6v ）=3，T （4v ）=10，（b ）标号中T （6v ）最小，令P （6v ）=3，=1S {7v 6v }；i=2：（a ）T （8v ）=6， T （5v ）=5，T （4v ）=10，（b ）标号中T （5v ）最小，令P （5v ）=5，=2S {7v 6v 5v }；i=3：（a ）T （8v ）=6， T （4v ）=9，（b ）标号中T （8v ）最小，令P （8v ）=6，=3S {7v 6v 5v 8v }； i=4：（a ）T （3v ）=15，T （2v ）= 14，（b ）标号中T （2v ）最小，令P （2v ）=14，=4S {7v 6v 5v 8v 2v }； 因为7Z =Max{ P （i v ）；i=1-8} ≥P （2v ）=14>12 所以Y=Min{1Z 2Z 3Z 4Z 5Z 6Z 7Z }=12 8. 以8v 为出发点i=0：令=0S {8v }，P （8v ）=0,； i=1：（a ）T （7v ）=6， T （6v ）=4，（b ）标号中T （6v ）最小，令P （6v ）=4，=1S {8v 6v }；i=2：（a ）T （7v ）=6， T （5v ）=13，（b ）标号中T （7v ）最小，令P （7v ）=6，=2S {8v 6v 7v }；i=3：（a ）T （5v ）=11， T （4v ）=16，（b ）标号中T （5v ）最小，令P （5v ）=6，=3S {8v 6v 7v 5v }； i=4：（a ）T （4v ）=15，（b ）标号中T （4v ）最小，令P （4v ）=15，=4S {8v 6v 7v 5v 4v }； 因为7Z =Max{ P （i v ）；i=1-8} ≥P （4v ）=15>12 所以Y=Min{1Z 2Z 3Z 4Z 5Z 6Z 7Z 8Z }=5Z =12七、分析结果与方案评价分析可知v5点为最佳中心医院建立点符合使离医院最远的小区居民就诊时所走的路程为12。
