Эволюционные алгоритмы решения задач смешанной целочисленной оптимизации

• Автор: Хоролич, Галина Борисовна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Красноярск
• Количество страниц: 164 с. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
ГЛАВА 1. Практические задачи принятия решений и выбора вариантов при управлении техническими и организационными системами 1.1. Задача составления расписания посадок самолетов для аэропортов

средних размеров

1.2. Задача составления расписания посадок самолетов для аэропортов с

интенсивным воздушным движением.

1.3. Формирование кредитного портфеля банка нахождение оптимального набора кредитных заявок при согласованном виде структуры активов
пассивов

1.4. Задача формирования заявки на отгрузку товара в крупном торговом

предприятии.

ГЛАВА 2. Методы решения задач дискретной оптимизации

2.1. Метод ветвей и границ
2.2. Генетические алгоритмы.
2.3. Поисковые методы оптимизации и гибридные алгоритмы.
Выводы.
ГЛАВА 3. Генетические алгоритмы решения задач смешанного целочисленного математического программирования
3.1. I енетический алгоритм для решения задач СЦ
3.2. Сравнительный анализ алгоритмов эволюционного типа и метода
ветвей и границ в решении тестовых задач СЦЛТТ.
3.3. Сравнительный анализ метода ветвей и границ и генетического
алгоритма в решении задач нелинейного СЦП
3.4. Решение тестовых задач СЦП гибридными алгоритмами
ВыводыИЗ
ГЛАВА 4. Применение поисковых адаптивных алгоритмов к решению практических задач СЦП
4.1. Описание пакета программ для решения задач СЦЛТ.
4.2. Описание пакета программ для решения задач нелинейного СЦП.
4.3. Решение задачи составления расписания посадок самолетов в
аэропорту.
4.4. Решение задачи формирования кредитного портфеля банка
4.5. Решение задачи формирования заявки на отгрузку товара
Выводы.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Для решения специальных задач нелинейного целочисленного программирования следует выделить оригинальный метод последовательных расчегов, предложенный В. П. Черениным []. Из проведенного обзора можно сделать вывод, что надежда на создание точных методов, гарантирующих определение за приемлемое время оптимального решения для многих практических задач целочисленного программирования, является, по-видимому, иллюзорной []. В настоящее время для решения таких задач приходится довольствоваться приближенными подходами. Одним из перспективных подходов к решению задач С ЦП большой размерности является применение методов эволюционного поиска. В [] предложен генетический алгоритм для решения задач С ЦП. Идея состоит в разбиении множества переменных на множество целочисленных и множество вещественных []. Целочисленные переменные фиксируются через эволюционную систему, а вещественные определяются как функции от них через решение задачи математического программирования. Решение тестовых задач показало перспективность такого подхода. Разрабатываются и гибридные алгоритмы. Дополнительным преимуществом генетического алгоритма для полностью целочисленных задач нелинейного программирования является возможность неаналитическою задания целевой функции. Целью диссертационной работы является создание эффективного математического, алгоритмического и программного обеспечения для решения практических задач смешанной оптимизации. Методы исследования. Для решения поставленных задач использовался аппарат системного анализа, теории вероятностей и теории стохастических процессов, теории множеств и теории оптимизации. Выполнена модификация формальных моделей составления расписания посадок самолетов в аэропорту. Построены новые формальные модели формирования кредитного портфеля банка, формирования заявки на отгрузку товара в крупном торговом предприятии. Предложен новый генетический алгоритм для решения задач линейного СЦП, отличающийся от известных алгоритмов способом представления переменных и видом генетических операторов и превосходящий известные алгоритмы по эффективности. Впервые предложен генетический алгоритм для решения задач нелинейного СЦП. Практическое значение. Полученные в работе результаты позволяют решать практические задачи принятия решений и выбора вариантов при управлении техническими и организационными системами. Предложенные модели составления расписания посадок самолетов в аэропорту, формализованные в виде задач смешанного целочисленного линейного математического программирования, а также алгоритмы решения задач СЦЛП и программное обеспечение, реализующее указанные модели и алгоритмы, переданы Красноярскому филиалу ГУДП “Аэронавигация Центральной Сибири”. Отдельные разделы диссертации используются в учебном процессе при обучении студентов по курсам методов оптимизации и управления сложными системами на кафедре СА и ИО, по курсу математического программирования на кафедре высшей магематики Сибирской аэрокосмической академии им. М. Ф. Решетнева. Основные защищаемые положения. Задачи составления расписания посадок самолетов в аэропорту, формирования кредитного портфеля банка, формирования заявки на отгрузку товара крупною торговою предприятия адекватно формализуются в виде задач смешанного целочисленного программирования. Предлагаемые генетические атгоритмы обеспечивают более быстрое нахождение допустимого решения хорошего качества по сравнению с классическими подходами. Разработанное программное обеспечение отвечает современным требованиям к прикладному ПО и позволяет эффективно решать реальные практические задачи, формализованные в виде задач СЦП. Публикации. По теме диссертации опубликовано тринадцать печатных работ, которые приводятся в списке литературы под номерами -, ,-. Апробация работы. Сибирской аэрокосмической академии им. М. Ф. Решетнева (Красноярск, -). Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Изложение иллюстрируется рисунками, 8 графиками и таблицами. Общий объем -3 страницы, список литературы - наименований.