网络流(network-flows)是一种类比水流的解决问题方法,与线性规划密切相关。网络流的理论和应用在不断发展,出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。图论中的一种理论与方法,研究网络上的一类最优化问题 。1955年 ,T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年,L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法,从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= (V、E、C