Содержание к диссертации
Введение
Глава 1. Необходимые сведения о задачах оптимального управления ... 11
1.1. Постановка задачи и достаточные условия оптимальности ... 11
1.2. Алгоритмы последовательных улучшений 15
1.3. Задача с параметром 23
Глава 2. Задача управления параметрами в алгоритмах слабого улучшения 31
2.1. Автоматизация выбора значений параметров алгоритма в задаче оптимального управления 31
2.2. Вывод формул для производных функционала по компонентам параметра в алгоритме слабого улучшения 33
2.3. Новые алгоритмы слабого улучшения 2-го порядка 56
2.4. Свойства алгоритма с astart = О 66
Глава 3. Задача управления параметрами в алгоритмах сильного улучшения 70
3.1. Вывод формул для производных функционала по компонентам параметра в алгоритме сильного улучшения ... 70
3.2. Новый алгоритм сильного улучшения 2-го порядка 76
Глава 4. Программно-алгоритмическая реализация 81
4.1. Описание программного комплекса 81
4.2. Тестовые примеры 84
4.3. Задача управления эколого-экономической моделью 102
Заключение 116
Список использованной литературы 118
- Постановка задачи и достаточные условия оптимальности
- Вывод формул для производных функционала по компонентам параметра в алгоритме слабого улучшения
- Вывод формул для производных функционала по компонентам параметра в алгоритме сильного улучшения
- Задача управления эколого-экономической моделью
Введение к работе
Актуальность темы. В настоящее время существует немало алгоритмов, предназначенных для решения задач оптимального управления. Бурное развитие в середине шестидесятых годов прошлого столетия этого раздела математики связано с требованиями практической деятельности людей. Многие процессы, имеющие место в технических системах, в экономике, в управлении деятельностью человеческого сообщества, моделируются учеными как задачи оптимального управления.
Основополагающими результатами теории оптимального управления являются: принцип максимума Л.С. Понтрягина, метод динамического программирования Р. Беллмана, достаточные условия оптимальности В.Ф. Кротова. На основе этих классических результатов созданы различные методы последовательных улучшений первого и второго порядка. Наиболее изученными оказались такие классы задач оптимального управления, как линейные, билинейные, квадратичные задачи. Свойства перечисленных классов задач позволяют упростить многие операции, необходимые для поиска решения, что приводит к созданию эффективных алгоритмов улучшения. Сложнее обстоит дело, когда надо решать задачу оптимального управления нелинейной системой, характер нелинейности которой не известен заранее. Алгоритмы последовательных улучшений, разработанные в предположении, что система и функционал имеют общий вид, как правило, содержат параметры, роль которых - регуляторы шага, обеспечивающие эффективное решение задачи улучшения. В результате эффективность такого алгоритма в той или иной степени (иногда в очень большой) зависит от выбора значений параметров. В то же время вопрос выбора наилучших значений параметров либо сводится к решению одномерной задачи минимизации (если она не трудоемка, то решение вопроса закрыто), либо часто не рассматривается, считается достаточным указать только область допустимых значений. Поэтому при практическом решении задачи оптимального управления достаточно хорошие значения параметров алгоритма обычно находятся методом «проб и ошибок», отнимая у пользователя много времени.
Таким образом, актуальной является проблема управления параметрами алгоритма, в частности, проблема автоматизации поиска наилучших значений параметров на каждой итерации.
Цель работы — создать алгоритмы сильного и слабого улучшения второго порядка, в которых автоматизирован процесс управления выбором значений параметров алгоритма, рассмотреть задачу с параметром как частный случай задачи оптимального управления с параметром и исследовать полученные новые алгоритмы на предмет их релаксационности и сходимости.
Методы исследования. При выполнении работы использовались аппарат дифференциального исчисления, элементы теории матриц и векторов, методы оптимизации.
Научная новизна. Основные результаты диссертационной работы являются новыми и заключаются в следующем:
предложены новые алгоритмы сильного и слабого улучшения вто
рого порядка для задачи оптимального управления со свободным
правым концом, доказаны теоремы о релаксационности новых алго
ритмов;
выведены формулы частных производных функционала по парамет
рам алгоритма улучшения;
" исследованы свойства наименее трудоемкого из предложенных алгоритмов, доказаны теоремы о его релаксационности и сходимости;
" создано программно-алгоритмическое обеспечение, реализующее предложенные в работе методы улучшения;
проведена проверка работоспособности и эффективности новых ал
горитмов на серии тестовых примеров;
полученные новые методы улучшения применены для сценарного
анализа в задаче управления эколого-экономической системой.
Практическая ценность. Разработанные алгоритмы могут использоваться при решении различных прикладных задач (технических, экономических, природно-экономических и др.). Работоспособность и эффективность этих алгоритмов подтверждена рядом тестовых примеров.
Апробация работы. Основные результаты работы докладывались и обсуждались:
на первой конференции молодых ученых Иркутского государственного университета (Иркутск, 1983),
на второй конференции молодых ученых Иркутского государственного университета (Иркутск, 1984),
на Всероссийской конференции «Инфокоммуникационные и вычислительные технологии и системы» (Улан-Удэ, 2003),
на Ляпуновских чтениях (Иркутск, 2003),
на региональной конференции молодых ученых «Филология и современное лингвистическое образование» (Иркутск, 2004),
на семинаре «Приближенные методы и алгоритмы оптимального управления», проводимом в рамках симпозиума IFAC по обобщенным решениям в задачах управления (GSCP-2004) (Переславль-Залесский, 2004),
на Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании» (Алматы, 2004),
на VII школе-семинаре молодых ученых «Математическое моделирование и информационные технологии» (Иркутск, 2005),
на IV Всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005).
Результаты работы обсуждались на семинарах лаборатории «Системного анализа и методов оптимального управления» и Объединенном семинаре ИДСТУ СО РАН.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Список использованной литературы содержит 86 наименований. Общий объем диссертации - 127 страниц.
Постановка задачи и достаточные условия оптимальности
Данная задача оптимального управления достаточно хорошо решается базовыми алгоритмами при а = 1 на всех итерациях, а в этом случае модифицированные алгоритмы не имеют преимуществ перед базовыми по времени вычислений. Минимумы функционала, найденные базовыми и модифицированными алгоритмами при а = 1 практически совпали. Когда начальное значение параметра задавалось равным 0.7, модифицированным алгоритмам для получения решения требовалось меньше итераций, чем базовым, при этом минимум функционала находился немного точнее. Среди рассмотренных сценариев эколого-экономической системы наибольшую полезность (соответствующую наименьшему значению функционала) имеет сценарий, при котором мощности восстановительной отрасли уменьшаются (например, направляются на производство продукции вместо восстановления ресурса). Это может быть связано с достаточно мощным процессом естественного восстановления природного ресурса. В диссертационной работе получены следующие результаты и выводы. 1. Предложен подход к решению задачи управления параметрами алгоритмов улучшения второго порядка для задачи оптимального управления со свободным правым концом. Этот подход основан на рассмотрении решаемой на каждой итерации задачи улучшения управления как задачи минимизации функционала по параметрам. 2. Выведены формулы частных производных функционала по параметрам алгоритма, необходимые для решения задачи поиска наилучших значений параметров на данной итерации. Формулы частных производных первого порядка получены для алгоритмов слабого и сильного улучшения. Для алгоритма слабого улучшения получены также формулы частных производных второго порядка. 3. Разработаны новые алгоритмы 2-го порядка слабого и сильного улучшения. Особенностями этих алгоритмов являются: 1) разложение по параметру решений вспомогательной векторно-матричной системы дифференциальных уравнений, что позволяет избежать ее многократного интегрирования на каждой итерации; 2) возможность применять эффективно процедуры одномерной задачи минимизации (в отличие от базовых алгоритмов второго порядка), т.е. выбирать наилучшие значения параметров на каждой итерации. Доказаны теоремы о релаксационное новых алгоритмов. 4. Разработан алгоритм слабого улучшения 2-го порядка, в котором управление производится только одним скалярным параметром. Начальное значение этого параметра на каждой итерации алгоритма полагается равным нулю. Итерация такого алгоритма является наименее трудоемкой из всех рассмотренных в работе алгоритмов, потому что векторно-матричная система дифференциальных уравнений, которую необходимо интегрировать на каждой итерации, в данном случае является линейной, в то время как в других алгоритмах она содержит более сложные уравнения. Показано, что этот алгоритм улучшает любое управление, не удовлетворяющее условию стационарности, и сходится к выполнению условия стационарности. 5. Создано программно-алгоритмическое обеспечение, реализующее предложенные в работе методы улучшения. 6. На тестовых примерах проверена работоспособность разработанных алгоритмов слабого и сильного улучшения и проведено их сравнение с базовыми алгоритмами. Сравнение показало, что в некоторых случаях новые алгоритмы работают эффективнее (справляются с решением задачи быстрее, точнее находят минимум функционала). 7. Полученные новые методы улучшения применены для сценарного анализа в задаче управления эколого-экономической системой.
Вывод формул для производных функционала по компонентам параметра в алгоритме слабого улучшения
В настоящее время существует немало алгоритмов, предназначенных для решения задач оптимального управления. Бурное развитие с середины шестидесятых годов прошлого столетия этого раздела математики связано с требованиями практической деятельности людей. Многие процессы, имеющие место в технических системах, в экономике, в управлении деятельностью человеческого сообщества, моделируются учеными как задачи оптимального управления.
Основополагающими результатами теории оптимального управления являются: принцип максимума Л.С. Понтрягина, метод динамического программирования Р. Беллмана, достаточные условия оптимальности В.Ф.Кротова. На основе этих классических результатов созданы различные методы последовательных улучшений первого и второго порядка. Наиболее изученными оказались такие классы задач оптимального управления как линейные, билинейные, квадратичные задачи. Свойства перечисленных классов задач позволяют упростить многие операции, необходимые для поиска решения, что приводит к созданию эффективных алгоритмов улучшения. Сложнее обстоит дело, когда надо решать задачу оптимального управления нелинейной системой, характер нелинейности которой не известен заранее. Алгоритмы последовательных улучшений, разработанные в предположении, что система и функционал имеют общий вид, как правило, содержат параметры, роль которых - регуляторы шага, обеспечивающие эффективное решение задачи улучшения. В результате, эффективность такого алгоритма в той или иной степени (иногда в очень большой) зависит от выбора значений параметров. В то же время вопрос выбора наилучших значений параметров либо сводится к решению одномерной задачи минимизации (если она не трудоемка, то решение вопроса закрыто), либо часто не рассматривается, считается достаточным указать только область допустимых значений. Поэтому при практическом решении задачи оптимального управления достаточно хорошие значения параметров алгоритма обычно находятся методом «проб и ошибок», отнимая у пользователя много времени.
Таким образом, актуальной является проблема управления параметрами алгоритма, в частности, проблема автоматизации поиска наилучших значений параметров на каждой итерации.
Краткий обзор. Разнообразие задач оптимального управления, возникающих в практической деятельности людей, и различные подходы к их решению обусловили создание разных групп методов (алгоритмов, вычислительных процедур). Один из таких подходов заключается в распространении на задачи оптимального управления методов, основанных на необходимых условиях оптимальности.
Большую группу составляют методы градиентного типа [Брайсон, Хо Ю-Ши, 1972; Васильев О.В., 1994; Васильев О.В., Аргучинцев, 1999; Келли, 1965; Кротов, Гурман, 1973; Полак, 1974; Сеа, 1973; Федоренко, 1978; Шатровский, 1962; Энеев, 1966]. При наличии ограничений на управление и фазовые переменные в градиентных методах первого порядка возникают трудности, которые преодолеваются путем модификации алгоритмов. Некоторые модификации связаны с методом штрафных функций [Гермейер, 1971], другие — это методы спуска в пространстве управлений, представляющие собой аналоги методов конечномерной оптимизации: условного градиента, проекции градиента [Демьянов, Рубинов, 1968; Федоренко, 1975], возможных направлений [Зойтендейк, 1963; Гюрджиев, 1980]; сопряженных градиентов [Брайсон, Хо Ю-Ши, 1972; Федоренко, 1978].
В отдельную группу можно выделить методы, основанные на применении разнообразных алгоритмов нелинейного программирования к конечномерным представлениям задач оптимального управления [Евтушенко, 1982; Моисеев, 1975; Мордухович, 1980; Пшеничный, Данилин, 1975].
Еще одну группу составляют метод вариаций в фазовом пространстве [Васильев Ф.П., 1980; Моисеев, 1964, 1966, 1975; Федоренко, 1978] и его разновидности: метод локальных вариаций [Крылов, Черноусько, 1966; Черноусько, Баничук, 1973] и метод блуждающей трубки [Моисеев, 1966].
Открытый Л.С. Понтрягиным принцип максимума широко используется для построения вычислительных методов решения задач оптимального управления [Аргучинцев, Васильев О.В., 1996; Васильев О.В., 1994; ВасильевО.В., Бельтюков, Терлецкий, 1991; Васильев О.В., Надежкина, 1996; ВасильевО.В., Срочко В.А., Терлецкий, 1990; Васильев О.В., Тятюшкин, 1981, 1983; Васильев Ф.П., 1980, 1981; Любушин, Черноусько, 1983; Моисеев, 1975; Срочко, 1989; Федоренко, 1978; Черноусько, Колмановский, 1977]. Эти работы наиболее полное отражение нашли в монограмме В.А. Срочко [Срочко, 2000]. Простейший алгоритм предложен в работе [Крылов, Черноусько, 1962], он предусматривает последовательное интегрирование исходной и сопряженной систем и выбор управления из условия максимума функции Понтрягина. Метод далеко не всегда сходится, однако известны его модификации, обладающие релаксационностью и сходимостью [Крылов, Черноусько, 1972; Любушин, 1979, 1982; Цирлин, Балакирев, Дудников, 1976].
Вывод формул для производных функционала по компонентам параметра в алгоритме сильного улучшения
Первая глава носит вводный характер. В разделе 1.1 приводится постановка задачи оптимального управления со свободным правым концом, понятие улучшения и метода локализации, принцип расширения и достаточные условия Кротова. В разделе 1.2 излагаются методы сильного и слабого улучшения второго порядка для поставленной задачи оптимального управления. Раздел 1.3 посвящен исследованию задачи с параметром.
В разделе 2.1 сформулирована постановка задачи управления параметрами алгоритма улучшения и изложен общий подход к решению этой задачи. Остальные разделы второй главы направлены на реализацию предложенного подхода применительно к алгоритму слабого улучшения второго порядка: выведены формулы для производных функционала по компонентам параметра, предложены новые алгоритмы, исследованы их свойства.
Третья глава посвящена реализации предложенного подхода применительно к алгоритму сильного улучшения второго порядка: выведены формулы для производных функционала по компонентам параметра, предложен новый алгоритм, доказана его релаксационность.
В четвертой главе дано описание комплекса программ для решения задачи оптимального управления со свободным правым концом с помощью алгоритмов последовательных улучшений, изложенных в главе 1, и с помощью алгоритмов, предложенных в главах 2 и 3. На серии тестовых задач проводятся вычислительные эксперименты и сравнение исходных и разработанных алгоритмов. Также приведены результаты решения практической задачи управления эколого-экономической моделью.
В заключении излагаются основные результаты диссертации. Научная новизна. Все результаты, полученные в работе автором, являются новыми. К ним относятся формулы для производных функционала по компонентам параметра, новые алгоритмы, исследование их свойств, решение тестовых примеров.
Практическая ценность. Разработанные алгоритмы могут использоваться при решении различных прикладных задач (технических, экономических, природно-экономических и др.). Работоспособность и эффективность этих алгоритмов подтверждена рядом тестовых примеров.
Апробация работы. Основные результаты работы докладывались и обсуждались на первой конференции молодых ученых Иркутского государственного университета (Иркутск, 1983), на второй конференции молодых ученых ИГУ (Иркутск, 1984), на Всероссийской конференции «Инфокоммуникационные и вычислительные технологии и системы» (Улан-Удэ, 2003), на Ляпуновских чтениях (Иркутск, 2003), на региональной конференции молодых ученых «Филология и современное лингвистическое образование» (Иркутск, 2004), на семинаре «Приближенные методы и алгоритмы оптимального управления», проводимого в рамках симпозиума IFAC по обобщенным решениям в задачах управления (GSCP-2004) (Переславль-Залесский, 2004), на Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании» (Алматы, 2004), на VII школе-семинаре «Математическое моделирование и информационные технологии» (Иркутск, 2005), на IV Всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005), на семинарах лаборатории «Системного анализа и методов оптимального управления» и Объединенном семинаре ИДСТУ СО РАН. Основное содержание диссертации опубликовано в работах [Батурин, Черемных, 1983, 1984, 2002, 2003, 2004, 2006; Черемных, 2004; Baturin, Cheremnykh, 2004].
Задача управления эколого-экономической моделью
Таким образом, актуальной является проблема управления параметрами алгоритма, в частности, проблема автоматизации поиска наилучших значений параметров на каждой итерации.
Краткий обзор. Разнообразие задач оптимального управления, возникающих в практической деятельности людей, и различные подходы к их решению обусловили создание разных групп методов (алгоритмов, вычислительных процедур). Один из таких подходов заключается в распространении на задачи оптимального управления методов, основанных на необходимых условиях оптимальности.
Большую группу составляют методы градиентного типа [Брайсон, Хо Ю-Ши, 1972; Васильев О.В., 1994; Васильев О.В., Аргучинцев, 1999; Келли, 1965; Кротов, Гурман, 1973; Полак, 1974; Сеа, 1973; Федоренко, 1978; Шатровский, 1962; Энеев, 1966]. При наличии ограничений на управление и фазовые переменные в градиентных методах первого порядка возникают трудности, которые преодолеваются путем модификации алгоритмов. Некоторые модификации связаны с методом штрафных функций [Гермейер, 1971], другие — это методы спуска в пространстве управлений, представляющие собой аналоги методов конечномерной оптимизации: условного градиента, проекции градиента [Демьянов, Рубинов, 1968; Федоренко, 1975], возможных направлений [Зойтендейк, 1963; Гюрджиев, 1980]; сопряженных градиентов [Брайсон, Хо Ю-Ши, 1972; Федоренко, 1978].
В отдельную группу можно выделить методы, основанные на применении разнообразных алгоритмов нелинейного программирования к конечномерным представлениям задач оптимального управления [Евтушенко, 1982; Моисеев, 1975; Мордухович, 1980; Пшеничный, Данилин, 1975].
Еще одну группу составляют метод вариаций в фазовом пространстве [Васильев Ф.П., 1980; Моисеев, 1964, 1966, 1975; Федоренко, 1978] и его разновидности: метод локальных вариаций [Крылов, Черноусько, 1966; Черноусько, Баничук, 1973] и метод блуждающей трубки [Моисеев, 1966].
Открытый Л.С. Понтрягиным принцип максимума широко используется для построения вычислительных методов решения задач оптимального управления [Аргучинцев, Васильев О.В., 1996; Васильев О.В., 1994; ВасильевО.В., Бельтюков, Терлецкий, 1991; Васильев О.В., Надежкина, 1996; ВасильевО.В., Срочко В.А., Терлецкий, 1990; Васильев О.В., Тятюшкин, 1981, 1983; Васильев Ф.П., 1980, 1981; Любушин, Черноусько, 1983; Моисеев, 1975; Срочко, 1989; Федоренко, 1978; Черноусько, Колмановский, 1977]. Эти работы наиболее полное отражение нашли в монограмме В.А. Срочко [Срочко, 2000]. Простейший алгоритм предложен в работе [Крылов, Черноусько, 1962], он предусматривает последовательное интегрирование исходной и сопряженной систем и выбор управления из условия максимума функции Понтрягина. Метод далеко не всегда сходится, однако известны его модификации, обладающие релаксационностью и сходимостью [Крылов, Черноусько, 1972; Любушин, 1979, 1982; Цирлин, Балакирев, Дудников, 1976].
Для линейных и выпуклых задач оптимального управления принцип максимума Л.С. Понтрягина является не только необходимым, но и достаточным условием оптимальности. Поэтому во всех случаях, когда управляемые процессы можно с достаточной степенью точности моделировать (аппроксимировать) линейными уравнениями, целесообразно применять методы, ориентированные на решение задач оптимального управления для линейных систем [Габасов, Кириллова, 1973, 1981, 1983; Еремин, Астафьев, 1976; Оптимальное управление ..., 1993] и методы линеаризации [Федоренко, 1978].
В работах [Аэродинамика, 1968; Jacobson, 1968] предложены методы, основанные на разложении до второго порядка включительно функции Беллмана и левой части уравнения Беллмана. Для обеспечения близости соседних приближений предлагается применять процедуру не на всем отрезке 70,/,], а на последней его части [г,?,], при этом г выступает в
алгоритме как регулятор.
