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

Расчет t p o и t p ведется от начала сетевого графика к концу, а расчет t n и t n о - от конца к началу. При этом для конечного события t p = t n.

При расчете временных параметров сетевых графиков с детерминированным временем выполнения операций не учитываются случайные изменения продолжительности операций, которые могут оказывать существенное ялияния на срок завершения всего комплекса операций.

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

1) ранний срок наступления события j

æ t i p + t i j, если к событию j подходит одна

t j p = í операция

è max {t i p + t i j}, если к событию j подходит

{i} несколько операций;

 

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

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

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

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

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

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, tn (i) — это разность между продолжительностью максимального пути lmax и пути наибольшей продолжительности от данного события i до конечного события.

2) поздний срок наступления события j

æ t j п - t i j если от события j отходит одна

t i п = í операция;

è min {t j п - t i j}, если от события j отходит

{j} несколько операций

 

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

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

t_n(7) = t_p(7)=39

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

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

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

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

t_n(2)=min{t_n­­­­­­­_­(5) - t_2,5 ; t_n­­­­­­­_­(3) - t_1,3}=min{8 - 5;29 - 4}= 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.

3) Находим резерв времени по событиям:

R(i) = t_n(i) - t_p(i).

R(1) = 0;

R(2) = 3-2 =1;

R(3) = 8-8 = 0;

R(4) = 17-15 = 2;

R(5) = 29-27 = 2;

R(6) = 31-31 = 0;

R(7) = 39-39 = 0.

 

Критический путь сетевого графика Lкр - это последовательность операций, продолжительность которых составляет максимальное время выполнения всего комплекса операций. Продолжительность критического пути называют критическим временем Tkp. Критический путь Lkp определяется как последовательностью операций с наименьшим полным резервом.

4) Критический путь проходит по событиям с нулевым резервом времени R(i) = 0, т.е. 1, 3, 6, 7, (выделено на графе). Длина критического пути Lкр — это самый длинный путь от начального события до конечного:

L_кр = t_p(7) = 39.

Рассчитаем необходимые параметры по работам.

 

5) Ранний срок окончания работы (i, j):

ранний срок окончания операции (i, j)

t_p.o(i, j)=t_p(i) + t_i,j

t_p.o(1,2)=t_p(1) + t_1,2 = 0+2 = 2;

t_p.o(1,3)=t_p(1) + t_1,3 = 0+8 = 8;

t_p.o(2,3)=t_p(2) + t_2,3 = 2+5 = 7;

t_p.o(2,5)=t_p(2) + t_2,5 = 2+4 = 6;

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

t_p.o(3,6)=t_p(3) + t_3,6 = 8+23 = 31;

t_p.o(4,5)=t_p(4) + t_4,5 = 15+12 = 27;

t_p.o(4,6)=t_p(4) + t_4,6 = 15+4 = 19;

t_p.o(4,7)=t_p(4) + t_4,7 = 15+5 = 20;

t_p.o(5,7)=t_p(5) + t_5,7 = 27+10 = 37;

t_p.o(6,7)=t_p(6) + t_6,7 = 31+8 = 39;

 

6) Поздний срок наступления окончания работы (i, j):

t _{n о} (i, j)= t _n (j)

t_n.o (1,2) = t_n(2) = 3; t_n.o (2,3) = t_n(3) = 8;

t_n.o (1,3) = t_n(3) = 8; t_n.o (2,5) = t_n(5) = 29;

t_n.o (3,4) = t_n(4) = 17; t_n.o (4,5) = t_n(5) = 29;

t_n.o (3,6) = t_n(6) = 31; t_n.o (4,6) = t_n(6) = 31;

t_n.o (5,7) = t_n(7) = 39; t_n.o (4,7) = t_n(7) = 39.

t_n.o (6,7) = t_n(7) = 39;

7) Полный резерв времени работы i, j — это время, на которое можно увеличить продолжительность данной работы, не изменяя при этом продолжительность критического пути Lкр.

полный резерв времени операции (i, j)

R n = Tn - Tp - t i j;

где R n - максимальное время, на которое можно отсрочить или увеличить продолжительность работы (i, j), не изменяя директивного или раннего срока наступления завершающего события; R п принимают минимальные значения для операций, лежащих на критическом пути; эти минимальные значения равны нулю, если директивный срок наступления завершающего события не задан или превышает начало выполнения операций на время, равное продолжительности критического пути.

R_n(i, j) = t_n (j) - t_p(i) - - t_i,j;

R_n(1,2) = t_n (2) - t_p(1) - t_1,2 = 3-0-2 = 1;

R_n(1,3) = t_n (3) - t_p(1) - t_1,3 = 8-0-8 = 0;

R_n(2,3) = t_n (3) - t_p(2) - t_2,3 = 8-2-5 = 1;

R_n(2,5) = t_n (5) - t_p(2) - t_2,5 = 8-2-4 = 2;

R_n(3,4) = t_n (4) - t_p(3) - t_3,4 = 17-8-7 = 2;

R_n(3,6) = t_n (6) - t_p(3) - t_3,6 = 31-8-23 = 0;

R_n(4,5) = t_n (5) - t_p(4) - t_4,5 = 29-15-12 = 2;

R_n(4,6) = t_n (6) - t_p(4) - t_4,6 = 31-15-4 = 12;

R_n(5,7) = t_n (7) - t_p(5) - t_5,7 = 39-27-10 = 2;

R_n(6,7) = t_n (7) - t_p(6) - t_6,7 = 39-31-8 = 0;

 

Работа (4,7) имеет большой резерв времени (12), значит можно с этой работы снять на данном этапе ресурсы и перебросить их на работы лежащие на критическом пути. Аналогично, работы (2,5),(3,4),(4,5),(5,7) имеют резерв времени равный 2. Работу (2,3) считаем под критической, а работы с нулевым резервом времени — критические. На рисунке критический путь отмечен жирной линией.

 

15. Метод Дейкстры. (!)

Задача маршрутизации.

Алгори́тм Де́йкстры — алгоритм на графах. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

16. Метод Форда Фалкерсона. (!)