网络流简介 网络流理论是图论中的一种理论与方法,研究网络上的· 类最优化问题; ■1955年,TE哈里斯在研究铁路最大通量时首先提出在 个给定的网络上寻求两点间最大运输量的问题。1956年, L.R福特和DR富尔克森等人给出了解决这类问题的算法, 从而建立了网络流理论; ■目前网络流的理论和应用在不断发展,出现了具有增益的 流、多终端流、多商品流以及网络流的分解与合成等新课 题 ■网络流的应用已遍及通讯、运输、电力、工程规划、任务 分派、设备更新以及计算机辅助设计等众多领域
11 网络流简介 ◼ 网络流理论是图论中的一种理论与方法，研究网络上的一 类最优化问题； ◼ 1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一 个给定的网络上寻求两点间最大运输量的问题。1956年， L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法， 从而建立了网络流理论； ◼ 目前网络流的理论和应用在不断发展，出现了具有增益的 流、多终端流、多商品流以及网络流的分解与合成等新课 题； ◼ 网络流的应用已遍及通讯、运输、电力、工程规划、任务 分派、设备更新以及计算机辅助设计等众多领域
◎引例:运输方案 连接产品产地v1和销地v6的交通网,每一条边GV,V 表示从到V的运输线,产品经这条边由V输送到V,边上 的数字表示这条运输线的最大通行能力(简称容量 产品经过交通网从V1输送到V6,现要求制定一个输送方案, 使得从Ⅵ运到V6的产品数量最多 产地(1 6)销地 2 12
12 引例：运输方案 ◼ 连接产品产地V1和销地V6的交通网，每一条边（Vi，Vj） 表示从Vi到Vj的运输线，产品经这条边由Vi输送到Vj，边上 的数字表示这条运输线的最大通行能力（简称容量）； ◼ 产品经过交通网从V1输送到V6，现要求制定一个输送方案， 使得从V1运到V6的产品数量最多。 1 2 3 4 5 4 4 8 4 2 产地 6 销地 1 2 7 3
■下面考虑可行的输送方案,用边上方框内的数字表示该运 输线的实际运输量(单位:吨) 4 产地(1 6)销地 3 ■运输方案: 2 口2吨产品沿有向路P1(V1,Ⅵ2,V4,V)运到销地; 口1吨产品沿有向路P2(V1,V2,V5,V)运到销地; 口2吨产品沿有向路P3(V1,V3,V5,V)运到销地 注意:需要满足实际的物理限制!
13 ◼ 下面考虑可行的输送方案，用边上方框内的数字表示该运 输线的实际运输量（单位：吨）： ◼ 运输方案： 2吨产品沿有向路P1（V1，V2，V4，V6）运到销地； 1吨产品沿有向路P2（V1，V2，V5，V6）运到销地； 2吨产品沿有向路P3（V1，V3，V5，V6）运到销地。 1 2 3 4 5 4 4 8 4 2 产地 6 销地 1 2 7 3 2 2 2 1 2 2 1 1 2 注意：需要满足实际的物理限制！
产地④2 6)销地 2 合并各个边上的运输 总共有5吨产 量,得到运输方案 品从V1运到V6 产地 销地 14
14 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 22 21 2 2 1 1 2 1 2 3 4 5 4 4 8 4 2 产地 6 销地 12 7 3 32 21 2 2 3 合并各个边上的运输 量，得到运输方案 总共有 5吨产 品从 V 1运到 V 6
■可行的运输方案必须满足以下三个条件: 口实际运输量不能是负的; 口每条边的实际运输量不能大于该边的容量; 口除了起点V和终点V6,对其它结点(中间点)来说,不能囤积物资, 即运到它那儿的物资是多少,从它那儿运走的物资也应该是多少。 思考:有没有可能改进运输方案?即 根据这个运输网,是否可增大运输量? 产地(以 2(6销地 5 3 15
15 1 2 3 4 5 4 4 8 4 2 产地 6 销地 1 2 7 3 3 2 2 1 2 2 3 ◼ 可行的运输方案必须满足以下三个条件： 实际运输量不能是负的； 每条边的实际运输量不能大于该边的容量； 除了起点V1和终点V6，对其它结点（中间点）来说，不能囤积物资， 即运到它那儿的物资是多少，从它那儿运走的物资也应该是多少。 思考：有没有可能改进运输方案？即 根据这个运输网，是否可增大运输量？