多物网络流问题

多物网络流问题（Multi-commodity Flow Problem）是多种物品（或货物）在网络中从不同的源点流向不同的汇点的网络流问题。

定义

已知一流网络${\displaystyle \,G(V,E)}$，其中边${\displaystyle (u,v)\in E}$的容量为${\displaystyle \,c(u,v)}$。有${\displaystyle \,k}$件物品${\displaystyle K_{1},K_{2},\dots ,K_{k}}$，定义为${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$，其中${\displaystyle \,s_{i}}$和${\displaystyle \,t_{i}}$是物品${\displaystyle \,i}$的源点及汇点，及${\displaystyle \,d_{i}}$是需求。物品${\displaystyle \,i}$沿边${\displaystyle \,(u,v)}$的流量是${\displaystyle \,f_{i}(u,v)}$。求一个符合以下限制的流量分配：

容量限制：	${\displaystyle \,\sum _{i=1}^{k}f_{i}(u,v)\leq c(u,v)}$
流守恒：	${\displaystyle \,\sum _{q\in V}f_{i}(u,q)-\sum _{w\in V}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}$
需求的满足：	${\displaystyle \,\sum _{w\in V}f_{i}(s_{i},w)=d_{i}\Leftrightarrow \sum _{w\in V}f_{i}(w,t_{i})=d_{i}}$

在最小成本多物网络流问题中，在${\displaystyle \,(u,v)}$上传送需要成本${\displaystyle a(u,v)\cdot f(u,v)}$。目的是要最小化

${\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\right)}$

在最大多物网络流问题中，每件物品都没有硬性的需求，但最大化总生产量：

${\displaystyle \sum _{i=1}^{k}\sum _{w\in V}f_{i}(s_{i},w)}$

在最大同时网络流问题中，任务是要将物品的流量对它的需求的最小比例最大化：

${\displaystyle \min _{1\leq i\leq k}{\frac {\sum _{w\in V}f_{i}(s_{i},w)}{d_{i}}}}$

与其它问题的关系

最小成本变体是普遍化的最小成本网络流问题。环流问题的变体是所有网络流问题的概括。

用途

利用多物网络流的公式可以接近在光学网络的光学群聚交换中的路由波长分配（RWA, Routing Wavelength Assignment）。

解

这问题已知的解是建基于线性规划^[1].

就算只有两件物品，对于整体流来说，这问题是NP完全^[2]。在有错误限下，已有完全多项式时间近似值的方法去解决这难题^[3]。对于这难题的分数变体，在多项式时间中已有解。