Некоторые методы решения оптимизационных задач комбинаторного типа и их исследование (диссертация)

УДК 519. 854+681.3 А. Н. Ходзинский В работе рассматривается несколько типов задач комбинаторной оптимизации. Каждая конкретная задача характеризуется набором ограничений, которые задают допустимую область, и видом критерия. Именно в зависимости от вида критерия изучаемые задачи относятся к одному из следующих типов: линейная задача о назначениях; задача о коммивояжере; квадратичная задача о назначениях; задача разбиения; задача размещения; задача расписания. ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ 1. Осуществлена формализация и проведено исследование ряда важных в практическом и теоретическом отношении задач (размещения, теории расписаний и др.), сформулированных как комбинаторные задачи оптимизации. 2. Предложен ряд новых алгоритмов решения выделенного класса задач и исследована их эффективность. 3. Разработаны принципы организации и функционирования мобильных ПП для решения задач комбинаторной оптимизации, которые нашли применение при создании ПП ВЕКТОР-2. 4. Проведен численный эксперимент по решению широкого круга практических и тестовых задач комбинаторной оптимизации, который подтвердил эффективность предложенных алгоритмов. 5. Разработаны компоненты модульного программного обеспечения пакета программ ВЕКТОР-2, в котором реализованы основные алгоритмы, предложенные в диссертации. 6. Разработаны алгоритмы решения задач из выбранного класса, предназначенные для реализации на ЭВМ с параллельной организацией вычислений.