网络流基础及应用.doc

网络流基础及应用一.引例 运输方案2284371V1V2V5V3V4V644图1下图为联结产品产地V1和销地V6的交通网，每一边(Vi,Vj)代表从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边旁的数字表示这条运输线的最大通行能力(简称容量)。产品经过交通网从V1输送到V6，现要求制定一个输送方案，使V1运到V6的产品数量最多。下面是一个可行的输送方案，边旁的数字为该运输线的实际运输量(单位：吨)。2230203021V1V2V5V3V4V6图2该运输方案表示：2吨产品沿有向路P1(V1,V2,V4,V6)运到销地；1吨产品沿有向路P2(V1,V2,V5,V6)运到销地；2吨产品沿有向路P3(V1,V3,V5,V6)运到销地。总共有5吨从V1运到V6。运输方案的可行必须满足以下三个条件：实际运输量不能是负的；每条边的实际运输量不能大于该边的容量；除了起点V1和终点V6，对其他顶点(中间点)来说，不能囤积物