2.5.1. Определения и постановки задач

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

Примеры:

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

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

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

4. В предыдущем примере известна стоимость передачи пакета для каждого канала сети. Требуется минимизировать стоимость передачи сообщения.

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

Введем определение потока в сети. Пусть имеется ориентированный граф, содержащий Nвершин иRдуг, в котором заданы две вершины - источникsи стокt, а для каждой дуги – неотрицательное числоC_ij, называемоепропускной способностьюдуги(i,j).ПотокомизsвtвеличиныVназывается набор чисел {f_ij},i,j=1,…,N, такой, что выполнены следующие условия:

При этом f_ij- величина потока на дуге(i,j). Условие (2.5.1) представляет собой принцип сохранения потока: из источникаsисходит поток величины V, такой же поток входит в стокt, а в промежуточных вершинах поток не может ни возникать, ни исчезать: количество потока, входящего в вершину, равно количеству потока, выходящего из нее. Условие (2.2) предусматривает, что величина потока на каждой дуге не должна превышать пропускную способность дуги, подобное условие характерно для многих прикладных задач.

Главная задача, которая возникает в всязи с понятием потока в сети – это задача о поиске максимального потокаизsвt. Требуется найти набор чисел {f_ij} , удовлетворяющий условиям (2.1) и (2.2), при котором величина потокаVмаксимальна. Постановка задачи может быть записана следующим образом:

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

Пусть X– некоторое множество вершин графа такое, чтоsX, аtX. Множество дуг(i,j)таких, что один конец дуги принадлежитX, а другой не принадлежитX, называетсяразрезом. Разрез, таким образом, - это множество дуг, исключение которых из сети отделило бы некоторое множество узлов от остальной части узлов. Дуги(i,j)такие, чтоiX, аjX, называютсяпрямымидугами разреза. Если жеjX,iX, то дуга называетсяобратной.Пропускной способностью разрезаназывается величина, равная сумме пропускных способностей всех прямых дуг разреза. Разрез называетсяминимальным, если его пропускная способность является наименьшей среди всех разрезов сети. Понятно, что в сети может быть несколько минимальных разрезов. Разрез называетсянасыщенным, если для прямых дуг величина потока равна пропускной способностиf_ij=C_ij, а для обратных дугf_ij=0.

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

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

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

Рис. 2.11

Пример. В графе на рис 2.11 числа на дугах обозначают пропускную способность и величину потока (числа в скобках). Поток V=6является максимальным, насыщенный разрез обозначен пунктирной линией.

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

С этой задачей тесно связана еще одна: о поиске максимального потока минимальной стоимости.

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

Пусть имеются mзаводов иnскладов. За определенный период времениi– й завод производитs_iединиц продукции,j– й склад может принятьd_jединиц. Стоимость перевозки единицы продукции с заводаiна складjравнаa_ij. Требуется максимизировать количество произведенной продукции и найти способ ее перевозки на склады, имеющий минимальную стоимость.

Все заводы могут произвести

единиц продукции, а склады – принять

единиц. Понятно, что максимальное количество производимой продукции равно минимальному из этих двух чисел.

Если обозначить f_ij- количество единиц продукции, перевозимых с завода на склад , то стоимость всех перевозок равна

и нужно найти величины f_ij, доставляющие минимум выражению (2.9).

Данная задача может быть представлена как задача поиска максимального потока минимальной стоимости.

Рис 2.12

На рис. 2.12 приведена сеть для транспортной задачи, в скобках – стоимость a_ijи пропускная способностьC_ijдуг. Вершиныз₁,…,з_mсоответствуют заводам, вершиныс₁,…,с_n– складам, добавлены фиктивный источникsи фиктивный стокt. Для дуг(s,з_i)установлена пропускная способностьs_i, для дуг(с_j,t)–d_j. Это обеспечит выполнение ограничения на количество продукции, производимой на каждом заводе и потребляемой на каждом складе. Для дуг вида(з_i,с_j)установлена стоимость передачи единицы потокаa_ij. Для решения задачи следует найти в этой сети максимальный поток минимальной стоимости. Тогдаf_s,зi будет означать количество продукции, которую следует произвести на заводеi, f_сj,t- количество продукции, потребляемой складомj, аf_зi,сj - количество продукции, которую с заводаiследует перевезти на складj. Насыщенным разрезом будет либо группа дуг, исходящих изs(еслиV₁V₂), либо группа дуг, заходящих вt(в противном случае).

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