Алгоритм нахождения поздних сроков наступления событий

Алгоритм нахождения ранних сроков наступления событий

1. Полагаем T₁^P = 0.

2. Для j = 2, 3,..., n вычисляем T_j^P = (T_k^P + t_kj)

Здесь I(j) – множество всех дуг, входящих в вершину j.

Критическое время Т_kp = T_n^P.

1. Полагаем Т_n^П = Т (как правило Т = Т_kp.).

2. Для i = n-1, n-2,... 1, вычисляем

T^П_i = .

Здесь 0 (i) – множество вершин, которые являются конечным для дуг, выходящих из вершины i.

Рассмотрим сетевой график, описанный в таблице 1. События (вершины) сетевого графика изображены следующим образом:

В верхней четверти записан номер события (вершины) в соответствии с правильной нумерацией. Номер вершины k_i, при движении из которой получе­но значение T_i^P, заносится в нижнюю четверть. В левой четверти записывается ранний срок наступления события T_i^P, а в правой четверти – его поздний срок наступления T_i^П.

Найдем ранние сроки наступления каждого события для сетевого графика, изображенного на рис. 3.

Полагаем T₁^P = 0, k₁ = 0. Рассматриваем вершины в порядке возрастания их номеров.

T₂^P = T₁^P + t₁₂ = 0 + 10 = 10, k₂ = 1;

T₃^P = max (T₁^P + t₁₃; T₂^P + t₂₃) = max (0 + 15; 10 + 0) = T₁^P + t₁₃ = 15, k₃ = 1;

T₄^P = max (T₂^P + t₂₄; T₃^P + t₃₄) = max (10 + 5; 15 + 20) = T₃^P + t₃₄ = 35, k₄=3;

T₅^P = max (T₃^P + t₃₅, T₄^P + t₄₅) = max (15 + 15; 35 + 8) = T₄^P + t₄₅ = 43, k₅=4;

T₆^P = T₄^P+ t₄₆ = 35 + 6 = 41, k₆ = 4;

T_kP = max (T₅^P + t₅₇; T₆^P + t₆₇) = max (43 + 15; 41 + 10) = T₅^P + t₅₇ = 58, k₇=5.

Построим критический путь, начиная с конечной вершины, двигаясь по номерам вершин k_i,, стоящих в нижней четверти.

В результате получим 1 – 3 – 4 – 5 – 7. Найдем поздние сроки наступле­ния событий. Полагаем время окончания всего проекта T = T₇^П = T_kp. = 58. Поставим это значение в правую четверть конечной вершины 7.

T₆^П = T₇^П – t₆₇ = 58 – 10 = 48;

T₅^П = T₇^П – t₅₇ = 58 – 15 = 43;

П₄^П = min (T₆^П – t₄₆; T₅^П – t₄₅) = min (48 - 6; 43 - 8) = 35;

T₃^П = min (T₅^П - t₃₅; T₄^П - t₃₄) = min (43 - 15; 35 - 20) = 15;

T₂^П = min (T₄^П - t₂₄; T₃^П – t₂₃) = min (35 - 5; 15 - 0) = 15;

T₁^П = min (T_П³ - t₁₃; T₂^П – t_1П) = (15 – 15; 15 – 10) = 0.

В результате получаем следующую сетевую модель, содержащую под­робную информацию о ранних, поздних сроках наступления событий, крити­ческом времени и критическом пути. Критический путь отмечен двойными линиями.

Рис. 7

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 7. В приведенных ниже таблицах комплекс работ задан их порядковыми номерами, отношением предшествования. Указаны про­должительности работ. Необходимо составить сетевой график выполне­ния работ и посчитать все его числовые характеристики.

№ ра-бот № ва-рианта
	Каким работам предшествует	4,10	10,5		8,10				-	-
Продолжитель-ности работ
	Каким работам предшествует		10,6	5,10		10,9			-	-
Продолжитель­ности работ
	Каким работам предшествует		10,4,7						-	-
Продолжитель­ности работ
	Каким работам предшествует	4,9,5	9,8						-		-
Продолжитель-ности работ
	Каким работам предшествует	4,9		5,9					-	6,7	-
Продолжитель-ности работ
	Каким работам предшествует	3,4				9,7					-
Продолжитель-ности работ
	Каким работам прешествует	3,4				7,9			7,9		-
Продолжитель-ности работ
	Каким работам предшествует	3,4	5,8	7,9	5,8				7,9		-
Продолжитель-ности работ
	Каким работам предшествует	3,4		6,8,9						-	-
Продолжитель-ности работ
	Каким работам предшествует		5,7	8,9		4,6	8,9			-	-
Продолжитель-ности работ

ЛИТЕРАТУРА

1. Кузнецов А.В., Холод Н.И. Математическое программирование. – Мн., Вышэйшая школа, 1984.

2. Балашевич В.А. Математические методы в управление производством. – Мн., Вышэйшая школа, 1976.

3. Банди Б. Основы линейного программирования. – М., Радио и связь, 1988.

4. Банди Б. Методы оптимизации. Вводный курс. – М., Радио и связь, 1989.

5. Калихман И.Л. Сборник задач по математическому программированию. – М., Высшая школа, 1975.

6. ЕмеличеваЕ.В., Еровенко Л.Д., Корзников А.Д., Ласый П.Г. Сборник задач и методические указания к решению задач по математическому программированию. – Мн., ротапринт БГПА, 1996.

7. Гайков Н.Е., Емеличева Е.В., Корзников А.Д., Павлов В.В., Смирнов М.Б. Математические методы в технико-экономических задачах. – Мн., ротапринт БПИ, 1991.

СОДЕРЖАНИЕ

Стр.

1.	РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ЖОРДАНА-ГАУССА …………………………………………………….
	Контрольные задания для самостоятельного решения ………………..
2.	РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГЕО­МЕТРИЧЕСКИМ МЕТОДОМ …………………………………………..
	Контрольные задания для самостоятельного решения…………………
3.	Решение задачи линейного программирования Симплекс-методом…………………………………………………
	Контрольные задания для самостоятельного решения…………………
4.	ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД………………………………
	Контрольные задания для самостоятельного решения…………………
5.	ТРАНСПОРТНАЯ ЗАДАЧА……………………………………………..
	Контрольные задания для самостоятельного решения…………………
6.	Задача о максимальном потоке в сети…………………...
	Контрольные задания для самостоятельного решения…………………
7.	Сетевое планирование…………………………………………...
	Контрольные задания для самостоятельного решения…………………
8.	ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ ……………………………………..
	Контрольные задания для самостоятельного решения…………………
	ЛИТЕРАТУРА…………………………………………………………….

Дата добавления: 2017-02-01