Задача о критическом пути

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

При использовании указанных методов зависимость между отдельными работами задается с помощью некоторого орграфа Г,в котором каждая дуга отвечает определенной работе. Если в этом графе дуги образуют путь из вершины в вершину , то это означает, что выполнение работ s, для которых = , может начинаться лишь после завершения всех работ . Ввиду этого каждую вершину i орграфа Г интерпретируют как событие, означающее возможность выполнения тех работ s, для которых = i, т. е. завершение всех работ s, для которых = i. Приведенная интерпретация означает, что для выполнимости рассматриваемого комплекса работ соответствующий орграф Г не должен содержать контуров. Действительно, если бы имелся некоторый контур , то для выполнения каждой работы потребовалось бы предварительно завершить все остальные работы, что приводит к неразрешимому вопросу, типа известного вопроса о том, кто снес яйцо, из которого вылупилась первая курица.

Следовательно, практически реализуемые комплексы работ описываются орграфами Г, не содержащими контуров. Ясно, что в каждом таком орграфе имеется, по крайней мере, одна начальная вершина , для которой

Æ,

и, по крайней мере, одна конечная вершина , для которой

Æ.

В сетевом планировании обычно ограничиваются рассмотрением случая, когда = 1 является единственной начальной вершиной, a = n — единственной конечной вершиной. Первая из этих вершин интерпретируется как начальное событие, а вторая — как конечное событие, означающее завершение всего комплекса работ. При этом, как нетрудно проверить, для каждой вершины в орграфе Г имеется путь с концом в этой вершине и началом в вершине = 1. Точно так же для каждой вершины имеется путь из этой вершины в конечную вершину ⁼ n.

Рис. 16.

Легко проверить, что в орграфе Г, изображенном на рис. 16, нет контуров и в нем имеются одна начальная вершина = 1 и одна конечная вершина = 8. Жирной линией показан путь из начальной вершины = 1 в конечную вершину = 8.

Допустим теперь, что рассматриваемый комплекс работ описывается орграфом Г, обладающим указанными свойствами. Кроме того, известно время , необходимое для выполнения каждой работы . В этом случае, говорят, что имеется сетевой график Г,где .

Календарный план выполнения сетевого графика Г,определяется выбором m -мерного вектора

, (6.1)

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

, . (6.2)

При этом срок выполнения всего комплекса работ определяется величиной

. (6.3)

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

Задача о кратчайшем сроке. При заданном сетевом графике Г определить вектор (6.1), минимизирующий линейную функцию (6.3) при ограничениях (6.2).

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

Задача о критическом пути. При исходных данных задачи о кратчайшем сроке определить п-мерный вектор

x = (x₁, х₂,..., х_m), , (6.4)

максимизирующий линейную функцию

(6.5)

при ограничениях

(6.6)

Ясно, что задача о критическом пути является частным случаем сетевой транспортной задачи, в которой = 1, = -1 и = 0, , a , .

Рассмотренные задачи могут решаться простым методом, сводящийся к последовательным просмотрам дуг сетевого графика.

Для каждой вершины , как уже отмечалось, имеется, по крайней мере, один путь р = { } с концом в этой вершине и началом в вершине = 1. Множество та­ких путей обозначим через и рассмотрим величины

, , . (6.7)

Нетрудно проверить, что они удовлетворяют соотношениям

, (6.8)

где — определяемый формулой (5.3) кратчайший срок для сетевого графика Г. Но тогда в качестве решения задачи о кратчайшем сроке может быть принят вектор (6.1) с компонентами (6.7).

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

, , (6.9)

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

Пример 6.1. Рассмотрим сетевой график Г, отвечающий числовым данным, приведенным в табл. 10. Заметим, что соответствующий орграф Г совпадает с изображенным на рис. 16.

Таблица 10

s
is, js	1, 2	1, 3	1, 4	2, 5	3, 2	3, 5	3, 6	3, 7	4, 3	4, 7	5, 8	6, 8	7, 6	7, 8

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

.

Получаемые при этом величины , очевидно также не превосходят . Далее, если при очередном просмотре всех дуг не происходит ни одного изменения величин , то это означает, что имеющиеся совпадают с искомыми величинами (6.9).

В качестве исходных принимаем =0, . Затем, просматривая дуги , последовательно находим новые значения

= 10, = 3, = 2, = 15, = 10, = 23, = 15, = 7, = 12, = 7, = 33, = 33, = 15, = 33,

которые приведены во второй строке табл. 11.

На втором просмотре дуг определяем новые значения величин , приведенные в третьей строке табл. 11. На третьем просмотре дуг ни одна из найденных величин не изменяется. Следовательно, полученные при втором просмотре величины ti совпадают с искомыми величинами .

Таблица 11

1	2	3	4	5	6	7	8

Рассмотренные величины (6.7) определяют минимально возможные сроки выполнения всех событий. При анализе сетевых графиков представляет интерес выявление имеющихся резервов в сроках выполнения отдельных событий. С этой целью через для каждой вершины обозначим множество путей из этой вершины в конечную вершину i = n. Затем рассмотрим величины

, , . (6.10)

Так как множество путей очевидно, совпадает с множеством путей , то

.

Что касается остальных вершин , то для них, очевидно, имеют место неравенства

, . (6.11)

При этом неотрицательные величины

, (6.12)

можно интерпретировать как имеющиеся резервы времени для выполнения соответствующих событий. Событие i сетевого графика Г называется критическим, если в соответствующем неравенстве (6.11) достигается равенство, т. е. резерв времени (6.12) для выполнения этого события равен нулю.

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

, (6.13)

где под понимается множество дуг с началом в вершине i.

Работу s сетевого графика Г называют напряженной если события и , являются критическими и при этом , или, что то же, . Ясно, что для определения всех критических событий и всех напряженных дуг достаточно вычислить величины (6.7) и (6.10).

Пример 5.2. Для сетевого графика Г, который уже рассматривался в связи с определением величин (см. пример 6.1), найдем величины , , , а также все критические события и напряженные работы. Исходные данные примера повторены в табл. 10 с тем, чтобы читатель мог проводить соответствующие выкладки, не отрываясь от текста. Кроме того, во второй строке табл. 11 приведены величины , , найденные при решении примера 6.1. Интересующие нас величины , , также определяются за просмотров дуг . Предпо­ложим, что уже имеются некоторые величины , , причем = = 42. Тогда при просмотре очеред­ной дуги s новое значение определяется по формуле

.

Получаемые при этом величины , очевидно, также не меньше . Далее, если при очередном просмотре всех дуг не происходит ни одного изменения величин t_i, то это означает, что имеющиеся t_i совпадают с искомыми величинами (6.10). В качестве исходных принимаем , . Затем за несколько просмотров дуг находим величины которые приведены в третьей строке табл. 12. В последнюю строку таблицы заносим величины , подсчитанные по формулам (6.12). Так как = = = = = 0, то соответствующие события являются критическими. Что касается напряженных работ, то таковыми являются работы s {3, 6, 9, 11). На рис. 16 соответствующие дуги отмечены жирными линиями.

Таблица 12

i

Лемма. Путь р = { s₁, s₂,..., s_l } из = 1 в = n в том и только том случае является критическим, когда соответствующим вершинам отвечают критические события, а дугам — напряженные работы.