Задача об источниках и потребителях

Транспортная сеть

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

2.1.2 В теории графов транспортная сеть – ориентированный взвешенный граф N=(V,E) без петель, в котором каждое ребро (i,j) E имеет неотрицательную пропускную способность (capacity) d_ij≥0. Если ребро (i,j) E, то d_ij=0. Под потоком (flow) x_ij понимается количество груза (продукции, вещества, энергии, информации), проходящего через ребро (i,j) в единицу времени, и называемое потоком по ребру (i,j). Принимается, что x_ii=0 (граф без петель!). В транспортной сети выделяются две вершины: источник (source) (исток или вход сети) s и сток (или выход сети) (sink) t такие, что любая другая вершина сети лежит на пути из s в t. В транспортной сети существует один исток и один сток. Случаи, когда имеется несколько источников и/или несколько стоков, могут быть сведены к рассматриваемому нами случаю введением обобщённых (фиктивных) источника и стока. Считается, что пропускная способность вершин неограничена, т.е. d_i=∞. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.

Целочисленная транспортная сеть – транспортная сеть, все пропускные способности рёбер которой – целые числа.

2.1.3 Потоком в транспортной сети N называется неотрицательная вещественная функция, определённая на множестве дуг и удовлетворяющая следующим условиям:

–ограниченности (capacity constraints) – поток не может превысить пропускную способность, т.е.

x_ij≤d_ij; (2.1)

–антисимметричности (skew symmetry) – предполагается, что если из вершины i в вершину j направляется поток величиной x_ij, то величина обратного потока из j в i равна -x_ij, т.е.

x_ji = -x_ij; (2.2)

–cохранения потока (flow conservation) – означает, что количество груза, притекающее в вершину, равно количеству груза, вытекающего из него, т.е.

для всех . (2.3)

Это свойство математически вытекает из условия антисимметричности.

Из свойств потоков по рёбрам сети следует, что общее количество груза, исходящего из истока s, совпадает с общим количеством груза, поступающего в сток t, т.е. величина (значение, мощность) f потока (value of flow) на сети равна

. (2.4)

Необходимо различать понятия потока в сети и величины потока. Поток в сети – это функция X=[x_ij], определённая на множестве дуг, а величина потока определяется последней формулой. Эти понятия часто путают, однако, между ними существенное различие: поток – это функция, а величина потока – число.

2.1.4 Дуга сети (i,j) называется насыщенной, если потокпо этой дуге равен пропускной способности этой дуги, т.е. x_ij=d_ij, и ненасыщенной, если x_ij<d_ij.

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

Введём понятие разреза сети. Разрезом (s-t cut) называется разбиение множества всех вершин V сети на два подмножества A и B таких, что , , т.е. разрезом сети А/В называют совокупность рёбер (i,j), начальные вершины которых принадлежат подмножеству А, а конечные – подмножеству В.

Величина

, (2.5)

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

Величина

, (2.6)

представляющая собой сумму потоков x_ij по всем рёбрам разреза, называется потоком через разрез.

Отыскание минимального разреза – одна из основных задач анализа транспортных сетей.

В силу конечности графа минимальный разрез может быть найден перебором всех разрезов, но этот путь, конечно, неприемлем для достаточно больших графов. Оказывается, что минимальный разрез можно отыскать при помощи максимального потока сети на основании теоремы Форда-Фалкерсона.

Теорема Форда-Фалкерсона. В любой транспортной сети величина любого максимального потокаравна пропускной способности любого минимального разреза.

2.2 Задача о максимальном потоке

2.2.1 История задачи

Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW.

После вступления США во Вторую мировую войну в 1941 году, математик Джордж Бернард Данциг поступил на работу в отдел статистического управления Военно-воздушные силы США в Вашингтоне. С 1941 по 1946 годы он возглавлял подразделение анализа военных действий (Combat Analysis Branch), где работал над различными математическими проблемами. Впоследствии, используя работу Данцига, задача о максимальном потоке была впервые решена в ходе подготовки воздушного моста во время блокады Западного Берлина, происходившей в 1948–1949 гг.

В 1951-м году Джордж Данциг впервые сформулировал задачу в общем виде.

В 1955-м году, Лестер Форд (англ. Lester Randolph Ford, Jr.) и Делберт Фалкерсон (англ. Delbert Ray Fulkerson) впервые построили алгоритм, специально предназначенный для решения этой задачи. Их алгоритм получил название алгоритма Форда-Фалкерсона.

В дальнейшем решение задачи много раз улучшалось.

В 2010 году исследователи Джонатан Кёлнер (Jonathan Kelner) и Александр Мэдри (Aleksander Mądry) из МТИ (Массачусетский технологический институт) вместе со своими коллегами Дэниелем Спилманом (Daniel Spielman) из Йельского университета и Шень-Хуа Тенем (Shang-Hua Teng) из Южно-Калифорнийского университета продемонстрировали очередное улучшение алгоритма, впервые за 10 лет.

2.2.2 Постановка задачи

2.2.2.1 Задачу о максимальном потоке (maximum flow problem) можно сформулировать следующим образом. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена? Или, найти поток на сети такой, чтобы его величина f была максимальна. А вот ещё одна формулировка задачи: найти такой поток по транспортной сети, чтобы сумма потоков из истока, или, что то же самое, сумма потоков в сток была максимальна. И, наконец, найти максимальный поток в транспортной сети.

Математически задача о максимальном потоке формулируется следующим образом: найти поток на сети X=[x_ij] такой, который удовлетворяет условиям (2.1)–(2.3) и максимизирует целевую функцию (2.4).

2.2.2.2 Алгоритм Форда-Фалкерсона позволяет определить максимальный поток на сети с заданными пропускными способностями рёбер (дуг) и состоит из следующих шагов (здесь представлена одна из многочисленных интерпретаций алгоритма):

– шаг 1 – найти цепь, соединяющую s с t, по которой поток принимает положительное значение в направлении s→t. Если такой цепи не существует, то перейти к шагу 3; в противном случае – к шагу 2;

– шаг 2 – пусть – пропускные способности дуг цепи (s,t) в направлении s→t (t→s) и

. (2.7)

Матрицу пропускных способностей D=[d_ij] изменить следующим образом:

1) вычесть θ из всех (эта операция даёт возможность использовать остатки пропускных способностей дуг выбранной цепи в направлении s→t);

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

Заменить текущую D-матрицу на вновь полученную и перейти к шагу 1;

– шаг 3 – найти максимальный поток в сети. Пусть D=[d_ij] – исходная матрица пропускных способностей транспортной сети, и пусть D*=[d_ij*] – последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2). Оптимальный поток в дугах X=[x_ij] задаётся как

(2.8)

Максимальная величина потока из s в t равна

. (2.9)

Заметим, что f_max есть сумма всех положительных θ, определённых на шаге 2. Таким образом, можно объяснить, почему используются положительные элементы матрицы D-D* для определения результирующего потока в направлении s→t.

Алгоритм Форда-Фалкерсона используется при решении многих практических задач. Одна из них – задача об источниках и потребителях.

2.2.2.3 Минимальный разрез А/В ищут по матрице D* следующим образом. Для его нахождения необходимо выделить вершины подмножества А; их выделяют постепенно, начиная с истока s. С этой целью просматривают первую строку матрицы D* – строку s – и выписывают номера (обозначения) вершин, соответствующих ненулевым элементам: это и будут вершины, в которые можно попасть из истока s по ненасыщенным рёбрам сети. Составляют список вершины s. Далее рассматриваем каждую из вершин списка вершины s и составляем для неё аналогичным образом свой список (при этом вершины, встречавшиеся в прежних списках, повторно не выписываются). Если в этом процессе сток t не встретится, то поток максимален и задача решена (в противном случае поток не максимален и его мощность можно увеличить). Остальные вершины сети составят подмножество В. Минимальный разрез будет представлять собой совокупность рёбер (i,j), начальные вершины которых принадлежат подмножеству А, а конечные – подмножеству В. На сети минимальный разрез изображается в виде линии, пересекающей все рёбра, входящие в него.

2.2.2.4 Приведём случаи задач, сводящихся к постановке исходной задачи о максимальном потоке:

– произвольное число источников и/или стоков – еслиисточников s_i больше одного, добавляем новую вершину s, которую делаем единственным источником. Добавляем рёбра с бесконечной пропускной способностью от s к каждому из старых источников s_i (либо с пропускной способностью, равной сумме пропускных способностей рёбер, исходящих из s_i). Аналогично, если стоков t_j больше одного, добавляем новую вершину t, которую делаем единственным стоком. Добавляем рёбра с бесконечной пропускной способностью от каждого из старых стоков к t (либо с пропускной способностью, равной сумме пропускных способностей рёбер, входящих в t_j);

– неориентированные рёбра – каждое неориентированное ребро {u,v} заменяем на пару ориентированных рёбер (u,v) и (v,u);

– ограничение пропускной способности вершин – каждую вершину v с ограниченной пропускной способностью d_v расщепляем на две вершины v_in и v_out. Все рёбра, до расщепления входящие в v, теперь входят в v_in. Все рёбра, до расщепления исходящие из v, теперь исходят из v_out. Добавляем ребро (v_in,v_out) с пропускной способностью d_v;

– несколько источников s_i с запасами продукции a_i и несколько стоков t_j с потребностями b_j в ней (задача об источниках и потребителях) – добавляем единственный источник s и соединяем с источником s_i дугой c пропускной способностью a_i; аналогично, каждый сток t_j соединяем с единственным добавленным стоком t дугой с пропускной способностью b_j.

2.2.2.4 Найдём максимальный поток (согласно приведенному в подпункте 2.2.2.2 алгоритму) на транспортной сети, представленной на рисунке 2.1.

Матрица D, соответствующая сети на рисунке 2.1, представлена таблицей 2.1.

Таблица 2.1

В качестве исходной цепи можно выбрать цепь s→1→t. Таким образом (см. таблицу 2.1), ячейки (s,1), (1,t) помечаются знаком «минус», а ячейки (1,s), (t,1) – знаком «плюс». Для данной цепи максимальный поток определяется как

.

Матрица D в таблице 2.1 корректируется путём вычитания θ=7 из всех элементов, помеченных знаком «минус», и сложения со всеми элементами, имеющими знак «плюс». Результаты приведены в таблице 2.2. Результаты последующих итераций приведены в таблицах 2.2–2.5.

Таблица 2.2

Таблица 2.3

Таблица 2.4

Таблица 2.5

Таблица 2.6 – Матрица D*

Из таблицы 2.6 следует, что между s и t нельзя построить цепей с положительным потоком, таким образом, таблица 2.6 даёт матрицу D*. Максимальный (оптимальный) поток Х получают путём вычитания из матрицы D (см. таблицу 2.1) матрицы D* (см. таблицу 2.6) и заменой отрицательных величин нулями (пустыми клетками). Таблица 2.7 даёт матрицу X=D–D*. Из таблицы 2.6 видно, что величина максимального потока

.

Таблица 2.7 – Матрица X=D–D*

Сумма всех θ (7+5+4+3+1) даёт ту же величину максимального потока. Графически решение представлено на рисунке 2.2; здесь же изображён разрез А/В минимальной пропускной способности (составляем список вершины s: s||3; список вершины 3 пуст: 3||^., следовательно, в подмножество А попали вершины s и 3)

,

где А={s,3}; B={1,2,t}.

Варианты заданий

Задание №1

Задача об источниках и потребителях

Задана транспортная сеть (рисунок 2.3). Известны объёмы продукции у поставщиков a₁ и a₂ и потребность продукции у потребителей b₁ и b₂. Требуется максимально удовлетворить потребности потребителей.