Задачи, связанные с теорией потоков в сетях представляют собой одни из базовых проблем в исследовании операций, а также в инженерном деле. Существуют многочисленные практические приложения теории потоков.
Цель работы состоит в разработке подсистемы анализа вычислительных сетей на основе теории потоков.
Задачи данной работы:
– проведение изучение основных понятий и алгоритмов, применяемых в теории потоков;
– определение наиболее эффективного алгоритма и формирование структуры программы;
– разработка подсистемы анализа вычислительных сетей.
Алгоритм Форда – Фалкерсона позволяет находить максимальный поток, идущий от источника к приемнику при определенной конфигурации сети. Если конфигурация изменяется, то тогда возникает новый поток. Тогда при создании сети может быть предусмотрено, что в ней будет реализовываться определенные потоки, соответствующие какой-то конфигурации сети среди множества возможных потоков, которые идут от источника к приемнику. Потоки могут отличаться не только тем, как соединяются элементы сети, но какое число этих элементов. При определении оптимальной конфигурации необходимо использовать критерием максимума суммарного трафика или, максимума среднего потока.
При реализации алгоритма поиска максимального потока была разработана программа в среде Delphi. Эта программа функционирует в режиме диалога с пользователем и она создана на основе модульного принципа.
В программе задается максимальное число вершин сети, которое равно 40.
Формируются процедуры обработки данных. В них используются следующие данные – матрица узлов сети, коодинаты узлов сети, номера элементов.
Программа была написана исходя из модульно–иерархической структуры. Связь модулей происходит на основе параметров – данных и общего блока данных.
Такая связь получается тогда, когда все необходимые данные модуль принимает и передает как параметры вызова, эти данные представляют собой простые переменные.
Для ввода сети необходимо нажать кнопку 1. Происходит фиксация кнопки. Можно приступать к вводу. Размещение узлов производится на основе щелчка левой кнопки мыши на поле построения. Для того, чтобы построить ребро требуется указать правой кнопкой мыши начало ребра и конец ребра. Чтобы завершить ввод сети, требуется вновь нажать кнопку 1. Комбинация Shift + левая кнопка мыши удаляет узел; Ctrl + левая кнопка мыши позволяет переместить узел в другую точку.
Для того, чтобы провести определение максимальной пропускной способности сети, необходимо нажать кнопку 2. Используется алгоритм Форда- Фалкерсона.
Введённую сеть можно сохранить в файле на диске – пункт меню Файл – Сохранить.