Алгоритмы оптимизации на графовых моделях

В данной главе рассматриваются графовые модели [4,5] для оптимизации транспортных сетей и потоков, решения задач календарного планирования, задач о назначениях и других задач дискретной оптимизации. Изложение алгоритмов оптимизации ориентировано на реализацию с помощью цифровых вычислительных машин.

Решение задачи о максимальном потоке методом расстановки пометок на графе (алгоритм Форда-Фалкерсона).

Граф, элементам которого поставлены в соответствие некоторые параметры, называется сетью. В зависимости от приложений различают транспортные, электрические, информационные и т. п. сети.

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

Каждая вершина I характеризуется интенсивностью d (i). Те вершины, для которых D (i) 0, называются источниками, вершины, для которых D (i) 0 — стоками, остальные — нейтральными. Так, для транспортной сети источниками являются пункты-поставщики, стоками — пункты-получатели, нейтральными — пункты, где отсутствует как производство, так и потребление данного продукта.

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

Если в сети с одним источником S и одним стоком t задана функция пропускной способности {r_ij}, то в ней может быть задана также функция, называемая потоком.

Потоком в сети называется функция, сопоставляющая с каждой дугой целое число d_ij и обладающая свойствами:

0 d_ij r_ij, {x_i, x_j} X; (3.1).

(3.2).

(3.3).

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

Таким образом, потоком в сети или просто потоком называется совокупность {_ij} по всем дугам сети.

Условия (3.1) означают, что поток по каждой дуге неотрицателен и не превышает ее пропускной способности; условия (3.2) показывают, что количество вещества, протекающего в любую нейтральную вершину, равно количеству вещества, вытекающего из нее. Следовательно, общее количество вещества, вытекающего из источника, совпадает с общим количеством вещества, притекающего в сток, что и отражается в условии (3.3).

Линейная форма V в (3.3) есть величина потока в сети. Одна из основных задач на сетях состоит в определении величины наибольшего потока, допустимого в сети при заданных ограничениях на интенсивности потоков дуг. Математически она формулируется так: найти значения переменных d_ij, максимизирующие линейную форму (3.3) при ограничениях (3.1)-(3.2).

Рассмотрим решение поставленной задачи методом расстановки пометок непосредственно на графе (алгоритм Форда-Фалкерсона). Решение проводится путем многократного повторения двух шагов алгоритма.

Первый шаг. Пометим вершину-исток S меткой (0,) и отнесем вершину S к множеству R, а остальные вершины графа к множеству. Далее расстановка меток осуществляется последовательно. Рассмотрим правило формирования меток. Выберем любую помеченную вершину i (первоначально это единственная вершина S) (в дальнейшем для упрощения записи формул, относящихся к одному графу, вместо «вершина x_i» будем писать просто номер вершины «i». Отмеченные вершины относятся к множеству R, непомеченные к множеству. Рассмотрим все непомеченные вершины j, связанные дугами с вершиной i. Вершину j относят к множеству R, если выполняется одно из условий:

i R и d_ij r_ij; (3.4).

i R и d_ji 0. (3.5).

Тем вершинам j, для которых выполняется условие (3.4), припишем метку (i⁺, _j), где _j = min{_i, r_ij — d_ij}. Тем вершинам j, для которых выполняется условие (3.5), припишем метку (i^-, _j), где _j = min{_i, d_ji}.

Изложенное правило формирования меток для наглядности представим графически с помощью рис. 3.1 и 3.2 соответственно для случаев (3.4) и (3.5).

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

В первом случае (помечена вершина t) перейдем ко второму шагу, во втором случае исходный поток максимален.

Второй шаг. Вершина t имеет пометку (j⁺, _t) или (j^-, _t). Если пометка вида (j⁺, _t), заменяем d_jt на (d_jt + _t), если пометка вида (j^-, _t), то заменяем d_tj на (d_tj — _t). Затем в любом случае переходим к вершине j. В отношении любой вершины j поступаем аналогично: если ее пометка вида (i⁺, _j), то заменяем d_ij на (d_jt + _t), если ее пометка вида (j^-, _j), то заменяем d_ji на (d_ji — _t) и переходим к вершине i. Так поступаем, пока не достигнем источника S. После этого стираем все пометки и вновь переходим к первому шагу.

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

Несколько источников и стоков Предположим, что множество узлов сети разбито на три множества: S — множество источников, Т — множество стоков, R — множество промежуточных узлов. Расширим сеть, добавив два узла S^* и Т^* и все дуги (S^*, S) и (Т, Т^*). Доопределим значения пропускных способностей на вновь введенных дугах:

r^*(S^*, x_i) =, x_i S;

r^*(x_j, T^*) =, x_j T.

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