系统工程导论

系统工程导论蒋珉东南大学自动化学院本课程学学习要求求：掌握基本本理论；；熟悉基本本方法；；能联系实实际，解解决问题题。本课程学学习方法法及考核核：以课堂讨讨论、自自学为主主，教师师讲授为为辅。考核成绩绩=大作作业成绩绩（60%，大作业业报告、、发言情情况）++平时作作业（10%）+开开卷考试试成绩（（30%）第7章图图和和网络优优化图论广泛泛地应用用与物理理学、化化学、控控制论、、信息、、科学管管理、电电子计算算机等领领域。很很多实际际问题可可以采用用图论的的理论和和方法来来解决。。图论的历历史最早早可以追追溯到1736年E.Euler（瑞士数数学家））解决著名名的哥尼尼斯堡七七桥问题题。第7章图图和和网络优优化原问题：：能否走走过七座座桥，且且每座桥桥只走过过一次，，最后回回到出发发点？Euler解题的思思路：将将原问题题化为一一笔画问问题。图图中的每每个点都都只与奇奇数条线线相关联联，不可可能不重重复地一一笔画成成。第7章图图和和网络优优化第7章图图和和网络优优化结论：哥哥尼斯堡堡七桥问问题不可可能有解解。第7章图图和网络络优化许多工程程问题可可以采用用图来描描述，并并且可以以化为相相应的优优化问题题，最终终采用优优化算法法来加以以解决。。由于计计算机的的普及和和大量算算法的出出现，使使得图论论方法的的应用成成为了可可能。第7章图图和网络络优化第1节图的的概念图：由点点和线组组成，可可以表示示对象之之间的相相互关系系。一、图概概念的引引进第1节图的的概念例1十个城市市之间的的铁路交交通图。。反映了了这十个个城市之之间的铁铁路分布布情况。。点代表表城市，，点与点点之间的的连线代代表相邻邻两个城城市之间间的铁路路线。类似的问问题还有有电话线线分布图图、煤气气管道图图、航空空线路图图等。第1节图的的概念例2球队之间间比赛的的情况。。vi(i=1,…,5)表示五个个球队。。如果某某两个球球队比赛赛过了，，则在这这两个队队所相应应的点之之间联一一条线，，这条线线不过其其它点。。第1节图的的概念例3化学药品品储存问问题。某某些药品品不能储储存在同同一个库库房里。。vi(i=1,…,8)表示八八种药品品。若药药品vi和药品vj不能储存在同同一个库库房里，，则在它它们之间间联一条条线。需需要解决决的问题题是：至至少需要要几个库库房，能能将储存存这八种种药品第1节图的的概念图是反映映对象之之间关系系的一种种工具，，是一种种数学抽抽象。通通常用点点代表研研究的对对象，用用点与点点之间的的连线表表示这两两个对象象之间有有特定的的关系。。注意：图图中点的的相对位位置如何何，点与与点之间间的连线线的长短短曲直，，对于反反映对象象之间的的关系并并不重要要。第1节图的的概念反映例2中球队之之间的比比赛情况况的两种种图没有有本质上上的区别别。第1节图的的概念例1～例3中涉及到到的对象象之间的的“关系系”具有有“对称称性”。。即：如如果甲与与乙有某某种关系系，则乙乙与甲也也有同样样的这种种关系。。在实际生生活中，，有许多多关系不不具有这这种对称称性。例例2中的比赛赛胜负情情况就不不能用简简单的连连线来表表示。为为了反映映这种关关系，可可以用一一条带箭箭头的连线表表示。第1节图的的概念二、定义义图：由一些些点及一一些点之之间的连连线（带带箭头或或不带箭箭头）所所组成。。边：两点之之间的不不带箭头头的连线线。弧：两点之之间的带带箭头的的连线。。无向图（简称图）：由点点及边构构成的图图。有向图：由点及及弧构成成的图。。第1节图的的概念点用集合合V={v1,…,,vn}表示。联结点vi和vj∈V的边记为为[vi,vj](或[vj,vi]）。联结点vi和vj∈V的弧记为为（vi,vj），方向向是从vi指向vj。无向图记为G=(V,E)，V、E分别为G的点集合合和边集集合。有向图记为D=(V,A)，V、A分别为G的点集合合和弧集集合。第1节图的的概念无向图实实例第1节图的的概念有向图实实例第1节图的的概念图G或D中的点数数记为p(G)或p(D)，边（弧弧）数记记为q(G)或q(D)。简记为为p或q。第1节图的的概念三、术语语1、无向图图若，，则则称u，v是e的端点，也称u，v是相邻的。称e是点u（及点v）的关连边。若图G中，某个个边e的两个端端点相同同，则称称e是环；若两个个点之间间有多于于一条的的边，称称这些边边为多重边。一个无环环，无多多重边的的图称为为简单图；一个无无环，但但允许有有多重边边的图称称为多重图。第1节图的的概念以点v为端点的的边的个个数称为为v的次，记为或或。。注意：图图中环在在计算边边时记做做两次。。称次为1的点为悬挂点，悬挂点点的关连连边称为为悬挂边，次为零的点称称为孤立点。第1节图的的概念定理1图中中，，所有点点的次之之和是边边数的两两倍，即即次为奇数数的点称称为奇点，否则称称为偶点。定理2任一图中中，奇点点的个数数为偶数数。第1节图的的概念给定一个个图，，一一个点边边的交错错序列，，若若，，则称为一一条联结结和和的的链，记为，，有时称点点为为链的的中间点。第1节图的的概念链中中，若，，则则称之为为一个圈，记为。。若若链中中，，点都都是不同同的，则则称之为为初等链；若圈中中，点点都都是不不同的，，则称之为初等圈；若链（（圈）中中含的边边均不相相同，则则称之为简单(链)圈。除非特别别说明，，链（圈圈）均指指初等链链（圈））。第1节图的的概念是一条简简单链，，但不是是初等链链，是是一条初初等链。。该图中中，不不存在联联结和和的的链。是是一个初初等圈，，是是简单单圈，但但不是初初等圈。。图中，第1节图的的概念图G中，若任任何两个个点之间间，至少少有一条条链，则则称G是连通图，否则称称为不连通图图。若G是不连通通图，它它的每个个连通的的部分称称为G的一个连通分图图（简称为为分图）。第1节图的的概念给定一个个图，，如果果图，，使及及，，则称称是是的的一一个支撑子图图。设，，用表表示从从图G中去掉v及v的关联边边后得到到的一个个图。第1节图的的概念2、有向图图设给定了了一个有有向图，，从D中去掉所所有弧上上的箭头头，就得得到了一一个无向向图，称称之为D的基础图，记之为为G(D)。给定D中的一条条弧，，称称u为a的始点，v为a的终点，称弧a是从u指向v的。第1节图的的概念设是是D中的点弧弧交错序序列，如如果该序序列在基基础图G(D)中所对应应的点边边序列是是一条链链，则称称该点弧弧交错序序列是D的一条链链。类似似定义圈圈和初等等链（圈圈）。如果是是D中的一条条链，并并且对，，均均有，，称称之为从到到的的一一条路。若路的的第一个个点和最最后一个个点相同同，则称称之为回路。类似定定义初等路（回路）。第1节图图的概念念是一个回回路；是是从到到的的路；；是是一条条链，但但不是路路。第7章图图和网络络优化第2节树树2.1树及其性性质定义1一个无圈圈的连通通图称为为树。树是极其其简单然然而却是是非常有有用的一一类图。。2.1树及其性性质例4五个城市市之间架架设电话话线。要要求任何何两个城城市都可可以相互互通话（（允许通通过其他他城市）），并且且电话线线的根数数最少。。用五个点点代代表表五个城城市。若若在某两两个城市市之间架架设电话话线，则则在相应应的两个个点之间间连一条条边。这这样一个个电话线线网就可可以用一一个图来来表示。。2.1树及其性性质为了使任任何两个个城市都都可以通通话，这这样的图图必须是是连通的的。如果图中中有圈的的话，从从圈中去去掉任意意一条边边，剩下下的图仍仍然是连连通的。。如此可可以省去去一条电电话线。。因此，，满足要要求的电电话线网网必定是是树（无无圈的连连通图））。2.1树及其性性质例5某工厂的的组织结结构可以以表示成成一个树树。2.1树及其性性质定理3设图是是一一个树，，，，则G中至少有有两个悬悬挂点。。定理４图是是一个个树的充充分必要要条件是是G不含圈，，且恰有有条边。定理５图是是一个个树的充充分必要要条件是是G是连通图图，并且且定理６图G是一个树树的充分分必要条条件是任意两个个顶点之之间恰有有一条链链。2.1树及其性性质推论１从从一个个树中去去掉任意意一条边边，则余余下的图图是不连连通的。。即：在在点集合合相同的的所有图图中，树树是含边边树最少少的连通通图。推论２在在树中中不相邻邻的两个个点间添添上一条条边，则则恰好得得到一个个圈。第2节树树2.2图的支撑撑树定义2设图是是图的的支撑子子图，如如果图是是一个个树，则则称T是G的一个支支撑树。。2.2图的支撑撑树若图是是图的的一个支支撑树，，则树Ｔ中边的个个树是，，G中不属于于树T的边数是是。。定理７图G有支撑树充充分必要要条件是是图G是连通的的。利用定理理７充充分性的的证明过过程，可可以得到到一个寻寻求连通通图的支支撑树的的方法——“破圈法法”：任取一一个圈，，从圈中中去掉一一边，对对余下的的图重复复该步骤骤，直到到不含圈圈为止。。2.2图的支撑撑树例6在图7-15中，用“破圈法”求出图的的一个支撑树。。2.2图的支撑撑树另外一种种寻求连连通图的的支撑树树的方法法—“避圈法法”：在图中中任取一一条边，，找一一条与不不构成成圈的边边，再再找一条条与不不构构成圈的的边。。一般，，设已有有，，找找一条与与中中的的任何一一条边不不构成圈圈的边。。重复复上述过过程，直直到不能能进行为为止。2.2图的支撑撑树例7在图7-16中，用““避圈法法”求出出图的一一个支撑撑树。2.2图的支撑撑树根据定理理４和定定理５可可知，在在“破圈圈法”中中去掉的的边数必必是条条；；在“避避圈法””中取出出的边数数必是条条。。第2节树树2.3最小支撑撑树问题定义３给定图，，对图图G中的每一一条边，，相应地地有一个个数，，则称这这样的图图为赋权图，称为为边上上的的权。这里所说说的“权权”是指指与边有有关的数数量指标标。可以以根据实实际问题题，赋予予它不同同的含义义。赋权图不不仅指出出了各个个点之间间的连结结关系，，而且同同时也表表示出各各点之间间的数量量关系。。所以，，赋权图图被广泛泛地应用用于解决决最优化化问题。。2.3最小支撑撑树问题题设有一个个连通图图，，每一边边，，有一一个非负负权

定义４如果图是是图G的一个支支撑树，，称中中所有边边的权之之和为支支撑树T的权，记记为。。即即2.3最小支撑撑树问题题如果支撑撑树的的权是是G的所有支撑树的的权中最最小者，，则称是是G的最小支撑撑树（简称最小树）。即式中对G的所有支支撑树T取最小。。最小支撑撑树问题题就是要要求给定定连通赋赋值权图图G的最小支支撑树。。实际应用用：城市市间交通通网的建建造问题题。两种求最最小树的的方法：：“避避圈法””和“破破圈法””2.3最小支撑撑树问题题1、避圈法法开始选一一条权最最小的边边，以后后每一步步，总从从与已选选边不构构成圈的的那些未未选边中中，选一一条权最最小的。。在每一一步中，，如果有有两条或或两条以以上的边边都是权权最小的的边，则则从中任任选一条条。2.3最小支撑撑树问题题算法步骤骤：第1步令令（（表表示空集集）；第2步选选一一条边，，使是是使使不不含含圈的所所有边中中权最小小的边。。令，，如果这这样的边边不存在在，则第3步把把换换成，，转入入第2步。2.3最小支撑撑树问题题例8已知某工工厂内联联结六个个车间的的道路网网及每条条道路的的长，要要求沿道道路架设设六个车间间的电话话线网，，是电话话线的总总长度最最小。2.3最小支撑撑树问题题2、破圈法法任取一个个圈，从从圈中去去掉权最最大的边边（如果果有两条条或两条条以上的的边都是是权最大大的边，，则任意意去掉其其中的一一条）。。在余下下的图中中，重复复这个步步骤，直直到得到到一个不不含圈的的图为止止。这时时的图就就是最小小树。2.3最小支撑撑树问题题例9用破圈法法求例8中的最小小支撑树。。第7章图图和网络络优化第3节最最短路问问题3.1引例例10如图7-18所示的单单行线交交通网，，每弧旁旁的数字字表示通通过该单行线所所需的费费用。从从v1出发到v8，求使总总费用为为最小的的旅行路路线。3.1引例显然，从从v1到v8的旅行线线路很多多。不同同的路线线，所需需的总费费用是不不同的。。一条旅旅行线路路的总费费用就是是相应的的从v1到v8的路中所所有弧旁旁数字之之和。注意：这这里所说说的路可可以不是是初等路路。3.1引例一般的最最短路问问题：给定一个个赋权有有向图，，即给定定一个有有向图D=(V,A),对每个弧弧a=(vi,vj),有权ω(a)=ωij。又给定定D中两个顶顶点vs和vt。设P是D中从vs到vt的一条路路，定义义路P的权是P中所有弧弧的权之之和，记记为ω(P)。最短路问问题就是是要在所所有从vs到vt的路中，，找一条条权最小小的路，，即寻找找P0，使3.1引例上式中，，称：：P0是从vs到vt的最短路；路P0的权为从从vs到vt的距离，记为d(vs,vt)。最短路问问题是网网络理论论中应用用最广泛泛的问题题之一。。许多优优化问题题可以使使用这个个模型．．如设备备更新、、管道铺铺设、线线路安排排、厂区区布局等等。第3节最最短短路问题题Dijkstra算法本算法由由Dijkstra于1959年提提出，可可用于求求解指定定两点vs、vt间的最短短路，或或从指定定点vs到其余各各点的最最短路。。思路———若序列{vs,v1,…,vn-1,vn}是从vs到vn的最短路路，则{vs,v1,…,vn-1}必为从vs到vn-1的最短路路。适用范围围——有向图中所有弧弧的权均均非负，，即：ωij≧0。3.2最短路算算法3.2最短路算算法Dijkstra算法的基基本步骤骤，采用用标号法法。用两种标标号：T标号与P标号，T标号为试试探性标标号，P为永久性性标号。。给vi点一个P标号时，，表示从从vs到点vi的最短路路权,vi点的标号号不再改改变。给给vi点一个T标号时，，表示从从vs到vi点的估计计最短路路权的上上界，是是一种临临时标号号。凡没没有得到到P标号的点点都有T标号。3.2最短路算算法算法的每每一步都都把某一一点的T标号改为为P标号，当当终点vt得到P标号时，，全部计计算结束束。对于于有n个顶点的的图，最最多经n-1步就可以以得到从从始点到到终点的的最短路路。标号的意意义：①标号P(永久性标标号)—从始点到到该标号号点的最最短路权权；②标号T(临时性标标号)—从始点到到该标号号点的最最短路权权上界。3.2最短路算算法计算步骤骤第1步给始点vs标上永久久性标号号P(vs)=0，其余各各点标临临时性标标号T(vj)=+；第2步若vi为刚得到到P标号的点点，考虑虑这样的的点vj：(vi,vj)属于D，且vj为T标号。对对vj的T标号进行行如下的的更改：：T(vj)=min{{T(vj),P(vi)+ωij}3.2最短路算算法第3步比比较所有有具有T标号的点点，把最最小者改改为P标号，即即当存在两两个以上上最小者者时，可可同时改改为P标号。若若全部点点均为P标号则停停止。否否则用代代vi转回第二二步。3.2最短路算算法例用用Dijkstra算法求下下图中v1到v7点的最短短路。•••••••v1v2v7v5v4171344452572v33.2最短路算算法图中()内的数表表示P标号，[]内的数表表示T标号。•••••••v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7(1)首先给v1以P标号,P(v1)=0,,其余所有有点给T标号,T(vi)=+∞∞；3.2最短路算算法(2)由于弧(v1,v2)、(v1,v3)、(v1,v4)属于D，且v2、v3、v4为T标号，所所以修改改这三个个点的标标号：T(v2)=min{T(v2),P(v1)+ω12}=min{∞∞,0++4}==4T(v3)=min{T(v3),P(v1)+ω13}=min{∞∞,0++2}==2T(v4)=min{T(v4),P(v1)+ω14}=min{∞∞,0++5}==5•••••••v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞]73.2最短路算算法(3)比较所有有T标号，T(v3)最小，故故令令P(v3)=2•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]73.2最短路算算法(4)v3为刚得到到P标号的点点，考察察弧(v3,v4)，(v3,v6)的端点v4,v6T(v4)=min{T(v4),P(v3)+ω34}=min{5,2++2}==4T(v6)=min{T(v6),P(v3)+ω36}=min{∞∞,2++7}==9•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]73.2最短路算算法(5)比较所有有T标号，T(v2),T(v4)最小，所所以令P(v2)=P(v4)=4•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][4][9][∞][∞]73.2最短路算算法•••••••v1(0)v2v7v5v411344452572v3(2)v6(4)(4)[9][∞][∞]73.2最短路算算法(6)v2,v4为刚得到到P标号的点点,考察弧(v2,v5)，(v4,v5)，(v4,v6)的端点v5,v6T(v5)=min{T(v5),P(v4)+ω45,P(v2)+ω25}==min{{∞,4+3,,4+4}=7T(v6)=min{T(v6),P(v4)+ω46}=min{9,4++4}==8•••••••v1(0)v2v7v5v411344452572(4)(4)[8][7][∞]7v3(2)v63.2最短路算算法(7)比较所有有T标号，T(v5)最小，所以令P(v5)=7•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[∞][8]v3(2)v673.2最短路算算法•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[14]][8]v3(2)v6(8)v5为刚得到到P标号的点点，考察察弧(v5,v6)，(v5,v7)的端点v6,v7T(v6)=min{T(v6),P(v5)+ω56}=min{8,7++1}==8T(v7)=min{T(v7),P(v5)+ω57}=min{∞∞,7++7}==1473.2最短路算算法(9)比较所有有T标号，T(v6)最小，所所以令P(v6)=8•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[14]](8)v3(2)v673.2最短路算算法(10))v6为刚得到到P标号的点点，考察察弧(v6,v7)的端点v7T(v7)=min{T(v7),P(v6)+ω67}=min{14,8+5}}=13•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[13]](8)v3(2)v673.2最短路算算法(11))只有一个个T标号T(v7)，令P(v7)=13，停止。。•••••••v1(0)v2v7v5v411344452572(4)(4)(7)(13))(8)v3(2)v67计算结果果见上图图，v1到v7的最短路路为：同时得到到v1到其余各各点的最最短路。。3.2最短路算算法例11用Dijkstra算法求图图7-19中v1到v8的最短路路。计算过程程略，v1到v8的最短路路为：3.2最短路算算法Dijkstra算法只适适用于全全部权为为非负情情况．如如果某弧弧的权为为负，算算法失效效。负权的情情况自学学讨论。。第3节最最短路问问题最短路问问题是网网络理论论中应用用最广泛泛的问题题之一。。许多优优化问题题可以使使用这个个模型．．如设备备更新、、管道铺铺设、线线路安排排、厂区区布局等等。3.3应用举例例3.3应用举例例例(设备更新新问题)某企业在在四年内内都要使使用某种种设备，，在每年年年初作作出是购购买新设设备还是是继续使使用旧设设备的决决策。若若购买新新设备就就要支付付购置费费；若继继续使用用旧设备备，则需需支付维维修费用用。这种种设备在在四年之之内每年年年初的的价格以以及使用用不同时时间（年年）的设设备的维维修费用用估计为为：年份1234年初购价10111213维修费用247143.2应用举例例问题：制制定一个个四年之之内的设设备更新新计划，，使得四四年之内内的设备备购置费费和维修修费用之之和最小小。可以用求求最短路路问题的的方法来来解决总总费用最最少的设设备更新新计划问问题。3.3应用举例例符号的含含义：vi—第i年年初购购进一台台新设备备(v5表示第四四年年底底)；弧(vi,vj)—第i年年初购购进的设设备一直直使用到到第j年年初(即第j-1年年底)；弧(vi,vj)的权数—从第i年年初购购进的设设备一直直使用到到第j年年初所所花费的的购置费费和维修修费用的的总和。。3.3应用举例例如何制定定使得总总费用最最少的设设备更新新计划问问题可以以转化最最短路问问题。此此最短路路问题如如图所示示。3.3应用举例例图中权数数ij的确定：：12=10++2=12；13=10++2+4=16；14=10++2+4+7==23；15=10++2+4+7++14==37；23=11++2=13；24=11++2+4=17；25=11++2+4+7==24；34=12++2=14；35=12++2+4=18；45=13++2=153.3应用举例例如何制定定使得总总费用最最少的设设备更新新计划问问题可以以转化最最短路问问题。此此最短路路问题如如图所示示。3.3应用举例例图中权数数ij的确定：：12=10++2=12;13=10++2+4=16;14=10++2+4+7==23；15=10++2+4+7++14==37;;23=11++2=13；24=11++2+4=17;25=11++2+4+7==24;;34=12++2=14;35=12++2+4=18;45=13++2=153.3应用举例例用Dijkstra算法求v1到v5的最短路路。(1)给v1以P标号,P(v1)=0,,其余各点点给以T标号T(vi)=++∞((i==2,3,4,,5)（图中()内的数表表示P标号；[]内的数表表示T标号）3.3应用举例例(2)由于（v1,v2）,(v1,v3),（v1,v4）,（v1,v5）∈D，且v2,v3,v4,v5为T标号，所所以修改改这四个个点的标标号：T(v2)=min{{T(v2),P(v1)+12}=min{{+∞∞,0+12}=12T(v3)=min{{T(v3),P(v1)+13}=min{{+∞∞,0+16}=16T(v4)=min{{T(v4),P(v1)+14}=min{{+∞∞,0+23}=23T(v5)=min{{T(v5),P(v1)+15}=min{{+∞∞,0+37}=373.3应用举例例(3)比较所有有具有T标号的点点，把最最小者改改为P标号。T(v2)最小，令令P(v2)=12。3.3应用举例例(4)v2为刚得到到P标号的点点，考察察弧(v2,v3),((v2,v4),((v2,v5)的端点v3,v4,v5。T(v3)=min{{T(v3),P(v2)+23}=min{{16,12+13}==16T(v4)=min{{T(v4),P(v2)+24}=min{{23,12+17}==23T(v5)=min{{T(v5),P(v2)+25}=min{{37,12+24}==363.3应用举例例(5)比较所有有具有T标号的点点，把最最小者改改为P标号。T(v3)最小，令令P(v3)=16。3.3应用举例例(6)考察点v3T(v4)=min{{T(v4),P(v3)+34}=min{{23,,16+14}=23T(v5)=min{{T(v5),P(v3)+35}=min{{36,,16+18}=34(7)所有T标号中，，T(v4)最小，令令P(v4)=233.3应用举例例(8)考察点v4T(v5)=min{{T(v5),P(v4)+45}=min{{34,,23+15}=34(9)只有一个个T标号T(v5)，令P(v5)=34。计算结束束。由上可知知：v1到v5的最短路路为v1→v3→v5,长度为34。其含义义为：最最佳更新新计划为为第一年年年初购购买新设设备使用用到第二二年年底底(第三年年年初)，第三年年年初再再购买新新设备使使用到第第四年年年底，这这个计划划使得总总的支付付最小，，其值为为34。3.3应用举例例例13(类似）自己完成成。第7章图图和网络络优化最大流问问题是在在一个给给定网络络上求流流量最大大的可行行流，即即给一个个网络的的每条弧弧规定一一个流量量的上界界，求从从点vs到vt的最大流流。第4节网网络最大大流问题题第4节网网络最大大流问题题下图是一一个输油油管道网网，vs为起点，，vt为终点，，v1~v6为中转站站，弧旁旁的数表表示该管管道的最最大输油油量。问题：如如何安排排，才能能使从vs到vt的输油量量最大？？第4节网网络最大大流问题题4.1基本概念念与基本本定理1、网络与与流定义6给定有向向图D=(V,A)，在V中指定一一点称为为发点（记为vi），而另另一点称称为收点（记为vj），其余余的点为为中间点点。对于于每个弧弧(vi,vj)∈A，对应有有一个c(vi,vj)≧0（简简写为cij），称为为弧的容容量。这这样的D称为一个个网络，记为D=(V,A,C)4.1基本概念念与基本本定理所谓网络络上的流流，是指指定义在在弧集合合A上的一个个函数f={f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量（简记为为fij)。图7-23和图7-24给出了发发点、收收点、弧弧的容量量和弧的的流量的的例子。。4.1基本概念念与基本本定理2、可行流流与最大大流在运输网网络的实实际问题题中，对对流有两两个明显显的要求求：①每每个弧上上的流量量不能超超过该弧弧的最大大通行能能力（即即弧的容容量）；；②中间间点的流流量为零零。理由：对对于每一一个点，，运出该该点的产产品总量量与运出出该点的的产品总总量之差差为该点点的净输输出量，，简称为为该点的的流量；；中间点点只起转转运作用用，其流流量为零零。易见，发发点的净净流出量量与收点点的净流流入量相相等，也也就是该该方案的的总输送送量。4.1基本概念念与基本本定理定义7满足下述述条件的的流f称为可行流：（1）容量限限制条件件：对每每一弧(vi,vj)∈A（2）平衡条条件：对于中间间点：流流入量等等于流出出量，即即对于每每个i(i≠s,t)，有4.1基本概念念与基本本定理对于发点点vs，记对于收点点vs，记式中v(f)称为这个个可行流流的流量量，即发发点的净净输出量量（或收收点的净净输入量量）。4.1基本概念念与基本本定理最大流问问题就是求一一个流{fij}使其流量量v(f)达到最大大，并且且满足：：4.1基本概念念与基本本定理最大流问问题是一一个特殊殊的求极极大值的的线性规规划问题题。利用用图的特特点，可可以比采采用线性性规划的的一般方方法更为直观观简便地地求解。4.1基本概念念与基本本定理3、增广链若给定一一个可行行流f={fij}，把网络络中使fij=cij的弧称为为饱和弧，使fij<cij的弧称为为非饱和弧弧，使fij=0的弧称为为零流弧，使fij>0的弧称为为非零流弧弧。若μ是网络中中联结发发点vs和收点vt的一条链链,定义链的的方向是是从vs到vt,则链上上的弧被被分为两两类:一一类是弧弧的方向向与链的的方向一一致,称为前向弧；另一类类弧与链链的方向向相反，，称为后向弧。前向弧的的全体记记为μ＋；后向弧的的全体记记为μ－。4.1基本概念念与基本本定理定义8设f是一个可可行流，，μ是网络中中联结发发点vs和收点vt的一条链链。若μ满足下列列条件，，称之为为（关于于可行流流f的)增广链。在弧(vi,vj)∈μ＋上，0≤fij<cij，即μ＋中每一弧弧是非饱饱和弧；；在弧(vi,vj)∈μ－上，0<fij≤cij，即μ－中每一弧弧是非零零和弧；；4.1基本概念念与基本本定理4、截集与截截量设S,T∈V，S∩T=Φ，把始点点在S中、终点在T中的所有有弧构成成的集合合，记为为(S,T)。定义9给定网络络D=(V,A,C)，若点集集V被剖分为为两个非非空集合合V1和，，使，，则把把弧集称称为是是（分离离vs和vt的）截集。显然，若若把某一一截集的的弧从网网络中去去掉，则则从发点点到收点点便不存存在路。。所以，，截集是是从发点点到收点点的必经经之道。。4.1基本概念念与基本本定理定义10给定一截集。把截集中所有弧弧的容量量之和称称为这个个截集的的容量（（简称为为截量），记为为，，即不难证明明，任何何一个可可行流的的流量v(f)都不会超超过任一一截集的的容量，，即4.1基本概念念与基本本定理由截集的的定义可可知：截截集是从从vs到vt的必经之之路，无无论去掉掉哪个截截集，从从vs到vt就不存在在路了。。因此任任何一个个可行流流的流量量不会超超过任何何一个截截集的容容量。因因而若能能找到一一个可行行流和一一个截集集，使得得可行流流的流量量等于这这个截集集的容量量，则该该可行流流一定是是最大流流，该截截集一定定是最小小截集。。4.1基本概念念与基本本定理在上图中中，若令令Vs={vs,v1,v6},Vt={v2,v3,v4,v5,vt},则：截集集为{(vs,v5),(v1,v2),(v1,v5),((v6,v5),((v6,v4)},截量为3+2++4+2+3==14。4.1基本概念念与基本本定理定理8可行流f*是最大流流，当且且仅当不不存在关关于f*的增广链链。（证证明从略略）显然，若若对于一一个可行行流f*，网络中中有一个个截集，，使，，则f*必是最大大流，而而必必定定是D的所有截截集中，，容量最最小的一一个，即即最小截截集。4.1基本概念念与基本本定理若f*是最大流流，则网网络中必必存在一一个截集集，，使最大流量量最小截截量定理理：任一网网络D中，从vs到vt的最大流流等于分分离vs,vt的最小截截集容量量。定理8提供了寻寻求网络络中最大大流的一一个方法法。实际际计算时时，通常常采用标标号法。。第4节网网络最大大流问题题4.2寻求最大大流的标标号法设已有一一个可行行流f(若网络络中没有有给出可可行流，，则可设设f为零流))，标号号法可分分为两步步进行。。1、标号过过程在这个过过程中,,网络中中的点或或者是标标号点，，或者是是未标号号点。每每个标号号点的标标号包含含两个部分分：第一个个标号表表明它的的标号是是从哪一一点得到到的，以以便找出出增广链链；第二二个标号号是为确确定增广广链的调调整量用的。4.2寻求最大大流的标标号法(1)给发点vs以标号（（0，+∞），第二个数数值表示示从上一一标号点点到这个个标号点点的最大大允许调调整量。vs为发点，，不限允允许调整整量，故故为+∞。(2)选择一个个已标号号的点vi，对于vi的所有未未标号的的邻点vj，按下列列规则处处理：若在(vi,vj)上，fij<cij，则令l(vj)=min{l(vi),cij-fij}，并给vj以标号(vi,l(vj))。若在(vj,vi)上，fji>0，则令l(vj)=min{{fji,l(vi)}，并给vj以标号(-vi,l(vj))。4.2寻求最大大流的标标号法(3)重复(2)直到收点点vt被标号或或不再有有点可标标号时为为止。若vt得到标号号，说明明存在一一条增广广链，转转入调整过程程。若vt未得到标标号，标标号过程程已无法法进行时时，说明明f已是最大大流。4.2寻求最大大流的标标号法2、调整过程程(1)确定调整整量=l(vt)。(2)若vt的标号为为(vj,l(vt))，则以fit+代替fit；若vt的标号为为(-vj,l(vt))，则以fit-代替fit。(3)令vj代替vt，返回(2)；若vj=vs，则去掉掉所有标标号转入入标号过过程。4.2寻求最大大流的标标号法例用用标号法法求下图图所示的的网络中中从vs到vt的最大流流量，图图中弧旁旁数值为为容量cij。4.2寻求最大大流的标标号法(1)图中没有有给出初初始可行行流，可可设零流流为出初初始可行行流（如如图1所示）。。先给vs标以标号号(0,++∞)。4.2寻求最大大流的标标号法(2)检查vs的邻点v1,v2，可知在在弧(vs,v1)上，fs1=0<cs1=10。令l(v1)=min{++∞,,10--0}}=10，给v1以标号(vs,10))。用同样样的方法法给v2以标号(vs,14))。见图2。4.2寻求最大大流的标标号法(3)检查v1的尚未标标号的邻邻点v3,v4，可知在在弧(v1,v3)上，f13=0<c13=10。令l(v3)=min{l(v1),10-0}==min{10,10}=10，给v3以标号(v1,10))。用同样样的方法法给v4以标号(v1,10))。见图3。4.2寻求最大大流的标标号法(4)检查v3的尚未标标号的邻邻点v5,v6，可知在弧弧(v3,v5)上，f35=0<c35=4。令l(v5)=min{l(v3),4-0}}=min{{10,,4}==4，给v5以标号(v3,4)。对于v6，由于f63=0，不满足足标号条条件。检查v4的尚未标标号的邻邻点vt，f4t=0<c4t=13。令l(vt)=min{l(v4),13-0}=min{{10,,13}}=10,给vt以标号(v4,10))。见图4。4.2寻求最大大流的标标号法4.2寻求最大大流的标标号法(5)由于vt已得到标标号，则则存在增增广链，，标号过过程结束束，转入入调整过过程。令=l(vt)=10为调整量量，从vt开始，按按标号(v4,10))找到v4并用f4t+10代替f4t；由标号号(v1,10))找到v1并用f14+10代替f14；再由标标号(vs,10))找到vs，并用fs1+10代替fs1，调整过过程结束束。调整整后的可可行流见见图5。4.2寻求最大大流的标标号法去掉所有有标号，，重新开开始标号号过程。。图54.2寻求最大大流的标标号法先给vs以标号(0,++∞)。检查vs的邻点v1,v2，可知fs1=10==cs1=10,,不满足标标号条件件；fs2=0<cs2=14。令l(v2)=min{+∞∞，14-0}==14，给v2以标号(vs,14))。图6用同样的的方法可可得v6的标号(v2,5)，vt的标号(v6,5)。见图6。(v6,5)4.2寻求最大大流的标标号法令=5为调整量量，从vt开始进行行调整，，调整后后的可行行流见下下图。4.2寻求最大大流的标标号法去掉所有有标号，，重新开开始标号号过程。。(0.++∞)(vs,9)(v2,.5))(v3,5)(v3,4)不满足标标号条件件（反向向零流弧弧）(v4,3)4.2寻求最大大流的标标号法令=3为调整量量，从vt开始进行行调整，，调整后后的可行行流见下下图。4.2寻求最大大流的标标号法去掉所有有标号，，重新开开始标号号过程。。(0.++∞)(v2,.2))(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)4.2寻求最大大流的标标号法令=2为调整量量，从vt开始进行行调整，，调整后后的可行行流见下下图。(0.++∞)(v2,.2))(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)4.2寻求最大大流的标标号法去掉所有有标号，，重新开开始标号号过程。。(0.++∞)(vs,4)vt未得到标标号，但但标号过过程已无无法进行行,说明已得得到最大大流.其值为20