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

Пусть задан ориентированный граф G =á E, V, H ñ, в котором направление каждой дуги v Î V означает направление движения потока (например, поток автомобилей), пропускная способность каждой дуги равна d_v. На множестве вершин E выделены две вершины н и к. Вершина н является источником потока, к – стоком. Требуется определить максимальный поток, который может быть пропущен из вершины н в к.

Обозначим через x_v величину потока, движущегося по дуге v. Очевидно, что

0 £ xv £ dv, vÎV

(7.13)

В каждой вершине iÎE\ { н, к } объем потока входящего равен объему потока выходящего, т.е. справедливо равенство

или
	(7.14)

Соответственно для вершин н и к выполняется

	(7.15)
	(7.16)

Величина Q является величиной потока, который выходит из вершины н и входит в вершину к.

Задача. Определить

Q ® max

(77.5)

при ограничениях (7.13) – (7.16).

Величины (Q, x_v, vÎV) удовлетворяющие ограничениям (7.13) – (7.16) будем называть потоком в сети, и если они максимизируют величину Q, то максимальным потоком. Нетрудно видеть, что значения Q =0, x_v =0, v Î V, являются потоком в сети. Задача (7.13) – (7.16) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.

Разобьем множество вершины E на две непересекающиеся части E ₁ и E ₂ таким образом, чтобы н Î E ₁, к Î E ₂. Разрезом R (E ₁, E ₂), разделяющим н и к будем называть множество R (E ₁, E ₂)Ì V такое, что для каждой дуги v Î R (E ₁, E ₂) либо h ₁(v)Î E ₁и h ₂(v)Î E ₂, либо h ₁(v)Î E ₂и h ₂(v)Î E ₁. Так на следующем рисунке множество E ₁={1,4,7}, эти вершины имеют темную заливку. E ₂={2,3,5,6,8,9}. Разрезом R (E ₁, E ₂) являются дуги, через которые прошла пунктирная линия.

 

Разобьем множество R (E 1, E 2) на две частиследующим образом:

R⁺ (E ₁, E ₂)={ v Î R (E ₁, E ₂) | h ₁(v)Î E ₁и h ₂(v)Î E ₂}

R^– (E ₁, E ₂)={ v Î R (E ₁, E ₂) | h ₂(v)Î E ₁и h ₁(v)Î E ₂}

Элементы множества R⁺ (E ₁, E ₂) будем называть прямыми дугами, они ведут из множества E ₁, в E ₂. Элементы множества R^– (E ₁, E ₂) – обратными дугами, они ведут из множества E ₂, в E ₁. Потоком через разрез будем называть величину

.

Пропускной способностью разреза будем называть величину

.

Очевидно, что 0£ X (E ₁, E ₂)£ D (E ₁, E ₂).

Справедлива следующая теорема.

Теорема 1. (О максимальном потоке и минимальном разрезе).

В любой сети величина максимального потока Q из источника н в сток к равна минимальной пропускной способности D (E ₁, E ₂) среди всех разрезов R (E ₁, E ₂), разделяющих вершины н и к.

Разрез , на котором Q = , будем называть ограничивающим. На ограничивающем разрезе выполняется

Пусть (Q, x_v, v Î V) – некоторый поток в сети, и последовательность н = i ₀, v ₁, i ₁, v ₂, i ₂, ..., v_K, i_K = к, является цепью, соединяющих вершины н и к. Зададим на этой цепи направление движения от вершины н к к. Дуга v_j из этой цепи называется прямой, если ее направление совпадает с направлением движения от н к к, и обратной в противном случае. Эту цепь будем называть цепью увеличения потока, если для прямых дуг v цепи (d_v– x_v)>0 и для обратных x_v> 0. По этой цепи можно пропустить дополнительный поток q из н к к величиной q =min(q ₁, q ₂), где q ₁=min(d_v – x_v), минимум берется по всем прямым дугам цепи, q ₂=min(x_v), минимум берется по всем обратным дугам цепи.

Теорема 2. Поток (Q, x_v, vÎV), максимальный тогда и только тогда, когда не существует пути увеличения потока.

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

Каждой вершине i припишем пометку P_i =[ g_i, v_i, q ], где g_i – величина дополнительного потока, поступившего в вершину i, v_i – дуга, по которой поступил поток, q – знак «+», если поток поступил по дуге v_i , направленной в i (по прямой дуге; q – знак «–», если поток поступил по дуге v_i , направленной от i (по обратной дуге),

Будем говорить, что вершина i

1. Не помечена, если до нее не дошел дополнительный поток. Эта пометка будет иметь вид P_i =[0,–, q ],

2. Помечена, но не просмотрена, если до нее поток дошел, но не пропущен дальше, пометка будет иметь вид P_i =[ g_i, v_i, q ], где g_i >0.

3. Помечена и просмотрена, если до нее поток дошел и пропущен дальше, пометка будет иметь вид .

Алгоритм.

П.0. Для всех v Î V полагаем x_v =0, полагаем Q= 0.

П.1. Все вершины делаем непомеченными. Вершину н делаем помеченной, но не просмотренной с пометкой P_н =[¥,–,–]. Это означает, что в эту вершину поступает поток неограниченного объема.

П.2. Ищем помеченную, но не просмотренную вершину. Если такой нет, то найденный поток Q, x_v, v Î V, максимальный и алгоритм заканчивает работу. Если такая вершина нашлась, i – ее номер, то переходим к П.3.

П.3 (просмотр вершины i).

a) для всех выполнить:

положить j = h ₂(v),

если вершина j не помечена и (d_v – x_v)>0, то пометить ее с пометкой P_j =[ q, v,+], где q =min(q_i, (d_v – x_v)), если j = к, то перерейти к П4;

b) для всех выполнить:

положить j = h ₁(v),

если вершина j не помечена и x_v >0, то пометить ее с пометкой P_j =[ q, v,–], где q =min(q_i, x_v), если j = к, то перерейти к П4;

c) пометить вершину i как просмотренную и перейти к П.2.

П.4 (пропуск дополнительного потока).

d) Положить j = к, q = g_к;

e) Положить v = v_j,

если q =«+», то выполнить: {положить x_v = x_v + q, i = h ₁(v), если i = н, то перейти к П.1, иначе положить j=i и перейти к e) }

если q =«–», то выполнить: {положить x_v = x_v – q, i = h ₂(v), если i = н, то перейти к П.1, иначе положить j=i и перейти к e) }

 

В результате выполнения этого алгоритма будет получен поток (Q, x_v, vÎV). Для поиска разреза с минимальной пропускной способностью следует поступить так. На последнем этапе работы алгоритма в П.2 часть вершин будет помечена и просмотрена, эти вершины включим в множество . Разрез будет искомым.

Пример. Для графа, приведенного на следующем рисунке, найти максимальный поток, который будет пропущен из 1–ой вершины в 6–ю. Величины пропускных способностей указаны около дуг.

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

Для этого случая Q =4, потоки по дугам приведены в таблице

Дуга	v 1	v 2	v 3	v 4	v 5	v 6	v 7	v 8	v 9	v 10
поток

 

Шаг 1.

вершина
пометка	[¥,–, q ]	[0,–, q ]	[0,–, q ]	[0,–, q ]	[0,–, q ]	[0,–, q ]

Шаг 2. Просматриваем вершину 1. Выходящие дуги v ₁, v ₂, v ₃, но только для v ₂ (d_v–x_v)>0, поэтом вершина 4 получает пометку [2, v ₂,+]. Входящих дуг нет, поэтому дополнительно помеченных вершин нет. Вершина 1 получается помеченной и просмотренной.

вершина
пометка	[¥,–, q ]	[0,–, q ]	[0,–, q ]	[2, v 2,+]	[0,–, q ]	[0,–, q ]

Шаг 3. Помеченная не просмотреная вершина 4, из нее вершина 5 получает пометку
[2, v ₈,+], и вершина 2 получает пометку [1, v ₄, –]. Вершина 4 получается помеченной и просмотренной.

вершина
пометка	[¥,–, q ]	[1, v 4,-]	[0,–, q ]	[2, v 2,+]	[2, v 8,+]	[0,–, q ]

Шаг 4. Просматриваем вершину 2. Из нее помечается вершина 6, она получает пометку [1, v ₆,+].

вершина
пометка	[¥,–, q ]	[1, v 4,-]	[0,–, q ]	[2, v 2,+]	[2, v 8,+]	[1, v 6,+]

Эта вершина концевая, поэтому дополнительный поток, который придет в эту вершину q =1. Переходим к восстановлению цепи, по которой может быть пропущен поток и изменению потоков.

Шаг 5 (начало восстановления цепи пропуска дополнительного потока).

Полагаем Q = Q + q =4+1=5.

В вершину 6 дополнительный поток поступил по дуге v ₆, направление дуги прямое (смотри пометку этой вершины), поэтому полагаем . Поток поступил из вершины j = h ₁(v ₆)=2, переходим к анализу этой вершины.

Шаг 6. В вершину 2 дополнительный поток поступил по дуге v ₄, направление дуги обратное (смотри пометку вершины 2), поэтому полагаем . Поток поступил из вершины j = h ₂(v ₄)=4, переходим к анализу этой вершины.

Шаг 7. В вершину 4 дополнительный поток поступил по дуге v ₂, направление дуги прямое, поэтому полагаем . Поток поступил из вершины j = h ₁(v ₂)=1 – начальная вершина, цепь восстановления потока получена, изменения значений потоков вносим в таблицу

Дуга	v 1	v 2	v 3	v 4	v 5	v 6	v 7	v 8	v 9	v 10
поток

 

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

Шаг 1.

вершина
пометка	[¥,–, q ]	[0,–, q ]	[0,–, q ]	[0,–, q ]	[0,–, q ]	[0,–, q ]

Шаг 2. Просматривая вершину 1, получим

вершина
пометка	[¥,–, q ]	[0,–, q ]	[0,–, q ]	[1, v 2, + ]	[0,–, q ]	[0,–, q ]

Шаг 3. Просматривая вершину 4 получим

вершина
пометка	[¥,–, q ]	[0,–, q ]	[0,–, q ]	[1, v 2, + ]	[1, v 8,+]	[0,–, q ]

Шаг 4. Просматривая вершину 5 получим

вершина
пометка	[¥,–, q ]	[0,–, q ]	[1, v 7,–]	[1, v 2, + ]	[1, v 8,+]	[0,–, q ]

Шаг 4. Просматривая вершину 3 получим

вершина
пометка	[¥,–, q ]	[0,–, q ]	[1, v 7,–]	[1, v 2, + ]	[1, v 8,+]	[0,–, q ]

Все вершины, которые были помечены, просмотрены, однако вершина 6 не достигнута. Получен максимальный поток.

Ответ: Q=5, значения потоков по дугам приведены в таблице:

Дуга	v 1	v 2	v 3	v 4	v 5	v 6	v 7	v 8	v 9	v 10
поток

 

Покажем, как можно получить разрез, на котором максимальный поток совпадает с его пропускной способностью. Вершины, просмотренные на шаге 4 образуют множество E ₁={1,3,4,5}, E ₂= E\E ₁={2,6}. Выделим на графе вершины из E ₁={1,3,4,5} толщиной окружности и заливкой

Дуги между выделенными и невыдененными вершинами образуют искомый разрез. На графе они также выделены, и по ним проведена пунктирная линия. Из рисунка видно, что дуга v ₄ разреза обратная, остальные дуги этого разреза прямые. Просчитаем пропускную способность этого разреза и поток по нему . Эти величины совпадают, на прямых дугах поток совпадает с ее пропускной способностью, на обратных дугах поток равен 0.

Рассчитаем пропускную способность некоторого произвольного разреза и поток по нему, например, по разрезу, изображенному на следующем рисунке

D ({1,2,3},{4,5,6}=

X ({1,2,3},{4,5,6}= ,

0£ X ({1,2,3},{4,5,6}£ D ({1,2,3},{4,5,6}. Можно показать (это следует из условия сохранения потока в вершинах), что величина потока не зависит от разреза.

Самостоятельная работа 17.

Для графа, имеющего вид

найти:

a) максимальный поток, который может быть пропущен и вершины 1 в вершину 9,

b) разрез, на котором максимальный поток равен его пропускной способности,

c) найти разрез, на котором максимальный поток меньше его пропускной способности.

 

Варианты заданий приведены в следующей таблице:

Номер

v 1

v 2

v 3

v 4

v 5

v 6

v 7

v 8

v 9

v 10

v 11

v 12

v 13

v 14

v 15

v 16

v 17

 

 

 

 

Литература.

1. Моисеев Н.Н. Математические задачи системного анализа.–М., Наука, 1981, 487 с.

2. Гермейер Ю.Б. Введение в теорию исследования операций. – М., Наука, 1971.

3. Зайченко Ю.П. Исследование операций. – Киев, Вiща школа,1975.

4. Коваленко А.Г. Элементы выпуклого векторного программирования. Учебное пособие. – Самара, 1990, 83 стр.

5. Коваленко А.Г., Власова И.А. Цветков Ю.Д. – Лабораторный практикум по методам оптимизации. – Куйбышев, СамГУ, 1991, 59 стр.

6. Подиновский В.В., Ногин В.Д. Парето – оптимальные решения. М., Наука, 1971.

7. Дубов Ю.А. и др. Многокритериальные модели формирования и выбора вариантов систем. М., Наука, 1986.

8. Романовский И.В. Алгоритмы решения экстремальных задач. М. Наука, 1977.

9. Коваленко А.Г. Алгоритмы решения некоторых задач оптимизации многошаговых процессов. Куйбышев, 1985, 72 стр.

10.Тетерев А.Г. Динамическое программирование в курсе исследования операций. – Куйбышев, 1983.

11. Исследование операций под ред. Дж.Моудера, С.Элмаграби. М., "Мир",1981,т.1,2.

12. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М. Наука М., Наука, 1971.

14. Хедли Дж. Нелинейное и динамическое программирование. – М., Мир, 1967.

15. Ху Т. Целочисленное программирование и потоки в сетях. М., Мир, 1971.

16. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М., Наука, 1975.

17. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М., Мир, 1965.

18. Акоф Р., Сасиени М. Основы исследования операций. М. Мир. 1971.

19. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М., «Наука», 1970.

20. Подиновский В.В., Ногин В.Д. Парето–оптимальные решения многокритериальных задач. М. Наука, 1982, 256 с.

24.Коваленко А.Г., Власова И.А., Федечев А.Ф. Лабораторный практикум по методам оптимизации. Изд. «Самарский университет», Самара, 1998 г.

25.Коваленко А.Г., Власова И.А., Шведова И.А. Лабораторный практикум по методам исследования операций. Изд. «Самарский университет», Самара, 1997 г.

26. Юдин Д.Б., Гольштейн E. Г. Задачи линейного программирования транспортного типа. М. «Наука» 1969.

 

27. Бусыгин, В. П. Желободько Е. В., Коровин С. Г., Цыплаков А. А. Микроэкономический анализ несовершенных рынков: Ч.1.– Новосибирск: Новосибирский государственный университет, 2000. – 264 с.

28. Хачатуров, В. Р. Математические методы регионального программирования. – М.: Наука, 1989. – 304 с.

 

[1] В настоящей главе приведены основные теоремы векторного выпуклого программирования и многокритериальной задачи без доказательств, и авторы предлагают читателю самостоятельно доказать предложенные теоремы. Доказательства этих теорем можно найти в работах Коваленко А.Г. Элементы выпуклого векторного программирования [4] и Карманова В.Г. Математическое программирование [26].