最小费用流

一、直观理解：既要完成输送任务，又要花钱最少

最大流只关心“能不能运到上限”。**最小费用流（Min-Cost Flow）**在满足供应、需求与容量的前提下，使

$$\sum_{(u,v)} cost(u,v)\cdot f(u,v)$$

最小。

典型故事：

• 多个工厂有产量，多个市场有需求，道路有运力与单位运费，求总运费最小方案；
• 任务分配可看成二分图上的费用流；
• 带费用的疏散或通信路由。

当只要求从 $s$ 到 $t$ 送固定流量 $F$ 且费用最小，称为最小费用最大流的“指定流量”版本；先增广费用最小的路径是经典思路。

二、适用场景与优缺点

类型	说明
适用场景	运输问题；分配问题；带容量与线性费用的网络规划；需同时给流量与总费用。
核心优点	比纯 LP 叙述更贴网络；有组合算法；结果可解释到边；与匹配/指派统一。
局限与缺点	费用非线性/凹凸需另法；负环要处理；实现比最大流复杂；大规模需高效算法或求解器。

三、核心原理

1. 模型

对每个点 $b(i)$：供应 $>0$，需求 $<0$，中间 $=0$，且 $\sum b(i)=0$。

$$\begin{aligned} \min\quad &\sum_{(i,j)} c_{ij}f_{ij}\\ \mathrm{s.t.}\quad &\sum_j f_{ij}-\sum_j f_{ji}=b(i)\\ &0\le f_{ij}\le u_{ij} \end{aligned}$$

2. 连续最短路增广（Successive Shortest Path）

在残量网中找关于单位费用的最短路（可用势函数处理负权），沿路按瓶颈增广，直到供需满足。费用不可为负环。

3. 消环

任意可行流，若费用负环存在，沿环增广可降费；最优流的残量网无负费环。

4. 与 LP

运输问题单纯形/网络单纯形与上述组合算法等价于求解该 LP。MATLAB 可用 intlinprog/linprog 建模验证。

四、关键决策

1. 目标是最大流还是固定需求

先明确 $b(i)$ 或 $s$-$t$ 指定流量。

2. 费用单位

与容量量纲独立；报告总费用单位。

3. 负费用

允许“收益边”，但要保证无负环或可检测。

4. 验证

守恒、容量、目标值；与 LP 对照；对小网络枚举。

五、MATLAB 示例

% 运输：供应点1,2 需求点3,4
% 节点 b: +20,+10,-15,-15
% 边: 1->3,1->4,2->3,2->4 容量与费用
% 用 linprog 解最小费用流

% 变量 f13,f14,f23,f24
c = [2; 4; 3; 1];          % 费用
Aeq = [
    1 1 0 0                 % 节点1 流出
    0 0 1 1                 % 节点2
   -1 0 -1 0                % 节点3 流入为正？用流出-流入=b
    0 -1 0 -1
];
% 定义流向：f13从1到3，对点1贡献+ f，对点3贡献-
% b = [20;10;-15;-15]
beq = [20;10;-15;-15];
lb = zeros(4,1);
ub = [25;25;25;25];         % 容量

opts = optimoptions("linprog", "Display","none");
[f, fval] = linprog(c, [], [], Aeq, beq, lb, ub, opts);
disp("边流量 [f13 f14 f23 f24]:"); disp(f');
fprintf("最小总费用=%g\n", fval);

% 残量/最短路增广思想演示（s-t 指定流量）
% 小网络：1->2 cost2 cap2; 1->3 cost4 cap3; 2->3 cost1 cap2; 2->4 cost5 cap3; 3->4 cost2 cap4
% 求送流量 F=3 的最小费用
edges = [
% u v cap cost
1 2 2 2
1 3 3 4
2 3 2 1
2 4 3 5
3 4 4 2
];
Fneed = 3;
% 使用多次 Bellman-Ford 找最小费用增广（教学）
n=4; flow=zeros(n); sent=0; totalCost=0;
while sent < Fneed - 1e-9
    % 残量费用图
    dist=inf(1,n); dist(1)=0; pre=zeros(1,n);
    for it=1:n-1
        updated=false;
        for e=1:size(edges,1)
            u=edges(e,1); v=edges(e,2); cap=edges(e,3); cos=edges(e,4);
            % 正向残量
            if flow(u,v) < cap && dist(v) > dist(u)+cos + 1e-12
                dist(v)=dist(u)+cos; pre(v)=u; pev(v)=cos; dir(v)=1; %#ok<SAGROW>
                updated=true;
            end
            % 反向
            if flow(u,v) > 0 && dist(u) > dist(v)-cos + 1e-12
                dist(u)=dist(v)-cos; pre(u)=v; pev(u)=-cos; dir(u)=-1;
                updated=true;
            end
        end
        if ~updated, break; end
    end
    if ~isfinite(dist(4))
        error("不可行：无法继续增广");
    end
    % 瓶颈
    add = Fneed-sent; v=4; path=[];
    while v~=1
        u=pre(v); path=[u v; path]; %#ok<AGROW>
        % 找容量
        ee = find(edges(:,1)==u & edges(:,2)==v,1);
        if ~isempty(ee)
            add=min(add, edges(ee,3)-flow(u,v));
        else
            % 反向：对应原边 v->u
            ee = find(edges(:,1)==v & edges(:,2)==u,1);
            add=min(add, flow(v,u));
        end
        v=u;
    end
    % 增广
    v=4;
    while v~=1
        u=pre(v);
        ee = find(edges(:,1)==u & edges(:,2)==v,1);
        if ~isempty(ee)
            flow(u,v)=flow(u,v)+add; totalCost=totalCost+add*edges(ee,4);
        else
            flow(v,u)=flow(v,u)-add; ee=find(edges(:,1)==v & edges(:,2)==u,1);
            totalCost=totalCost-add*edges(ee,4);
        end
        v=u;
    end
    sent=sent+add;
end
fprintf("指定流量最小费用（手写增广）=%g, 实际送达=%g\n", totalCost, sent);
disp(flow);

六、如何解释结果

1. 供应需求、容量、费用单位；
2. 总费用与各边流量表；
3. 是否达最大必要流量/是否可行；
4. 瓶颈与高费用边；
5. 灵敏度（费用或产能变化）；
6. 算法或求解器。

七、常见误区

1. 先最大流再在最大流中选费用

指定流量未必等于最大流；即使是，也要用费用准则增广，不能任意最大流。

2. 供需不平衡未处理

不可行或需虚拟源汇。

3. 忽略负环

“最优”可能不是。

4. 只给总费用不给方案

工程上无法执行。

八、小结

最小费用流的核心是：

在容量与供需约束下，选择总费用最小的可行流。

它是运输与分配类赛题的网络标准模型。可用连续最短路增广或 LP 求解，并用守恒与无负费环验证最优性叙事。