RUS  ENG
Полная версия
СЕМИНАРЫ

Общемосковский постоянный научный семинар «Теория автоматического управления и оптимизации»
16 апреля 2024 г. 11:30, г. Москва, очно: ИПУ РАН комн.433, +трансляция ZOOM, идентификатор конференции 425 322 745 Для получения ссылки и пароля напишите e-mail на stefa@ipu.ru (+копия rezkov@ipu.ru)


Количественное измерение NP-трудности задач дискретной оптимизации и теории расписаний

Д. В. Лемтюжникова

Институт проблем управления им. В. А. Трапезникова РАН, г. Москва

Аннотация: В диссертационной работе предлагается технология количественного измерения сложности NP-трудных задач с различными целевыми функциями. Данная технология базируется на концепции метода попарного сходства, использует понятия устойчивости, меры неразрешимости и меры близости задачи, а также вспомогательные методы интерполяции, аппроксимации, декомпозиции, теории графов и машинного обучения. Метод попарного сходства используется для получения оценки погрешности целевой функции, качества применяемой декомпозиции или оценки скорости сходимости исследуемого алгоритма за счет использования знаний о данной задаче, разработанных для нее эвристик, декомпозиций и функций попарного сходства. Под знаниями о данной задаче подразумеваются так называемые специальные случаи - подмножества примеров задачи, для которых удалось установить некоторую зависимость входных параметров и качества работы соответствующего алгоритма. Полученные результаты предлагается использовать для оценки количественной сложности NP-трудных задач за счет построения сложностных карт на основе зависимостей между параметрами примеров задач и соответствующих алгоритмов решения. Разрабатываемые модели и методы используются для решения следующих практических задач: задача оптимального распределения ресурсов операционных в больнице, задача оптимизации заявок на грузоперевозки, управление цепочкой поставок потребителям в сложных сетях с многоагентной маршрутизацией, управление движением спутников и др.


© МИАН, 2024