多物网络流问题

已知一流网络${\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]。对于这难题的分数变体，在多项式时间中已有解。

1. ^ Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein. 29. Introduction to Algorithms 2nd edition. MIT Press and McGraw-Hill. 2001: 788–789 [1990].   引文格式1维护：冗余文本 (link)
2. ^ S. Even and A. Itai and A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing (SIAM). 1976, 5 (4): 691–703 [2021-08-31]. doi:10.1137/0205048. （原始内容存档于2013-01-12）. 
3. ^ George Karakostas. Faster approximation schemes for fractional multicommodity flow problems. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms: 166––173. 2002. ISBN 0-89871-513-X.