Динамические потоки. Задача транспортировки

Интерес к транспортировке возник в области потоков в сетях в течение 1940-х и 50-х годов. Было опубликовано множество работ в этой области, однако все они содержали одно интересное упущение. Несмотря на естественную связь между потоками в сетях и задачами транспортировки, большинство исследований в области теории потоков игнорировали самый главный вопрос, который задает любой ребенок, сидящий на заднем сиденье автомобиля: «Мы уже приехали?». Родители, вынужденные постоянно выслушивать этот вопрос, несомненно, подумают о времени, прежде чем думать о том, куда и как ехать далее.

Форд и Фалкерсон были хорошо осведомлены о важности времени в транспортировке, и они учли его в их модели сети. Они обобщили стандартное определение сети путем добавления в него транзитных времен между вершинами, получив тем самым динамическую сеть. Каждое ребро yz в динамической сети моделирует трубопровод из вершины y в вершину z. Пропускная способность ребра yz соответствует площади сечения труб, тем самым ограничивая количество потока, которое может быть передано за единицу времени. Транзитные времена соответствуют длине трубопровода; они определяют, сколько времени требуется потоку на прохождения из вершины y в вершину z вдоль ребра yz. Динамический поток перемещается с течением времени в динамической сети. Он является расширением традиционных потоков; отображением пар (ребро, время) в величину потока, а не отображением ребер как это было ранее.

Со времен Форда и Фалкерсона исследования в области динамических потоков направлены как на теоретические исследования математических моделей, так и на практические и алгоритмические аспекты их реализации. В то же время было уделено недостаточно внимания алгоритмической теории. В частности, очень немного было известно о вычислительной сложности задач о динамических потоках. В диссертации Хоупа (Hoppe, 1995) акцент был сделан именно на разработке теоретически эффективных алгоритмов. Эта работа устранила разрыв между изучением потоков в традиционных и динамических сетях.

Универсально-максимальные динамические потоки

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

Форд и Фалкерсон обнаружили оригинальный полиномиальный алгоритм для данной задачи. Гэйл, Уилкинсон и Миниека рассматривали вариант задачи о максимальном динамическом потоке, в котором сток должен был получить как можно больше потока на каждом промежуточном шаге до T и включительно. Вдобавок к этому поток должен покидать источник как можно позднее. (Факт существования такого потока нетривиален и был установлен Гэйлом). Позже Уилкинсон и Миниека независимо получили псевдополиномиальный алгоритм нахождения такого потока.

Первый полиномиальный алгоритм нахождения значения универсально-максимального динамического потока для любого ребра для каждого отдельного момента времени (т.е. временной разрез полного решения) был предложен Хоупом. Он также предложил первый полиномиальный алгоритм, который приближает универсально-максимальный динамический поток с коэффициентом 1 + eps для любого eps > 0. (Алгоритм работает полиномиальное относительно 1/eps время).

Наибыстрейшие потоки

Другой вариант задачи о максимальном динамическом потоке это задача о наибыстрейшем потоке, в которой нам задана величина потока v и

требуется найти допустимый динамический поток, который доставит v единиц потока из источника в сток за наименьшее возможное время. Задача о наибыстрейшем потоке может быть сведена к задаче о максимальном динамическом потоке с помощью двоичного поиска. Баркард (Burkard) и др. изучали эту задачу и описали более эффективную технику ее решения.

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

Хоуп (Hoppe) в своей диссертации (1995) представил первый (сильно) полиномиальный алгоритм для задачи о наибыстрейших перевозках - обобщении задачи эвакуации, где в дополнение к нескольким источникам разрешены несколько стоков. Алгоритм Хоупа также для целочисленных входных данных гарантирует целочисленное решение.

В 2005 году в работе «Наибыстрейшие потоки с несколькими источниками» Рауфа (Rauf) алгоритм Хоупа был обобщен на случай сетей с несколькими источниками.

Планирование сетей

Несмотря на то, что задача эвакуации и задача о наибыстрейшей перевозке мотивированы необходимостью планирования действий в случае бедствий и непредвиденных ситуаций, они имеют приложения и в других областях. Рассмотрим компьютерную сеть; каждая машина имеет свою очередь на вычисление задач единичного размера. Задача может быть либо вычислена на машине локально, либо послана по сети для удаленного вычисления. Каждое соединение в сети можно охарактеризовать пропускной способностью и временем транзита. Требуется распланировать выполнение задач таким образом, чтобы последняя из них была вычислена как можно раньше.

Эта задача легко сводится к задаче о наибыстрейших перевозках, применяя наш алгоритм решения которой мы получим первый полиномиальный алгоритм решения задаче о планировании вычислительных сетей для задач единичного размера, но только в некоторых очень специальных случаях. Физзано (Fizzano) и Штейн (Stein) рассматривали кольцевые сети с единичными пропускными способностями и транзитными временами. Хоуп предложил алгоритм, работающий в сети общего вида, с произвольными пропускными способностями и временами транзита.

Заключение

Исследования потоков в сетях развивались одновременно с теорией линейного программирования (и теорией оптимизации в более общем случае). Так как потоки в сетях представляют собой специальный вид линейных программ, они могут быть решены как линейные программы. Более того, для сетей с целочисленными пропускными способностями гарантировано наличие целочисленного решения. Доказательство этого факта в 1955 году позволило получить первый алгоритм точного решения потоковых задач в сетях небольшого размера.

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

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

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

 «Мирным» применением теории потоков являются всевозможные задачи связанные с транспортировкой грузов. В более простой модели ответ на этот вопрос дает задача о назначениях – обобщение задачи о максимальном паросочетании. Более сложные модели опираются на теорию динамических потоков, и здесь есть еще много задач для дальнейших исследований.

Библиография

1. Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficieny. Volume A. Springer, Berlin, 2003

2. Bruce E. Hoppe. Efficient Dynamic Flow Algorithms. PhD Thesis, Cornell Univeristy, 1995

3. T. Кормен, Ч. Лейзесон, Р. Ривест. Алгоритмы: построение и анализ. МЦНМО, 2001

4. Л. Р. Форд, Д. Р. Фалкерсон. Потоки в сетях. Перевод с английского И.А. Вайнштейна. М:Мир, 1966

5. E. Minieka. Dynamic network flows with arc changes. Networks journal, 1974

6. David Gale. Transient Flows in networks. RAND, 1958

7. Imran Rauf. Earliest Arrival Flows with Multiple Sources. Master Thesis in Computer Science. Saarland University, 2005

8. Wikipedia, the Free Encyclopedia http://en.wikipedia.org

9. «Алголист». http://algolist.manual.ru/maths/graphs/maxflows/