6.6.4. Формализация задачи поиска критического пути как задачи ЛП

Задача определения критического пути в сети проектов, решаемая методом СРМ, противоположна задаче вычисления кратчайшего пути (раздел 6.3) в том смысле, что здесь ищется самый длинный путь от начального узла до конечного. Можно применить формализацию задачи поиска кратчайшего пути из раздела 6.3.3 к задачам нахождения критического пути, решаемых метом СРМ (для краткости будем называть такие задачи задачами СРМ), следующим образом. Предположим, что в сеть в начальном узле поступает одна единица потока, которая покидает сеть в конечном узле. Обозначим

хц - величина потока, проходящего по дуге (£, j), соответствующей процессу (г, j), Dtj - длительность процесса (i, ;). В этих обозначениях целевая функция задачи линейного программирования запишется как

максимизировать г =

но всем процессам

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

общий входной поток = общий выходной поток.

Очевидно, что все переменные xtj неотрицательны. Отметим, что одно из ограничений избыточно.

Опять, как и в задачах поиска кратчайшего пути, для решения задачи СРМ можно применить двойственную задачу ЛП. В следующем примере покажем две формализации задачи СРМ.

Пример 6.6.5

Ниже дана формулировка задачи из примера 6.6.2 (см. рис. 6.54) в терминах сетевых моделей линейного программирования. Отметим, что узлы 1 и 6 являются соответственно начальным и конечным узлами.

С помощью программы TORA было получено следующее оптимальное решение: 2 = 25, х12(А)= 1, x2i(D) = 1, х45(Фиктивный) = 1, x66(G) = 1, все другие переменные равны 0. Решение определяет следующий критический путь: А -> D -> Фиктивный - G, при этом длительность проекта равна 25 дней.

Приведем формулировку двойственной задачи ЛП.

Минимизировать w = y6- ух

при выполнении условий

все yt не ограничены в знаке.

В формулировке двойственной задачи можно дать интересную интерпретацию двойственных переменных. Пусть yt - время узла отсчитываемое от некоторого момента времени, общего для всех узлов. В этом случае w = уе - у1 будет представлять длительность проекта. Каждое ограничение связано с определенным процессом, они устанавливают отношения предшествования между различными процессами. Например, неравенство у2-ул > 5 эквивалентно неравенству у2>у] + 5, которое показывает, что для узла 2 время у2 не может быть меньшим времени у, + 5. Минимум целевой функции определяет наименьший промежуток времени, при котором будут выполняться все ограничения. В этой интерпретации двойственные переменные могут принимать только неотрицательные значения. Время начала выполнения проекта г/, естественно установить равным нулю. В этом случае целевую функцию можно переписать как w = у&. Задание значения у1 = О также согласуется с тем, что одно из первоначальных условий лишнее.

С учетом того, что переменные могут принимать только неотрицательные значения, в программе TORA было получено следующее оптимальное решение двойственной задачи: w = 25, г/, = 0, у2 = 5, у3 = 11, у4 = 13, уъ = 13, ув = 25. Из полученного решения видно, что длительность проекта составляет w = 25 дней.

В соответствии с ограничениями, которые выполняются строго в виде равенств, определяем критические процессы: А -> D -> Фиктивный -> G. Из того факта, что, если ограничение удовлетворено в виде равенства, то соответствующее значение двойственной задачи должно быть положительным, в данном случае вытекает, что значения переменных прямой задачи СРМ (поскольку мы решаем двойственную), ассоциированные с такими ограничениями, будут равны 1. На этом основании можно заполнить следующую таблицу.

Отсюда получаем, что путь А - D - Фиктивный -> G является критическим. Заметьте, что положительное значение переменной прямой задачи всегда равно 1, поскольку задержка в один день для любого критического процесса приведет к увеличению продолжительности проекта на один день (напомним, что двойственные переменные интерпретируются как стоимость единицы ресурса, см. раздел 4.3.1).

УПРАЖНЕНИЯ 6.6.4

1. Используя формализацию линейного программирования, определите критический путь для сети проекта, показанного на рис. 6.55.

2. Используя формализацию линейного программирования, определите критический путь для сетей проектов, которые представлены на рис. 6.56.

6.6.5. Сети PERT

Метод PERT отличается от СРМ тем, что здесь длительность процессов характеризуется тремя оценками.

1. Оптимистичная оценка времени а, когда предполагается, что выполнение процесса будет происходить максимально быстро.

2. Наиболее вероятная оценка времени т, когда предполагается, что выполнение процесса будет происходить нормально.

3. Пессимистическая оценка времени Ь, когда предполагается, что выполнение процесса будет происходить очень медленно.

Любая возможная оценка времени выполнения процесса будет лежать в интервале (а, Ь). Поэтому оценка времени т также должна лежать в этом интервале. На основе этих оценок среднее время D выполнения процесса и дисперсия v вычисляются по формулам

- a + Am + b (b-a\2

Все вычисления метода СРМ, которые описаны в разделах 6.6.2 и 6.6.3 выполнимы, если заменить значения длительностей D процессов оценками D .

Теперь можно определить вероятность того, что узел модели будет достигнут в заранее запланированное время Sf. Пусть е.- время наискорейшего достижения узла Поскольку длительности выполнения процессов, которые ведут от начального узла к узлу j, - случайные величины, то ej также является случайной величиной. Предположив, что все процессы в сети статистически независимы, можно определить среднее (математическое ожидание) М{е;) и дисперсию var{e;} следующим образом. Если существует только один путь от начального узла к узлу j, то среднее является суммой ожидаемых длительностей D выполнения всех процессов, входящих в этот путь, а дисперсия равна сумме дисперсий v тех же процессов. С другой стороны, если к узлу ведет более одного пути, то до того, как будут вычислены среднее и дисперсия, необходимо найти вероятностное распределение длительности выполнения процессов, которые составляют самый длинный путь. Эта задача достаточно сложная, поскольку она эквивалентна задаче, вычисляющей распределение максимума нескольких случайных величин. Для упрощения этой задачи среднее МЦ} и дисперсия var{e} вычисляются только для пути, для которого сумма ожидаемой длительности выполнения процессов максимальна. Если несколько путей имеют равные значения среднего, то выбирается тот, для которого дисперсия больше, поскольку этот путь отражен наименее четко, и поэтому будет вычислена более общая оценка вероятностей.

После того как будет вычислено среднее М{е} и дисперсия уагЦ}, вероятность того, что узел будет достигнут в запланированное время S, можно вычислить по формуле

\е -Ще } S.-M{e }} P{jZS,} = P\ ; < ; \ = P{z<K,},