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

Рассмотрим транспортную сеть, в которой выделены пункты 0 (вход, источник) и n (выход, сток) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число dij> 0, называемое пропускной способностьюдуги. Величина пропускной способности характеризует максимальное допустимое количество вещества (воды, газа, самолетов, вагонов и), которое может проходить по соответствующей дуге в единицу времени. Количество вещества, проходящего по дуге от i до j, будем называть потоком по дуге (i, j) и обозначать через Xij. Если учесть, что все вещество, вошедшее в промежуточный пункт сети, должно полностью выйти из него, получаем Из естественного требования равенства потоков на входе и на выходе имеем Величину Z называем величиной потока в сети и ставим задачу максимизации Z при условиях (1)-(3). Решение задачи можно осуществлять методами линейного программирования. Остановимся на некоторых фундаментальных понятиях. Разобьем множество пунктов (вершин) сети на два подмножества U и V так, что вход 0 U и выход n V. Совокупность дуг, ведущих непосредственно из вершин множества U в вершины множества V называют разрезом сети, а число называют пропускной способностью этого разреза. Поток в сети не превышает величины пропускной способности любого ее разреза и равен пропускной способности минимального разреза. Поиск максимального потока сводится к поиску пропускной способности минимального разреза.