关键路径.ppt

1
关键路径
问题:
假设以有向网表示一个施工流图,弧上的权值表示完成某活动所需时间。
问:哪些活动是“关键活动”?
即:哪些活动将影响整个工程的完成期限的?
a
b
c
d
e
f
g
h
k
6
4
5
2
1
1
8
7
2
4
4
6
1
7
4
活动
事件
漾爹泌鳖笔哨泣庞抓摔荣粱缩狱傈芋封臻网掣畦润东鲤填晚上掣鸟贺挺困关键路径关键路径
2
a
b
c
d
e
f
g
h
k
6
4
5
2
1
1
8
2
4
4
6
1
4
7
“关键活动”指的是:该弧上的权值增加将使有向图上的最长路径的长度增加。
整个工程完成的时间为:从有向图的源点到汇点的最长路径。
源点
汇点
7
喷莉辩膝质吗子醋盲关龚衡柔呼诵男驹饺嗽宣贬也狈壶袜瘁许淹娩郝闽舅关键路径关键路径
3
如何求关键活动?
“活动(弧)”的最早开始时间 e(i)
“活动(弧)”的最迟开始时间 l(i)
关键活动: e(i) = l(i)
“事件(顶点)”的最早发生时间 ve(j)
“事件(顶点)”的最迟发生时间 vl(k)
假设第 i 条弧为<j, k> 则对第 i 项活动言
e(i) = ve(j);
l(i) = vl(k) – dut(<j,k>);
j
k
i
a
b
c
e
6
4
1
1
6
1
扎檬光峪够圃抚拭览叠匡擞恬拯凰矛计酣皖衰喜掠杭谷蝉寨文博蝴湍析呻关键路径关键路径
4
事件(顶点)发生时间的计算公式
最早开始时间:
ve(源点) = 0;
ve(k) = Max{ve(j) + dut(<j, k>)}
最迟开始时间:
vl(汇点) = ve(汇点);
vl(j) = Min{vl(k) – dut(<j, k>)}
a
b
c
e
6
4
1
1
6
1
鲜疙凶蓉瑟赋堪蝗妊耘目均桨嘘尘霍胚挽采韧涣霓厄泰示胃追煌郴棉晤美关键路径关键路径
5
a
b
c
d
e
f
g
h
k
6
4
5
2
1
1
8
7
2
4
4
0
0
0
0
0
0
0
0
0
6
4
5
7
11
5
7
15
14
18
18
18
18
18
18
18
18
18