《运筹学》第六章 网络计划方法

图2
14
图3
5)网络图中不能有缺口和回路 在网络图中，除始点和终点外，其它各个结点的前后都
应有弧相连接，即图中不能有缺口，使网络图从始点经 任何路线都可到达终点。否则，将使某些工序失去与其 紧后（或紧前）工序应有的联系。
在本章讨论的网络图中不能有回路，即不能有循环现 象。否则将使组成回路的子工程永远不能完工。在如下 网络图4中出现的情况是错误的。
EFTj= ESTj+ tj
一项工作的结束时间应等于其开始时间加
12
1) 方向、时序与结点编号
网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列。 网络图中的各个结点都有一个时间(某一个或若干个工序开始或结 束的时间),一般按各个结点的时间顺序编号。为了便于修改编号及 调整计划,可以在编号过程中留出一些编号
2)紧前工序与紧后工序
例如,在图1中,只有在a 工序结束以后,b、c、d、e工序才能开始。a 工序是b、c、d、e 等工序的紧前工序,而b、c、d、e等工序则是工 序a 的紧后工序
这种计划借助于网络表示各项工作与所需要的时间，以 及各项工作的相互关系。通过网络分析研究工程费用与 工期的相互关系。并找出在编制计划时及计划执行过程 中的关键路线。这种方法称为关键路线法（Critical Path Method）简称CPM。
• 工程计划与甘特图
不易表现工程全貌 不便于对各项工作的安排进行筹划和推敲 不能识别影响进度的关键工作 不能反映一项工作不能按进度完成时对工程进度的影
99-7-5
2 拟拟拟拟拟拟拟拟拟拟拟拟拟
99-7-12
3 拟拟拟拟
99-7-13
99-7-22
4 拟拟拟拟拟拟拟
99-7-23

A
拆迁
/
2
B
工程设计
/
3
C
土建工程设计
B
2.5
D
采购设备
B
6
E
厂房土建
C、A
20
F
设备安装
D、E
4
G
设备调试
F
2
A（2）
1
B (3)
2
C (2.5)
3
D (6)
E (20)
G (2)
F (4)
4
5
6
用箭秆删除法标号（保证箭尾号大于箭头号)
工序
A
B
C
D
EFGHIJKL
M
N
紧前工序
_
_
_
_
D
E
A
F
G
B
由本例可见：关键工序 头尾皆有
=
关键工序时间之和=工期T。
，但反之未必。
二、工程完工期的概率分析
（计划评审技术PERT）
1、PERT与 CPM的区别：
CPM工序时间是确定的
工程工期的概率分析是是时间不确定情况下PERT
的主要工作
确定平均工序时间的三点估计法：
设工序最乐观时间为aij，最悲观时间为bij，最可能时间为m ij ,
t ij
a ij 4m ij bij
- 给任意点 i 标 Li ,
Li=Min{以 i 为箭尾的各箭之 “箭头
- 箭长tij”}
16
（3）求关键路（用标号法）
6
2
8
0
0 1
3
B '(0)
3
2）计算各工序 i

4
H,4
22
第二节 绘制网络图
三、网络图的绘制举例
【例】
工序 紧前工序 工序时间
A G、M
3 ②
B H
4
C
— 7
D L
3
E，5
M，3
E C
5
F A、E
5
G B、C
2
H
— 5 ⑦
I A、L
2
F，5
K F、I
1
L B、C
7
M C
3
C，7
⑩
I，2
K，1 11
①
H，5
⑤
G，2
A，3
⑥
⑨
D，3
③
23
B，4
④
7
I
8
C
H
21
OM:SM
第二节 绘制网络图
三、网络图的绘制举例 【例】
工 序 A — 2 B A 4 C B 4
2 A，2
D — 4.7
B,4
E — 7.2
5 G,6.2
F E 2
G D、 F 6.2
H D、 F 4
I H 4.3
紧前工序 工序时间
C,4
7 I,4.3 6
OM:SM
1
D，4.7 E,7.2 F,2 3
13
OM:SM
第二节 绘制网络图
一、网络图中工序间的表达方式
1、当工序a完工后b和c可以开工
○
2、当工序a和b完工后c才能开工
○
a
b
○
○
a
○
c
c
○
○ ○
b
3、工序c在工序a完工后就可以开工， 但工序d必须在a和b都完工后才能开工

关键路径分析
什么是关键路径?
是需要在规定时限内完成的，不 能被延误的最长任务序列。
为什么重要?
因为这条路径上的任何延误都会 导致整个项目的延误。
如何确定?
通过计算出每个任务的最早开始 时间和最晚结束时间，从而找出 关键路径。
项目进度管理
1
制订进度计划
确定任务的完成时间，为项目进度的管
进度监控
2
理提供基础。
风险管理的好处?
有助于降低项目失败风险，增强 规划的稳健性，避免额外成本损 失和延迟。
关键路径法和PERT/CPM方法的比较
相似点
都是用来解决项目延误问题、进行进度计划、任务分析等。
不同点-PERT/CPM
适合单一的大规模计划，对时间的估计更加准确，适合波动较大的工作。
不同点-关键路径法
更适合复杂的工作计划，可以快速有效地过滤重要的任务，以使项目进度良好地推进。
运筹学网络计划方法
运筹学网络计划是一个强大的项目管理工具，能够帮助团队更好地理解项目， 并更好地规划工作。
定义
1 网络计划
是指通过图形化的方式，展现了项目中各项 任务的工作量、执行时间以及任务间的依赖 关系。
2 网络计划方法
是利用网络图形的结构，为项目管理提供项 目的计划、实施、控制和组织，以确保项目 的顺利开展。
网络计划在实际项目中的应用
1
建筑
对建筑贸易来说，它是一种标准的工具，用于确定工作任务，减少延误、提早完 成。
2
IT 项目
在软件和硬件开发过程中，它被广泛使用，以便跟踪任务、减少重叠和缺陷，并 计划偏差管理方法。
3
制造业
网络计划可帮助管理、确定生产期、调度工作、支持制造商的计划和进度控制。

工序(i,j)的总时差=(j)最迟开始时间-t(i,j) -(i)最早开始时间
工序(i,j)的自由时差=(j）最早开始时间- (i）最早完成时间
所有时间参数
例3（P136）某项课题研究工作分解的作业表如下。根据此表绘制此项科研工作的网络图，计算时间参数，并确定关键路线。
工序代号
工序
紧前工序
工序时间
（3）按照工作的新工时，重新计算网络计划的关键 路线及关键工序。
（4）再比较关键工序的直接费用率与间接费用率。
不断重复，直到使总费用上升为止。 （直接费用率>间接费用率）
注：若压缩引起出现多于一条新的关键路线时，需同时压缩各关键路线.
（因为不同时压，则工期不能缩短， 工期=关键工序上工时之和）
表示相邻工序时间分界点，称为事 项，
用 表示
（3）相邻弧：
表示工序的前后衔接关系，称为紧前 （或紧后）关系。
如
A
B
A是B的紧前工序，B是A的紧后工序。
A
（4）虚工序（虚箭线）
为表示工序前后衔接关系的需要而增加的。
6.1 网络计划图的绘制 6.2 时间参数计算与关键路线确定 6.3 网络图的调整及优化
CLICK HERE TO ADD A TITLE
1.问题的一般提法：
设有一项工程，可分为若干道工序，已知各工序间 的先后关系以及各工序所需时间t。
问：
（1）工程完工期T？
（2）工程的关键工序有哪些？
若再各压缩1天
则应压缩B、C（同时压）
此时的直接费用率将是3+4=7>5
故最低成本工期为10天。
注：
（1）有时资料未给可压缩时间，但给了正常工作时间及最短工作时间。则压缩时间=正常工作时间-最短工作时间。

第7章网络计划方法PERT：计划评审方法CPM：关键路线法用于大型项目的进度管理。

第1节PERT网络图一、PERT网络图的基本概念PERT网络图由节点和弧构成，与上一章所讲的网络图的概念一致。

作业：需消耗一定时间的一项活动，也称工序。

作业对应于网络中的弧，弧也称箭线。

事件：标志作业的开始或结束，本身不消耗时间。

事件对应于网络中的节点。

如：通过某一节点前后相邻的两个作业相互称为紧前作业和紧后作业。

每项作业都有一个起点事件（箭尾事件）和一个终点事件（箭头事件）。

一个事件可作为多项作业的终点事件并可同时作为另外多项作业的起点事件。

若一项作业的起点事件为i，终点事件为j，则将该项作业标记为(i, j )。

如“概念设计”作业可标记为(1, 2)。

整个PERT网络图开始的事件称为最初事件，整个PERT网络图结束的事件称为最终事件。

如下图中的1和6。

路线：网络图中从最初事件到最终事件的一条路。

在PERT网络图中每项作业都具有一定的持续时间，称为计划时间。

路线的长度：路中各项作业的计划时间之和。

网络中通常存在多条不同的路线。

关键路线：所有路线中计划时间之和最长的那条路。

如上图中1—3—5—6即为关键路路线，其时间长度为11小时。

二、建立PERT 网络图的准则1. 一项作业用一条箭线表示；每项作业的终点事件编号应大于起点事件编号。

2. 两个事件之间只能有一条箭线，若存在两项或更多项作业，则需引入虚作业进行表示，如下图。

3. 作业之间的几种典型关系在网络图中的表示：4. PERT 网络图有唯一的最初事件和唯一的最终事件。

5. PERT 网络图中不允许出现回路。

6. PERT 网络图的绘制应进行适当的布局：尽量避免箭线之间出现交叉；使各条箭线尽量按从左到右的方向展开。

7. 在实际应用中，对大型项目，可绘制多个层次的网络图。

高层次网络图中的一项或几项作业，可展开绘制成一张低层次的网络图。

三、PERT网络图的绘制例1(1)某项工程由11项作业组成，各项作业之间的先后展开关系如下：解：绘制网络图的步骤：(1) 由最初节点画出所有无紧前作业的作业；(2) 逐条绘制紧前作业已全部画出的作业：将全部紧前作业指向同一个终点事件，再从该终点事件画出当前作业。

5、制造某机床需要A、B、C三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果制造100台机车，问最少要用多少根圆钢？试建立该问题的线性规划模型，并写出其对偶规划。
轴件
规格：长度（米）
每台机床所需轴件数量
A
B
C
2.9
2.1
1.5
1
1
1
6、试用单纯形法求解下列线性规划问题
2、某工厂生产A、B、C三种产品，现根据订货合同以及生产状况制定生产计划。
已知甲合同为：A产品1000件，单价600元，违约金为120元/件；
B产品700件，单价500元，违约金为100元/件。
乙合同为：B产品900件，单价550元，违约金为110元/件；
C产品800件，单价450元，违约金为90元/件。
有关各产品生产过程所需工时以及原材料的情况见下表。试以利润最大为目标，建立该工厂的生产计划线性规划模型（不求解）。
（1）应如何指派，使总的翻译效率最高？
（2）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？
第五章图与网络分析
一复习思考题
1．通常用G(V，E)来表示一个图，试述符号V，E及这个表达式的涵义。
2．解释下列各组名词，并说明相互间的联系和区别：(a)端点，相邻，关联边；(b)环，多重边，简单图；(c)链，初等链；(d)圈，初等圈，简单圈；(e)回路，初等路；(f)节点的次，悬挂点，孤立点；(g)连通图，支撑子图；(h)有向图，赋权图。
2、用分技定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数是该问题目标函数值的下界；
3、用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝；

《运筹学》重要知识点解析和例题分析第六部分一．图的基本概念 定义一个图G 是指一个二元组(V(G),E(G)).即图是由点及点之间的联线所组成。

其中: 1）图中的点称为图的顶点(vertex).记为：v2）图中的连线称为图的边(edge).记为：,i j e v v ⎡⎤=⎣⎦.,i j v v 是边 e 的端点。

3）图中带箭头的连线称为图的弧(arc).记为：(),i j a v v =.,i j v v 是弧 a 的端点。

—— 要研究某些对象间的二元关系时.就可以借助于图进行研究 分类▪ 无向图：点集V 和边集E 构成的图称为无向图(undirected graph).记为： G(V.E)—— 若这种二元关系是对称的.则可以用无向图进行研究▪ 有向图：点集V 和弧集A 构成的图称为有向图(directed graph) .记为：D(V.A)—— 若这种二元关系是非对称的.则可以用有向图进行研究▪ 有限图: 若一个图的顶点集和边集都是有限集.则称为有限图.只有一个顶点的图称为平凡图.其他的所有图都称为非平凡图.图的特点：1 图反映对象之间关系的一种工具.与几何图形不同。

2 图中任何两条边只可能在顶点交叉.在别的地方是立体交叉.不是图的顶点。

3 图的连线不用按比例画.线段不代表真正的长度.点和线的位置有任意性。

4 图的表示不唯一。

如：以下两个图都可以描述“七桥问题”。

点(vertex)的概念1 端点：若e =[u.v] ∈E.则称u.v 是 e 的端点。

2 点的次：以点 v 为端点的边的个数称为点 v 的次.记为：()d v 。

在无向图G 中.与顶点v 关联的边的数目(环算两次),称为顶点v 的度或次数.记为()d v 或 dG(v).在有向图中.从顶点v 引出的边的数目称为顶点v 的出度.记为d+(v).从顶点v 引入的边的数目称为v 的入度.记为d -(v). 称()d v = d+(v)+d -(v)为顶点v 的度或次数． 3 奇点：次为奇数的点。

自由时差或单时差FF：
◦ 单代号：FFi＝min{ESj}－EFi ◦ 双代号：FFij＝min{ESjk}－EFij
48
工作A的TF
工作 A
工作A紧后工作B 工作A的TF
工作A的FF 工作A紧后工作C
总时差为零的工作单时差一定为零，总时差不为零 自由时差也可能是零
49


图上作业法 ◦ 单代号 ◦ 双代号 ◦ 绘制时标网络进度求 时间参数 表上作业法 i
37
工序名 称
紧前工 作
工作时 间
工序名 称
紧前工 作
工作时 间
工序名 称
紧前工 作
工作时 间
A
B C D
－
A A A
60
14 20 30
G
H I J
BC
EF F
7
12 60
M
N O P
JK
IL N M
5
15 2 7
DG 10
E
F
A
A
21
10
K
L
H
JK
25
10
Q
OP
5
38
B A
G M
C
J
P
D E L O H I K N Q
21
A
B Finish
Start
C
D
E
22

优点：
◦ 工序之间关系明确 ◦ 易于绘制 ◦ 国外常用软件采用

缺点：
◦ 无法带时标 ◦ 不够直观，所以国内工程师习惯双代号
23

基本概念：
◦ 以结点表示事件，即一项活动的开始或结束 ◦ 以箭线表示一项活动 ◦ 箭首和箭尾事件：一项工作的开始通常称为箭尾事件； 一项工作的结束通常称为箭首事件。

两个约束条件
(1/3)x1+(1/3)x2=1
及非负条件x1,x2 0所代表的公共部分
－－图中阴影区, 就是满足所有约束条件和非负
条件的点的集合, 即可行域。在这个区域中的每
一个点都对应着一个可行的生产方案。
22
5–
最优点
4–
l1 3B E
2D
（1/3）x1+(4/3)x2=3
l2 1–
0 1〡 2〡 3A 4〡 5〡 6〡 7〡 8〡 9〡C
运筹学 Operational Research
运筹帷幄，决胜千里
史记《张良传》
1
目录
绪论 第一章 线性规划 第二章 运输问题 第三章 整数规划 第四章 动态规划 第五章 目标规划 第六章 图与网络分析
2
运筹学的分支 数学规划: 线性规划、非线性规划、整数规划、 动态规划、目标规划、多目标规划 图论与网络理论 随机服务理论: 排队论 存储理论 决策理论 对策论 系统仿真: 随机模拟技术、系统动力学 可靠性理论
32
西北角
(一)西北角法
销地
产地
B1
0.3
A1
300
0.1 A2
0.7 A3
销量 300
B2
1.1
400
0.9
200
0.4
600
B3
0.3
0.2
200
1.0
300 500
B4
产量
1.0
700 ②
0.8
400 ④
0.5
600
900 ⑥
600
2000
①
③
⑤
⑥
34
Z
cij xij 0.3 300 1.1 400 0.9 200

2 1 3 1 3 正确的画法
不正确的画法
可引入虚作业。
虚作业
虚作业是为了表达相邻作业之间的逻辑关系而虚设的作业。 它不消耗时间、费用和资源，一般用虚箭线表示。 虚作业的引进原因(1) 两个事件之间的工作过程只能代表一项作业，当两个或两 个以上的作业具有同一个始点和终点时，需要引入虚作业，予 以区别。
分解任务的原则
工作的性质不同或由不同单位执行的工作应分开； 如产品设计与工装设计，铸造、锻、机械加工、装配要分开

同一单位进行的工作，时间先后不衔接的要分开； 如技术设计与工作图设计，材料采购与外协件采购要分开
占用时间不消耗资源，但影响工程完工日期的工作应作为分任务；
如油漆后的干燥，热处理后的冷却，方案的审批等
网络图中只能有一个始点和一个终点，使得自网络图的始点 经由任何路径都可以到达终点。

编号的规定
编号应从始事件开始，按照时序依次从小到大对事件编号，直到终 事件。 编号时不允许箭头编号小于箭尾编号。 事件的编号原则 箭尾事件(i)小于箭头事件(j)；一般采用非连续编号，即可空留 出几个号，跳着编，将来有变化时，不致打乱全局。
分解任务的要求
编制计划要熟悉业务，了解工程项目的各个组成部分，深入调查。
例：下表是某一工程的作业明细表
任务经过分解以后，可以列出作业明细表。
某一工程的作业时细表 作业 紧接的前项作业 作业时间(周) A 2 无 B 3 无 C A，B 4 D B 1 E A 5 F C 3 G E，F 2 H D，F 7 I G，H 6 J I 5
答案
作业名称 A 紧前作业 无
B 无
C 无
D A
E B
F B、C
A
1

资源分级
02
03
资源租赁与购买
Hale Waihona Puke 根据资源的重要性和稀缺性，对 资源进行分级管理，优先满足关 键资源的供给。
在项目资源不足时，考虑租赁或 购买外部资源，以满足项目需求。
调整关键路径
压缩关键路径
通过优化关键路径上的工作，缩短项目总工 期。
增加人力与物力
在关键路径上增加资源投入，提高工作效率。
任务并行化
通过合理安排任务顺序，使非关键路径上的 工作与关键路径上的工作并行进行。
THANKS FOR WATCHING
感谢您的观看
确定活动之间的逻辑关系
根据确定的活动先后关系，确定各个活动之间的逻辑关系，如并行关系、串行关系等。
确定活动的持续时间
根据历史数据、经验或实际情况，为每个活动分配合理的持续时间。
绘制网络图
使用合适的绘图工具
选择合适的绘图工具，如Visio、 Draw.io等，用于绘制网络图。
绘制网络图
根据确定的活动和关系，绘制出项目 的网络图，清晰地展示各个活动之间 的关系和顺序。
优化项目进度
进度计划优化
根据项目目标和资源状况，制定合理的进度计划，确 保项目按时完成。
进度控制
通过监控项目进度，及时发现偏差并采取措施进行调 整，确保项目按计划进行。
风险管理
识别项目中的潜在风险，制定应对措施，降低进度延 误的风险。
05 网络计划的评价与控制
评价网络计划的可行性
资源可行性
评估项目所需资源是否充足，是否符合 实际资源条件，避免资源浪费和短缺。
成本控制
制定项目成本预算，监控项目成本，及时发现和解决成本超支问题，确保项目成本控制 在预算范围内。

定义（虚工作）延续时间为零的假定 工作，称为虚工作。用虚箭线表示。 定义（紧前工作）紧接在该工作前面 的工作，称为该工作的紧前工作。 定义（紧后工作）紧接在该工作后面 的工作，称为该工作的紧后工作。
定义（结点）紧前工作与紧后工作 的交接点称为结点（节点、事项）。 结点功能——衔接前后工作和控制 工作进程。 结点特征——瞬时性。结点实现不
8
4
第二步：令最快进度为指令工期D=16天。 求出正常时间，计算工期T=23天。
16 5 5 0 1 2 2 2 5 7 7 3 2 4 4 5
11
4 7
18
6 5
23 7
8
4
第二步：令最快进度为指令工期D=16天。 求出正常时间，计算工期T=23天。
16 5 5 0 1 -7 2 2 2 -5 5 7 7 0 3 2 4 4 11 5
F
40 I 50
10
B 2 A 1 H 30 5 50 30 40 4 3 E
C 50
6
D 30 7 G 40 8 J 50 K 30 9
F
40 I 50
10
关键线路：1-2-3-4-7-8-9-10
关键线路长度=280
B 2 A 1 H 30 5 50 50 30 40 4 3 E C 50 6 D 30 7 40 I 40 8 G J 50 K 30 9
特点： PERT属于非肯定型，工作 时间采用“三个估计值”（最乐 观时间、最可能时间、最悲观时 间）适用于科研项目和一次性计 划，它着重考虑时间因素，主要 用于控制进度。
特点： CPM属于肯定型，工作时间采 用“一个估计值”（最可能时 间），它适用于工程建设项目， 它往往兼顾时间和费用两大因素， 力求用最低费用去确定工期，在 时间和费用两个方面作出决择。

《运筹学》重要知识点解析和例题分析第六部分一．图的基本概念 定义一个图G 是指一个二元组(V(G),E(G)).即图是由点及点之间的联线所组成。

其中: 1）图中的点称为图的顶点(vertex).记为：v2）图中的连线称为图的边(edge).记为：,i j e v v ⎡⎤=⎣⎦.,i j v v 是边 e 的端点。

3）图中带箭头的连线称为图的弧(arc).记为：(),i j a v v =.,i j v v 是弧 a 的端点。

—— 要研究某些对象间的二元关系时.就可以借助于图进行研究 分类▪ 无向图：点集V 和边集E 构成的图称为无向图(undirected graph).记为： G(V.E)—— 若这种二元关系是对称的.则可以用无向图进行研究▪ 有向图：点集V 和弧集A 构成的图称为有向图(directed graph) .记为：D(V.A)—— 若这种二元关系是非对称的.则可以用有向图进行研究▪ 有限图: 若一个图的顶点集和边集都是有限集.则称为有限图.只有一个顶点的图称为平凡图.其他的所有图都称为非平凡图.图的特点：1 图反映对象之间关系的一种工具.与几何图形不同。

2 图中任何两条边只可能在顶点交叉.在别的地方是立体交叉.不是图的顶点。

3 图的连线不用按比例画.线段不代表真正的长度.点和线的位置有任意性。

4 图的表示不唯一。

如：以下两个图都可以描述“七桥问题”。

点(vertex)的概念1 端点：若e =[u.v] ∈E.则称u.v 是 e 的端点。

2 点的次：以点 v 为端点的边的个数称为点 v 的次.记为：()d v 。

在无向图G 中.与顶点v 关联的边的数目(环算两次),称为顶点v 的度或次数.记为()d v 或 dG(v).在有向图中.从顶点v 引出的边的数目称为顶点v 的出度.记为d+(v).从顶点v 引入的边的数目称为v 的入度.记为d -(v). 称()d v = d+(v)+d -(v)为顶点v 的度或次数． 3 奇点：次为奇数的点。

紧后活动
B,C D
E,F G,I G,I
H6 8 8 5 3 6 3 5 8 3
3
D
8
B4
A
C
E
G
J
L
13 2
6
48
63
85
93
10
F
5
I3
K 8
H
56
7
四、PERT图的分类
（1）按工时估计的性质： A：确定型网络，每个工作的预计工时只估一个值， 即，这些工作的实际完成情况一般地可按预计工时达 到，也即实现的概率等于或近似等于1。 B：概率型网络，每个工作按三种情况下给定工时，最 快可能完成工时，最可能完成工时，最慢可能完成工 时。
23
5
2
8 25
26
2。作业时间参数：方括号－最早开工时间 tES ，三角 －最晚开工时间 tlS
4 00
0
01
2
46
4
3
4 15
3
1010
8
4
2 18
18
10 0 13
5
3
20
6
2 23
29
20 0
23 23
78
24 23 2
32
9
31 31 1
5
25
26
10 32
8
3。总时差，自由时差：中括号－总时差，园括号－ 自由时差
60年代耗时11年阿波罗登月计划3000亿$,42万人,2 万家公司,120所大学,600台计算机,700万零件,终于在 1969年7月，阿波罗11号船长阿姆斯特朗登上月球。
60-70年代我国开始应用和推广。 钱学森、华罗庚等都曾为此做 了大量工作。

项目四图与网络分析任务八图与网络的应用练习1、求下图的最小支撑树。

用破圈法求该图的最小支撑树：（1）（2）（3）（4）2、分别用破圈法和避圈法求下列各个图的最小支撑树。

a-1：用破圈法求图a的最小支撑树：a-2：用避圈法求图a的最小支撑树：b-1：用破圈法求图b 的最小支撑树：b-2：用避圈法求图b 的最小支撑树：3、用标号法求下图中1v 至7v 的最短路。

1）标号过程（1）初始化；令起点v 1的标号为P ，记做P(1) =0；令其余各点的标号为T ，记做T(i)=∞；（2）计算T标号：刚得到P标号的点为v1，考虑所有与v1相邻的T标号点v 2、v3、v5，修改v2、v3、v5的T标号为：T(2)=min[T(2)，P(1)+d12]=min[+∞，0+4]=4T(3)=min[T(3)，P(1)+d13]=min[+∞，0+3]=3T(5)=min[T(5)，P(1)+d15]=min[+∞，0+5]=5 （3）确定P标号：在所有的T标号点中，找出标号值最小的点标上P标号。

T(2)= 4 T(3) =3 T(4) =+∞T(5)=5 T(6)= +∞ T(7)= +∞令P(3)=3。

（4）计算T标号：刚得到P标号的点为v3，考虑所有与v3相邻的T标号点v 6，修改v6的T标号为：T(6)=min[T(6)，P(3)+d36]=min[+∞，3+2]=5 （5）确定P标号：在所有的T标号点中，找出标号值最小的点标上P标号。

T(2)= 4 T(4) =+∞ T(5)=5 T(6)= 5 T(7)= +∞令P(2)=4。

（6）计算T标号：刚得到P标号的点为v2，考虑所有与v2相邻的T标号点v 5，修改v5的T标号为：T(5)=min[T(5)，P(2)+d25]=min[5，4+1]=5（7）确定P标号：在所有的T标号点中，找出标号值最小的点标上P标号。

T(4) =+∞ T(5)=5 T(6)= 5 T(7)= +∞令P(5)=5。