南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）最大流算法（一）

计算机问题求解一论题3-13 -网络流 2020年12月8日 2020/12/08

计算机问题求解 – 论题3-13 - 网络流 2020年12月8日 2020/12/08 1

Lucky Puck Company's Trucking Problem Lucky2公司生产冰球，其工厂在温哥华，仓库在温尼泊。公司 委托物流公司运输。物流公司经营固定线路网，可能经过多 个中间城市。分配给Lucky公司的任意两个城市间的最大运输 量是固定的。如果Lucky公司是按运输量确定生产量，它如何 计划它每天最大产量？ 问题1： 如何建立解决这个问题的模型？ 2020/12/08

Lucky Puck Company’s Trucking Problem Lucky公司生产冰球，其工厂在温哥华，仓库在温尼泊。公司 委托物流公司运输。物流公司经营固定线路网，可能经过多 个中间城市。分配给Lucky公司的任意两个城市间的最大运输 量是固定的。如果Lucky公司是按运输量确定生产量，它如何 计划它每天最大产量？ 2020/12/08 2

Edmonton Saskatoon 12 12/12 Vancouver 16 20 V3 Winnipeg 11/16 15/20 4/9 13 VA 8/13 4/4 14 Calgary Regina 11/14 问题2： 运输方案有多种，最优方案是什么？ 图中的方案是最优的吗？ 2020/12/08

问题2: 运输方案有多种,最优方案是什么? 图中的方案是最优的吗? 2020/12/08 3

问题3： 如果工厂与仓库都不止一个 该怎么办？ 2020/12/08 4

2020/12/08 4

A Model of Oil Supply 17 supplying capacity cosuming capacity 17 16 18 a 12 17 00 12 10 15 00 >(e h 20 20 00 Vertices: b 13 30 a,b:refineries g,h,i:markets others:relays 17 >pipeline,with max capacity/week 2020/12/08 5

A Model of Oil Supply a b c d f e g h i S ∞ ∞ D ∞ ∞ ∞ 16 18 12 17 10 7 13 30 20 15 Vertices: a, b: refineries g, h, i: markets others: relays 17 pipeline, with max capacity/week 17 17 supplying capacity cosuming capacity 12 20 2020/12/08 5

10 10 12 2 5 5 5 6 00 6 00 12 12 20 20 14 14 6 7 3 13 SA SA 18 18 2 2020/12/08 6

2020/12/08 6

严格的数学模型-Flow Network A.flow network G=(V,E)is adirected graph in which each edge (u,v)EE has a nonnegative capacity c(u,v)=0.We further require that if E contains an edge (u,v),then there is no edge (v,u)in the reverse direction.(We shall see shortly how to work around this restriction.)If (u,v)E,then for convenience we define c(u,v)=0,and we disallow self-loops.We distinguish two vertices in a flow network:a source s and a sink t.For convenience,we assume that each vertex lies on some path from the source to the sink.That is,for each vertex v eV, the flow network contains a path svt.The graph is therefore connected and,since each vertex other than s has at least one entering edge,EV-1. 2020/12/08

严格的数学模型- Flow Network 2020/12/08 7

严格的数学模型-FloW We are now ready to define flows more formally.Let G =(V.E)be a flow network with a capacity function c.Let s be the source of the network,and let t be the sink.A flow in G is a real-valued function f:Vx V->R that satisfies the following two properties: Capacity constraint: Flow conservation: When (u.v)E,there can be no flow from u to v,and f(u.v)=0. 2020/12/08

严格的数学模型-Flow 2020/12/08 8

问题4： 什么叫一个flow的“value”? IfI=∑fs,)-∑fw,s) vEV vey 什么是最大流问题？ 2020/12/08

问题4: 什么叫一个flow的“value”? 什么是最大流问题? 2020/12/08 9

How to get the maximum flow? 5 4 5 6 2 6 4 5 2 3 5 2020/12/08 10

How to get the maximum flow? 6 4 5 2 3 1 5 5 4 7 5 6 2 2020/12/08 10