7. Максимальный поток на сети.

ЗАДАЧА. Найти величину максимального потока на транспортной сети.

ПОСТАНОВКА ЗАДАЧИ.

Рассмотрим транспортную задачу на сети (I,D,G) с заданными пропускными способностями дуг c(i,j).

Выделим две фиксированные вершины: s - источник и t – сток. Потоком на сети s→t назовем числовую функцию f, определенную на множестве дуг и удовлетворяющую следующим линейным уравнениям и неравенствам:

0≤ f(i,j) ≤c(i,j) для любых (i,j)

Требуется максимизировать переменную x

Разрезом L в сети, отделяющим вершины s t называется множество дуг

Любой путь s→t содержит по крайней мере одну дугу разреза.

КРИТЕРИЙ ОПТИМАЛЬНОСТИ: на реальной сети величина произвольного потока не превосходит пропускной способности разреза, а величина максимального потока равна минимальной пропускной способности разреза.

П

Пропускная способность исходящих дуг (Р,Т) и (М,К) превышает суммарную пропускную способность входящих в соответствующую вершину дуг. Для того, чтобы сеть стала реальной, заменим с(Р,Т)=4, с(М,К)=8.

Найдем и вычислим значение пропускных способностей всех разрезов. (К,В) – (Т,В) разрез с минимальной пропускной способностью =10. Следовательно, максимальный поток х=10

РИМЕР 3.12.

М 9 К

8 4 3

А

3 1 2 2 7 В

Р 5 Т

М 8 К

8 4 3

А

3 1 2 2 7 В

Р 4 Т

ПРИМЕР 3.13.

М 2 К

8 2 1

А 1 2 В

3 2 7

Р 1 Т

РЕШЕНИЕ:

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

Найдем и вычислим значение пропускных способностей всех разрезов. (К,В) – (Т,В) разрез с минимальной пропускной способностью =6. Следовательно, максимальный поток =6.

Сеть, имеющую несколько источников и стоков можно свести к сети с одним источником и стоком.

ПРИМЕР. Пусть имеется несколько источников S и стоков T (транспортная задача). Расширим сеть, добавив два узла s* , t* и все дуги (s*, S) , (T,t*). Доопределим функцию пропускной способности, положив

МЕТОД РАССТАНОВКИ ПОМЕТОК.

1. Начальный поток f(i,j) = 0. Припишем вершинам данной сети пометки, которые будут иметь вид (i+, ε) или (i^-, ε). Источник пометим (-, ∞), т.е. ε(s)= ∞.

2. Для любой помеченной вершины i выберем все непомеченные вершины j для которых f(i,j)<c(i,j) и припишем им пометки (i+, ε(j)), где ε(j)=min[ε(i), f(i,j)]. Тем вершинам, которые останутся непомеченными, но для которых f(i,j)>0, приписываем пометку (i-, ε(j)).

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

3. Пусть сток имеет пометку (j+, ε(t)), тогда f(j,t) заменяем на f(j,t)+ε(t). Если же сток имеет пометку (j-, ε(t)), то f(j,t) заменяем на f(j,t)-ε(t). Переходим к вершине j. Если j имеет пометку (i+, ε(j)), то заменяем f(i,j) на f(i,j)+ε(t), а если ­(i-, ε(j)), f(j,i) заменяем на f(j,i)-ε(t). Переходим к вершине i. Эту операцию повторяем до тех пор, пока не достигнем источника s . Изменение потока прекращается, стираются все пометки и переходим к п.2

ПРИМЕР 3.14.

М 4 К

8 4 3

А

3 1 2 4 7 В

Р 5 Т

1 шаг	А → (-, ∞) М → (А+,8) Р → (А+,3) К → (Р+,3) Т → (Р+,3) В → (Т+,3)	f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(А,М)=0 f(М,Р)=0 f(М,К)=0 f(М,Т)=0 f(К,Т)=0 f(К,В)=0
2 шаг	А → (-, ∞) М → (А+,8) Р → (М+,1) К → (М+,4) Т → (М+,2)	f(К,В)=3 f(М,К)=3 f(А,М)=3 f(Т,В)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Т)=0 f(М,Р)=0 f(К,Т)=0
3 шаг	А → (-, ∞) М → (А+,5) Р → (М+,1) К → (М+,1) Т → (М+,2) В → (Т+,2)	f(Т,В)=5 f(М,Т)=2 f(А,М)=5 f(К,В)=3 f(М,К)=3 f(Р,Т)=3 f(А,Р)=3 f(Р,К)=0 f(М,Р)=0 f(К,Т)=0
4 шаг	А → (-, ∞) М → (А+,3) Р → (М+,1) К → (М+,1) Т → (Р+,1) В → (Т+,1)	f(А,М)=6 f(Т,В)=6 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(М,К)=3 f(А,Р)=3 f(Р,К)=0 f(К,Т)=0
5 шаг	А → (-, ∞) М → (А+,2) Р → (М-,1) К → (М+,1) Т → (К+,1) В → (Т+,1)	f(А,М)=7 f(М,К)=4 f(К,Т)=1 f(Т,В)=7 f(Р,Т)=4 f(М,Р)=1 f(М,Т)=2 f(К,В)=3 f(А,Р)=3 f(Р,К)=0
6 шаг	А → (-, ∞) М → (А+,1)	Поток оптимален f=10 Минимальный разрез:М→Т-М→Р-М→К

ЗАДАЧА. Найти наибольший поток на сети

АЛГОРИТМ

Обозначим вершину s= х₀. Все остальные – х_i.

1 этап.

1. Выбираем любой путь, все дуги которого не насыщены.

2. Увеличиваем величину потока по этому пути на единицу до тех пор, пока в нем не будет насыщенной дуги.

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

2 этап.

1. Помечаем х₀ индексом 0.

2. Если х_i уже помеченная вершина, то помечаем (+i) все непомеченные вершины, в которые идут не насыщенные дуги из х_i, и индексом (–i) все непомеченные вершины, из которых идут дуги с ненулевым потоком в х_i.

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

4. Когда вершину t невозможно пометить процесс прекращается и полученный поток является наибольшим потоком сети.

ПРИМЕЧАНИЕ. Перейти к 2 этапу можно, не завершая первого этапа (см. пример 3.16).

ПРИМЕР 3.15.

9

8 4 3

s 1 2 t

3 2 7

5

РЕШЕНИЕ:

На заданной транспортной сети найден полный поток. Насыщенные дуги выделены

Пометим сеть и увеличим в ней поток согласно алгоритму. Получим

В этой сети также можно пометить конечную вершину, причем результат разметки окажется тем же самым. Изменив поток, получим сеть, в которой конечную вершину пометить невозможно, поэтому поток в ней является наибольшим и равен 10.

ПРИМЕР 3.16.

2

8 2 1

s 1 2 t

3 2 7

1

РЕШЕНИЕ.

На заданной транспортной сети найден неполный поток

Пометим сеть и увеличим в ней поток согласно алгоритму. Получим

В этой сети также можно пометить конечную вершину, причем результат разметки окажется тем же самым. Изменив поток, получим сеть, в которой конечную вершину пометить невозможно, поэтому поток в ней является наибольшим и равен 6.