автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему: Методы улучшения в задаче оптимального управления на сети операторов
Автореферат диссертации по теме "Методы улучшения в задаче оптимального управления на сети операторов"
на правах рукописи
Лемперт Анна Ананьевна
Методы улучшения в задаче оптимального управления на сети операторов
05.13.01 — Системный анализ, управление и обработка информации (в технике, экологии и экономике)
диссертации на соискание ученой степени кандидата физико-математических наук
Работа выполнена в Институте
хнамикк систем и теории упр 1С У) СО РАН
доктор физико-матем с.н.с. Батурин Владимир Ал<
доктор физиКо-математически аук, доцент Булдаев Александр Се! ¡вич
кандидат физико-математ доцент Сидоренко Геннадий
Защита состоится 28 декабря ционного совета Д 003.021.01 в ЯСТ ул. Лермонтова, 134, зйл заседаний С диссертацией можно ознакоми ся Автореферат разослан 25 ноябр^рОО
Ученый секретарь д иссертационного совета лт.н.
Иркутский гххударствжнный унквери^г
6 г. в 15.00 час. на заседания
У СО РАН по адресу: 664033, Й еного Совета, ком. 407. в библиотеке ИДСТУ СО РАД. 6 года. •
Общая характеристика работы
Актуальность темы. В настоящее время существует немало алгоритмов, предназначенных для решения задач оптимального управления. Бурное развитие в середине шестидесятых годов прошлого столетия этого раздела математики связано с требованиями практической деятельности людей. Многие процессы, имеющие место в технических системах, в экономике, в управлении деятельностью человеческого сообщества, моделируются учеными как задачи оптимального управления.
Основополагающими результатами теории оптимального управления являются: принцип максимума Л. С. Понтрягина, метод динамического программирования Р. Беллмана, достаточные условия оптимальности В.Ф. Кротова. На основе этих классических результатов созданы различные методы последовательных улучшений первого и второго порядка. Наиболее изученными оказались классы таких задач оптимального управления, как линейные, билинейные, квадратичные задачи. Свойства перечисленных классов задач позволяют упростить многие операции, необходимые для поиска решения, что приводит к созданию эффективных алгоритмов улучшения, однако встречающиеся на практике задачи по своей природе описываются более сложными структурами, такими, как многоэтапные процессы и сети операторов. Например, химические технологии, управление качеством воды в бассейне реки, литейное производство, процессы роста растений. Управление такими процессами может быть как точечным, так и распределенным по независимой переменной (по времени или расстоянию).
Таким образом, создание конструктивных методов решения задачи управления и, в частности, оптимального управления, актуально при исследовании такого рода объектов.
Цель работы - создать алгоритмы улучшения первого и второго порядков для решения задачи оптимального управления на сети операторов, рассмотреть задачу управления многоэтапным процессом как частный случай задачи оптимального управления на сети операторов и исследовать полученные новые алгоритмы на предмет их релаксационности и сходимости.
Методы исследования. При выполнении работы использовались аппарат дифференциального исчисления, элементы теории матриц и векторов, методы теории оптимального управления.
Научная новизна. Основные результаты работы являются новыми и заключаются в следующем:
• Для задачи оптимального управления многоэтапным процессом сформулированы и доказаны достаточные условия оптимальности В.Ф. Кротова, по-
строены методы сильного и слабого улучшения первого и второго порядков, доказаны свойства релаксационности и сходимости.
• Исследована задача параметрической идентификации как многоэтапный процесс, для нее адаптированы предложенные выше методы.
• Сформулированы и доказаны достаточные условия оптимальности для задачи оптимального управления на сети операторов, построены методы сильного и слабого улучшения второго порядка, доказаны свойства релаксационности и сходимости.
• Создана новая версия пакета по идентификации "ПСИ", на его основе разработал вычислительный сервер.
• Созданным программным комплексом решена задача идентификации коэффициентов по серии испытаний в модели движения вертолета типа "горка".
• На математической модели качества водных ресурсов бассейна р. Селенга решена задача нормирования сбросов загрязняющих веществ.
Практическая ценность. Разработанные алгоритмы могут использоваться при решении различных прикладных задач (технических, экономических, природ-но-экономических и др.). Работоспособность и эффективность этих алгоритмов подтверждена рядом тестовых примеров и решением задач эколого-экономическо-го и технического содержания.
Аппробация работы. Основные результаты работы докладывались и обсуждались на школе-семинаре молодых ученых "Математическое моделирование и информационные технологии: состояние и перспектива" (Аршан, 2001); на конференциях ИДСТУ СО РАН "Ляпуновские чтения" (Иркутск, 2002, 2003); на Школе-семинаре молодых ученых "Математическое моделирование и информационные технологии: управление, искусственный интеллект, прикладное программное обеспечение и технологии программирования" (Ангасолка, 2002, 2003, 2004, 2005); на Всероссийской конференции "Инфокоммуникационные и вычислительные технологии и системы" (Улан-Удэ - Байкал, 2003); на Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2004); на Байкальской Всероссийской конференции "Информационные и математические технологии" (Иркутск, 2004); на Международной конференции "ЕМУИ10М18'2004" (Томск, 2004); на Международной конференции "Вычислительные и информационные технологии в науке, технике и образовании" (Алматы, 2004); на XIII Байкальской Международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005); на Всероссийской с международным участием кон-
ференции "Информационные и математические технологии в науке, технике и образовании" (Северобайкальск, 2005); на VI Всероссийской конференции молодых ученых "Математическое моделирование и информационные технологии (Кемерово, 2005); на Международной конференции "Вычислительные и информационные технологии в науке, технике и образовании" (Павлодар, 2006).
Результаты работы обсуждались на семинарах лаборатории "Системного анализа и методов оптимального управления", кафедры теории систем Иркутского государственного университета и Объединенном семинаре ИДСТУ СО РАН.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Список использованной литературы содержит 98 наименований. Общий объем диссертации - 95 страниц.
Краткое содержание диссертационной работы
Во введении обосновывается актуальность темы диссертационной работы, формулируется цель научного исследования, отмечаются новизна и практическая значимость полученных результатов, дается обзор литературы по методам решения задач оптимального управления.
Первая глава посвящена исследованию задач управления для объектов с многоэтапной структурой.
! Рассматривается управляемый процесс, состоящий из нескольких этапов, причем момент окончания предыдущего этапа является моментом начала следующего этапа. Каждый этап описывается своей математической моделью:
Начальные условия на каждом этапе определяются из соотношений
х°(го) = к0 (а0), ¿(п) = = Т^. (2)
Функции xl(t) - кусочно дифференцируемы и принимают значения в евклидовом пространстве ul(t) € £/» С R"1^ - кусочно непрерывны; аг 6 Ai -векторные параметры из RT® к1 - заданные функции.
Множество троек (х,и,а), удовлетворяющих перечисленным условиям, а также дифференциальным связям (1) и начальным условиям (2), будем называть множеством допустимых и обозначать D, предполагается, что D ф 0.
1(х, и, а) = F (хр(тр+1)) —* min. (3)
Поставим задачу о поиске последовательности С D, на которой J(xe, иа, аа) —*■ inf I = /», s —> оо.
Сформулируем и докажем обобщение теоремы Кротова о достаточных условиях оптимальности.
Введем следующие конструкции. Пусть <px(t, х\ a*) - функции, непрерывно дифференцируемые по своим аргументам, t € [г*, 7V+i],
R% x\ u\ a') = xS a')x\ v>) + ^(t, xf, a%
Теорема 1.1 (Достаточные условия оптимальности)
Пусть имеется последовательность С D и функции <pl(t, х', а1) такие, что:
Тогда последовательность - минимизирующая, и всякая минимизирующая последовательность удовлетворяет условиям 1-3.
На основе доказанной теоремы разработаны алгоритмы последовательных улучшений второго порядка. При выводе алгоритмов разлагались приращения функций (? и Д1, г = 0, р в окрестности текущего приближения (х/, щ, а/) в ряд
Тейлора до слагаемых второго порядка, функции Кротова <£>*(£, х\ а1) задавались в классе линейно-квадратичных функций.
Алгоритм слабого улучшения второго порядка
1. На каждом этапе задаются начальные управления «>(£), параметры а>, из уравнений (1) и начальных условий (2) определяются х>(£).
2. Задается параметр а € (0,1] и из следующей системы находятся •0*(£), ст'(£),
3. Подсчитываются а>/ = а> + Да1, где Да* вычисляются по формуле Да* = - [(^(г;) • 4<)'а, + • • ^ - (1 - X
Дгх< = - (Н^ - (1 - а)^))-1 (я*, + + /*сг<) Дх'), тем самым получаются и новые управления и>/ = -I- Дм*(£, — х>(г)).
5. Сравниваются значения функционалов 7(х/,и/, а/) и 1(хц,иц,ац). Если улучшения не произошло, то параметр а уменьшается и процесс повторяется, начиная с шага 2.
Для данного алгоритма доказана монотонность по функционалу последовательности, генерируемой алгоритмом.
Теорема 1.2 (о релаксационности алгоритма)
Пусть функция Р(хр) дважды дифференцируема, функции /*(£, х*, и*) дважды дифференцируемы и хотя бы на одном этапе управление не удовлетворяет условию стационарности //*;(£,х>(г),^»*(г), ^ 0 при а = 1.
Тогда алгоритм улучшает управление и7(£).
Алгоритм сильного улучшения второго порядка
1. На каждом этапе задаются начальные управления u)(t), параметры а>, из уравнений (1) и начальных условий (2) определяются x)(t).
2. Задается параметр a G (0,1] и из дифференциальных уравнений ^ = -Пхх< - er* - Нхф1) ,
aP(rp+1) = —ocFxpxJ> - (1 - a)£^> находятся -0*(£) и cr*(£).
3. По формуле Да* = - + - (1 - фн(т^ подсчитываются Да* и ахп = Oj + Да*.
4. Интегрируются уравнения
= fl(t,xx(t),ul(t,xxtipx(t) + а*(£)Дх*(£))),г = О,р, при условиях (2), тем самым находится Xj7(i) и uxrI(t) = u*(i,X//(i),V»*(£) + a*(i)(x/j(i) — х>(£))).
5. Сравниваются значения функционалов /(xj,uj,aj) и 1(хц, иц, а и). Если улучшения не произошло, то параметр а уменьшается и процесс повторяется, начиная с шага 2.
Теорема 1.3 (о релаксационности алгоритма)
Пусть функция F(xp) непрерывна и дважды дифференцируема, а функции Н1(-),Я*(-) и üx(t,xx,px) удовлетворяют условиям:
1) функции 7ix(£, х*, р*) непрерывны и непрерывно-дифференцируемы дважды по х\р1;
2) существуют непрерывные и дважды дифференцируемые по р1 функции ü*(t, х*, р*) такие, что Hx(t, хг, р\ üx(t, хх, р*)) = 7ix(t, х*, р*).
Во второй главе рассматривается более общая задача - задача оптимального управления на сети операторов.
В разделе 2.1 сформулирована постановка задачи и доказана теорема о достаточных условиях оптимальности.
Пусть задан ориентированный граф с вершинами i — О, N + к.
Пусть первые к вершин графа являются входными, а последние к вершин -выходными, т.е. = 0 при г = 0, к и = 0 при г = N + I, N + 1г.
На каждом ребре состояние процесса описывается своей математической моделью в форме обыкновенных дифференциальных уравнений:
Начальные условия на каждом ребре определяются из следующих соотношений:
= /ь. /р 6 Аи г = к+ТГЛГ. (5)
Функции ху'(£) - кусочно дифференцируемы и принимают значения в евклидовом пространстве € 17^ С ВГ1^ - кусочно непрерывны; а1^ € Лу -векторные параметры из к1! - заданные функции.
Множество троек (x, и, а), удовлетворяющих перечисленным условиям, а также дифференциальным связям (4) и начальным условиям (5), будем называть множеством допустимых и обозначать D, предполагается, что D ^ 0. Определим функционал
/(*, u,a) = F (xs™>n+1(tn+1), . xs^+h(rn+h)) - min. (6)
В разделе 2.2 приводится вывод и обоснование алгоритмов слабого улучшения первого и второго порядков, исследуются их свойства. Алгоритм слабого улучшения
1. На каждом ребре задаются начальные управления ti/J(£), параметры а1/, из уравнений (4) и начальных условий (5) определяются xl/(t).
2. Задается параметр а € (0,1] и Tpl^(t)ta^(t), г = 0, N,j е В, находятся из уравнений:
<rij(Tj) = -aFxü^)^^^) при j — N + 1,N + h, i e Aj.
3. Подсчитываются al/j — а)3 + Да*7, где
4. Новая траектория определяется из уравнений (4) при условиях
5. Сравниваются значения функционалов /(х/,и/,а/) и 1(хц,Щ1,ац). Если улучшения не произошло, то параметр а уменьшается и процесс повторяется, начиная с шага 2.
В разделе 2.3 строятся методы сильного улучшения первого и второго порядков, доказываются свойства релаксационности и сходимости.
Глава 3 посвящена программно-алгоритмической реализации методов улучшения и решению прикладных задач.
В разделе 3.1 дано описание комплекса программ для решения задачи параметрической идентификации, которая рассматривается как частный случай задачи оптимального управления многоэтапным процессом.
Пусть математическая модель управляемого объекта описывается системой обыкновенных дифференциальных уравнений
Наблюдения за объектом ведутся на некоторых отрезках времени Тг = [¿о, Ь\] С Г, г = 1 ,р, на каждом из которых известна вектор-функция дг (£, х, и, а), описывающая математическую модель оператора измерений над объектом, заданы вектор начальных состояний х (¿о), вектор значений оператора измерений на всем отрезке времени д1 (¿), а также математическая модель оператора измерений С (¿¡,х, а) при £ = ¿1 и вектор его значений СР.
Задача параметрической идентификации состоит в поиске таких коэффициентов модели, чтобы математическая модель (7) описывала наилучшим образом поведение объекта, например, в смысле минимума функционала отклонения полученных расчетных результатов от реально измеренных величин:
где ßl(t) и <5* - диагональные положительно определенные матрицы.
Сформулированная задача укладывается в общую постановку из раздела 1.1, так как необходимо определить параметр а, а управления ux