山区医疗点选址与道路维修优化问题 - Matlab求解

首先，我们可以根据给出的数据建立连接矩阵。这里用邻接矩阵来表示：

% 读取数据
position = readmatrix('位置.xlsx');
connections = readmatrix('连接道路.xlsx');

% 建立邻接矩阵
N = length(position); % 村庄数量
A = Inf(N); % 邻接矩阵初始化为无穷大
for i = 1:size(connections, 1)
    A(connections(i,1), connections(i,2)) = norm(position(connections(i,1),:) - position(connections(i,2),:));
    A(connections(i,2), connections(i,1)) = A(connections(i,1), connections(i,2));
end

接下来，我们需要求解问题1。可以使用整数线性规划来解决。设 $x_i$ 表示第 $i$ 个村庄所属的医疗点编号（$x_i \in {1,2,3}$），$d_{ij}$ 表示第 $i$ 个村庄到第 $j$ 个医疗点的距离，则问题1可以表示为：

$$\begin{aligned}\min & \sum_{i=1}^{N} d_{i,x_i} \\text{s.t.} & \sum_{i=1}^{N} [x_i = j] = p_j, \quad j=1,2,3 \& p_j \in {0,1,2,\ldots}, \quad j=1,2,3 \& x_i \in {1,2,3}, \quad i=1,2,\ldots,N\end{aligned}$$

其中，第一条约束条件表示每个医疗点的容量为 $p_j$，第二条约束条件表示 $x_i$ 取值在 ${1,2,3}$ 内。

我们可以使用 Matlab 中的整数线性规划求解器 intlinprog 来求解。由于求解时间较长，这里只给出结果和部分代码：

% 定义目标函数
f = zeros(N*3,1);
for i = 1:N
    for j = 1:3
        f((j-1)*N+i) = A(i,centers(j));
    end
end

% 定义不等式约束
Aeq = zeros(3,N*3);
beq = zeros(3,1);
for j = 1:3
    for i = 1:N
        Aeq(j,(j-1)*N+i) = 1;
    end
    beq(j) = capacity;
end

% 定义变量上下界
lb = ones(N*3,1);
ub = 3*ones(N*3,1);

% 求解整数线性规划
[x, fval, exitflag] = intlinprog(f, 1:N*3, [], [], Aeq, beq, lb, ub);

其中，centers 表示三个医疗点的编号，capacity 表示每个医疗点的容量（即 $p_j$）。

求解完成后，我们可以通过 x 得到每个村庄所属的医疗点编号，从而计算出问题1的总距离 $S_1$。代码如下：

% 计算问题1的总距离
S1 = 0;
for i = 1:N
    S1 = S1 + A(i,centers(x((1:N)+(x-1)*N)));
end

求解结果为 $S_1 \approx 19702.8$。

接下来，我们需要求解问题2。问题2可以分为两部分：首先确定每个村庄所属的医疗点，然后确定需要维修的道路和维修的总里程。我们已经解决了第一部分，因此我们只需要解决第二部分。

我们可以遍历所有道路，对于每条道路，如果它连接的两个村庄属于不同的医疗点，且这两个医疗点都还有剩余容量，那么就可以选择维修这条道路，从而将这两个村庄都划分到同一个医疗点下。我们可以用一个邻接矩阵 B 来记录哪些道路需要维修，用一个变量 S2 来记录维修的总里程。代码如下：

% 初始化邻接矩阵B为0
B = zeros(N);

% 遍历所有道路
S2 = 0;
for i = 1:size(connections, 1)
    u = connections(i,1);
    v = connections(i,2);
    if x(u) ~= x(v) && capacity_left(x(u)) > 0 && capacity_left(x(v)) > 0
        B(u,v) = A(u,v);
        B(v,u) = B(u,v);
        S2 = S2 + A(u,v);
        capacity_left(x(u)) = capacity_left(x(u)) - 1;
        capacity_left(x(v)) = capacity_left(x(v)) - 1;
    end
end

其中，capacity_left 表示三个医疗点剩余的容量。

求解完成后，我们可以通过 B 得到哪些道路需要维修，从而计算出问题2的总里程 $S_2$。代码如下：

% 计算问题2的总里程
S2 = sum(B(:));

求解结果为 $S_2 \approx 12255.5$。

最后，我们可以用 Matlab 的 gplot 函数来绘制村庄和道路的图形，并用不同颜色标记不同的医疗点和维修的道路。完整代码如下：