Решение задач на тему: Задача о максимальном потоке. Структура исходных данных задачи и результатов

Введение

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

Количество вещества, проходящего по дуге от i до j, будем называть потоком по дуге (i, j) и обозначать через Xij(0≤Xij≤dij). Если учесть, что все вещество, вошедшее в промежуточный пункт сети, должно полностью выйти из него, получаем ΣiXij=ΣkXjk, j=1,..n;

Из естественного требования равенства потоков на входе и на выходе имеем ΣiX0j=ΣiXjn=Z.

Величину Z называем величиной потока в сети и ставим задачу максимизации Z указанных выше условиях. Решение задачи можно осуществлять методами линейного программирования, но едва ли эта возможность осуществима для сколь-нибудь реальной сети. Остановимся на некоторых фундаментальных понятиях. Разобьем множество пунктов (вершин) сети на два подмножества U и V. Совокупность дуг, ведущих непосредственно из вершин множества U в вершины множества V называют разрезом сети, а число А(U, V)=Σdij называют пропускной способностью этого разреза. Очевидно, что поток в сети не превышает величины пропускной способности любого ее разреза и равен пропускной способности минимального разреза. Таким образом, поиск максимального потока сводится к поиску пропускной способности минимального разреза.

Оглавление

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

- Структура исходных данных задачи и результатов

- Алгоритм нахождения максимального потока в сети

- Описание пользовательского интерфейса программы

- Тестирование