|
|
4 |
Переход в Шаг 2. |
2 |
РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)} {РНАЧ(11) стало равным 24} РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(10)}{РНАЧ(11) стало равным 29} РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 29}. |
3 |
Переход в Шаг 5. |
5 |
Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ. |
Таблица результатов работы алгоритма.
n
1
2
3
4
5
6
7
8
9
10
11
РНАЧ(v)
0
0
5
8
18
5
12
12
19
24
29
РВЫП(v)
0
5
8
18
23
12
19
24
24
29
29
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=29. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Шаг n
Действия выполняемые шагом
1
Объявление значений ПВЫП(v), vÎV равным Т.
Текущая вершина vk=11.
2
ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 29}.
3
ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 29}
ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 29}.
4
Текущая вершина vk=10.
5
Переход в Шаг 2.
2
ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 24}.
3
ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(10)}{ПВЫП(8) стало равным 24}
4
Текущая вершина vk=9.
5
Переход в Шаг 2.
2
ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 24}.
3
ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(9)}{ПВЫП(7) стало равным 24}.
4
Текущая вершина vk=8.
5
Переход в Шаг 2.
2
ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 12}.
3
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(8)}{ПВЫП(6) стало равным 12}.
4
Текущая вершина vk=7.
5
Переход в Шаг 2.
2
ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 17}.
3
ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 12}.
4
Текущая вершина vk=6.
5
Переход в Шаг 2.
2
ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 5}.
3
ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(6)}{ПВЫП(2) стало равным 5}.
4
Текущая вершина vk=5.
5
Переход в шаг 2.
2
ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 24}.
3
ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(5)}{ПВЫП(4) стало равным 24}.
4
Текущая вершина vk=4.
5
Переход в Шаг 2.
2
ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 14}.
3
ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 14}.
4
Текущая вершина vk=3.
5
Переход в Шаг 2.
2
ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 11}.
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
Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.
Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPB(v)=ПHAЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).
Работы
РНАЧ
РВЫП
ПНАЧ
ПВЫП
Резерв
1
0
0
0
0
0
2
0
5
0
5
0
3
5
8
11
14
3
4
8
18
14
24
10
5
18
23
24
29
5
6
5
12
5
12
0
7
12
19
17
24
7
8
12
24
12
24
0
9
19
24
24
29
5
10
24
29
24
29
0
11
29
29
29
29
0
Из таблиы видно, что критическими работами являются 1, 2, 6, 8, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=29.
Пример 3: Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге.
n
Наименование работы
Предшеству-ющие работы
Время вы-полнения t(vk)
1.
Начало проекта (фиктивн. Работа)
Нет
0
2.
При использовании материалов активная ссылка на источник обязательна.