Введение к работе
Актуальность теми. В настоящее время, особенно в связи с азвитием космической техники, с усложнением в увеличением коли-эотва одновременно находящихся в полете (на орбите) летательных апаратов (ЛА), возрастанием оложности решаемых ими задач и цены шибки, особую актуальность приобретает разработка и реализация асокоточных и надежных систем навигации и управления.
Для обеспечения высокой точности и надежности названных сис-ем обычно требуется учет неконтролируемых факторов, рассмотрение остаточно адекватных моделей движения, использование критериев ачества, наиболее точно отражавдих реальные требования к втим истемам. Все это приводит к потребности в развернутом и сложном атематическом обеспечении. Указанное математическое обеспечение олжно включать в себя методы решения, в первую очередь, сложных адач оптимального управления (ОУ) различных классов. Это и дина-ические (многошаговые) задачи, которые, в свою очередь, могут ыть задачами синтеза и программного управления. Это и статичес-ие или одношаговые задачи (задачи математического программировали - МП). Должно оно включать и методы решения задач оценивания [ фильтрации, задач анализа качества систем управления и вавига-да, задач устойчивости и других.
С другой стороны, возможность реализации на практике уже меющихся достижений в этой области, в свою очередь, непосредст-іенно связана с наличием эффективных и высокоточных алгоритмов іешения подзадач из смежных областей. В первую очередь вто каса-!тся задач МП, возникающих практически во всех разделах оптималь-юго управления и навигации, да и не только в них. Касается вто акже вычисления многомерных интегралов (т.е. интегралов высокой іратности), возникающих при вычислении вероятности достижения цепі управления в задачах оценки качества (по вероятностному крите-ш>) систем управления и навигации, при решении вероятностных за-фч и во многих других случаях; вычисления определителей и обращения матриц (особенно плохо обусловленных матриц высоких размер-гостей), что повсеместно требуется в задачах фильтрации и управ-іения, в задачах устойчивости, в задачах планирования, построения жотем массового обслуживания, в комбинаторике; решения систем алгебраических уравнений и неравенотв, возникающих при поиске до-іуетимьц управлений или решений, при дезагрегировании найденных агрегированных решений "больших" задач оптимального управления, а
также некоторых других эадач.
Для всех перечисленных задач и подзадач методы и алгоритмы в той или ивой мере существуют. Однако при увеличении размерности задач вычислительные затраты при использовании втих алгоритмов обычно стремительно растут (очень часто - экспоненциально). Кроме того, большинство известных алгоритмов плохо приспособлено для решения очень многих задач, реально возникающих на практике - например, с функциями, заданными таблично или определяемыми опытным или расчетным путем, с "плохими" функциями.
Таким образом, модзрнизация имеющихся и разработка новых оф-фективных методов решения перечисленных задач и подзадач чрезвычайно актуальна и непосредственно связана с разработкой, построением и реализацией современных надежных и аффективных систем управления и навигации. При этом, учитывая высокую эффективность метода динамического программирования (Дії) в задачах динамического и статического управления, его универсальность и неприхотливость к виду функций и переменных, чрезвычайно заманчиво распространить его и на другие классы задач.
Однако не только нет общей теории ДП, позволяющей переносить его алгоритмы на новые классы задач, не только нет примеров применения ДП к нетрадиционным задачам, но даже и само ДП в своих традиционных областях применения (динамические задачи ОУ и детерминированные задачи МП) используется не самым эффективным образом и остро нуждается в повышении эффективности.
динамическое программирование, начиная с Р.Беллмана, развивалось многими авторами. Однако попыток записи единого алгоритма ДП в общем виде с целью его применения для различных классов задач в литературе не известно. Пожалуй, наиболее близким приближением к обобщению ДП и созданию единого алгоритма можно считать запись ДП в динамичеоких диокретновременных задачах в операторной форме в работе, например, Д.Бертсекаса, С.Шрива, однако даже там вто делалось, главным образом, для удобства записи и единого обоснования применимости ДП в различных типах указанных динамических задач. Отсутствие единого общего алгоритма решения и оказалось на том, что до сих пор метод ДП применялся лишь в указанных выше задачах и не самым эффективным образом.
Таким образом, разработка теории, позволяющей унифицировать задачи различной природы, и получать для их решения алгоритмы, сходные с алгоритмами ДП (по структуре и по эффективности), разработка ее приложений для нетрадиционных задач, а также повышение
(фектавнооти самого ДП является очень актуальной проблемой. Цель работы ооотоит в!
разработке теории обобщенного динамического программирова-ія (теории ОДП) - развернутого математического аппарата, позво-шцего получать о единых позиций эффективные методы решения для ірокого крута разнородных задач, позволявшего переносить методы эвышения вффективнооти с одних классов задач на другие, а также ащего единое описание рассматриваемых задач.
приложении теории ОДП к ряду классов задач, возникающих ри разработке и реализации систем управления и навигации ЛА (как ^посредственно, так и в виде подзадач), для получения вффектив-а методов решения втих задач.
Методика исследований. При построении аппарата теории ОДП шользуютея в качестве основы для обобщений соотношения метода I в диокретновременных задачах синтеза ОУ. При разработке прило-ший теории ОДП используются ее аппарат я методы повышения эф-эктивности. При решении задачи управления стационарным ИСЗ ис-эльзуется полученная в диссертации методика сокращения вычисле-Ш в методе ДП.
Научная новизна. Новыми научными результатами в диссертации зляются:
Идея и аппарат теории обобщенного динамического программи-звания (ОДП), включающий в себя оригинальную унификацию операто-эв на основе введенного понятия оператора-свертки по переменной, циный (стандартный) вид объектов теории ОДП - задач с рекуррент-su применением операторов (задач о РПО), рекуррентные еоотноше-ія для вводимой функции промежуточного результата (ФПР), цеха-їзм рекуррентной агрегации аргументов ФПР (в фотэме обобщенного азового вектора - ОФВ), подход к нахождению подходящего ОФВ, энцепции разбиения и объединения операторов и, наконец, единый пгоритм решения рассматриваемых задач (метод ОДП).
Система общих подходоа, методов, способов, касающихся заїси задач в стандартном виде, наиболее вффективного применения эории ОДП, оптимизации ее алгоритмов и т.д.
Методика радикального (до нескольких порядков) сокращения Зъема вычислений при использовании метода динамического програмування в динамических задачах синтеза оптимального управления ЭУ) - детерминированных, стохастических, минимаксных и т.д. денки эффективности методики.
Метод сведения решения обратных вероятностных задач к ре-
июнию прямых вероятностны?, задач.
Метод замораживания переменных в методике сокращения вычислений, существенно расширяющий область применения последней.
Алгоритмы (метода) решения широкого крута задач математического программирования - детерминированных (в оамом общей виде), минимаксных, стохастических, минимаксно-стохастических и минимаксных стохастических (в том числе, со сложными ограничениями). Методы повышения вф&ективноети предлагаемых алгоритмов.
Выражения для градиентов функций вероятности и квантили -для вероятностных задач МП.
Решение минимаксной задачи программного управления.
Алгоритм (метод) вычисления определенных интегралов высокой кратности (до 20 и выше), имеющий для широких классов интегралов трудоемкость, возрастающую о ростом размерности примерно линейно. Модификации базового алгоритма для интегралов вероятности и других частных случаев. Методы повышения еффективности предлагаемых, алгоритмов, в частности, метод замораживания переменных.
Решение задачи анализа качества системы управления ЛА (критерий - вероятностный).
Высокоточные алгоритмы (методы) вычисления определителей и обращения матриц. Методы повышения их еффективности и расширения применимости.
Метод поиска стационарных точек функций многих переиенных и точек с заданным значением градиента.
Метод решения систем алгебраических уравнений и неравенств с дискретнозначными переменными.
Решение задачи оптимизации коррекции стационарного ИСЗ с ВДУ малой тяги по прямому вероятностному критерию.
Практическая значимость. Предлагаемая теория ОДП и ее приложения непосредственно касаются математического обеспечения построения и реализации систем управления и навигации движущихся объектов и прежде всего - ЛА. Эти приложения направлены на решение как непосредственно задач управления и навигации (динамических задач позиционного и программного 0У, одношаговых задач 0У - задач МП), так и из подзадач: опять-таки задач МП, вычисления многомерных интегралов, в частности, интегралов вероятности в задачах анализа качества систем управления и в вероятностных задачах ОУ, вычисления определителей и обращения матриц в фильтрации, управлении и т.д., решения систем алгебраических уравнений и неравенств при поиске допустимого управления и при дезагрегации и
.д. Поэтому результати, полученные в диссертации, могут Сыть ис-ользованы при разработке и реализации систем управления и нави-ации JL4, а также во многих других задачах.
Работа является составной частью научно-исследовательской аботы, проводимой на кафедре "Системный анализ и управление'.' МАИ.
Апробация работы. Основные результаты диссертации были доле— ены автором на международной школе-семинаре по методам оптимиза-ии и их приложениям (Иркутск, 1989), на V Всесоюзной Четаевокой энференции (пленарный доклад, Казань, 1987), на XVI Гагаринских гениях (Ыоеквс, 1986), на П Всесоюзной школе-семинаре молодых эеннх и специалистов "Динамика, управление полетом и иеследова-ге операций летательных аппаратов" (Клин, 1987), на Всесоюзной энференции "Моделирование систем информатики" (Новосибирск, Э88), на Всесоюзной школе-семинаре "Динамика ползта, управление исследование операций" (Клин, 1990), а такке на конференциях элодых ученых МАИ и на различных семинарах.
Диссертация в целом апробирована на семинарах кафедры прик-»дной механики МГУ, кафедры прикладной математики МТТУ и кафедры Системный анализ и управление" МАИ.
Личный вклад и публикации. Все результаты диссертации полу-кны лично автором, основные из них опубликованы в 18 печатных іботах.
Структура и объем диссертации. Диссертация состоит из введе-гя, двух частей, содержащих девять глав, выводов, приложения и шока литературы из 141 наименования. Общий объем работы - 242 границы, в том числе 1 рисунок и 6 таблиц.