Уравнение беллмана простым языком

Содержание

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

Принцип оптимальности. Уравнение Беллмана

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

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

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

, (1)

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

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

Если начальное состояние задано , то непосредственно

определяют максимум целевой функции

. (2)

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

В рассмотренных рекуррентных соотношениях предписывают начинать вычисления с последнего этапа и затем передвигаться назад до этапа 1. Такой метод вычислений известен как алгоритм обратной прогонки. Если расчеты осуществляются в естественном порядке следования этапов, то такой метод вычислений известен как алгоритм прямой прогонки.

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

;

В результате решения этих уравнений получим последовательности

; .

Видео:Принцип оптимальности Беллмана Скачать

Далее определим безусловное оптимальное управление по цепочке

Источник

Уравнение Беллмана

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

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

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

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

Это заготовка статьи о программировании. Вы можете помочь проекту, дополнив её.

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

Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License.

Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. wiki2.info является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).

Источник

Динамическое программирование, принцип Беллмана, схема метода.

ДП – математический метод оптимизации многошаговых процессов принятия решений.

Видео:Динамическое программирование Скачать

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

Решение – не точечная акция (во времени и пространстве), а последовательность шагов (этапов), на каждом из которых принимается некоторое решение, определяющее изменение состояния системы на каждом шаге.

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

· оптимизация маршрутов на сетях;

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

Имеется система S, которая переходит из начального состояния S₀ в конечное состояние S_m под воздействием вектора управлений U. В развернутом виде это выглядит:

Где – вектор управлений.

Все эти переходы можно представиться как траекторию в фазовом пространстве:

(Рисунок рассмотрен для случая, когда состояния системы описываются двумерным вектором).

Управление тоже может описываться вектором.

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

Также кроме аддитивного критерия может применяться мультипликативный, где .

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

Видео:Семинар 10. Ужегов. Принцип Беллмана Скачать

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

Рассмотрим последовательность переходов состояний в виде следующей схемы:

Доход на i – м шаге: . – наилучшая эффективность при движении из S_i в S_m– называется Условно Оптимальным Выигрышем (УОВ). УОВ зависит только от состояния, это непосредственно вытекает из формулы для УОВ. Управление, при котором достигается УОВ называется Условно Оптимальным Управлением (УОУ) и обозначается .

Назовем конструкцию – полуоптимальным выигрышем (ПОВ). В таком случае УОВ на i-м шаге будет иметь вид (Уравнение Беллмана):

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

Реализация вышеописанных идей предполагает 2 этапа:

1. Обратная прогонка.

m-й шаг:

, где – множество возможных «предпоследних» состояний. — УОУ.

m-1-й шаг:

, где . – УОУ. УОВ – полученна предыдущем шаге.

i-йшаг:

, где . – УОУ.

1-йшаг:

, где . – УОУ.

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

35. Динамическое программирование. Задача распределения капиталовложений (ресурсов).

Для решения задачи данной задачи необходимо:

· решить, что есть управление;

· сформировать оценки управлений.

В качестве шагов будем рассматривать вклад ресурса в конкретное предприятие. Состояние будет описываться количеством оставшегося ресурса к концу шага . Величина вклада будет выступать управлением, оценка управления – выигрыш от вложения средств в предприятие. Функция перехода состояний количество ресурса в начала шага вычесть вкладываемый ресурс: . Будем считать, что монотонно возрастают, тогда очевидно, что максимальный выигрыш будет достигнут только при распределении имеющегося ресурса без остатка. Нарисуем схему переходов состояний с отображением управлений и выигрышей:

с учетом требования к трате всего ресурса на последнем шаге получаем:

Видео:Лекция 1 | Введение в теорию функции Беллмана | Василий Васюнин | Лекториум Скачать

Источник

Принцип оптимальности и уравнения Беллмана

Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):

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

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

Рассмотрим общую задачу динамического программирования, приведенную выше. На каждом шаге кроме последнего для любого состояния системы s_k_-1 управленческое решение X_k необходимо выбирать «с оглядкой», так как этот выбор влияет на последующее состояние системы s_k.

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

Рассмотрим последний n-й шаг:

s_n_-1 – состояние системы к началу n-го шага;

s_n – конечное состояние системы;

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

называют условным максимумом целевой функции на n-ом шаге, и определяют по следующей формуле:

. (11.5)

Видео:СПбГУ -- 2022.04.15 -- Марковские процессы принятия решений: уравнения Беллмана Скачать

Максимизация ведется по всем допустимым управлениям X_n.

Решение X_n, при котором достигается , также зависит от s_n_-1 и называется условным оптимальным решением на n-ом шаге. Обозначим его через .

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

Рассмотрим двухшаговую задачу: присоединим к n-му шагу (n–1)-й.

Для любых состояний s_n_-2, произвольных управленческих решений X_n_-1 и оптимальном управлении на n-ом шаге значение целевой функции на двух последних шагах вычисляется по формуле:

. (11.6)

Согласно принципу оптимальности Беллмана для любых s_n_-2 решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (n-ом) шаге приводило бы к оптимуму целевой функции на двух последних шагах. Следовательно, необходимо отыскать оптимум выражения (11.6) по всем допустимым управленческим решениям X_n_-1:

. (11.6)

– называют условным максимумом целевой функции при оптимальном управлении на двух последних шагах. Необходимо отметить, что выражение в фигурных скобках в формуле (11.6), зависит только от s_n_-2 и X_n_-1, так как s_n_-1 можно найти из уравнения состояний (11.1) при :

. (11.7)

Соответствующее управление X_n_-1 на (n–1)-ом шаге обозначается через и называют условным оптимальным управлением на (n–1)-ом.

Аналогично определяются условные оптимумы целевой функции при оптимальном управлении на (n–k+1) шагах, начиная с k-го до конца, при условии, что к началу k-го шага система находилась в состоянии s_k_-1:

. (11.8)

Управление X_k на k-ом шаге, при котором достигается максимум по (11.8), обозначается и называется условным оптимальным управлением на k-ом шаге.

Уравнения (11.5) и (11.8) называют рекуррентными уравнения Беллмана (обратная схема). Процесс решения данных уравнений называют условной оптимизацией.

В результате условной оптимизации получаются две последовательности:

, , …, , – условные максимумы целевой функции на последнем, двух последних, …, на n шагах;

, , …, , – условные оптимальные управления на n-ом, (n–1)-ом, …, на 1-ом шагах.

Используя данные последовательности, можно найти решение задачи динамического программирования при данных n и s₀:

В результате получаем оптимальное решение задачи динамического программирования: .

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

, (11.9)

. (11.10)

Оптимальное решение задачи в данном случае находится по следующей схеме:

Видео:Уравнение Беллмана в задаче управления инвестициями в модели с трансакционными издержками Скачать

Таким образом, построение модели динамического программирования и решение задачи на ее основе в общем виде можно представить в виде следующих этапов:

1. Выбирают способ деления процесса управления на шаги.

2. Определяют параметры состояния s_k и переменные управления X_k на каждом шаге, записывают уравнения состояний.

3. Вводят целевые функции k-ого шага и суммарную целевую функцию, а также условные оптимумы и условное оптимальное управление на k-ом шаге ( ).

4. Записывают в соответствии с обратной или прямой схемой рекуррентные уравнения Беллмана и после выполнения условной оптимизации получают две последовательности: < > и < >.

5. Определяют оптимальное значение целевой функции и оптимальное решение .