Сетевые графики (стр. 3 из 3)

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.	Разработка грунта экскаваторами с ковшом 0.5 м3 с погрузкой на автомобили-самосвалы.	1	16
3.	Зачистка дна и стенок с выкидкой грунта.	2	10
4.	Монтаж водопроводных колодцев	1	32
5.	Монтаж плит перекрытий из легкого бетона.	3	21
6.	Пробивка в бетонных стенах и полах отверстий.	5	5
7.	Оклейка плит рубероидом и гидроизолом на нефтебитуме в 1 слой.	4,5	14
8.	Заделка сальников при проходе труб через фундаменты или стены подвалов.	5	10
9.	Монтаж скоб.	6	7
10.	Устройство стяжек цементных.	9	5
11.	Конец проекта. (фиктивн. Работа)	7,8,10	0

Рис 3. Проект водоснабжения и наружной канализации при застройки квартала по ул. Токарей-Синяева в г. Екатеринбурге.

Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов.

Шаг n	Действия выполняемые шагом
1	Объявление значений РНАЧ(v) и РВЫП(v), vÎV равным нулю. Текущая вершина vk=1.
2	Вершин предшествующей первой нет. Значение РНАЧ(1)=РВЫП(1)+t(1).
3	Текущая вершина vk=2.
4	Переход в Шаг 2.
2	РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)}{РНАЧ(2) стало равным 0} РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 16}.
3	Текущая вершина vk=3.
4	Переход в Шаг 2.
2	РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)}{РНАЧ(2) стало равным 16} РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 26}.
3	Текущая вершина vk=4.
4	Переход в Шаг 2.
2	РНАЧ(4)=МАКС{РВЫП(1),РНАЧ(4)}{РНАЧ(4) стало равным 0} РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 32}.
3	Текущая вершина vk=5.
4	Переход в Шаг 2.
2	РНАЧ(5)=МАКС{РВЫП(3),РНАЧ(5)}{РНАЧ(5) стало равным 26} РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 47}.
3	Текущая вершина vk=6.
4	Переход в Шаг 2.
2	РНАЧ(6)=МАКС{РВЫП(5),РНАЧ(6)}{РНАЧ(6) стало равным 47} РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 52}.
3	Текущая вершина vk=7.
4	Переход в Шаг 2.
2	РНАЧ(7)=МАКС{РВЫП(5),РНАЧ(7)}{РНАЧ(7) стало равным 47 РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 61}.
3	Текущая вершина vk=8.
4	Переход в Шаг 2.
2	РНАЧ(8)=МАКС{РВЫП(5),РНАЧ(8)}{РНАЧ(8) стало равным 47} РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 57}.
3	Текущая вершина vk=9.
4	Переход в Шаг 2.
2	РНАЧ(9)=МАКС{РВЫП(6),РНАЧ(9)}{РНАЧ(9) стало равным 52} РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным }.
3	Текущая вершина vk=10.
4	Переход в Шаг 2.
2	РНАЧ(10)=МАКС{РВЫП(9),РНАЧ(10)}{РНАЧ(10) стало равным 59} РВЫП(10)=РНАЧ(10)+t(10) {РВЫП(10) стало равным 64}.
3	Текущая вершина vk=11.
4	Переход в Шаг 2.
2	РНАЧ(11)=МАКС{РВЫП(7),РНАЧ(11)}{РНАЧ(11) стало равным 61} РНАЧ(11)=МАКС{РВЫП(8),РНАЧ(11)}{РНАЧ(11) стало рвным 61} РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(11)}{РНАЧ(11) стало равным 64} РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 64}.
3	Переход в Шаг 5.
5	Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.

Таблица результатов работы алгоритма.

n	1	2	3	4	5	6	7	8	9	10	11
РНАЧ(v)	0	0	16	0	26	47	47	47	52	59	64
РВЫП(v)	0	16	26	32	47	52	61	57	59	64	64

Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=64. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.

Шаг n	Действия выполняемые шагом
1	Объявление значений ПВЫП(v), vÎV равным Т. Текущая вершина 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	0	0	0	0	0
2	0	16	0	16	0
3	16	26	16	26	0
4	0	32	18	50	32
5	26	47	26	47	0
6	47	52	47	52	0
7	47	61	50	64	3
8	47	57	54	64	10
9	52	59	52	59	0
10	59	64	59	64	0
11	59	64	64	64	0

Из таблицы видно, что критическими работами являются 1, 2, 3, 5, 6, 9, 10, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=64.

Литература:

1. Асанов М. О. «Дискретная оптимизация», УралНАУКА, Екатеринбург 1998.