Критический путь. Алгоритм Беллмана–Калаба.

Задача о критическом пути ставится таким образом. Задаётся орграф, который называется транспортной сетью, каждой дуге которого  соответствует некоторая величина – длина дуги . Нужно найти кратчайший путь из истока 0 в сток z. Как длина пути может фигурировать длина дороги, количество бензина, израсходованное при движении по этому участку дороги, стоимость проезда по этому участку и т.д.

Задача определения критического пути часто возникает в сетевом планировании и управлении. Любая сложная комплексная работа изображается в виде кибернетической модели – сетевого графика, который является некоторой транспортной сетью. Начальная точка 0 этой сети соответствует началу, конечная точка z – окончанию комплексных работ. Каждая отдельная работа комплекса показана в виде дуги, начальная вершина которой соответствует началу работы, а конечная вершина – концу. Каждой дуге  соответствует время выполнения работы , каждой вершине  – время наступления этого события  [началу работы, изображенной дугой ].

Первое, что нужно сделать при использовании метода нахождения критического пути, это составить перечень операций, которые могут быть детализированны. Потом, для каждой операции определить операции, которые ей предшествуют. Эта часть анализа является очень важной и занимает много времени.

Если комплекс работ состоит в создании фирмы, которая занимается вопросами защиты информации и информационных сетей, то отдельными операциями (работами) могут быть:

1) изучение рынка услуг в сфере защиты информации и информационных сетей;

2) знакомство с работой фирм, которые работают в направлении защиты информации;

3) разработка пилотного проекта;

4) поиск инвесторов;

5) получение лицензии;

6) получение кредитов;

7) поиск помещения для офиса;

8) ремонт помещения;

9) подбор персонала;

10) закупка оборудования;

11) установка оборудования;

12) рекламная акция;

13) поиск клиентов, оформление договоров;

14) выполнение контрактов.

На рис. 5 показан сетевой график, состоящий из восьми работ.

Рис. 5. Пример сетевого графика.

Путь, вдоль которого суммарное время выполнения работ было бы максимальным, называется критическим. Без его уменьшения нельзя сократить общее время выполнения работ. Критических путей может быть несколько. Тогда для сокращения времени выполнения комплекса работ необходимо уменьшить время выполнения работ, входящих в критические пути. Если ввести в рассмотрение еще и стоимости выполнения работ, то в этом критическом пути следует сократить те работы, которые имеют наименьшее увеличение стоимости при сокращении времени выполнения работ, т.е. если обозначить зависимость стоимости выполнения работы от времени через , то сократить нужно ту работу критического пути, для которого производная  будет максимальной. После сокращения времени одного критического пути может появиться другой критический путь.

Для нахождения критического пути в сети рассмотрим алгоритм Беллмана-Калаба. Он основан на принципе оптимальности и использует функциональное уравнение Беллмана. Принцип оптимальности Беллмана в данном случае можно сформулировать так: любой максимальный (критический) путь, содержащий не более  дуг, образованный частичными путями, содержащими не более  дуг, , которые (пути) также максимальны.

Пусть  – множество дуг, образующих сеть проекта,  – время выполнения операции ,  – сроки наступления события , которые ожидаются и  – граничный срок. Тогда

, , ,      (1)

где  – дуга, которая идет из вершины  в вершину , а  – подмножество дуг, которые входят в вершину .

j

 

Рис.1               Рис.2

Рис.3

МАХ означает, что мы берем максимум по всем дугам, которые принадлежат .

Таким же образом

,                                          (2)

 – срок окончания всего проекта,                                          (3)

 – момент начала работ.                                                                 (4)

Резервы времени событий и операций получаются из (1) и (2) и определяются следующими соотношениями:

резерв времени событий                                                   (5)

полный резерв времени операции                             (6)

свободный резерв времени операции                       (7)

независимый резерв времени операции                              (8)

Резервы событий и операций могут быть вычислены и другим методом:

, ,                       (9)

где  означает множество путей, соединяющих 1 с ,

                    (10)

где  означает множество путей, соединяющих  с

                                                                                   (11)

Потом по формулам (5)-(8) определяют резервы времени событий и операций.