系统工程导论课件

系统工程导论蒋珉东南大学自动化学院系统工程导论蒋珉1本课程学习要求：掌握基本理论；熟悉基本方法；能联系实际，解决问题。本课程学习要求：掌握基本理论；2本课程学习方法及考核：以课堂讨论、自学为主，教师讲授为辅。 考核成绩=大作业成绩（60%，大作业报告、发言情况）+平时作业（10%）+开卷考试成绩（30%）本课程学习方法及考核：以课堂讨论、自学为主，教师讲授为辅3第7章图和网络优化图论广泛地应用与物理学、化学、控制论、信息、科学管理、电子计算机等领域。很多实际问题可以采用图论的理论和方法来解决。图论的历史最早可以追溯到1736年E.Euler（瑞士数学家）解决著名的哥尼斯堡七桥问题。第7章图和网络优化图论广泛地应用与物理学、化学、控制4第7章图和网络优化原问题：能否走过七座桥，且每座桥只走过一次，最后回到出发点？第7章图和网络优化原问题：能否走过七座桥，且每座桥只5

Euler解题的思路：将原问题化为一笔画问题。图中的每个点都只与奇数条线相关联，不可能不重复地一笔画成。第7章图和网络优化Euler解题的思路：将原问题化为一笔画问题。图中的每6第7章图和网络优化结论：哥尼斯堡七桥问题不可能有解。第7章图和网络优化结论：哥尼斯堡七桥问题不可能有解。7第7章图和网络优化 许多工程问题可以采用图来描述，并且可以化为相应的优化问题，最终采用优化算法来加以解决。由于计算机的普及和大量算法的出现，使得图论方法的应用成为了可能。第7章图和网络优化 许多工程问题可以采用图来描述，并且可8第7章图和网络优化第1节图的概念 图：由点和线组成，可以表示对象之间的相互关系。一、图概念的引进第7章图和网络优化第1节图的概念 图：由点和线组成，可9 第1节图的概念

例1

十个城市之间的铁路交通图。反映了这十个城市之间的铁路分布情况。点代表城市，点与点之间的连线代表相邻两个城市之间的铁路线。 类似的问题还有电话线分布图、煤气管道图、航空线路图等。 第1节图的概念 例1十个城市之间的铁路交通图。反映了10第1节图的概念

例2

球队之间比赛的情况。vi(i=1,…,5)表示五个球队。如果某两个球队比赛过了，则在这两个队所相应的点之间联一条线，这条线不过其它点。第1节图的概念 例2球队之间比赛的情况。vi(i=1,11第1节图的概念

例3

化学药品储存问题。某些药品不能储存在同一个库房里。vi(i=1,…,8)表示八种药品。若药品vi和药品vj

不能储存在同一个库房里，则在它们之间联一条线。需要解决的问题是：至少需要几个库房，能将储存这八种药品第1节图的概念 例3化学药品储存问题。某些药品不能储存12第1节图的概念

图是反映对象之间关系的一种工具，是一种数学抽象。通常用点代表研究的对象，用点与点之间的连线表示这两个对象之间有特定的关系。

注意：图中点的相对位置如何，点与点之间的连线的长短曲直，对于反映对象之间的关系并不重要。第1节图的概念 图是反映对象之间关系的一种工具，是一种数学13第1节图的概念 反映例2中球队之间的比赛情况的两种图没有本质上的区别。第1节图的概念 反映例2中球队之间的比赛情况的两种图没有本14第1节图的概念 例1～例3中涉及到的对象之间的“关系”具有“对称性”。即：如果甲与乙有某种关系，则乙与甲也有同样的这种关系。 在实际生活中，有许多关系不具有这种对称性。例2中的比赛胜负情况就不能用简单的连线来表示。为了反映这种关系，可以用一条带箭头的连线表示。第1节图的概念 例1～例3中涉及到的对象之间的“关系”具有15第1节图的概念二、定义

图：由一些点及一些点之间的连线（带箭头或不带箭头）所组成。

边：两点之间的不带箭头的连线。

弧：两点之间的带箭头的连线。

无向图（简称图）：由点及边构成的图。

有向图：由点及弧构成的图。第1节图的概念二、定义 图：由一些点及一些点之间的连线（带16第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节图的概念 点用集合V={v1,…,vn}表示。 17第1节图的概念 无向图实例第1节图的概念 无向图实例18第1节图的概念 有向图实例第1节图的概念 有向图实例19第1节图的概念 图G或D中的点数记为p(G)或p(D)，边（弧）数记为q(G)或q(D)。简记为p或q。第1节图的概念 图G或D中的点数记为p(G)或p(D)，边20第1节图的概念三、术语1、无向图 若，则称u，v是e的端点，也称u，v是相邻的。称e是点u（及点v）的关连边。 若图G中，某个边e的两个端点相同，则称e是环；若两个点之间有多于一条的边，称这些边为多重边。 一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。第1节图的概念三、术语1、无向图 若21第1节图的概念 以点v为端点的边的个数称为v的次，记为或。

注意：图中环在计算边时记做两次。 称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。第1节图的概念 以点v为端点的边的个数称为v的次，记为22第1节图的概念

定理1图中，所有点的次之和是边数的两倍，即 次为奇数的点称为奇点，否则称为偶点。

定理2任一图中，奇点的个数为偶数。第1节图的概念 定理1图中，23第1节图的概念 给定一个图，一个点边的交错序列，若，则称为一条联结和的链，记为，有时称点为链的中间点。第1节图的概念 给定一个图，一个点24第1节图的概念 链中，若，则称之为一个圈，记为。若链中，点都是不同的，则称之为初等链；若圈中，点都是不同的，则称之为初等圈；若链（圈）中含的边均不相同，则称之为简单(链)圈。除非特别说明，链（圈）均指初等链（圈）。第1节图的概念 链25第1节图的概念是一条简单链，但不是初等链，是一条初等链。该图中，不存在联结和的链。 是一个初等圈，是简单圈，但不是初等圈。图中，第1节图的概念是一条简单链，但不是初等链，26第1节图的概念 图G中，若任何两个点之间，至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每个连通的部分称为G的一个连通分图（简称为分图）。第1节图的概念 图G中，若任何两个点之间，至少有一条链，则27第1节图的概念 给定一个图，如果图，使 及，则称是的一个支撑子图。 设，用表示从图G中去掉v及v的关联边后得到的一个图。第1节图的概念 给定一个图，如果图28第1节图的概念2、有向图 设给定了一个有向图，从D中去掉所有弧上的箭头，就得到了一个无向图，称之为D的基础图，记之为G(D)。 给定D中的一条弧，称u为a的始点，v为a的终点，称弧a是从u指向v的。第1节图的概念2、有向图 设给定了一个有向图29第1节图的概念 设是D中的点弧交错序列，如果该序列在基础图G(D)中所对应的点边序列是一条链，则称该点弧交错序列是D的一条链。类似定义圈和初等链（圈）。 如果是D中的一条链，并且对，均有，称之为从到的一条路。若路的第一个点和最后一个点相同，则称之为回路。类似定义初等路（回路）。第1节图的概念 设30第1节图的概念 是一个回路； 是从到的路； 是一条链，但不是路。第1节图的概念 是一个回路31第7章图和网络优化第2节树2.1树及其性质

定义1一个无圈的连通图称为树。 树是极其简单然而却是非常有用的一类图。第7章图和网络优化第2节树2.1树及其性质 定义322.1树及其性质 例4

五个城市之间架设电话线。要求任何两个城市都可以相互通话（允许通过其他城市），并且电话线的根数最少。 用五个点 代表五个城市。若在某两个城市之间架设电话线，则在相应的两个点之间连一条边。这样一个电话线网就可以用一个图来表示。2.1树及其性质 例4五个城市之间架设电话线。要求任何332.1树及其性质 为了使任何两个城市都可以通话，这样的图必须是连通的。 如果图中有圈的话，从圈中去掉任意一条边，剩下的图仍然是连通的。如此可以省去一条电话线。因此，满足要求的电话线网必定是树（无圈的连通图）。2.1树及其性质 为了使任何两个城市都可以通话，这样的图342.1树及其性质 例5

某工厂的组织结构可以表示成一个树。2.1树及其性质 例5某工厂的组织结构可以表示成一个352.1树及其性质 定理3设图是一个树， ，则G中至少有两个悬挂点。 定理４图是一个树的充分必要条件是G不含圈，且恰有条边。 定理５图是一个树的充分必要条件是G是连通图，并且 定理６图G是一个树的充分必要条件是任意两个顶点之间恰有一条链。2.1树及其性质 定理3设图362.1树及其性质 推论１从一个树中去掉任意一条边，则余下的图是不连通的。即：在点集合相同的所有图中，树是含边树最少的连通图。 推论２在树中不相邻的两个点间添上一条边，则恰好得到一个圈。2.1树及其性质 推论１从一个树中去掉任意一条边，则余37第2节树2.2图的支撑树

定义2设图是图的支撑子图，如果图是一个树，则称T是G的一个支撑树。第2节树2.2图的支撑树 定义2设图是382.2图的支撑树 若图是图的一个支撑树，则树Ｔ中边的个树是，G中不属于树T的边数是。 定理７图G有支撑树充分必要条件是图G是连通的。 利用定理７充分性的证明过程，可以得到一个寻求连通图的支撑树的方法—“破圈法”：任取一个圈，从圈中去掉一边，对余下的图重复该步骤，直到不含圈为止。2.2图的支撑树 若图是图的一个支撑树，392.2图的支撑树 例6在图7-15中，用“破圈法”求出图的一个支撑树。2.2图的支撑树 例6在图7-15中，用“破圈法”求402.2图的支撑树 另外一种寻求连通图的支撑树的方法—“避圈法”：在图中任取一条边，找一条与不构成圈的边，再找一条与不构成圈的边。一般，设已有，找一条与中的任何一条边不构成圈的边。重复上述过程，直到不能进行为止。2.2图的支撑树 另外一种寻求连通图的支撑树的方法—“避412.2图的支撑树 例7在图7-16中，用“避圈法”求出图的一个支撑树。2.2图的支撑树 例7在图7-16中，用“避圈法”求422.2图的支撑树 根据定理４和定理５可知，在“破圈法”中去掉的边数必是 条；在“避圈法”中取出的边数必是 条。2.2图的支撑树 根据定理４和定理５可知，在“破圈法”中43第2节树2.3最小支撑树问题

定义３给定图，对图G中的每一条边，相应地有一个数，则称这样的图为赋权图，称为边上的权。 这里所说的“权”是指与边有关的数量指标。可以根据实际问题，赋予它不同的含义。 赋权图不仅指出了各个点之间的连结关系，而且同时也表示出各点之间的数量关系。所以，赋权图被广泛地应用于解决最优化问题。第2节树2.3最小支撑树问题 定义３给定图442.3最小支撑树问题 设有一个连通图 ，每一边 ，有一个非负权

定义４如果图是图G的一个支撑树，称中所有边的权之和为支撑树T的权，记为。即2.3最小支撑树问题 设有一个连通图 ，每一边 ，452.3最小支撑树问题 如果支撑树的权是G的所有支撑树的权中最小者，则称是G的最小支撑树（简称最小树）。即式中对G的所有支撑树T取最小。 最小支撑树问题就是要求给定连通赋值权图G的最小支撑树。 实际应用：城市间交通网的建造问题。 两种求最小树的方法：“避圈法”和“破圈法”2.3最小支撑树问题 如果支撑树的权是G的所有支462.3最小支撑树问题1、避圈法

开始选一条权最小的边，以后每一步，总从与已选边不构成圈的那些未选边中，选一条权最小的。在每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条。2.3最小支撑树问题1、避圈法472.3最小支撑树问题算法步骤： 第1步令（表示空集）； 第2步选一条边 ，使是使 不含圈的所有边 中权最小的边。令 ，如果这样的边不存在，则 第3步把换成 ，转入第2步。2.3最小支撑树问题算法步骤：482.3最小支撑树问题例8已知某工厂内联结六个车间的道路网及每条道路的长，要求沿道路架设六个车间的电话线网，是电话线的总长度最小。2.3最小支撑树问题例8已知某工厂内联结492.3最小支撑树问题2、破圈法

任取一个圈，从圈中去掉权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中的一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止。这时的图就是最小树。2.3最小支撑树问题2、破圈法502.3最小支撑树问题 例9

用破圈法求例8中的最小支撑树。2.3最小支撑树问题 例9用破圈法求例8中的最小支撑51第7章图和网络优化第3节最短路问题3.1引例 例10如图7-18所示的单行线交通网，每弧旁的数字表示通过该单行线所需的费用。从v1出发到v8，求使总费用为最小的旅行路线。第7章图和网络优化第3节最短路问题3.1引例 例523.1引例 显然，从v1到v8

的旅行线路很多。不同的路线，所需的总费用是不同的。一条旅行线路的总费用就是相应的从v1到v8

的路中所有弧旁数字之和。

注意：这里所说的路可以不是初等路。3.1引例 显然，从v1到v8的旅行线路很多。不同的路533.1引例一般的最短路问题：

给定一个赋权有向图，即给定一个有向图D=(V,A),对每个弧a=(vi,vj),有权ω(a)=ωij。又给定D中两个顶点vs和vt。设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为ω(P)。 最短路问题就是要在所有从vs到vt的路中，找一条权最小的路，即寻找P0，使3.1引例一般的最短路问题： 给定一个赋权有向图，即给定543.1引例上式中，称：P0是从vs到vt的最短路；路P0的权为从vs到vt的距离，记为d(vs,vt)。 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型．如设备更新、管道铺设、线路安排、厂区布局等。3.1引例上式中，称：P0是从vs到vt的最短路；路P55第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节最短路问题Dijkstra算法思路—563.2最短路算法

Dijkstra算法的基本步骤，采用标号法。 用两种标号：T标号与P标号，T标号为试探性标号，P为永久性标号。给vi点一个P标号时，表示从vs到点vi的最短路权,vi点的标号不再改变。给vi点一个T标号时，表示从vs到vi点的估计最短路权的上界，是一种临时标号。凡没有得到P标号的点都有T标号。3.2最短路算法 Dijkstra算法的基本步骤，采用标573.2最短路算法

算法的每一步都把某一点的T标号改为P标号，当终点vt得到P标号时，全部计算结束。对于有n个顶点的图，最多经n-1步就可以得到从始点到终点的最短路。 标号的意义：

①标号P(永久性标号)—从始点到该标号点的最短路权； ②标号T(临时性标号)—从始点到该标号点的最短路权上界。3.2最短路算法 算法的每一步都把某一点的T标号改为P标583.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最短路算法 计算步骤 第1步给始点vs标上永久593.2最短路算法

第3步比较所有具有T标号的点，把最小者改为P标号，即当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则用代vi转回第二步。3.2最短路算法 第3步比较所有具有T标号的点，把最603.2最短路算法 例用Dijkstra算法求下图中v1到v7点的最短路。•••••••v1v2v7v5v4171344452572v33.2最短路算法 例用Dijkstra算法求下613.2最短路算法图中()内的数表示P标号，[]内的数表示T标号。•••••••v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7

(1)首先给v1以P标号,P(v1)=0,其余所有点给T标号,T(vi)=+∞；3.2最短路算法图中()内的数表示P标号，[]内的数623.2最短路算法

(2)由于弧(v1,v2)、(v1,v3)、(v1,v4)属于D，且v2、

v3、

v4为T标号，所以修改这三个点的标号：

T(v2)=min{T(v2),P(v1)+ω12}=min{∞,0+4}=4

T(v3)=min{T(v3),P(v1)+ω13}=min{∞,0+2}=2

T(v4)=min{T(v4),P(v1)+ω14}=min{∞,0+5}=5•••••••v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞]73.2最短路算法(2)由于弧(v1,633.2最短路算法(3)比较所有T标号，T(v3)最小，故令P(v3)=2•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]73.2最短路算法(3)比较所有T标号，643.2最短路算法(4)v3为刚得到P标号的点，考察弧(v3,v4)，(v3,v6)的端点v4,v6

T(v4)=min{T(v4),P(v3)+ω34}=min{5,2+2}=4

T(v6)=min{T(v6),P(v3)+ω36}=min{∞,2+7}=9•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]73.2最短路算法(4)v3为刚得到P标653.2最短路算法

(5)比较所有T标号，T(v2),T(v4)最小，所以令P(v2)=P(v4)=4•••••••v1(0)v2v7v5v411344452572v3(2)v6[4][4][9][∞][∞]73.2最短路算法(5)比较所有T标号，663.2最短路算法•••••••v1(0)v2v7v5v411344452572v3(2)v6(4)(4)[9][∞][∞]73.2最短路算法•••••••v1v2v7v5v4113673.2最短路算法

(6)v2,v4为刚得到P标号的点,考察弧(v2,v5)，(v4,v5)，(v4,v6)的端点v5,v6

T(v5)=min{T(v5),P(v4)+ω45,P(v2)+ω25} =min{∞,4+3,4+4}=7

T(v6)=min{T(v6),P(v4)+ω46}=min{9,4+4}=8•••••••v1(0)v2v7v5v411344452572(4)(4)[8][7][∞]7v3(2)v63.2最短路算法(6)v2,v4为刚683.2最短路算法

(7)比较所有T标号，T(v5)最小，所以令P(v5)=7•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[∞][8]v3(2)v673.2最短路算法(7)比较所有T标号，T(v5693.2最短路算法•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[14][8]v3(2)v6(8)v5为刚得到P标号的点，考察弧(v5,v6)，(v5,v7)的端点v6,v7

T(v6)=min{T(v6),P(v5)+ω56}=min{8,7+1}=8

T(v7)=min{T(v7),P(v5)+ω57}=min{∞,7+7}=1473.2最短路算法•••••••v1v2v7v5v4113703.2最短路算法

(9)比较所有T标号，T(v6)最小，所以令P(v6)=8•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[14](8)v3(2)v673.2最短路算法(9)比较所有T标号，T(v713.2最短路算法

(10)v6为刚得到P标号的点，考察弧(v6,v7)的端点v7

T(v7)=min{T(v7),P(v6)+ω67}=min{14,8+5}=13•••••••v1(0)v2v7v5v411344452572(4)(4)(7)[13](8)v3(2)v673.2最短路算法(10)v6为刚得723.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)只有一个T标733.2最短路算法例11用Dijkstra算法求图7-19中v1到v8的最短路。

计算过程略，v1到v8的最短路为：3.2最短路算法例11用Dijkstr743.2最短路算法 Dijkstra算法只适用于全部权为非负情况．如果某弧的权为负，算法失效。

负权的情况自学讨论。3.2最短路算法 Dijkstra算法只适用于全部权为非75第3节最短路问题 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型．如设备更新、管道铺设、线路安排、厂区布局等。3.3应用举例第3节最短路问题 最短路问题是网络理论中应用最广泛的问题763.3应用举例例(设备更新问题)某企业在四年内都要使用某种设备，在每年年初作出是购买新设备还是继续使用旧设备的决策。若购买新设备就要支付购置费；若继续使用旧设备，则需支付维修费用。这种设备在四年之内每年年初的价格以及使用不同时间（年）的设备的维修费用估计为：年份1234年初购价10111213维修费用247143.3应用举例例(设备更新问题)某企业在四年内773.2应用举例

问题：制定一个四年之内的设备更新计划，使得四年之内的设备购置费和维修费用之和最小。 可以用求最短路问题的方法来解决总费用最少的设备更新计划问题。3.2应用举例问题：制定一个四年之783.3应用举例符号的含义：vi—第i年年初购进一台新设备(v5表示第四年年底)；弧(vi,vj)—第i年年初购进的设备一直使用到第j年年初(即第j-1年年底)；弧(vi

,vj)的权数—从第i年年初购进的设备一直使用到第j年年初所花费的购置费和维修费用的总和。3.3应用举例符号的含义：793.3应用举例如何制定使得总费用最少的设备更新计划问题可以转化最短路问题。此最短路问题如图所示。3.3应用举例如何制定使得总费用最少的设备803.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应用举例 图中权数ij的确定：813.3应用举例 如何制定使得总费用最少的设备更新计划问题可以转化最短路问题。此最短路问题如图所示。3.3应用举例 如何制定使得总费用最少的设备更新计划问题823.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应用举例图中权数ij的确定：833.3应用举例

用Dijkstra算法求v1到v5的最短路。(1)给v1以P标号,P(v1)=0,其余各点给以T标号T(vi)=+∞(i=2,3,4,5)（图中()内的数表示P标号；[]内的数表示T标号）3.3应用举例 用Dijkstra算法求v1到843.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应用举例 (2)由于（v1,v2）,(v1,v3)853.3应用举例

(3)比较所有具有T标号的点，把最小者改为P标号。T(v2)最小，令P(v2)=12。

3.3应用举例 (3)比较所有具有T标号的点，把最小者863.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应用举例(4)v2为刚得到P标号的点，考察873.3应用举例(5)比较所有具有T标号的点，把最小者改为P标号。T(v3)最小，令P(v3)=16。

3.3应用举例(5)比较所有具有T标号的点，把最小883.3应用举例

(6)考察点v3

T(v4)=min{T(v4),P(v3)+34}=min{23,16+14}=23

T(v5)=min{T(v5),P(v3)+35}=min{36,16+18}=34 (7)所有T标号中，T(v4)最小，令P(v4)=233.3应用举例 (6)考察点v3893.3应用举例

(8)考察点v4

T(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应用举例 (8)考察点v4 由上可知：v1到v5903.3应用举例 例13(类似）自己完成。3.3应用举例 例13(类似）自己完成。91第7章图和网络优化 最大流问题是在一个给定网络上求流量最大的可行流，即给一个网络的每条弧规定一个流量的上界，求从点vs到vt的最大流。第4节网络最大流问题第7章图和网络优化 最大流问题是在一个给定网络上求流量最92第4节网络最大流问题

下图是一个输油管道网，vs为起点，vt为终点，v1~v6为中转站，弧旁的数表示该管道的最大输油量。 问题：如何安排，才能使从vs到vt的输油量最大？第4节网络最大流问题 下图是一个输油管道网，vs为起点，93第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节网络最大流问题4.1基本概念与基本定理1、网络944.1基本概念与基本定理

所谓网络上的流，是指定义在弧集合A上的一个函数f={f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量（简记为fij)。 图7-23和图7-24给出了发点、收点、弧的容量和弧的流量的例子。4.1基本概念与基本定理 所谓网络上的流，是指定义在弧集954.1基本概念与基本定理2、可行流与最大流

在运输网络的实际问题中，对流有两个明显的要求：①每个弧上的流量不能超过该弧的最大通行能力（即弧的容量）；②中间点的流量为零。 理由：对于每一个点，运出该点的产品总量与运出该点的产品总量之差为该点的净输出量，简称为该点的流量；中间点只起转运作用，其流量为零。 易见，发点的净流出量与收点的净流入量相等，也就是该方案的总输送量。4.1基本概念与基本定理2、可行流与最大流 在运输网络的964.1基本概念与基本定理 定义7

满足下述条件的流f称为可行流：

（1）容量限制条件：对每一弧(vi,vj)∈A

（2）平衡条件： 对于中间点：流入量等于流出量，即对于每个i(i≠s,t)，有4.1基本概念与基本定理 定义7满足下述条件的流f974.1基本概念与基本定理

对于发点vs，记

对于收点vs，记 式中v(f)称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。4.1基本概念与基本定理 对于发点vs，记 对于收点v984.1基本概念与基本定理

最大流问题就是求一个流{fij}使其流量v(f)达到最大，并且满足：4.1基本概念与基本定理 最大流问题就是求一个流{fij994.1基本概念与基本定理 最大流问题是一个特殊的求极大值的线性规划问题。利用图的特点，可以比采用线性规划的一般方法更为直观简便地求解。4.1基本概念与基本定理 最大流问题是一个特殊的求极大值1004.1基本概念与基本定理3、增广链

若给定一个可行流f={fij}，把网络中使fij=cij的弧称为饱和弧，使fij<cij的弧称为非饱和弧，使fij=0的弧称为零流弧，使fij>0的弧称为非零流弧。

若μ是网络中联结发点vs和收点vt的一条链,定义链的方向是从vs到vt,则链上的弧被分为两类:一类是弧的方向与链的方向一致,称为前向弧；另一类弧与链的方向相反，称为后向弧。前向弧的全体记为μ＋

；后向弧的全体记为μ－

。4.1基本概念与基本定理3、增广链 若给定一个可行流f1014.1基本概念与基本定理 定义8

设f是一个可行流，μ是网络中联结发点vs和收点vt的一条链。若μ满足下列条件，称之为（关于可行流f的)增广链。

在弧(vi,vj)∈μ＋上，0≤fij<cij，即μ＋中每一弧是非饱和弧；

在弧(vi,vj)∈μ－上，0<fij≤

cij，即μ－中每一弧是非零和弧；

4.1基本概念与基本定理 定义8设f是一个可行流1024.1基本概念与基本定理4、截集与截量

设S,T∈V，S∩T=Φ，把始点在S中、终点在T中的所有弧构成的集合，记为(S,T)。 定义9

给定网络D=(V,A,C)，若点集V被剖分为两个非空集合V1和，使，则把弧集称为是（分离vs和vt的）截集。 显然，若把某一截集的弧从网络中去掉，则从发点到收点便不存在路。所以，截集是从发点到收点的必经之道。4.1基本概念与基本定理4、截集与截量 设S,T∈V，S1034.1基本概念与基本定理 定义10

给定一截集。把截集

中所有弧的容量之和称为这个截集的容量（简称为截量），记为，即

不难证明，任何一个可行流的流量v(f)都不会超过任一截集的容量，即4.1基本概念与基本定理 定义10给定一截集1044.1基本概念与基本定理

由截集的定义可知：截集是从vs到vt的必经之路，无论去掉哪个截集，从vs到vt就不存在路了。因此任何一个可行流的流量不会超过任何一个截集的容量。因而若能找到一个可行流和一个截集，使得可行流的流量等于这个截集的容量，则该可行流一定是最大流，该截集一定是最小截集。

4.1基本概念与基本定理由截集的定义1054.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基本概念与基本定理 在上图中，若令Vs={vs,v1064.1基本概念与基本定理 定理8可行流f*是最大流，当且仅当不存在关于f*的增广链。（证明从略）

显然，若对于一个可行流f*，网络中有一个截集，使，则f*必是最大流，而必定是D的所有截集中，容量最小的一个，即最小截集。4.1基本概念与基本定理 定理8可行流f*是最大流，1074.1基本概念与基本定理

若f*是最大流，则网络中必存在一个截集，使

最大流量最小截量定理：任一网络D中，从vs到vt的最大流等于分离vs,vt的最小截集容量。

定理8提供了寻求网络中最大流的一个方法。实际计算时，通常采用标号法。4.1基本概念与基本定理 若f*是最大流，则网络中必存在108第4节网络最大流问题4.2寻求最大流的标号法 设已有一个可行流f(若网络中没有给出可行流，则可设f为零流)，标号法可分为两步进行。1、标号过程 在这个过程中,网络中的点或者是标号点，或者是未标号点。每个标号点的标号包含两个部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。第4节网络最大流问题4.2寻求最大流的标号法 设已有1094.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寻求最大流的标号法 (1)给发点vs以标号（0，1104.2寻求最大流的标号法 (3)重复(2)直到收点vt被标号或不再有点可标号时为止。 若vt得到标号，说明存在一条增广链，转入调整过程。 若vt未得到标号，标号过程已无法进行时，说明f已是最大流。4.2寻求最大流的标号法 (3)重复(2)直到收点vt1114.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寻求最大流的标号法2、调整过程 (1)确定调整量1124.2寻求最大流的标号法

例用标号法求下图所示的网络中从vs到vt的最大流量，图中弧旁数值为容量cij。4.2寻求最大流的标号法 例用标号法求下图所示的网络1134.2寻求最大流的标号法 (1)图中没有给出初始可行流，可设零流为出初始可行流（如图1所示）。 先给vs标以标号(0,+∞)。4.2寻求最大流的标号法 (1)图中没有给出初始可行流1144.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寻求最大流的标号法 (2)检查vs的邻点v1,v1154.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寻求最大流的标号法 (3)检查v1的尚未标号的邻1164.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)检查v3的尚未标号的邻1174.2寻求最大流的标号法4.2寻求最大流的标号法1184.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寻求最大流的标号法 (5)由于vt已得到标号，则存1194.2寻求最大流的标号法

去掉所有标号，重新开始标号过程。图54.2寻求最大流的标号法 去掉所有标号，重新开始标号过程1204.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寻求最大流的标号法 先给vs以标号(0,+∞)。检1214.2寻求最大流的标号法 令=5为调整量，从vt开始进行调整，调整后的可行流见下图。4.2寻求最大流的标号法 令=5为调整量，从vt开始1224.2寻求最大流的标号法

去掉所有标号，重新开始标号过程。(0.+∞)(vs,9)(v2,.5)(v3,5)(v3,4)不满足标号条件（反向零流弧）(v4,3)4.2寻求最大流的标号法 去掉所有标号，重新开始标号过程1234.2寻求最大流的标号法

令

=3为调整量，从vt开始进行调整，调整后的可行流见下图。4.2寻求最大流的标号法 令=3为调整量，从vt开始1244.2寻求最大流的标号法 去掉所有标号，重新开始标号过程。(0.+∞)(v2,.2)(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)4.2寻求最大流的标号法 去掉所有标号，重新开始标号过程1254.2寻求最大流的标号法 令=2为调整量，从vt开始进行调整，调整后的可行流见下图。(0.+∞)(v2,.2)(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)4.2寻求最大流的标号法 令=2为调整量，从vt开始1264.2寻求最大流的标号法去掉所有标号，重新开始标号过程。(0.+∞)(vs,4)vt未得到标号，但标号过程已无法进行,说明已得到最大流.其值为20。4.2寻求最大流的标号法去掉所有标号，重新开始标号过程。1274.2寻求最大流的标号法(0.+∞)(vs,4) 用标号法在得到最大流的同时也得到最小截集(如图中虚线所示)。标号点集合为VS，即VS={vs,v2}，未标号点集合为Vt，即Vt={v1,v3,v4,v5,v6,vt}，最小截集{(vs,v1),(v2,v3),(v2,v6)}。 最小截集的意义：最小截集中各弧的容量总和决定了网络的通过能力，为了提高网络的通过能力，就必须增大最小截集中弧的容量。4.2寻求最大流的标号法(0.+∞)(vs,4) 用标号128第7章图和网络优化第5节最小费用最大流问题

最小费用最大流问题：给定了一个带收发点的网络，对每一条弧(vi,vj),除了给出容量cij外，还给出了这条弧的单位流量的费用b(vi,vj)≥0(简记为bij），要求一个最大流f，并使流的总运送费用取极小值。第7章图和网络优化第5节最小费用最大流问题 最小费用129第5节最小费用最大流问题 最小费用最大流的网络图论解法较麻烦，因此下面结合实例介绍用线性规划模型求解最小费用最大流问题。第5节最小费用最大流问题 最小费用最大流的网络图论解法较130第5节最小费用最大流问题 例某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点。这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道(vi,vj)的容量cij(单位：万加仑/小时，各段管道单位流量的费用为bij(单位：百元/万加仑)。如图，从采地v1向销地v7运送石油。问：怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用(弧旁括号中第一个数表示容量cij,第二个数表示单位流量的费用bij)。第5节最小费用最大流问题 例某石油公司拥有一个管道网131第5节最小费用最大流问题(6,6)(3,4)(5,7)(2,5)(2,4)(2,3)(4,4)(1,3)(2,8)(6,3)(3,2)v1v2v7v4v3v6第5节最小费用最大流问题(6,6)(3,4)(5,7)(132第5节最小费用最大流问题 用线性规划模型求解该问题，可分为两个步骤:

第一步先求出此网络图中的最大流量F，利用上一节介绍的内容，获得以下结果： f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2， f36=2，f57=5，f67=3；最大流量F=10。第5节最小费用最大流问题 用线性规划模型求解该问题，可分133第5节最小费用最大流问题

第二步在最大流量f的所有解中,找出一个最小费用的解。下面建立第二步中的线性规划模型如下：仍然设弧(vi,vj)上的流量为fij，这时已知网络中最大流量为F。第5节最小费用最大流问题 第二步在最大流量f的所134第5节最小费用最大流问题 线性规划模型如下：第5节最小费用最大流问题 线性规划模型如下：135第5节最小费用最大流问题

解此线性规划模型，可求得如下结果：f12=4，f14=6，f23=1，f25=3，f36=2，f35=2，f43=3，f46=1，f47=2，f57=5，f67=3；最优值(最小费用)=145。

与前面求最大流的结果对比：f12=5，f14=5，f23=2，f25=3，f35=2，f36=2，f43=2，f46=1，f47=2，f57=5，f67=3；最大流量=10。第5节最小费用最大流问题 解此线性规划模型，可求得如下结136第5节最小费用最大流问题

如果把上例的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在上例中只要把f12+f14=F改为f12+f14=f=6，就得到了最小费用流的线性规划的模型。第5节最小费用最大流问题 如果把上例的问题改为：每小时运137系统工程导论蒋珉东南大学自动化学院系统工程导论蒋珉138本课程学习要求：掌握基本理论；熟悉基本方法；能联系实际，解决问题。本课程学习要求：掌握基本理论；139本课程学习方法及考核：以课堂讨论、自学为主，教师讲授为辅。 考核成绩=大作业成绩（60%，大作业报告、发言情况）+平时作业（10%）+开卷考试成绩（30%）本课程学习方法及考核：以课堂讨论、自学为主，教师讲授为辅140第7章图和网络优化图论广泛地应用与物理学、化学、控制论、信息、科学管理、电子计算机等领域。很多实际问题可以采用图论的理论和方法来解决。图论的历史最早可以追溯到1736年E.Euler（瑞士数学家）解决著名的哥尼斯堡七桥问题。第7章图和网络优化图论广泛地应用与物理学、化学、控制141第7章图和网络优化原问题：能否走过七座桥，且每座桥只走过一次，最后回到出发点？第7章图和网络优化原问题：能否走过七座桥，且每座桥只142

Euler解题的思路：将原问题化为一笔画问题。图中的每个点都只与奇数条线相关联，不可能不重复地一笔画成。第7章图和网络优化Euler解题的思路：将原问题化为一笔画问题。图中的每143第7章图和网络优化结论：哥尼斯堡七桥问题不可能有解。第7章图和网络优化结论：哥尼斯堡七桥问题不可能有解。144第7章图和网络优化 许多工程问题可以采用图来描述，并且可以化为相应的优化问题，最终采用优化算法来加以解决。由于计算机的普及和大量算法的出现，使得图论方法的应用成为了可能。第7章图和网络优化 许多工程问题可以采用图来描述，并且可145第7章图和网络优化第1节图的概念 图：由点和线组成，可以表示对象之间的相互关系。一、图概念的引进第7章图和网络优化第1节图的概念 图：由点和线组成，可146 第1节图的概念

例1

十个城市之间的铁路交通图。反映了这十个城市之间的铁路分布情况。点代表城市，点与点之间的连线代表相邻两个城市之间的铁路线。 类似的问题还有电话线分布图、煤气管道图、航空线路图等。 第1节图的概念 例1十个城市之间的铁路交通图。反映了147第1节图的概念

例2

球队之间比赛的情况。vi(i=1,…,5)表示五个球队。如果某两个球队比赛过了，则在这两个队所相应的点之间联一条线，这条线不过其它点。第1节图的概念 例2球队之间比赛的情况。vi(i=1,148第1节图的概念

例3

化学药品储存问题。某些药品不能储存在同一个库房里。vi(i=1,…,8)表示八种药品。若药品vi和药品vj

不能储存在同一个库房里，则在它们之间联一条线。需要解决的问题是：至少需要几个库房，能将储存这八种药品第1节图的概念 例3化学药品储存问题。某些药品不能储存149第1节图的概念

图是反映对象之间关系的一种工具，是一种数学抽象。通常用点代表研究的对象，用点与点之间的连线表示这两个对象之间有特定的关系。

注意：图中点的相对位置如何，点与点之间的连线的长短曲直，对于反映对象之间的关系并不重要。第1节图的概念 图是反映对象之间关系的一种工具，是一种数学150第1节图的概念 反映例2中球队之间的比赛情况的两种图没有本质上的区别。第1节图的概念 反映例2中球队之间的比赛情况的两种图没有本151第1节图的概念 例1～例3中涉及到的对象之间的“关系”具有“对称性”。即：如果甲与乙有某种关系，则乙与甲也有同样的这种关系。 在实际生活中，有许多关系不具有这种对称性。例2中的比赛胜负情况就不能用简单的连线来表示。为了反映这种关系，可以用一条带箭头的连线表示。第1节图的概念 例1～例3中涉及到的对象之间的“关系”具有152第1节图的概念二、定义

图：由一些点及一些点之间的连线（带箭头或不带箭头）所组成。

边：两点之间的不带箭头的连线。

弧：两点之间的带箭头的连线。

无向图（简称图）：由点及边构成的图。

有向图：由点及弧构成的图。第1节图的概念二、定义 图：由一些点及一些点之间的连线（带153第1节图的概念 点用集合V={v1,…,vn}表示。 联结