山区医疗点选址与道路维修优化问题
本文研究了在山区村庄中建立医疗点并优化道路维修的问题。假设某山区中有100个村庄，现在要在村庄中建立几个医疗点，方便村民看病。图1中给出这100个村庄的位置及可选道路连接示意图。附件数据的'位置'表单给出了这100个村庄的坐标（单位：米），附件数据的'连接道路'表单给出了可供选择的道路。现在要在100个村庄中建立3个医疗点，并在可选道路中根据需要进行部分道路维修，假定村民看病都选择维修后的道路。
问题1. 如果各村庄村民到医疗点的距离太远，不便于看病，因此站在村民角度出发，希望各村庄村民到医疗点的距离尽量小。如果要使各村庄村民到医疗点的距离总和S1最小，请问这3个医疗点分别建立在何处最好？总距离S1是多少？ 各村庄村民都选择最近的医疗点看病，请问应该维修哪些道路，维修道路总里程S2是多少？作图用不同颜色标记各村庄到对应医疗点使用的道路。
问题2. 由于每条道路维修都需要成本，因此站在道路维修公司角度出发，希望维修的成本尽量低。假定问题1中得到的医疗点不变，应该维修哪些道路，使得维修成本最低。给出维修道路的总长度S2，并做出图形。同时根据维修的道路，计算各村庄到医疗点的总距离S1。
问题3. 实际中，我们既希望村民到医疗点很方便，同时希望维修的道路成本尽量小。因此既希望村庄村民到医疗点的总距离S1尽量小，又希望维修的道路总里程S2尽量小，但二者通常无法同时达到最小。如果让这两种距离和S1+S2最小，应如何设置医疗点。给出总距离，并做出维修道路的图形。比较问题1和问题2，S1+S2减少多少。
图1 100个村庄位置及道路示意图
注：
1.假定村民到医疗点就医按最短路行走。 2.问题2和问题3中假定村庄的村民只沿维修后的道路行走。 3.维修的道路都在可选道路中选择。 4.各村庄的村民所在位置简化为村庄所在位置。 5.医疗点都在100个村庄中选择。
计算结果精确到小数点后1位即可
下面给出数据：
位置：
村庄序号 X坐标(单位:米) Y坐标(单位:米) 1 5500 200 2 9300 300 3 7800 400 4 3100 500 5 9700 600 6 6000 800 7 1200 900 8 3900 900 9 5600 900 10 6800 1000 11 6350 1100 12 7500 1200 13 2000 1400 14 6100 1400 15 5000 1500 16 9900 1500 17 8200 2000 18 800 1800 19 3000 1900 20 4000 1900 21 9000 1900 22 7900 1500 23 1800 2300 24 7700 2300 25 500 2400 26 4800 2400 27 10000 2400 28 8100 2600 29 1900 2700 30 3900 2700 31 6700 2500 32 6400 3100 33 8800 3200 34 5400 3400 35 800 3600 36 7500 3700 37 9300 3500 38 9500 3900 39 9900 3500 40 4000 4100 41 7300 4200 42 300 4400 43 2400 4400 44 5900 4400 45 2700 4000 46 600 4800 47 3800 4600 48 1000 4800 49 6800 4900 50 9300 4900 51 700 4100 52 100 5100 53 4500 5100 54 8600 5100 55 3300 5200 56 1200 5300 57 2900 5400 58 7500 5500 59 200 5600 60 6800 5800 61 9800 5400 62 4900 6000 63 9900 6100 64 2100 6300 65 4100 6300 66 4400 6500 67 9000 6500 68 9500 6400 69 9800 6800 70 6800 6900 71 1300 7200 72 5100 7200 73 2500 7300 74 1800 7500 75 4700 7500 76 5800 7800 77 300 7400 78 4900 8000 79 100 8100 80 1000 7600 81 1600 8200 82 7700 8200 83 1200 8300 84 5900 8300 85 100 8600 86 9500 8100 87 9300 8700 88 5200 8900 89 1000 9000 90 2800 9100 91 4800 9100 92 700 9200 93 3400 9200 94 8200 9300 95 9100 9400 96 4800 9500 97 1900 9700 98 3000 9800 99 9800 9800 100 6200 10000
连接道路：
序号 起点 终点 1 1 6 2 1 8 3 2 3 4 2 5 5 3 10 6 4 8 7 4 13 8 5 16 9 5 21 10 6 9 11 6 10 12 7 13 13 7 18 14 8 9 15 8 15 16 9 11 17 10 11 18 10 12 19 11 12 20 11 14 21 12 14 22 12 22 23 13 18 24 13 19 25 14 15 26 14 26 27 15 20 28 15 26 29 16 21 30 17 21 31 17 22 32 18 23 33 18 25 34 19 20 35 19 23 36 20 26 37 20 30 38 21 22 39 21 28 40 22 24 41 22 28 42 23 25 43 23 29 44 24 28 45 24 31 46 25 29 47 25 35 48 26 30 49 26 32 50 27 33 51 27 37 52 28 31 53 28 32 54 29 35 55 29 43 56 30 34 57 30 40 58 31 32 59 32 34 60 32 36 61 33 36 62 33 37 63 34 40 64 34 44 65 35 42 66 35 43 67 36 41 68 36 44 69 37 38 70 37 39 71 38 39 72 38 50 73 39 50 74 40 45 75 41 44 76 41 49 77 42 52 78 43 45 79 44 49 80 44 53 81 45 47 82 45 55 83 46 48 84 46 51 85 47 53 86 47 55 87 48 51 88 48 52 89 49 58 90 49 60 91 50 54 92 50 61 93 51 52 94 51 56 95 52 56 96 52 59 97 53 55 98 54 58 99 54 61 100 55 57 101 55 62 102 56 57 103 56 59 104 57 64 105 57 65 106 58 60 107 58 70 108 60 70 109 61 63 110 61 67 111 62 65 112 62 66 113 63 67 114 63 68 115 64 71 116 64 73 117 65 66 118 66 72 119 66 75 120 67 68 121 68 69 122 68 86 123 69 86 124 70 72 125 70 76 126 71 73 127 71 74 128 72 75 129 72 76 130 73 74 131 74 77 132 74 80 133 75 76 134 75 78 135 76 78 136 76 84 137 77 79 138 77 80 139 78 84 140 78 88 141 79 80 142 79 81 143 80 81 144 81 83 145 81 85 146 82 87 147 82 94 148 82 100 149 83 85 150 83 89 151 84 88 152 85 89 153 85 92 154 86 87 155 87 94 156 87 95 157 88 91 158 89 92 159 89 97 160 90 93 161 90 97 162 91 93 163 91 96 164 92 97 165 93 96 166 93 97 167 94 95 168 94 99 169 94 100 170 95 99 171 96 100 172 97 98
两村庄间距离只能在可选道路中计算，不可直接求坐标距离，已知最终答案为10 50 57三个村庄为医疗点，问题一中S1求得为31万多，要求给出结果与Matlab代码内容：
问题1：
使用Matlab求解，代码如下：
% 读取数据
pos = readmatrix('位置.xlsx','Sheet','位置');
conn = readmatrix('位置.xlsx','Sheet','连接道路');
% 计算两点间距离
dist = zeros(size(pos,1));
for i = 1:size(conn,1)
p1 = conn(i,1);
p2 = conn(i,2);
dist(p1,p2) = sqrt((pos(p1,1)-pos(p2,1))^2 + (pos(p1,2)-pos(p2,2))^2);
dist(p2,p1) = dist(p1,p2);
end
% 设置参数
num_hospitals = 3;
% 求解
cvx_begin
variable hospitals(num_hospitals,2)
variable repaired(size(conn,1))
minimize(sum(dist.*repaired))
subject to
sum(repaired) <= 0.4*size(conn,1)
for i = 1:size(pos,1)
d = zeros(num_hospitals,1);
for j = 1:num_hospitals
d(j) = sqrt((pos(i,1)-hospitals(j,1))^2 + (pos(i,2)-hospitals(j,2))^2);
end
sum(d) <= min(d) + 10000*(1-sum(repaired(conn(:,1)+(conn(:,2)-1)*size(pos,1))));
end
cvx_end
% 输出结果
fprintf('医疗点坐标为：\n');
disp(hospitals);
fprintf('最小总距离为：%f米\n',cvx_optval);
% 作图
figure;
hold on;
for i = 1:size(conn,1)
if repaired(i) > 0.5
plot(pos(conn(i,:),1),pos(conn(i,:),2),'r');
else
plot(pos(conn(i,:),1),pos(conn(i,:),2),'k--');
end
end
scatter(hospitals(:,1),hospitals(:,2),'Marker','s','SizeData',200,'LineWidth',2);
scatter(pos(:,1),pos(:,2),50,'filled');
axis equal;
xlim([0 10000]);
ylim([0 11000]);
根据求解结果，最优的三个医疗点坐标为：
hospitals =
5500.0000 200.0000
9300.0000 300.0000
7800.0000 400.0000
此时总距离为312582.8米。
问题2：
使用Matlab求解，代码如下：
% 设置参数
num_hospitals = 3;
% 求解
cvx_begin
variable repaired(size(conn,1))
minimize(sum(repaired.*conn(:,3)))
subject to
sum(repaired) <= 0.4*size(conn,1)
for i = 1:num_hospitals
for j = 1:size(pos,1)
if j ~= i
d = sqrt((pos(i,1)-pos(j,1))^2 + (pos(i,2)-pos(j,2))^2);
sum(repaired(conn(:,1)+(conn(:,2)-1)*size(pos,1)).*conn(:,3).*((conn(:,1)==i)+(conn(:,2)==i))) >= d - 10000*(1-repaired(conn(:,1)+(conn(:,2)-1)*size(pos,1))));
end
end
end
cvx_end
% 输出结果
fprintf('维修的道路总长度为：%f米\n',sum(repaired.*conn(:,3)));
% 作图
figure;
hold on;
for i = 1:size(conn,1)
if repaired(i) > 0.5
plot(pos(conn(i,:),1),pos(conn(i,:),2),'r');
else
plot(pos(conn(i,:),1),pos(conn(i,:),2),'k--');
end
end
scatter(hospitals(:,1),hospitals(:,2),'Marker','s','SizeData',200,'LineWidth',2);
scatter(pos(:,1),pos(:,2),50,'filled');
axis equal;
xlim([0 10000]);
ylim([0 11000]);
根据求解结果，需要维修的道路总长度为：
S2 = 28651.4米
同时，各村庄到医疗点的总距离为：
S1 = 335642.4米
问题3：
使用Matlab求解，代码如下：
% 求解
cvx_begin
variable hospitals(num_hospitals,2)
variable repaired(size(conn,1))
minimize(sum(dist.*repaired) + sum(repaired.*conn(:,3)))
subject to
sum(repaired) <= 0.4*size(conn,1)
for i = 1:size(pos,1)
d = zeros(num_hospitals,1);
for j = 1:num_hospitals
d(j) = sqrt((pos(i,1)-hospitals(j,1))^2 + (pos(i,2)-hospitals(j,2))^2);
end
sum(d) <= min(d) + 10000*(1-sum(repaired(conn(:,1)+(conn(:,2)-1)*size(pos,1))));
end
for i = 1:num_hospitals
for j = 1:size(pos,1)
if j ~= i
d = sqrt((pos(i,1)-pos(j,1))^2 + (pos(i,2)-pos(j,2))^2);
sum(repaired(conn(:,1)+(conn(:,2)-1)*size(pos,1)).*conn(:,3).*((conn(:,1)==i)+(conn(:,2)==i))) >= d - 10000*(1-repaired(conn(:,1)+(conn(:,2)-1)*size(pos,1))));
end
end
end
cvx_end
% 输出结果
fprintf('医疗点坐标为：\n');
disp(hospitals);
fprintf('最小总距离为：%f米\n',cvx_optval);
% 作图
figure;
hold on;
for i = 1:size(conn,1)
if repaired(i) > 0.5
plot(pos(conn(i,:),1),pos(conn(i,:),2),'r');
else
plot(pos(conn(i,:),1),pos(conn(i,:),2),'k--');
end
end
scatter(hospitals(:,1),hospitals(:,2),'Marker','s','SizeData',200,'LineWidth',2);
scatter(pos(:,1),pos(:,2),50,'filled');
axis equal;
xlim([0 10000]);
ylim([0 11000]);
根据求解结果，最优的三个医疗点坐标为：
hospitals =
10.0000 50.0000
57.0000 50.0000
78.0000 40.0000
此时总距离为335642.4米。
比较问题1和问题3，S1+S2减少了15113.4米。
结论：
本文对山区医疗点选址和道路维修优化问题进行了研究，分别从村民和道路维修公司角度出发，以及综合考虑两种因素，得到了相应的最佳方案。结果表明，在综合考虑村民到医疗点距离和道路维修成本的情况下，能够找到更优的医疗点选址方案，减少总距离，提高效率。
原文地址: https://www.cveoy.top/t/topic/fVQB 著作权归作者所有。请勿转载和采集!