系统工程导论

系统工程导论蒋珉东南大学自动化学院本课程学习要求：掌握基本理论；熟悉基本方法；能联系实际，解决问题。本课程学习方法及考核：以课堂讨论、自学为主，教师讲授为辅。考核成绩=大作业成绩（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节图的概念},,,{4321vvvvV},,,,,,{7654321eeeeeeeE无向图实例],[],,[],,[],,[],,[],,[],,[447316415434323212211vvevvevvevvevvevvevve第1节图的概念},,,,,,{7654321vvvvvvvV},,,,,{114321aaaaaA),(),,(),,(),,(),,(),,(),,(),,(),,(),,(),,(76116510459358647546425434233312211vvavvavvavvavvavvavvavvavvavvavva有向图实例第1节图的概念图G或D中的点数记为p(G)或p(D)，边（弧）数记为q(G)或q(D)。简记为p或q。第1节图的概念Evue],[三、术语1、无向图若，则称u，v是e的端点，也称u，v是相邻的。称e是点u（及点v）的关连边。若图G中，某个边e的两个端点相同，则称e是环；若两个点之间有多于一条的边，称这些边为多重边。一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。),(EVG第1节图的概念)(vdG以点v为端点的边的个数称为v的次，记为或。)(vd注意：图中环在计算边时记做两次。称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。第1节图的概念),(EVG定理1图中，所有点的次之和是边数的两倍，即Vvqvd2)(次为奇数的点称为奇点，否则称为偶点。定理2任一图中，奇点的个数为偶数。第1节图的概念给定一个图，一个点边的交错序列，若，则称为一条联结和的链，记为，有时称点为链的中间点。),(EVG)1,,2,1](,[1ktvvetttiii),,,,,,,(112211kkkiiiiiiivveevev12,,kiivv1ivkiv),,,,(121kkiiiivvvv第1节图的概念链中，若，则称之为一个圈，记为。若链中，点都是不同的，则称之为初等链；若圈中，点都是不同的，则称之为初等圈；若链（圈）中含的边均不相同，则称之为简单(链)圈。除非特别说明，链（圈）均指初等链（圈）。),,,,(121kkiiiivvvvkiivv1),,,,(1121iiiivvvvk),,,,(121kkiiiivvvvkkiiiivvvv,,,,121),,,,(1121iiiivvvvk121,,,kiiivvv第1节图的概念),,,,,,,(76354321vvvvvvvv),,,,,,,(76354321vvvvvvvv),,,,(76321vvvvv是一条简单链，但不是初等链，是一条初等链。该图中，不存在联结和的链。是一个初等圈，是简单圈，但不是初等圈。),,,,,,,,(436753214vvvvvvvvv1v9v),,,,(14321vvvvv图中，第1节图的概念图G中，若任何两个点之间，至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每个连通的部分称为G的一个连通分图（简称为分图）。第1节图的概念),(EVG),(EVG给定一个图，如果图，使及，则称是的一个支撑子图。设，用表示从图G中去掉v及v的关联边后得到的一个图。EEVV)(GVvvGGG第1节图的概念),(AVD2、有向图设给定了一个有向图，从D中去掉所有弧上的箭头，就得到了一个无向图，称之为D的基础图，记之为G(D)。给定D中的一条弧，称u为a的始点，v为a的终点，称弧a是从u指向v的。),(vua第1节图的概念设是D中的点弧交错序列，如果该序列在基础图G(D)中所对应的点边序列是一条链，则称该点弧交错序列是D的一条链。类似定义圈和初等链（圈）。如果是D中的一条链，并且对，均有，称之为从到的一条路。若路的第一个点和最后一个点相同，则称之为回路。类似定义初等路（回路）。1,,2,1kt),,,,,,,(112211kkkiiiiiiivavavav1ivkiv),(1tttiiivva),,,,,,,(112211kkkiiiiiiivavavav第1节图的概念1v)),,(,),,(,),,(,(6644433311vvvvvvvvvv6v)),,(,),,(,),,(,),,(,(3355544422233vvvvvvvvvvvvv)),,(,),,(,),,(,(6655353311vvvvvvvvvv是一个回路；是从到的路；是一条链，但不是路。第7章图和网络优化第2节树2.1树及其性质定义1一个无圈的连通图称为树。树是极其简单然而却是非常有用的一类图。2.1树及其性质例4五个城市之间架设电话线。要求任何两个城市都可以相互通话（允许通过其他城市），并且电话线的根数最少。用五个点代表五个城市。若在某两个城市之间架设电话线，则在相应的两个点之间连一条边。这样一个电话线网就可以用一个图来表示。54321,,,,vvvvv2.1树及其性质为了使任何两个城市都可以通话，这样的图必须是连通的。如果图中有圈的话，从圈中去掉任意一条边，剩下的图仍然是连通的。如此可以省去一条电话线。因此，满足要求的电话线网必定是树（无圈的连通图）。2.1树及其性质例5某工厂的组织结构可以表示成一个树。2.1树及其性质定理3设图是一个树，，则G中至少有两个悬挂点。),(EVG2)(Gp1p定理４图是一个树的充分必要条件是G不含圈，且恰有条边。),(EVG定理５图是一个树的充分必要条件是G是连通图，并且),(EVG1)()(GpGq定理６图G是一个树的充分必要条件是任意两个顶点之间恰有一条链。2.1树及其性质推论１从一个树中去掉任意一条边，则余下的图是不连通的。即：在点集合相同的所有图中，树是含边树最少的连通图。推论２在树中不相邻的两个点间添上一条边，则恰好得到一个圈。第2节树2.2图的支撑树定义2设图是图的支撑子图，如果图是一个树，则称T是G的一个支撑树。),(EVG),(EVT),(EVT2.2图的支撑树1p若图是图的一个支撑树，则树Ｔ中边的个树是，G中不属于树T的边数是。),(EVG),(EVT1)()(GpGq定理７图G有支撑树充分必要条件是图G是连通的。利用定理７充分性的证明过程，可以得到一个寻求连通图的支撑树的方法—“破圈法”：任取一个圈，从圈中去掉一边，对余下的图重复该步骤，直到不含圈为止。2.2图的支撑树例6在图7-15中，用“破圈法”求出图的一个支撑树。2.2图的支撑树另外一种寻求连通图的支撑树的方法—“避圈法”：在图中任取一条边，找一条与不构成圈的边，再找一条与不构成圈的边。一般，设已有，找一条与中的任何一条边不构成圈的边。重复上述过程，直到不能进行为止。1e1e2e3e1ke},{21ee},,,{21keee},,,{21keee2.2图的支撑树例7在图7-16中，用“避圈法”求出图的一个支撑树。2.2图的支撑树根据定理４和定理５可知，在“破圈法”中去掉的边数必是条；在“避圈法”中取出的边数必是条。1)(Gp1)()(GpGq第2节树2.3最小支撑树问题定义３给定图，对图G中的每一条边，相应地有一个数，则称这样的图为赋权图，称为边上的权。),(EVG],[jivvij],[jivvij这里所说的“权”是指与边有关的数量指标。可以根据实际问题，赋予它不同的含义。赋权图不仅指出了各个点之间的连结关系，而且同时也表示出各点之间的数量关系。所以，赋权图被广泛地应用于解决最优化问题。2.3最小支撑树问题),(EVG设有一个连通图，每一边，有一个非负权定义４如果图是图G的一个支撑树，称中所有边的权之和为支撑树T的权，记为。即),(EVT],[jivve)0()(ijije)(TTvvijjiT],[)(E2.3最小支撑树问题如果支撑树的权是G的所有支撑树的权中最小者，则称是G的最小支撑树（简称最小树）。即)(*T*T*T)(min)(*TTT式中对G的所有支撑树T取最小。最小支撑树问题就是要求给定连通赋值权图G的最小支撑树。实际应用：城市间交通网的建造问题。两种求最小树的方法：“避圈法”和“破圈法”2.3最小支撑树问题1、避圈法开始选一条权最小的边，以后每一步，总从与已选边不构成圈的那些未选边中，选一条权最小的。在每一步中，如果有两条或两条以上的边都是权最小的边，则从中任选一条。2.3最小支撑树问题1i算法步骤：第1步令（表示空集）；第2步选一条边，使是使不含圈的所有边中权最小的边。令，如果这样的边不存在，则第3步把换成，转入第2步。0,1Ei1\iiEEeie}){,(1eEVi)\(1iEEee}{1eEEii),(1iEV