Алгоритм вычисления резервов времени

Шаг 0. Полагаем.

Шаг 1. ПолагаемМ = 0.

Для делаем следующее:если, то полагаемМ = 1; принимаем.

Шаг 2. ЕслиМ=0 (т. е. значенияне изменялись), то полагаем. Конец.

Если М 0, то переходим на шаг 1.

Замечание.Пустьдлина максимального (по числу дуг) пути из вершины 1 в вершинуm. Очевидно, что не более чем запросмотров списка дуг сетевого графика все координаты векторабудут определены.

Пример 6. Для сетевого графикаГ(8, 14,S, T) (см. табл. 3) найти критические события и напряженные работы, соответствующие найденному в примере 5 календарному плану.

Решение.Применяя описанный выше алгоритм вычисления резервов времени, получим:

Т а б л и ц а 5

	1	2	3	4	5	6	7	8
	0	19	12	2	32	24	16	42
	0	27	12	2	32	37	30	42
	0	8	0	0	0	13	14	0

Критические события: 1, 3, 4, 5, 8.

Напряженные работы: 3, 6, 9, 11.

Определение 15.Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на этом пути:

.

Определение 16. Путь, имеющий наибольшую продолжительность, называетсякритическим.

Так как ,, и, то продолжительность любого критического пути совпадает с кратчайшим сроком выполнения всего комплекса работ:

.

От продолжительности работ, лежащих на критическом пути (критических работ), зависит срок завершения всех работ. Сокращение или увеличение сроков выполнения критических работ соответственно сокращает или увеличивает продолжительность выполнения всего проекта.

Теорема 6.Для критичности путииз вершинывнеобходимо и достаточно, чтобы все его дуги отвечали напряженным работам.

Доказательство.Рассмотрим путьиз вершиныв. Пронумеруем его вершины:

.

Напомним, что работа sназывается напряженной, если:

а) события являются критическими, т. е.

; (11)

б) (). (12)

Доказательство теоремы проведем в два этапа.

1) Докажем, что путь рявляется критическим тогда и только тогда, когда для всех его дуг выполняются соотношения (12).

Из допустимости векторов следует, что

.

.

Аналогично получаем для вектора :

.

Путь ркритичен в том и только в том случае, если. Следовательно, все приведенные выше неравенства выполняются как равенства, т. е.и соотношения (12) верны для всех дуг путир. Таким образом, установлено, что путь является критическим тогда и только тогда, когда все его дуги отвечают напряженным работам.

2) Докажем, что для пути, ведущего из вершины в, условия (11) и (12) эквивалентны.

Действительно, так как , то. Тогда из соотношений (12) следует, что

и .

Аналогично устанавливаем, что условия (11) выполняются для всех остальных вершин пути р. Таким образом, из соотношений (12) вытекает справедливость формул (11). Обратная связь также очевидна. Теорема доказана.

10. ЗАДАЧИ ЛП, ЭКВИВАЛЕНТНЫЕ ЗАДАЧАМ О КРИТИЧЕСКОМ ПУТИ И КРАТЧАЙШЕМ СРОКЕ