Курсовая работа на 2 курсе
Нам дают матрицу трафика, которая показывает, какое количество трафика проходит между каждой парой вершин. Также нам дают пару: отправитель сигнала и получатель сигнала, между которыми идет сигнал.
Наша задача заключается в том, чтобы построить граф по матрице трафика и найти оптимальный поток для данных вершин.
В идеальном мире между всеми узлами есть соединение, но у нас есть ограничение на количество приемников и передатчиков на узел. В нашем случае два. Это означает, что из каждой вершины исходит два ребра и в каждую входит два ребра. Количество приемников и передатчиков будем обозначать буквой T.
Основную проблему мы разделяем на две независимые: проблему подключения (CP) и проблему маршрутизации (RP).
Решение проблемы CP подразумевает назначение длины волн соединениям, причем таким образом, чтобы соответствовать любой базовой структуре матрицы трафика.
После получения схемы подключения (т.е. графа) необходимо оптимально распределить потоки по ссылкам логической схемы. Это приводит к решению проблемы маршрутизации (RP).
Проблема CP описывается более подробно в отчете в соответствующем отеделе.
Эту задачу можно решить с помощью линейного программирования, используя симплекс-метод.
Решение описано в Jupiter Notebook.
Проблема RP также более подробно описывается в отчете в соответствующем отеделе.
Главное, нам надо понять как оптимально распределить веса на ребра, чтобы значение максимального ребра было минимальным. В этом нам поможет оператор FD (более подробно описано в отчете).
С помощью этого оператора, мы можем оптимизировать веса двух потоков. Поэтому нам достаточно найти два различных пути между необходимыми узлами, а затем применить к ним оператор FD. Тогда мы сможем найти значение лямбда, при котором максимальное ребро будет иметь минимальное значение.
Именно это выполняет код на C++ представленный в папке Networks.