5第五章图与网络分析

格式：ppt
大小：1.49 MB
文档页数：51

下载文档原格式

/ 51

汽车服务系统规划教学大纲

《汽车服务系统规划》课程教学大纲课程编号：适用专业：汽车服务工程专业学时数：32学分数：2.0执笔者：周斌编写日期：2014年3月一、课程的性质和目的《汽车服务系统规划》是四年制本科汽车服务工程专业的一门专业技术课程。

作为本专业课程结构体系中的主要专业课，主要研究汽车服务系统的线性规划、整数规划、动态规划问题；汽车服务系统的排队论、存储轮及预测的相关知识；系统评价的方法。

通过本课程的学习，要使学生：（1）对汽车服务系统的各种规划方法有所了解。

（2）为今后从事产品设计、产品制造、企业管理、产品售后技术服务等方面的工作提供基础知识和方法。

（3）使学生学会用科学的方法，对汽车进行必要的、合理的技术维修，以便更好地发挥汽车运输生产的经济效益。

二、课程的教学内容和学时分配第一章系统和系统分析（2学时）教学内容：系统和系统工程的概念，汽车服务系统概念；系统分析的概念，系统科学的一般性研究方法；系统分析的方法。

教学要求：1．理解系统和系统工程的概念，汽车服务系统概念；系统分析的概念； 2．掌握系统科学的一般性研究方法。

重点：掌握系统科学的一般性研究方法。

难点：系统科学的一般性研究方法。

第二章线性规划（4学时）教学内容：线性规划的问题及数学模型；线性规划问题的图解法；线性规划问题的基本概念个性质；平单纯形法的算法和步骤，单纯形表；运输问题及其解法，运输问题的数学模型，表上作业法，产销不平衡的运输问题；线性规划方法在汽车服务系统中的应用。

教学要求：掌握线性规划的问题及数学模型；掌握线性规划问题的图解法；掌握单纯形法的算法和步骤，单纯形表；理解线性规划方法在汽车服务系统中的应用。

重点：掌握线性规划的问题及数学模型；掌握线性规划问题的图解法；掌握单纯形法的算法和步骤，单纯形表。

难点：线性规划的问题及数学模型；线性规划问题的图解法；单纯形法的算法和步骤，单纯形表。

第三章整数规划（4学时）教学内容：整数规划问题的提出；整数规划的基本解法，分枝定界法，割平面法，0—1规划，指派问题；整数规划在汽车服务系统中的应用。

模电第五章答案解析

【例5-1】电路如图 (a)、(b)所示。

（1）判断图示电路的反馈极性及类型；（2）求出反馈电路的反馈系数。

图(a) 图(b)【相关知识】负反馈及负反馈放大电路。

【解题思路】（1）根据瞬时极性法判断电路的反馈极性及类型。

（2）根据反馈网络求电路的反馈系数。

【解题过程】（1）判断电路反馈极性及类型。

在图(a)中，电阻网络构成反馈网络，电阻两端的电压是反馈电压，输入电压与串联叠加后作用到放大电路的输入端（管的）；当令=0时，＝0，即正比与；当输入信号对地极性为♁时，从输出端反馈回来的信号对地极性也为♁，故本电路是电压串联负反馈电路。

在图（b）电路中，反馈网络的结构与图（a）相同，反馈信号与输入信号也时串联叠加，但反馈网络的输入量不是电路的输出电压而是电路输出电流（集电极电流），反馈极性与图（a）相同，故本电路是电流串联负反馈电路。

（2）为了分析问题方便，画出图(a) 、(b)的反馈网络分别如图（c）、(d)所示。

图(c) 图(d)由于图(a)电路是电压负反馈，能稳定输出电压，即输出电压信号近似恒压源，内阻很小，计算反馈系数时，不起作用。

由图（c）可知，反馈电压等于输出电压在电阻上的分压。

即故图(a)电路的反馈系数由图（d）可知反馈电压等于输出电流的分流在电阻上的压降。

故图(b)电路的反馈系数【例5-2】在括号内填入“√”或“×”，表明下列说法是否正确。

（1）若从放大电路的输出回路有通路引回其输入回路，则说明电路引入了反馈。

（2）若放大电路的放大倍数为“＋”，则引入的反馈一定是正反馈，若放大电路的放大倍数为“−”，则引入的反馈一定是负反馈。

（3）直接耦合放大电路引入的反馈为直流反馈，阻容耦合放大电路引入的反馈为交流反馈。

（4）既然电压负反馈可以稳定输出电压，即负载上的电压，那么它也就稳定了负载电流。

（5）放大电路的净输入电压等于输入电压与反馈电压之差，说明电路引入了串联负反馈；净输入电流等于输入电流与反馈电流之差，说明电路引入了并联负反馈。

《运筹学》教学大纲

《运筹学》教学大纲一、课程基本信息1、课程英文名称：Operations Research2、课程类别：专业基础课程3、课程学时：总学时64，实验学时84、学分：45、先修课程：高等数学、线性代数、概率统计6、适用专业：信息管理与信息系统7、大纲执笔：管理工程教研室张吉军8、大纲审批：经济管理学院学术委员会9、制定(修订)时间：2006年12月二、课程目的与任务《运筹学》是信息管理与信息系统专业的专业基础课程之一，它涉及线性规划、整数规划、动态规划等基本内容。

本课程旨在使同学们正确、全面地掌握各级管理工作中已被广泛应用、发展比较成熟的最优化理论与方法，并能运用所学理论和方法解决管理工作中出现的各种优化问题，为后续课程奠定定量分析基础。

三、课程基本要求信息管理与信息系统专业的学生应系统地学习《运筹学》的全部内容。

系统掌握线性规划、运输问题、目标规划、整数规划、动态规划、图与网络分析的理论和方法；能借助电子计算手段，运用所学理论和方法解决实际问题。

通过该课程的学习，进一步培养学生的分析问题和解决问题的能力。

四、教学内容、要求、及学时分配（一）理论教学绪论（2学时）内容：第一节运筹学释义与发展简史1、运筹学名称的来历；2、运筹学的发展简史。

第二节运筹学研究的基本特征与基本方法1、运筹学研究的基本特征；2、运筹学研究的基本方法。

第三节运筹学主要分支简介1、线性规划；2、非线性规划；3、动态规划；4、图与网络分析；5、存贮论；6、排队论；7、对策论；8、决策分析；9、整数规划；10、多目标规划；11、其它。

第四节运筹学与管理科学1、运筹学的诞生既是管理科学发展的需要，又是管理科学研究深化的标志；2、运筹学在管理人才的培养中占有十分重要的地位；3、运筹学的研究应用已经给企业和国民经济各部门带来了巨大的财富。

基本要求：1、让学生了解运筹学名称的来历和发展历史；2、使学生正确理解运筹学研究的基于特征和基本方法；3、让学生了解运筹学的主要分支；4、让学生初步理解运筹学与管理科学的关系。

图与网络分析

end;
例 1 中 1 到 7 点的最短路是 1-2-5-7
查伴随矩阵 E 的第一行
1234567
10020255 19
hw
小结
• 最短路有广泛的应用 (P176案例) • 最短路的多种形式：无向图，有向图无循环圈，有向
图，混合图，无负边权，有负边权，有负回路，k-最短路等 • 当存在负权值边时，Floyd算法比Dijkstra算法效率高，且程序极简单。但Dijkstra算法灵活 • 若图是前向的，则Dijkstra算法也可以求两点间最长路 • 一般情况下，两点间最长路是 NP-complete，但最短路是 P算法 • 两点间k-最短路：分为边不相交的和边相交的求边不相交的k-最短路非常容易：先求最短路，将该最短路中的边从网路删去，再用Dijkstra算法可求次最短路，以此类推
hw
6.1.4 链，圈，路径，回路，连通图
• 走过图中所有边且每条边仅走一次的闭行走称为欧拉回路
定理 2：偶图一定存在欧拉回路(一笔画定理) 6.1.4 连通图，子图，成分
• 设有两个图 G1(V1, E1), G2(V2, E2), 若V2 V1, E2 E1，则 G2 是 G1 的子图
• 无向图中，若任意两点间至少存在一条路径，则称为连通图(connected graph)，否则为非连通图( disconnected graph)；非连通图中的每个连通子图称为成分 (component)
线表示实体间的关联
A
A D
C
C
D
B
B
2
hw
6.1 图与网络的基本概念
6.1.1图与网络 • 节点 (Vertex)
– 物理实体、事物、概念 – 一般用 vi 表示

运筹学6(图与网络分析)

定义7：子图、生成子图（支撑子图）
图G1={V1、E1}和图G2={V2，E2}如果 V1 V2和E1 E2 称G1是G2的一个子图。
若有 V1＝V2，E1 E2 则称 G1是G2的一个支撑子图（部分图）。
图8-2（a）是图 6-1的一个子图，图8-2 （b）是图 8-1的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。 e1
v2 ▲如果链中所有的顶点v0，v1，…，vk也不相
e1 e2 e4 v1 e3
v3 e5
同，这样的链称初等链（或路）。
e6
▲如果链中各边e1,e2…,ek互不相同称为简单链。
e7
e8
▲当v0与vk重合时称为回路（或圈），如果边不 v4
v5
重复称为简单回路，如果边不重复点也不重复
则称为初等回路。
图8－1中， μ1={v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v5}是一条链，μ1中因顶点v3重复出现，不能称作路。
e1
e2 e4 v1 e3
v2
v3
e5
e6
e7
e8
v4
v5
定理1 任何图中，顶点次数的总和等于边数的2倍。
v1
v3
v2
定理2 任何图中，次为奇数的顶点必为偶数个。
e1
e2 e4 v1 e3
v2
v3
e5
e6
e7
e8
v4
v5
定义4 有向图：如果图的每条边都有一个方向则称为有向图
定义5 混合图：如何图G中部分边有方向则称为混合图 ② ⑤ ④
定理4 有向连通图G是欧拉图，当且仅当G中每个顶点的出次等于入次。
② 15
9 10

运筹学-图论

v3
v5
v7
v1
v6
v2
v4
图 5.5
图的基本概念
一个图G或有向图D中的点数，记作P(G)或P(D)，简记作P；边数或者弧数，记作q(G)或者q(D)，简记作q 。如果边[vi ,vj]E ，那么称vi , vj 是边的端点，或者vi ,vj是相邻的。如果一个图G中，一条边的两个端点是相同的，那么称为这条边是环，如图5.4中的边[v3 ,v3]是环。
C
A
B
D
哥尼斯堡七橋問題可以看成是：对这样一个封闭的图形，是否可以
一笔画完成C 它并且回到原点
A
B
D
数学家欧拉(Euler, 1707-1783) 于1736年严格地证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式
即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。
• 各种通信网络的合理架设 • 交通网络的合理分布等
生活中的一些例子
台大网路架构图
例5.1 图5.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用
点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。
太原重庆
石家庄郑州
北京天津
vV2
图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列。如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,…,vn-1 , en ， vn ; v0 ，vn分别为链的起点和终点。记作（ v0 ,v1 , v2， ,v3 , …, vn-1 , vn ）简单链：链中所含的边均不相同；初等链：链中所含的点均不相同, 也称通路；

第五章正弦稳态电路的分析

正弦电流电路
激励和响应均为同频率的正弦量的线性电路（正弦稳态电路）称为正弦电路或交流电路。
研究正弦电路的意义
1.正弦稳态电路在电力系统和电子技术领域占有十分重要的地位。
优 ①正弦函数是周期函数，其加、减、求导、点积分运算后仍是同频率的正弦函数。
②正弦信号容易产生、传送和使用。
返回上页下页
j
F | F | e | F |
j
极坐标式
返回上页下页
几种表示法的关系：
Im
F a jb
F | F | e | F |
j
b |F|
F

O
| F | a b b 或 θ arctan( ) a
2 2
a
Re
a | F | cos b | F | sin
O

F Re
返回
上页
下页
特殊旋转因子
jF
Im
F
Re
jF
π jπ π π 2 , e cos( ) jsin( ) j 2 2 2
O
F
π j π π π 2 , e cos( ) jsin( ) j 2 2 2
π , e
w 2π f 2π T (3) 初相位
单位： rad/s ，弧度/秒
反映正弦量的计时起点，常用角度表示。
返回上页下页
注意同一个正弦量，计时起点不同，初相
位不同。
i
=0
一般规定：| |< 。
O
=/2
wt
=－/2
返回
上页

自动控制原理第五章

•表5-1 RC网络的幅频特性和相频特性数据

A( )
( )
0 1 0
1 0.707
45
2 0.45
5 0.196

0
63.4 78.69 90
图5-2 RC网络的幅频和相频特性
图5-3 RC网络频率特性的幅相曲线
对数频率特性图又称伯德图（Bode图），包括对数幅频特性和对数相频特性两条曲线，其中，幅频特性曲线可以表示一个线性系统或环节对不同频率正弦输入信号的稳态增益；而相频特性曲线则可以表示一个线性系统或环节对不同频率正弦输入信号的相位差。对数频率特性图通常绘制在半对数坐标纸上，也称单对数坐标纸。
图5-20控制系统结构图
将系统的开环频率特性函数按典型环节划分，可以分解为： ( j 1) ( ( j ) 2 ( j ) 1) k
m1 m2
G ( j ) H ( j )
k
2 l
2
l l
( j )
0
k 1 n1
( i s 1) ( 2 ( j ) 2 2 j j ( j ) 1) j
图5-19 Ⅱ型三阶系统幅相频率特性图
讨论更一般的情况，对于如图5-20所示的闭环控制系统结构图，其开环传递函数为 G( s) H ( s) ，可以把系统的开环频率特性写作如下的极坐标形式或直角坐标形式：
G( j)H ( j) G( j)H ( j) e j () P() jQ()
•图5-6积分环节频率特性的极坐标图
在伯德图上，积分环节的对数频率特性为
L( ) lg A( ) lg G( j ) lg ( ) 2
图5-7积分环节的伯德图

《运筹学教程》胡云权第五版第五章图与网络分析

最小支撑树问题
1、树
连通且无圈的无向图
判断下面图形哪个是树：
(A)
(B)
(C)
树的性质： 1、树中任两点中有且仅有一条链； 2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。
3、边数 = 顶点数 – 1。
最小支撑树问题
2、图的支撑树
若一个图 G =（V , E）的支撑子图 T=（V , E´）构成树，则称 T 为 G的支撑树，又称生成树、部分树。
v1
v3 7.5 v4
v5 v3
v4
最小支撑树问题
3、最小支撑树问题问题：求网络的支撑树，使其权和最小。 v 5
2
v1
3 4 2
3.5
v5
算法1（避圈法）：把边按权从小到大依次 5.5 添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。【例】求上例中的最小支撑树 5
第五章图论与网络分析
学习目标
图的基本概念
图论起源——哥尼斯堡七桥问题
A C B D C A D
B
问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？
结论：每个结点关联的边数均为偶数。
图的基本概念
哈密尔顿回路问题：环球旅行遊戏
13 2 12 15 11 16 10 3 9 4 17 7 8 14 1 20 19 18 6 5
6
v2
2
1
v5
2
v8
6
3
v1
1
3
2
v3 v4
6
4
10
3
v9 v7
4
10
v6

图与网络分析GraphTheoryandNetworkAnalysis

(一)、狄克斯屈拉(Dijkstra)算法适用于wij≥0，给出了从vs到任意一个点vj的最短路。
算法步骤： 1.给始点vs以P标号 P(vs ) 0 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号，T (v j ) ( j 2,3, , n) 。 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中
v2
A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,
v1
(v2 , v4 ),(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 )
, (v5 , v4 ) , (v5 , v6 ) }
v3
v4 v6
v5
图2
4、一条边的两个端点是相同的,那么称为这条边是环。
v2
v5
v2
v4
v3
v4
v3
一个图G 有生成树的充要条件是G 是连通图。
用破圈法求出下图的一个生成树。
v2
e1 v1
e4 e7 e3 v4 e8
e2
e5
e6
v2
v3
e1
e4 e7
v1
e3
v4 e8
v5
e2
e5
e6
v3
v5
v2
e4
v1 e2 v3
v4 e8
v5
e6
（一）破圈法
（二）避圈法
在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1， e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。
2. 简单链：没有重复边的链。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

有向图中两点之间有不同方向的两条边，不是多重边。
定义2：不含环和多重边的图是简单图，含有多重边的图称为多重图。下图哪些是简单图，哪些是多重图？
(a)
(b)
(c)
(d)
a,b为简单图，c,d为多重图。
定义3: 每一对顶点间都有边相连的无向简单图称为完全图。每一对顶点间有且仅有一条有向边的简单图称为有向完全图。
A
C
D
B
此难题于1736年被瑞士数学家欧拉解决，他在 “依据几何位置的解题方法”论文中证明这样的走法不存在。欧拉被公认为图论的创始人。
A
Cቤተ መጻሕፍቲ ባይዱ
D
B
A D
C
B
1857年，英国数学家Hamilton发明一种游戏，用一个实心正12面体象征地球，其20个顶点分别表示世界的20个城市，要求游戏者从某一城市出发寻找一条经由每个城市一次且仅经一次再回到原出发点的路。此问题有解。
v4
1 aij 0
边(vi , v j ) E 其他
v1
称矩阵A为图G的邻接矩阵。当G为
v2
v3
无向图时，邻接矩阵为对称矩阵。
右图的邻接阵为： 0 1 1 1 1
0 0 0 1 0 A 0 1 0 0 1
0 0 1 0 1 0 0 0 0 0
四、欧拉回路与中国邮路问题
定义13：连通图中，若存在一条回路，经过每边一次且仅一次，则称之为欧拉回路。具有欧拉回路的图称为欧拉图（E图）。定理3：无向连通图G是欧拉图，当且仅当G中无奇点。
定义7：图G=(V,E)，若E’是E的子集，V’是V的子集，且E’中的边仅与V’中的顶点相关联，则称G’=(V’,E’)是 G的一个子图。若V’=V, 则G’称为G的生成子图。
例，下图(b)为(a)的子图，(c)为(a)的生成子图。
v1
v1
v1
v2 v5
v4 v2 v5
v2 v5
v4
v3
v3
v3
(a)
5.1 图与网络基本知识
一、图与网络的基本概念
企业A 企业B
企业C
企业D
企业E
工人甲
乙丙丁戊
工作
A B C D
图：反映对象之间关系的一种工具。
定义1：一个图是由点集V={vi}和边集E={ek}（所有边的端点都属于V）所构成的二元组，记为G=(V,E)。vi 为顶点，ek为边，当V、E为有限集时G为有限图。
定理4：有向连通图G是欧拉图，当且仅当G的每个顶点的出次等于入次。
中国邮路问题：邮递员从邮局出发，走遍该地区所有街道再返回邮局，如何安排路线可以使所走总路程最短？
Euler回路：在图中找一条经过每边一次且仅一次的路且回到原点。 Hamilton回路：在图中找一条经过每个点一次其仅一次的路且回到原点。
图论第一本专著：《有限图与无限图的理论》，1936，匈牙利数学家。
图论迅速发展时期：20世纪中期，电子计算机的发展以及离散数学的发展，促使图论在管理科学、信息论、控制论等各领域广泛应用。
第五章图与网络分析
主要内容： 5.1 图与网络的基本知识 5.2 树 5.3 最短路问题 5.4 最大流问题
思考：哥尼斯堡七桥问题
哥尼斯堡（现名加里宁格勒）是欧洲一个城市，有一条河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次，最后回到原地呢？
定义8：无向图G中能够连接两点的点、边序列构成一定条SvS112,==义链v{{4vv9的。11：,,一ee没11无,,条vv有向33,,链重ee图77,,；复vvG55,,点ee中64,,或一vv34重,}条e为7复,链v初5边,的e等4的,始v链4链点}为为和连初终接等点链是v。同1 e一e12e点v3vv3时42ee5e，64e7 v5 称为圈。没有重复点或重复边的圈为初等圈。 S1={v1,e1,v3,e7,v5,e6,v3,e7,v5,e4,v4,e2,v1}为一个圈； S2={v1,e1,v3,e7,v5,e4,v4,e2,v1}为一个初等圈。
24 8
aij
0wij
边(vi , v j ) E 其他
9 v2
3 v3
称矩阵A为网络G的权矩阵。
右图的权矩阵为： 0 9 2 4 7
9 0 3 4 0 A 2 3 0 8 5
4 4 8 0 6 7 0 5 6 0
三、图的矩阵表示
v5 定义12：图G=(V,E)的顶点的数量
为n，构造矩阵A=(aij)n×n，其中
(b)
(c)
权：点或边相关的某些数量指标，可代表距离、费用、容量等。网络：点或边带有某种数量指标的图。
v3
5 23
v1
2 4 v256
v5
v4
(a)
v3
v1
5 2
2
3
4 v256
v5
v4
(b)
(a),(b)是常见网络例子，(a)网络图常见于最短路问题， (b)网络图常见于管道运输网络。
二、连通图
e1
右图中d(v1)=4 (e1计算两次)
d(v3)=4
e2
v2
v4
v1 e4
e3
e6
v3
e5
v5 定理1：任何图中，顶点次数的总和等于边数的2倍。定理2：任何图中，次为奇数的顶点必为偶数个。
定义6：有向图中以vi为始点的边数称为vi的出次，记为 d+(vi) ，以vi为终点的边数称为vi的入次，记为d-(vi) 。
有向图中边的方向相同时，链和圈分别称为道路和回路。定义10：一个图中任意两点间至少有一条链，称为连通图。任何非连通图都可以分为若干个连通子图(分图)。
三、图的矩阵表示
定义11：网络(赋权图)G=(V,E)上的
v5 6
边(vi,vj)有权wij，构造矩阵 A=(aij)n×n，其中
7
5
v4
4
v1
例：右图中
e1
V={v1,v2,v3,v4,v5}
v4
E={e1,e2,e3,e4,e5,e6} e1=(v1,v1),e2=(v1,v2),…
e2 v2
无向图：任意边都是无向边的图
v1 e4
e3
e6
v3
e5
有向图：任意边都是有向边的图
v5
环：边的两端点相同也称环，如e1;
多重边：两点间多于一条边，如e4,e5
定义4：图G的点集V可以分成两个非空子集X,Y,使得 E中每条边的两个端点必有一个属于X，另一个属于Y，则G称为二部图。
以下哪些是二部图？
(a)
(b)
a,b图都是二部图。
定义5：以点v为端点的边数叫做点v的次。记为
deg(v),简记d(v)。
次为奇数的点称为奇点，次为偶数的点称为偶
点。次为0的点称为孤立点。