线性规划问题

中心医院选址问题摘要 本篇论文对选址问题进行了较为全面的介绍。内容包括中心医院选址的模型及其建立。针对中心医院选址的一般要求,结合中心医院选址实例，运用所建立的混合整数规划模型确定中心医院选址最佳方案 运用 Floyd 法解决选址问题关键字：运筹学；选址；中心医院一、提出问题图论是数学的一个分支, 它以图为研究对象.图论中的图是由若干给定的点及连接两边所构成的图形, 用连接两点的边表示相应两个事物间具有某种特定关系。在社区医院的选址问题中, 点表示社区主要居民小区, 而其间的连线(边)则表示小区距离。图论中的最短路径算法包括指定的顶点对之间的最短路径算法和全部顶点间的最短路径算法.前者可用具体患者就医路径的合理化决策分析, 而后者很适合于社区医院的选址, 使得整个社区患者总的就医路径最短。二、问题分析题中要求在该地区的交通网络图中，从 - 代表八个居民小区的1v8点中选择一个点 （i=1,28）即一个小区建立中心医院，使得离iv距离最大的点到 的距离最小。ivi三、模型假设1.假设医院与居民点的距离为直线距离2 不考虑各小区的实际尺度，简化为点处理四、符号说明 Aij 居民点 到居民点 的距离ivjvXij 居民点 到居民点 的最短距离i jZi 以居民点 为出发点到各居民点的最短距离中的最iv大距离表示中 Zi 的最小值Y1v2v3v4v5v6v7v8v0103563 6944五、建立模型分别以 - 为出发点，用图论中的求最短路的算法（Dijkstra 法）1v8求个点到出发点的最短距离，选其最大值作为的 Zi 值，再在 Zi 中选取最小值，得出最终解。六、模型求解 1. 以 为出发点1vi=0：令 ，P（ ）=0,；0S11vi=1：（a）T（ ）=3 ，T （ ）=10 ，23（b）标号中 T（ ）最小，令 P（ ）=3， ；2v2v1Sv2i=2：（a）T（ ）=10 ，T （ ）= P（ ）+ =3+5=8，344A（b）标号中 T（ ）最小，令 P（ ）=8， ；4vv1v24i=3：（a）T（ ）=10 ，T （ ）= P（ ）35+ =8+4=12，T（ ）= P（ ）+ =8+10=18，54A7v4v7A（b）标号中 T（ ）最小，令 P（ ）=10， ；33v1Sv243i=4：（a）T（ ）=12，T （ ）=18 ，5v7v（b）标号中 T（ ）最小，令 P（ ）=12， ；5v1Sv2435i=5：（a）T（ ）=min18, P（ ）+ =12+5=177v 5v7A=17，T（ ）= P （ ）+ =12+9=21，65v6A（b）标号中 T（ ）最小，令 P（ ）=17， 7v7v1Sv2435；7vi=6：（a）T（ ）= min21, P（ ）+ =17+3=206v 7v67A=20，T（ ）= P （ ）+ =17+6=23,87v8A（b）标号中 T（ ）最小，令 P（ ）=20， 661Sv2435；7v6i=7：（a）T（ ）= min23, P（ ）+ =20+4=24=23,8v6v8A（b）标号中 T（ ）最小，令 P（ ）=23， 8 1Sv2435；7v68所以 =Max P（ ） ；i=1-8=23；Y=231Ziv2. 以 为出发点2vi=0：令 ，P（ ）=0,；0S22vi=1：（a）T（ ）=3 ，T （ ）=5 ，14（b）标号中 T（ ）最小，令 P（ ）=3， ；1v1v1Sv2i=2：（a）T（ ）=13 ，T （ ）=5 ，34（b）标号中 T（ ）最小，令 P（ ）=5， ；4v4v21v24i=3：（a）T（ ）=11 ，T （ ）= 9，T（ ）=15，357（b）标号中 T（ ）最小，令 P（ ）=9， ；5v5v3S1v245i=4：（a）T（ ）=11，T （ ）=14 ，T（ ）=18,3v7v6v（b）标号中 T（ ）最小，令 P（ ）=11， ；34S1v2435i=5：（a）T（ ）=14，T （ ）= 18，7v6v（b）标号中 T（ ）最小，令 P（ ）=14， 77v5S1v2435；7vi=6：（a）T（ ）= 17，T （ ）=20,6v8v（b）标号中 T（ ）最小，令 P（ ）=17， 66v6S1v2435；7v6i=7：（a）T（ ）=20,8v（b）标号中 T（ ）最小，令 P（ ）=20， 88v7S1v2435；7v68所以 =Max P（ ） ；i=1-8=20 ；Y=Min = Min23 202Ziv1Z2=203. 以 为出发点3vi=0：令 ，P（ ）=0,；0S33vi=1：（a）T（ ）=10 ，T （ ）=6 ，14（b）标号中 T（ ）最小，令 P（ ）=6， ；4v4v1S3v4i=2：（a）T（ ）=10 ，T （ ）=11 ， T（ ）=10，T（ ）1257=16，（b）标号中 T（ ）最小，令 P（ ）=10，P （ ）=10，1v1v5v ；2S3v415i=3：（a）T（ ）=11 ，T （ ）=19 ， T（ ）=15，2v6v7v（b）标号中 T（ ）最小，令 P（ ）=11， 223Sv415；2vi=4：（a）T（ ）=19，T （ ）=15,6v7v（b）标号中 T（ ）最小，令 P（ ）=15， 77v4S3v4152；7vi=5：（a）T（ ）= 18，P（ ）=216v8v（b）标号中 T（ ）最小，令 P（ ）=18， 66v5S3v4152；7v6i=6：（a）T（ ）=21,8v（b）标号中 T（ ）最小，令 P（ ）=21， 88v6S3v4152；7v68所以 =Max P（ ） ；i=1-8=21；Y=Min = Min23 20 3Ziv1Z2321=204. 以 为出发点4vi=0：令 ，P（ ）=0,；0S44vi=1：（a）T（ ）=5 ，T （ ）=6 ，T（ ）=4，T（ ）=10，235v7v（b）标号中 T（ ）最小，令 P（ ）=4， ；5v 1S45i=2：（a）T（ ）=5 ，T （ ）=6 ， T（ ）=9，T（ ）= 23 7v6v13，（b）标号中 T（ ）最小，令 P（ ）=5， ；2v2v2S4v52i=3：（a）T（ ）=9 ，T （ ）= 13，T（ ）=6，T（ ）=8，7631（b）标号中 T（ ）最小，令 P（ ）=6， ；3vv34v523i=4：（a）T（ ）=9，T （ ）= 13， T（ ）=8，7v6v1v（b）标号中 T（ ）最小，令 P（ ）=8， ；1 4S5v231i=5：（a）T（ ）=9，T （ ）= 13，7v6v（b）标号中 T（ ）最小，令 P（ ）=9， 77v5S4v5231；7vi=6：（a）T（ ）= 12，T （ ）=25,6v8v（b）标号中 T（ ）最小，令 P（ ）=12， 66v6S1v2435；7v6i=7：（a）T（ ）=15,8v（b）标号中 T（ ）最小，令 P（ ）=15， 88v7S1v2435；7v68所以 =Max P（ ） ；i=1-8=15；Y=Min = Min23 4Ziv1Z23420 21 15=155. 以 为出发点5vi=0：令 ，P（ ）=0,；0S55vi=1：（a）T（ ）=4 ，T （ ）=9 ， T（ ）=4，467v（b）标号中 T（ ）最小，令 P（ ）=4， ；4v41S4v5i=2：（a）T（ ）=9 ，T （ ）=10 ， T（ ）=5，T（ ）= 23 769，（b）标号中 T（ ）最小，令 P（ ）=5， ；7v7v2S4v57i=3：（a）T（ ）=11 ，T （ ）= 8，T（ ）=10，T（ ）8v6v3v2v=9，（b）标号中 T（ ）最小，令 P（ ）=8， ；6v6v3S4v576i=4：（a）T（ ）=11， T（ ）=10 ，T（ ）=9，8v3v2v（b）标号中 T（ ）最小，令 P（ ）=9， ；2 4S5v762i=5：（a）T（ ）=11， T（ ）=10 ，T（ ）=128v3v1v（b）标号中 T（ ）最小，令 P（ ）=10， 335S4v5762；3vi=6：（a）T（ ）= 12，T （ ）=11,18v（b）标号中 T（ ）最小，令 P（ ）=11， 88v6S4v5762；3v8i=7：（a）T（ ）= 12，1v（b）标号中 T（ ）最小，令 P（ ）=12， 1v7S4v5762；3v81所以 =Max P（ ） ；i=1-8=12；Y=Min = 5Ziv1Z2345Min23 20 21 15 12=126. 以 为出发点6vi=0：令 ，P（ ）=0,；0S66vi=1：（a）T（ ）=4 ， T（ ）=9 ，T（ ）=3，857v（b）标号中 T（ ）最小，令 P（ ）=3， ；7v 1S6v7i=2：（a）T（ ）=4 ， T（ ）=8 ，T（ ）=13，8v5v4v（b）标号中 T（ ）最小，令 P（ ）=4， ；882S6v78i=3：（a）T（ ）=8 ，T （ ）=13 ，5v4v（b）标号中 T（ ）最小，令 P（ ）=8， ；55v36v785i=4：（a）T（ ）=12，4v（b）标号中 T（ ）最小，令 P（ ）=8， ；4v4S6v7854i=5：（a）T（ ）=18，T （ ）= 17，3v2v（b）标号中 T（ ）最小，令 P（ ）=17， 22v5S6v7854；2v因为 =Max P（ ） ；i=1-8 P（ ）=17126Ziv2v所以 Y=Min =12123Z4567. 以 为出发点7vi=0：令 ，P（ ）=0,；0S77vi=1：（a）T（ ）=6 ， T（ ）=5，T（ ）=3，T（ ）8 5v6v4v=10，（b）标号中 T（ ）最小，令 P（ ）=3， ；6v6v1S7v6i=2：（a）T（ ）=6 ， T（ ）=5 ，T（ ）=10，854（b）标号中 T（ ）最小，令 P（ ）=5， ；5v5v27v65i=3：（a）T（ ）=6 ， T（ ）=9 ，84（b）标号中 T（ ）最小，令 P（ ）=6， ；8v8v3S7v658i=4：（a）T（ ）=15，T （ ）= 14，3v2v（b）标号中 T（ ）最小，令 P（ ）=14， ；22v4S7v6582因为 =Max P（ ） ；i=1-8 P（ ）=14127Ziv2v所以 Y=Min =12123Z45678. 以 为出发点8vi=0：令 ，P（ ）=0,；0S88vi=1：（a）T（ ）=6 ， T（ ）=4 ，76（b）标号中 T（ ）最小，令 P（ ）=4， ；6v6v1S8v6i=2：（a）T（ ）=6 ， T（ ）=13 ，75（b）标号中 T（ ）最小，令 P（ ）=6， ；7v7v28v67i=3：（a）T（ ）=11 ， T（ ）=16 ，54（b）标号中 T（ ）最小，令 P（ ）=6， ；5v5v3S8v675i=4：（a）T（ ）=15，4v（b）标号中 T（ ）最小，令 P（ ）=15， ；4v4S8v6