Критический путь

Постановка задачи.
В середине 50-х годов в теории графов сформировалась довольно странная на первый взгляд потоковая задача про поиск максимального пути на сетке, ведь логично было б искать пути, которые минимизируют определенный интегральный показатель, что сводиться чаще всего к затратам.
Основою этой задачи стала практика современного менеджмента относительно управления сложными проектами, основанная в США (1968 г.), моделями которых есть так званые сетевые графики. Соответственная методология получила название «сетевое планирование и управление» (СПУ).
Узлы в этой сетки называются событиями, а дуги – операциями (работами). Событие есть результатом выполнения всех операций, от которых оно зависит, на сетке это узел, в который входят соответствующие дуги, то есть, их концы имеют признак (номер, название). После достижения события начинаются следующие операции, что зависит от него, на сетке это узел, с которого выходят соответствующие дуги, их начала имеют признак (номер, название).
В сетевом графике реализованы два принципа:
операция начинается только тогда, когда достигнуто ее начальное событие;
событие считается достигнутым, если исполнены все операции, которые есть входами.
Для расчета сетевого графика разработаны два методы:
критического пути (Critical Path Method, CPM), где длительность операций однозначно определенно и задано конкретными числами;
анализа и просмотра программ (Program Evaluation and Review Technique, PERT), где длительность операций неопределенно, потому их задают определенными вероятностными оценками.
Цель обоих методов одинакова – она состоит в определении минимальной продолжительности исполнения всех операций проекта. Оказалось, что, чтобы определить минимальный строк исполнения всего проекта, графической и математической моделью есть сетевой график, нужно найти конфигурацию та длину максимального пути, что соединяет начальный узел с конечным. Этот путь называют критическим путем, операции, что его образовывают, есть критическими, поскольку должны быть исполнены в определенный для них срок, их задержка приведет к увеличению длительности проекта. Все остальные операции некритические, поскольку имеют резерв времени. Следовательно, основное внимание менеджера должно быть сосредоточено на критических работах.
Пример: Задано сетевой график в виде ориентированного графа, который состоит из 9 узлов (событий) и 13 дуг (операций). Нужно найти критический путь от узла № 1 к узлу № 2.
Экономико-математическая модель.
Найти вектор неизвестных (Дуга), чтобы
Общая длина пути = Дуга*Продолжительность - mах
При условии сохранения балансу потоков для каждого узла: для узла-источника – Выход – Вход = 1; для промежуточных узлов - Выход – Вход = 0; для узла –стока - Выход – Вход = -1; все неизвестные больше нуля.
Реализация в Excel.
В таблице для операций определяем диапазон для неизвестных (Дуга) и вычисляем значение целевой ячейки (Длительность) за формулой =СУММПРОИЗВ(Дуга; Продолжительность).

В таблице для событий вычислить суму входящих (Вход) и выходящих (Выход) потоков, их алгебраическую суму (Сума), задать колонку правых ограничений (Ограничения).
Для вычисления потока в узлах используют функцию вычисления сумы величин, координаты которых удовлетворяют определенные условия (то есть, если определенная величина принадлежит соответствующему множеству). В Excel такую процедуру исполняет функция =СУММЕСЛИ(). Например, сума входящих потоков узла определяется за формулой =СУММЕСЛИ(Все концы дуг; узел; потоки), то есть, суммируются потоки по тем дугам, концы которых совпадают с поточным узлом.
За формулой =СУММЕСЛИ(Все начала дуг; узел; потоки) суммируют выходящие потоки.

Запускаем программу Поиск решений командой Данные/Анализ / Поиск решения (В Excel 2007) Сервис/Поиск решения (В Excel 2003 и ниже). В полях Установить целевую ячейку, Изменяя ячейки, Ограничения вводим соответствующие адреса ячеек. Так как это линейная модель, то не забываем фиксировать в окне Параметры поиска решений переключатель на позицию Линейная модель и Неотрицательные значения. Нажимаем кнопку Выполнить и в появившемся окне Результаты поиска решения выводим отчет по устойчивости.

Анализ результата.
Найденные критические работы (см. таб.) дают максимальную продолжительность проекта – 48.
Нормированные стоимости (Н-стоим) некритических работ указывают на резерв времени.
Теневые цены (Т-цена) для узлов-событий определяют частичные критические пути от узла 1 к всем остальным узлам, включительно узел 9.