Пупков К.В. Методы классической и современной теории автоматического управления. Том 2 (2000) (1095389), страница 102
Текст из файла (страница 102)
Динамическое программирование хорошо обосновано для дискретных процессов. Обоснованное применение динамического программирования для непрерывных процессов не всегда возможно. Это связано с тем, что при выводе функционального уравнения Беллмана приходится делать предположение, непосредственная проверка которого по уравнениям движения и функционалу невозможна. И только после решения уравнения Беллмана можно проверить, выполняется ли сделанное предположение или нет. Далее, функциональное уравнение Беллмана для непрерывных процессов представляет собой дифференциальное уравнение в частных производных. Это уравнение обычно имеет весьма сложный вид, и численное его решение часто весьма затруднительно.
Если иметь в виду не только задачи оптимального управления, то необходимо отметить, что динамическое программирование обладает большой универсальностью. Его можно использовать для решения широкого класса задач оптимизации. В настоящей главе излагается основное содержание динамического программирования как метода оптимизации. Рассматриваются как дискретные многошаговые процессы принятия решений, так и непрерывные процессы. Приводится ряд примеров по решению задач оптимизации методом динамического программирования, в том числе его применение к задаче об аналитическом конструировании регуляторов.
4.1. ДИСКРЕТНЫЙ ейНОГОШАГОВЫЙ ПРОЦЕСС ПРИНЯТИЯ РЕШЕНИЙ Пусть состояние системы задается вектором р = ( рп рз,..., р„) . Обозначим р = (р,, рз,..., р„) начальное состояние системы, р — состояние системы на единицу времени позже и т.д. Последовательность р,р,р,...,р, где рьм =Т(р,ц ), й =0,!,...,Ф (4.!) задает изменение состояния системы в дискретные моменты времени. В равенстве (4.1) Т=(Т,,Ты...,Т„) — и-мерный вектор, и =(и,,из,...,и ) т-мерный вектор. На изменения состояния системы можно влиять, выбирая на каждом шаге вектор и из некоторого заданного множества 1). Вектор ц называется вектором решения, вектором упровеения или просто решением. В силу особенностей динамического программирования начальное состояние системы удобно обозначать вектором р.
Последовательность (4.2) 34 Зак. 366 538 Методы тео ии оптимального п авления. Часть РП где р '~ =Т(р,и ), к =0,1,...,Ф называют многошаговым процессом принятия решений. Если )Ц вЂ” конечное число, то такой процесс называют конечношаговым, если число элементов в последовательности (4.2) не ограничено, то — бесконечношаговым. Будем качество многошагового процесса оценивать функцией й( 1 з ри„о„~ „и) Для дискретного многошагового процесса функция (4.3) является функционалом, поэтому именно так она и называется в дальнейшем.
За оптимальное будем принимать максимальное значение функционала (4.3). Равенство (4.!) представляет собой систему разностных уравнений. Строго говоря, введенное здесь понятие многошагового процесса сводится именно к системе разностных уравнений. Однако в динамическом программировании рассматриваются многошаговые процессы, которые невозможно задавать системой разностных уравнений. Пример такого многошагового процесса будет рассмотрен ниже. Отметим одно свойство многошагового процесса, которое в дальнейшем играет важную роль. Это свойство можно сформулировать так: для миогошагового процесса будущее в полной мере определяется настоящим.
Если настоящее состояние системы характеризуется вектором р, то для будущего состояния р" неважно, каким образом система попала в состояние р . Оно полностью определяется многошаговым процессом, который начинается из состояния р . Введем важное понятие стратегии. Будем на каждом шаге вектор управления и задавать в виде функции вектора состояния р; и =и (р).
(4.4) Функция (4.4) задает правило, по которому на каждом шаге выбирается веюпор решения и называется функцией стратегии, или просто стратегией. Стратегия, которая максимизирует функционал (4.3), называется оптимальной. Возможность задания оптимального управления в виде оптимальной стратегии непосредственно следует из отмеченного выше свойства многошаговых процессов. Сформулированный многошаговый процесс принятия решений не задает никаких условий на конечное значение вектора состояния, т.е. речь идет о многошаговых процессах со свободным правым концом. Именно такие процессы рассматриваются ниже.
Однако можно рассматривать многошаговые процессы, у которых конечное значение вектора состояния фиксировано либо на его значение заданы какие-либо условия. 4.2. ПРИНЦИП ОПТИМАЛЬНОСТИ. ОСНОВНОЕ ФУНКЦИОНАЛЬНОЕ УРАВНЕНИЕ БЕЛЛМАНА В основу динамического программирования положен достаточно очевидный принцип оптимальности Беллмана. Его можно сформулировать следующим образом.
Оптииальная стратегия обладает тем свойством, что независимо от того, каким было первоначальное состояние и первоначальное решение, последующие решение должны быть оптимальными относительно состояния, которое возникло после принятия первого решения, Поясним принцип оптимальности. Пусть н,н,...,п — оптимальная последовав ~ и тельность решений для )ц-шагового процесса, который начинается из состояния р. Глава 4. инамическое п о амми ование 539 Тогда, очевидно, н|,нз,...,пн является оптимальной последовательностью решений для зз'-1-шагового процесса, который начинается из состояния р . Рассмотрим многошаговый процесс принятия решений (4.2). Будем качество этого процесса оценивать функционалом й(рк,н ), здесь и — скалярная функция векторного аргумента.
Функционал (4,5) для дискретных многошаговых процессов играет ту же роль, что и функционал вида т .У = ) й ( р, н ) аг о (4.7) для непрерывных процессов. Максимальное значение функционала (4.5) однозначно определяется начальным значением вектора состояния р и числом шагов У. Обозначим максимальное значение функционала 7н(р).Функцию Дн (р) будем считать определенной для любого значения вектора состояния р и любого числа шагов )ч'. Воспользуемся принципом оптимальности Беллмана. Пусть на первом шаге выбрано некоторое решение не, а в последующем в соответствии с принципом оптимальности принимаются оптимальные решения.
Тогда функционал ,7 =п(р,н )+7з(р',н')+...ь)з(р,п")= (4.6) =п(р,н~)+Дн,(р )=п(р,и )+Дн,(Т(р,п )) Для того чтобы оптимизировать У-шаговый процесс, необходимо, очевидно, вектор нь выбрать таким образом, чтобы он максимизировал правую часть равенства (4.б). В результате получим соотношение Ь(р) = ~й(р,п')+Хн,(Т(р,"))~, ~Ч>1. К равенству (4.7) следует добавить уравнение А(р) = шах[А(р,ц')~. (4.8) н еп Функция Д~ (р) задает максимальное значение функционала (4.5), когда ои содержит только одно слагаемое.
Равенство (4.7) связывает между собой максимавьное значение функционала для 77-шагового процесса с максимальным значением функционала для (7з'-1)-шагового процесса и называется основным функциональным уравнением Беллмана. Равенство (4.7) задает рекуррентное соотношение, которое решается последовательно. Из уравнения (4.8) определяется функция А (р) и подставляется в правую часть равенства (4.7), положив )ч' = 1.
Максимизировав правую часть равенства (4.7), получим функцию /~(р). Затем по функции Я,(р) определяется функция /~(р) и т.д. При этом наряду с последовательностью функций Д (р),Я,(р),7з(р),..., которые задают максимальное значение функционала, получим последовательность функций и (р),п~(р),ц~(р), задающих оптимальную стратегию. Последовательность и (р),п (р),... состоит из функций, которые максимизируют правую часть уравнения (4.7)(при зч' = 0 — правую часть уравнения (4.8)). 34' 540 Методы тео ии оптимального п авления. Часть! П г =8(Р ) Принцип оптимальности Беллмана в этом случае приводит к функциональному урав- нению 7"н (Р) м шах )~, (Т(Р,ц )), 1>г >1; А(Р) =8(Р) Для вариацнонного исчисления весьма сложными являются функционалы вида .У = шах 8(р,н ).
(4.9) овеян Обозначим 7н(р) максимальное значение функционала (4.9). Применяя принцип оптимальности Беллмана, получим функциональное уравнение Г, 1р) - [ г (р,,'); Г„ , (г(р, ' ))] . Если рассматривается бесконечношаговый процесс, то функционал (4.5) принимает вид )г(ре,на). а=о (4.10) Будем предполагать, что ряд (4.10) сходится при любых значениях векторов и е У . а Максимальное значение функционала (4.10) в этом случае однозначно определяется начальным значением вектора р. Принцип оптимальности Беллмана приводит к функциональному уравнению г (р) — шах[)г(р цо)+Т(Т(р ио))] Пример 4.1.
Задача а замене оборудования. Пусть имеется некоторый комплект оборудования, который характеризуется пок>иной ценой р и функцией ежегодного дохода п(г). Функция л(г) задаст доход ат работы оборудования в течение одного года ат момента г до момента г~1, здесь г — возраст оборудования в годах г = О, 1, 2, Будем, далее, предполагать, чта оборудование являеюя специальным и не имеет продажной цены. Требуется определись опгимаяьную политику замены оборудования, которая дает максимальный доход для 1-лстнего производственного процесса. Обозначим /г(г) максимальный доход, который можно получить от Блетнсго производственного процесса, если к началу згого процесса имеется оборудование, возраст которого г лег (г = О, 1, 2, ).
В на- Запишем уравнения (4.7) и (4.8), используя скалярные функции и скалярные переменные: Зн(Р1 Рз* — Рн) =шах]п(Р1 Рг - Р и1 ° из -*" )+ о о о1 н егз +Зн 1(Т(Р„...,Р,и,,...,и ),Тг(РП...,Р„,и,,...,и ),... ..., Т„(р>, ..., р„, и1,..., и ))~, З>1 > 1; о о от )а(Р1 Рт" Рн) =шах "(Р1 Рг -*Р"иг "»- "и) е егг Отметим одну важную особенность метода динамического программирования. Данным методам оптимальные решения определяются в виде функции стратегии. Если использовать терминологию главы 2, то можно сказать, что метод позволяет определять оптимальное управление только в виде синтезирующей функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
