Шаг n
|
Действия выполняемые шагом
|
|
1
|
Объявление значений ПВЫП(v), vV равным Т.
Текущая вершина vk=11.
|
|
2
|
ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 64}.
|
|
3
|
ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(11)}{ПВЫП(7) стало равным 64}
ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(11)}{ПВЫП(8) стало равным 64}
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(10)}{ПВЫП(9) стало равным 64}.
|
|
4
|
Текущая вершина vk=10.
|
|
5
|
Переход в Шаг 2.
|
|
2
|
ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 59}.
|
|
3
|
ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(10)} {ПВЫП(9) стало равным 59}.
|
|
4
|
Текущая вершина vk=9.
|
|
5
|
Переход в Шаг 2.
|
|
2
|
ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало ранвым 52}.
|
|
3
|
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(9)}{ПВЫП(6) стало равным 52}.
|
|
4
|
Текущая вершина vk=8.
|
|
5
|
Переход в Шаг 2.
|
|
2
|
ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 54}.
|
|
3
|
ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(8)}{ПВЫП(5) стало равным 54}.
|
|
4
|
Текущая вершина vk=7.
|
|
5
|
Переход в Шаг 2.
|
|
2
|
ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 50}.
|
|
3
|
ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 50}
ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(7)}{ПВЫП(4) стало равным 50}.
|
|
4
|
Текущая вершина vk=6.
|
|
5
|
Переход в Шаг 2.
|
|
2
|
ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 47}.
|
|
3
|
ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(6)}{ПВЫП(5) стало равным 47}.
|
|
4
|
Текущая вершина vk=5.
|
|
5
|
Переход в Шаг 2.
|
|
2
|
ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 26}.
|
|
3
|
ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 26}.
|
|
4
|
Текущая вершина vk=4.
|
|
5
|
Переход в Шаг 2.
|
|
2
|
ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 18}.
|
|
3
|
ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(4)}{ПВЫП(1) стало равным 18}.
|
|
4
|
Текущая вершина vk=3.
|
|
5
|
Переходв Шаг 2.
|
|
2
|
ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 16}.
|
|
3
|
ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 16}.
|
|
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
|
Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.
|
|
|
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPB(v)=ПHAЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
Из таблицы видно, что критическими работами являются 1, 2, 3, 5, 6, 9, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=64.
1. Асанов М. О. «Дискретная оптимизация», УралНАУКА, Екатеринбург 1998.