运筹学 北京邮电大学 课件ch7-4学习资料

基本概念①②③④⑤⑥4844122679容量：在某时期内弧(i，j)上的最大通过能力。记为C(i，j)或Cij

在上图中，C12=4，C13＝8，C23＝4等，怎样安排运输方案，才能使在某一时期内从v1运到v6的物资最多，这样的问题就是最大流问题，网络中所有流起源于一个叫做发点的节点（源）所有的流终止于一个叫做收点的节点其余所有的节点叫做中间点（转运点）通过每一条弧的流只允许沿着弧的箭头方向流动目标是使得从发点到收点的总流量最大4/8/2025流量：弧(i，j)的实际通过量，记为f(i，j)或fij可行流：如果fij满足：1.对于所有弧(i，j)有0≤fij≤Cij

2.对于发点vs有：3.对于收点vt有：则称流量集合｛fij｝为网络的一个可行流，简记为f,v称为可行流的流量或值，记为v(f).以下假设网络是一个简单连通图。4.对于中间点点vm有：4/8/2025截集将图G＝（V，E）的点集分割成两部分称为一个截集，截集中所有弧的容量之和称为截集的截量。①②③④⑤⑥68441226796411322306下图所示的截集为请看演示4/8/2025①②③④⑤⑥68441226796401322106又如下图所示的截集为上图所示的截集为所有截量中此截量最小且等于最大流量，此截集称为最小截集。【定理】最大流量等于最小截集的截量。4/8/2025链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。前向弧：与链的方向相同的弧称为前向弧。后向弧：与链的方向相反的弧称为后向弧。增广链

设f

是一个可行流，如果存在一条从vs到vt的链，满足：1.所有前向弧上fij<Cij2.所有后向弧上fij>0则该链称为增广链①②③④⑤⑥前向弧后向弧8446952346容量流量想一想，这是一条增广链吗？4/8/2025【定理】设网络G的一个可行流f，如果存在一条从vs到vt的增广链，那么就可改进一个值更大的可行流f1，并且val

f1>valf【证】设valf＝v对改进的可行流f1：4/8/2025最大流的标号算法步骤1.找出第一个可行流，例如所有弧的流量fij=02.用标号的方法找一条增广链

A1：发点标号（∞），

A2：选一个点vi已标号并且另一端未标号的弧沿着某条链向收点检查：如果弧的方向向前并且有fij<Cij，则vj标号（Cij－fij)

如果弧的方向指向vi并且有fji>0，则vj标号（fji)当收点不能得到标号时，说明不存在增广链，计算结束。当收点已得到标号时，说明已找到增广链。【定理】可行流是最大流当且仅当不存在发点到收点的增广链4/8/20254.调整流量得到新的可行流，去掉所有标号，从发点重新标号寻找增广链，直到收点不能标号为止。3.依据vi的第一个标号反向跟踪得到一条增广链；依据vi的第二个标号求最小值得到调整量θ进入演示和练习4/8/2025∞①②③④⑤⑥684412267942202222046217【例】求下图v1到v6的最大流及最大流量【解】1.通过观察得到初始可行流2.标号3.得到增广链4/8/2025∞①②③④⑤⑥68441226794211322304223得到增广链4.求调整量5.调整可行流去掉所有标号，重新标号∞①②③④⑤⑥6844122679422022220462174/8/2025①②③④⑤⑥68441226796411322306求调整量调整可行流去掉所有标号，重新标号∞5标号不能继续进行，说明不存在从发点到收点的增广链，得到最大流.最大流量v=6+3=914/8/2025TheEndofChapter6作业:教材P285T10.1110.1210.14下一章：网络计划Exit1.基本概念容量、流量、可行流、前向弧、后向弧、