有上下界流

一、直观理解：边不仅不能超载，有时还必须“至少流过多少”

经典最大流约束是 $0\le f_e\le c_e$。现实中常见：

• 管道有最小开工流量（不开就得关，开了至少某值）；
• 合同规定至少运输量；
• 环流问题中边有上下界。

于是约束变为

$$l_e\le f_e\le u_e$$

问题包括：

1. 可行流：是否存在满足上下界与守恒的流；
2. 有上下界的最大流/最小流；
3. 循环流（无源汇，$b=0$）的可行性。

关键技巧是：通过变换化成普通最大流/循环流问题，而不是从零发明算法。

二、适用场景与优缺点

类型	说明
适用场景	最小运量约束；必须经过的“保底流量”；带上下界的循环调度；可行性诊断。
核心优点	归约清晰；可判断不可行并定位紧张边；与普通 max-flow 工具链兼容。
局限与缺点	建模步骤易错（平衡、附加源汇）；下界过大导致不可行需合理解释；费用版本更复杂。

三、核心原理

1. 下界消除（可行流变换）

令 $f_e=f'_e+l_e$，则 $0\le f'_e\le u_e-l_e$，但点守恒会出现额外供需：

$$b'(v)=\sum_{e\ \mathrm{out}}l_e-\sum_{e\ \mathrm{in}}l_e$$

（符号依 $b$ 定义约定。）原守恒 + 下界强制 = 新网络上带供应需求的可行流问题。

2. 用最大流检验可行性

构造附加源 $s^*$、汇 $t^*$：

• 对 $b'(v)>0$（多余流出要求）的点，$v\to t^*$ 容量 $b'(v)$；
• 对 $b'(v)<0$ 的点，$s^*\to v$ 容量 $-b'(v)$；
• 原边容量改为 $u_e-l_e$。

若 $s^*\to t^*$ 最大流等于所有正需求之和，则存在可行 $f'$，从而 $f=f'+l$ 可行。

3. 有上下界 $s$-$t$ 最大流

先找一可行流 $f_0$，再在残量（对上界与下界）上对普通最大流增广；或使用已知归约一次性建模。

4. 不可行时

最大流小于需求总量 ⇒ 不存在可行流。可结合最小割解释“哪侧下界/上界冲突”。

四、关键决策

1. 先可行性，再优化

下界太猛时最优化无意义。

2. 下界是否必须

软下界可用罚费用；硬下界用本节模型。

3. 与费用结合

有上下界最小费用流：先化下界，再跑 min-cost flow。

4. 验证

逐边 $l\le f\le u$，中间点守恒，源汇差额正确。

五、MATLAB 示例

% 例：边有下界的 s-t 网络，检查可行并求最大流（教学归约）
% 点 1=s, 4=t
% 边列表: u v low up
E = [
1 2 1 4
1 3 1 3
2 3 0 2
2 4 2 5
3 4 1 4
];
n = 4; s=1; t=4;

% ---- 1) 寻找可行流：循环+ s-t 可先加 t->s 无限边把问题变循环 ----
% 这里演示“消除下界 + 附加源汇”检查一般可行循环/平衡
low = E(:,3); up = E(:,4);
cap2 = up - low;           % 新容量
% 每个点因下界产生的不平衡：out low - in low
b = zeros(n,1);
for e=1:size(E,1)
    u=E(e,1); v=E(e,2); L=low(e);
    b(u)=b(u)+L;  % 被迫多流出 L
    b(v)=b(v)-L;  % 被迫多流入 L
end
% 我们需要额外流来抵消 b：若 b(v)>0，v 需要额外流入 b(v)
% 构造 s* = n+1, t* = n+2
ss = n+1; tt = n+2;
se = []; te = []; ca = [];
% 原边（变换后）
for e=1:size(E,1)
    se(end+1)=E(e,1); te(end+1)=E(e,2); ca(end+1)=cap2(e); %#ok<SAGROW>
end
need = 0;
for v=1:n
    if b(v) > 0
        % v 被迫净流出过多，需要从网络得到补偿：v -> t*
        se(end+1)=v; te(end+1)=tt; ca(end+1)=b(v);
        need = need + b(v);
    elseif b(v) < 0
        % v 被迫净流入过多，需要排出：s* -> v
        se(end+1)=ss; te(end+1)=v; ca(end+1)=-b(v);
    end
end
G = digraph(se, te, ca);
mf = maxflow(G, ss, tt);
fprintf("可行性检验最大流=%g, 需要=%g => %s\n", mf, need, ...
    string(abs(mf-need)<1e-8));

% ---- 2) 若可行，构造一个具体可行流 f = f' + low ----
[mf2, GF] = maxflow(G, ss, tt);
% 从 GF 取原边流量作为 f'
fprime = zeros(size(E,1),1);
for e=1:size(E,1)
    u=E(e,1); v=E(e,2);
    % 在 GF 中找边
    eid = findedge(GF, u, v);
    if eid > 0
        fprime(e) = GF.Edges.Weight(eid); % 注意：不同版本 maxflow 返回的 GF 含义请核对
    end
end
% 兼容：若 Weight 不是流量，改用手写 EK 更稳；这里给出解析小例的手算可行流
% 直接给出满足下界的可行流示例：
f = low; % 先全部取下界
% 检查 b 是否已被残量网络解决；教学上打印下界流的不平衡
bal = zeros(n,1);
for e=1:size(E,1)
    bal(E(e,1))=bal(E(e,1))-f(e);
    bal(E(e,2))=bal(E(e,2))+f(e);
end
fprintf("仅取下界时的净流入:\n"); disp(bal');

% 手写：在无附加点的残量上找可行调整（对小例子用 linprog）
% 变量 f_e，约束 l<=f<=u，中间点2,3守恒，最大化 t 净流入
% 点2: f12 - f23 - f24 = 0
% 点3: f13 + f23 - f34 = 0
% max (f24 + f34)  s.t. 上述 + bounds  （s 流出自由）
c = -[0;0;0;1;1]; % 对应 f12 f13 f23 f24 f34 最大化 f24+f34
Aeq = [
1 0 -1 -1 0
0 1 1 0 -1
];
beq = [0;0];
lb = low; ub = up;
[ff, fval] = linprog(c, [], [], Aeq, beq, lb, ub, optimoptions("linprog","Display","none"));
if isempty(ff)
    disp("linprog 未找到有上下界可行流");
else
    disp("边流量:"); disp(ff');
    fprintf("s-t 流量=%g\n", -fval);
    % 验证上下界
    assert(all(ff>=lb-1e-8 & ff<=ub+1e-8));
end

说明：有上下界流的工程实现重在归约正确。赛题中用 linprog/maxflow 按本节变换建模，并打印每条边的 $[l,u]$ 与 $f$，是最稳妥写法。

六、如何解释结果

1. 每条边下界/上界的业务理由；
2. 可行性结论；若不可行，指出冲突割/过紧下界；
3. 可行方案流量表；
4. 若做最大流，给出有上下界约束下的最大输送量；
5. 与“无下界”模型的对照。

七、常见误区

1. 只把下界当初始流却不再检验守恒

取 $f=l$ 一般不守恒。

2. 变换时 $b(v)$ 符号弄反

可行性判断全错。

3. 上界小于下界

数据错误应先清洗。

4. 不可行时硬报最大流数字

应先诊断约束。

八、小结

有上下界流的核心是：

将 $l_e\le f_e\le u_e$ 通过 $f=f'+l$ 化为普通容量网络上的供需可行流/最大流问题。

它让“保底运量”类约束变得可计算、可诊断。建模时把变换步骤、可行性检验与最终流量表写全，才算完成。