线性规划问题

1、中心医院选址问题摘要 本篇论文对选址问题进行了较为全面的介绍。内容包括中心医院选址的模型及其建立。针对中心医院选址的一般要求,结合中心医院选址实例，运用所建立的混合整数规划模型确定中心医院选址最佳方案 运用Floyd法解决选址问题关键字：运筹学；选址；中心医院一、提出问题图论是数学的一个分支, 它以图为研究对象.图论中的图是由若干给定的点及连接两边所构成的图形, 用连接两点的边表示相应两个事物间具有某种特定关系。在社区医院的选址问题中, 点表示社区主要居民小区, 而其间的连线(边)则表示小区距离。图论中的最短路径算法包括指定的顶点对之间的最短路径算法和全部顶点间的最短路径算法.前者可用具体患者

2、就医路径的合理化决策分析, 而后者很适合于社区医院的选址, 使得整个社区患者总的就医路径最短。二、问题分析题中要求在该地区的交通网络图中，从-代表八个居民小区的点中选择一个点（i=1,28）即一个小区建立中心医院，使得离距离最大的点到的距离最小。三、模型假设1.假设医院与居民点的距离为直线距离2不考虑各小区的实际尺度，简化为点处理四、符号说明Aij 居民点到居民点的距离Xij 居民点到居民点的最短距离Zi 以居民点为出发点到各居民点的最短距离中的最大距离表示中Zi的最小值五、建立模型 分别以-为出发点，用图论中的求最短路的算法（Dijkstra法）求个点到出发点的最短距离，选其最大值作为的Zi

3、值，再在Zi中选取最小值，得出最终解。六、模型求解 1. 以为出发点 i=0：令，P（）=0,； i=1：（a）T（）=3，T（）=10，（b）标号中T（）最小，令P（）=3，； i=2：（a）T（）=10，T（）= P（）+=3+5=8，（b）标号中T（）最小，令P（）=8，； i=3：（a）T（）=10，T（）= P（）+=8+4=12，T（）= P（）+=8+10=18，（b）标号中T（）最小，令P（）=10，；i=4：（a）T（）=12，T（）=18，（b）标号中T（）最小，令P（）=12，；i=5：（a）T（）=min18, P（）+=12+5=17=17，T（）= P（）+=12+

4、9=21，（b）标号中T（）最小，令P（）=17，；i=6：（a）T（）= min21, P（）+=17+3=20=20，T（）= P（）+=17+6=23,（b）标号中T（）最小，令P（）=20，；i=7：（a）T（）= min23, P（）+=20+4=24=23,（b）标号中T（）最小，令P（）=23，； 所以=Max P（）；i=1-8=23；Y=232. 以为出发点 i=0：令，P（）=0,； i=1：（a）T（）=3，T（）=5，（b）标号中T（）最小，令P（）=3，； i=2：（a）T（）=13，T（）=5，（b）标号中T（）最小，令P（）=5，； i=3：（a）T（）=11，T

5、（）= 9，T（）=15，（b）标号中T（）最小，令P（）=9，；i=4：（a）T（）=11，T（）=14，T（）=18,（b）标号中T（）最小，令P（）=11，；i=5：（a）T（）=14，T（）= 18，（b）标号中T（）最小，令P（）=14，；i=6：（a）T（）= 17，T（）=20,（b）标号中T（）最小，令P（）=17，；i=7：（a）T（）=20,（b）标号中T（）最小，令P（）=20，； 所以=Max P（）；i=1-8=20；Y=Min= Min23 20=203. 以为出发点 i=0：令，P（）=0,； i=1：（a）T（）=10，T（）=6，（b）标号中T（）最小，令P（

6、）=6，； i=2：（a）T（）=10，T（）=11，T（）=10，T（）=16，（b）标号中T（）最小，令P（）=10，P（）=10，； i=3：（a）T（）=11，T（）=19，T（）=15，（b）标号中T（）最小，令P（）=11，；i=4：（a）T（）=19，T（）=15,（b）标号中T（）最小，令P（）=15，；i=5：（a）T（）= 18，P（）=21（b）标号中T（）最小，令P（）=18，；i=6：（a）T（）=21,（b）标号中T（）最小，令P（）=21，； 所以=Max P（）；i=1-8=21；Y=Min= Min23 20 21=204. 以为出发点 i=0：令，P（）=0

7、,； i=1：（a）T（）=5，T（）=6，T（）=4，T（）=10，（b）标号中T（）最小，令P（）=4，； i=2：（a）T（）=5，T（）=6， T（）=9，T（）= 13，（b）标号中T（）最小，令P（）=5，； i=3：（a）T（）=9，T（）= 13，T（）=6，T（）=8，（b）标号中T（）最小，令P（）=6，；i=4：（a）T（）=9，T（）= 13， T（）=8，（b）标号中T（）最小，令P（）=8，；i=5：（a）T（）=9，T（）= 13，（b）标号中T（）最小，令P（）=9，；i=6：（a）T（）= 12，T（）=25,（b）标号中T（）最小，令P（）=12，；i=7：

8、（a）T（）=15,（b）标号中T（）最小，令P（）=15，； 所以=Max P（）；i=1-8=15；Y=Min= Min23 20 21 15=155. 以为出发点 i=0：令，P（）=0,； i=1：（a）T（）=4，T（）=9， T（）=4，（b）标号中T（）最小，令P（）=4，； i=2：（a）T（）=9，T（）=10， T（）=5，T（）= 9，（b）标号中T（）最小，令P（）=5，； i=3：（a）T（）=11，T（）= 8，T（）=10，T（）=9，（b）标号中T（）最小，令P（）=8，；i=4：（a）T（）=11， T（）=10，T（）=9，（b）标号中T（）最小，令P（）=

9、9，；i=5：（a）T（）=11， T（）=10，T（）=12（b）标号中T（）最小，令P（）=10，；i=6：（a）T（）= 12，T（）=11,（b）标号中T（）最小，令P（）=11，；i=7：（a）T（）= 12，（b）标号中T（）最小，令P（）=12，； 所以=Max P（）；i=1-8=12；Y=Min= Min23 20 21 15 12=126. 以为出发点 i=0：令，P（）=0,； i=1：（a）T（）=4， T（）=9，T（）=3，（b）标号中T（）最小，令P（）=3，； i=2：（a）T（）=4， T（）=8，T（）=13，（b）标号中T（）最小，令P（）=4，； i=3

10、：（a）T（）=8，T（）=13，（b）标号中T（）最小，令P（）=8，；i=4：（a）T（）=12，（b）标号中T（）最小，令P（）=8，；i=5：（a）T（）=18，T（）= 17，（b）标号中T（）最小，令P（）=17，；因为=Max P（）；i=1-8 P（）=17>12所以Y=Min=127. 以为出发点 i=0：令，P（）=0,； i=1：（a）T（）=6， T（）=5，T（）=3，T（）=10，（b）标号中T（）最小，令P（）=3，； i=2：（a）T（）=6， T（）=5，T（）=10，（b）标号中T（）最小，令P（）=5，； i=3：（a）T（）=6， T（）=9，（b

11、）标号中T（）最小，令P（）=6，；i=4：（a）T（）=15，T（）= 14，（b）标号中T（）最小，令P（）=14，；因为=Max P（）；i=1-8 P（）=14>12所以Y=Min=128. 以为出发点 i=0：令，P（）=0,； i=1：（a）T（）=6， T（）=4，（b）标号中T（）最小，令P（）=4，； i=2：（a）T（）=6， T（）=13，（b）标号中T（）最小，令P（）=6，； i=3：（a）T（）=11， T（）=16，（b）标号中T（）最小，令P（）=6，；i=4：（a）T（）=15，（b）标号中T（）最小，令P（）=15，；因为=Max P（）；i=1-8 P（）=15>12所以Y=Min=12七、分析