Презентация на тему по теме Динамическое программирование

решения многошаговых задач оптимального управления

управлений ищется то, которое доставляет экстремальное (наименьшее или наибольшее)

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

X состоит из t шагов (этапов); на i-м шаге

управление yi переводит систему из состояния xi-1, достигнутого в результате (i-1)-го шага, в новое состояние ж,-. Этот процесс перехода осуществляет заданная функция fi(x, у), и новое состояние определяется значениями xi-1, yi :

состояния в конечное -  где  x0 и Хт- совокупности допустимых начальных и конечных состояний

системы X. Опишем одну из возможных постановок экстремальной задачи. Начальное состояние х 0 задано. Требуется выбрать управления у 1, у 2, ..., у т таким образом, чтобы система X перешла в допустимое конечное состояние и при этом заданная целевая функция F(x0, у1,x1, у 2, ... , у т, х т )достигла максимального значения F*, т. е.

он применим лишь для аддитивной целевой функции.. В рассмотренном

примере это означает, что


Кроме того, в методе динамического программирования требуется, чтобы задача характеризовалась отсутствием "последействия": решения (управления), принимаемые на шаге, оказывают влияние только на состояние х i системы в момент i. Другими словами, процессы, описываемые функциями вида xi=fi (xi-1, yi, xi-2, yi-1,..., y1, xo) не рассматриваются. Оба упомянутых ограничительных условия можно ослабить, но только за счет существенного усложнения метода.

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

вычислений. В основе метода динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом (R. Bellman): предположим, что осуществляя управление дискретной системой X, мы уже выбрали некоторые управления дискретной системой у 1, у 2, ... , уk тем самым траекторию состояний х 0, х 1, . . . , xk, и хотим завершить процесс, т. е. выбрать yk+1, yk+2,... , у т (а значит и xk+1,xk+ 2, ...,xm);тогда, если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции



То и весь процесс не будет оптимальным

Определим последовательность функций переменной х:

,
где k=1, 2,…, m
Здесь максимум берется по всем управлениям, допустимым на шаге к. Соотношение, определяющее зависимость wk-1 от wk, принято называть Беллмана уравнением. 

оказалась в состоянии х, то wk-1(x) есть максимально возможное значение функции F. Одновременно

с построением функций wk-1 (х). находятся условные оптимальные управления yk (х)на каждом шаге (т. е. значения оптимального управления при всевозможных предположениях о состоянии х системы на шаге k-1). Окончательно оптимальные управления находятся последовательным вычислением величин