О максимальном потоке (в сетевой постановке)

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

Рассмотрим транспортную сеть, имеющую один пункт производства , один пункт потребления и N — 2 перевалочных пункта. Назовем потоком из пункта в пункт систему перевозок, удовлетворяющую следующим условиям:

(4.24).

(4.25).

(4.26).

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

(4.27).

Сложим последнее равенство со всеми равенствами (4.25) и (4.26). Нетрудно видеть, что левая часть полученного равенства обращается в нуль, так как для любого числа , стоящего со знаком «плюс», найдется это же число, стоящее со знаком «минус». Действительно, всякая коммуникация выходит ровно из одного пункта и входит ровно в один пункт . Поэтому одно из равенств (4.25) или (4.26), соответствующее пункту , содержит в левой части слагаемое , а другое, соответствующее пункту , — вычитаемое . Таким образом, приходим к соотношению.

Итак, из пункта вывозится отрицательное количество единиц продукта (-р), а это и означает, что в него ввозится р единиц, что и утверждалось.

Пункт PN носит название «сток» .

Задачей о максимальном потоке называется задача отыскания потока наибольшей величины из пункта в пункт или, что-то же самое, задача нахождения максимума линейной функции (4.26) при линейных ограничениях (4.25) и (4.24).

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

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

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

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

В этом случае под потоком понимается система перевозок, удовлетворяющая следующим условиям:

Здесь I — множество номеров всех пунктов транспортной сети, за исключением пунктов . Величиной потока р, которая максимизируется, называется суммарное количество продукта, вывозимое из пунктов

Метод решения задачи о максимальном потоке разработан американскими математиками Фордом и Фулкерсоном [11, 36, 38, 39].