Сетевые потоки

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

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

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

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

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

OR-Tools предоставляет несколько решателей для задач сетевого потока в своих графовых библиотеках.

В следующих разделах представлены примеры проблем с сетевыми потоками и показано, как их решить:

• Максимальные потоки
• Потоки с минимальными затратами
• Назначение как поток минимальной стоимости
• Назначение с бригадами рабочих