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

«'.и О* 2 '» НОВ

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

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

ОБОБЩЕННОЕ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ И ЕГО ПРИМЕНЕНИЕ да ЗАДАЧ УПРАВЛЕНИЯ КОСМИЧЕСКИМИ АППАРАТАМИ

05.13.01 - управление в технических системах

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

Москва - 1997 г.

Работа выполнена в Московском государственном авиационном институте (техническом университете)

доктор технических наук, профессор В.В.Малышев

доктор технических наук, профессор В.С.Поляков;

доктор физико-математических наук, профессор В.В.Александров;

доктор физико-математических наук, профессор М.М.Хрусталев.

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

Защита состоится "_11 _ 199_ г. в _ часов

на заседании диссертационного совета Д 053-18.08 в Московском государственном авиационном институте (техническом университете) по адресу: 125371, Мосюза, ГСП, Волоколамское шоссе, дом 4.

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

Автореферат разослан "_11 _ 199_г.

Отзывы просим направлять в двух экземплярах, заверенных печатью, по адресу: 125871, Москва, ГСП, Волоколамское шоссе, 4-

Ученый секретарь диссертационного совета доц. к.т.н.

Научный консультант:

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

К.А.Карп

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

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

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

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

В соответствии со сказанным, для построения и реализации современных надежны! и эффективных систем управления КА чрезвычайно актуальной является проблема модернизации имеющихся и разработки

д

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

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

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

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

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

- Аппарат обобщенного динамического программирования (ОДП), включающий в себя обобщение операторов перехода от шага к шагу н соотношениях ДП, единый (стандартный) вид задач, рэссттрт<;»шп. ОДП, рекуррентшю роотношенил для вводимой функции иромпжугочпоги результата (<W1Pi, ыьединие обобщенного фазового вектора (<A>bi <•• целью рекуррентной агрегации аргументов ФПР, подход к нахождения ОФВ, концепции разбиения и объединения операторов и, наконец, единый алгоритм решения рассматриваемых эадач (метод ОДП).

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

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

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

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

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

- Решение с помощью ОДП задачи оптимизации коррекции стационарного ИСЗ о двигателем малой тяги по прямому вероятностному критерию. Решение задачи анализа качества системы управления стационарным ИСЗ (критерий - вероятностный).

- Решение о помощью ОДП задачи планирования съемки наземных объектов системой ИСЗ.

о

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

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

Полученные в диссертации результаты могут быть использованы при разработке и эксплуатации систем управления КА. в соответствующих организациях. В частности, они внедрены и используются в НПО им. С.А.Лавочкина, в НПО ЦНИИМА1Е и в МАИ. При этом многие результаты диссертации имеют более широкую область применения. Теоретические результаты также могут быть использованы при чтении курсов по оптимальному управлению и методам вычислений. В частности, они внедрены в учебный процесс и использованы на механико-математическ-тэм ф-те МГУ (в курсе "Оптимальное управление движением", читаемом аспирантам кафедры прикладной механики и управления), а также в МАИ.

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

Апробация работы. Основные результаты диссертации были доложены автором на международной школе-семинаре по методам оптимизации и их приложениям, на 1У Международном семинаре "Устойчивость и колебания нелинейных систем управления", на четырех всесоюзных конференциях (в том числе сделан пленарный доклад на V Всесоюзной Четаевской конференции), а также на различных семинарах.

Диссертация в целом апробирована на семинаре в ЦНИШАШ, семинаре кафедры 24 ВВИА им.Жуковского, семинаре кафедры прикладной механики и управления механико-математического ф-та МГУ, семинаре кафедры исследования операций ф-та ВМиК МГУ, семинаре академика Ф.Л.Черноусько в ИПМ РАН, семинаре профессоров В.Ф.Кротова и

ь

Е.С.Пятницкого в ИЛУ РАН, семинаре кафедры прикладной математики МГТУ и семинарах кафедр "Системный анализ и управление" и "Теория вероятности" МАИ.

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

На защиту выносятся:

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

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

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

Структура и объем диссертации. Диссертация состоит из введения, трех частей, содержащих восемь глав, выводов, приложения и списка литературы из 153 наименований. Общий объем работы - 281 страница, в том числе 7 рисунков и 21 таблица.

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

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

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

В первой главе вводятся основные понятия и положения, разрабатывается аппарат ОДП.

В начале главы приводится краткий обзор по теме диссертации,

¡з которого следует, в частности, необходимость развития и обоб-19ния ДП. Кроме того напоминаются соотношения метода ДП в динами-[ееких i!ад-14я? синтеза оптимального управления (ОУ) о дискретным феменем. Например, при разностных уравнениях

z. = g.fz.,u.,UJ, 1 = 1 z и W - заданы , (I) »♦1 i » i \ l

эписывающих движение, и критерии

E6?(X,u.,WJ + ?{z Л —> mln (2)

иц.1 * ' ' 1 J ueU ^

* l н

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

R.(z.) = mln II.. fg?iz.,u.,B J + Л. 4fg.iz.,u.,UJ.)] , » » ц > » » » »♦! 1 » » i J

WW : ' (3)

Здесь z- я-мерный фазовый вектор состояния управляемого объекта i

в t-й момент времени (на i-м шаге), u.eU <йг, u,=u,(z ) - вектор

> « lit

управления, U е О,«Й*- вектор случайных возмущений (ti , и., и

i . rt k j k

и и попарно независимы при k*J), g., g. и F - некоторые задан-

j 1 1 к

ные функции, и = соКи . U = colfO ,...,0^.), Ми - усред-

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

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

»г »

исчезают соответствующие переменные (и. и и.). Т.е. он как бы

i i

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

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

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

UT UT

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

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

о

имя "/" зарезервируем именно для этого и только для этого. Так,

например, соотношение con (p,f(t)) = 2 min f(t) + p означает

teT UT

лишь то, что данная параметрическая свертка (G-W=Fr) является минимизацией с удвоением полученного результата и прибавлением к нему параметра р.

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

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

W с {g:P —» IVj}, то указанный оператор А может быть представлен еще и в виде р-параметрической яг -значной свертки.

3. Свертка оперирует о функциями конкретной переменной.

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

х. к функции аргументов х.....х ,х. является функция аргумен-

г i »-i i

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

сверток. Пусть некоторая р-параметрическая свертка по íef применяется к некоторой функции <Q(s,t), определенной на SVT. Пусть

р еР, з eS. Тогда сол (p,<p(3,t))\„ „ и con (рл,$( 3n,t)) • Это о о tcI. 1ро* о tcT 4

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

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

5. Поскольку, как установлено в замечании 4. свертка применяется при фиксированных значениях параметров как самой свертки, так и сворачиваемой функции, то ситуация не становится неопределенной и в случае совпадения некоторых аргументов-параметров сворачиваемой функции с некоторыми параметрами свертки. При этом ре-

а

зультат применения, например, свертки con (р,-) к функции ) будет при р=р равен сon (р ,ф(р ,t)). Примером может служить па-

0 ^ О О

раметрический интеграл J(p)=P\ $(p,t)dt, который является резуль-

<У .

татом применения параметрической свертки con(p,f(t)) - /<í >dt к

t (У

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

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

Например, con (p,f(t)) = mlп f(t). В етом примере (см. также teñ1 tcfp.p+IJ

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

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

+ooJ

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

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

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

пример, состоять из некоторой другой свертки и функции.

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

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

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

J(s) = con con ... con F(3,xü • • ,x ) = ? (4)

id icí x 1 * n

112 2 un

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

1 n 0 n

некоторые множества; F - некоторая функция, F : SxX x...xX —»ff ;

1 n n

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

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

х.еХ., определена на ff.-значных функциях переменной х.еХ. и яв-»t \ ti ляется ff. -значной и, вообще говоря, параметрической о парамет-»-1

рами з, г.....х, ., т.е. записывается в виде

1 г -1

соп(з,х ,...,х ,•)• Обратим внимание, что от втих же парамет-

х. 1 1-1

i

ров, вообще говоря, зависит и функция, к которой эта свертка на деле применяется в (4) (см. замечание 5).

По аналогии с функцией будущих потерь, фигурирующей в (3), введем функцию

С.(з,х ) = сотг ... con F(3,x .... ,х ), i=l;n*-1,

ti i-l £ g 1 л

i ti

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

\

ff -значной ФПР С, Лв,х ,-,х ,х). Результатом такого примене-» »♦ 1 i »-1» ния является ff, -значная ШР С (з,х ,-,х ), что позволяет \ -1 i i »-1 применять затем следующую, 1-1-ю свертку (2sisn) и т.д.

п

Очевидно, что для ФПР выполняются рекуррентные соотношения С J9.X.....X ) = F(3,X ,. . . ,Х ),

И ♦ 1 1 Л 1 II

0.(3,х....... ) = con (з,х.-,х. ,,С. (з,х ,x.)), t=ñla,

» 1 »-i ¡reX »-1 i ♦ i i «

í i

J(s) ш С (3) = con (s,C (з,х )). (5)

1 xxeX 2 1

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

з,ха,...,х, л должно позволять применять свертки со« con к

с

я

- г• - i-,

1 »-1 г г.

функции в (4).

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

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

У, = yjaj, у, = YJyt,xt)t ••• » У . = * (У .х )

"1 О lit "ntl n n n

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

(6)

2) на каждом t-м шаге (l=f;n+í) он содержит информацию о

значениях переменных з,г ,~.х, . достаточную для применения

i »-i

сверток сап ,...,соп и вычисления функции F. Или, иначе говоря, х х.

для любого 1=1 ;п-1-1 ОФВ позволяет в списке параметров любой й свертки (J=i ;п) и функции 7 заменить з,х 4 на у., т.е.

соп (з,х,,-,х. ,•) заменить на согг(у. ,х., - ,х. . а

т 1 г • ' I'1

] ]

Е(з,х.....,х ) - на 2(х1.,х.,...,х ).

1 П \ \ 1>

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

«1 »-1 » <

Заметим, что свертки и функция Е при замене з, ......х

1 «-1

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

Введем также вспомогательное понятие ОФВ свертки.

ÍA

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

У.. 'У. Ja). y¡.=Y.Jy..-*.).....У.. "У. . Jy. . )

jl jO j2 jJ jl 1 jj J.J-1 J.J-1 j-1

(где y,.- J-й ОФВС на i-м шаге, У - некоторые функции), ji jk

2) на каждом 1-м шаге (£=777) он содержит информацию о

значениях переменных а,г ,-,х. ., достаточную для применения

i >-1

J-й свертки (или вычисления функции F при J=n+1).

n+í-й ОФВС, соответствующий функции F, будем также называть ОФВС функции F.

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

Теорема В задаче (4) ОФВ (а также любой ОФВС) существует и не обладает единственностью. В частности, всегда существует

тривиальный ОФВ (аналогично ОФВС) вида у, = соКз.х , -,х, ),

> 1 i -1

£=T7ñ+T, т.е. Yq(3) ~ з, Y^(y^,xv) = col(y^,x^), k=TJñ. Такой ОФВ

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

Теорема Любой ОФВ задачи (4) является также и J-и ОФВС

для любого J=1;п+1. С другой стороны, если у ,..., у - все

1 л+11

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

i it n + i, i

задачи (4). Иначе говоря, простое соединение всех ОФВС задачи уже само по себе является ее ОФВ.

Теорема Если в задаче (4) свертки с первой по п-ю - непараметрические, то любой й ОФВС (т.е. ОФВС функции У) является также и ОФВ,

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

С Jy .) = Р(у ,)>

п ♦ 1 п + 1 ^п»!

CJy.) = con(y.,C. JY.(y. ,х.))), l=ñjl, i « х.еХ. 1 ' 1 '

i >

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

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

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

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

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

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

х. ,...,5с. в одну свертку по переменной col(x ,-,хJ, получим i-k » i-k » соотношение

С. Гу. J = con С. (Y,( ...Y. (у. .х. J.....х.)). (8)

t-« «-* j, — X 1 1 1 ' ' 1

i - k i

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

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

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

о.1*

(также в точках соответствующей сетки) функции С (у ). Мно-

_ »«1

хество В, (1=1,п+1), в пределах которого достаточно выбирать

точки сетки, ох'раничено следующим образом:

В.сУ/Б) 4 {У.Га; I зсй}, 2>.е У. (В, ,Д. ) , иТ^СЛ. (9) 10 0 » »-I \-1 »-1

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

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

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

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

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

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

или нескольких шагов, на которых ОФВ имеет слишком большую размерность .

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

Пусть некоторый компонент ОФВ на й-м шаге не поглощается ОФВом на нескольких следующих шагах (см. (6)) и до ./-го (nzJ>k>¡) шага сохраняется как компонент ОФВ. Для определенности положим, что этот компонент первый и остается первым, т.е. у\=у\ ^...-у*.

При стандартном использовании алгоритма (7) его фрагмент,

соответствующий вычислению ШР С.....,С , просчитывается при ОФВ

1 *

у.сИ = ЛсО2, С=/7£ (где {у11}... ,у(1>} соответствует дискре-

1« кг к к к

газированному компоненту у*). Метод замораживания переменных позволяет заменить этот фрагмент на X последовательно просчитываемых фрагментов с у.сО?. Благодаря етому при том же объеме вычислений

11 I 1

размерность ОФВ уменьшается.(не требуется компонент у: ^ у*).

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

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

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

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

Сначала указанная методика разрабатывается в общем виде.

Применим ОДП для решения задачи (1), (2). Данная задача фактически уже записана в стандартном виде (4), где з отсутст-

вует, х.= со1(и,,ы,), свертки имеют вид

I » «

соп (г.,/(х.)) = соп (г.,/(и.,а,)) - М„ Г е°.(г.,и.,ы.) +

х. 1 1 и ,ч х 1 ' и «.1. » » »

» I > >

+ 1(и,,и.)\, а фазовый вектор г., 1=1;Я+1, связан с другими пе-

> I ] I

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

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

Пусть функции g. и в (1) и (2) предетавимы в виде:

I «

1111 1111 \ вЧ(г. ,и.,«.; = 8й}(2..х1,) + 5?г0р.<Х,:г!;,х?; , (10)

I I < I II» » » » I I

где х. и - соответственно п- и й-мерные вектор-функции, а векторы и х? независимы между собой и

• I

со 1(2?;,з?.) = соКи, ,а.) и х. (т.е. и.хП. = Х!хХг) с точностью до

«I >1 I II г 1

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

* I

Пусть Ъ£п (случай £>гг рассматривается ниже). В этом случае каждую свертку по х. = со1(и,,Ц.) можно разбить на две

> II.

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

II II

пример, если х\ = со1(и*.-,иГ,И*,~,<<>}). х? = соХГи^1,-,^^» то

согг (г.,з£,/(а*)) Г + /(х?Л

» » 1 « » » » « « J

¡ i

пег.,/^;;» mln М, Г * /^Л.

i 1 ' и.,-,иГ. »J

con X

I

Для изменившегося стандартного вида запишем уравнения z- = Ч.(г.,хЬ , z. = г.(2. , U77» , (11)

»«1/2 iit ni i i»l/2 i

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

ifl/Г , 1*1/2' i»l » М/2' I

х2. \

С.(а.) = con Гг.,С. ,Jt?Jz.,x*)) , <=fM , (12)

» t ,i i*l/2 » « i г:

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

z по отношению к исходной задаче представляют собой промежу-1*1/2

точные фиктивные фазовые состояния.

Предположим, что для реализации соотношений (3) используется

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

решения задачи при использовании (12) вместо (3) объем вычислений

сокращается примерно в V*V*/(V*+V*) раз (где V1 и V2 - коли -

till i 1

чества перебираемых значений векторов х] и if). Поскольку нере-

1 »

бирается обычно большое число значений (т.е. V* и V? велики),

1 «

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

случаев эффект может оказаться еще выше (например, когда dim

2 <п или когда хотя бы одна ira функций ». и %. изменяет не \»1/2 » 1 вое компоненты ОФВ).

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

1 1

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

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

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

1

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

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

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

Пусть в задаче (1),(2) соотношения (1) линейны:

z. , ^ A.z,+ 8,и.+ и,, (13)

il il 1

ib

причем m=n, компоненты вектора х = соЦи,tí) независимы, a g? = О (для простота) при произвольной функции F в (2).

В этом случае каждая свертка con = min Мп разбивается на

V »

i i

J=n+r сверток min, -,min,H , ,М , а алгоритм принимает вид

«í «у и! ц-\ \

с. = М с. (г. * (о.....,

«♦(j-i)/j »»tj-ll/i ЦП í«t i

i.

е.* 'Л' ví = M* c*'.Vz.*' + ?e>;o;.:..b;V

i»r/j 1 J \f(r»tt/'j чг/j I

i

с , ,,..(2., )=minC. (z * B.-(0,...,0,ur.):),

»»tr-i)/j »♦ lr-1 J/j i*r/¡ «»Ir-D/j i »

С fzj = C. ,,.M.z. + B. •íuf.O.....0)T)

i I , »«1/j » » l \

i

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

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

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

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

z. = TítO+u. ,

lit < i i i i

и с функциями 8°- в критерии, имеющими вид

i i i i i I III i i i

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

1«1 lili l+l It«

где z\ и z2 (и и1,, и?) - группы компонентов фазового вектора (и «i i i

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

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

i i

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

ь

Z\ &\(ь\лг,.и\). 2? = 2? ,

¡♦1/2 » г » » »»1/2 «

г1 = г* г* = йг(г2 ,иЬ .

{♦1 1*1/2 !»1 М/2 »

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

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

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

Отдельно в главе 3 рассматриваются вероятностные динамические задачи оптимального управления.

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

Предположим, что цель управления достигается при выполнении неравенств 5 9 и 5 О, где ре("-»,<».) - некоторый

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

Рл(и) А Р{Ф<-г щ, (¡(г )*0} -* таг . (14) Р ям км Ц€1/

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

лива), приходим к задаче с уравнениями (1) и обратным вероятностным критерием

ФJu) = mtn{$ I vju)za) min , (15)

a v ueU

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

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

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

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

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

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

минимаксных задач МП, поэтому не будем на втом здесь останавливаться. К недетерминированным задачам МП метод ДО прежде не применялся.

Далее ОДП применяется к минимаксным задачам МП в достаточно общей постановке

пах b(u,v) -» min , пах Q(u,v) s О , (16)

veV ueü ueW

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

Irl»

Подобные постановки (особенно при ff=V) типичны для задач гарантированного одношагового управления (принятия решений) в условиях неопределенности (они представляют собой "игру" с природой и несколько отличаются от традиционных игровых задач). В них обычно требуется минимизировать некоторый критерий $(v.,v) (например, расход топлива) при наихудших воздействиях неопределенного вектора v из некоторого множества V при гарантированном (относительно тех же v) выполнении некоторого условия Q(u,v) s О , например, ограничения по скорости, ориентации.

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

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

Запишем множества U, V и W в виде U - {ueRr | G(uJsO), V = {veR9 I g(v)£ö}, ff = {уел* I h(v)so), где G, g и К - некоторые функции. Представим функции Ф (аналогично Q), g (аналогично h) и G в виде рекурсивно вычислимых.:

Ф(и,и) = Ф ^Ф J-P ГФ (и ,и ),~,и ),v ), -,v ),v ) ,

г*» г»ч-1 м1 г 2 1 2 г 1 »-1 »

g(v) = gje^f-fs/^'^ '■■■■) ,vm) ,

Giu) = G (G t(~(G(u.u), -),U t).u) , (17)

r r-1 2 12 r-1 r

где Ф (i=2,r+m), g. (i=2,m) и G. (1=2,r) - некоторые вектор-t < i функции. Такое представление всегда возможно. Вопрос лишь в том,

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

С помощью ОДП для задачи (16) получен алгоритм, один из вариантов которого имеет вид

С , (yi , ,yJ , ) = тюх Q Су1 , w ;,

■ « г*2а

с (у1,у2)= тах С (Q (yl,w ),h (уг,ю )), qkr+2m-1,

' 4 4 v) ее (у)я г< * * »-1 »-1 »

С Jy1 .,у2 .)= тх С (Q (yi ,w),h(y2

2 2 Уг««»2

С fy ) = тах С (Q (у t,w ),w J ,

г»«*1 p«««t jy r*»*2 г*1 г«а»1 1 1

с (1 ,уг ,y3 ) = rnox Ф (y2 ,v ),

p*. "p»a у eB fj.3 ; r»» P*a »

■ я р«»

С(1,уг,у3)= тах С (1,b(y2,v ),g iy3 ,v

4 4 4 v eS (У ) r" * 4 * 4 *"

■ -1 ■ -1 q

2 2 p*2

С (1,y2 J = тах С ( 1 (у2 t,v).v) , rtl г«1 у r*2 r<t r<l 1 1

С (0,y2 ) = C JO.y2 > =...= с fO.y2 J « С /у2 J •

p»l r»l r-»2 r»l r«» r»l p»a»l r»l

С (у1,у2,у3) = min С (1Л (у1,и )),

Г Р Г Г u ^¡J Г*1 Г Р г

где И = {и Су5; | с (0,<3 Су2,и ;;*о}

г г г г»2 г вр г

с (у1.у2.уг) = яш с сф гучи ;.q fy2,u ;,g гу»,и ;;

4 4 * 4 и еЛ (у*) г«чч ч q ч qqq

(У ч q ч

q=r-},

С (у ) = min С (Ь (у .и ),Q (у m),G (у ,и )) , 22 U GA (и ) 3 2 2 2 2 2 2 222 2 2 2

J = min С (и ) , (18)

и 2 1 1 1

где множества Е. (аналогично А. и В.) имеют вид

i г i

Е = Е (у2 ) = {т | h (у2 ,ш jsO},

ж я р» 2» а « rt 2« в

Е. = Е/у2 J = {ш. | Е. (h.(y2 ш%т.))*а),

] 1 r*»»j j j Г»»м j

= {"'j I E Сш^^я}, верхние индексы у игреков означают соответствующие компоненты ОФВ fне обязательно скалярные;. При у1= О и при = 1 ((=r+i ,гт) второй компонент ОФВ имеет различную ири-

роду, поэтому при у: = О он помечается волной, а вообще уравнения 1

перехода ОФВ можно проследить по непосредственным аргументам ФПР

б правых частях соотношений (18).

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

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

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

МЕ юг Ф(u,£,v) -» min , М- wax Q(u,l,v) s О ,

* ueV ueU ? veW

где U, 7 и ff - те же, что ив (16), а £сЗсйк - случайный вектор.

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

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

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

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

4'к

чество оценивается по вероятностному критерию.

Рассмотрим многомерный параметрический интеграл вида

Лз) = Г р(з,х.....х )бх . ..<±г , (19)

1 я 1 и

где X = Х(з) = {яеХ х...хХ | е(з,х ,-,х , 8 ~ вектор-функция.

1 п 1 В

Аналогично (17) представим функции р и ев виде р(а,хй....,х ) = р (р /~:(р/р/з,х ),г,),~).х ),х) ,

1 к л п-1 2 1 12 п-1 л

В(3,Х>.....X ) = £ (8 /-(6,(6/3,X ),Х.),-),X ),X },

1 и п п-1 2 1 1 2 п-1 п

где р, и 8, (1=йп) - некоторые вектор-функции.

« I

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

Тогда приняв уравнения перехода ОФВ в виде, например,

Ух = з, уг = соКр^у^х^гЗ^у^)),

у = С0КРг(у\,хг).8г(у\,хг)).....= соК^.Х1).б^.хх})

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

С (у ) = Г Р (у1,х )йх

в п ^ Л ч п п п п

о.(У.) = Г с, /Р.1у\,х.),8.(уг.,х.)№. , 1-0=775. (20)

I 1 д4 « » I 11 I I

i

Л(з) = С/у ) ^ Г С (р/з.х ),8/з,х ))<2х

11 ы 2 1 11 1 1 \

где множества А имеют вид >

А = А (уг) = {х | 8 (Уг.з )*0), Л. = А.(у\) =

П ПП 11ППП ) 3 ]

= (х. I А (е/уг.,х.»*а}, = Ц | А^в^з.х^^я) )

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

__I

£-м шаге (1=п;1) перебираются значения ОФВ у. из некоторой сетки в пределах множества, определяемого согласно главе 1 с учетом специфики задачи (в частности, чтобы А,(уЪ*»)• Приведенные в

I 1

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

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

1 I

(или одинаковой для всех { суммарной размерностью р. и в,) вы> I

числительная сложность алгоритма (20) ориентировочно пропорциональна п3/г. Благодаря этому появляется возможность эффективно

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

На основе алгоритма (20) выводятся алгоритмы для частных случаев интегралов (19). Для интегралов вероятности вида

.Г = Г р(х).....р (х }бх

уг} Г\ 1 » п

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

алгоритм имеет вид

С (у ) = \ р (х )бх ,

П П ^ } » я II

л

С.(у.) = Г р.(х.)'С. Лв.(у.,х,))бх., 1=п=Т?2, (21)

! Л" ' » « I »

I

\

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

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

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

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

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

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

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

При п-3 время счета при прямом интегрировании оказалось в 7'1 раза больше, чем у алгоритма (21) при несколько лучшей точности последнего. При п>3 прямое интегрирование невозможно, а алгоритм (21) позволил вычислить интегралы при п=7 и при п=19 при сравнительно небольшом времени счета. С помощью метода Монте-Карло вероятность не удалось вычислить с приемлемой точностью из-за большого объема вычислений (при п=3 вероятность составляла 0,999929, а ее вычисление требовало очень большого числа испытаний).

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

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

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

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

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

найти аналитическое решение задачи. Приведен пример.

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

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

Третья часть содержит две главы и посвящена практическим задачам управления КА, которые решаются с помощью ОДП и его приложений.

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

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

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

В настоящей главе задача коррекции движения СИСЗ ставится и решается в вероятностной постановке, отражающей такую важную характеристику качества управления, как вероятность достижения цели управления. При этом рассматриваются презде не учитываемы? случайные величины (входящие ы уравнения движения аддитивно).

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

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

Р 2

Z = Z + Z kt--1-СОЗ ffljz + -=-z .sin

í i*l í» 2i » r0 » 3« \

- -f- Z2b + —-— (1-СОЗ 2КХ.)Ъ. M . , l = 77ft , i \ j[2 \ \ ii

z = z - 31 b, + И . , 2>»1 2\ i \ 2i

Г

z = z соз o + z sin <0 + —(1-соз 2КХ.)Ъ. + U, , 3i*t 3« 4 4i 2Ъг i i 3»

b.r

Z = - Z 3Ín б + z соз tf + —4 3ln 2ПХ. + И . ,

«»•»i з; » »i i 2пг '

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

з» _i

/ / г г

и связаны с ним соотношением в = —- / z\, + z\. ; г - радиус

i Г . V 3 i 41 О

О

стационарной орбиты; 2П(Х .+■ t,,)¡ t. и t„ - продолжитель-

i i м < íi

ность соответственно активного (КДУ работает) и пассивного (КДУ не работает) í-ro участка (it = í -t = Т.+ t„,)\ b.- ±b

í 4l 1 \ 4v »

(b характеризует тягу КДУ), a u з = Т73, - независимые случайные величины. Значения z^, з = 774, - известны.

Параметрами управления в задаче являются число N включений

КДУ, направление тяги КДУ (т.е. знаки bj, длительности т. вктив-

« >

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

г

ограничении t = и -г.г t*.

и > ; » п

Предполагается, что получено решение С, «Ь^.Х^.Д^,.....Ь^.Х^.Д^,,) задачи перевода СИСЗ на требуемую орбиту при отсутствии возмущений. Для борьбы с воздействием случайных факторов вводятся в качестве параметров управления величины ДХ., представляющие собой отклонения от полученных длительностей т активных участков. Производится линеаризация от-

I*

носитвльно полученного детерминированного решения. Из линеаризованных уравнений первые два имеют вид Дг'. , = Дг'.+ Д{; Аг - Зх. Ь ДХ.+ Г. ,

Дг = Ая ЗЬ ДХ.+ Е . ,

2»*1 г» 1* « 2»

где Дз .- отклонение от опорного значения г : Дг' - новая пере-

2л 2» 1»

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

о 1» 1»

- ^2» " V

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

В соответствии с этим ставится задача синтеза ОУ, максимизирующая вероятность достижения заданного состояния:

ЛДХ) = ,Д2 )*0} —+ пах

111,1 211,1 АХ, |ДХ, |*гДХ

где выполнение неравенства Т(г±, )0 означает достижение

1М»1 2И»1

заданного состояния СИСЗ с требуемой точностью и является целью управления (вид функции Р заранее не уточняется, т.к. разрабатываемый алгоритм годится для разных функций). При этом ДХ* в ограничении выбирается таким образом, чтобы екцентриситет был достаточно мал (для получения оценки эксцентриситета используются два последних уравнения в линеаризованной системе).

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

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

С. (г1 ) = Мс С. (г^ ,22

С (г1 ,гг ) = МЕ С. (г1 ) ,

= тхс . С. (г^+г^. ,-ЗХ.Ь ,ДХ. ,г?-ЗЬ ДХ ) 4 1 1 ДХ,,IДХ. |£ДХ, ,,1/э ' 4 4 1 г 1 1 11

л>

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

(), если .2* ) * О

с (г ,22 ; = ] ки

»♦1 к»1 |р в противном случае

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

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

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

В восьмой главе рассматривается и решается с использованием ОДП задача оперативного планирования съемки компактных наземных объектов системой автоматических ИСЗ. Эта задача возникла в связи с проблемой контроля из космоса за экологическим состоянием ряда крупных городов мира. Актуальность этой проблемы признана рядом государств.

В.В.Малышевым и Д.В.Моисеевым была произведена постановка задачи планирования съемки поверхности Земли одним ИСЗ. С учетом прежде всего этой постановки ставится следующая задача планирования съемки системой ИСЗ.

Рассматривается система ИСЗ (см. рис.1), каждый из которых обращается по орбите с известными параметрами и несет съемочную и передающую аппаратуру, а также бортовое запоминающее устройство (БЗУ), в котором собранная информация хранится от момента съемки до момента передачи на Землю. При этом за время нахождения в зон« радиовидимости, вообще говоря, не вся информация, накопленная в БЗУ, успевает передаться на Землю.

Известны местоположения объектов съемки, а также условия их освещенности и прогноз состояния облачного покрова к моменту

Л

стон дня

приёма информации

\

V

71

/

/

/

у ->>

X

интервал

сброса

информации

•орбиты ИОз' подспутник оная линия

общий •'объект

<т □

- граница ооласти дости^мооти съомочион аиларатуры

- обьекти съёмки

- границы воамсшшх кадров

рис. I

съемки. Объекты предполагаются компактными, т.е. могут быть накрыты одним кадром. Размеры и расположение зон радиовидимости, в которых ИСЗ могут передавать информацию, также известны.

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

Необходимость в планировании съемки возникает главным образом из-за ограниченности емкости их БЗУ. Для системы ИСЗ наблюдения появляется еще один аспект, связанный с тем, что некоторые объекты могут быть сняты несколькими ИСЗ системы (но в различные моменты времени) и возникает дополнительная проблема наиболее рационального распределения таких объектов (которые будем называть общими) по ИСЗ, которым они доступны. При этом информация, собираемая о различных районов Земли, неравноценна как из-за различий в качестве, вытекающих вследствие различий в условиях съемки этих районов (освещенности, степени облачности и других факторов), так и из-за различной ценности самой информации, связанной с различными приоритетами съемки тех или иных объектов.

Задача планирования съемки с учетом компактности снимаемых объектов заключается в определении для каждого ИСЗ из системы такой последовательности моментов съемки (считая, что каждый раз делается один кадр), которая бы обеспечила наиболее эф!>ективное использование всей системы при заданных ограничениях. Эффективность функционирования системы ИСЗ можно оценить, например, количеством полезной информации, собранной в совокупности всеми спутниками системы, причем предполагается, что если информация от разных ИСЗ не дублируется, то она просто складывается.

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

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

¿л

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

Общее число объектов возможной съемки ,/-м, ИСЗ за пе-

риод планирования обозначим N.. Будем предполагать, что среди них нет повторяющихся. Некоторые объекты доступны для съемки несколькими ИСЗ (в разное время). Такие объекты будем называть общими. Общие объекты перенумерованы (произвольным образом) от 1 до Н.

Согласно сказанному на основе исходных данных для каждого 3-го ИСЗ, 3=Г,т, можно рассчитать последовательности ?г .....Н и а ,...,а. . Если (-й, 1=1 по счету объект

возможной съемки втим ИСЗ является общим, то Ь.. - есть номер етого общего объекта. Если же ©тот 1-й объект не является общим, то ?1..=0. Каждая величина а., представляет собой количество информации, которое может быть сброшено с БЗУ /-го ИСЗ за время между пролетом его (-)-го и {-го объектов возможной съемки.

Для кавдого 3-го, 3=1,ш , ИСЗ выберем моменты дискретизации t.. - моменты времени сразу после моментов возможной съемки, а - начальный момент времени. Таким образом ( будет меняться от 1 до ЛГ.+К Согласно оказанному для любого отрезка Г 4 ] известны Ь. - номер приходящегося на него общего

объекта ("О", если объект - не общий) и а. - количество информации, которое может быть сброшено с БЗУ.

Для каждого 3-го ИСЗ, /=ГТт , введем фазовую переменную

2.., 1=1.+1, характеризующую заполненность БЗУ (в кадрах): ]| )

г =0, если БЗУ полностью свободно, и г. =гест полностью зэ-

л )

полнено (предельная заполненность г" БЗУ го ИСЗ известна). По

условию задачи 0£г.&г*, причем начальное заполнение г, БЗУ бу-

)> I н

дем считать известным,

С учетом сказанного можно записать уравнения, отражающие динамику изменения заполнения БЗУ 3~го ИСЗ:

г . = таг { г .- а ; О } + и , 1=1 , (22)

где и.. - управление, которое по смыслу задачи равно "1" (1 кадр), если объект снимается, и "О", если не снимается, т.е.

и..€ и = (О; 1} . (23)

Имеется твкже и фазовое ограничение

О ^ 2, 5 г* . (24)

>«♦1 )

В качестве максимизируемого критерия возьмем взвешенное число отснятих объектов:

т

Л = У V & &

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

(это касается общих объектов), т.е. п

Ей 5 1 , Ь=Г,Н, (26)

№ *

где („ , Н=Г777, - номер шага для /-го ИСЗ, на котором тот может снимать общий объект под номером И. Если J-мy ИСЗ Л-й общий объект недоступен, то соответствующее слагаемое в (26) отсутствует.

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

Учитывая сказанное, математическую постановку задачи можно записать следующим образом. Для каждого /-го, ИСЗ требу-

ется найти такое программное управление, т.е. последовательность (и и, }, которая бы максимизировала критерий (25) при

уравнениях (22) динамики изменения заполненности БЗУ каждого ИСЗ и ограничениях (23), (24), (26).

При наличии общих объектов поставленная звдача не разбивается на отдельные задачи для ИСЗ и оказывается весьма сложной. Так, даже метод динамического программирования для нее неприменим, причем дело здесь даже не столько в "проклятьи размерности", сколько в отсутствии из-за ограничения (26) марковских свойств у всей системы.

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

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

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

Предположим, что каздый ИСЗ в течение периода планирования может снимать общие объекты с номерами в за-

писанной последовательности, где через Н. обозначено число общих объектов, проходимых J-u ИСЗ.

На первом этапе метода для кавдого J-гo ИСЗ, J-Г,т~ , о помощью ОДП при всех различных значениях параметров р ,...,

р. , , соответствующих общим объектам с номерами h(J,1),..., 1Н|,Я л

находится функция С.Гр ,...,р представ-

ляющая собой значение части критерия, соответствующей этому ИСЗ,

т.е. С =«7= Уй ц . Каждый параметр равен нулю, если Л I ^ л ]•

связанный с ним общий объект не снимается данным ИСЗ (соответствующее и„=0), и равен единице, если может сниматься (и..^(0,1))

3*

Представим рекуррентные соотношения для получения функции С , соответствующей ^-му ИСЗ,

Граничные условия для ШР имеют вид

С. „ гг. ) = О . (27)

Параметров здесь еще нет.

Пусть получена ФПР на {+/-м шаге, причем в ней уже появились параметры р , ... ,р , соответствующие общим льи.м .¡Ыз.н.)

объектам с номерами Ь.(J,з), ... которые ИСЗ прохо-

дит после 1 + 1-го шага. Иначе говоря, получена функция

С. . (р , ,...,р ,2 ). Покажем, как получается чьи,«)' чыз.нл'

функция промежуточного результата С., на очередном шаге.

Если и =0, т.е. (—й объект }-го ИСЗ не является общим, то согласно алгоритму ОДП для всех сочетаний значений параметров р.,,. ,,...,р......и значений г .ьЮ,... вычисляется

Р..,. . .,г..) = (28)

Л лЬ (Л, в > 11

С. . Iр. , ,™,р ,тах(г -о ;0}+и..

= ИИ

тохСг , -а ;0)+и ¿г* }* 1« 3 ! I

Л Л

Зо

Еелк «6 и.. = п(],з-1) * о, т.е. (-й объект /-го ИСЗ яв-

ляетоя общим под номером 1\(1,з~1)> то у С„ согласно сказанному

л

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

^1.1,5-1)

С должна быть вычислена при Р, . =0 и при р -1.

Чьи,^ Чьи,5-1)

Таким образом, при р . =0 (объект не снимается) для всех лЬ О,е-11

сочетаний значений параметров р. ,. р.. , и значений

г еГ0,...,2") вычисляется

Л» }

= С. .

ь<«1

Р.... .....Р.... .

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

р .....р и значений г„еСО,...,г*} вычисляется

41>и.'> ЧЫьНЛ л }

Л зМ.Ы) jhlj.IL) л

С- ■ 4

= пах

и. е(0;1),и,,: *1 '1

тюхСг,,-а..;0}+и,.£2*

J» J» 1« 1

Р....

В результате получим функцию промежуточного результата С.Ср ,...,р . если £-й объект /-го ИСЗ не

Л ^ з,н.» д

является общим, и ■ . .,»Рч,- ......Р-ч •

если является общим под номером h(j,з~1).

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

.11 лЫ) ]1

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

т

Ус/р. .......Р......) -» _ (29)

^ jl |Ыь1> JMJ.IL> ,Н

при ограничении

т

У р = 1 , m=Q? . (30)

& *

Отсутствующие параметры считаются равными нулю.

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

J = ( J (V.'-'J ), который указывает, каким ИСЗ мо-

opt ept opl

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

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

р ,...,Р , принимающие значения "О" и "1" предлагали, s) jh(j,H.l

ется заменять объединенным текущим параметром v = р + 2р + 2гр +

Ч чш.нл Чьц.и.-и ^jhij.B^aj и.-J

+ ... + 2 1 р , jHb»>

считая, что з-й по счету (в прямом времени) общий объект уже пройден алгоритмом (продвигающимся в обратном времени), а е»-(-й -еще нет. Для второго втагш дана укрупненная блок-схема алгоритма.

Предлагаемый алгоритм реализован в виде программы для ЭВМ. Программа опробована на задачах с различными исходными данными и показала достаточно высокую эффективность. В этих задачах число ИСЗ бралось от т-3 до »1=24, число общих объектов достигало 21.

С помощью полученной программы решена задача планирования съемки с реальными исходными данными. В етой задаче в качестве снимаемых объектов выступал ряд крупных городов мира, а съемка производилась с целью контроля за их вкологическим состоянием. Всего рассматривалось 25 городов, которые перенумерованы следующим образом: 1 - Москва, 2 - Вашингтон, 3 - Бонн, 4 - Токио,

зь

5 - Лондон, 6 - Париж, 7 - Оттава, 8 - Рим, 9 - Осло, 10 - Лиссабон, 11 - Мадрид, 12 - Белград, 13 - Будапешт, 14 - Вена, 15 -Варшава, 16 - София, 17 - Стокгольм, 18 - Хельсинки, - Бухарест, 20 - Прага, 2! - Копенгаген, 22 - Амстердам, 23 - Брюссель, 24 - Берн, 2Ъ - Афины. Система состояла из 3 спутников. Для указанной задачи рассчитана оптимальная программа съемки.

Таким образом, предлагаемые метод, алгоритм и программа доказали свои работоспособность и эффективность. Данная программа входит в пакет программ для решения практических задач оптимального планирования съемки наземных объектов системой ИСЗ.

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

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

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

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

- единый (стандартный) вид записи задач, рассматриваемых ОДП;

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

- механизм рекуррентной агрегации аргументов ФПР (в форме обобщенного фазового вектора - ОФВ).

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

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

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

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

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

Зо

случаях (в том числе, в задачах о линейными уравнениями движения). Получены оценки эффективности методики. Они подтверждены численно: например, в задаче оптимизации коррекции стационарного ИСЗ сокращение вычислений составило три порядка.

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

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

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

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

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

4. Получен алгоритм (метод) вычисления определенных интегралов высокой кратности (от 3 до 20 и вышй). Для широких классов интегралов он имеет невысокую скорость роста трудоемкости с рос-

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

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

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

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

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

'Произведено численное сравнение эффективности предложенного метода с существующими, подтвердившее высокую точность и достаточную эффективность первого.

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

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

6. Решена практическая задача оптимального управления стационарным ИСЗ с двигателем малой тяги (в вероятностной постановке). Применение ОДП в ней позволило сократить объем вычислений по сравнению с непосредственным применением ДО на три порядка и тем самым эффективно решить задачу.

7. Решена практическая задача планирования съемки наземных объектов системой ИСЗ. Применение ОДП позволило получить еффек-

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

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

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

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

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

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.

19. Чернов Д.Э. Обобщенное динамическое программирование и некоторые его приложения. // 1У Международный Семинар "Устойчивость и колебания нелинейных систем управления. Тезисы докладов. - М.: МЛУ РАН, 1996. С. 32-33.

20. Чернов Д.Э. Обобщенное динамическое программирование. Два новых приложения. // Автоматика и телемеханика, 1997, N 4- С. 103-112.

21. Малышев В.В., Чернов Д.Э. Планирование съемки наземных объектов системой автоматических искусственных спутников Земли. // Изв. РАН. Теория и системы управления, 1997, N 6. С. 76-82.