运筹学-网络流问题(名校讲义)

1、28、29讲座网络流问题、1网络流2最大流和最小切削3最大流算法4最小成本流、1网络流(1)、1网络流的概念问题简单地说明，流是将目标或对象从一个位置发送到另一个位置。希望现有物理网络图中从一个地点发运到另一个地点的最大运输量，或者希望将特定项目从一个地点发运到另一个地点的成本最低。例5-10承运人接受任务，原产地x1和x2两区内的保管品必须通过v1、v2、v3等三个中继站运输到用户y1和y2。公司获得的利润与运输总量成正比。据悉，X1、x2分别需要120吨、240吨、y1和y2分别需要180吨、200吨，图5-31中显示了总体交通网络布局和交通干线容量。1网络流(2)，问题是找到最大总运输的

2、最佳运输方案。1网络流(3)、运输网络(v，e)、与每个边相对应的非负c(e)以及指定v的两个非空集x(出货量集)和y(点集)，XY=(v，e，c)另外，c(e)是边e的容量，x的顶点x是g的源，y的顶点y是g的汇款。顶点集I=V(XY)称为g的中间顶点。Ii)网络流将f(e)设置为域，将f (v)和f(v)分别设置为v点的起点和v点的终点，并将所有转向边的相应函数值的总和设置为。在网络g中，f(e)为0 f(e) c(e)，eE(约束)，1网络流(4)，f (v)=f(v)，vI(保留条件)为f gF(e)在边e上称为f的流。所有网络g，至少有一个流，如果每个边的f(e)=0，则称为零流。2

3、单个和单个运输网络的实际问题通常有多源多交换网络(例如，图5-31是双源双交换网络)。为了规格化计算，可以使多源多源网络g成为单源单源网络g。1网络流(5)，在原始地物g中添加两个新顶点x和y，以在新g中作为单个源和单个源时，g中的所有顶点v将成为g的中间顶点集。对于XX，使用相切边(x，x)连接顶点x和x。边的容量取决于实际情况或特定值。同样，对于yY，通过垂直边(y，y)连接顶点y和y，边容量可以是或特定值。如果f是原始图g的流，则可以定义对应的新g的流f:1网络流(6)。显示时，f定义适合g的流。相反，如果定义g的上一个流f，则f落在图g中的部分必须是图g中的相应流。可以看到，多源多源网

4、络和单源单源网络之间的转换是完全等效的转换。示例5-11将图5-31中所示的图转换为单个源单个源网络g，图5-32中所示的图g将给定流f转换为图g中相应的流f。1网络流(7)，解决方案1)首先提供g的单个源x和单个源y，根据规则配置新g，g的每个变量C(e)为2，计算与图5-32所示g的f流相对应的流f，从而得出：1网络流(1、以后，通常基于单一源单一源网络分析。2最大流和最小切削(1)、1切削的定义和属性是s设定为v的子集，来源是从s和端点开始的所有方向边集。也就是说，边集是网络g的一个切口。要截断K的容量，请用C(K)记录。2最大流和最小切削(2)，5-12给定图g查找与给定Sj(j=1，

5、2，3)相对应的切削集容量C(Kj)，如图5-34所示。解决方案1)如果S1=x，v1，则K1=(v1，v3)，(v1，v2)，(x，v2)和C(K1)=10 6 9=25 2) S2定义：如果f流的流值为V(f)，则I)符合以下f*:称为g的最大流V(f*)=max V(f)f为g的流ii)满足以下K*:设置最小切削C(K*)=min C(K)K为g的切削清理清理清理清理清理清理1 f，在图g中分别为顶部和随机切削的情况下，存储在V(f)=f(s)f(s)f(s)f(s)中。其中，图g中任意部分的净流量值V(f)为f (f)，2最大流量和最小切削(4)，其他术语：f是图g的一个流，对于eE，

6、定义：f(e)=c(e)如果F(e)为0，则边e为f的正边。如果F(e)=0，则边e是f的零边。2最大和最小切削(5)，如果将f和k分别设置为图g中的一流和随机切削，则清除2必须存在。i) V(f) C(K) ii) V(f)=C(K)的先决条件是在定理3中，f和K分别是图g的一个流，并且满足等式V(f)=C(K)。示例：f和k必须分别是图g中的最大和最小切削。2最大流和最小切削(6)、3延伸链和应用清理相关术语和定义I) g中有u-v的方向边(u、v)，则(u、v)是q的前边。Ii)如果g具有从v到u方向的边(v，u)，则称为q的后边缘。如果Iii) f是g的流，并且为eE(Q)定义，则iv

7、)是l(Q)=0，Q是f的饱和链。L(Q)0到Q称为f的不饱和链。2最大流和最小切削(7)，5-13图5-35显示了具有流f的图g，分析了上述术语和定义。解决方案1)如果先取Q1=xv2 v1 v3 v4，则前边缘为(x，v2)，(v1，v3)和(v3，v4)，l值为l(x，v2)=2，l(l反向边为(v1，v2)，相应的l(v1，v2)=0。因为L(Q1)=0已知，所以Q1是f的饱和链。2最大流和最小切削(8)，2)取Q2=xv2 V5 v4 v3y时，前边为(x，v2)，(v2，V5)和(v3，y)后边为(v4，V5)和(v3，v4)，其l值为l(v4，V5)=3，l (v3，v4)=3。

8、因为您知道L(Q2)=20，所以Q2是f的不饱和链。从以上分析可以看出。如果q为f的饱和链，则该链具有f饱和边或f的一个或多个零边。相反，q为f的不饱和链不在饱和前后0的链中。2最大流和最小切削(9)，v)从源x到huiy的不饱和链，称为f的增量链。Vi)如果网络g具有f增量链，则将创建每个侧流值为的g的新流。此时，新流值为f基于q链的修正流，q为饱和链。例如，、2最大和最小切削(10)。例如，在图5-35中，Q=xv2 V5 v4 v3y是l(Q)=2的增量流链，将f更改为后，修改为列在图5-36中。定理定理定理4流f为g的最大流的充分条件是g没有f增量链。，3最大流算法(1)，1算法思路判

9、别图g中当前指定的f没有增量链，则此流f是最大流。否则，求出修正流，将其看作f，进行判断和计算，直到找到最大流为止。2算法阶段(标签算法)、3最大流算法(2)、示例5-14图5-38所示的图g中，提出了现有流(侧面旁边前后的两个数字分别表示容量和实际流)，测试标签方法生成了最大流。解决方案1)根据图5-38所示的初始流程，图g中的所有点编号如图5-11所示。3最大流算法(3)，在表5-11，表5-11，表5-11中，Qy=xv2 v3 v4y，l(Qy)=l(y2)在图5-39中，继续标记顶点，如表5-12所示。(有点)，4最小成本流(1)，1应用程序背景和术语相关问题(应用程序背景)如何获得

10、满足运输量和最小化成本的流？这是最低成本流问题。将向具有点集合V、边集合e、边容量c、源点x和源点y的运输网络G=(V、e、c、x、y)添加集合w。4最小成本流(2)，I)如果fA是g的流，相应的流值V(f)=A，则定义W(fA)=流fA的成本。图g至x至y表示沿流fA运输a单位所需的总成本。Ii)如果有多个流的正常流值为a，则定义满足以下条件的流值a的流是图g中流值为a的最小成本流：如果W()=minW(f)f是g的网络流，流值V(f)=A是g的最大流值，则称为g的最小成本最大流。4最小成本流(3)，2流f的伴随网络定义1: f为G=(V，E，c，w，x，y)的网络流，新配置如下v) ii)

11、 e=(v，u) E(Gf)，c (v，u)=f(u，V)，w(v，u)=w(u，V ，4最小成本流(5)、示例5-15已知流值f为4的成本运输网络g如图5-41(a)所示。图中边旁边的数字按容量c(e)、流值f(e)、成本(或权重)值w(e)和f查找网络Gf。根据定义，解决方案可能在图5-41(b)中表示Gf。边参数分别为c(e)和w(e)。4仔细分析最小成本流(6)、Gf图形，读者不难发现此图形提供了以下两个重要信息：1)如果源x到huiy有路径，这意味着原始图g有f的增量链。否则，f是g的最大流。2)如果Gf具有权重w总和为负的循环，则增加该循环中的流值不会更改源x到y的f流值，但会减少

12、总成本，因此不会实现最小成本。相反，如果没有负回路，则必须达到该流下的最小成本。4最小成本流(7)、清理5 f为g的最大流的先决条件f的伴随网络Gf不包含源x到y的路径。定理6 fA具有g到a的流值的最小成本流的先决条件是fA的伴随网络Gf没有负循环。Gf中的所有回路l都具有。定理5和定理6分别提供了寻找网络最大流和网络最小成本流的有效方法。4最小成本流(8)、3最小成本流的算法思想在需要特定流值的最小成本流时有两种方法。I)从特定初始流(例如，零流)开始，使用标签方法获取给定流值的流f，然后使用清理6中所述的方法(确定f的伴随网络中是否存在负循环)逐步获取对应于该流值的最小成本流。Ii)从初

13、始最小成本流开始，逐步发现较大流值的最小成本流，以获得与以前方法不同的该流值的最小成本流。4最小成本流(9)，清理7(迭代最小成本流清理)如果fA是地物g的流值为a的最小成本流，则p是Gf的x到y的最短路径。使用正整数时，满足以下条件的fA的更正流将成为g流值为a的最小成本流：根据、清理7，一次可以找到指定流值的最小成本流。4最小成本流(10)，4最小成本流的算法步骤实例5-17已知发运网络g如图5-43所示，给出了流值为4的流F4，并测试了该网络中流值为6的最小成本流。解决方案1)图5-44中显示了针对该图提供的F4的伴随网络。4如最小成本流(11)、图5-44所示，给定初始流F4没有负循环，因此给定流是最小成本流(流值4)。此外，如果从x到y的最短路径(最小边界和)为xv2 v1y或xv2 y，并且存在一个xv2 v1y，则路径的最大流值为=minc (e) e p。6V(f4)=min c(x，v2)，c(v2，v