Теория обобщенного динамического программирования, ее приложения и использование в управлении и навигации ЛА тема автореферата и диссертации по механике, 01.02.01 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

л имени М.В.ЛОМОНОСОВА

"•> О, П

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

ЧЕРНОВ Дмитрий Эдгарович

ТЕОРИЯ ОБОБЩЕННОГО ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ, ЕВ ПРШГОЖЗШ И ИСПОЛЬЗОВАНИЕ В УПРАВЛЕНИИ И НАВИГАЦИИ ЛА

Специальность! 01.02.01 теоретическая метаника

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

Москва 1994-

Работа выполнена в Московской авиационном институте имени Серго Орджоникидзе.

Официальные оппоненты:

доктор фгаико-математическиг наук, профессор В.В.Александров доктор физико-математических наук, профессор М.Ы.Хрустадев доктор технических наук, профессор И.Б.Казаков

Ведущее предприятие! Институт проблем управления РАН

Защита состоится 18 февраля 1994 г. в 16°° на заседании специализированного совета Д 053.05.01 при Московской государственном университете по адресу: 119899, г. Москва, Воробьевы горы, главное здание МГУ, зона "А.", ауд. 16-10.

С диссертацией «окно ознакомиться в библиотеке механико-ыа-теыатического факультета МГУ.

Автореферат разослан 17 января 1994 г.

Ученый секретарь специализированного совета доктор физико-математических наук

Д.В.Трещев

ОВДАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

С другой стороны, возможность реализации на практике уже меющихся достижений в этой области, в свою очередь, непосредст-1енно связана с наличием эффективных и высокоточных алгоритмов >ешения подзадач из смежных областей. В первую очередь вто каса-!тся задач МП, возникающих практически во всех разделах оптималь-юго управления и навигации, да и не только в них. Касается вто •акже вычисления многомерных интегралов (т.е. интегралов высокой ¡ратности), возникающих при вычислении вероятности достижения пеги управления в задачах оценки качества (по вероятностному критерию) систем управления и навигации, при решении вероятностных за-(ач и во многих других случаях; вычисления определителей и обращения матриц (особенно плохо обусловленных матриц высоких размер-гостей), что повсеместно требуется в задачах фильтрации и управ-1ения, в задачах устойчивости, в задачах планирования, построения метем массового обслуживания, в комбинаторике; решения систем »лгебраическях уравнений и неравенотв, возникающих при поиске до-1устимых управлений или решений, при дезагрегировании найденных агрегированных решений "больших" задач оптимального управления, а

также нэкоторых других эадач.

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

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

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

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

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

Ефектавнооти самого ДП является очень актуальной проблемой.

Цель работы ооотоит В!

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

- приложении теории ОДП к ряду классов задач, возникающих ри разработке и реализации систем управления и навигации ЛА (как ^посредственно, так и в виде подзадач), для получения вффектив-д методов решения этих задач.

Методика исследований. При построении аппарата теории ОДП ^пользуются в качестве основы для обобщений соотношения метода I в дискретновременных задачах синтеза ОУ. При разработке приложив теории ОДП используются ее аппарат я методы повышения эф-эктивности. При решении задачи управления стационарным ИСЗ ис-эльзуется полученная в диссертации методика сокращения вычисле-Ш в методе ДП.

Научная новизна. Новыми научными результатами в диссертации зляются:

- Идея и аппарат теории обобщенного динамического программи-звания (ОДП), включающий в себя оригинальную унификацию операто-эв на основе введенного понятия оператора-свертки по переменной, циный (стандартный) вид объектов теории ОДП - задач с рекуррент-зм применением операторов (задач о РПО), рекуррентные соотноше-1Я для вводимой функции промеяугочного результата (®Р), цеха-1зм рекуррентной агрегации аргументов ФПР (в фотэме обобщенного азового вектора - ОФЗ), подход к нахождению подходящего ОФВ, энцепции разбиения и объединения операторов и, наконец, единый пгоритм решения рассматриваемых задач (метод ОДП).

- Система общих подходоа, методов, способов, касаицихся за-юи задач в стандартном виде, наиболее аффективного применения зории ОДП, оптимизации ее алгоритмов и т.д.

- Методика радикального (до нескольких порядков) сокращения Зъема вычислений при использовании метода динамического програм-дрования в динамических задачах синтеза оптимального управления ЭУ) - дегерминироваянш:, стохастических, минимаксных и т.д. денки эффективности методики.

- Метод сведения решения обратных вероятностных задач к ре-

пюнию прямых вероятностных задач.

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

- Алгоритмы (метода) решения широкого крута задач математического программирования - детерминированных (в оамси общей виде), минимаксных, стохастических, минимаксно-стохастических и минимаксных стохастических (в том числе, со сложными ограничениями). Методы повышения «эффективности предлагаемых алгоритмов.

- Выражения для градиентов функций вероятности и квантили -для вероятностных задач МП.

- Решение минимаксной задачи программного управления.

- Алгоритм (метод) вычисления определенных интегралов высокой кратности (до 20 и выше), имеющий для широких классов интегралов трудоемкость, возрастающую с ростом размерности примерно линейно. Модификации базового алгоритма для интегралов вероятности и других частных случаев. Методы повышения {эффективности предлагаемых алгоритмов, в частности, метод замораживания переменных.

- Решение задачи анализа качества системы управления ЛА (критерий - вероятностный).

- Высокоточные алгоритмы (методы) вычисления определителей и обращения матриц. Методы повышения их эффективности и расширения применимости.

- Метод поиска стационарных точек функций многих переиенных и точек с заданным значением градиента.

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

- Решение задачи оптимизации коррекции стационарного ИСЗ с ВДУ малой тяги по прямому вероятностному критерию.

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

.д. Поэтому результаты, полученные в диссертации, могут быть ис-ользованы при разработке и реализации систем управления и нави-ации ЛА, а также во многих другах задачах.

Работа является составной частью научно-исследовательской аботы, проводимой на кафедра "Системный анализ и управление'.' МАИ.

Апробация работы. Основные результаты диссертации были доло-ены автором на международной школе-семинаре по методам оптимиза-ии и их приложениям (Иркутск, 1989), на V Всесоюзной Четаевской энференции (пленарный доклад, Казань, 1987), на XVI Гагаринских гениях (Москва, 1986), на П Всесоюзной пколе-семинаре молодых зеных и специалистов "Динамика, управление полетом и иеследова-ге операций летательных аппаратов" (Клин, 1987), на Всесоюзной энференции "Моделирование систем информатики" (Новосибирск, Э88), на Всесоюзной школе-семинаре "Динамика ползта, управление исследование операций" (Клин, 1990), а такве на конференциях злодых ученых МАИ и на различных семинарах.

Диссертация в целом апробирована на семинарах кафедры прик->дной механики МГУ, кафедры прикладной математики МГТУ и кафедры Системный анализ и управление" МАИ.

Личный вклад и публикации. Все результаты диссертации полущи лично автором, основные из них опубликованы в 18 печатных ¡ботах.

Структура и объем диссертации. Диссертация состоит из введе-гя, двух частей, содержащих девять глав, выводов, приложения и шока литературы из 141 наименования. Общий объем работы - 242 границы, в том числе 1 рисунок и 6 таблиц.

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

Во введении обосновывается актуальность рассматриваемой в гсеертации проблемы, излагается современное состояние вопроса с [зороы имеющихся по нему публикаций, формулируется цель дисоер-дии и приводится краткое содержание последующих ее глав.

В первой части, содержащей две главы, приводятся основы тео- . л обобщенного динамического программирования (теории ОДП).

В первой главе развивается аппарат теории ОДП: вводятся ос-вные понятия, выводятся основные соотношения, формулируются нцепции, предлагается собственно метод ОДП.

В п. 1.1 напоминаются соотношения метода ДП в динамических дачах оптимального управления (ОУ) с дискретным временем. На-

пример, при рпзносттпа уравнений!

. = g.(z.,ut,ut), UT-Я. Z, ж К - ааданы , (1). »♦1 » I i % i

опиоывакщшс движение, и критерии I

Ма[ J -H{z Л —> mtn (2)

»l,7i » » » t J ueU^xU^

tnin

и

соотношения метода ДП имеют вид

w = ¿s^ltf'tW * ww] •

Здесь z- n-мерный фазовый вектор состояния управляемого объекта в 1-й момент времени (на i-и шаге), u{d7u=ujzj - вектор

управления, u.€ Q.c й* - вектор случайных возмущений (и. и., и.

» » я * j «

и И, попарно независимы при k*J), g,, tr и F - некоторые задан-j i » .. ные функции, и = col(u и = ,0^), ш0 - усред-

нение по а, Д.- функция будущих потерь (ФШ).

В п. 1.2 вводится понятие свертки по переменной (центральное понятие теории ОДП), приводятся замечания и пояснения, раскрывающие его суть, а также большое число примеров.

Каждый оператор перехода от шага к шагу в соотношениях ДП (в (3) ето - mi л К,, ) обладает следующей особенностью. В результате

I i

его применения из списка переменных (г , и, и ы,) обрабатываемой функции (Д, ,) исчезают соответствующие переменные (и, и и,).

4+1 I |

Т.е. он как бы сворачивает функцию по переменным и, и а., пере-

I \

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

Определение 1. Любой оператор, определенный на функциях переменной teT*B (где функции - из некоторого подмножества множества {f:T—>G}) и при каждом фиксированном реР*в однозначно ставящий в соответствие каждой такой функции некоторый влемент (зависящий от р) из множества W, назовем Г-значной (т.е. со значениями в F) сверткой по переменной t<eff (р-параметричеокой).

Будем обозначать любую р-параметрическую свертку (convolution) по tcT через con (р, -J или просто con. Различать разные

teT teT

свертки по одним и тем же переменным будем с помощью штрихов или

индексов. Раскрывать характер каждой конкретной свертки будем с помощью произвольной ("пробной") функции Г из области определе-

гая свертки, причем фушсцкя о именем Т' будет попользоваться для

iToro и только для этого. Так, например, соотношение

юп (p,í(t)) « 2 min í(t) + р означает лишь то, что данная пара-L€T t«T

1етрическая свертка является минимизацией с удвоением

[олученного результата а прибавлением к ному параметра р.

Замечания и пояснения. 1. Под параметрами (а также перемен-эаи) здесь и далее могут пониматься объединенные параметры - цене группы параметров, возможно самой различной природы. Множест-

0 Г (или Р) может состоять из одного элемента. Такие переменно назовем константными.

2. Свертка - не столько класс операторов, сколько форма их редставления. В принципе, вообще любой однозначный оператор функцию) А : V —* W можно представить в виде непараметрической параметр константен) lf-значной свертки (в работе показано, ка-им образом). Если элементы множества J являются или могут быть редставлены функциями неконстантной переменной реР, т.е. с {¿:Р —* f^}, то указанный оператор А может быть представлен ще и в виде р-параметрической f^-значной свертки.

3- Свертка оперирует о функциями конкретной переменной. При том одна и та же функция в зависимости от ее переменной воспри-имается сверткой по-разному. Например, свертка по t воспринима-т параболу pítjst*, teT=Ri, именно как параболу, а параболу (з)=ззе!Р, - как константу, зависящую от параметра а.

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

1 i i-i »

ов р,хА....,х, . Из сказанного вытекает следующее свойство 11-1

верток. Пусть некоторая р-параметрическая свертка по ícT при-

эняется к некоторой функции f(s,t), определенной на Sxf. Пусть

сР, seS. Тогда con (p,f(3,t))¡„ « con (р.,9(а ,t))- Это 3 о UT ,Pí'so t«T 0 0

эжное свойство позволяет получать результат применения свертки

эточечно, что существенно при численных расчетах.

5. Поскольку,как установлено в замечании 4, свертка применя-

етоя при фиксированных значениях параметров как самой свертки,так и сворачиваемой функции, то ситуация не становится неопределенной и в случае совпадения некоторых аргументов-параметров сворачиваемой функции о некоторыми параметрами свертки. Просто при этом результат применения, например, свертки con (р,-) к функции Q(p.t)

будет при р=рй равен con (p^fip^t)). Примером может служить параметрический интеграл J(p)=Pj p(p,t)dt, который является результатом применения параметрической свертки con(p,f(t)) =PJf(t)dt к

конкретной функции f(p,t). Аналогичная ситуация возникает также в динамических дискретновременных задачах синтеза оптимального управления при наличии интегральной составляющей в критерии качества,

6. Множество Т в определении 1 является не множеством, по которому производится сворачивание, а множеством, в пределах которого производится сворачивание. Оно играет роль "ограничителя" значений переменной t и роль множества, на котором определены сворачиваемые функции. Отсюда вытекает, в частности, что свертка по teT необязательно использует значения сворачиваемой функции во всех точках t из Т. Более того, согласно определению используемая часть множества Т может зависеть от параметра р свертки.

Например, confp,f(t)) = min f(t). В втом примере (см. также tcfl1 Uíp.p+1]

интеграл в замечании 5) Гей1, но фактическое сворачивание производится по переменной, пробегающей множество Т*(р) = [p,p+í] с Т.

7. Сам термин "свертка" введен по аналогии со сверткой тензора по индексам, сверткой критериев в многокритериальной оптимизации. Преобразование свертки рГг) = ""Г K(x-t)f(t)dt с ядром

fo»J

К представляет собой частный случай параметрической свертки по teR* с параметром х. Свертка двух функций (интегральная) в меньшей степени является прообразом введенной свертки.

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

азадрвтическое отклонение, вероятноать пепрошяпенил функцией зо-[шшого порога, квантиль заданного порядка (минимальный характерней коэффициент, при котором цель управления достигается с вероятностью, не меньшей заданной), колебание функции на множестве.

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

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

В п. 1.3 вводятся единый (стандартный) вид задач, расоматри-темых теорией ОДП, и функция промежуточного результата (ФПР), (ля которой записываются рекуррентные соотношения.

С введением понятия свертки появляется возможность зависнуть многие задачи различной природы в виде задач о рекуррентным грименением операторов-сверток (задач о РПО), кяадый из которых сроизводит сворачивание функции по "своей" очередной переменной. 1 таких задачах решение принципиально может быть получено путем >екуррентного применения указанных сверток к некоторой исходной функции многих переменных (в задачах оптимизации и выбора - с по-гутным нахоадением нужных точек).

Введем для задач о РПО следующий стандартный вид!

J(s) = con con ... con ?(з,х ) = ? U)

x eX x el x el i 2 »

11 i 2 in

т.е. требуется найти J(3)), где S, X., ... , X , ff , ... , ff

1 n 0 n

юкоторые множества; ? - некоторая функция, ? : SxJ^x.. .xX^—vffj

icS - параметр, по которому оворачивание вообще не производится;

i каадая {-я свертка (i=1;n), сворачивающая функцию по переменной

, определена на ff.-значных функциях переменной х,еХ, и яв-| i i ti [яется П, ^-значной и, вообще говоря, параметрической о парамет-

>ами з, х^, ... , а , т.е. записывается в виде

\оп(з,х....,х. Обратим внимание, что от втот же параметров

х. 1 »-1 i

1ависит и функция, к которой ета свертка на деле применяется в 4) (см. замечание 5). При етом оговоримся, что свертки и функция ' (будем называть ее исходной) в (4) не обязательно зависят неформально от всех записанных их аргументов (параметров). По аналогии с функцией будущих потерь введем функцию

CJa,x....,x. ) - con ... con ?(з,хл,...,х ), i=l;n+1,

»1 i-i x x 1«

i л

которую назовем функцией промежуточного результата (ФПР) на i-и шаге. Она представляет собой результат (функцию), полученный после применения к исходной функции F соответствующей части операторов. Таким образом, каждая свертка con в (4) применяется к

позначной ФПР ci4i(3>xl'~'xi Результатом такого примене-

ния является If, -значная ФПР С (а,х ,~,х, ), что позволяет »-i »11-1 применять затем следующую, 1-1-ю свертку (2sisn) и т.д.

Для ©IP выполняются рекуррентные соотношения С (з,х ,...,х ) = Р(з,х....... ),

а 1 п

с.(з,х........ ) = con (з,х.-,х. Л,С .(a,xt,~,x.)), i=ñ¡2,

% 1 »-1 х €Х ' 4

i i

J(3) Ш С (з) = con (з,Сл(з,х)). (5)

1 г ¿Г í 1

11

Важным шагом по превращению соотношений (5) в эффективный алгоритм решения задач, записанных в стандартном виде (4), является агрегация аргументов ФПР.

В п. 1.4 предлагается механизм рекуррентной агрегации аргументов ФПР. Вводятся понятия обобщенного фазового вектора (ОФВ) и ОФВ свертки (ОФВС). Рекуррентные соотношения для ФПР записываются в преобразованном виде, являющемся основой метода ОДП. Предлагается подход к построению нужного ОФВ.

В динамических даскретновременных задачах 0У фазовый вектор шаг за шагом фактически агрегирует в себе предшествующие вектора управления к реализаций возмущений и несет при втом информацию, достаточную для дальнейшего управления (в втом и заключается принцип оптимальности). Организуем агрегацию аргументов ФПР аналогичным образом: знание агрегата переменных а,х должно позволять применять свертки con con к функции Р в (4).

х х,

В X

Определение 2. Обобщенным фазовым вектором (ОФВ) задачи (4) назовем любой набор компонентов, удовлетворяющий условиям:

1) он меняется от шага к шагу согласно уравнениям перехода

У* = YJB>» f* = Y,(y.,x ), ••• • У , = Y (у ,х ) (6)

1 0 i 111 s«l an в

(где у. - ОФВ на í-м шаге, У^ - некоторые функции),

2) на каждом í-м шаге (t=1;п+1) он дает информацию о значениях переменных з,х,,-,х. , достаточную для применения сверток

i «-i

п ,...,сот. Или, иначе говоря, для любого 1=1;п+1 ОФВ позволя-м *«

1 в списке параметров любой J-й свертки (J~i;п+1) заменить х ,-,х на у , т.е. con (в,х,~,х ,-) заменить на

1 Í i лл 1 j*l

~J__

in(y..x -,х, ,■) для vj=l;n+1. , i i j-1

и етом очевидно, что С.(з,х ,...,х. можно заменить на С,(у.).

i i i-i, % » Здесь для удоботва функция F иэ (4) представлена в виде

i.a: ,...,а? )-параметрической свертки по константной переменной

(эта свертка ставит в соответствие любой функции функцию

з,х) ). Для нее ОФВ согласно сказанному позволяет заменить

з,хА,...,х ) на ?(у, ,х, ,...,х ) для Vl=l;n+1. Заметим здесь

1 в II а

, что свертки при замене а, а , ... , i на у, в списке их гументов-параметров, вообще говоря, становятся другими Однако будем менять их обозначений (т.е. не будем добавлять штрихи, дексы и т.д.), полагая, что путаницы тут возникнуть не должно, же самое примем и для функций. Введем также вспомогательное понятие ОФВ свертки. Определение 3. Обобщенным фазовым вектором J-ой U=1;n+1) ертки (J-ым ОФВС) в задаче (4) назовем любой набор компонентов, овлетворящий условиям: 1) он имеет уравнения перехода вида

4 - V»'' = VW.....yjj " ^J.J-i^J.J-Í-'JV

Де J-& ОФВС на t-u шаге, У - некоторые функции),

на каждом t-u шаге (<=77j) он дает информацию о значе-ях переменных з.з^.-.а^ , достаточную для применения J-4 ертки. Или, иначе говоря, для vi=1;J позволяет заменить п (3,xt,-,x, на con (у..,х,,~,х. .,■) •

i J-l х *

п+1-й ОФВС, соответствухций функции F, будем также называть ВС функции Р.

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

Замечания. 8. В задаче (4) ОФВ (а также любой ОФВС) сущест-

ет и не обладает единственностью. В частности, всегда существу-

тривиальный ОФВ (аналогично ОФВС) вида = ,

1;п+1, т.е. Y,(s) = s, YJy,,x ) = col(y.,x), k=TJñ. Такой ОФВ

О k к к к к

любом шаге содержит переменные в неагрегированном виде. Его

ществование может иногда оказаться веоьма полезным.

9. Из определений 2 и 3 вытекает, что любой ОФВ задачи (4)

ляется также и J-м ОФВС для любого J=1¡n+1. С другой стороны.

ÚX

если у^,»..., у , - вое п+1 ОФВС задачи (4) (звездочки заменяют здесь вторые индексы, пробегающие для каждого /-го ОФВС, J=1;n+1, значения от единицы до J), то объект

y,=col(y, ,,-,у ,), i=1;n+1, является ОФВ задача (4). Иначе го» I» ■♦!,» воря, простое соединение всех ОФВС задачи уже само по себе является ее ОФВ. В честности, поскольку для любой непараметрической свертки существует ОФВС, константный на каждом шаге, то если свертки с первой по п-ю - непараметрические, любой n+1-й ОФВС в задаче (4) (т.е. ОФВС функции F) является также и ее ОФВ.

10. ОФВ (ОФВС) может не являться вектором в обычном понимании этого слова. Компоненты О® (ОФВС) могуч иметь различную природу - быть скалярами, векторами или иными математическими объектами, могут быть простыми и структурированными (теми же векторами). Число же самих компонентов на разных шагах может быть различным (начиная с нуля - для константного ОФВ). Более того, даже для фиксированного шага ( число компонентов в конкретном ОФВ (аналогично для ОФВС) и их природа (связанная с тем, что и как они агрегируют) могут быть различными при разных значениях некоторых его компонентов, которые будем называть информационными.

С вводом ОФВ рекуррентные соотношения (5) примут вид

С .(у ) = F(y ),

а М « ♦ i »♦!

С.(у.) = con (у.,С. JY.(y.,x.))j, uñís,

1 1 a?.el. i i

С,(У.) = (¥t*C-(Y.(]f.¿B.))),

1 1

J(s) s С ¿Y¿a)) . (7)

Соотношения (7) представляют собой основу метода ОДП.

Учитывая неединственность OOS, можно поставить задачу выбора ОФВ, при котором алгоритм (7) наиболее эффективен.

Из замечания 9 вытекает подход к построению нужного ОФВ, состоящий в построении для каадой параметрической свертки своего подходящего ОФВС (в пункте показывается, как его получить), соединения полученных ОФВС и отбрасывании дублирующихся компонентов. Вообще же ряд рекомендаций, способов и соображений по поводу улучшения ОФВ приведен в главе 2.

В пункте подучено также условие существования ОФВС, лучшего, чем тривиальный. Условия существования ОФВ, лучшего, чем тривиальный, в общем случае вряд ли можно записать (все зависит от конкретного соотношения компонентов в разных ОФВС). Однако ука-

анние условия получены для трех важных частных случаев.

В п. 1.5 формулируются концепции разбиения и объединения верток, имеющие своей целью повышение эффективности. В оконча-ельном виде записывается обобщенный метод ДП.

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

Как можно более полное разбиение сверток производится для ого, чтобы выявить вое перспективные разбиения. Естественно, что ри таком тотальном разбиении многие разбиения могут оказаться енужными, неэффективными. В этом и некоторых других случаях дей-твует другая концепция теории ОДП - объединение сверток. Объедини в (7) свертки по переменным х. .,...,х. в одну свертку по

»-к г

временной col(x. .,...,х), получим

i-k V

. .(У. = con С. (Y.(...Y (у. ,х. ),...,я.)) (8)

»-к »-к _ _ > ♦ 1 г i -И » - к < - к «

» - к i

частности, так следует поступить при численном решении, если SB на некоторых шагах имеет слишком большую размерность и не дается подобрать ОФВ меньшей размерности (согласно (8) ФПР на агах i,...,t-k+1 не запоминается).

Итак, для решения задач, записанных в стандартном виде (4) песте с уравнениями некоторого ОФВ, предлагается метод, состоя-ий в использовании (7) с допущением объединения некоторых шагов см.(8)). Этот метод назовем обобщенным методом динамического рограммирования (методом ОДП). В некоторых задачах оптимального правления (оптимизации) он совпадает с методом ДП.

Численная реализация предлагаемого метода аналогична реали-ации метода ДП. Так при переходе от шага nt+1n к £-му следует вфиксировать некоторое значение j/J1' ОФВ (из некоторой сетки в ространстве ОФВ), вычислить результат применения свертки при том значении ОФВ, запомнить C.(j/j1,J, зафиксировать другое зна-эние j/|a> ОФВ и т.д. В результате получается MIP на

are Hí", вычисленная в точках некоторой сетки. И т.д. При этом

а 1-й шаге (t=1,n+1) множество D., в пределах которого доста-

»

точно выбирать точки сетки, ограничено следующим образом:

4 {У^В) | вез), В4« . С=Т7п+Т.

Более узкие пределы в ряде случаев можно получить о использованием специфики задачи, интуиции, о учетом здравого смысла (если некоторые значения ОФВ может принимать, но они явно плохи: не дадут экстремума в задачах оптимизации, дадут нуль при вычислении интегралов и т.д.), с учетом дополнительных ограничений, результатов прикидочвого решения задачи в нулевом приближении и т.д.

Вычисление результата применения свертки производится в зависимости от того, что она из себя представляет. Например, если она является экстре- мумом, то результат ее применения можно вычислять с помощью пере- бора, градиентных методов и т.д.

В п. 1.6 представлен примерный порядок решения новых задач (не вошедших в приложения теории) с помощью теории ОДП.

В п. 1.7 разбирается промер - вычисление кратной суммы по шести переменным, связанным общим ограничением:

J = ) ' X ={0; 1;-; 10000}.

х\х,еХ,лх +2х*10000 »(12 6

С помощью теории ОДП получен алгоритм = 1•_

,у.+6х £10000

6 6 6 г

УА+2х*10ООО 2 2 2 2

J = Ct(yi)= • (9)

Здесь у, - ОФВ, имеющий уравнения перехода

у1 - константен, у£ уз <* 2х%, ... , = у^ 6х(,

причем в качестве О, можно взять X,, 1-2;7.

Показано, что при использовании алгоритма (9) потребуется в общей сложности просуммировать менее 8-Ю7 слагаемых (и произвести аналогичное число сложений и умножений для получения у.+1х и _ . » » (, -С. ) в то время, как при вычислении И непосредственно или с

помощью повторного суммирования только просуммировать потребуется около 2-Ю'16 слагаемых, что невозможно на современных ЭВМ.

Во второй глава приведена система общих подходов, методов и

рекомендаций по поводу представления исходных задач в виде задач } РПО, поиска подходящего ОФВ и уменьшения его размерности, раз-Зиения свера'ок. Эта система должна помочь в наиболее аффективном щшенении теории ОДП, в повышении эффективности ее алгоритмов.

В п. 2.1 рассматриваются четыре варианта выбора функции F в [4) для задач, в которых сворачивается сложная функция. Для каждого из s тих вариантов записывается начало алгоритма и указывают-!я области предпочтительного применения. Также обсуждается воп-зос, когда предпочтительнее вычислять краевые условия для ИГР отдельным шагом, а когда учитывать их непосредственно при примене-ши первой свертки.

В п. 2.2 представлены общие методы и способы разбиения свер-гок на более простые (согласно концепции п. 1.5).

В четырех подпунктах п. 2.2 показывается, как производить )азбиение сверток, содержащих собственно свертку и функцию; свер-<ок, связанных совместными ограничениями на область переменных ¡вертявания; как производить разбиение сверток за счет дробления властей свертывания (при этом вводятся понятия разделимой и по-[уразделимой сверток) и с учетом преобразования ОФВ.

В п. 2.3 представлены общие методы и способы сокращения раз-1ерности ОФВ. Эти результаты направлены на преодоление "проклятья зазмерности", а также на повышение эффективности алгоритмов.

В четырех подпунктах п. 2.3 предлагается сокращать размер-гость ОФВ о помощью замен переменных в исходной задаче и введения ¡азисных компонентов в самом ОФВ, вынесения за знак свертки, разженил области свертывания на более простые, замораживания пере-(енных. (Концепция объединения сверток, сформулированная в главе I, также позволяет избавиться от одного или нескольких шагов, на »торых ОФВ имеет слишком большую размерность)

Вынесение за знак свертки можно считать обобщением вынесения юстоянного (не зависящего от переменной свертывания) слагаемого ta знак максимума и минимума, сомножителя за знак интеграла а т.д.

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

Пусть некоторый компонент ОФВ на fe-м шаге не поглощается ФВои на нескольких следующих шагах (см. (б)) н до J-го (n*J>k>1) tara сохраняется как компонент ОФВ. Для определенности положим.

что этот компонент первый: и остается першах, т.е. у\~у\ • • При стандартном использовании алгоритма (7) его' фрагмент, соответствующий вычислению ФПР С,,___.С^, просчитывается при ОФВ

y,el\= i=J7k (где Z>?- 1]...,у[1)) соответствует дискре-

тизированному компоненту j/j). Метод замораживания переменных позволяет заменить этот фрашент на X последовательно просчитываемых фрагментов с J/{eDj. Благодаря этому при том же объеме вычислений размерность ОФВ уменьшается (не требуется компонент у\ я yj).

Предлокено также развитие метода замораживания для случая,

когда ¡A =х , а озертка по я является максимумом, минимумом, к к-1 1-1 суммой, интегралом. В втом случае можно расширить фрагмент на

один шаг - до вычисления ФПР С . Здесь используется то свойство максимума (аналогично - минимума, интеграла), что его можно вычислять не только одновременно, зная значения максимизируемой функции во всех точках, но и поэтапно, по мере вычисления этих значений (как только вычислено очередное значение, оно сравнивается с максимумом из уже найденных).

Во второй части, посвященной приложениям теории ОДП, содержится семь глав: в шести главах приведено семь приложений, в последней главе - решается задача управления стационарным ИСЗ.

В третьей главе приведено первое приложение теории ОДП к динамическим дискретновременным задачам синтеза ОУ: разрабатывается методика сокращения объема вычислений при численном использовании метода ДП в указанных задачах с детерминированными, байесовскими, прямыми вероятностными, минимаксными и смешанными критериями.

В п.3.1 указанная методика разрабатывается для общего случая. Применим для решения задачи (1), (2) теорию ОДП. Данная задача фактически уже записана в стандартном виде (4), где n=N, з

отсутствует, х,= col(u,,a.), свертки имеют вид i «i

con (z.,f(x.)) = con (z.,f(v,,ii.)) = min H., f g4(z.,u.,<¡.) +

X. * » и.,и. ' 1 ' и. V ' 1 » 1

» л » » , »

+ /(и.,Ы л, а фазовый вектор z , t=1;N+1, - связан с другими

i i J \

переменными через уравнения (1) z являетоя также ОФВ для указанного стандартного вида.

Попытаемся теперь в соответствии с концепцией разбиения операторов разбить их на более простые.

Пусть функции s. и S? в (1) и (2) предстазимы в виде: i >

g.(z.,u.,UJ =

I » I X I t t 1 I

5?Í2.,u.,U.J = g°}(z.,x^) 8<i2(f.(z.,xí.)M) , (10)

Ittl I < I lili I

(e x. и у. - соответственно п- и Л-мерные вектор-функции, а

1Кторы i}n ij независимы между собой и

col(u.,u ) вт (т.е. У.хО. - с точностью до

Ii Ii I III!

простановок компонентов в векторе и, и в и,.

Пусть кт (случай к>п рассматривается в главе 4). В этом гучае каждую свертку по х. = со1(и.,ы.) можно разбить на две юртки - по xj и по каадая из которых включает операторы, ютветствущие входящим й i} и компонентам и. и И.. На-шмер, если z* = со1(и*,= coIfu|4l,-,ü*>« то

{ I I t I I I t

т = «1( f + /Саг?Л,

j 1 I I (jUl^ Q.l I I I I I 1 J

1 i

т = min М , Г + /Га*У|.

,1 1 * u.,-fur ■ в}.-.а}1 1 ' 1 ,J

I I I I

I

Для изменившегося стандартного вида запишем уравнения

и* я i.i«.»^ ' . = i.^. 1Я,г?-> . (11)

♦1/2 iii i«l i 1*1/2 i

^шагового перехода ОФВ и рекуррентные соотношения для ФПР: = ест (z ,С. (%.(z. .,£))) ,

i*l/2 i*l/2 . 1+1/2 i*l I 1*1/2 I

г?

fzj = соп Гг.,С. .„O.iz.,®*); , {--FT? , (12)

ii . . i 1*1/2 Iii

шлющиеся алгоритмом решения исходной задачи (1),(2).

Предположим, что для реализации соотношения. (3) используется зямой перебор. (Для способов, связанных с вычислением математи-зского ожидания с помощью метода Монте-Карло, с минимизацией о змощьи градиентных и иных методов, а также при использовании изустных методов сокращения вычислений вффект от применения теории /дет иметь примерно тот же порядок) При этом диекретизированы южества значений векторов управления и возмущений (т.е. полага-гся u.c|u!».-,««»)<». и u.€{aii>,-.öit,>}<^. о приписыванием

ii II ii II

аздой точке ü.'u вероятности Р(и!1')=р.'1> ). ФНП на £-м шаге

этисляется в точках z, =• z[*\ т=1,М, некоторой сетки:

i i

= min »+ R. JsJz^WMq*1*))]

1 1 fc=TTI » l » » » » I I . I J

перебором всех KL комбинаций u;15' и u |1 { причем значения

i i

ункции й (она также вычислена в точках некоторой сетки) оп-еделяютоя о помощью интерполяции.

Таким образом получаем, что при использовании (3) при пере-

ходе от t+1-vo соотоянию к i-uy (т.е. при получении функции

R.(zj в точках сетки при уже известной также в точках сетки » t

функции Я. (z. ,) ) потребуется получить (о использованием ин-

»+1 »U . , ,

тераоляции) и обработать МП, » MX1!2, значений ФБП R, . (где X* и _« J I « i+1 ,, «

If - количества перебираемых значений векторов х* и зг,). В то

же время щм использовании (11) с теш же перебираемыми значениями векторов потребуется получать и обработать MX* значений ФШ

(при одинаковых сетках в пространствах 2, и Z,, что вполне

»♦1/2 »

естественно, когда dim z, = dim z ) при переходе от состояния

»♦1/5 » ,

"1*1" к состояния "1+1/2", а также MX1, значений ФБП при переходе

»

от состояния * 1+1/2" к состоянию "i". Таким образом, при переходе от 1+1~го к .£-му состоянию в 8той случае требуется получить и обработать не более значений ФБП. Также потребуется

лишь MXj раз вычислить функцию х, и MXj раз - функцию у. вместо вычисления МХ*Хг раз функции д., т.е. по МХ^Х- раз функций » » . » » » и (для функции g® - аналогично).

С учетом сказанного получа»!, что в процессе численного решения задачи при использовании (11) вместо (3) объем вычислений сокращается примерно в Х1,Х*/(Х*+Хг.) раз. Поскольку перебирается

I I I I , ,

обычно большое число значений (т.е. XJ и велики), сокращение вычислений может достигать огромных величин.В ряде случаев вффект может оказаться еще выше (например, когда dim z-tU2<n> когда хотя бы одна из функций у, и х. изменяет не все компоненты ОФВ).

Каадую из получившихся сверток (по х1 и по г?) аналогично

» »

можно попытаться разбить на несколько. И так далее.

Предлагаемая методика сокращения вычислений, основанная на теории ОДП, таким образом, заключается во введении промежуточных фиктивных фазовых состояний и вычислении на каждом из этих состояний ФБП (ФПР). Эффект связан с тем, что ФШ вычисляется как бы опять-таки с помощью метода ДП.

Методика изложена для случая, когда неконтролируемые вектора были случайными. Аналогичные результаты без труда могут быть получены и при неопределенных векторах в (1) (при етом в соотношениях математическое ожидание заменится на максимум), а также при одновременном наличии случайных и неопределенных векторов.

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

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

В п. 3.2 показано применение методики сокращения вычислений к задачам с линейными уравнениями движения.

Пусть в задаче (1),(2) соотношения (1) имеют вид

2. , = A,Z.+ B.U.+ Ii., (13)

«♦1 » l » « »

причем т=п, компоненты вектора х = col (и, и) независимы, a gü, = О

i

(для проототы) при произвольной функции ? в (2).

Здесь кавдая свертка con = min М0 разбивается на J=n+r

2. U, i „ ,, » 1

сверток mtn,-,míntH ,-,М , а алгоритм принимает вид

i г И1 и"

и. иГ ¡ ; * «

С. ,. , ■ . г,-) = М С- ,. + .....0,(i4)*) ,

«♦íj-lJ/j i*lj-i)/j (jn »«1 i + tj-D/j »

i

с." ' ) = м" C.' " ' jz.' ' +

«♦r/j »+JVJ ц! » + (Г+1 J/j \*r/J »

i

C- , ntnc. (z. , B.-(0,...J),v*)r),

»«(r-D/j »«tr-D/j »«r/j i 1

»

C.fzJ*= mtn C, \ j'a'z,'+ 'в'-Ы1..Ь,'..\,*o/T;.........

»V . l \ > \

U;

г

(уравнения перехода ОФВ можно проследить по аргументам ФПР в правых частях соотношений). Заметим что на шагах,соответствующих усреднению, вместо n-мерной интерполяции требуется лишь одномерная.

Если предположить, что г=п=3, а все дискретизированные компоненты векторов ti, и и. принимают по 30 значений, то согласно » i

сказанному здесь можно ожидать сокращения вычислений в 30в/(6-30)к4млн. раз. Если же учесть,что на половине шагов потребуется уже не 3-мерная, а одномерная интерполяция, то эту цифру следует увеличить еще примерно в 2 раза. Подобные оценки эффективности подтверждаются численными расчетами в главе 9.

В п. 3.3 показано применение методики сокращения вычислений к задачам о нелинейно-сепарабельными уравнениями движения вида

z. . = sXz., »♦i \ » \ « » i » \

и о функциями ф. в критерии, имеющими вид » i » » \ » » i »

6 п. 3.4 показано применение методики оокршцения вычислений

к задачам управления по двум каналам. Соотношения, описывающие движение, приняты в виде

где z1 и 2S (и и*, и2) - группы компонентов фазового вектора (и ti i i

управления), связанные с соответствующими каналами. Пусть для

простоты критерий - терминальный, au* и и? независимы. Тогда

% %

промежуточные состояния могут быть введены следующим образом!

«Í <„ = 8и^Л.иЬ. г? = г? . »♦1/2 » i i « »+1/2 «

»♦1 Ui/2 М ö» i«l/2 i

Соответственно запишется и алгоритм.

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

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

Предположим, что цель управления достигается при выполнении неравенств s f и Qfz^J s О, где ре(-а>,ю) - некоторый

заданный параметр, а функция ограничений Q может быть векторной. Тогда можно поставить задачу синтеза оптимального управления с разностными уравнениями (1) и прямым вероятностным критерием

PJu) i P{*f* Q(z )sO} -> ш . (14)

? «И uéü

Если цель управления должна быть достигнута с вероятностью, не меньшей.а (заданного), а параметр $ не фиксирован и подлежит минимизации (например, Í'<'2!M1•, мохет характеризовать расход топлива), приходим к задаче с уравнениями (1) и обратным вероятностным критерием

bju) = min{if I -» min , (15)

Здесь Pq(u) - из (14).

Для решения динамических задач с прямым вероятностным критерием может быть использован метод ДП вместе о предложенной в п. 3.1 методикой сокращения вычислений (для втого следует записать функцию вероятности в виде математического ожидания функции, равной единице, если цель управления достигнута, и нулю в противном

случае). К обратным же вероятностным задачам метод ДП непосредственно не может быть применен из-за отсутствия в них марковских свойств. Для преодоления указанной трудности в пункте предлагается метод сведения решения обратной вероятностной задачи к решению прямых вероятностных задач. Метод основан на том свойстве, что оптимальное управление для задачи (15) может быть найдено как решение задачи (14) при р = Ф* (где Ф^ - минимальное значение критерия в задаче (15)), и предполагает решение задачи (14) со специально подбираемыми значениями р. Интервал неопределенности величины Ф* уменьшается с каждым шагом метода в два раза.

Тем самым метод позволяет использовать для решения обратных вероятностных динамических задач ОУ метод ДП и, соответственно, методику сокращения вычислений (п. 3.1) и метод замораживания переменных (глава 4).

В четвертой главе приведено второе приложение теории ОДП к динамическим дискретновременным задачам синтеза ОУ. Здесь на основе результатов глава 2 (п. 2.3.4) разрабатывается метод замораживания переменных в методике сокращения вычислений (представленной в главе 3), который существенно расширяет область применения последней. Метод предназначен для случая, когда получено представление (10) с к>п, т.е. размерность фиктивного фазового вектора (ОФВ на шаге, не совпадающим с реальным шагом в эволюции системы) больше размерности фазового пространства. Замораживание "лишних" компонентов ОФВ позволяет сократить до п его размерность на всех шагах (за счет просчитывания соответствующих фрагментов алгоритма требующееся количество раз) и достигнуть эффективности по сравнению о непосредственным применением ДП.

Показано, как производится замораживание "лишних" компонентов ОФВ, являющихся компонентами векторов управления (п. 4.1), возмущений (п. 4.2), фазового вектора (п. 4.3), агрегатов из этих компонентов (п. 4.4). Получены оценки эффективности использования методики в паре с методом замораживания. Приведен пример.

Результаты, представленные в главах 3 и 4 существенно расширяют возможности численного применения ДП в динамических задачах ОУ и позволяют решать многие задачи, ранее недоступные для ДП.

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

2.2

квантили. К задачам МП сводятся задачи программного управления, повтому глава 5 имеет и к ним самое непосредственное отношение. С помощью полученшс в нее результатов в завершение главы решается минимаксная задача программного управления.

В п. 5.1 рассматриваются детерминированные задачи МП. Эти задачи являются областью традиционного применения ДО, повтому в етом пункте значительное место занимает обзор. В нем представлены известные результаты, касающиеся применения ДП к детерминированным задачам МП. В завершение пункта представлены новые результаты, которые дает теория ОДЕ в указанных задачах. Эти результаты легко могут быть получены как частный случай результатов п. 5.2, поэтому не будем на етом здесь останавливаться. К недетерминированным задачам МП метод ДП прежде не применялся.

В п. 5.2 теория ОДП применяется к минимаксным задачам МП в

достаточно общей постановке

mar $(u,v) -у min , гаг Q(u,v) * о , (16)

vcV исП veff

где и=(и.,~,и )х, v=(v.-,v ;Т. а Q может быть и вектор-функцией.

1 г la

Подобные постановки (особенно при ff«V) типичны для задач гарантированного одношагового управления (принятия решений) в условиях неопределенности (они представляют собой "игру" о природой и несколько отличаются от традиционных игровых задач). При етом управление 2-го игрока (природы) не ищется. В таких задачах обычно требуется минимизировать некоторый критерий 9(u,v) (например, расход топлива) при наихудших воздействиях неопределенного вектора v из некоторого множества 7 (так возникает шг Ф(u,v) —» min )

и и

при гарантированном (относительно тех же и) выполнении некоторого условия, например, ограничения по скорости, ориентации (так

возникает сложное ограничение mar Q(u,v) s О ).

и

Необходимость решения задач типа (16) (при ffeV) возникает также при решении вероятностных задач о помощью минимаксного или обобщенного минимаксного подходов.

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

Запишем множества U, 7 к W в виде U = {tt€Är | G(u)sO}, V = {vcii* | g(v)sO), IT = {ücJS" | h(v)sO), где 0, g и h - некото-

рые функции. Представим функции Ф (аналогично Q), g (аналогично Л) и G в виде рекурсивно вычислимых:

ФГи.и; = Ф СФ С-Ф /Ф .и ). -,и ),v ),■■■,v ),и ) ,

г«-1 г«1 г 2 1 2 г 1 »-1 ■

gfV) - •

G(u) = G (G (~(G (и ,u ).■),u ) ,u ) , (17)

r r-i 2 12 г-i г

где Ф. (i=2,rm), я. (i=S\m) и G. - некоторые вектор-

i I «

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

С помощью теории ОДП для задачи (16) получен следующий алгоритм (один из вариантов - без вычисления краевых условий отдельным шагом):

С (у J = max Q (yi , w ), г42ш "г.2« ш €2 (уг ) r*ia

а ■ г+2»

С (у )= max С (Q ,),h t(yi.w )), qkr+2m-1,

" ' w eS (уг) 9+1 r4*'1 ' 4 *~l

m -1 »-1 q

с Jy ' j= * ' С JQ jy1 У*

r»»»2 r»»»2 w ¿n (Vl \ r»«»S r*l r*»»2 2 2 *r»»»2 2

i г{уг*»*г

С (у ) = max С (Q Су .,w),w) , г»»»1 r»»«t jy г»1»2 г«1 г«»«1 1 1

С ,уй ) = max , Ф (у2 ,v ),

г*ш Г'Ш г** и gg /уЗ J г»« г»я *

■ ■ г»»

с (1,уг,у*)= шах С (1.ifyi.v ) ,g (у* ,v )). qkr+m-1, ' ' * v еВ (у*) г>" " ' '

■-i ■ -! г

С П.у* J = шаг, С M.),BA\f 4.wj; .

r»2 "г«2 г*2 у €jj (-уЗ j гО г*2 сг»2 2 2 г«2 2 2 2 г*2

С (1,у*) = тх С (1, Ф /y',,V'V '

г+1 м! у gjj г+2 г+1 г«1 t 1

с ЛО.у1 .) = С (О.у1 ) =...= С (0,у2 ) = С Луг ) , С (у ) = min С (1,9 (у*.и )),

г г и еН гЛ г Г Г

где Н = (и еА (у3) | С JO.Q (уг,и ))*0} .

г г г г г т

с (у ) = min С сФ (у1,и ).Q (у*,и ),а (у3,и .).) , qhr-1,

4 1 U €4 Су3) г««« ЧЧЧ 4ЧЧ Ч Ч 1

J = mtn CJu) ! (18)

vV 1

где множества Е. имеют вид

Si ~ ' E^v^+a}, а ^ и i( - аналогичные, верхние индексы у игреков означают соответствующие компоненты ОФВ Сне обязательно скалярные,). При О и при = 1 (i=r+l,rm) второй компонент ОФВ имеет различную природу, поэтому при yj = О он помечается волной, а вообще уравнения перехода ОФВ можно проследить по непосредственным аргументам ФОР в правых частях соотношений (18).

В пункте приведены также некоторые подхода и способы, вытекающие из главы 2, способствующие повышению эффективности и расширению возможностей алгоритма (18).

Аналогично (18) нетрудно выписать и алгоритмы решения задач со связанными переменными (в которых функции g и h зависят еще и от и), а также задач с параметром з. Полученные результаты нетрудно также распространить на задачи отыскания кратного минимак-са со связанными переменными. При отсутствии сложного ограничения эти алгоритмы, как и алгоритм (18), значительно упрощаются.

В п. 5.3 алгоритмы, аналогичные (18), выводятся для стохастических, минимаксно-стохастических (в которых вместо одного из максимумов в (16) стоит математическое ожидание) и минимаксных стохастических задач вида

kL тах -> min , М- шах Q(u,%,v) л О ,

5 v^V иеО 5 veW

где ö, V и W - те же, что ив (16), а ScScfi* - случайный вектор.

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

В п. 5.4 выводятся формулы для градиентов функций вероятности и квантили, что позволит применять для решения вероятностных задач МП градиентные методы и необходимые условия оптимальности. Градиенты имеют вид поверхностных интегралов, для вычисления которых могут быть использованы результаты главы 6.

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

В шестой главе с помощью теории ОДП выводятся алгоритмы вы-

числения определенных интегралов высокой кратности (до 20 и выше).

В п. 6.1 рассматриваются многомерные параметрические интегралы вида

J(a) = Г f(a,s.,...,x )dx ...dx , (19)

jJ 1 n 1 n

где X = XIз) s (xeZ x...xX | g(a,x)*0)w 8 ~ вектор-функция.

1 в In

Аналогично (17) представим функции ? и g в виде f(a.x,...,x) = f(f t(~(V,(f,(s,x ),x ),-),x ),х ) .

1 an в-1 2 1 12 а-1 я

8(9.х ,...,х)=в(г .(~(8j&t(3,X ),X ),-),X ),Х ),

1 оа а-1 2 1 12 а-1 а

где f, и 8. (i=fjn) - некоторые вектор-функции.

% г

Применим к задаче интегрирования (19) теорию ОДП. Пользуясь представлением кратных интегралов в виде повторных, ее можно записать в стандартном виде (4), где свертки - одномерные интегралы. Тогда приняв уравнения перехода ОФВ в виде, например,

у = со1(1 (у\,х),8 )),..., у = col(f (у*.х ) ,g (у1 ,х ))

3 2 J 2 2 2 2 в*1 я я n они

(где верхние индексы, как и выше, обозначают соответствующие компоненты ОФВ, не обязательно скалярные), получим алгоритм

с (у ) = Г f (У*.х )dx

а а j J » » в п а

С.(у.) = Г с. .(9.аА,х,),8.(у*.х.))ах, , i=n^iJ2, (20)

» » jJ i 1 i I i i i

i

J(a) = CJyJ =J Ci(fl(3,xi),8l(3,xi))dxi где множества А. имеют вид

I

А = А (у1) = {х | 8 (У*.я J*0}. Л. = Л.(уЬ =

а по в в а а j j j

= te. I Л1л(8}(уг.,х.))*в). J=n=1JS, Ai = {х | Ax(Bja,xJ)+e) )

При реализации алгоритма (20) для построения функции С. на

i-м шаге (£=тг7Т) перебираются значения ОФВ у^ из некоторой сетки

в пределах множества, определяемого согласно главе 1 с учетом

специфики задачи (в частности, чтобы А,(уг)*а). Все приведенные

» i

в п.5.2 способы сокращения размерности ОФВ с незначительными изменениями годятся и для алгоритма (20).

Для семейств интегралов со скалярными функциями р. и g, (или одинаковой для всех I суммарной рэзмерностьп р. и 8-) числительная сложность алгоритма (20) приблизительно пропорциональна числу шагов п. Благодаря этому появляется возможность вф-

фектипно вычислять многие интегралы выоокой кратности.

В п.б.2 на основе алгоритма (20) выводится алгоритм для частного случая интегралов (19) - интегралов с мультипликативно-се-парабельной подынтегральной функцией. Для интегралов вероятности

3 - [ Р,(х,)'--Р (х )<3х

р 11 а

(где р.(х,), 1=ТТп, - соответствующие плотности вероятностей) он имеет вид

С (У ) = Г Р (х )вх ,

а п ^ J *и а в а

с,(у.> * I Р.(*.)-С. .Шу..я.))Оххш <=л"=775, (21)

V 1 А» ч » ч»1 ч » ч I

3 = |

А1

где А, - че ив, что и в п.6.1 (но игреки - без верхних индексов).

В п. 6.3 подробно разбирается применение метода заыоражива-ния переменных (п.2.3-4) для расширения области практической применимости алгоритмов, полученных в пп 6.1 и 6.2.

В п. 6.4 о помощью алгоритма (21) решается задача анализа качества системы управления ЛА, где качество оценивается по вероятностному критерию. Задача описывается линейными уравнениями движения с двумерным фазовым вектором (отклонения от опорных координаты и скорости) и аддитивным двумерным случайным возмущением. Требуется найти вероятность достижения цели управления, состоящей в невыходе отклонения от опорной координаты в терминальный момент времени из заданной окрестности нуля.

После преобразований задача сведена к вычислению интеграла вероятности - интегралу по пирамиде в п-мерном пространстве, где пк2Ы-1, 8 - число шагов в исходных уравнениях движения.

С помощью алгоритма (21) на ЭВМ ЕС-1045 получено численное решение задачи при п=3 (К=2), п=7 (N=4) и п=19 (N=10).

Для сравнения эффективности при п=3 интеграл вычислялся также традиционным способом. При втом для справедливости сравнения интегрирование в обоих случаях производилось "в лоб", поскольку известные способы сокращения вычислений и увеличения точности (переменная длина шага, частичное аналитическое интегрирование и др.) могут быть использованы и в предлагаемом алгоритме.

При п=3 время счета традиционного алгоритма составило почти 16 минут, а алгоритма (21) - 13 секунд при несколько лучшей точности (6*10*4£). Для обеспечения точности порядка 2« 10*3£ алго-

ритм (21) требует около 1,2 сек. При л>3 традиционный алгоритм бессилен, a алгоритм (21) позволил вычислить интегралы при п*7 -за 4,25 мин. при точности 0,1% (и 11 сок. при точности около 1,5%), а при п=19 - за 19,6 ши. при точности около 4 %.

В седьмой главе на основе теории ОДП выводятся алгоритмы высокоточного вычисления определителей и обращения матриц.

В п. 7.1 выводится алгоритм вычисления определителей матриц А = порядка п. За основу берется выражение определителя А через сумму взятых о соответствующими знаками произведений элементов матрицы. После преобразований теория ОДП позволяет получить следующий алгоритм: n-C+i

CJJ.-.J а..С. (J ,J ,-,J ),

» 1 »-»ti ¿j ijk 1 »-1 «♦* в-х+1

k= 1

C(J)=a . . C(J ,-,J ) « A , (22)

ni ujj 11»

где {ИР имеет смысл нижнего минора (соответствующего порядка) матрицы А, а аргументы ®Р - столбцы, присутствующие в миноре, расположенные по возрастанию их номеров.

При численной реализации алгоритма удобнее перенумеровать тем или иным способом миноры и использовать номера в качестве аргументов ШР. В пункте предлагается весьма удобная нумерация с использованием двоичной системы: номер минора равен сумме степеней двойки, соответствующих присутствующим в нем столбцам (так, номер минора С JJ ,J ,J ) со столбцами 1-й, 5-м и 6-м будет

я-2 12 3

равен 21"1+ 26"1+ = 49). При такой нумерации все миноры порядков от 1-го до п-1-го сохраняются до самого конца. Это, во-первых, позволяет использовать для всех шагов один и тот же массив, постепенно его заполняя по мере продвижения по шагам - с использованием уже заполненных его ячеек, соответствующих минорам низших порядков. И во-вторых, сохранение миноров всех порядков может пригодиться в задачах, включающих вычисление определителей в качестве подзадач. Например, для обращения матриц, вычисления мало отличающихся определителей (в том числе нескольких пересекающихся миноров одной матрицы), параметрических определителей (в частности, выяснение зависимости от параметра) и т.д.

В п. 7.2 представляется рациональный способ реализации предлагаемого алгоритма (с двоичной нумерацией миноров), записывается детальный алгоритм. Приводятся также результаты численных расчетов. По трудоемкости предлагаемый метод радикально эффективнее

метода непосредственного вычисления (определителей) и его аналогичных по трудоемкости вариаций, использующих разбиения по строкам или столбцам (уже для п=9 - в 1400 раз, причем с ростом п последнее число стремительно растет). С методом, использующим приведение к треугольному виду, и близкими к нему по трудоемкости методами Ш/-разлокения, преобразования Хаусхолдера и другими предлагаемый метод сравним по эффективности (при малых п он вфек-тивнее, начиная с п=7 - начинает уступать, при п=13 он уступает примерно в 30 раз). Однако перед ними предлагаемый метод имеет два существенных преимущества. Первое - высокая точность вычислений (свойственная лишь методам непосредственного вычисления определителей, а нередко и еще выше), а также отсутствие сбоев ЭВМ, свойственных этим методам при работе с почти вырожденными матрицами. Второе - отсутствие делений, что делает етот метод эффективным и удобным средством ручного (без ЭВМ) вычисления определителей матриц невысокого порядка (до 7+8, а при некоторых видах матриц и выше), и особенно целочисленных, что продемонстрировано на примере.

В п. 7.3 предлагаются некоторые методы и подходы по повышению потолка порядка матриц (л«25), доступных для предлагаемого метода, и повышения эффективности последнего.

В пункте также представляется другой вариант реализации предлагаемого алгоритма (в рамках той же двоичной нумерации).

В п. 7.4 предлагается использовать метод, полученный в п.7.1, для обращения матриц - вычисляя алгебраические дополнения. Он очень подходящ для такого способа обращения, поскольку в силу своей конструкции позволяет вычислять сразу значительную часть алгебраических дополнений почти с теми же затратами, что и один из них, да и для вычисления оставшихся используются многие уже полученные промежуточные результаты вычислений. Это связано о тем, что любые два дополнительных минора одной матрицы, как известно, различаются не более, чем одной строкой и одним столбцом (возможно, с перестановкой). Поэтому затраты на вычисление всех алгебраических дополнений относительно невелики: при самой пртят-тивной алгоритмизации они примерно лишь в п/2 раз превосходят затраты на вычисление одного алгебраического дополнения (а при идеальной - ориентировочно лишь в два раза).

В п.7.5 очерчивается область применения предложенных алгоритмов. Это

1. Высокоточное вычисление определителей и обращение матриц

(особенно важно для почти вырожденных матриц): до п«25 - произвольных, более высокого порядка - разреженных (особенно с нулевыми блоками, ленточньп), целочисленных, а также о использованием методов понижения порядка, экономии памяти.

2. Ручное (без ЭЕМ) вычисление определителей матриц невысокого порядка (до 7+8, а для разреженных матриц - и выше), и особенно целочисленных.

3. Вычисление зависимостей определителей матриц от параметров, а также вычисление определителей семейств матриц с общими блоками.

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

В восьмой главе приводятся еще два приложения теории ОДП.

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

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

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

Приведен пример, демонстрирующий сказанное.

В девятой главе на основе полученных в диссертации результатов решается задача оптимальной коррекции движения стационарного ИСЗ (СИСЗ) с помощью корректирующей двигательной установки (КДУ) малой тяги при движении его в плоскости и окрестности стационарной орбиты. Критерий оптимальности - прямой вероятностный.

В п. 9.1 приводится постанозка задачи к производятся некото-

рыв преобразования. Предполагается, что спутник ухе находится в плоскости екватора на орбите, близкой к стационарной. Целью коррекции является приведение спутника на стационарную орбиту в заданную точку виоения. Управление осуществляется с помощью включения и выключения ИДУ малой тяги. При этом тяга направлена вдоль нормали к текущему радиусу-вектору и в течение активного участка постоянна, но при очередном включении может быть направлена в противоположную сторону.

На основе уравнений движения в полярных координатах А.А.Лебедевым и В.В.Малышевым с помощью линеаризации и дискретизации получены следующие уравнения движения СИСЗ (дополненные здесь аддитивными случайными факторами):

Р. р р

i» С» íi \ 3\ Гф u V

- -4- Т?Ь. + ■ 4 (1-соз 2ЯХ.)Ъ. + ü , t = тл? .

^ i • e2jr;í i г 1»

Г . = X - ЗТ Ь, +01 , 2**1 2» i i 2>

2г

х , = х соз <р + х sin р. + -(1-соз 2%Х,)Ъ, + и ,

3«*1 3% I Ь % (2К) 1 1

гь.г

Г . = - X .sin Р. + X СОЗ в. + -* Sin 2КХ, + Ü ,

<»♦1 3» г <! i (2ъ)г 1 <г

где время считается в сутках, - отклонение от заданной долготы в момент времени t, (момент t-1-го выключения КДУ): г - те-i t\ кущая скорость дрейфа; х их характеризуют эксцентриситет е,

3i _^ v

и связаны с ним соотношением е.= ~ J х\. + х\. ; г - радиус

i " э» <« о

Р. 0

стационарной орбиты; -gj = 1 ! Е. и - продолжитель-

ность соответственно активного (ВДУ работает) и пассивного (КДУ

не работает) í-ro участка (At. A t, -í. = t.+ t.J; b,= ±b

i t+1 » l >

(b характеризует тягу КДУ), а и а = 773, - независимые

и

случайные величины.

Параметрами управления в задаче являются число N включений КДУ, направление тяги КДУ (т.е. знаки b ), длительности т. актив-

I « _

них участков и промежутки Ai. времени между выключениями КДУ при

ограничении t„.= At.-T.a t_.

"i i > i Предполагается, что получено решение

(íí.'bi»,ti.'Aí1».....bv»,T*»,AV; задачи т°чного перевода СИСЗ

на требуемую орбиту (т.е. в состояние (0,0,0,0) ) при отсутствии

возмущений. Действие возмущений предлагается парировать малыми

изменениями Ат. длительностей активных участков. Производится ли-1

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

LV. , = At..A3\- 3T.,b.£ . . {♦1 "i »* i 1» »• i li

Al. = Lr - 3b..AT.+ F . itl i %• » Si

где As. - отклонение от опорного значения г: At/. - новая пере-

I 2« >

менная (введенная А.А.Лебедевым. В.В.Малышевым), близкая при малом эксцентриситете к отклонению от заданной долготы; £ , = ы -5 ll 1«

" -^V «« - V

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

В соответствии с втим ставится задача максимизации вероятности достижения заданного состояния:

•J(AT) = P{JfAu ,Ат —» шх ,

Ui АТ, |AT, | sAT

(вид функции F заранее не уточняется, т.к. разрабатываемый алгоритм годится для разных функций). При этом ограничение Ат1 выбирается таким образом, чтобы екцентриситет был достаточно мал (используются два последних уравнения в линеаризованной системе).

В п. 9.2 для решения поставленной задачи используется метод ДП и разработанная в главе 3 методика радикального сокращения объема вычислений.

После разбиения каждого шага дискретизации на три подшага (согласно методике) рекуррентные соотношения для ФПР записываются в виде:

I>

z\,z\) = тпах С (2Í+2JAí. -3X..&..AT. ,2?-ЗЬ..АТ J

* » » AT., IAT. IsAt* ,il/3 » « »' •»>»«« »• »

при краевом условии

С (z1 ,z* ) = к+1 *♦! »«i

1. если F(z\ ,z* ) so IUI *«1

О в противном случае В 8Т0М Жб ПУНКТЭ ПОКаЗЫБйёТСЯ, KSK ПрймомЯЗТОЯ М9тОДИК5 При

налички еще и мультипликативных возмущение.

- В п.9.3 производится детализация алгоритма численного решения задачи.

В п.9.4 приводятся численные результаты решения, показывающие, в частности, работоспособность и эффективность алгоритма. Кроме того, производится оценка эффективности предложенной методики. С помощью расчетов, проведенных для сетки с 6 узлами (при даскре газированных компонентах случайного вектора и управляющего параметра, принимающих по 41 значению), вместе с дальнейшим анализом показывается, что без применения методики задача не может быть решена численно из-за слишком большого времени счета. В частности, при сетке из 61x81 узлов оно должно составлять около 7 суток на ЭВМ ЕС-1045. Применение методики сокращает ето время до 9,4 минуты.

В приложении представлены доказательства теорем.

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

1. Предложена идея и разработан аппарат теории обобщенного динамического программирования (ОДП), включающий в себя:

- оригинальное единое описание операторов на основе введенного понятия оператора-свертки по переменной;

- основанный на этом единый (стандартный) вид записи задач с рекуррентным применением операторов (РПО);

- введение функции промежуточного результата (И1Р) и рекуррентные соотношения для нее;

- механизм рекуррентной агрегации аргументов ФПР (в форме обобщенного фазового вектора - ООО), подход к нахождению подходящего ОФВ;

- концепции разбиения и объединения операторов;

- единый алгоритм решения задач с РПО (метод ОДП);

2. Разработана система общих методов, подходов и рекомендаций по наиболее эффективному применению теории ОДП - по записи задач в стандартном виде, разбиению сверток, поиску подходящего ОФВ и уменьшению его размерности, оптимизации алгоритмов.

Перечисленные выше результаты открывают возможность записи в едином (стандартном) виде разнообразных семейств задач (определенного типа) и получения для них методов (алгоритмов), по структуре аналогичных ДП и эффективных для широкого их круга. Кроме того, они дают возможность повыаения эффективности и самого ДП.

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

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

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

6. Предложен алгоритм сведения решения обратных вероятностных задач к решению прямых вероятностных задач. Это позволяет использовать метод ДП (и, соответственно, методику сокращения вычислений, метод замораживания переменных) не только для прямых вероятностных динамических задач, но и для обратных, для которых он непосредственно неприменим.

7. На основе теории ОДП получены алгоритмы (методы) решения широкого крута задач математического программирования (МП) - детерминированных, минимаксных, стохастических, минимаксно-стохастических и минимаксных стохастических (в том числе, со сложными ограничениями)..Предложены методы дополнительного повышения эффективности предлагаемых алгоритмов. Для широкого круга указанных задач предложенные алгоритмы представляются весьма эффективным средством решения. Сказанное подтвердилось при решении модельной минимаксной динамической задачи программного управления.

8. Выведены формулы для градиентов функций вероятности и

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

9. На основе теории ОДП получен не имеющий аналогов в литературе алгоритм (метод) вычисления определенных интегралов высокой кратности (от 3 До 20 и выше), имеющий для широких классов интегралов трудоемкость, возрастающую о ростом размерности примерно линейно. Записаны модификации базового алгоритма для интегралов вероятности и других частных случаев. Предложены метода повышения эффективности предлагаемых алгоритмов, в частности, метод замораживания переменных. Предложенный алгоритм уже для трехкратных интегралов на порядки превосходит традиционный метод. При больших же размерностях существующие методы вряд ли могут составить ему конкуренцию. Полученные алгоритмы могут быть весьма полезны при решении вероятностных задач управления и навигации, а также в других случаях.

10. С помощью полученного алгоритма решена задача анализа качества системы управления ЛА (критерий - вероятностный). Решение подтвердило работоспособность и эффективность предложенного алгоритма (в частности, легко вычислен 19-мерный интеграл).

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

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

12. На основе теории ОДП разработан метод поиска стационарных точек функций многих переменных и точек с заданным значением градиента.

13. На основе теории ОДП разработан метод решения систем

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

14. На основе полученных в диссертации результатов решена задача оптимального управления стационарным ИСЗ с прямым вероятностным критерием. Применение теории ОДП в ней позволило сократить объем вычислений по сравнению с непосредственным применением ЦП на три порядка и тем самым решить неподъемную для ДП задачу.

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

1. Малышев В.В., Карп К.А., Чернов Д.Э. К вычислению градиента квантили в задачах вероятностной оптимизации. // Проблемы оптимизации качества управления полетом и навигации воздушных судов. - Киев: КИИГА, 1987- 0. 61-71.

2. Малышев В.В., Хибзун А.И., Чернов Д.Э. Два подхода к решению вероятностных задач оптимизации. // Автоматика, 1987, N 3. С. 29-36.

3. Малышев В.В., Чернов Д.Э. О решении стохастических задач позиционного управления со сложным вероятностным критерием. // У Всесоюзная Четаевская конференция "Аналитическая механика, устойчивость и управление движением". Тезисы докладов. - Казань: КАИ,

1987. С. 64.

4. Малышев В.В., Чернов Д.Э. Основи теории последовательных операторов. - М.: ВИНИТИ, деп. 21.08.87, N 6149-В87. - 89 с.

5. Малышев В.В., Чернов Д.Э. Оптимизация коррекции СИСЗ по вероятностному критерию. // Тр. XVI Гагаринских чтений. - М.: Наука, 1987. С. 70.

6. Малышев В.В., Чернов Д.Э. Динамические задачи управления с вероятностными критериями. // Изв. АН СССР. Техническая кибернетика, 1988, N 4. С. 213-217.

7. Малышев В.В., Чернов Д.Э. К сокращению вычислительных затрат при использовании метода динамического программирования.. // Автоматика, 1988, N 5. С. 52-58.

8. Малышев В.В., Чернов Д.Э. Некоторые аспекты эффективного применения динамического программирования. // Моделирование систем информатики. Тезисы докладов. - Новосибирск: ВЦ СО АН СССР,

1988. С. 72-74.

9. Чернов Д.Э. Теория последовательного применения операторов в задачах вероятностной оптимизации. // Вопросы совершенствования информационно-измерительных и управляющих систем воздушных судов. - Киев! КИИГА, 1989. С. 34-48.

10. Малышев В.В., Чернов Д.Э. О повышении эффективности динамического программирования. // Международная школа-семинар по методам оптимизации и их приложениям. Тезисы докладов. - Иркутск, 1989. С. 135-136.

11. Чернов Д.Э. Динамическое программирование. Замораживание переменных в методике сокращения вычислений.// Изв. АН СССР. Техн. кибернет.. 1990. N 3. С. 121-127.

12. Чернов Д.Э. Теория последовательного применения операторов в задачах оптимального управления. // Всесоюзная школа-семинар "Динамика полета, управление и исследование операций". Тезисы докладов. - М.: МАМ, 1990. С. 109-110.

13- Чернов Д.Э., Леонов В.В. К вычислению многомерных интегралов вероятности в задачах оптимального управления летательными аппаратами. // Управление и навигация ДА в условиях параметрической неопределенности. - М.: МАИ, 1991. С. 57-62.

14. Малышев В.В., Чернов Д.Э. О решении стохастических задач позиционного управления со сложным вероятностным критерием. // Проблемы аналитической механики, устойчивости и управления движением. - Новосибирск: Наука. Сибирское отделение, 1991. С. 162-170.

15. Малышев В.В., Чернов Д.Э. О повышении эффективности динамического программирования // Численные метода оптимизации и анализа. Сб. научных статей. - Новосибирск: Наука. Сибирское отделение, 1992. С. 35-41.

16. Чернов Д.Э. Вычисление определителей и обращение матриц с помощью теории обобщенного динамического программирования. // Изв. РАН. Техническая кибернетика, 1993, N 6. С. 214-221.

17. Малышев В.В., Чернов Д.Э. Обобщенное динамическое программирование. Общие положения. // Автоматика и телемеханика,

1993, N 12. С. 101-110.

18. Малышев В.В., Чернов Д.Э. Обобщенное динамическое программирование. Некоторые приложения. // Автоматика и телемеханика,

1994, N 1. С. 117-127.