автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Численные методы решения задач оптимального управления с использованием дискретной аппроксимации

На правах рукописи

ЧЕКАРЕВ Денис Анатольевич

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ С ИСПОЛЬЗОВАНИЕМ ДИСКРЕТНОЙ АППРОКСИМАЦИИ

Специальность 0"5 13 18 - «Математическое моделирование, численные методы и

комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена на кафедре высшей математики Московского физико-технического института (государственного университета) Научный руководитель. член-корреспондент

Российской академии образования, доктор физ.-мат. наук, профессор

Яковлев Геннадий Николаевич

Официальные оппоненты доктор физ -мат. наук,

профессор

Абрамов Александр Петрович

кандидат физ.-мат. наук, доцент

Бирюков Александр Гаврилович

Ведущая организация' Институт Проблем Управления

Российской Академии Наук

Защита состоится « июкл 2005 г в у7 на заседании

диссертационного совета К 212 156.02 при МФТИ в Московском физико-техническом институте по адресу 141700, г Долгопрудный Московской обл , Институтский пер , д.9

С диссертацией можно ознакомиться в библиотеке МФТИ

Автореферат разослан « ЛиЗЛ 2005 г

Ученый секретарь кандидат физ -мат. наук диссертационного советае^у-—г_---^Федько О С

83 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Данная работа посвящена разработке и исследованию свойств методов решения линейных задач оптимального управления (ОУ) со смешанными ограничениями. Предположение о линейности, хотя и сужает область применимости предлагаемого подхода, но, тем не менее, позволяет получать практически значимые результаты при исследовании широкого класса динамических моделей, поскольку во многих случаях такое исследование сводится к решению линейных задач ОУ Для решения задач ОУ в настоящее время широко применяются различные модификации метода «прогонки», а также численные методы решения задач ОУ, использующие сведение к конечномерным задачам нелинейного программирования, наиболее весомый вклад в развитие которых внесли- Ю Г Евтушенко, В Г Жадан, Б Т Поляк, А И. Голиков, В.В. Дикусар, А.Е Умнов, И.И Еремин, В Д Мазуров, Н Н Астафьев, О.Л. Мангасарьян и другие

Эффективность этих методов для задач с ограничениями на управления (класс задач Л.С. Понтрягина) подтверждена экспериментально и не вызывает сомнений. При этом, однако, наличие смешанных ограничений, зависящих как от фазовых переменных, так и от управлений, существенно усложняет структуру задачи, и в ряде случаев приводит к возникновению дополнительных вычислительных затруднений. Можно констатировать, что развитые к настоящему времени практически эффективные схемы решения задач ОУ этого класса либо в основном базируются на использовании специфики их условий (например, на априорном предположении о поведении оптимального управления), либо требуют альтернативных вычислительных подходов. В этой ситуации вопрос построения практически эффективной вычислительной схемы решения задач ОУ со смешанными ограничениями остается актуальным и сегодня.

В общем случае такая система должна

позволять находить приближенное численное решение задачи ОУ,

допускать проверку допустимости и оптимальности полученного решения,

кроме того, при необходимости, обеспечивать построение аналитического решения методом формулировки и проверки гипотезы о геометрии оптимальной траектории.

Следует отметить, что исследуемая в диссертации методология решения задач ОУ со смешанными ограничениями позволяет не только находить оптимальные решения, но и исследовать такие их характеристики как чувствительность и устойчивость по параметрам Понятно, что это

СОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

существенно улучшает качество и облегчает интерпретируемость получаемых решений Наконец, оказывается возможным ставить и решать задачи поиска оптимальных параметров модели, при которых значение целевого функционала достигает своего экстремума

Цель и задачи исследования

Основная цель исследования состоит в разработке и обосновании методики решения линейных задач ОУ со смешанными ограничениями, в обосновании оптимальности получаемых решений, а также в анализе условий сходимости схем численного решения задачи к точному решению исходной задачи.

Предлагаемый в диссертации подход основан на сведении линейных задач ОУ к задачам линейного программирования (ЛП) в конечномерных пространствах дискретизацией по времени и последующем решении получающихся задач ЛП В работе предлагается схема, позволяющая за счет использования специальных аналитических и программно-вычислительных инструментов преодолевать возникающие вычислительные проблемы, обусловленные недостаточной точностью стандартных схем компьютерных вычислений, вызываемых чрезвычайным ростом размерности возникающих задач ЛП. Кроме того, работа имеет своей целью показать практическую эффективность предлагаемой методики с точки зрения затрат вычислительных ресурсов.

Для контроля оптимальности и исследования свойств исходной задачи ОУ в диссертационной работе применен подход, основанный на одновременном рассмотрении пары задач ОУ- исходной и двойственной к ней задаче ЛП в банаховом пространстве

В соответствии с целью исследования поставлены и решены следующие задачи:

1. Разработка численно-аналитической схемы решения линейных задач оптимального управления со смешанными ограничениями, основанных на совместном решении пары задач ОУ, сводимых к двойственным задачам ЛП в банаховых пространствах;

2. Анализ и приведение к виду, удобному для использования, необходимых и достаточных условий экстремума в рассматриваемых задачах;

3. Обоснование алгоритма решения исходной задачи ОУ, включающего построение и проверку гипотезы о геометрии оптимальных траекторий, возможно, с использованием принципа максимума Л С. Понтрягина;

4. Компьютерная реализация предлагаемого подхода и исследование его эффективности при решении конкретных задач оптимального управления;

5. Исследование способов повышения качества численных приближенных решений задачи ОУ, включая разработку компьютерной арифметики повышенной точности;

6. Анализ сходимости и устойчивости дискретной аппроксимации исходной задачи, включая методы параметрической оптимизации получаемых решений.

Объект исследования

Объектом исследования является линейная математическая модель обслуживания внешнего государственного долга в условиях двухсекгорной экономики.

Предмет исследования

Предметом исследования является процесс решения линейной параметрической задачи ОУ со смешанными ограничениями.

Теоретические и методологические основы исследования

Теоретическую и методологическую основу диссертации составляют труды российских и зарубежных ученых-математиков по методам решения задач ОУ, задач ЛП, методам оптимизации, теории машинных вычислений В основном используются результаты исследований В В Дикусара. Ю Г Евтушенко, А.М Тер-Крикорова, схема Дубовицкого-Милютина

Научная новизна исследования

В диссертационной работе предложена схема решения линейных задач ОУ со смешанными ограничениями, основанная на совместном численном решении пары задач, сводимых к задачам ЛП в банаховых пространствах по результатам работ A.M. Тер-Крикорова и схемы Дубовицкого-Милютина Модифицированы достаточные условия оптимальности линейной задачи ОУ

со смешанными ограничениями типа равенства и неравенства, допускающей уменьшение размерности вектора управлений за счет исключения ограничений типа равенства Разработана методика численного решения, позволяющая решать линейные задачи ОУ со смешанными ограничениями, основанная на предложенной схеме Основой предложенного подхода является использование дискретной аппроксимации пары задач ОУ с фазовыми и смешанными ограничениями и последующего решения пары конечномерных задач ЛП Показано, что на основе разработанной схемы возможно обобщение линейной задачи ОУ со смешанными ограничениями путем превращения коэффициентов задачи в параметры Приведено обоснование сходимости численного решения задачи ОУ со смешанными ограничениями к оптимальному

Практическая значимость

Модели, методы и алгоритмы, разработанные в исследовании, применялись для решения различных задач моделирования экономических процессов в Московском физико-техническом институте и в Вычислительном Центре РАН с 1999 по 2004гг

Предложенная методика может эффективно применяться в прикладных задачах Результаты работы могут быть использованы в научных исследованиях и практических решениях задач в таких организациях, как ВЦ РАН, ИММ РАН, МФТИ.

Публикации

Основные результаты исследования опубликованы в десяти работах Апробация результатов исследования

Основные положения исследования докладывались и обсуждались на ХЫП и Х1_У1 научных конференциях МФТИ в 2000 и 2003гг Результаты исследования докладывались на заседаниях научного семинара кафедры высшей математики МФТИ, научного семинара ВЦ РАН под руководством член-корр РАН Ю Г Евтушенко, научных семинарах в отделе проблем моделирования и в отделе методов нелинейного анализа Вычислительного Центра РАН

Структура и объем работы

Диссертация состоит из пяти глав, приложения и заключения Основное содержание диссертации изложено на 99 страницах печатного текста. Список использованной литературы составляет 50 наименований

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В настоящей работе предложен численный метод решения линейной задачи ОУ со смешанными ограничениями, основанный на дискретизации по времени пары связанных линейных задач ОУ Кроме того, для решения линейной параметрической задачи ОУ со смешанными ограничениями предлагается способ, основанный на многократном решении линейных задач ОУ при различных фиксированных параметрах, когда решение, полученное при данных значениях параметров, дает информацию для следующего выбора новых значений параметров Когда параметры задачи фиксированы, то задача превращается в линейную задачу ОУ Поэтому основной акцент в работе сделан на разработку эффективных способов решения линейных задач ОУ со смешанными ограничениями.

В первой главе «Введение» изложены обоснование предмета и цели исследования, обзор литературы по данному вопросу и основные результаты, выносимые на защиту, характеристика их научной новизны, практической значимости и апробации полученных результатов, дается краткое описание моделируемой системы оптимального управления внешним долгом.

Вторая глава «Математическое моделирование линейных динамических систем со смешанными ограничениями» посвящена постановке задачи ОУ со смешанными ограничениями, для которой формулируются необходимые условия оптимальности с использованием принципа максимума Понтрягина и формализма Дубовицкого-Милютина Далее рассматриваются линейные задачи ОУ со смешанными ограничениями как частный случай задачи ОУ. Для линейного случая

]УТ(1)х(1)+еТ(<)иф + Хгх(Г)^ т.п (2 3 1)

о

при условиях

т = А(1)х(1) + В(1)и(1) + /(/), х(0) = х0 , х(Т) е 5, (2 3 2)

5 = {г 6 Л" | ГЬг + /3 = о}, К(х,/)=£/еЛ' |С(0*(0+ К(0"С)+ «■(') 2 о}, л

необходимые условия оптимальности имеют вид

л,схем*«+тт+«-с»; =о, ддо>о, /е[о,г], (2 4 5)

Г0еЧ1)+</Т(1Щ1)+Лтт(0=0, (2 4 б)

й{/) = агй шах^0(сГ(1)х(1) + е7(/МО) + у7т(/)(Л(/)х'(/) + £(/)>•(/) +/(»)), (2 4 7)

где вектор i/(i) является решением системы уравнений

«*г=-Мт(/)-рт(/)Л(/)+Ат(/)С(/), V„s0, (2.4 3)

с условиями

ут(Г)-Го*Г=С,ТП (2.4.4)

Далее рассматриваются достаточные условия оптимального управления, основанные на методике сведения линейной задачи ОУ со смешанными ограничениями к задаче ЛП в банаховых пространствах, предложенной AM Тер-Крикоровым в книге «Оптимальное управление и математическая экономика» (М • Наука, 1977) Эти условия приводятся ниже (теорема 1) в терминах пары задач А и Б.

Рассматриваются две задачи

Задача А

Найти управления ¡/(í)e ¿*[о,7"], дающие максимум линейному функционалу

y

j{u')=*'(7> +}[*'('>(/) + !/* (ф(/)]л->тах, (2 5 1)

о

при следующих ограничениях

х =x'A(t)+u'B{l)+a'(l), (2 52)

Jt'(0) = a', x'{T)Q>c\ (2 5 3)

-x'C(t)+u'D(t)<b'(l),u'>0 (2.54)

Матрицы A(t), B(t), C(t) и D(t) и векторы a'(t), b'(t) имеют ограниченные измеримые компоненты Соответствующие матрицы и векторы имеют следующие размеры А[пхп\, В[тхи], С[ихг], D[mxr], Q[nxq], а*[п], b*[г], а[л], с*[g] Векторы с символом * являются строками, без - столбцами

Задача Б

Найти управления v(i)e L], [о,г], i] е Rq, дающие минимум линейному функционалу

J(v) = a * а (0) — с "/7 H- J [/?* (л +бг*(/)д р/ —> min (2 5 5)

(i

при аедующих ограничениях

-х = A{t)x + C(l)v + a(l), (2 5 6)

x{T) = a+Qr], (2 5 7)

-B(l)x + D(t)\'>b{l), v> 0 (25 8)

Достаточные условия оптимальности задач А и Б даются следующей теоремой:

Теорема 1 (AM Тер-Крикоров) Пусть для некоторых допустимых управлений ïï'(t) и v(i), r¡ задач А и Б выполнены условия

"Л" в{1)х + 0(/)у - г>(/)1 = 0, / = Гй, (2 5 9)

[-x'C(l)+й'D(l)-b'{t)\JvJ =0, у = й. (2 5 10)

=0,* = й, (2 5 11)

причем первые два равенства выполняются почти при всех I Тогда ¿7'(/), Зс'(г) будет оптимальным решением задачи А, а у(/), 7, *(/) будет оптимальным решением задачи Б.

Пусть в задаче А, рассматриваемой с точки зрения принципа максимума Понтрягина и формализма Дубовицкого-Милютина, вектору ограничений типа неравенства -х*С(/)+и*£(?)-6"(/)<0 соответствует вектор неотрицательных множителей Лагранжа 0, вектору ограничений типа неравенства -и' <0 соответствует вектор неотрицательных множителей Лагранжа //(/)> 0. Необходимые условия оптимальности для задачи А можно сформулировать в терминах принципа максимума Понтрягина с использованием сопряженных переменных ¡/(/) При этом связь сопряженных переменных 11/(1) и переменных задачи Б дается утверждениями:

Утверждение 1. Если при допустимом управлении задачи А существует вектор сопряженных переменных константа ц/0<0 и

векторы множителей Лагранжа Я(г), удовлетворяющие

дифференциальным уравнениям и краевым условиям для (2 4 3)-(2 4 4), условиям Блисса и условиям дополняющей нежесткости для Я(/), ¿1(1) (2 4.5)-(2.4.6), то Х{{) и у/{{) являются допустимыми управлением и фазовым вектором задачи Б.

Утверждение 2. Если существуют допустимые управления !/*(/), »(/), г] задач А и Б, и они удовлетворяют условиям (2.5.9)-(2.5 11), то вектор траектории л(/) задачи (2 5 5)-(2.5.8), соответствующей управлению у(/), является вектором сопряженных переменных 4/(1) задачи (2 5 1)-(2 5 4) при Со =-1

Приведем условия (2 4 3)-(2.4 7) в терминах задачи А Дифференциальные уравнения и краевые условия для определения 4/(1) ян

= (2 5 12)

дх

дЬ дх (Г)

Условия Блисса принимают вид:

^ = -Ь(^+В(1Ы')-О(1)Я(1) + м(1) = 0, (2 5 14)

ди

а условия дополняющей нежесткости - соответственно

U'(')k(')=0. //,(/)£ 0, / = ПЯ _

l-/(r)C(/) + u,(0o(')-ft4')l^(i) = 0, Ay(i)>0, J = \,r, (2515)

На основании утверждений 1 и 2 теорема 1 имеет следующую формулировку.

Теорема 2. Ясли при данном допустимом управлении ü'(i) задачи А суи(ествуют число ц/0 = -1, кусочно-гладкая вектор-функция t//(t), измеримые вектор-функции Я(()>0, /j (i) > 0 и вектор ß >0 такие, что выполняются условия (2.5.12)-(2.5.15), то «"(/) - оптимальное управление задачи А

Таким образом, теорема 2 дает возможность использовать сопряженные переменные ty(t) для доказательства оптимальности полученного решения в задаче ОУ.

Третья глава «Решение линейных задач оптимального управления со смешанными ограничениями методом дискретизации по времени» в §3 1 описывает построение конечно-разностных аппроксимаций для задачи ОУ, в §3.2 приводится двухэтапная схема решения линейной задачи ОУ со смешанными ограничениями и описывается каждый этап схемы На первом этапе численно решается дискретный аналог непрерывной задачи ОУ Дискретное решение позволяет сформировать гипотезу о промежутках постоянства по времени множеств активных ограничений. На втором этапе по данной гипотезе строится аналитическое решение прямой и сопряженной задач, находятся времена переключений управлений и проверяются необходимые условия экстремума. В §3.3 для оценки погрешности, как по функционалу, так и по фазовым переменным, численного решения для метода дискретной аппроксимации рассматриваются задача ОУ

;(и(/)) = аЧ(Г)->тш, (3 3 1)

х = A{t)x + B(l)u +/(/), О <1<Т, (3 3 2)

x(0) = ß. Qx(T)>c, (3 3 3)

+ (3 3 4)

задача ЛП, получаемая из задачи ОУ дискретизацией по схеме Эйлера первого порядка точности'

j(u) = a'xN -»min, u = u°,...,uN, (3 3 5)

= У + h{A{ih)x' + B{ih)u' + f{ih)), i = 0,N~\, (3 3 6)

x°=ß, Qxn >c, (3 3 7)

ueUN = 6 Яг(Л,+1) | C.M*'+Д(/ЛУ <A,(/A), / = Öjv}, (3 3 8)

и доказывается следующая теорема

Теорема 1. Пусть все матрицы и столбцы в условии задачи (3 3.1)-(3 3 4) кусочно непрерывны на отрезке [0,7"], а функция f(i) удовлетворяет \сювию Липшица с константой Lf на [о,г]' |/(/,)-у(/2)||<-/2| Пусть

u(t)eU, Vie[0,7"], где U - выпуклый компакт. Пусть существует такое допустимое управление «(/) задачи, что набор управляющих и фазовых переменных й(г), х(/) принадлежит e-сужению G~e(i) допустимого множества G(t) с непустой внутренностью при некотором малом е>0. Тогда существует решение дискретной задачи ЛП (3 3.5)-(3.3.8) при всех достаточно больших N, и lim e(w,) = J,.

В §3 4 для задач, в которых смешанные ограничения присутствуют также в виде равенств'

x'C2(t)+uD2{l) = b'2(t), (3 4 5)

показано, что теорема 1 оказывается справедливой при выполнении условий теоремы:

Теорема 2. Пусть рассматривается линейная задача ОУ со смешанными ограничениями типа равенства и неравенства (3 4 1)-(3,4 5) Пусть в любой момент времени можно разрешить все г2 ограничений типа равенства относительно г2 из т управлений (г2<т)

%=%(*>">'), J = \7г (3.4.6)

Далее, пусть при подстановке выраженных таким образом ик в ограничения типа неравенства (3 4 4) получаются неравенства относительно п + т-г2 переменных (п переменных х и т-г2 переменных и), причем на оставшиеся управления накладываются условия неотрицательности

u,>0,i*kJ,4j = \J1 (3.4 7)

Получившаяся таким образом задача имеет форму задачи А, следовательно для нее можно сформулировать задачу Б. Пусть для некоторых допустимых управлений задач А и Б выполнены условия теоремы 1, то есть получены оптимальные управления и фазовые переменные задачи А Тогда подстановкой их в выражения (3 4 6) получаются оптимальные управления и фазовые переменные исходной задачи

Далее предлагается следующая схема (метод) решения линейных задач ОУ со смешанными ограничениями Рассматривается задача без ограничений типа равенства, либо с ограничениями типа равенства, удовлетворяющими теореме 2, т е задача, которая сводится к задаче А, или изначально является задачей А. Для этой задачи составляется задача Б. Обе эти задачи являются линейными задачами ОУ со смешанными ограничениями типа неравенства. Для них одинаковой дискретизацией по времени выписываются задачи ЛП Одинаковая дискретизация означает применение одной и той же схемы дискретизации для обеих задач. После решения этих задач получаются численные дискретные траектории, на которых проверяются условия (2.5.9)-(2 5 11), и если эти условия выполняются, а функционалы задач отличаются незначительно, то полученное численное решение дискретной задачи дает достаточное приближение к точному решению непрерывной задачи. Таким образом отпадает необходимость нахождения аналитического решения

задачи Одним из достоинств данного метода является возможность получения численных оценок сверху и снизу значения целевого функционала решаемой задачи, а также проверка в каждой точке дискретизации достаточного условия оптимальности решения.

В §§3 5-3.6 описаны применения схем дискретизации различных порядков точности на основе схем Рунге-Кутта для получения численного решения задачи ОУ Показано, что в случае существования устойчивого решения задачи ОУ применение схем высших порядков точности не дает значительного увеличения точности численного решения. Аналогичный результат для задачи ОУ без смешанных ограничений получен в книге Ю.М Ермольева, В П Гуленко, Т И. Царенко «Конечно-разностный метод в задачах оптимального управления» (К., «Наук, думка», 1978). Схемы высших порядков точности имеет смысл применять, если численное решение будет сразу применяться на практике, без решения сопряженной задачи и нахождения точных времен переключений (то есть времена переключений приближенно находятся по численному решению). Дело в том, что получение аналитического решения представляет определенные сложности, а именно, для построения аналитического решения (рассматривается в главе 4) требуется проделать несколько трудоемких шагов Первое: строить функцию Понтрягина, функцию Гамильтона, систему дифференциальных уравнений для сопряженных переменных, выписывать условия Блисса и условия дополняющей нежесткости для определения множителей Лагранжа, определять краевые условия для сопряженных переменных. Второе: аналитически интегрировать исходные и сопряженные дифференциальные уравнения на каждом промежутке постоянства множеств активных ограничений, при этом используются условия непрерывности фазовых и сопряженных переменных в моменты переключений (изменений множеств активных ограничений) Третье- решать трансцендентные уравнения для точного определения времен переключений Временные затраты при этом значительно превосходят затраты на дискретизацию исходной задачи и решение получившейся задачи ЛП

Наряду с применением различных схем дискретизации, как возможность повышения качества численного решения, исследовалась и разностная схема с переменным шагом Именно, фиксировалось два возможных шага' Илеут и В каждом узле дискретизации шаг, т е

расстояние до следующего узла, выбирался из этих двух величин. При этом крупный шаг дискретизации применяется внутри промежутков, где существует только один вариант гипотезы о поведении оптимальной траектории. Малые шаги дискретизации выбирались в окрестности точек,'для которых дискретизация с постоянным шагом не давала однозначной гипотезы поведения оптимальной траектории. Сгущения узлов дискретизации в окрестности неоднозначных точек позволяют ответить на вопрос, что происходит с управлениями на некотором промежутке - быстрый рост или скачок Кроме того, сгущения узлов дискретизации позволяют более точно оценить моменты переключений.

В §3.7 приведено полное описание класса чисел повышенной точности на С++, являющегося авторской разработкой Данный класс позволяет проводить вычисления с большей точностью, чем базовые классы языка С Так, стандартный тип языка С double позволяет проводить вычисления с точностью 15 десятичных знаков, новый класс чисел повышенной точности обеспечивает точность 36 десятичных знаков В рамках данного класса реализовано 4 арифметических операции и вспомогательные операции ввода-вывода из/в стандартные типы языка С. При создании этого класса использовалась теория точных компьютерных вычислений, описанная во втором томе «Получисленные алгоритмы» книги Д Кнута «Искусство программирования для ЭВМ» (МИР, 1977) Удобство работы с классом обеспечивается переопределением всех арифметических операций и отсутствием необходимости проводить инициализирующие вызовы при динамическом создании объектов данного класса При использовании данного Данный класс может использоваться в любых пользовательских программах, написанных на языке С++ вместо стандартного типа float (double) простым переопределением типа.

На рисунках приведены графики десятичных логарифмов относительных погрешностей решений систем линейных уравнений (СЛУ) с матрицами Гильберта и Годунова для старого и нового классов

100 '

»1д(мов) ....... 1д(ст)-eps-0 001

Рис 1 логарифмы относительных погрешностей Рис 2 логарифмы относительных погрешностей

решений СЛУ с матрицей Гильберта решений СЛУ с матрицей Годунова

В §3 8 приводится анализ устойчивости дискретной аппроксимации задачи ОУ (т е. задачи ЛП), осуществляемый с помощью критерия оптимальности. На основании определения устойчивого решения, как решения, в котором при вариациях параметров задачи множества индексов базисных и небазисных переменных остаются неизменными, формулируются и доказываются теоремы о необходимых и достаточных условиях устойчивости для общей задачи ЛП и задачи ЛП в канонической форме В работе приведен пример устойчивого и неустойчивого решений дискретизированной задачи ОУ.

Основные результаты третьей главы опубликованы в работах [1], [2], [4], [7], [9].

В четвертой главе «Применение метода дискретной аппроксимации для параметрических динамических моделей обслуживания внешнего государственного долга» дается постановка и решение задачи ОУ внешним долгом на модели, являющейся развитием

моделей, построенных В В Дикусаром и С.Ю. Синягиным, а также описанных в [3]

Модель рассматривается на отрезке времени 0 < / < 7* = 100. Модель описывает двухсекторную экономическую систему, первый сектор которой добывает ресурсы, а второй производит продукцию конечного потребления (фондообразующую). Погашение внешнего долга происходит за счет экспорта продукции первого сектора (экспорт ресурсов). Общий объем вложенных средств в первый (второй) сектор к моменту времени / описывается фазовой переменной х,(/) (х2(/)). Общий объем износа (амортизации) фондов первого (второго) сектора к моменту времени / описывается фазовой переменной х„(/) (*5(/)). Объем внешнего долга в момент времени / описывается фазовой переменной х3(г). Управление «,(/) (г/,(/)) задает скорость вложения импортной фондообразующей продукции в первый (второй) сектор. Управление и2(г) (и4(0) задает скорость вложения отечественной фондообразующей продукции в первый (второй) сектор При этом фондовооруженность соответствующего сектора возрастает. Снижение фондовооруженности секторов происходит при производстве ими продукции, и является прямо пропорциональным объему произведенной продукции с коэффициентом пропорциональности Д (/?2) для первого (второго) сектора. Внутреннее потребление не может быть ниже некоторого уровня (задается константой с) и складывается из импорта и продукции второго сектора Кроме того, сумма вложений, отечественной продукции в оба сектора не может быть больше объема продукции, произведенной вторым сектором Максимальные объемы производства продукции обоих секторов зависят от их фондовооруженностей В модели принята линейная зависимость максимальных объемов производства от фондовооруженности с коэффициентом пропорциональности а, (а2) для первого (второго) сектора Наконец, увеличение внешнего долга происходит за счет импорта фондообразующей продукции в оба сектора, за счет затрат на обслуживание долга (проценты), и за счет импорта товаров потребления Уменьшение внешнего долга происходит за счет экспорта продукции первого сектора, с коэффициентом , описывающим разницу внутренних и внешних цен Минимизируемый функционал (внешний долг) ■/(*,«) = х3(Ю0)

Система дифференциальных уравнений и ограничения задачи

*з = Язхз + и\ + "з + "> - к\иЬ'

X, =и, +и2, X, =«, +м41

/ = 1,7,

щ <, аг(х2 - х,),

¿4 =

*5 = А" 7.

«2 +И4 < И7,

Ц2 + И4 + С й И, + 1/5

Значения коэффициентов задачи, начальных и конечных условий

а. = 0 03, *,(0)=*,„=25, = о, / = 1,7,

«2 = 0 03, х;(0)=х:п =15, "|пмх = ")т>* = 0 1,

Д = 0.18, г,(0)=*,„=400, »2^=0 5,

Pi = 0.18, ^(0)=х4О=0, U4ma = M5mtx = 0 3,

к\ = 0.9, *,(о)=х,0 =0, ~~ тех = 2 0,

И 3 = 0 002, ху(Г)-хА{Т)=Ри= 25, с = 0 2

Г = 100, х, (Г) - х, (Т) = F2, =15,

Данная задача имеет форму (3 3 1 )-(3 3 4) при п = 5, m = 7, A(t) - А = comí, B(i) = В = const, /(/) = 0. Если при дискретизации отрезок интегрирования разбивается на N равных отрезков, и дифференциальные уравнения (3.3.2) заменяются конечно-разностными отношениями, то получается дискретная задача ОУ вида (3 3 5)-(3 3 8), которая эквивалентна задаче ЛП размерности 12 • (N +1)

Наряду с исходной задачей рассматривалась связанная с ней задача

ОУ:

j(y/,v,r¡)-> min ,

5 г

i.l о

=«!vi. = (fj + vs >0,

-V,+v3 + V4+V620, -(/,=^3, ^,(7")=-l, +v7ä 0,

V4(7')=-7I+'72. -V;+"3 + v4+v8 SO,

-Гs = -a2Vj, y/¡(r)=-r],+ъ, -y,-v„+v, >0,

- ßyV> + v, + v,0 > 0, - + v2 - v, - v4 + v„ > 0 В этой задаче все коэффициенты берутся из исходной задачи (вот почему эти две задачи являются связанными)

При численном решении обеих задач проводилась дискретизация по времени как с использованием явной схемы Эйлера первого порядка точности, так и с использованием модифицированной схемы Эйлера второго порядка точности. Разностные уравнения для этих схем имеют вид

x'+1 = JC' +fi(Ax' +Ви') и x'^=x'+^[ax' +Bu'+a(x' +h(Ax' + Яы'))+Ям'+1],

/ = 0,N-1. Решения по разным схемам отличались только в моментах переключений, на промежутках непрерывности управлений отличия были в пределах погрешностей Для решения построенных задач ЯП был создан программный комплекс «MultiLc», ядром которого является программа «Баланс-2», использующая прямой симплекс-метод Система «MultiLc» работает под платформой Win32, может решать задачи ЛП с большим числом переменных, использует класс чисел повышенной точности для уменьшения ошибок округления, позволяет создавать, запускать и анализировать набор численных задач с различными значениями параметров

Для организации ввода-вывода данных дискретных аппроксимаций задач ОУ был применен Язык генерации линейных моделей Ь (представляющий собой модифицированное подмножество языка С++)

Система позволяет удобно описывать и решать дискретные аппроксимации задач ОУ при большом числе точек дискретизации и, следовательно, при большой размерности задачи ЛП Решение и> = и0, х°, и", х" задачи ЛП показано на рис. 3-6.

415л

410 405 400 395 3901,4 1,2 1

0,8 0.6 0.4 0,2 о

0 20 40 60 80 100 Рис 3 Фазовые переменные х,, х2, х*, х5

од.

0,5 0,4 0,3 0,2 0,1 о

0 20 40 60 80 Рис 4. Фазовая переменная х3

100

. . иг.___.

___J&

К

иЗ_

0 10 20 30 40 50 60 70 6( Рнс 6 Управления U6, ш

90 100

0 Ю 20 30 40 50 60 70 ВО 90 100 Рис S Управления Ui-Us

Решение дискретной аппроксимации связанной задачи показано на рис 7-9 Фазовые переменные y/x...y/s являются сопряженными переменными, а управления v,... vn - множителями Лагранжа для исходной задачи.

Рис 7 Сопряженные переменные ViW-VsW

Рис 8. Управления v, -v4

0 368

0.364 0.36 0 3S6

0 352

О 20 40 60 80 100 Рис 9 Управления v5-v„ Рис 10 Функция Потретииа H(t)

Аналитическое решение для данной модели построено на основе принципа максимума Понтрягина. Высказана гипотеза о том, что траектория системы состоит из пяти промежутков постоянства индексов активных ограничений На каждом промежутке из активных ограничений выражались управления и аналитически решалась задача Коши, при этом момент времени переключения полагался параметром Сопряженная система интегрировалась справа налево, с параметрами, являющимися моментами времен переключений Значения времен переключений определялись из решения трансцендентных уравнений, связывающих фазовые переменные и сопряженные переменные задачи. Вычисления проводились в пакете Maple 9 Полное решение задачи приведено в диссертации. Сопряженные переменные задачи являются кусочно-гладкими функциями и, в соответствии с утверждениями 1 и 2 гл. 2, полностью совпадают с фазовыми переменными (/,(/),..., y/s (t) связанной задачи. Функция Понтрягина приведена на рис 10

В работе проведено сравнение численного решения и аналитического, показавшее высокую точность численного решения. Для этого брались значения аналитического решения в те моменты времени, в которых получено численное решение. В результате получаются две таблицы, в первой из которых находятся значения аналитического решения в моменты времени t, = ih, / = 0,N, а во второй находятся значения численного решения При этом становится возможным найти абсолютную и относительную погрешности численного решения. На приведенных ниже рисунках представлены относительные погрешности фазовых переменных г,(/), , \Д/) и абсолютные погрешности управлений и,,...,«,-

х1 ~х2 хЭ -Х4 -х5

Рис 11 Относительные погрешности фаз Рис 12 Абсолютные погрешности управлений

Как видно из рисунка, относительная погрешность по фазовым переменным не превышает 0 18% Для управлений приведены абсолютные погрешности, так как относительную погрешность по управлениям посчитать невозможно в силу того, что управления принимают нулевые значения на некоторой части отрезка интегрирования Максимальные значения управлений и,,...,и5 лежат в пределах 0.1-0.5, и из диаграммы видно, что в трех точках, являющихся точками переключения, величина погрещлости становится сравнимой с величиной управлений. Это объясняется тем, что найденные аналитически времена переключений отличаются от времен переключений, получаемых при численном решении на величину порядка шага дискретизации Если при этом происходит переключение управления с максимального значения до минимального (или наоборот), то погрешность в данной точке сразу становится равной скачку управления. То есть, численное управление уже совершило скачок, а аналитическое - еще нет. Для получения картины поведения абсолютной погрешности управлений следует убрать из рассмотрения получающиеся таким образом скачки Тогда абсолютные величины погрешностей по управлению принимают вид:

Рис 13 Погрешности управлении и,,

Рис 14 Погрешности управлений г/6,г/,

Как видно из рисунков, без учета погрешности из-за отличия моментов переключений, абсолютные погрешности не превышают 0.001. Если взять максимальные значения управлений и для каждого управления разделить абсолютную погрешность на возможное максимальное значение этого управления, то получим, что такая величина меньше 0.003 для всех управлений.

Также произведено исследование задачи по параметру. Для этого рассматривалась некоторая модификация задачи, выражающаяся в том, что коэффициенты и Д2 уже не являлись постоянными во времени, а представляли собой прямоугольные импульсы постоянной длины 1 = 5. Начала импульсов jk и }Ъ2 являлись параметрами задачи (¡к задает цачало скачка по коэффициенту «■,, ,)Ь2 - по коэффициенту рг). Внутри импульсов коэффициенты к-, и р2 имели значения = 0 99, /?2 =01, вне импульсов -стандартные значения задачи к,= 0.9, Д, =018. Значения целевого функционала при различных значениях параметров приведены на рис 15.

Рис 15. Значения целевого функционала при разных значениях параметров задачи

Основные результаты четвертой главы опубликованы в работах [3], [8], [5], [6].

В пятой главе «Применение предложенной методики для решения других практических задач» приводится модель прогнозирования обслуживания внешнего долга с актуализированными данными. По оценке министра финансов РФ Алексея Кудрина, сделанной им 11 февраля 2005, внешний долг России на начало 2005 года составил 115 млрд долл , средний уровень ставки по обслуживанию долга достигает 7,13% Объем ВВП за 2004 год в текущих ценах составил 580 млрд долл. Объем промышленного производства составляет порядка 27% По этим данным была построена модель прогноза обслуживания внешнего долга на 10 лет Динамические соотношения претерпели некоторые изменения, в модели учтены затраты энергоносителей и природного сырья (продукция первого сектора) при производстве продукции конечного потребления (второго сектора) Основные же изменения произошли в количественных показателях задачи

д= и, + и2, хг = и, + ut,

",n»n Z», * ' = 1.7, ut+run -хД

"7 Sa2(x2 -Jf5),

Ii j +M4 i «,, l/;+»4+CS U1 +«,

x}=fJ,x3+ul+u)+ui-Klu6

*4 = A(M6 +У"Л *5 =ßl" 7.

Значения коэффициентов задачи, начальных и конечных условий

а, =0.195, х,(0)=100, =0,1 = 1,7,

а: = 0 195, ' х2 (о) = 60, ~~ "згмх = 4.0,

А =0.2, х,(0)= 115, и2тю = 20.0,

А =02, *4(0)=0, и4тшх ~ иЬтлх = 12 0,

л-, =0 9, х,(0)=0. "бтм — = 20.0,

Мз = 0.07, *>(?)-х,{Т) = 110, с = 8.0.

Г = 0 5, 70,

Т = 10,

Результаты расчетов приведены ниже'

14

12 ------

10 -и1

-------и2

113

В

и4

4 -и5

2

1

0123456789 10

Рис 16 Внешний долг (хЗ), фондовооруженности Рис 17 Управления 11,-115

первого (Р1) и второго (Р2) секторов

На данных графиках показано, что при нынешнем уровне цен на нефть и производительности секторов минимально возможный внешний долг, который может остаться через 10 лет, будет около 91 млрд. долл. То есть, если данный прогноз не является приемлемым, то следует искать другие пути уменьшения внешнего долга за счет изменения остальных требований.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬ ТА ТЫ

Результаты проведенного диссертационного исследования позволили разработать комплексную численно-аналитическую методику решения линейных задач оптимального управления со смешанными ограничениями Данная методика позволяет получать решения задач ОУ, обосновывать их оптимальность и, при необходимости, выполнять исследование параметрической устойчивости и оптимизации по параметрам

В рамках предложенного подхода:

1. Разработан метод численного решения линейных задач ОУ со смешанными ограничениями, основанный на совместном решении пары дискретизированных задач ОУ

2 Обобщены достаточные условия оптимальности для линейной задачи ОУ со смешанными ограничениями типа равенства и неравенства в случае исключения ограничений типа равенства уменьшением размерности вектора управлений Получено доказательство слабой сходимости дискретизированного решения задачи ОУ к непрерывному

3. Разработан комплекс программных средств формирования и решения аппроксимационных задач с варьируемыми значениями коэффициентов, позволяющий оценивать характеристики как получаемых решений, так и характеристики процессов решений,

4 Предложена линейная динамическая модель управления государственным внешним долгом РФ, для которой решена серия параметрических задач ОУ;

5 Проведено экспериментальное исследование данной модели, показавшее высокую эффективность предложенного подхода,

6 Исследовано влияние применения различных схем дискретизации на точность получающегося численного решения.

7 Предложен метод оптимизации характеристик решений линейных задач ОУ по параметрам модели Проведен анализ устойчивости решений аппроксимационных задач от коэффициентов исходной задачи оптимального управления

Основные результаты диссертации опубликованы в работах

1 Чекарев ДА Построение класса чисел с плавающей точкой повышенной точности // Управление и обработка информации модели процессов' Сб.ст /Моек физ -тех. ин-т. - М, 2001. - С 244248.

2 Чекарев ДА. Схема получения численного решения сопряженной задачи по известному численному решению прямой в задаче оптимального управления. // Обработка информации и моделирование. Сб ст./Моск физ.-тех. ин-т. - М, 2002. - С 329332

3 Чекарев ДА Модель экономической системы с эффектом накопления в задаче оптимального управления внешним долгом. // Моделирование и обработка информации: Сб.ст./Моск. физ.-тех ин-т. - М , 2003 - С. 39-43

4 Умное А Е, Умное Е.А , Чекарев ДА Анализ эффективности схем дискретной аппроксимации в задачах оптимального управления. // Моделирование и обработка информации' Сб ст./Моск физ -тех ин-т - М , 2003 - С. 44-52

5 Умное А Е, Умное Е А, Чекарев ДА. Использование метода параметризации в задачах оптимального управления со смешанными ограничениями // Моделирование процессов управления Сбст/Моск физ-тех ин-т. - М., 2004. - С 124-131.

6 Умное АЕ, Умное ЕА, Чекарев ДА. Параметрический двухуровневый метод решения задач оптимального управления со смешанными ограничениями // Моделирование процессов управления' Сб ст /Моек физ -тех. ин-т - М , 2004. - С 132-140

7 Умное А Е, Умное Е.А, Чекарев ДА Оценки погрешности дискретной аппроксимации решения задач оптимального управления со смешанными ограничениями. // Моделирование процессов управления- Сб ст /Моек физ.-тех. ин-т. - М , 2004. С -141-148

8 Дикусар В В, Чекарев Д.А Численно-аналитический метод решения задач оптимального управления' Сообщ по прикл матем / ВЦ РАН. - М., 2004.-31с.

9 Чекарев ДА Увеличение разрядной точности решателя посредством введения нового класса чисел с плавающей точкой повышенной точности XLIII Научная конференция МФТИ Тез. докл - М, 2000, ч VII, С 27

10 Чекарев ДА Оценка погрешности численного решения задачи оптимального управления для линейной модели управления внешним долгом XLVI Научная конференция МФТИ' Тез докл -М, 2003, С 91

Чекарев Денис Анатольевич

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ С ИСПОЛЬЗОВАНИЕМ ДИСКРЕТНОЙ АППРОКСИМАЦИИ

Подписано в печать Формат бумаги 60x84 1/16 Бумага офсетная Уел печ л 1,0 Тираж 80 экз Заказ № - ¿Ь

Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ» 141700, Московская обл , г Долгопрудный, Институтский пер , 9

P1 0884!

РНБ Русский фонд

2006-4 5883

о

I

1. Введение.

1.1. Общее описание проблемы.

1.2. Место работы в современной науке.

1.3. Формулировка темы работы. Актуальность.б

1.4. Цель и задачи исследования.

1.5. Научная новизна исследования.

1.6. Предлагаемый подход к решению.

1.7. Основное содержание работы.

1.8. Практическая значимость. Публикации.

1.9. Апробация результатов исследования.

1.10. Структура и объем работы.

1.11. Личный вклад диссертанта.

2. Математическое моделирование линейных динамических систем со смешанными ограничениями.

2.1. Постановка параметрической задачи оптимального управления.

2.2. Необходимые условия оптимальности для общей задачи оптимального управления. Принцип максимума Понтрягина и формализм Дубовицкого-Милютина.

2.3. Линейные параметрические модели с ограничениями смешанного типа.

2.4. Условия оптимальности для линейных задач.

2.5. Задачи оптимального управления А и Б.

3. Решение линейных задач оптимального управления со смешанными ограничениями методом дискретизации по времени.

3.1. Построение конечно-разностной аппроксимации модели.

3.2. Схема решения параметрических задач оптимального управления.

3.2.1. Получение аппроксимации решения прямой задачи.

3.2.2. Выделение множества активных ограничений.

3.2.3. Построение аппроксимации решения сопряженной задачи.

3.3. Сходимость дискретных аппроксимаций.

3.4. Общая схема решения линейных задач ОУ.

3.4.1. Случай исключения ограничений типа равенства.

3.4.2. Схема решения линейной задачи ОУ.

3.5. Применение схем дискретизации различных порядков точности.

3.6. Применение схем дискретизации с переменным шагом.

3.7. Описание нового класса чисел повышенной точности.

3.8. Анализ устойчивости дискретной аппроксимации на основе критерия оптимальности.

3.8.1. Определение устойчивости задачи ЛП, основанное на критерии оптимальности.

3.8.2. Меняются коэффициенты матрицы А.

3.8.3. Меняется столбец Ь.

3.8.4. Меняетсяолбец

3.8.5. Меняются коэффициенты Л и Ь.

3.8.6. Меняются коэффициенты А и

3.8.7. Меняются коэффициенты Ь и С.

3.8.8. Обший случай (меняются коэффициенты А, Ь , с).

Применение метода дискретной аппроксимации для параметрических динамических моделей обслуживания внешнего государственного долга.

4.1. Содержательное описание особенностей моделируемой системы.

4.2. Математическая формулировка модели.

4.2.1. Обозначения для количественных характеристик системы.

4.2.2. Динамические соотношения системы.

4.2.3. Ограничения на фазовые переменные и управления системы.

4.2.4. Целевая функция.

4.3. Общая формулировка задачи.

4.4. Решение задачи.

4.4.1. Построение конечно-разностной аппроксимации.

4.4.2. Решение дискретной аппроксимации с помощью системы «Баланс-2».

4.4.3. Формирование гипотезы о геометрии оптимальной траектории.

4.4.4. Решение исходной системы.

4.4.5. Решение сопряженной системы.

4.4.6. Полное решение задачи.

4.5. Применение различных схем дискретизации.

4.5.1. Применение схем дискретизации разных порядков точности.

4.5.2. Применение схемы дискретизации с переменным шагом дискретизации.

4.6. Формулировка и решение параметрической задачи ОУ.

Применение рассматриваемого подхода для анализа параметрической модели оптимального управления.

5.1. Содержательное описание особенностей моделируемой системы.

5.2. Теорема о сходимости дискретных аппроксимаций.

§1.1. Общее описание проблемы Данная работа посвящена разработке и исследованию методов численного и аналитического решения линейных параметрических задач оптимального управления (ОУ) со смешанными ограничениями. Предположение о линейности хотя и сужает область применимости предлагаемого подхода к построению численных методов решения задач ОУ, но, тем не менее, позволяет получать значимые результаты при решении различных практических задач, поскольку многие задачи ОУ описываются линейными моделями. Для решения задач ОУ при наличии ограничений только на управления широко применяется метод «прогонки».Наличие же смешанных ограничений, включающих как фазовые переменные, так и управления, существенно усложняет структуру задачи, и может сделать использование этого метода малоэффективным. Можно констатировать, что развитые к настоящему времени схемы решения задач оптимального управления либо в основном базируются на использовании специфики их условий (например, отсутствии ограничений по фазовым переменным или априорном предположении о поведении оптимального управления), либо требуют альтернативных подходов. Таким образом, вопрос построения эффективных интерактивных вычислительных систем для решения указанного класса задач остается актуальным и в настоящее время. Такая система должна находить приближенное численное решение задачи ОУ, осуществлять проверку истинности ее решения и, в случае необходимости, построение аналитического решения посредством формулировки и проверки гипотезы о геометрии оптимальной траектории. Как расширение класса решаемых задач, параметрическая задача ОУ позволяет не только исследовать актуальные вопросы чувствительности и устойчивости решения, но и улучшить интерпретируемость получаемых решений. Например, оказывается возможным ставить задачи поиска оптимальных значений параметров задачи, при которых значение целевого функционала оптимизируется на множестве значений параметров.

1. O.L. Mangasarian. Sufiicient conditions for the optimal control of nonlinear systems. S1.AM. J. Control 4 (1966), P. 139-151.

2. Арутюнов A.B. Условия экстремума. Анормальные и вырожденные задачи. М.: Изд-во "Факгориал",1997.

3. Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления. М.: Высш. школа, 2003.

4. Афанасьев А.П., Дикусар В.В., Милютин А.А., Чуканов С.А. Необходимое условие в оптимальном управлении. М.: Наука, 1990.

5. Афанасьев А.П. Линейные по управляющим воздействиям задачи оптимального управления. Препринт. М.: ВНИИСИ.

6. Васильев Ф.П. Методы решения экстремальных задач. М.: Наука, 1981. - 400 с.

7. Васильев Ф.П. Методы оптимизации. М, Факториал, 2002.

8. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.

9. Га басов Р., Кириллова Ф.М. Принцип максимума в теории оптимального управления. -Минск, "Наука и техника", 1974.

10. Дикусар В.В. Методика численного решения краевых вариационных задач для системы обыкновенных дифференциальных уравнений. Автореф. дис. докт. физ.-мат. наук. -Дубна, ОИЯИ, 1982.

11. Дикусар В.В., Милютин АЛ, Качественные и численные методы в принципе максимума. М., Наука, 1989.

12. Дикусар В.В., Кошька М., Фигура А. Методы продолжения решений в прикладных задачах оптимального управления. М., МФТИ, 2001.

13. Дикусар В.В., Гживачевский М., Кошька М., Фигура А. Методы продолжения решений в прикладных задачах оптимального управления. М., МФТИ, 2001.

14. Дикусар В.В., Кошька М., Фигура А. Задачи оптимального управления при наличии ограничений общего вида. М., МФТИ, 2001.

15. Дикусар В.В., Синягин С.Ю. Качественные и численные методы в задаче оптимального управления внешним долгом: Сообщ. по прикл. матем. / ВЦ РАН. М., 2000.16.