Автореферат диссертации
Повний текст публікації
Реферат
УДК 519. 854+681.3
А. Н. Ходзинский
НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА И ИХ ИССЛЕДОВАНИЕ
Автореферат диссертации на соискание ученой степени кандидата физико-математических наук
В работе рассматривается несколько типов задач комбинаторной оптимизации. Каждая конкретная задача характеризуется набором ограничений, которые задают допустимую область, и видом критерия. Именно в зависимости от вида критерия изучаемые задачи относятся к одному из следующих типов: линейная задача о назначениях; задача о коммивояжере; квадратичная задача о назначениях; задача разбиения; задача размещения; задача расписания.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
- Осуществлена формализация и проведено исследование ряда важных в практическом и теоретическом отношении задач (размещения, теории расписаний и др.), сформулированных как комбинаторные задачи оптимизации.
- Предложен ряд новых алгоритмов решения выделенного класса задач и исследована их эффективность.
- Разработаны принципы организации и функционирования мобильных ПП для решения задач комбинаторной оптимизации, которые нашли применение при создании ПП ВЕКТОР-2.
- Проведен численный эксперимент по решению широкого круга практических и тестовых задач комбинаторной оптимизации, который подтвердил эффективность предложенных алгоритмов.
- Разработаны компоненты модульного программного обеспечения пакета программ ВЕКТОР-2, в котором реализованы основные алгоритмы, предложенные в диссертации.
- Разработаны алгоритмы решения задач из выбранного класса, предназначенные для реализации на ЭВМ с параллельной организацией вычислений.
2006-06-17