ЗАДАЧА ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ПОТОКА

 

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

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

Мощность потока может зависеть от его направления.

Это условное обозначение означает, что мощность потока от узла 1 к узлу 2 равна 6, а мощность потока от узла 2 к узлу 1 равна 0, т.е. это «улица с односторонним движением».

Условное обозначение

означает, что мощность потока в каждом направлении равна 2.

Алгоритм:

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

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

Шаг 2. Найти наименьшее значение мощности дуги P_f на выбранном пути шага 1. Увеличить поток через сеть на величину P_f.

Шаг 3. На пути из шага 1 сократить на P_f мощности потоков на всех дугах в направлении потока и увеличить на P_f мощности потоков на всех дугах, в обратном направлении. Перейти к шагу 1.

 

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

1. Каков максимальный поток через эту систему (тыс. автомашин в час)?

2. Сколько автомашин должно проехать по дороге 5-6, чтобы обеспечить максимальный поток?

 

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

Итерация 1. Выберем путь 1-3-6.

P_f = min{6, 2}=2. Поэтому мощности потоков на пути 1-3-6 в направлении потока (а именно, 6 и 2) уменьшаем на величину P_f =2, а мощности потоков в обратном направлении на пути 1-3-6 (0 и 0) увеличиваем на P_f =2. Общий поток станет 0+2=2.

Получим:

Итерация 2. Выберем путь 1-4-6.

P_f = min{3, 3}=3. Все потоки на пути 1-4-6 в направлении общего потока (3 и 3) уменьшаем на P_f =3, а все потоки на этом пути в обратном направлении (0 и 0) увеличиваем на P_f =3. Общий поток увеличиваем на P_f =3 (2+3=5).

Получим:

Итерация 3. Выбираем путь 1-2-5-6.

P_f = min{2, 4, 6}=2. Все потоки на пути 1-2-5-6 в направлении общего потока (2, 4, 6) уменьшаем на P_f =2, а все потоки на этом пути в обратном направлении (0, 4, 0) увеличиваем на P_f =2. Общий поток увеличиваем на P_f =2 (5+2=7).

Получим:

Итерация 4. Выбираем путь 1-3-4-5-6.

P_f = min{4, 3, 1, 4}=1. Все потоки на пути 1-3-4-5-6 в направлении общего потока (4, 3, 1, 4) уменьшаем на P_f =1, а все потоки на этом пути в обратном направлении (2, 3, 1, 2) увеличиваем на P_f =1. Общий поток увеличиваем на P_f =1 (7+1=8).

Получим:

Итерация 5. Выбираем путь 1-3-4-2-5-6.

P_f = min{3, 2, 1, 2, 3}=1. Все потоки на пути 1-3-4-2-5-6 в направлении общего потока (3, 2, 1, 2, 3) уменьшаем на P_f =1, а все потоки на этом пути в обратном направлении (3, 4, 1, 6, 3) увеличиваем на P_f =1. Общий поток увеличиваем на P_f =1 (8+1=9).

Получим:

Больше не существует путей из узла 1 в узел 6 с мощностью, превышающей нуль на всем пути. Следовательно, 9 тыс. – это максимальный поток через сеть.

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

- дуга 1-2: первоначальная мощность равна 2, конечная – 0, следовательно, в направлении от узла 1 к узлу 2 поток имеет мощность 2-0=2;

- дуга 1-3: 6-2=4; – дуга 4-2: 1-0=1;

- дуга 1-4: 3-0=3; – дуга 4-5: 1-0=1;

- дуга 2-5: 4-1=3; – дуга 4-6: 3-0=3;

- дуга 3-4: 3-1=2; – дуга 5-6: 6-2=4.

- дуга 3-6: 2-0=2;