Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 22

Алгоритм расчета раннего момента наступления событий.

шаг 1: принять для начальной вершины графа t_p(0)=0 и p=0, где p-шаг итерации;

шаг 2: определить на шаге итерации p ранний момент наступления события j по формуле: t_p(j)=(t_p(i)+t_j,i), где t_p(i)-события i с известным ранним моментом наступления; t_j,i-продолжительность работы (i,j) от события, имеющего t_p(i);

а) если к вершине j подходит одна дуга (i,j), то принять t_p(j)=(t_p(i)+t_j,i),

б) если к вершине j подходит несколько дуг {(i,j)}, то сравнить и найти максимальное значение раннего момента наступления события j по формуле: t_p(j)=max_i{t_p(i)+t_i,j}.

шаг 3: если p=(n-1), то конец, иначе принять p=(p+1) и перейти к шагу 2 алгоритма.

Результаты вычислений представлены таблицей.

Алгоритм расчета позднего момента наступления события.

шаг 1: принять для конечной вершины графа t_n(k)=t_p(k) и р=0, где р-шаг итерации;

шаг 2: определить на шаге итерации р поздний момент наступления события j по формуле: t_n(j)=(t_n(i)-t_j,i), где t_n(i)-событие i с известным поздним моментом наступления; t_j,i-продолжительность работы (i,j) от события, имеющего t_n(i);

а) если от вершины j отходит одна дуга (i,j),то принять t_n(j)=(t_n(i)-t_j,i);

б) если от вершины j отходит несколько дуг (i,j), то сравнить и найти минимальное значение позднего момента наступления события j по формуле: t_n(j)=min_i{(t_n(i)-t_j,i)};

шаг 3: если р=(n-1), то конец, иначе принять р=(р+1) и перейти к шагу 2 алгоритма.

Результаты вычисления представлены  таблицей.

Алгоритм расчета резерва времени события.

шаг 1: принять р=0, где р-шаг итерации;

шаг 2: определить на шаге итерации р индекс события i и резерв его ожидания по формуле: t₀(i)=(t_n(i)-t_p(i));

шаг 3: если р=(n-1), то конец, иначе принять р=(р+1) и перейти к шагу 2.

Результаты вычислений представлены таблицей.