Корректность и эффективные методы решения задач дискретной оптимизации с многими критериями и неполной информацией : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котов

Abstract

Объектом исследования являются задачи дискретной оптимизации. Цель работы состоит в создании математического аппарата для интеллектуальной информационной поддержки принятия решений в условиях неполной информации. Основные результаты исследований. Для задач теории расписаний установ-лена устойчивость алгоритмов в терминах гарантированной оценки, обусловленная классификацией объектов и объемом доступной информации. Предложен единый подход к исследованию разных типов устойчивости многокритериальных комбинаторных задач. На его основе найдены формулы радиусов устойчивости многокритериальной задачи о максимальном разрезе графа. Для этой задачи также установлено, что наличие полиномиального алгоритма для нахождения любого из радиусов устойчивости влечет P = NP. Указаны достижимые границы для радиуса устойчивости эффективного портфеля многокритериальной инвестиционной задачи оптимизации Марковица с критериями Вальда. Показано, что для любого (при P  NP) задачу о наименьшем максимальном диссоциирующем множестве для двудольных графов порядка нельзя аппроксимировать за полиномиальное время с точностью до . Установлено, что задача о наибольшем диссоциирующем множестве в классе всех графов порядка n не аппроксимируется за полиномиальное время с точностью до для любого . Установлена вычислительная сложность и сложность аппроксимации ряда теоретико-графовых параметров, родственных классическим числам независимости и доминирования. Найдены новые достаточные условия существования совершенного паросочетания в графах с предписанной локальной структурой.