2. Пример. В таблице записаны работы ( I , j ) и время их выполнения tij ;

i , j	1, 2	1, 3	2, 3	2, 5	3, 4	3, 6	4, 5	4, 6	4, 7	5, 7	6,7
tij	2	8	5	4	7	23	12	4	5	10	8

Начертить сетевой график и найти параметры сетевого графика по событиям и работам.

РЕШЕНИЕ По данным работам i, j строим сетевой график. Событий всего 7, значит рисуем 7 вершин. Надо так расположить вершины, чтобы работы i , j не пересекались.

27

2 4 5 2

2 1 29 10

3

2 12 39

7 0

0 15 39

1 0 5 4 2 5

0 17 8

7 8

8 8

3 0 23 31

8 6 0

t _p 31

N R

t _n

Находим параметры по событиям.

1) Ранний срок наступления события I, tp ( I ).Это максимальный путь от начального события до I - го события:

t_p( 1 ) = 0; t_p( 2 ) = t_1,2 = 2

В третье событие входят 2 работы : (2,3) и (1,3), значит

t_p(3)=max{t_p(2) + t_2,3 ; t_p(1) + t_1,3}=max{2+5, 8}= 8

В четвертое событие входит одна работа (3,4)

t_p(4) = t_p(3)+t_3,4 = 8+7=15

В пятое событие входят 2 работы : (2,5) и (4,5), значит

t_p(5)=max{t_p(2) + t_2,5 ; t_p() + t_4,5}=max{2+4, 15+12}= 27

В шестое событие входят две работы : (4,6) и (3,6), значит

t_p(6)=max{t_p(4) + t_2,5 ; t_p(3) + t_3,6}=max{15+4, 8+23}= 31

В седьмое событие входят три работы : (5,7); (4,7); (6,8) значит

t_p(7)=max{t_p(5) + t_5,7 ; t_p(4) + t_4,7; t_p(6) + t_6,7}=

max{5+5, 27+10,31+8}= 39

2) Поздний срок наступления события i, t_n ( i ) — это разность между продолжительностью максимального пути l_max и пути наибольшей продолжительности от данного события i до конечного события.

Рассчитывается t_n ( i ) по обратной схеме t_p ( i ). Значит, расчет начинаем от конечного события, ориентируемся на выходящие работы, берем минимум разности.

Для конечного события

t_n(7) = t_p(7)=39

Из шестого события выходит одна работа : (6,7)

t_n(6) = t_n­­­­­­­_­(7) - t_6,7 = 39 - 8 = 31

Из пятого события выходит одна работа : (5,7)

t_n(5) = t_n­­­­­­­­(7) - t_5,7 = 39 - 10 = 29

Из четвертого события выходит 3 работы : (4,5); (4,6); (4,7)

t_n(4) = min{ t_n­­­­­­­_­(5) - t_4,5 ; t_n­­­­­­­_­(6) - t_4,6 ; t_n­­­­­­­_­(7) - t_4,7 }=

min{29 - 12; 31 - 4; 39 - 5}= 17

Из третьего события выходит 2 работы : (3,4);(3,6)

t_n(3)=min{t_n­­­­­­­_­(4) - t_3,4 ; t_n­­­­­­­_­(6) - t_3,6}=min{17 - 7;31 - 23}= 8

Из второго события выходит 2 работы : (2,5);(2,3)

t_n(2)=min{t_n­­­­­­­_­(5) - t_2,5 ; t_n­­­­­­­_­(3) - t_1,3}=min{8 - 5;29 - 4}= 3

Из начального события выходит 2 работы : (1,2);(1,3)

t_n(1)=min{t_n­­­­­­­_­(2) - t_1,2 ; t_n­­­­­­­_­(3) - t_1,3}=min{3 - 2;8 - 8}= 0

Для начального события должно выполняться условие:

t_p( 1 ) = t_n ( 1 ) = 0 .