选址问题

中心医院选址问题摘要本篇论文对选址问题进行了较为全面的介绍。内容包括中心医院选址的模型及其建立。针对中心医院选址的一般要求,,结合中心医院选址实例，运用所建立的混合整数规划模型确定中心医院选址最佳方案运用Floyd法解决选址问题关键字：运筹学；选址；中心医院一、提出问题图论是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两边所构成的图形,用连接两点的边表示相应两个事物间具有某种特定关系。在社区医院的选址问题中,点表示社区主要居民小区,而其间的连线(边)则表示小区距离。图论中的最短路径算法包括指定的顶点对之间的最短路径算法和全部顶点间的最短路径算法.前者可用具体患者就医路径的合理化决策分析,而后者很适合于社区医院的选址,使得整个社区患者总的就医路径最短。二、问题分析题中要求在该地区的交通网络图中，从1v-8v代表八个居民小区的点中选择一个点iv（i=1,2…8）即一个小区建立中心医院，使得离iv距离最大的点到iv的距离最小。三、模型假设1.假设医院与居民点的距离为直线距离2不考虑各小区的实际尺度，简化为点处理四、符号说明Aij居民点iv到居民点jv的距离Xij居民点iv到居民点jv的最短距离Zi以居民点iv为出发点到各居民点的最短距离中的最大距离Y表示中Zi的最小值1v2v3v4v5v6v7v8v1010356356944五、建立模型分别以1v-8v为出发点，用图论中的求最短路的算法（Dijkstra法）求个点到出发点的最短距离，选其最大值作为的Zi值，再在Zi中选取最小值，得出最终解。六、模型求解1.以1v为出发点i=0：令0S{1v}，P（1v）=0,；i=1：（a）T（2v）=3，T（3v）=10，（b）标号中T（2v）最小，令P（2v）=3，1S{1v2v}；i=2：（a）T（3v）=10，T（4v）=P（2v）+24A=3+5=8，（b）标号中T（4v）最小，令P（4v）=8，1S{1v2v4v}；i=3：（a）T（3v）=10，T（5v）=P（4v）+54A=8+4=12，T（7v）=P（4v）+47A=8+10=18，（b）标号中T（3v）最小，令P（3v）=10，1S{1v2v4v3v}；i=4：（a）T（5v）=12，T（7v）=18，（b）标号中T（5v）最小，令P（5v）=12，1S{1v2v4v3v5v}；i=5：（a）T（7v）=min{18,P（5v）+57A=12+5=17}=17，T（6v）=P（5v）+56A=12+9=21，（b）标号中T（7v）最小，令P（7v）=17，1S{1v2v4v3v5v7v}；i=6：（a）T（6v）=min{21,P（7v）+67A=17+3=20}=20，T（8v）=P（7v）+78A=17+6=23,（b）标号中T（6v）最小，令P（6v）=20，1S{1v2v4v3v5v7v6v}；i=7：（a）T（8v）=min{23,P（6v）+68A=20+4=24}=23,（b）标号中T（8v）最小，令P（8v）=23，1S{1v2v4v3v5v7v6v8v}；所以1Z=Max{P（iv）；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{1v2v}；i=2：（a）T（3v）=13，T（4v）=5，（b）标号中T（4v）最小，令P（4v）=5，2S{1v2v4v}；i=3：（a）T（3v）=11，T（5v）=9，T（7v）=15，（b）标号中T（5v）最小，令P（5v）=9，3S{1v2v4v5v}；i=4：（a）T（3v）=11，T（7v）=14，T（6v）=18,（b）标号中T（3v）最小，令P（3v）=11，4S{1v2v4v3v5v}；i=5：（a）T（7v）=14，T（6v）=18，（b）标号中T（7v）最小，令P（7v）=14，5S{1v2v4v3v5v7v}；i=6：（a）T（6v）=17，T（8v）=20,（b）标号中T（6v）最小，令P（6v）=17，6S{1v2v4v3v5v7v6v}；i=7：（a）T（8v）=20,（b）标号中T（8v）最小，令P（8v）=20，7S{1v2v4v3v5v7v6v8v}；所以2Z=Max{P（iv）；i=1-8}=20；Y=Min{1Z2Z}=Min{2320}=203.以3v为出发点i=0：令0S{3v}，P（3v）=0,；i=1：（a）T（1v）=10，T（4v）=6，（b）标号中T（4v）最小，令P（4v）=6，1S{3v4v}；i=2：（a）T（1v）=10，T（2v）=11，T（5v）=10，T（7v）=16，（b）标号中T（1v）最小，令P（1v）=10，P（5v）=10，2S{3v4v1v5v}；i=3：（a）T（2v）=11，T（6v）=19，T（7v）=15，（b）标号中T（2v）最小，令P（2v）=11，3S{3v4v1v5v2v}；i=4：（a）T（6v）=19，T（7v）=15,（b）标号中T（7v）最小，令P（7v）=15，4S{3v4v1v5v2v7v}；i=5：（a）T（6v）=18，P（8v）=21（b）标号中T（6v）最小，令P（6v）=18，5S{3v4v1v5v2v7v6v}；i=6：（a）T（8v）=21,（b）标号中T（8v）最小，令P（8v）=21，6S{3v4v1v5v2v7v6v8v}；所以3Z=Max{P（iv）；i=1-8}=21；Y=Min{1Z2Z3Z}=Min{232021}=204.以4v为出发点i=0：令0S{4v}，P（4v）=0,；i=1：（a）T（2v）=5，T（3v）=6，T（5v）=4，T（7v）=10，（b）标号中T（5v）最小，令P（5v）=4，1S{4v5v}；i=2：（a）T（2v）=5，T（3v）=6，T（7v）=9，T（6v）=13，（b）标号中T（2v）最小，令P（2v）=5，2S{4v5v2v}；i=3：（a）T（7v）=9，T（6v）=13，T（3v）=6，T（1v）=8，（b）标号中T（3v）最小，令P（3v）=6，3S{4v5v2v3v}；i=4：（a）T（7v）=9，T（6v）=13，T（1v）=8，（b）标号中T（1v）最小，令P（1v）=8，4S{4v5v2v3v1v}；i=5：（a）T（7v）=9，T（6v）=13，（b）标号中T（7v）最小，令P（7v）=9，5S{4v5v2v3v1v7v}；i=6：（a）T（6v）=12，T（8v）=25,（b）标号中T（6v）最小，令P（6v）=12，6S{1v2v4v3v5v7v6v}；i=7：（a）T（8v）=15,（b）标号中T（8v）最小，令P（8v）=15，7S{1v2v4v3v5v7v6v8v}；所以4Z=Max{P（iv）；i=1-8}=15；Y=Min{1Z2Z3Z4Z}=Min{23202115}=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{4v5v}；i=2：（a）T（2v）=9，T（3v）=10，T（7v）=5，T（6v）=9，（b）标号中T（7v）最小，令P（7v）=5，2S{4v5v7v}；i=3：（a）T（8v）=11，T（6v）=8，T（3v）=10，T（2v）=9，（b）标号中T（6v）最小，令P（6v）=8，3S{4v5v7v6v}；i=4：（a）T（8v）=11，T（3v）=10，T（2v）=9，（b）标号中T（2v）最小，令P（2v）=9，4S{4v5v7v6v2v}；i=5：（a）T（8v）=11，T（3v）=10，T（1v）=12（b）标号中T（3v）最小，令P（3v）=10，5S{4v5v7v6v2v3v}；i=6：（a）T（1v）=12，T（8v）=11,（b）标号中T（8v）最小，令P（8v）=11，6S{4v5v7v6v2v3v8v}；i=7：（a）T（1v）=12，（b）标号中T（1v）最小，令P（1v）=12，7S{4v5v7v6v2v3v8v1v}；所以5Z=Max{P（iv）；i=1-8}=12；Y=Min{1Z2Z3Z4Z5Z}=Min{2320211512}=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{6v7v}；i=2：（a）T（8v）=4，T（5v）=8，T（4v）=13，（b）标号中T（8v）最小，令P（8v）=4，2S{6v7v8v}；i=3：（a）T（5v）=8，T（4v）=13，（b）标号中T（5v）最小，令P（5v）=8，3S{6v7v8v5v}；i=4：（a）T（4v）=12，（b）标号中T（4v）最小，令P（4v）=8，4S{6v7v8v5v4v}；i=5：（a）T（3v）=18，T（2v）=17，（b）标号中T（2v）最小，令P（2v）=17，5S{6v7v8v5v4v2v}；因为6Z=Max{P（iv）；i=1-8}P（2v）=1712所以Y=Min{1Z2Z3Z4Z5Z6Z}=127.以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{7v6v}；i=2：（a）T（8v）=6，T（5v）=5，T（4v）=10，（b）标号中T（5v）最小，令P（5v）=5，2S{7v6v5v}；i=3：（a）T（8v）=6，T（4v）=9，（b）标号中T（8v）最小，令P（8v）=6，3S{7v6v5v8v}；i=4：（a）T（3v）=15，T（2v）=14，（b）标号中T（2v）最小，令P（2v）=14，4S{7v6v5v8v2v}；因为7Z=Max{P（iv）；i=1-8}P（2v）=1412所以Y=Min{1Z2Z3Z4Z5Z6Z7Z}=128.以8v为出发点i=0：令0S{8v}，P（8v）=0,；i=1：（a）T（7v）=6，T（6v）=4，（b）标号中T（6v）最小，令P（6v）=4，1S{8v6v}；i=2：（a）T（7v）=6，T（5v）=13，（b）标号中T（7v）最小，令P（7v）=6，2S{8v6v7v}；i=3：（a）T（5v）=11，T（4v）=16，（b）标号中T（5v）最小，令P（5v）=6，3S{8v6v7v5v}；i=4：（a）T（4v）=15，（b）标号中T（4v）最小，令P（4v）=15，4S{8v6v7v5v4v}；因为7Z=Max{P（iv）；i=1-8}P（4v）=1512所以Y=Min{1Z2Z3Z4Z5Z6Z7Z8Z}=5Z=12七、分析结果与方案评价分析可知v5点为最佳中心医院建立点符合使离医院最远的小区居民就诊时所走的路程为12。参考文献：屈婉玲，耿素云，张立昂，离散数学，北京：高等教育出版社，2008.胡运权《运筹学》，2003朱德通.最优化模型与实验[M].上海:同济大学出版社,2003陈綖《决策分析》1997姜启源，谢金星，数学建模，北京：高等教育出版社，2003。