13.2. Алгоритм Форда
Для нахождения критического пути и срока завершения проекта разработан ряд алгоритмов. Приведем один из них.
1. Отметить каждую
вершину индексом
.
Положить все
.
2. Найти такую дугу
,
что
,
и заменить
на
.
Заметим, что
,
если
.
3. Продолжать так
до тех пор, пока не останется дуг,
приводящих к увеличению
.
Существует вершина
такая, что
,
так как
монотонно возрастает в течении процедуры
2) – 3) и вершина
является последней вершиной, использованной
для увеличения
.
Точно также пусть
вершина
такова, что
,
и т.д.
Так как
последовательность
,
,
,
… является строго убывающей, то в
некоторый момент времени получим, что
.
Тогда
будет величиной самого длинного пути
из
в
(продолжительность реализации проекта)
и последовательность вершин
,
определит критический путь.
Контрольные вопросы:
1. Сетевая модель, ее характеристика и особенности.
2. Области применения и эффективность сетевых моделей.
3. В чем состоит технология построения сетевых графиков (работы, события, критический путь)?
4. Каковы правила построения сетевого графика?
5. Как рассчитать временные параметры сетевого графика, продолжительность критического пути?
6. Что понимается под полным и частным резервами времени?
7. Как отразить расчет параметров сетевой модели на графике и в таблице?
8. Как оптимизировать сетевую модель по критерию времени?