Введение 6
1 Методы решения многокритериальных задач оптимизации сети передачи
данных 8
1.1 Многокритериальная оптимизация 8
1.2 Подходы к решению 9
1.2.1 Свертывание критериев 9
1.2.2 Концепция Парето 10
1.3 Метод ветвей и границ в решении задач оптимизации 11
1.4 Эвристические алгоритмы 12
1.5 Задачи транспортного типа 13
1.6 Моделирование сети передачи данных. Методы оптимизации 14
1.7 Выводы по главе 1 15
2 Математическая модель, задача и алгоритмы оптимизации сети передачи
данных 15
2.1 Структура сети передачи данных банка 15
2.2 Математическая модель сети передачи данных 16
2.3 Задача оптимизации сети передачи данных 17
2.4 Определение множества Парето-оптимальных решений задачи
оптимизации сети передачи данных путем полного перебора 19
2.5 Определение множества Парето-оптимальных решений задачи
оптимизации сети передачи данных методом ветвей и границ 19
2.5.1 Пример решения задачи методом ветвей и границ 23
2.6 Выводы по главе 2 27
3 Поиск субоптимального множества решений задачи оптимизации сети
передачи данных 27
3.1 Субоптимальное множество 28
3.2 Оценка отклонения субоптимального множества решений от множества
Парето 28
3.2.1 Метод подсчета решений 29
3.2.2 Метод оценки точности приближения субоптимального множества
решений к Парето-оптимальному 30
3.3 Поиск субоптимального множества решений с применением имитации
отжига 31
3.3.1 Начальный вектор решений. Получение нового решения 32
3.3.2 Снижение температуры. Вычисление энергии 32
3.3.3 Критерии допуска и критерий останова 33
3.3.4 Дополнительные эвристики 34
3.3.5 Оценка вычислительной сложности 34
3.4 Комбинированный метод 34
3.5 Вычислительный эксперимент 35
4 Программный комплекс решения задачи проектирования и оптимизации сети
передачи данных на примере Сибирского банка 39
4.1 Назначения и возможности программного комплексаЕггог! Bookmark not defined.
4.3 Системные требования 39
4.4 Описание графического пользовательского интерфейса 40
4.4.1 Главное окно программы 40
4.4.2 Главное меню программы 42
4.5 Окно ввода данных о канале связи 44
4.6 Типовой сценарий работы с программным комплексом 45
4.7 Рекомендации по использованию программного комплекса 46
Список использованных источников 51
Приложение
С каждым годом объемы передаваемой информации посредством сети Интернет стремительно растут. Соответственно возрастает нагрузка на сети передачи данных (далее СПД), что служит толчком для усовершенствования и оптимизации.
Интернет-провайдеры (далее провайдеры) стремятся быть
конкурентоспособными, поэтому качество предоставляемых услуг улучшается, изменяется стоимость аренды каналов, появляются новые каналы связи и т.д.
Иногда изменения в тарифных планах существенны и выгодны для пользователей, но проанализировать и решить, стоит ли воспользоваться теми или иными услугами довольно проблематично.
Рассмотрим Сибирский банк - филиал ПАО Сбербанка России. Он обслуживает клиентов на территории Сибирского федерального округа.
С целью повышения качества сервиса и эффективности обслуживания банк активно развивает как существующие технологии предоставления услуг, так и внедряет новые. Например, услуга приема платежей у населения реализована и в банкоматах, и в информационно-платежных терминалах Банка. Связь между банкоматами, терминалами, отделениями и центром обработки данных обеспечивается с помощью арендованных у провайдера каналов связи.
Проанализировав деятельность отдела систем связи и телекоммуникаций было выявлено, что существует нехватка программного обеспечения, готового анализировать предложения провайдеров и предоставлять альтернативные решения при определении плана аренды дополнительных каналов для улучшения технических характеристик СПД.
Банк заинтересован в получении качественных услуг от провайдеров за минимально возможную стоимость. В этом случае необходимо учитывать два различных критерия. Таким образом, можно определить задачу
бикритериальной оптимизации.
Объектом исследования является сеть передачи данных и методы её оптимизации.
Предметом исследования является математическая модель и алгоритмы оптимизации СПД Сибирского банка.
Целью работы является разработка и реализация алгоритма, способного находить с приемлемой точностью решение задачи многокритериальной оптимизации сети передачи данных Сибирского банка при большой размерности.
Для достижения поставленной цели решались следующие задачи:
- моделирование существующей СПД Сибирского банка;
- определение основных критериев оптимальности, постановка задачи бикритериальной оптимизации сети;
- анализ существующих методов решения многокритериальных задач и выбор наиболее подходящих для решения рассматриваемой практической задачи;
- программная реализация выбранных методов;
- разработка и реализация программы с графическим интерфейсом для нужд Сибирского банка.
В ходе работы были выполнены следующие задачи:
- построена модель сети передачи данных Сибирского банка;
- поставлена задача бикритериальной оптимизации сети;
- проведен анализ существующих методов решения задач МКО сети передачи данных, выявлены их преимущества и недостатки;
- предложена модификация метода ветвей и границ, позволяющая существенно сократить время работы при решении задачи большой размерности, при этом не потеряв в качестве полученного решения;
- разработана и реализована программа, предназначенная для поиска оптимальных решений оптимизации сети передачи данных Сибирского банка.
