Logo BSU

Please use this identifier to cite or link to this item: http://elib.bsu.by/handle/123456789/149569
Title: Корректность и эффективные методы решения задач дискретной оптимизации с многими критериями и неполной информацией : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котов
Authors: Котов, В. М.
Орлович, Ю. Л.
Емеличев, В. А.
Кузьмин, К. Г.
Иржавский, П. А.
Keywords: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Issue Date: 2015
Publisher: Минск : БГУ
Abstract: Объектом исследования являются задачи дискретной оптимизации. Цель работы состоит в создании математического аппарата для интеллектуальной информационной поддержки принятия решений в условиях неполной информации. Основные результаты исследований. Для задач теории расписаний установ-лена устойчивость алгоритмов в терминах гарантированной оценки, обусловленная классификацией объектов и объемом доступной информации. Предложен единый подход к исследованию разных типов устойчивости многокритериальных комбинаторных задач. На его основе найдены формулы радиусов устойчивости многокритериальной задачи о максимальном разрезе графа. Для этой задачи также установлено, что наличие полиномиального алгоритма для нахождения любого из радиусов устойчивости влечет P = NP. Указаны достижимые границы для радиуса устойчивости эффективного портфеля многокритериальной инвестиционной задачи оптимизации Марковица с критериями Вальда. Показано, что для любого (при P  NP) задачу о наименьшем максимальном диссоциирующем множестве для двудольных графов порядка нельзя аппроксимировать за полиномиальное время с точностью до . Установлено, что задача о наибольшем диссоциирующем множестве в классе всех графов порядка n не аппроксимируется за полиномиальное время с точностью до для любого . Установлена вычислительная сложность и сложность аппроксимации ряда теоретико-графовых параметров, родственных классическим числам независимости и доминирования. Найдены новые достаточные условия существования совершенного паросочетания в графах с предписанной локальной структурой.
URI: http://elib.bsu.by/handle/123456789/149569
Registration number: № госрегистрации 20131167
Appears in Collections:Отчеты 2015

Files in This Item:
File Description SizeFormat 
Отчет 20131167-КОТОВ.doc4,07 MBMicrosoft WordView/Open


PlumX

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.