n

1

2

3

4

5

6

7

8

9

10

11

РНАЧ(v)

0

0

5

35

35

50

55

65

68

65

71

РВЫП(v)

0

5

35

50

47

55

65

68

71

68

71

Шаг n

Действия выполняемые шагом

1

Объявление значений ПВЫП(v), vV равным Т.

Текущая вершина vk=11.

2

ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 71}.

3

ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 71}

ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 71}

4

Текущая вершина vk=10.

5

Переход в Шаг 2.

2

ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 68}

3

ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(10)}{ПВЫП(7) стало равным 68}

4

Текущая вершина vk=9.

5

Переход в Шаг 2.

2

ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 68}

3

ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(9)}{ПВЫП(8) стало равным 68}

4

Текущая вершина vk=8.

5

Переход в Шаг 2.

2

ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 65}

3

ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(8)}{ПВЫП(7) стало равным 65}

4

Текущая вершина vk=7.

5

Переход в Шаг 2.

2

ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 55}

3

ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 55}

ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 55}

4

Текущая вершина vk=6.

5

Переход в Шаг 2.

2

ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 50}

3

ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(6)}{ПВЫП(5) стало равным 50}

4

Текущая вершина vk=5.

5

Переход в Шаг 2.

2

ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 43}

3

ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 43}

4

Текущая вершина vk=4.

5

Переход в Шаг 2.

2

ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 35}

3

ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 35}

4

Текущая вершина vk=3.

5

Переход в шаг 2.

2

ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 5}

3

ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 5}

4

Текущая вершина vk=2.

5

Переход в Шаг 2.

2

ПНАЧ(2)=ПВЫП(2)-t(2) {ПНАЧ(2) стало равным 0}

3

ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0}

4

Текущая вершина vk=1.

5

Переход в Шаг 2.

2

ПНАЧ(1)=ПВЫП(1)-t(1) {ПНАЧ(1) стало равным 0}

3

Переход в Шаг 4.

4

Переход в Шаг 6.

6

Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.

Работы

РНАЧ

РВЫП

ПНАЧ

ПВЫП

Резерв

1

0

0

0

0

0

2

0

5

0

5

0

3

5

35

5

35

0

4

35

50

35

50

0

5

35

47

43

55

8

6

50

55

50

55

0

7

55

65

55

65

0

8

65

68

65

68

0

9

68

71

68

71

0

10

65

68

68

71

3

11

71

71

71

71

0

n

Наименование работы

Предшеству-ющие работы

Время вы-полнения t(vk)

1.

Начало проекта (фиктивн. работа)

Нет

0

2.

Монтаж металлоконструкций нижней обвязки каркаса

1

5

3.

Устройство бетона под стойки

2

3

4.

Монтаж стоек

3

10

5.

Монтаж опорных столиков

4

5

6.

Монтаж балок

2

7

7.

Монтаж металлоконструкций ворот

6

7

8.

Обшивка стен и кровли волнистым листом

6

12

9.

Монтаж козлового крана

7

5

10.

Устройство асфальтобетонных покрытий

8

5

11.

Конец проекта (фиктивн. работа)

5,9,10

0

Шаг n

Действия выполняемые шагом

1

Объявление значений РНАЧ(v) и РВЫП(v), vV равным нулю.

Текущая вершина vk=1.

2

Вершин предшествующей первой нет.

Значение РНАЧ(1)=РВЫП(1)+t(1).

3

Текущая вершина vk=2.

4

Переход в Шаг 2.

2

РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0}

РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 5}.

3

Текущая вершина vk=3.

4

Переход в Шаг 2.

2

РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5}

РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 8}.

3

Текущая вершина vk=4.

4

Переход в Шаг 2.

2

РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)} {РНАЧ(4) стало равным 8}

РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 18}.

3

Текущая вершина vk=5.

4

Переход в Шаг 2.

2

РНАЧ(5)=МАКС{РВЫП(4),РНАЧ(5)} {РНАЧ(5) стало равным 18}

РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 23}.

3

Текущая вершина vk=6.

4

Переход в Шаг 2.

2

РНАЧ(6)={РВЫП(2),РНАЧ(6)} {РНАЧ(6) стало равным 5}

РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 12}.

3

Текущая вершина vk=7.

4

Переход в Шаг 2.

2

РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)} {РНАЧ(7) стало равным 12}

РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 19}.

3

Текущая вершина vk=8.

4

Переход в Шаг 2.

2

РНАЧ(8)=МАКС{РВЫП(6),РНАЧ(8)} {РНАЧ(8) стало равным 12}

РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 24}.

3

Текущая вершина vk=9.

4

Переход в Шаг 2.

2

РНАЧ(9)=МАКС{РВЫП(7),РНАЧ(9)} {РНАЧ(9) стало равным 19}

РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 24}.

3

Текущая вершина vk=10.

4

Переход в Шаг 2.

2

РНАЧ(10)=МАКС{РВЫП(8),РНАЧ(10)} {РНАЧ(10) стало равным 24}

РВЫП(10)=РНАЧ(10)+t(10) {РВЫП(10) стало равным 29}.

3

Текущая вершина vk=11.

4

Переход в Шаг 2.

2

РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)} {РНАЧ(11) стало равным 24}

РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(10)}{РНАЧ(11) стало равным 29}

РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 29}.

3

Переход в Шаг 5.

5

Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.