Оптимизация пути на сети
Пусть сетевой график построен. За какое время его можно осуществить?
Путём в сети называется последовательность рёбер, такая, что конец каждого ребра совпадает с началом следующего и ни одно ребро не встречается больше одного раза.
Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на нём.
Рассмотрим все пути, ведущие от исходного события к завершающему. Как правило, их несколько. Путь с наибольшей продолжительностью называется критическим путём, а работы, на нём лежащие - критическими.
Оказывается, минимальное время осуществления всего проекта равно продолжительности критического пути. Действительно, все работы, в том числе критические, необходимо выполнять в порядке, который определяет сетевой график, то есть движение по критическому пути неизбежно. Кстати, в сети может быть несколько критических путей.
Понятно, что сокращение или увеличение сроков выполнения критических работ соответственно сокращает или увеличивает общее время выполнения проекта.
На сетевом графике критический путь выделяют более жирными стрелками.
Что касается работ, не лежащих на критическом пути, то они, вообще говоря, допускают некоторое запаздывание в их выполнении, которое не задержит сроков реализации всего проекта.
Для отыскания критического пути на сети и его продолжительности применяется алгоритм пошаговоё оптимизации. Он основан на принципе оптимальности Р. Беллмана: критический путь обладает тем свойством, что каков бы ни был его отрезок от исходной до некоторой вершины сети, оставшаяся часть критического пути между этой и завершающей вершинами должна быть наиболее продолжительной.
Рассмотрим использование этого алгоритма
на примере конкретного сетевого графика
(цифры
в нижних половинках кружков являются
номерами этих вершин).
Обозначим
через
продолжительность
наиболее «долгого пути», ведущего от
вершины 0 к вершине
.
Тогда
В соответствии с принципом оптимальности
Р.Беллмана получаем:
(*)
где
- множество вершин сети, непосредственно
предшествующих
- ой вершине (при
=5,
например,
),
- продолжительность работы между
-ой
и
-ой
вершинами (
).
В нашем случае:
Заметим, что в рассмотренном примере вершина 3 при вычислениях предшествовала вершине 2, а вершина 6 - вершине 5.
Итак, время (наименьшее) выполнения всего проекта равно 48 единицам. Соответствующий этому времени путь несложно восстановить, двигаясь назад от завершающей вершины 9 к исходной 0. В вершину 9 можно попасть лишь из вершины 8 (48 = 42+6), в 8 - из 6 (42 = 29+13), в 6 - из 2 (29 = 20+9), в 2 - из 3 (20 = 13+7) и, наконец, в 0 - из 3 (13 = 13+0).
Таким образом, критический путь
Аналогичным образом можно определить
кратчайший путь на сети. Для
этого в формуле (*) достаточно
заменить на
В нашем случае этот путь, точнее пути
и
имеют продолжительность 22 единицы.
Действительно,
В заключение отметим, что все вычисления можно выполнять непосредственно на сети. При этом полезно вычёркивать рёбра, «прошедшие «обработку», и последовательно приписывать каждой рассмотренной вершине наиболее продолжительное время её достижения из 0, как это сделано на последнем рисунке.