Тема 16. Оптимизация сетевых потоков Основные понятия и определения
Составляющие транспортной сети: источник, сток, промежуточные вершины. Поток. Пропускная способность. Задача о максимальном потоке. Задача о потоке минимальной стоимости. Задача о кратчайшем маршруте.
На этой лекции мы рассмотрим 3 класса задач, имеющих важное прикладное значение. Их решение позволяет наиболее эффективно использовать имеющиеся транспортные системы, например, максимизировать их пропускные способности либо свести к минимуму транспортные издержки. Одной из таких задач является задача о максимальном потоке.
16.1. Задача о максимальном потоке
По
сети, состоящей из множества вершин
и дуг, пропускаются потоки вещества
(газ, жидкость) или транспорта. Каждая
вершина
характеризуется интенсивностью потока
,
причем если
,
то вершина называется источником,
если
,
- стоком;
все
остальные вершины являются промежуточными.
Каждой дуге (
)
сети соответствует некоторая пропуская
способность
,
т.е. максимальный поток, который она
может пропустить за единицу времени. В
простейшем случае имеется единственный
источник
и единственный сток
.
Требуется
найти максимальную величину потока из
источника в сток. Поток в сети представляет
совокупность потоков {
}
по всем ее дугам (количество перемещаемой
субстанции в единицу времени).
Математическая
формулировка задачи: найти значения
,
максимизирующие поток в сети
при ограничениях:
;
Условие (16.1) определяет поток в сети, который равен количеству вещества, вытекающего из источника, или притекающего в сток. Условия (16.2) учитывают пропускные способности дуг; условия (16.3) предполагают, что поток не исчезает в процессе транспортировки (условия сохранения потока).
Покажем, как более сложные задачи с произвольным числом источников и стоков могут быть сведены к задачам с единственным источником и стоком.
Имеется
сеть с тремя источниками и двумя стоками
(Рис. 16.1). Из источников
продукт транспортируется на заводы
через промежуточные пункты. Чтобы найти
максимальный передаваемый поток,
достаточно расширить сеть, добавив один
фиктивный источник и один фиктивный
сток (фиктивные дуги обозначены штриховыми
линиями).
Действительно, величина потока, как в исходной, так и в расширенной сети определяется пропускными способностями дуг исходной сети. Таким образом, задача эквивалентна задаче с единственным источником и единственным стоком.
Рис. 16.1. Введение фиктивного источника и стока
Пример 1.
Имеется транспортная сеть (Рис. 16.2.), в которой транспортные потоки могут идти в обоих направлениях некоторых дуг. На рисунке обозначены пропускные способности в обоих направлениях: например из пункта 3 в пункт 6 может быть транспортирован поток интенсивностью 4 единицы, и такой же поток – из 6 в 3. Нули у окончаний некоторых дуг означают невозможность транспортировки в соответствующем направлении (например, из п. 4 в п. 2 поток перемещаться не может). Требуется определить максимальную пропускную способность сети .
Рис. 16.2. Транспортная сеть рассматриваемого примера.
Решение.
Задача может быть сформулирована следующим образом:
Максимизировать при ограничениях:
Решение
задачи дает
,
причем оптимальное решение является
неединственным, - данному максимальному
потоку может соответствовать различное
распределение потоков по дугам.