Файл: М.А. Тынкевич Потоки в сетях и транспортная задача по критерию времени.pdf

1

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

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

i и j, сопоставлено число dij > 0 , называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество вещества (воды, газа, самолетов, вагонов и т. п.), которое может проходить по соответствующей дуге в единицу времени.

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

Для стационарных потоков, параметры которых в любой момент времени неизменны, естественно требовать равенства потоков на входе и на выходе :

∑ X 0 j = ∑ X i n = Z .

j i

Рассмотрим задачу максимизации величины потока в сети Z при указанных условиях .

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

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

В случае т. н. (0, n) - плоских сетей, т. е. сетей, которые можно изобразить на плоскости по одну сторону от ли-

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

Берем самый "верхний" (по принципу левостороннего движения) путь от вершины 0 к вершине 7: [0 - 1 - 5 - 7] и отыскиваем минимальную пропускную способность составляющих его дуг, равную 5 , и уменьшаем пропускные

2

способности дуг на эту величину. Очередной "верхний" путь [0 - 1 - 5

- 4 - 7] имеет пропускную способность 5.

Очередной путь [0 - 1 - 4 - 7] имеет пропускную способность 10. Последующий поиск обнаруживает потоки по путям [0 - 1 - 4 - 6 - 7] c величиной потока 5 и [0 - 1 - 2 - 3 - 6 - 7] c величиной 5 . В итоге сеть ока-

залась разорванной и максимальный поток равен 30 .

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

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

берем симметричные значения элементов матрицы di j=dj i ).

Основные шаги алгоритма состоят в поиске некоторого пути и коррекции потока на этом пути.

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

ку, ищем в ней непомеченный столбец с d i j > 0 и сопоставляем ему метки

j = i , Vj = min (Vj, di j).

Метки столбцов переносим на строки и этот процесс продолжаем до тех

й вершине, и уменьшаем пропускные способности дуг пути (элементы мат-

рицы) на Vn и увеличиваем симметричные элементы на эту же величину. Такая процедура продолжается до тех пор, пока отмечание n - й вершины

не станет невозможным.

Максимальный поток может быть найден суммированием найденных промежуточных потоков или вычитанием из исходной матрицы D0 получаемой после вышеприведенной корректуры матрицы пропускных способностей

X = max (D0 - Dk , 0) .

Обратимся к рассмотренному выше примеру.

Из нулевой строки отмечаем вершины (строки-столбцы) 1 , 2 и 3 индексами =0 и V, равными 30 , 10 и 10.

Из помеченной строки 1 метим вершины 4 и 5 индексами =1 и

V4 = min( 30, 15 ) = 15 , V5 = min( 30,10 ) = 10 .

5

требителей с пропускными способностями bj (j=1…n). В результате получаем сеть с одним входом и одним выходом, в которой осуществляется переброска R единиц груза от псевдовхода до псевдовыхода.

Выбираем минимальное из значений tij и строим т.н. допустимую сеть,

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

Единственный недостаток такого решения в том, что придется оперировать с матрицами размерности m+n+2, в которой всего mn+m+n ненулевых элементов. Поэтому рассмотрим компактную схему поиска максимального потока, позволяющую работать с матрицами размерности m× n.

Пусть найден некоторый поток X в допустимой сети S, удовлетворяющий естественным условиям:

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

Для строк i, в которых