《线性规划问题》由会员分享，可在线阅读，更多相关《线性规划问题（10页珍藏版）》请在金锄头文库上搜索。
1、中心医院选址问题摘要 本篇论文对选址问题进行了较为全面的介绍。内容包括中心医院选址的模型及其建立。针对中心医院选址的一般要求,结合中心医院选址实例，运用所建立的混合整数规划模型确定中心医院选址最佳方案 运用 FloydFloyd 法解决选址问题关键字：运筹学；选址；中心医院一、提出问题一、提出问题图论是数学的一个分支, 它以图为研究对象.图论中的图是由若干给定的点及连接两边所构成的图形, 用连接两点的边表示相应两个事物间具有某种特定关系。在社区医院的选址问题中, 点表示社区主要居民小区, 而其间的连线(边)则表示小区距离。图论中的最短路径算法包括指定的顶点对之间的最短路径算法和全部顶点间的最短
2、路径算法.前者可用具体患者就医路径的合理化决策分析, 而后者很适合于社区医院的选址, 使得整个社区患者总的就医路径最短。二、问题分析二、问题分析题中要求在该地区的交通网络图中，从 -代表八个居民小区的1v8v点中选择一个点（i=1,28）即一个小区建立中心医院，使得离iv距离最大的点到的距离最小。iviv三、模型假设三、模型假设1.假设医院与居民点的距离为直线距离2 不考虑各小区的实际尺度，简化为点处理四、符号说明四、符号说明 Aij 居民点到居民点的距离ivjvXij 居民点到居民点的最短距离ivjvZi 以居民点为出发点到各居民点的最短距离中的最iv大距离表示中 Zi的最小值Y1v2v3v
3、4v5v6v7v8v1010356356944五、建立模型五、建立模型分别以 -为出发点，用图论中的求最短路的算法（Dijkstra 法）1v8v求个点到出发点的最短距离，选其最大值作为的 Zi值，再在 Zi中选取最小值，得出最终解。六、模型求解六、模型求解 1. 以为出发点1vi=0：令，P（）=0,；0S1v1vi=1：（a）T（）=3，T（）=10，2v3v（b）标号中 T（）最小，令 P（）=3，；2v2v1S1v2vi=2：（a）T（）=10，T（）= P（）+=3+5=8，3v4v2v24A（b）标号中 T（）最小，令 P（）=8，；4v4v1S1v2v4vi=3：（a）T（）=1
4、0，T（）= P（）3v5v4v+=8+4=12，T（）= P（）+=8+10=18，54A7v4v47A（b）标号中 T（）最小，令 P（）=10，；3v3v1S1v2v4v3vi=4：（a）T（）=12，T（）=18，5v7v（b）标号中 T（）最小，令 P（）=12，；5v5v1S1v2v4v3v5vi=5：（a）T（）=min18, P（）+=12+5=177v5v57A=17，T（）= P（）+=12+9=21，6v5v56A（b）标号中 T（）最小，令 P（）=17，7v7v1S1v2v4v3v5v；7vi=6：（a）T（）= min21, P（）+=17+3=206v7v67A=
5、20，T（）= P（）+=17+6=23,8v7v78A（b）标号中 T（）最小，令 P（）=20，6v6v1S1v2v4v3v5v；7v6vi=7：（a）T（）= min23, P（）+=20+4=24=23,8v6v68A（b）标号中 T（）最小，令 P（）=23，8v8v1S1v2v4v3v5v；7v6v8v所以=Max P（） ；i=1-8=23；Y=231Ziv2. 以为出发点2vi=0：令，P（）=0,；0S2v2vi=1：（a）T（）=3，T（）=5，1v4v（b）标号中 T（）最小，令 P（）=3，；1v1v1S1v2vi=2：（a）T（）=13，T（）=5，3v4v（b）标号
6、中 T（）最小，令 P（）=5，；4v4v2S1v2v4vi=3：（a）T（）=11，T（）= 9，T（）=15，3v5v7v（b）标号中 T（）最小，令 P（）=9，；5v5v3S1v2v4v5vi=4：（a）T（）=11，T（）=14，T（）=18,3v7v6v（b）标号中 T（）最小，令 P（）=11，；3v3v4S1v2v4v3v5vi=5：（a）T（）=14，T（）= 18，7v6v（b）标号中 T（）最小，令 P（）=14，7v7v5S1v2v4v3v5v；7vi=6：（a）T（）= 17，T（）=20,6v8v（b）标号中 T（）最小，令 P（）=17，6v6v6S1v2v4v3
7、v5v；7v6vi=7：（a）T（）=20,8v（b）标号中 T（）最小，令 P（）=20，8v8v7S1v2v4v3v5v；7v6v8v所以=Max P（） ；i=1-8=20；Y=Min= Min23 202Ziv1Z2Z=203. 以为出发点3vi=0：令，P（）=0,；0S3v3vi=1：（a）T（）=10，T（）=6，1v4v（b）标号中 T（）最小，令 P（）=6，；4v4v1S3v4vi=2：（a）T（）=10，T（）=11，T（）=10，T（）1v2v5v7v=16，（b）标号中 T（）最小，令 P（）=10，P（）=10，1v1v5v；2S3v4v1v5vi=3：（a）T（）
8、=11，T（）=19，T（）=15，2v6v7v（b）标号中 T（）最小，令 P（）=11，2v2v3S3v4v1v5v；2vi=4：（a）T（）=19，T（）=15,6v7v（b）标号中 T（）最小，令 P（）=15，7v7v4S3v4v1v5v2v；7vi=5：（a）T（）= 18，P（）=216v8v（b）标号中 T（）最小，令 P（）=18，6v6v5S3v4v1v5v2v；7v6vi=6：（a）T（）=21,8v（b）标号中 T（）最小，令 P（）=21，8v8v6S3v4v1v5v2v；7v6v8v所以=Max P（） ；i=1-8=21；Y=Min= Min23 20 3Ziv1
9、Z2Z3Z21=204. 以为出发点4vi=0：令，P（）=0,；0S4v4vi=1：（a）T（）=5，T（）=6，T（）=4，T（）=10，2v3v5v7v（b）标号中 T（）最小，令 P（）=4，；5v5v1S4v5vi=2：（a）T（）=5，T（）=6， T（）=9，T（）= 2v3v7v6v13，（b）标号中 T（）最小，令 P（）=5，；2v2v2S4v5v2vi=3：（a）T（）=9，T（）= 13，T（）=6，T（）=8，7v6v3v1v（b）标号中 T（）最小，令 P（）=6，；3v3v3S4v5v2v3vi=4：（a）T（）=9，T（）= 13， T（）=8，7v6v1v（b
10、）标号中 T（）最小，令 P（）=8，；1v1v4S4v5v2v3v1vi=5：（a）T（）=9，T（）= 13，7v6v（b）标号中 T（）最小，令 P（）=9，7v7v5S4v5v2v3v1v；7vi=6：（a）T（）= 12，T（）=25,6v8v（b）标号中 T（）最小，令 P（）=12，6v6v6S1v2v4v3v5v；7v6vi=7：（a）T（）=15,8v（b）标号中 T（）最小，令 P（）=15，8v8v7S1v2v4v3v5v；7v6v8v所以=Max P（） ；i=1-8=15；Y=Min= Min23 4Ziv1Z2Z3Z4Z20 21 15=155. 以为出发点5vi=
11、0：令，P（）=0,；0S5v5vi=1：（a）T（）=4，T（）=9， T（）=4，4v6v7v（b）标号中 T（）最小，令 P（）=4，；4v4v1S4v5vi=2：（a）T（）=9，T（）=10， T（）=5，T（）= 2v3v7v6v9，（b）标号中 T（）最小，令 P（）=5，；7v7v2S4v5v7vi=3：（a）T（）=11，T（）= 8，T（）=10，T（）8v6v3v2v=9，（b）标号中 T（）最小，令 P（）=8，；6v6v3S4v5v7v6vi=4：（a）T（）=11， T（）=10，T（）=9，8v3v2v（b）标号中 T（）最小，令 P（）=9，；2v2v4S4v5
12、v7v6v2vi=5：（a）T（）=11， T（）=10，T（）=128v3v1v（b）标号中 T（）最小，令 P（）=10，3v3v5S4v5v7v6v2v；3vi=6：（a）T（）= 12，T（）=11,1v8v（b）标号中 T（）最小，令 P（）=11，8v8v6S4v5v7v6v2v；3v8vi=7：（a）T（）= 12，1v（b）标号中 T（）最小，令 P（）=12，1v1v7S4v5v7v6v2v；3v8v1v所以=Max P（） ；i=1-8=12；Y=Min= 5Ziv1Z2Z3Z4Z5ZMin23 20 21 15 12=126. 以为出发点6vi=0：令，P（）=0,；0S
13、6v6vi=1：（a）T（）=4， T（）=9，T（）=3，8v5v7v（b）标号中 T（）最小，令 P（）=3，；7v7v1S6v7vi=2：（a）T（）=4， T（）=8，T（）=13，8v5v4v（b）标号中 T（）最小，令 P（）=4，；8v8v2S6v7v8vi=3：（a）T（）=8，T（）=13，5v4v（b）标号中 T（）最小，令 P（）=8，；5v5v3S6v7v8v5vi=4：（a）T（）=12，4v（b）标号中 T（）最小，令 P（）=8，；4v4v4S6v7v8v5v4vi=5：（a）T（）=18，T（）= 17，3v2v（b）标号中 T（）最小，令 P（）=17，2v2
14、v5S6v7v8v5v4v；2v因为=Max P（） ；i=1-8 P（）=17126Ziv2v所以 Y=Min=121Z2Z3Z4Z5Z6Z7. 以为出发点7vi=0：令，P（）=0,；0S7v7vi=1：（a）T（）=6， T（）=5，T（）=3，T（）8v5v6v4v=10，（b）标号中 T（）最小，令 P（）=3，；6v6v1S7v6vi=2：（a）T（）=6， T（）=5，T（）=10，8v5v4v（b）标号中 T（）最小，令 P（）=5，；5v5v2S7v6v5vi=3：（a）T（）=6， T（）=9，8v4v（b）标号中 T（）最小，令 P（）=6，；8v8v3S7v6v5v8v
15、i=4：（a）T（）=15，T（）= 14，3v2v（b）标号中 T（）最小，令 P（）=14，；2v2v4S7v6v5v8v2v因为=Max P（） ；i=1-8 P（）=14127Ziv2v所以 Y=Min=121Z2Z3Z4Z5Z6Z7Z8. 以为出发点8vi=0：令，P（）=0,；0S8v8vi=1：（a）T（）=6， T（）=4，7v6v（b）标号中 T（）最小，令 P（）=4，；6v6v1S8v6vi=2：（a）T（）=6， T（）=13，7v5v（b）标号中 T（）最小，令 P（）=6，；7v7v2S8v6v7vi=3：（a）T（）=11， T（）=16，5v4v（b）标号中 T（）最小，令 P（）=6，；5v5v3S8v6v7v5vi=4：（a）T（）=15，4v（b）标号中 T（）最小，令 P（）=15，；4v4v4S8v6v7v5v4v因为=Max P（） ；i=1-8 P（）=15127Ziv4v所以 Y=Min=121Z2Z3Z4Z5Z6Z7Z8Z5Z七、分析结果与方案评价七、分析结果与方案评价分析可知v5点为最佳中心医院建立点符合使离医院最远的小区居民就诊时所走的路程为 12。参考文献：屈婉玲，耿素云，张立昂，离散数学，北京：高等教育出版社，2008.胡运权
