Пример. В вершину 1входит лишь одна дуга (0,1), поэтому

В вершину 1 входит лишь одна дуга (0,1), поэтому

λ ¹j = λ o + y 01 = 1

В вершину b входят две дуги (a,b) и (g,b), поэтому

λ ¹b = max{ λ ¹a + y ab, λ ⁰g + y gb} = max{2, 1} = 2

Аналогично:

λ ¹c = max{ λ ¹b + y bc, λ ⁰g + y gc,

λ ⁰d + y dc } = max{3, 1, 1} = 3

λ ¹d = max{ λ ⁰e + y ed, λ ⁰f + y fd} = max{1, 1} = 1

λ ¹e = max{ λ ¹a + y ae, λ o + y oe, λ ⁰f + y fe } =

= max{2,1,1} = 2

λ ¹f = λ o + y of = 1

λ ¹g = max{ λ ¹a + y ag, λ ⁰e + y eg} = max{2, 3} = 3

Второй шаг: (например с конца)

λ ²g =  ¹ g = 3

λ ²f = λ ¹ f = 1

λ e = max{ λ ¹a + y ae, λ o + y oe, λ ²f + y fe } =

= max{2, 1, 1} = 2

λ ²d = max{ λ ²e + y ed, λ ²f + y fd } = 3

λ ²c = max{ λ ¹b + y bc, λ ²g + y gc, λ ²d + y dc } = 4

λ ²b = max{ λ ¹a + y ab, λ ²g + y gc } = 4

λ ²a = λ o + y oa = 1

На третьем шаге: (с начала сети)

λ ³a = 1, λ ³a = 4, λ ³a = 5, λ ³a = 3, λ ³a = 2,

λ ³a = 1, λ ³a = 3.

На четвертом шаге: не меняется ни одно λ ³j

λ ⁴j = λ ³j = λ^ j (j = 1, …, 7)

Т.о получаем распределение вершин (рис. 6.6):

0 – 0-го ранга

a,f – 1-го ранга

e – 2-го ранга

d,g – 3-го ранга

b – 4-го ранга

c – 5-го ранга

Затем присваиваем номера как выше.

Алгоритм вычисления минимального времени и критического пути

Аналогичен предыдущему, но вместо У ij = 1 Þ У ij = tij

Первый шаг: Каждому j приписываем λj = 0 и У ij = tij

Общий шаг: Для всей пронумерованной сети от 0 до n последовательно вычисляем новое значения:

λ`j = max{ λ`i + tij} (j = 1, …, n) λ`o = λo = 0

I

и записываем около каждого вычисленного λ`j номера

i 1, i 2,…, iν, тех событий i, для которых в предыдущей формуле был достигнут максимум.

Эти пометки будут затем использованы при отыскании критического пути.

Т.к. сеть просматриваем в порядке 0,1, …,i, …,j, … n

то λ`j вычисляется лишь после того, как вычислены все λ`i, участвующие в вычислении λ ` j (i < j).

Каждое из чисел λ`j (j = 1, …, n), полученное после единственного шага, определяет максимальную продолжительность пути из 0 в 1 и, по определению, равно минимальному времени Т j наступления события j.

Наконец число λ`n = Т nдает критическое время проекта.

Пример. Вернемся к сетевому графику рис.6.6 и пометим продолжительность каждой работы.

Рис.6.7.

Предварительный шаг: Для каждого j число λj = 0.

Первый шаг. Просматриваем сеть, начиная с 0, и по формуле вычисляем все λ`j = Т ⁰ j.

В скобках рядом с Т ⁰ j пометим номера тех событий i, для которых достигаются соответствующие T j.

Получим:

λ`o = λo = 0 = T ⁰ o,

λ` 1 = λ ` o + to 1 = 2 = T ⁰1 (0),

λ` 2 = λ ` o + to 2 = 1 = T ⁰2 (0),

λ` 3 = max{λ ` o+to 3, λ `1 +t 13, λ `2 +t 23 }= max{5,4,3}

= 5 = T ⁰3 (0),

λ` 4 = max{λ `2 +t 24, λ `3 +t 34 }= max{8,11}

= 11= T ⁰4 (3),

λ` 5 = max{λ `3 +t 35, λ `1 +t 15 }= max{7,8}

= 8 = T ⁰5 (1),

λ` 6 = max{λ `5 +t 56, λ `1 +t 16 }= max{10,7}

= 10 = T ⁰6 (5),

λ` 7 = max{λ `4 +t 47, λ `5 +t 57, λ `6 +t 67 } =

= max{15,15,14}=15=T ⁰7 (4,5)

Таким образом, критическое время проекта T ⁰7 = 15.