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




Лекция №9.

 

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

Предполагается, что сеть является симметрическим графом, т.е. если дуга (i,j) входит в сеть, то в неё входит и симметрическая дуга (j,i), хотя реально такой дуги может и не быть. Каждой дуге поставлено в соответствие число dij, называемое пропускной способностью дуги. Величина dij определяет максимальное количество продукции, которое может быть переведено по дуге (i,j) в единицу времени. Узел с номером Øимеет неограниченный запас продукции и называется источником, а узел с номером n имеет неограниченную потребность в эой продукции и называется стоком. В остальных узлах, которые называются промежуточными, запас продукции или потребность в ней равны нулю.

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

Данная постановка справедлива для смешанных и неориентированных графов, т.е. множество D может содержать дуги и рёбра, только дуги или только рёбра.

Для математической постановки задачи введём переменные xij - количество продукции, перевозимое по дуге (i,j). Эта велчина называется потоком по дуге (i,j). Тогда математическая модель задачи будет иметь вид:

 

(1)

(2)

(3)

 

Целевая функция (1) отражает величину потока по сети, которая должна быть максимизирована. Очевидно, поток на сети равен количеству продукции, вывозимой из источника или ввозимой в сток. Равенство (2) для промежуточных узлов записано из условия баланса: количество продукции, привозимого в узел, должно равняться количеству продукции, вывозимого из узла. Ограничения (3) очевидны. Модель (1)- (3) относиться к классу ЗЛП. Однако существует более эффективеый алгоритм решения этой модели. Это алгоритм Форда.

Важную роль в обосновании алгоритма Форда решения задачи о максимальном потоке играет понятие разреза сети.

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

Таким образом, разрезом сети называется совокупность всех дуг (i,j), которые исходят из узлов и заканчиваются в узлах . Каждый разрез сети характеризуется пропускной способностью d (R, ), которая численно равна сумме пропускных способностей дуг, образующих разрез, т.е.

d (R, )=

Очевидно, что любой путь из источника в сток содержит хотя бы одну дугу разреза (R, ). Поэтому если удалить все дуги какого-либо разреза, то все пути из источника в сток будут блокированы. Поскольку пропускная способность пути равна наименьшей из пропускных способностей дуг, входящих в этот путь, то величина потока V перемещаемого по всем возможным путям, соединяющим исток со стоком, не может превышать пропускной способности любого разреза сети, т.е. V≤ d (R, ). Следовательно, если удастся постоить такой поток, что его величина V * окажется равной пропускной способности некоторого разреза (R *, *), т.е. V *= d (R *, *), этот поток и будет максимальным, а (R *, *) - разрезом с минимальной пропускной способностью.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: