Павлова Л. А. Разработка и исследование ПДС-алгоритмов для труднорешаемых задач комбинаторной оптимизации

Объект исследования: Труднорешаемые задачи комбинаторной оптимизации. Цель исследования: Создание нового подхода к разработке точных алгоритмов для труднорешаемых комбинаторных задач и исследование его эффективности. Методы исследования и аппаратура: Базируются на понятиях и результатах теории алгоритмов, теории графов. теории расписаний и методов дискретной оптимизации. Теоретические результаты и новизна: 1.Введено понятие ПДС-алгоритма для труднорешаемой комбинаторной задачи и предложена оценка его эффективности. 2.Разработаны ПДС-алгоритмы для задач "Максимальное независимое множество" и "Минимизация суммарного взвешеного момента окончания работ". Практические результаты и новизна: Определены ограничения на параметры задач "Максимальное независимое множество" и "Минимизация суммарного взвешенного момента окончания работ", при выполнении которых полиномиальная составляющая их ПДС-алгоритмов является эффективной. Предмет и степень внедрения: ПДС-алгоритмы на этапе создания опытных образцов. Эффективность внедрения: Разработанные ПДС-алгоритмы могут быть использованыдля получения точного решения задач Максимальное независимое множество, Минимизация суммарного взвешенного момента окончания работ, Выполнимость, Клика, вершинное Покрытие, Разбиение на клики, Хроматическое число, Гамильтонов цикл, Гамильтонов путь. Сфера (область) использования: Информатика, исследование операций, современная теория управления, экономическая кибернетика, прикладная и вычислительная математика.