Пусть проект описывается взвешенным графом, где дуги соответствуют операциям (этапам) проекта, а вес дуги. 2

Пусть проект описывается взвешенным графом, где дуги соответствуют операциям (этапам) проекта, а вес дуги обозначает время выполнения соответствующей операции Найти наименьшее время выполнения проекта, критические пути и резерв времени для выполнения операции v1→v4

Решение задачи разобьём на этапы.
Этап 1.
Найдем наибольшее время l(vj) начала операции, соответствующие дугам, исходящим из вершины vi , где i=1, 2,…, n, ji, по формуле
l(vi)= max(l(vi)+ t(vivj)
При этом считаем, что l(v1)= 0 – начальное условие алгоритма.
l(v4)= l(v1)+ t(v1v4)=0+6=6;
l(v2)= max(l(v1)+ t(v1v2); l(v4)+ t(v4v2))= max(0+4;6+3)=9;
l(v3)= l(v2)+ t(v2v3)=9+5=14;
l(v5)= max(l(v2)+ t(v2,v5); l(v4)+ t(v4v5))= max(9+4;6+2)=13;
l(v6)= max(l(v1)+ t(v1v6); l(v4)+ t(v4v6))= max(0+4;6+5)=11;
l(v7)= max(l(v6)+ t(v6v7); l(v5)+ t(v5v7))= max(11+1;13+1)=14;
l(v8)= max(l(v3)+ t(v3v8); l(v5)+ tv5v8; l(v7)+ t(v7v8))= max(14+4;13+2; 14+1)=18;
Результаты вычислений запишем во вторую строку таблицы 2.10

. По результатам вычислений пучили, что минимальное время выполнения проекта равно l(v8)=18
i
1 2 3 4 5 6 7 8
l(vi)
0 9 14 6 13 11 14 18
Этап 2. Теперь определим критические пути, т.е. наибольшие пути от начальной вершины графа к конечной. Как видно из 1 этапа такой путь:
v1→v4→v2→v3→v8
Этап 3. Найдем самое позднее время начала операций lvi, отвечающих дугам, исходящим из вершины vi, при котором весь проект все еще может быть выполнен за минимальное время. Для этого:
а) поменяем ориентацию каждой дуги, при этом поменяются местами начальная и конечная вершины, т.е. v8 станет начальной вершиной графа, а v1 – конечной;
б) найдем самый длинный путь l(vj) от вершины v8 до вершины v1, используя алгоритм 1 этапа:
l'(v8)= 0
l'(v7)= l(v8)+ t(v8v7)=0+1=1;
l'(v5)= max(l(v8)+ t(v8v5); l(v7)+ t(v7v5))= max(0+2;1+1)=2;
l'(v6)= l(v7)+ t(v7v6)=1+1=2;
l'(v3)= l(v8)+ t(v8v3)=0+4=4;
l'(v2)= max(l(v5)+ t(v5,v2); l(v3)+ t(v3v2))= max(2+4;4+5)=9;
l'(v4)= max(l(v6)+ t(v6v4); l(v5)+ tv5v4; l(v2)+ t(v2v4))= max(2+4;2+2; 9+3)=12;
l'(v1)= max(l(v6)+ t(v6v1); l(v4)+ tv4v1; l(v2)+ t(v2v1))= max(2+4;12+6; 9+4)=18;
Результаты вычислений заносим в третью строку таблицы
i
1 2 3 4 5 6 7 8
l(vi)
0 9 14 6 13 11 14 18
l'(vi)
18 9 4 12 2 2 1 0
в) вычислим самое позднее время начала операций по формуле
L(vj)= l(v8)- l'(vj)
Результаты вычислений записаны в последней строке таблицы
i
1 2 3 4 5 6 7 8
l(vi)
0 9 14 6 13 11 14 18
l'(vi)
18 9 4 12 2 2 1 0
L(vi)
0 9 14 6 16 16 17 18
Этап 4