Введение к работе
Актуальность темы. Работа посвящена исследованию возможности решения оптимизационных ладам на основе декомпозиции .жстро-мума. Здесь под декомпозицией понимается процедура разделении соответствующей экстремальной операции в задаче со связанными переменными на две компоненты. При этом одна из компонент иключ.кчси в структуру оптимизируемой функции на основе специальных условий разложимости данной функции (критерия). Вопросы такого рода могут возникать в различных задачах оптимизации функций многих переменных, включая многокритериальные задачи и задачи оптимизации но конусу. Необходимость таких исследований связана также с появлением большого количества прикладных оптимизационных задач, множество решений которых имеет сложную дискретно - непрерывную структуру. К таковым, в частности, относятся экстремальные задачи, связанные с маршрутизацией и распределением заданий между исполнителями в условиях, когда варианты перехода от одной элементарной задачи к другой составляют бесконечное множество. Сложность их моделирования обусловлена невозможностью разделения исходной задачи на дискретную и непрерывную подзадачи в силу связанности дискретных и непрерывных переменных.
Метод декомпозиции экстремума является развитием пошагового метода решения задач применительно к задачам оптимизации. Идея пошагового решения задач анализа, оптимизации, теории дифференциальных уравнений использовалась давно и представлена в работах таких известных математиков как Ферма, Эйлер, Маклорен. Но лишь в 50-х годах нашего столетия Р. Беллман и его ученики создали единообразный математический аппарат для изучения многошаговых опти-мизационыых процессов, обладающих определенными свойствами инвариантности - динамическое программирование (ДП). В основе ЦП лежит частный случай "принципа инвариантного погружения" - принцип оптимальности Беллмала: оптимальное решение исходной задачи образовано оптимальными решениями частных подзадач. Возможность декомпозиции экстремума на основе принципа оптимальности определяется возможностью внесения оптимума по части переменных под знак функции агрегирования, посредством которой решения частных подзадач образуют решение исходной задачи.
Изначально принцип оптимальности был сформулирован Беллма-
ном для задач (включая маршрутные) с аддитивными функциями агрегирования, затем в работах Р.Беллмана, Р.С.Лсмана, Р.Калабы, С.Лрсйфуса, Р.Карпа, М.Хелда для функций агрегирования, представляющих собой максимум критериев частных подзадач. Отмстим здесь же исследования А.Вальда в области последовательного анализа статистических задач. Методы, использующие динамическое программирование и попятные процедуры, широко применялись в теории оптимального управления и дифференциальных игр. (см., в частности, исследования Врайсона, Хо, Айзскса, Фломинга,Фридмана, Эллиота, Калтона и целого ряда других специалистов в этой области.)
Большой вклад в развитие конструкций, связанных с динамическим программированием, внесли исследования Н.Н.Красовского, А.Б.Куржанского, Ю.С.Осипова, А.И.Субботина, А.Г.Ченцова. Принцип экстремального прицеливания Н.Н.Красовского позволил получить эффективный метод решения для широкого класса задач теории конфликтного управления на основе подхода к анализу уравнения Айзекса - Беллмана с использованием программных конструкций, восходящих к принципу максимума Понтрягина. Идеи, связанные с решением уравнения Айзекса - Беллмана с применением конструкций негладкого анализа, получили дальнейшее развитие в работах А.И.Субботина.
В работах Л.Миттена, Т.Морина, М.Мину, посвященных вопросам декомпозиции экстремума, был расширен класс задач, допускающих конструкцию повторной оптимизации. Однако указанные условия "разложимости" целевого функционала оказались слишком "сильными". Так, в работах А.Г.Ченцова, Л.Н.Коротаевой, А.Я.Сесекина, Э.М.Назарова были впервые получены аналоги функциональных уравнений Беллмана для некоторых задач дискретно - непрерывного характера, целевые функционалы в которых не обладают указанным свойством разложимости.
Целью данной работы является определение наименнее "жестких" условий на целевой оператор и пространство решений, которые позволяют моделировать оптимальные решения на основе декомпозиции экстремума.
Методы решения. Используются методы выпуклого анализа, математического и функционального анализа, математического програм-
мирования, общей топологии, теории сходимости по Мору-Смиту.
Научная новизна. Определены условия, допускающие до.комио.ш-цию экстремума при решении широкого класса задач оптимизации і,** том числе со скалярным критерием, многокритериальные задачи он nt-мизации по конусу в векторных пространствах, задачи оптимизации в произвольных топологических преду порядочен н ых пространствах^. Разработанные методы декомпозиции позволили построить модель аб-страктной дискретно - непрерывной маршрутной оптимизационной задачи с произвольной функцией агрегирования затрат.
Теоретическая и практическая ценность. Полученные условия декомпозиции экстремума в задачах оптимизации имеют самостоятельный теоретический интерес и являются основой пошагового решения задач сложной структуры. Результаты исследований позволили алгоритмизовать приемы построения функциональных уравнений Беллмала в задачах, допускающих декомпозицию. Получен алгоритм на функциональном уровне поиска оптимального и субоптималыюго решения абстрактной маршрутной задачи, охватывающей широкий класс известных задач маршрутизации и позволяющей решать новые задачи с неаддитивными функциями агрегирования.
Апробация работы. Результаты диссертационной работы докладывались на семинарах отдела управляемых систем ИММ УрО РАН, научном семинаре кафедры теории управления и оптимизации Челябинского госупиверситета, научном семинаре кафедры прикладной математики ЧГТУ, международном семинаре NDPCO 98.
Публикации. Основные результаты диссертации опубликованы в 6 работах.
Структура и объем работы. Диссертация состоит из введения, двух глав, приложения и списка литературы. Общий объем 110 страниц машинописного текста. Библиографический список содержит 68 наименований.
