ТЕМА 17. СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ

Задача о кратчайшем маршруте

Задача о потоке минимальной стоимости

Задача о максимальном потоке

Основные понятия и определения

ТЕМА 16. ОПТИМИЗАЦИЯ СЕТЕВЫХ ПОТОКОВ

Составляющие транспортной сети: источник, сток, промежуточные вершины. Поток. Пропускная способность. Задача о максимальном потоке. Задача о потоке минимальной стоимости. Задача о кратчайшем маршруте.

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

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

Требуется найти максимальную величину потока из источника в сток. Поток в сети представляет совокупность потоков {} по всем ее дугам (количество перемещаемой субстанции в единицу времени).

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

при ограничениях:

;

Условие (16.1) определяет поток в сети, который равен количеству вещества, вытекающего из источника, или притекающего в сток. Условия (16.2) учитывают пропускные способности дуг; условия (16.3) предполагают, что поток не исчезает в процессе транспортировки (условия сохранения потока).

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

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

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

Рис. 16.1. Введение фиктивного источника и стока

Пример 1.

Имеется транспортная сеть (Рис. 16.2.), в которой транспортные потоки могут идти в обоих направлениях некоторых дуг. На рисунке обозначены пропускные способности в обоих направлениях: например из пункта 3 в пункт 6 может быть транспортирован поток интенсивностью 4 единицы, и такой же поток – из 6 в 3. Нули у окончаний некоторых дуг означают невозможность транспортировки в соответствующем направлении (например, из п. 4 в п. 2 поток перемещаться не может). Требуется определить максимальную пропускную способность сети .

Рис. 16.2. Транспортная сеть рассматриваемого примера.

Решение.

Задача может быть сформулирована следующим образом:

Максимизировать при ограничениях:

Решение задачи дает , причем оптимальное решение является неединственным, - данному максимальному потоку может соответствовать различное распределение потоков по дугам.

К задачам такого типа сводятся транспортная задача, задача о назначениях и ряд других задач.

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

Формулировка задачи:

Пример 2

Рассматривается сеть, представленная на Рис. 16.3.

Рис. 16.3. Транспортная сеть примера.

Цифры в скобках обозначают: в случае узла 1 (источника) – количество имеющегося продукта, в случае узлов 4 и 5 – их потребности в продукте. Первые числа у стрелок означают удельную стоимость транспортировки продукта (), а вторые – пропускную способность дуги (например, магистрали). Индекс * у дуг (2,3) и (4,5) означает, что их пропускные способности могут считаться неограниченными (например, они значительно превосходят имеющиеся в наличии запасы продукта).

Требуется определить распределение потоков, при котором суммарная стоимость доставки минимальна, а потребности узлов 4 и 5 удовлетворяются.

Решение.

Задача сводится к минимизации функции

при ограничениях

Решение задачи дает минимальное значение стоимости потока:

при следующих интенсивностях дуговых потоков

(1,2)	(2,4)	(3,5)
(1,3)	(2,5)	(5,3)
(2,3)	(3,4)	(4,5)

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

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

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