MATLAB 最小费用流问题解决口罩分配难题

本代码使用 MATLAB 语言解决最小费用流问题，通过将口罩充足家庭和缺乏口罩家庭之间的距离作为边权重，找到最优分配方案，并计算学校支付的总快递费用。

% 输入数据
data = [1 18 12 14 15;
        2 23 17 14 9;
        3 10 0 15 9;
        4 15 25 4 8;
        5 13 10 8 10;
        6 20 20 12 8;
        7 20 25 13 18;
        8 32 15 7 11;
        9 15 18 11 18;
        10 24 9 23 24;
        11 3 8 15 4;
        12 33 3 17 10;
        13 34 26 5 9;
        14 37 23 19 27;
        15 18 4 11 5;
        16 42 8 20 7;
        17 50 23 2 6;
        18 53 16 10 8;
        19 55 38 11 18;
        20 7 42 13 18];

% 计算差值
diffneed = data(:, 4) - data(:, 5);
diffneed = diffneed';

% 找出口罩充足的家庭
sufficient = find(diffneed >= 0);

% 找出缺乏口罩的家庭
deficient = find(diffneed < 0);

% 构建最小费用流问题
num_nodes = length(sufficient) + length(deficient) + 2; % 包括源点和汇点
num_edges = length(sufficient) * length(deficient) + length(sufficient) + length(deficient);

capacities = zeros(num_nodes, num_nodes);
costs = zeros(num_nodes, num_nodes);

% 设置源点到口罩充足家庭的边
for i = 1:length(sufficient)
    capacities(1, i+1) = Inf;
    costs(1, i+1) = 0;
end

% 设置缺乏口罩家庭到汇点的边
for i = 1:length(deficient)
    capacities(i+length(sufficient)+1, num_nodes) = Inf;
    costs(i+length(sufficient)+1, num_nodes) = 0;
end

% 设置口罩充足家庭到缺乏口罩家庭的边
for i = 1:length(sufficient)
    for j = 1:length(deficient)
        capacities(i+1, j+length(sufficient)+1) = 1;
        costs(i+1, j+length(sufficient)+1) = sqrt((data(deficient(j), 2) - data(sufficient(i), 2))^2 + (data(deficient(j), 3) - data(sufficient(i), 3))^2);
    end
end

% 使用整数线性规划解决问题
% 在 MATLAB 中，使用 intvar 函数需要先安装 YALMIP 工具箱
% 可以在 MATLAB 命令窗口输入以下命令进行安装：
% >> !pip install yalmip
% >> !yalmip('install')
% 然后在代码中添加以下语句进行加载：
% addpath(genpath('路径/yalmip')); % 将路径替换为 YALMIP 工具箱的安装路径
% 接着将 intvar 函数替换为 binvar 函数即可，因为我们只需要二进制变量，而不需要整数变量
x = binvar(num_edges, 1);
y = binvar(num_edges, 1);
Objective = sum(sum(costs.*y));
Constraints = [sum(x(1:length(sufficient))) == length(deficient), sum(x(length(sufficient)+1:end)) == length(sufficient)];
for i = 1:length(sufficient)
    Constraints = [Constraints, sum(x(i+1:length(sufficient):end)) == 1];
end
for j = 1:length(deficient)
    Constraints = [Constraints, sum(x(length(sufficient)+j:length(deficient):end)) == 1];
end
Constraints = [Constraints, y >= x];
Constraints = [Constraints, y <= x.*(length(sufficient)*length(deficient))];

ops = sdpsettings('solver','gurobi');
optimize(Constraints, Objective, ops);

% 计算学校支付的总快递费用
totalCost = value(Objective);

% 输出结果
disp(['学校支付的总快递费用为：', num2str(totalCost), '元']);

代码说明：

输入数据：data 矩阵包含每个家庭的编号、横坐标、纵坐标、拥有口罩数量和需求口罩数量。
计算差值：diffneed 向量计算每个家庭的口罩缺口。
找出充足家庭和缺乏家庭：sufficient 和 deficient 向量分别存储充足和缺乏家庭的索引。
构建最小费用流问题：
- num_nodes 表示节点数量，包括源点、汇点和每个家庭。
- num_edges 表示边数量，包括源点到充足家庭、充足家庭到缺乏家庭、缺乏家庭到汇点。
- capacities 和 costs 矩阵分别存储边的容量和成本。
使用整数线性规划求解：
- x 和 y 变量表示是否选择这条边。
- Objective 函数表示总成本。
- Constraints 表示约束条件。
输出结果：显示学校支付的总快递费用。

注意事项：

需要安装 YALMIP 工具箱才能使用 intvar 函数。
可以使用其他求解器，例如 CPLEX 或 MOSEK。
可以根据实际情况调整代码，例如添加其他约束条件或目标函数。

扩展：

可以将该代码应用于其他资源分配问题，例如物资分配、人员分配等。
可以考虑使用不同的距离计算方法，例如考虑道路距离、交通时间等。
可以使用可视化工具绘制网络图，更加直观地展示分配方案。