Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

щее возможности начинать все работы, выходящие из события 5/, в их наиболее ранние допустимые сроки tp:

P'n — независимый резерв времени, определяется как макси­ мально допустимое увеличение продолжительности работы, при ко­ тором не изменяются резервы времени других работ:

З а д а ч а 2. Пусть для выполнения комплекса работ необходи­ мо k видов ресурсов, причем каждая работа выполняется одним ви­ дом ресурса и известна интенсивность его потребления при задан­ ной продолжительности работы.

Задача 2, а. Определить времена начала работ (с учетом их тех­ нологической последовательности), при которых комплекс работ будет выполнен в минимально возможное время без превышения ограничений по каждому виду ресурса.

Задача 2, б. Определить времена начала работ (с учетом их тех­ нологической последовательности), при которых потребление ре­ сурсов было бы оптимальным. Оптимальность здесь может опреде­ ляться в смысле минимизации среднеквадратичного уклонения потребляемых ресурсов наибольшего по модулю уклонения потреб­ ляемого ресурса от среднего ежедневного значения или другим критериям. Время выполнения всего комплекса работ в этом слу­ чае считается заданным.

З а д а ч а 3. Пусть для каждой работы сетевого графика из­ вестна зависимость стоимости прямых затрат на ее выполнение от продолжительности в некотором допустимом диапазоне изменения последней. .

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

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

1.7. ЗАДАЧИ О ПОТОКАХ В СЕТЯХ

Многие задачи науки и техники сводятся к решению транспортных сетей. Большое распространение получили задачи об оптимальном распределении потока в транспортной сети. Важней­ шими из них являются задачи определения максимального и мини­ мального потоков транспортной сети. Решение этих задач важно для повышения эффективности многих систем, имеющих сетевую структуру (системы связи, системы транспортных дорог, газопрово­ дов). Определение максимального и минимального потоков нахо­

26

дит широкое применение при решении задач о наименьшем покры­ тии [10], задач теории информации и т. п. Согласно теории Келли [323, к задаче о максимальном потоке может быть сведена парамет­ рическая задача минимизации стоимости при планировании. К за­ дачам об экстремальных потоках сводятся задачи минимизации бу­ левых функций определенного класса [69].

Определение экстремальных потоков состоит в следующем. За­ дана транспортная сеть — конечный граф без петель G (N, А). Граф состоит из совокупности N элементов хи х2, ..., хп вместе с А не­ которых пар (Х[, X/) элементов, взятых из N. Обычно элементы мно­ жества N называют узлами, вершинами и т. п., а элементы множест­ ва Л — ветвями, дугами, ребрами и т. п. Каждая ветвь характери­ зуется числом dij, которое определяет пропускную способность

ветви. Существует один такой узел к, что f,7l = 0 , этот узел называ­ ется входом или истоком. Существует один такой узел к, что Гк =

=0 . Он называется выходом или стоком.

■Задача определения максимального потока [10] достаточно под­ робно рассмотрена Фордом и Фалкерсоном [171].Максимальный по­ ток через сеть определяется структурой сети и максимальными про­ пускными способностями ветвей dt/-, составляющими эту сеть. При рассмотрении задачи о максимальном потоке важным понятием яв­ ляется разрез [171].

Разрез сети (N , А), отделяющий ник, есть множество дуг (X , X), где к £ X, а к £ X. Число D (X, X) называется пропускной спо­

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

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

внекотором пути, то она может участвовать в другом пути только

сизмененной пропускной способностью, определяемой как

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

Ѳт = min di,.

Таким образом, решение задачи сводится к отысканию суммы минимальных пропускных способностей всех путей транспортной сети. Данный способ реализуется на универсальных цифровых вы­ числительных машинах. При этом в машину вводится матрица свя­ зей с указанием истока и стока сети. Затем осуществляется по­ следовательный перебор путей в сети, идущих от истока к стоку,

27

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

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

Для определения максимального потока транспортной сети мож­ но применить алгоритм, заключающийся в реализации арифмети-

Форд и Фалкерсон [171] для задачи о максимальном потоке уста­ новили следующую теорему.

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

Исходя из этого задача о максимальном потоке сводится к задаче определения кратчайшего пути. Для определения макси­ мального потока необходимо построить граф, двойственный исход­ ной транспортной сети. На рис. 7 показана планарная транспорт­ ная сеть (ветви проведены прямыми линиями) и двойственный ей граф (ветви показаны волнистой линией). Построение двойственно­ го графа состоит в замене граней исходной сети узлами и соедине­ нии этих узлов дугами таким образом, чтобы пути двойственного графа соответствовали разрезам исходной сети. Так, разрез, про­ ходящий по ветвям (я, а), (b, d) исходной транспортной сети, соответ­

£>і), (Ьъ q), (q, ку) и т. д. Каждой ветви двойственного графа припи­ сывается длина, равная пропускной способности той ветви исходной сети, которую данная ветвь пересекает слева, и равная нулю, если, ветвь двойственной сети пересекает ветвь исходной сети справа. Левая и правая стороны ветви исходной сети определяются по направлению потока в этой ветви. Таким образом, длина каждого,

28.

пути двойственной сети будет соответствовать пропускной способ­ ности соответствующего разреза. Например,

L {(а, с); (d, с); (d, k)) = D {(я', b^\ (bv сх); (clt k')} = 19.

Для определения максимального потока транспортной сети, как следует из теоремы Форда — Фалкерсона, необходимо определить минимальное сечение. Для этого достаточно в двойственном графе найти кратчайший путь из « в к, который будет соответствовать максимальному потоку истока к в сток к транспортной сети. В слу­ чае, если исходная транспортная сеть непланарная, т. е. существу­ ют перекрещивающиеся ветви (на-рис. 8 (а, d) и («, с)), то предва­ рительно такая сеть преобразует­ ся в планарную. Преобразование осуществляется заменой пересека­ ющихся ветвей ветвями, сходя­ щимися в одном узле. Узел обра­ зуется в точке пересечения ветвей.

чения потока снизу [10].

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

Известны методы определения максимального потока в сети [10, 39].

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

Однако Берж привел алгоритм в сокращенном виде и без дока­ зательства, что способствует в некоторых случаях неправильному его пониманию. В частности, в работе [166], а вслед за ней и в [4] утверждается, что этот алгоритм применим только к одному пути. Данные утверждения не верны.

Пусть задана сеть, представленная ориентированным линейным графом без циклов G (N , Л), состоящим из совокупности множества

29