卫生站选址问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
我国的医疗卫生事关全民族的身体健康。卫生事业是社会公益事业,卫生事业发展必须与国民经济和社会发展相协调,人民健康保障水平必须与经济发展水平相适应。在社会主义市场经济条件下,发展卫生事业 ,应该坚持以政府为主导,同时发挥市场机制作用的方针,坚持以农村为重点,坚持预防为主,坚持中西医并重,依靠科技教育,动员全社会参与,为人民健康服务,为社会主义现代化建设服务。
农村卫生改革与发展是我国医疗卫生事业改革与发展的重点。也是我国构建和谐社会的基础。新型农村合作医疗
制度
关于办公室下班关闭电源制度矿山事故隐患举报和奖励制度制度下载人事管理制度doc盘点制度下载
是未来农村基本医疗保障制度的雏形。试点情况
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
明,这项制度对于缓解农民医疗的经济负担,提高农民医疗服务水平发挥了重要作用。国务院决定,到2008年在全国基本推行这项制度,充分发挥合作医疗制度对农村社会事业发展的促进作用。建设社会主义新农村,需要建立新型农村合作医疗制度,提高农村公共服务水平。自启动新型农村合作医疗试点工作以来,试点市县的农民减轻了医药费用负担,受到了农民群众的普遍欢迎。
某县要在其所辖的13个乡镇:V1,V2, …,V13 ,新建卫生站(建在乡镇),为13个乡镇服务,要求卫生站至最远乡镇的距离达到最小。假设该13个乡镇之间的交通网络被抽象为下图所示的无向赋权连通图,权值为乡镇之间的距离。
(1) 如果修建一个卫生站,该卫生站应设在哪个乡镇,即哪个顶点?
(2) 修建卫生站后,找出该卫生站到最近,最远乡镇的路径。
(3) 如果修建两个卫生站,使最大服务距离最小,卫生站又该设在哪两乡镇,即哪两顶点?
(4) 把13个乡镇用高压电缆连接起来建立一个电网, 使所用的电缆长度之和最短, 即总费用最小。
卫生站选址问题
卫生站选址问题
【摘 要】: 为解决当前人们就医难,看病难的问题,现某政府决定要在其所辖的乡镇新建卫生站,为考虑全体乡镇,统筹兼顾,最大限度的方便群众就医,充分发挥卫生站的作用。我们将各乡镇看成平面上的点,要求卫生站至最远点的距离达到最小。当各点到卫生站的距离有多种情况时,取其最优值,最后取最大服务距离最小的那种
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。可将全县的高压电缆架设问题看成点与点之间的连线问题求解。
其中模型的建立和解决运用了Floyd算法,排列组合,数列求和以及最优连线等数学方法。
该模型可以运用到解决类似的问题如学校选址,自来水管的铺设等问题,极大程度的方便了最优方案的建立,有效地缩短了解决问题的时间。
【关键词】:卫生站,选址,Floyd算法,排列组合,数列求和,最优连线
1、问题重述
某县要建卫生站为其所在辖的13个乡镇:V1,V2, …,V13服务,要求卫生站至最远乡镇的距离达到最小。
(1)若要修建一个卫生站,应建在哪个乡镇?
(2)修建好之后,找出其到最近、最远乡镇的路径?
(3)若修建两个卫生站,使最大服务距离最小,卫生站又设在哪两个乡镇?
(4)怎样将13个乡镇用高压电缆连接起来建立一个电网,使所用的电缆长度之和最短,总费用最少?
2、 模型假设
考虑该县的交通网络图为一个无向赋权连通图,其中顶点代表各个乡镇,边代表连接两个乡镇之间的公路段,现需在这些顶点中设立一个卫生站,如何选取可以使得其至最远乡镇的距离达到最小。怎样建立两个卫生站,可以使最大服务距离最小。由于建立卫生站需考虑人流及服务范围等因素,因此作出如下假设
( a) 建立一个卫生站时,只考虑卫生站至最远乡镇的距离;
( b) 建立两个卫生站时,卫生站所能提供的服务相同;
3、模型建立
第一二问:
把乡镇间的公路示意图抽象为一赋权连通图G(V,E),在权图G中,Vi
V(G)对应示意图中的乡镇所在地,Vi表示13个乡镇的所在地,ej
E(G)对应示意图中的公路,边权
( ej)对应示意图中的公路长度.
V10 V9
a) 用Floyd算法求出距离矩阵D=(
)
b) 计算在各点Vi 建立卫生站的最大服务距离S(vi):
S(Vi)=
(
),i=1,2,…,13
c) 求出顶点Vk ,使S(Vk )=
(S(Vi)),则Vk 就是要求的建立
卫生站的地点.
d) 用MATLAB编写主程序floyd.m,运行程序floyd.m后,得出的结果为:
两点的距离矩阵
d =
0 9 14 15 8 8 3 6 12 15 17 12 23
9 0 5 8 12 14 7 15 16 19 21 18 29
14 5 0 13 17 19 12 20 14 24 26 23 34
15 8 13 0 7 9 12 12 11 14 16 13 24
8 12 17 7 0 2 5 5 4 7 9 6 17
8 14 19 9 2 0 7 3 6 9 11 4 15
3 7 12 12 5 7 0 9 9 12 14 11 22
6 15 20 12 5 3 9 0 9 12 14 7 18
12 16 14 11 4 6 9 9 0 11 13 10 21
15 19 24 14 7 9 12 12 11 0 2 12 24
17 21 26 16 9 11 14 14 13 2 0 10 26
12 18 23 13 6 4 11 7 10 12 10 0 19
23 29 34 24 17 15 22 18 21 24 26 19 0
经过的中间点矩阵
r =
1 2 2 7 7 6 7 8 7 7 7 6 6
1 2 3 4 7 7 7 1 7 7 7 7 7
2 2 3 2 2 2 2 2 9 2 2 2 2
5 2 2 4 5 5 5 5 5 5 5 5 5
7 7 7 4 5 6 7 6 9 10 11 6 6
1 5 5 5 5 6 5 8 5 5 5 12 13
1 2 2 5 5 5 7 1 5 5 5 5 5
1 1 1 6 6 6 1 8 6 6 6 6 6
5 5 3 5 5 5 5 5 9 5 5 5 5
5 5 5 5 5 5 5 5 5 10 11 11 5
5 5 5 5 5 5 5 5 5 10 11 12 5
6 6 6 6 6 6 6 6 6 11 11 12 6
6 6 6 6 6 6 6 6 6 6 6 6 13
若V5为卫生站,最远点到卫生站的距离为17,最远距离最小。所以,卫生站应该建立在:V5处
到卫生站V5最近的乡镇是V6,路径为:V5→V6
到卫生站V5最远的乡镇是V3和V13,路径分别为:V5→V7→V2→V3,V5→V6→V13
第三问:
假设两卫生站地址已选定,则其他乡镇到卫生站的距离取其到两卫生站距离较小的一个,两卫生站的取法共有C
=78。不重复地取卫生站,若第一个卫生站取乡镇V1,第二个卫生站依次取V2,V3…V13则有12种取法;若第一个卫生站取乡镇V2,第二个卫生站依次取V3,V4…V13则有11种取法;若第一个卫生站取乡镇V3,第二个卫生站依次取V4,V5…V13则有10种取法;…若第一个卫生站取乡镇V12,第二个卫生站取V13则有1种取法,由上可得一个等差数列:首项为12,末项为1,公差为-1的一个等差数列:12,11,10, 9, 8, 7, 6, 5, 4, 3,2, 1。
依次计算出每种情况下各乡镇到卫生站的最优距离可得一个78行,13列的距离矩阵,如下
c =
0 0 5 8 8 8 3 6 12 15 17 12 23
0 5 0 13 8 8 3 6 12 15 17 12 23
0 8 13 0 7 8 3 6 11 14 16 12 23
0 9 14 7 0 2 3 5 4 7 9 6 17
0 9 14 9 2 0 3 3 6 9 11 4 15
0 7 12 12 5 7 0 6 9 12 14 11 22
0 9 14 12 5 3 3 0 9 12 14 7 18
0 9 14 11 4 6 3 6 0 11 13 10 21
0 9 14 14 7 8 3 6 11 0 2 12 23
0 9 14 15 8 8 3 6 12 2 0 10 23
0 9 14 13 6 4 3 6 10 12 10 0 19
0 9 14 15 8 8 3 6 12 15 17 12 0
9 0 0 8 12 14 7 15 14 19 21 18 29
9 0 5 0 7 9 7 12 11 14 16 13 24
8 0 5 7 0 2 5 5 4 7 9 6 17
8 0 5 8 2 0 7 3 6 9 11 4 15
3 0 5 8 5 7 0 9 9 12 14 11 22
6 0 5 8 5 3 7 0 9 12 14 7 18
9 0 5 8 4 6 7 9 0 11 13 10 21
9 0 5 8 7 9 7 12 11 0 2 12 24
9 0 5 8 9 11 7 14 13 2 0 10 26
9 0 5 8 6 4 7 7 10 12 10 0 19
9 0 5 8 12 14 7 15 16 19 21 18 0
14 5 0 0 7 9 12 12 11 14 16 13 24
8 5 0 7 0 2 5 5 4 7 9 6 17
8 5 0 9 2 0 7 3 6 9 11 4 15
3 5 0 12 5 7 0 9 9 12 14 11 22
6 5 0 12 5 3 9 0 9 12 14 7 18
12 5 0 11 4 6 9 9 0 11 13 10 21
14 5 0 13 7 9 12 12 11 0 2 12 24
14 5 0 13 9 11 12 14 13 2 0 10 26
12 5 0 13 6 4 11 7 10 12 10 0 19
14 5 0 13 17 15 12 18 14 24 26 19 0
8 8 13 0 0 2 5 5 4 7 9 6 17
8 8 13 0 2 0 7 3 6 9 11 4 15
3 7 12 0 5 7 0 9 9 12 14 11 22
6 8 13 0 5 3 9 0 9 12 14 7 18
12 8 13 0 4 6 9 9 0 11 13 10 21
15 8 13 0 7 9 12 12 11 0 2 12 24
15 8 13 0 7 9 12 12 11 2 0 10 24
12 8 13 0 6 4 11 7 10 12 10 0 19
15 8 13 0 7 9 12 12 11 14 16 13 0
8 12 17 7 0 0 5 3 4 7 9 4 15
3 7 12 7 0 2 0 5 4 7 9 6 17
6 12 17 7 0 2 5 0 4 7 9 6 17
8 12 14 7 0 2 5 5 0 7 9 6 17
8 12 17 7 0 2 5 5 4 0 2 6 17
8 12 17 7 0 2 5 5 4 2 0 6 17
8 12 17 7 0 2 5 5 4 7 9 0 17
8 12 17 7 0 2 5 5 4 7 9 6 0
3 7 12 9 2 0 0 3 6 9 11 4 15
6 14 19 9 2 0 7 0 6 9 11 4 15
8 14 14 9 2 0 7 3 0 9 11 4 15
8 14 19 9 2 0 7 3 6 0 2 4 15
8 14 19 9 2 0 7 3 6 2 0 4 15
8 14 19 9 2 0 7 3 6 9 10 0 15
8 14 19 9 2 0 7 3 6 9 11 4 0
3 7 12 12 5 3 0 0 9 12 14 7 18
3 7 12 11 4 6 0 9 0 11 13 10 21
3 7 12 12 5 7 0 9 9 0 2 11 22
3 7 12 12 5 7 0 9 9 2 0 10 22
3 7 12 12 5 4 0 7 9 12 10 0 19
3 7 12 12 5 7 0 9 9 12 14 11 0
6 15 14 11 4 3 9 0 0 11 13 7 18
6 15 20 12 5 3 9 0 9 0 2 7 18
6 15 20 12 5 3 9 0 9 2 0 7 18
6 15 20 12 5 3 9 0 9 12 10 0 18
6 15 20 12 5 3 9 0 9 12 14 7 0
12 16 14 11 4 6 9 9 0 0 2 10 21
12 16 14 11 4 6 9 9 0 2 0 10 21
12 16 14 11 4 4 9 7 0 11 10 0 19
12 16 14 11 4 6 9 9 0 11 13 10 0
15 19 24 14 7 9 12 12 11 0 0 10 24
12 18 23 13 6 4 11 7 10 0 2 0 19
15 19 24 14 7 9 12 12 11 0 2 12 0
12 18 23 13 6 4 11 7 10 2 0 0 19
17 21 26 16 9 11 14 14 13 2 0 10 0
12 18 23 13 6 4 11 7 10 12 10 0 0
在Matlab中:得到c的转置矩阵b,再用max函数求出b中每列的最大值(即c中每行的最大值),再用min函数得到最大值中的最小值e。有等差数列求和公式可得不等式
×h/2≤e<{12+
}×(h+1)/2 可得整数h,把h赋值给W
q=e-
×W/2
若q=0则说明第二个卫生站的点为V13
若q>0则说明第一个卫生站V的下标为w+1,第二个卫生站V的小标为w+1+q
由题最终得出最大服务距离最小的两个卫生站的选址为(V7,V13)
(前三问MATLAB解题程序详见附录一)
第四个问题:
将高压电缆架设问题看成点与点之间的连线问题求解,运用最优连线发求解:
设
是两点i与j之间的距离,
0或1(1表示连接,0表示不连接),并假设顶点1是生成树的根。
则数学表达式为:
min
EMBED Equation.3
s.t
EQ
EMBED Equation.3
EMBED Equation.3 (至少有一条边接到其它边)
(除根外每一条边进入)
(各边不构成圈) (第四问LINGO解题程序详见附录二)
结果如下:
V10 V9
4、模型的评价:
优点:
我国地域辽阔,各地区地理环境情况不尽相同,经济状况呈梯度分布。因此,本文是具体研究结合一个县,建立出特定的数学模型。
该模型是一个最短路应用中的选址问题,利用Floyed算法进行求解,用最小生成树方法进行检验,模型是合理且有可行性的。
具有较强的科学性,易于推广,实用性强,遇到类似选址的问题只需改变无向图的邻接矩阵即可得到一系列最优选址问题,无需改动具体的程序代码,形成一种模板,运用最优连线求解,结果简单,易于理解,可靠程度高,改变类似有关最优连线问题的距离矩阵即可得到最优连线,无需改动具体的程序代码,形成模板。该模型可以运用到解决类似的问题如学校选址,自来水管的铺设等问题
缺点:
Matlab求解结构代码较为繁琐复杂,用LINGO软件求解最优连线问题,其基本思想是将所求问题化为0--1整数规划,因此当所求问题的顶点数较大时,计算速度可能会比较慢。
5、模型的分析与检验
改变已知类似有关选址的问题的无向图的邻接矩阵仍可得到一系列最优选址问题,无需改动具体的程序代码,并且与实际情况相符合。参考第3版《数学建模与数学实验》page189例2
改变已知类似有关最优连线问题的距离矩阵仍可得到最优连线,无需改动具体的程序代码,并且与实际情况相符合。参考《Lingo和Excel在数学中的应用》page78例2.3.1
附录1:
a=[0 9 inf inf inf 8 3 6 inf inf inf inf inf;
9 0 5 8 inf inf 7 inf inf inf inf inf inf ;
inf 5 0 inf inf inf inf inf 14 inf inf inf inf ;
inf 8 inf 0 7 inf inf inf inf inf inf inf inf
inf inf inf 7 0 2 5 inf 4 7 9 inf inf ;
8 inf inf inf 2 0 inf 3 inf inf inf 4 15;
3 7 inf inf 5 inf 0 inf inf inf inf inf inf ;
6 inf inf inf inf 3 inf 0 inf inf inf inf inf ;
inf inf 14 inf 4 inf inf inf 0 inf inf inf inf;
inf inf inf inf 7 inf inf inf inf 0 2 inf inf;
inf inf inf inf 9 inf inf inf inf 2 0 10 inf
inf inf inf inf inf 4 inf inf inf inf 10 0 inf ;
inf inf inf inf inf 15 inf inf inf inf inf inf 0];
n=size(a,1); %矩阵的维数
d=a; %把矩阵a赋值给b
for i=1:n %赋值路径矩阵
for j=1:n
r(i,j)=j;
end
end
for k=1:n %求两点的距离矩阵和经过的中间点矩阵
for i=1:n
for j=1:n
if d(i,j)>d(i,k)+d(k,j)
d(i,j)=d(i,k)+d(k,j);
r(i,j)=r(i,k);
end
end
end
end
disp(['两点的距离矩阵'])
d %两点的距离矩阵
disp(['经过的中间点矩阵'])
r %经过的中间点矩阵
t=d'; %定义矩阵t为矩阵d的转置
for p=1:n %求每列的最大距离
g(p,1)=max(t(:,p)); %定义g为t矩阵每行的最大值
end
disp(['最大距离的最小值ans'])
min(g(:,1)) %最大距离的最小值
for k=1:n %求最大距离中的最小距离
if g(k,1)==min(g(:,1))
disp(['u为卫生站所在的行的序数'])
u= k %最大距离中的最小距离所在的行的下标
end
end
disp(['所以最优修建卫生站的乡镇位置是V',num2str(u)])
%如下是取两个卫生站时的相关代码
m=1;
for i=1:n
for j=i+1:n
for k=1:n
if d(i,k)>=d(j,k)
c(m,k)=d(j,k);
else
c(m,k)=d(i,k);
end
end
m;
c; %矩阵c为各点到两卫生站距离较小值的距离矩阵
c(m,:) ;
m=m+1;
end
end
sum1=0; %计算sum1为所有组合的总数
for i=1:n-1
sum1=sum1+i;
end
disp(['c为各点到两卫生站距离较小值的距离矩阵'])
c
b=c'; %定义矩阵b为矩阵c的转置
for m=1: sum1 %求每列的最大距离
f(m,1)=max(b(:,m));
end
f(:,1);
disp(['最大服务距离的最小值ans'])
min(f(:,1))
for k=1:sum1 %求最大距离中的最小距离
if f(k,1)==min(f(:,1))
disp(['e为组合所在的行的序数'])
e= k %最大距离中的最小距离所在的行
end
end
for h=1:12
if (12+(13-h))*h/2<=e & e<(12+(13-(h+1)))*(h+1)/2 %确定一个卫生站
w=h
end
end
q=e-(12+(13-w))*w/2; %确定另一个卫生站
if q==0
disp(['使最大服务距离最小应选择V',num2str(w),'和','V13','为卫生站'])
else
disp(['使最大服务距离最小应选择V',num2str(w+1),'和',num2str(w+1+q),'为卫生站'])
end
运行结果:
两点的距离矩阵
d =
0 9 14 15 8 8 3 6 12 15 17 12 23
9 0 5 8 12 14 7 15 16 19 21 18 29
14 5 0 13 17 19 12 20 14 24 26 23 34
15 8 13 0 7 9 12 12 11 14 16 13 24
8 12 17 7 0 2 5 5 4 7 9 6 17
8 14 19 9 2 0 7 3 6 9 11 4 15
3 7 12 12 5 7 0 9 9 12 14 11 22
6 15 20 12 5 3 9 0 9 12 14 7 18
12 16 14 11 4 6 9 9 0 11 13 10 21
15 19 24 14 7 9 12 12 11 0 2 12 24
17 21 26 16 9 11 14 14 13 2 0 10 26
12 18 23 13 6 4 11 7 10 12 10 0 19
23 29 34 24 17 15 22 18 21 24 26 19 0
经过的中间点矩阵
r =
1 2 2 7 7 6 7 8 7 7 7 6 6
1 2 3 4 7 7 7 1 7 7 7 7 7
2 2 3 2 2 2 2 2 9 2 2 2 2
5 2 2 4 5 5 5 5 5 5 5 5 5
7 7 7 4 5 6 7 6 9 10 11 6 6
1 5 5 5 5 6 5 8 5 5 5 12 13
1 2 2 5 5 5 7 1 5 5 5 5 5
1 1 1 6 6 6 1 8 6 6 6 6 6
5 5 3 5 5 5 5 5 9 5 5 5 5
5 5 5 5 5 5 5 5 5 10 11 11 5
5 5 5 5 5 5 5 5 5 10 11 12 5
6 6 6 6 6 6 6 6 6 11 11 12 6
6 6 6 6 6 6 6 6 6 6 6 6 13
最大距离的最小值ans
ans =
17
u为卫生站所在的行的序数
u =
5
所以最优修建卫生站的乡镇位置是V5
c为各点到两卫生站距离较小值的距离矩阵
c =
0 0 5 8 8 8 3 6 12 15 17 12 23
0 5 0 13 8 8 3 6 12 15 17 12 23
0 8 13 0 7 8 3 6 11 14 16 12 23
0 9 14 7 0 2 3 5 4 7 9 6 17
0 9 14 9 2 0 3 3 6 9 11 4 15
0 7 12 12 5 7 0 6 9 12 14 11 22
0 9 14 12 5 3 3 0 9 12 14 7 18
0 9 14 11 4 6 3 6 0 11 13 10 21
0 9 14 14 7 8 3 6 11 0 2 12 23
0 9 14 15 8 8 3 6 12 2 0 10 23
0 9 14 13 6 4 3 6 10 12 10 0 19
0 9 14 15 8 8 3 6 12 15 17 12 0
9 0 0 8 12 14 7 15 14 19 21 18 29
9 0 5 0 7 9 7 12 11 14 16 13 24
8 0 5 7 0 2 5 5 4 7 9 6 17
8 0 5 8 2 0 7 3 6 9 11 4 15
3 0 5 8 5 7 0 9 9 12 14 11 22
6 0 5 8 5 3 7 0 9 12 14 7 18
9 0 5 8 4 6 7 9 0 11 13 10 21
9 0 5 8 7 9 7 12 11 0 2 12 24
9 0 5 8 9 11 7 14 13 2 0 10 26
9 0 5 8 6 4 7 7 10 12 10 0 19
9 0 5 8 12 14 7 15 16 19 21 18 0
14 5 0 0 7 9 12 12 11 14 16 13 24
8 5 0 7 0 2 5 5 4 7 9 6 17
8 5 0 9 2 0 7 3 6 9 11 4 15
3 5 0 12 5 7 0 9 9 12 14 11 22
6 5 0 12 5 3 9 0 9 12 14 7 18
12 5 0 11 4 6 9 9 0 11 13 10 21
14 5 0 13 7 9 12 12 11 0 2 12 24
14 5 0 13 9 11 12 14 13 2 0 10 26
12 5 0 13 6 4 11 7 10 12 10 0 19
14 5 0 13 17 15 12 18 14 24 26 19 0
8 8 13 0 0 2 5 5 4 7 9 6 17
8 8 13 0 2 0 7 3 6 9 11 4 15
3 7 12 0 5 7 0 9 9 12 14 11 22
6 8 13 0 5 3 9 0 9 12 14 7 18
12 8 13 0 4 6 9 9 0 11 13 10 21