多商品流

多商品流（multicommodity flow）在同一个网络中同时运输多组具有各自起点、终点和需求的流量，并让它们共享边容量。“商品”指必须保持身份的一组需求，不一定是实物货品，也可以是通信会话、不同起讫点的交通或运输任务。

例如，两组需求分别从 $s_1$ 到 $t_1$、从 $s_2$ 到 $t_2$，都必须经过公共边 $u\to v$。这条边容量为三，而两组各需二。每组单独运输都可行，但同时需要四，超过共享容量，所以联合不可行。不能把容量三分别完整地分配给每一种商品。

两种商品在公共边上的流量必须相加后与容量比较。外围边容量可取至少二。

分商品守恒与共享约束

设商品编号为 $k=1,\dots ,K$，各有源点 $s_k$、汇点 $t_k$ 和需求 $d_k\ge 0$。变量 $f_e^k\ge 0$ 表示商品 $k$ 在有向边 $e$ 上的流量。每一种商品都分别满足 $$\sum _{e\in {\delta }^{+}(v)}{f}_e^k-\sum _{e\in {\delta }^{-}(v)}{f}_e^k=\{\begin{array}{cc}{d}_k,& v=s_k,\\ -d_k,& v=t_k,\\ 0,& \text{其他}.\end{array}$$ 而每条边的共享容量约束为 $$\sum _{k=1}^K{f}_e^k\le u_e.$$ 若单位费用为 $c_e^k$，总费用可以写为 $\sum _k\sum _e{c}_e^k{f}_e^k$。不要求整数、允许分流时，这是一组线性约束，可构成线性规划；要求整条商品走同一路径或要求整数流，则改变了可行域。

主例可将外围四条边容量都设为二，公共边容量三。商品一经过 $s_1,u,v,t_1$，商品二经过 $s_2,u,v,t_2$；商品守恒分别要求公共边流量为二、二，容量式却要求 $2+2\le 3$，直接失败。若需求改为一、二，公共边总流量三，沿各自路径运输就给出联合可行解。

合并需求会丢失配对身份

把全部商品流相加，总流仍满足按顶点合并的供需守恒。但从合并流不总能恢复原定的源汇配对。

考虑四个不同顶点 $s_1,s_2,t_1,t_2$，原图只有两条边 $s_1\to t_2$ 和 $s_2\to t_1$，容量都为一。若只规定两个源各供应一、两个汇各接收一，沿这两条边运输便满足合并供需。然而原任务要求 $s_1$ 的商品到 $t_1$、$s_2$ 的商品到 $t_2$，两组均无合法路径，因此多商品流不可行。

这不是费用计算错误，而是模型删除了“谁必须到哪里”的约束。只有商品可以完全互换、目的地身份无须保持时，合并才可能符合任务本意；仅因它们共享同一网络并不足以合并。

割容量的必要条件

下面证明一个割容量的必要条件。任取顶点集 $S$，考虑源点在 $S$ 内、汇点在外的商品集合 $K_S$。对某一这样的商品，把 $S$ 内所有顶点的守恒式相加，内部边项抵消，得到 $$\sum _{e\in {\delta }^{+}(S)}{f}_e^k-\sum _{e\in {\delta }^{-}(S)}{f}_e^k=d_k.$$ 跨入流非负，所以跨出流至少为 $d_k$。对这些商品求和，再利用共享容量，得到必要条件 $$\sum _{k\in K_S}{d}_k\le \sum _{e\in {\delta }^{+}(S)}\sum _{k\in K_S}{f}_e^k\le \sum _{e\in {\delta }^{+}(S)}{u}_e.$$ 主例取 $S=\{s_1,s_2,u\}$，唯一跨出边为 $uv$，得到 $2+2\le 3$ 的矛盾。这个不等式可以证伪候选需求；上面的推导并未声称检查它就足以构造全部商品流。

最大共同满足比例

若不可能满足全部需求，可令每种商品完成同一比例 $\lambda \ge 0$，将守恒右端改为 $\lambda d_k$，并最大化 $\lambda$，称为最大并发流问题。主例的瓶颈给出 $4\lambda \le 3$，所以 $\lambda \le 3/4$；令两组各送 $3/2$，外围容量二足够、公共边总流量三，达到该上界。因此最优共同满足比例恰为 $3/4$，各组仍有四分之一需求未完成。

变式。 若两组需求改为一和二，公共边总量三，$\lambda =1$ 已可行。若仍以“最大化共同倍数”为目标而不额外加 $\lambda \le 1$，可能会出现超过一的解；当指标只表示需求满足率时，应明确加上这个范围限制。

分流、整数与不可拆分路径

允许分流时，同一种商品可以沿多条路径分配。最简单的区别是：一组需求为二，源汇之间有两条内部不相交的路径，每条容量一；分别送一可以满足总需求，但要求该商品全部沿一条路径就不可行。整数流允许这里的“一加一”，仍不等于不可拆分。

单商品整数容量网络的一些整数性结论，不能仅凭每个商品各自看起来是一个普通流就推广过来，因为共享容量把多组变量耦合。说明模型时应同时交代商品身份、容量共享方式、可否分流以及是否要求整数；它们分别决定可行方案的含义。