|
|
|||
|
8 |
Щебёночное основание под полы |
7 |
3 |
|
9 |
Асфальтовое покрытие |
8 |
3 |
|
10 |
Уборка строительного мусора после строит. |
7 |
3 |
|
11 |
Конец проекта (фиктивная работа) |
9,10 |
0 |
Рис 1. Проект гаража для стоянки автопогрузчиков.
Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Шаг n
Действия выполняемые шагом
1
Объявление значений РНАЧ(v) и РВЫП(v), vÎV равными нулю. Текущая вершина vk=1.
2
Вершин предшествующей первой нет.
РВЫП(1)=РНАЧ(1)+t(1). {РНАЧ(1) стало равным 0}
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) стало равным 35}.
3
Текущая вершина vk=4.
4
Переход в Шаг 2.
2
РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)}{РНАЧ(4) стало равным 35}
РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 50}.
3
Текущая вершина vk=5.
4
Переход в Шаг 2.
2
РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 35}
РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 47}.
3
Текущая вершина vk=6.
4
Переход в Шаг 2.
2
РНАЧ(6)=МАКС{РВЫП(4),РНАЧ(6)}{РНАЧ(6) стало равным 50}
РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 55}.
3
Текущая вершина vk=7.
4
Переход в Шаг 2.
2
РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47}
РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)}{РНАЧ(7) стало равным 55}
РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 65}.
3
Текущая вершина vk=8.
4
Переход в Шаг 2.
2
РНАЧ(8)=МАКС{РВЫП(7),РНАЧ(8)} {РНАЧ(8) стало равным 65}
РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 68}.
3
Текущая вершина vk=9.
4
Переход в Шаг 2.
2
РНАЧ(9)=МАКС{РВЫП(8),РНАЧ(9)}{РНАЧ(9) стало равным 68}
РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 71}.
3
Текущая вершина vk=10.
4
Переход в Шаг 2.
2
РНАЧ(10)=МАКС{РВЫП(7),РНАЧ(10)}{РНАЧ(10) стало равным 65}
3
Текущая вершина vk=11.
4
Переход в Шаг 2.
2
РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)}{РНАЧ(11) стало равным 71}
РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 71}
3
Переход в Шаг 5.
5
Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.
Таблица результатов работы алгоритма.
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
Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.
Шаг n
Действия выполняемые шагом
1
Объявление значений ПВЫП(v), vÎV равным Т.
Текущая вершина 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}
При использовании материалов активная ссылка на источник обязательна.