НЕКОТОРЫЕ МИНИМАКСНЫЕ ЗАДАЧИ УПРАВЛЕНИЯ И МАРШРУТИЗАЦИИ
|
Актуальность темы. Работа посвящена минимаксным задачам маршрутизации и последовательного управления.
В последние годы классические задачи комбинаторной оптимизации (в первую очередь, задача коммивояжера (ЗК), задача о наикратчайших путях (ЗИП), задача о минимальном остовном дереве) стали изучаться в обобщенной постановке, когда вместо фиксированного узла Xiрассматривается множество Mi,которому может принадлежать узел Xi.Преимуществом таких обобщенных постановок задач комбинаторной оптимизации является то, что появляется дополнительная свобода варьировать узлы Xi для достижения лучшего качества. Однако в ряде задач следует считаться с наличием неконтролируемых воздействий.
В связи с этим, в настоящей работе делается следующий шаг в этом направлении, и предлагается постановка, в которой нет возможности выбирать точки Xiили управлять ими. Таким образом, получаем игровую ситуацию, когда распоряжение точками Xiотдается игроку-противнику или (противостоящей) природе. Множествами Miмоделируется (непредсказуемое) поведение точек Xi(они могут представлять собой, в зависимости от конкретной задачи, помехи, ошибки, возмущения, шумы, сбои и т.п., или разумные управления игрока-противника).
Особый интерес представляют позиционные динамические задачи (ЗК ЗИП и др.), когда решения принимаются игроками в динамике, в зависимости от предыдущих действий противника. Построение позиционных стратегий управления является здесь новым, неисследованным и трудным кругом задач. Основной вопрос при решении задач этого класса заключается в следующем: как подойти к конструированию управления по принципу обратной связи в динамической игре с комбинаторным функционалом, и как сформулировать и решить задачу в замкнутом виде?
Н.Н. Красовским, А.И. Субботиным и их сотрудниками была создана теория позиционных дифференциальных игр. Настоящая работа, расовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. - М.: Наука, 1974.
в которой вводится и изучается обобщенная ЗК в игровой постановке в классе позиционных стратегий, основана на этом подходе, связанном с минимизацией гарантированного результата в классе позиционных стратегий, что объективно сближает рассматриваемую постановку с задача-ми теории дифференциальных игр. В даны многочисленные примеры содержательных задач управления, формализуемых в рамках теории дифференциальных игр. Теория дифференциальных игр получила свое глубокое развитие в работах Р.В. Гамкрелидзе, Н.Н. Красовского, А.В. Кряжимского, А.Б. Куржанского, Е.Ф. Мищенко, Ю.С. Осипова, Л.С. Понтрягина, Б.Н. Пшеничного, А.И. Субботина, В.Е. Третьякова, А.Г. Ченцова, Ф.Л. Черноусько, А.А. Чикрия; отметим также исследования Э.Г. Альбрехта, В.Д. Батухтина, П. Варайи, Н.Л. Григоренко, П.Б. Гусятникова, А.Ф. Клейменова, А.Н. Красовского, Дж. Лейтмана, Н.Ю. Лукоянова, М.С. Никольского, В.С. Пацко, Н.Н. Петрова, Л.А. Петросяна, Н.Н. Субботиной, А.М. Тарасьева, В.И. Ухоботова, В.Н. Ушакова, В. Флеминга, А. Фридмана и др.
Обобщенная (неигровая) ЗК и ее решение методом динамического программирования рассматривались ’ А.Г. Ченцовым и его сотрудниками. Следует отметить, что многие комбинаторные задачи могут быть переформулированы в виде ЗК или обобщенной ЗК. Как отмечается в литературе, ЗК занимает центральное место в комбинаторной оптимизации, и она явилась прототипической задачей современной комбинаторной оптимизации. Простота ее формулировки сочетается с трудностью решения. Многие подходы к решениям, ставшие стандартными в комбинаторной оптимизации, сначала были развиты и опробованы в контексте ЗК. Таким образом, в данной работе объединяются рамки и инструментарий теории динамических игр (программное движение, позиционная стратегия, движение, порожденное позиционной стратегией, многократный минимакс, позиционный минимакс, и др.) и весьма нетривиальная комбинаторная задача, каковой является обобщенная ЗК, так что данная тематика органически связана с задачами управления.
В диссертации рассматриваются также некоторые программные минимаксные задачи оптимального управления. Основой рассматриваемых конструкций является теория принципа максимума Л.С. Понтрягина. В работе изучаются, в частности, задачи сближения и уклонения траекторий управляемой системы относительно дискретной по времени системы выпуклых компактов, при различных типах (в том числе комбинированных) ограничений на управление. В идейном отношении предлагаемые конструкции следуют подходу, » который предполагает совместное исследование пары экстремальных задач (оптимального управления и математического программирования (МП)), находящихся в двойственности. Такой подход дает возможность в целом ряде случаев для решения задач оптимального управления использовать методы математического программирования, получая эквивалентные по результату конечномерные экстремальные задачи. В11 подход был продвинут на случай задачи сближения с выпуклым компактом в заданной момент времени (при геометрических ограничениях на управления). В работе Н.Н. Красовского для решения задач оптимизации впервые была применена проблема моментов. Различные задачи управления на основе функционального подхода рассматривались в работах Ф.М. Кирилловой, Р. Габасова, М.И. Гусева, А.Б. Куржанского, Ю.С. Осипова.
В работах Ю.И. Бердышева, А.В. Кряжимского, А.Г. Ченцова рассматривались задачи последовательного управления при обходе системы компактных множеств, когда производится совокупная минимизация системы рассогласований; такие постановки связывают конструкции теории оптимального управления и теории маршрутных задач. Задачи последовательной оптимизации в игровой постановке изучались в работах А.Н. Красовского, Н.Н. Красовского, Н.Ю. Лукоянова, А.А. Чикрия».
В ряде прикладных задач приходится решать вопросы взаимодействия двух управляемых систем с импульсными управлениями; это взаимодействие может проходить в условиях неполной информации и, возможно, конфликтности. Задачи управления с обратной связью традиционно являются одним из предметов теории дифференциальных игр. Также приходится работать и с минимаксными задачами программного управления (см.1,2,4,6,8-10, а также работы »). В диссертации исследуется, в частности, минимаксная задача импульсного программного управления в условиях, когда о фазовом состоянии одного из объектов имеется лишь неполная информация, а также в условиях последовательного обхода системы множеств. В смысле интегральных ограничений, ограничение на полный импульс управляющей программы представляет основной интерес, поскольку для многих задач механики, космической навигации, экономики, биомедицины, радиотехники и др. актуальны именно такие ограничения на управляющее воздействие. Для решения в замкнутом виде таких задач, рассматриваемых в диссертации, используются процедуры компактификации в классах обобщенных управлений-мер.
Цель работы. Построение теории позиционного управления в игровой комбинаторной задаче последовательного обхода системы множеств. Получение необходимых условий оптимальности для задач последовательного управления относительно системы выпуклых компактных множеств при различных ограничениях на управления.
Методы исследования. Используются методы теории оптимального управления, дифференциальных игр, функционального анализа, теории меры, комбинаторной оптимизации.
Научная новизна.
1. Построена теория позиционного управления в минимаксных задачах последовательного обхода конечной системы множеств.
2. Получены необходимые условия оптимальности в классе конечно-аддитивных управлений-мер для задач управления линейными системами с импульсными ограничениями и разрывными коэффициентами при управлении, включая задачи последовательного сближения с системой выпуклых компактов.
3. Получены необходимые условия оптимальности в задаче программного уклонения для собственно линейной системы.
Теоретическая и практическая ценность. Полученные результаты могут быть использованы при синтезе управления в прикладных задачах, связанных с маршрутизацией (например, в динамических сетевых задачах) при наличии неопределенностей. Результаты также могут применяться для построения управления в задачах последовательного обхода множеств.
Апробация работы. Результаты диссертационной работы докладывались на семинарах отдела управляемых систем ИММ УрО РАН, совместных семинарах кафедры теоретических основ радиотехники РТФ УГТУ-УПИ и отдела управляемых систем, VII Всесоюзной конф. ’’Качественная теория дифференциальных уравнений” (Рига, 1989), VII Всесоюзной конф. ’’Управление в механических системах” (Свердловск, 1990), 2 Междунар. Семинаре ’’Негладкие и разрывные задачи управления и оптимизации” (Челябинск, 1993), 11 Междунар. Семинаре ИФАК ’’Control Appications of Optimization” (С-Петербург, 2000), 5 Симпозиуме ИФАК ’’Nonlinear Control Systems” (С-Петербург, 2001).
Публикации. Основные результаты диссертации опубликованы в 12 работах [1-12].
Структура и объем работы. Диссертационная работа состоит из введения, двух глав, приложения и списка литературы. Общий объем — 107 страниц машинописного текста. Библиографический список содержит 101 наименование.
В последние годы классические задачи комбинаторной оптимизации (в первую очередь, задача коммивояжера (ЗК), задача о наикратчайших путях (ЗИП), задача о минимальном остовном дереве) стали изучаться в обобщенной постановке, когда вместо фиксированного узла Xiрассматривается множество Mi,которому может принадлежать узел Xi.Преимуществом таких обобщенных постановок задач комбинаторной оптимизации является то, что появляется дополнительная свобода варьировать узлы Xi для достижения лучшего качества. Однако в ряде задач следует считаться с наличием неконтролируемых воздействий.
В связи с этим, в настоящей работе делается следующий шаг в этом направлении, и предлагается постановка, в которой нет возможности выбирать точки Xiили управлять ими. Таким образом, получаем игровую ситуацию, когда распоряжение точками Xiотдается игроку-противнику или (противостоящей) природе. Множествами Miмоделируется (непредсказуемое) поведение точек Xi(они могут представлять собой, в зависимости от конкретной задачи, помехи, ошибки, возмущения, шумы, сбои и т.п., или разумные управления игрока-противника).
Особый интерес представляют позиционные динамические задачи (ЗК ЗИП и др.), когда решения принимаются игроками в динамике, в зависимости от предыдущих действий противника. Построение позиционных стратегий управления является здесь новым, неисследованным и трудным кругом задач. Основной вопрос при решении задач этого класса заключается в следующем: как подойти к конструированию управления по принципу обратной связи в динамической игре с комбинаторным функционалом, и как сформулировать и решить задачу в замкнутом виде?
Н.Н. Красовским, А.И. Субботиным и их сотрудниками была создана теория позиционных дифференциальных игр. Настоящая работа, расовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. - М.: Наука, 1974.
в которой вводится и изучается обобщенная ЗК в игровой постановке в классе позиционных стратегий, основана на этом подходе, связанном с минимизацией гарантированного результата в классе позиционных стратегий, что объективно сближает рассматриваемую постановку с задача-ми теории дифференциальных игр. В даны многочисленные примеры содержательных задач управления, формализуемых в рамках теории дифференциальных игр. Теория дифференциальных игр получила свое глубокое развитие в работах Р.В. Гамкрелидзе, Н.Н. Красовского, А.В. Кряжимского, А.Б. Куржанского, Е.Ф. Мищенко, Ю.С. Осипова, Л.С. Понтрягина, Б.Н. Пшеничного, А.И. Субботина, В.Е. Третьякова, А.Г. Ченцова, Ф.Л. Черноусько, А.А. Чикрия; отметим также исследования Э.Г. Альбрехта, В.Д. Батухтина, П. Варайи, Н.Л. Григоренко, П.Б. Гусятникова, А.Ф. Клейменова, А.Н. Красовского, Дж. Лейтмана, Н.Ю. Лукоянова, М.С. Никольского, В.С. Пацко, Н.Н. Петрова, Л.А. Петросяна, Н.Н. Субботиной, А.М. Тарасьева, В.И. Ухоботова, В.Н. Ушакова, В. Флеминга, А. Фридмана и др.
Обобщенная (неигровая) ЗК и ее решение методом динамического программирования рассматривались ’ А.Г. Ченцовым и его сотрудниками. Следует отметить, что многие комбинаторные задачи могут быть переформулированы в виде ЗК или обобщенной ЗК. Как отмечается в литературе, ЗК занимает центральное место в комбинаторной оптимизации, и она явилась прототипической задачей современной комбинаторной оптимизации. Простота ее формулировки сочетается с трудностью решения. Многие подходы к решениям, ставшие стандартными в комбинаторной оптимизации, сначала были развиты и опробованы в контексте ЗК. Таким образом, в данной работе объединяются рамки и инструментарий теории динамических игр (программное движение, позиционная стратегия, движение, порожденное позиционной стратегией, многократный минимакс, позиционный минимакс, и др.) и весьма нетривиальная комбинаторная задача, каковой является обобщенная ЗК, так что данная тематика органически связана с задачами управления.
В диссертации рассматриваются также некоторые программные минимаксные задачи оптимального управления. Основой рассматриваемых конструкций является теория принципа максимума Л.С. Понтрягина. В работе изучаются, в частности, задачи сближения и уклонения траекторий управляемой системы относительно дискретной по времени системы выпуклых компактов, при различных типах (в том числе комбинированных) ограничений на управление. В идейном отношении предлагаемые конструкции следуют подходу, » который предполагает совместное исследование пары экстремальных задач (оптимального управления и математического программирования (МП)), находящихся в двойственности. Такой подход дает возможность в целом ряде случаев для решения задач оптимального управления использовать методы математического программирования, получая эквивалентные по результату конечномерные экстремальные задачи. В11 подход был продвинут на случай задачи сближения с выпуклым компактом в заданной момент времени (при геометрических ограничениях на управления). В работе Н.Н. Красовского для решения задач оптимизации впервые была применена проблема моментов. Различные задачи управления на основе функционального подхода рассматривались в работах Ф.М. Кирилловой, Р. Габасова, М.И. Гусева, А.Б. Куржанского, Ю.С. Осипова.
В работах Ю.И. Бердышева, А.В. Кряжимского, А.Г. Ченцова рассматривались задачи последовательного управления при обходе системы компактных множеств, когда производится совокупная минимизация системы рассогласований; такие постановки связывают конструкции теории оптимального управления и теории маршрутных задач. Задачи последовательной оптимизации в игровой постановке изучались в работах А.Н. Красовского, Н.Н. Красовского, Н.Ю. Лукоянова, А.А. Чикрия».
В ряде прикладных задач приходится решать вопросы взаимодействия двух управляемых систем с импульсными управлениями; это взаимодействие может проходить в условиях неполной информации и, возможно, конфликтности. Задачи управления с обратной связью традиционно являются одним из предметов теории дифференциальных игр. Также приходится работать и с минимаксными задачами программного управления (см.1,2,4,6,8-10, а также работы »). В диссертации исследуется, в частности, минимаксная задача импульсного программного управления в условиях, когда о фазовом состоянии одного из объектов имеется лишь неполная информация, а также в условиях последовательного обхода системы множеств. В смысле интегральных ограничений, ограничение на полный импульс управляющей программы представляет основной интерес, поскольку для многих задач механики, космической навигации, экономики, биомедицины, радиотехники и др. актуальны именно такие ограничения на управляющее воздействие. Для решения в замкнутом виде таких задач, рассматриваемых в диссертации, используются процедуры компактификации в классах обобщенных управлений-мер.
Цель работы. Построение теории позиционного управления в игровой комбинаторной задаче последовательного обхода системы множеств. Получение необходимых условий оптимальности для задач последовательного управления относительно системы выпуклых компактных множеств при различных ограничениях на управления.
Методы исследования. Используются методы теории оптимального управления, дифференциальных игр, функционального анализа, теории меры, комбинаторной оптимизации.
Научная новизна.
1. Построена теория позиционного управления в минимаксных задачах последовательного обхода конечной системы множеств.
2. Получены необходимые условия оптимальности в классе конечно-аддитивных управлений-мер для задач управления линейными системами с импульсными ограничениями и разрывными коэффициентами при управлении, включая задачи последовательного сближения с системой выпуклых компактов.
3. Получены необходимые условия оптимальности в задаче программного уклонения для собственно линейной системы.
Теоретическая и практическая ценность. Полученные результаты могут быть использованы при синтезе управления в прикладных задачах, связанных с маршрутизацией (например, в динамических сетевых задачах) при наличии неопределенностей. Результаты также могут применяться для построения управления в задачах последовательного обхода множеств.
Апробация работы. Результаты диссертационной работы докладывались на семинарах отдела управляемых систем ИММ УрО РАН, совместных семинарах кафедры теоретических основ радиотехники РТФ УГТУ-УПИ и отдела управляемых систем, VII Всесоюзной конф. ’’Качественная теория дифференциальных уравнений” (Рига, 1989), VII Всесоюзной конф. ’’Управление в механических системах” (Свердловск, 1990), 2 Междунар. Семинаре ’’Негладкие и разрывные задачи управления и оптимизации” (Челябинск, 1993), 11 Междунар. Семинаре ИФАК ’’Control Appications of Optimization” (С-Петербург, 2000), 5 Симпозиуме ИФАК ’’Nonlinear Control Systems” (С-Петербург, 2001).
Публикации. Основные результаты диссертации опубликованы в 12 работах [1-12].
Структура и объем работы. Диссертационная работа состоит из введения, двух глав, приложения и списка литературы. Общий объем — 107 страниц машинописного текста. Библиографический список содержит 101 наименование.
Подобные работы
- НЕКОТОРЫЕ ЗАДАЧИ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ И ФУНКЦИЯМИ СТОИМОСТИ, ЗАВИСЯЩИМИ ОТ СПИСКА ЗАДАНИЙ
Диссертации (РГБ), математика. Язык работы: Русский. Цена: 4230 р. Год сдачи: 2021 - НЕКОТОРЫЕ ЗАДАЧИ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ И ФУНКЦИЯМИ СТОИМОСТИ, ЗАВИСЯЩИМИ ОТ СПИСКА ЗАДАНИЙ
Авторефераты (РГБ), математика. Язык работы: Русский. Цена: 250 р. Год сдачи: 2021 - Маршрутно-распределительные задачи:
теория и приложения
Диссертация , математика. Язык работы: Русский. Цена: 5770 р. Год сдачи: 2015