用Octave计算最小费用问题
广告
{{v.name}}
最小费用问题是运筹学中网络流优化的核心问题，全称为最小费用最大流问题（Minimum Cost Maximum Flow, MCMF），也可简化为固定流量的最小费用流问题。其核心是在一个带容量和单位流量费用的网络中，找到从源点到汇点的流分配方案，满足流量要求（最大流/固定流）的同时，使得总运输/传输费用最小。
该问题广泛应用于物流配送、资源调度、交通规划、供应链优化等场景（如：从仓库到门店的货物运输，各路径有运输容量和单位运费，求运量最大时总运费最低，或固定运量时总运费最低）。
一、 最小费用问题的核心概念（网络流基础）
1. 节点集 \(V\)：包含源点 \(s\)（流量出发节点，无入边）、汇点 \(t\)（流量终止节点，无出边）、中间节点；
2. 边集 \(E\)：每条有向边 \((i,j)\) 关联两个参数：
- 容量 \(c_{ij}\)：边 \((i,j)\) 最多可通过的流量（\(c_{ij} \ge 0\)）；
- 单位费用 \(w_{ij}\)：边 \((i,j)\) 每通过1单位流量的费用（\(w_{ij}\) 可正可负，实际问题中多为正）；
3. 流 \(f_{ij}\)：边 \((i,j)\) 上实际通过的流量，满足流量守恒和容量约束：
- 容量约束：\(0 \le f_{ij} \le c_{ij}\)；
- 流量守恒：对任意中间节点 \(k\)，流入流量 = 流出流量，即 \(\sum_{i}f_{ik} = \sum_{j}f_{kj}\)；
4. 总流量 \(v\)：从源点 \(s\) 流出的总流量（等于汇点 \(t\) 流入的总流量）；
5. 总费用 \(Cost\)：所有边的流量与单位费用乘积之和，\(Cost = \sum_{(i,j) \in E} f_{ij} \cdot w_{ij}\)。
二、 最小费用问题的分类
1. 最小费用最大流：求从 \(s\) 到 \(t\) 的最大可行总流量 \(v_{max}\)，且在此流量下总费用最小（最常用）；
2. 固定流量的最小费用流：求从 \(s\) 到 \(t\) 的固定总流量 \(v_0\)（\(v_0 \le v_{max}\)），且总费用最小（可视为最大流问题的特例）。
三、 核心求解算法：连续最短路算法（Successive Shortest Path）
这是求解最小费用流最经典、最易理解的算法，核心思想是“每次找从 \(s\) 到 \(t\) 的最小费用增广路，沿增广路增广流量，直到无法增广（达到最大流）或满足固定流量要求”。
算法核心原理
1. 残量网络：对原网络的每条边 \((i,j)\)，定义残量边和反向边，用于描述流量的可调整空间：
- 原边残量：\(r_{ij} = c_{ij} - f_{ij}\)（还能增广的流量），单位费用仍为 \(w_{ij}\)；
- 反向边 \((j,i)\)：用于流量“回退”，残量 \(r_{ji} = f_{ij}\)（已流的流量可退回），单位费用为 \(-w_{ij}\)（退回流量会减少总费用）。
2. 增广路：残量网络中从 \(s\) 到 \(t\) 的一条有向路径，路径上所有边的残量 \(r_{ij} > 0\)，可沿此路径增加流量；
3. 最小费用增广路：残量网络中从 \(s\) 到 \(t\) 的最短路（路径总单位费用最小），沿此路增广流量，能保证每一步增广的单位费用最低，最终总费用最小。
算法步骤（最小费用最大流）
设初始流 \(f_{ij}=0\)，总流量 \(v=0\)，总费用 \(Cost=0\)：
1. 构建残量网络：根据当前流 \(f_{ij}\)，计算所有边的残量 \(r_{ij}\) 和反向边，得到残量网络 \(G_f\)；
2. 找最小费用增广路：在残量网络 \(G_f\) 中，以单位费用 \(w_{ij}\) 为边权，求从 \(s\) 到 \(t\) 的最短路（可用Dijkstra算法，若有负费用边用SPFA/Bellman-Ford算法）；
3. 判断是否存在增广路：若不存在，算法终止，当前 \(v\) 为最大流，\(Cost\) 为最小费用；若存在，执行步骤4；
4. 确定增广流量：增广路的最大可增广流量 \(\Delta f = \min\{r_{ij} | (i,j) 属于增广路\}\)（路径上残量的最小值）；
5. 增广流量：对增广路上的每条边 \((i,j)\)，更新流量 \(f_{ij} = f_{ij} + \Delta f\)；对反向边 \((j,i)\)，更新 \(f_{ji} = f_{ji} - \Delta f\)；
6. 更新总流量和总费用：\(v = v + \Delta f\)，\(Cost = Cost + \Delta f \times\) 增广路的总单位费用；
7. 重复步骤1-6，直到无增广路。
固定流量的最小费用流调整
若需求固定流量 \(v_0\)，则在步骤5中，将增广流量改为 \(\Delta f = \min\{\text{原增广流量}, v_0 - v\}\)，当 \(v = v_0\) 时直接终止算法，此时的 \(Cost\) 即为固定流量下的最小费用。
例子：计算最小费用最大流
网络参数（源点\(s=1\)，汇点\(t=4\)）
某工厂生产\(x_1\)、\(x_2\)两种产品，已知：
| 有向边 \((i,j)\) | 容量 \(c_{ij}\) | 单位费用 \(w_{ij}\) |
|----------------|---------------|-------------------|
| (1,2) | 3 | 2 |
| (1,3) | 2 | 1 |
| (2,3) | 2 | 3 |
| (2,4) | 3 | 4 |
| (3,4) | 4 | 2 |
初始状态：\(f_{ij}=0\)，\(v=0\)，\(Cost=0\)。
第1次迭代
1. 残量网络：所有原边残量=容量，反向边残量=0；
2. 最小费用增广路：\(1 \rightarrow 3 \rightarrow 4\)，路径总费用=1+2=3；
3. 增广流量：\(\Delta f = \min\{2,4\} = 2\)；
4. 更新流量：\(f_{13}=2\)，\(f_{34}=2\)；
5. 总流量：\(v=2\)，总费用：\(Cost=2×3=6\)。
第2次迭代
1. 残量网络：\((1,3)\)残量=0，反向边(3,1)残量=2、费用=-1；\((3,4)\)残量=2；其余原边残量不变；
2. 最小费用增广路：\(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\)，路径总费用=2+3+2=7；
3. 增广流量：\(\Delta f = \min\{3,2,2\} = 2\)；
4. 更新流量：\(f_{12}=2\)，\(f_{23}=2\)，\(f_{34}=4\)（满容量）；
5. 总流量：\(v=4\)，总费用：\(Cost=6+2×7=20\)。
第3次迭代
1. 残量网络：\((3,4)\)残量=0，反向边(4,3)残量=4、费用=-2；\((2,3)\)残量=0；\((1,2)\)残量=1；\((2,4)\)残量=3；
2. 最小费用增广路：\(1 \rightarrow 2 \rightarrow 4\)，路径总费用=2+4=6；
3. 增广流量：\(\Delta f = \min\{1,3\} = 1\)；
4. 更新流量：\(f_{12}=3\)（满容量），\(f_{24}=1\)；
5. 总流量：\(v=5\)，总费用：\(Cost=20 + 1×6=26\)。
第4次迭代
1. 残量网络：所有从\(s=1\)出发的边均满容量（残量=0），无增广路；
2. 算法终止，最大流\(v_{max}=5\)，最小总费用\(Cost=26\)。
由于实际问题中可能存在负费用反向边，选择SPFA算法（队列优化的Bellman-Ford）求解残量网络的最短路，代码支持通用带费用网络，可直接输入边集、容量、费用，输出最大流和最小费用，也可调整为固定流量求解。
代码如下：
function [max_flow, min_cost, flow_matrix] = min_cost_max_flow(n, s, t, edges, c, w, fix_flow)
% 输入参数：
% n: 节点总数, s: 源点, t: 汇点（节点编号从1开始）
% edges: 边集，m×2矩阵，每行[i,j]表示有向边(i,j)
% c: 容量数组，m×1，对应edges的容量
% w: 单位费用数组，m×1，对应edges的单位费用
% fix_flow: 可选，固定流量要求，默认求最大流
% 输出参数：
% max_flow: 最大流/固定流量, min_cost: 最小总费用
% flow_matrix: n×n矩阵，flow_matrix(i,j)表示边(i,j)的实际流量
if nargin < 8
fix_flow = inf; % 默认求最大流
end
m = size(edges, 1);
flow = zeros(m, 1); % 每条边的实际流量
max_flow = 0;
min_cost = 0;
INF = 1e9;
while true
% 步骤1：SPFA求残量网络中s到t的最短路，记录前驱节点和边
dist = ones(n,1)*INF; % 各节点到s的最小费用
inqueue = false(n,1); % 节点是否在队列中
pre_node = zeros(n,1); % 前驱节点
pre_edge = zeros(n,1); % 前驱边的索引
dist(s) = 0;
q = [s];
inqueue(s) = true;
while ~isempty(q)
u = q(1);
q(1) = [];
inqueue(u) = false;
% 遍历所有边，找u的出边
for k = 1:m
i = edges(k,1);
j = edges(k,2);
r = c(k) - flow(k); % 原边残量
if i == u && r > 0 && dist(j) > dist(u) + w(k)
dist(j) = dist(u) + w(k);
pre_node(j) = u;
pre_edge(j) = k;
if ~inqueue(j)
q = [q; j];
inqueue(j) = true;
end
end
% 遍历反向边
if j == u && flow(k) > 0 && dist(i) > dist(u) - w(k)
dist(i) = dist(u) - w(k);
pre_node(i) = u;
pre_edge(i) = -k; % 负号表示反向边
if ~inqueue(i)
q = [q; i];
inqueue(i) = true;
end
end
end
end
% 步骤2：判断是否存在增广路
if dist(t) == INF
break;
end
% 步骤3：找增广路的最大可增广流量
delta_f = INF;
u = t;
while u ~= s
p = pre_edge(u);
if p > 0
% 原边增广
k = p;
delta_f = min(delta_f, c(k) - flow(k));
else
% 反向边增广
k = -p;
delta_f = min(delta_f, flow(k));
end
u = pre_node(u);
end
% 步骤4：固定流量调整
if max_flow + delta_f > fix_flow
delta_f = fix_flow - max_flow;
end
% 步骤5：增广流量，更新总流量和总费用
u = t;
while u ~= s
p = pre_edge(u);
if p > 0
k = p;
flow(k) = flow(k) + delta_f;
min_cost = min_cost + delta_f * w(k);
else
k = -p;
flow(k) = flow(k) - delta_f;
min_cost = min_cost - delta_f * w(k);
end
u = pre_node(u);
end
max_flow = max_flow + delta_f;
% 固定流量达到，提前终止
if max_flow == fix_flow
break;
end
end
% 构建流量矩阵
flow_matrix = zeros(n, n);
for k = 1:m
i = edges(k,1);
j = edges(k,2);
flow_matrix(i,j) = flow(k);
end
end
结果如下：
>> % 网络参数：4节点，源点1，汇点4
>> n = 4; s = 1; t = 4;
>> edges = [1 2; 1 3; 2 3; 2 4; 3 4]; % 边集
>> c = [3; 2; 2; 3; 4]; % 容量数组
>> w = [2; 1; 3; 4; 2]; % 单位费用数组
>> fix_flow = inf; % 求最大流，若固定流量改为具体值（如3）
>> [max_flow, min_cost, flow_matrix] = min_cost_max_flow(n, s, t, edges, c, w, fix_flow);
>> % 输出结果
>> fprintf('=== 最小费用最大流计算结果 ===\n');
>> fprintf('最大流：%d\n', max_flow);
>> fprintf('最小总费用：%d\n', min_cost);
>> fprintf('边流量矩阵（行i，列j表示边(i,j)的流量）：\n');
>> disp(flow_matrix);
=== 最小费用最大流计算结果 ===
最大流：5
最小总费用：24
边流量矩阵（行i，列j表示边(i,j)的流量）：
0 3 2 0
0 0 0 3
0 0 0 2
0 0 0 0
