Введение к работе
Актуальность темы. В настоящее время математические методы широко используются при исследовании сложных практических проблем принятия технических, экономических, социальных и др. решений. Возникающие при этом задачи являются, как правило, многокритериальными. Характерным примером могут служить территориалыю-распределенные (сетевые) многопользовательские системы, функционирование которых моделируется с помощью формализма многопродуктовых потоковых сетей. Вектор критериев определяется различием интересов пользователей системы.
Первым этапом решения многокритериальных задач является, обычно, построение или аппроксимация множества Парето-оптимальных решений. Один из наиболее распространенных методов аппроксимации эффективного множества — скаляризация векторного критерия, т.е. сведение исходной многокритериальной задачи к параметрическому семейству однокритериальных (скалярных) задач. Набор точек, аппроксимирующий множество Парето, получают, решая эти задачи для набора параметров из некоторой сетки на множестве всевозможных значений параметра. Основной проблемой такого рода методов является необходимость решения большого числа скалярных задач. В связи с этим актуальна задача построения методов, позволяющих сократить число решаемых оптимизационных задач.
Цель работы. Разработать и обосновать методы сокращения числа решаемых скалярных задач для линейных, в том числе, сетевых, и выпуклых многокритериальных задач.
Научная новизна. Для аппроксимации множества Парето используется обратная логическая свертка (ОЛС):
Ф(»»А)= min{у,-/А,-}.
і:Л,'>0
В работе показано, что функция максимума ОЛС в линейном случае легко может быть сведена к выпуклой кусочно-линейной функции параметра Л. Это свойство (отсутствующее у традиционно используемой гермейеровской свертки) дает возможность существенно сократить число узлов сетки на множестве значений параметра, требующих решения задач максимизации ОЛС.
Практическая ценность. Обоснована возможность использования ОЛС для аппроксимации множества Парето широкого класса многокритериальных задач. Предложены методы существенного сокращения числа решаемых скалярных задач, что значительно повышает эффективность метода свертки.
Публикации. По материалам диссертационной работы опубликовано 6 печатных работ.
Апробация работы. Основные результаты диссертации докладывались на 1-й Московской международной конференции по исследованию операций (Москва, 10—13 апреля 1996 г.) и на научно-исследовательских семинареах факультета ВМиК МГУ, ВЦ РАН и ИВВС РАН.
Структура и объем работы. Диссертация состоит из введения, четырех глав, приложения и списка литературы. Содержит страниц текста, включая приложение и список литературы из наименований.