Принцип оптимальности беллмана кратко
Обновлено: 30.06.2024
Принцип оптимальности Беллмана позволяет решать или осмыслить многие интересные задачи, возникающие в реальной жизни, например, задачу о рациональной эксплуатации генерирующего предприятия (ТЭЦ, ГЭС), выбора экономичного состава агрегатов и др.
При эксплуатации гидростанций и тепловых станций возникает необходимость периодической остановки агрегатов при снижении нагрузки и включения агрегатов, находящихся в резерве, когда нагрузка увеличивается. Включение в работу определенных агрегатов влияет на величину и размещение резервов системы, на режим электрической сети, на перетоки по межсистемным линиям электропередачи, на расход топлива и тд.
Если на станциях имеется n агрегатов и каждый из них может быть либо включен, либо отключен, то все множество всех вариантов для работы с любой мощностью составит 2 в степени n.
Даже для n = 50 число вариантов становится очень большим!
В общем виде такие задачи являются нелинейными, целочисленными, многоэкстремальными, на состав агрегатов влияет режим электрических сетей, который следует оценивать и прогнозировать статистическими методами. Для решения таких задач обычный математический аппарат не подходит.
В частном случае методы динамического программирования позволяют решать подобные задачи при числе агрегатов порядка 20-30.
Приведем примеры задач, в которых принцип динамического программирования эффективно работает и позволяет найти оптимальное решение.
Задача о графике эксплуатации электростанция. Станция имеет L агрегатов, известна производительность одного агрегата и цена единицы произведенной электроэнергии.
Задан график оплаченной электроэнергии, избыточно произведенная электроэнергия не оплачивается.
Известны затраты на поддержание в рабочем агрегатов, затраты на консервацию и затраты на пуск. Требуется определить оптимальный режим эксплуатации.
Интересны задачи о распределении инвестиций и ресурсов.
Задача о распределении инвестиций: имеется несколько предприятий, между которыми требуется распределить данную сумму инвестиций. Известна эффективность вложения данной суммы средств в каждое предприятие.
Задача о распределении ресурса: имеется N предприятий, каждое из которых приносит доход, зависящий от доли выделенного ресурса. Требуется наилучшим способом распределить между ними ограниченный ресурс a на доли x1, . , xN (x1 ≥ 0, . , xN ≥ 0, x1 +. + xN ≤ a).
Задача о наилучшей загрузке транспорта: транспорт, имеющее грузоподъемность a , загружается грузами N типов. Каждый тип груза имеет стоимость yi и вес zi .
Требуется найти оптимальный вариант загрузки, при котором стоимость взятых на борт предметов максимальна.
Задача о замене автомобиля: автотранспортное предприятие планирует приобрести автомобиль и эксплуатировать его в течение N лет.
Можно либо купить новый автомобиль возраста x0 = 0 лет и стоимости p, либо бывший в эксплуатации возраста x0 > 0 лет по стоимости, зависящей от времени эксплуатации.
Показатели эксплуатации автомобиля включают: f (t) – стоимость произведенных за год изделий на оборудовании возраста t лет; r(t) – затраты на эксплуатацию в течение года автомобиля возраста t.
В процессе эксплуатации автомобиль можно продавать по ликвидной стоимости и купить новый. В конце срока эксплуатации автомобиль также продается по ликвидной стоимости. Определить оптимальный возраст автомобиля при покупке и оптимальный график его замены.
Все эти и многие другие задачи могут быть решены с помощью принципа оптимальности Беллмана.
Опишем формально принцип Беллмана и объясним его смысл.
Ключевым является понятие управляемого объекта, к которому применяется принцип Беллмана.
Пусть имеется изменяющийся во времени объект, на который осуществляется внешнее воздействие u(t) или управление, а x(t) – описание этого объекта в момент времени t.
Если при известном управлении до момента t1, зная описание x(t) в момент времени t , можно однозначно определить его значение x(t) для любого t > t1 , то такое описание называют полным.
Полное описание называют состоянием, множество возможных состояний – пространством состояний.
Сам объект, допускающий возможность полного описания, называют динамической системой.
Будем рассматривать только дискретные моменты времени и в эти моменты управлять системой.
Каждому переходу из состояния xk в следующее состояние ставится в соответствие функция затрат, зависящая от состояния xk , момента времени и применяемого управления.
Требуется найти такое начальное состояние и такой допустимый набор управлений, переводящий систему в одно из конечных состояний, чтобы общие затраты, являющиеся аддитивной функцией затрат на отдельных шагах, были минимальны.
Итак, на каждом шаге мы вносим плату за выбранное управление, далее плата, внесенная на каждом шаге, суммируется и подводится итог.
Мы желаем таким образом управлять объектом, чтобы общая сумма затрат была минимальной.
Это и есть общая постановка задачи динамического программирования или управления динамической системой.
Иными словами, нам нужна программа действий на каждом шаге, позволяющий минимизировать затраты.
Общий принцип формулируется так: вне зависимости от того, каким образом управляемый процесс на шаге k попал в состояние xk , далее надо применять управление, оптимальное для этого состояния в завершающем (N − k)-шаговом процессе с учетом оптимального продолжения.
Это одна из возможных формулировок принципа Беллмана в форме достаточного условия.
Пусть Yk – множество состояний, из которых (при использовании допустимых управлений) можно ровно за k шагов попасть в одно из состояний финального множества X N.
Можно считать, что Y0 = X N.
Возьмем произвольное xN −k ∈Yk и обозначим через Sk (xN −k ) функцию, описывающую зависимость оптимальных затрат от состояния xN −k за k последних шагов, переводящих систему из xN −k в X N.
Такие функции называют функциями Беллмана.
Поскольку для состояний xN −1 из множества Y1 переход в XN происходит за один шаг, то функция оптимальных затрат S1(xN −1) может быть записана следующим образом:
Второе ограничение необходимо для того, чтобы гарантировать достижение заданного финального множества X N.
Значение uN , при котором достигается минимум в этом соотношении, обозначим через u*N( xN-1).
Несложно понять (сделайте это!), что функция оптимальных затрат Sk +1(xN −k −1) каждой следующей задачи рекуррентно выражается через предыдущую Sk (xN −k )
u*N −k (xN −k – 1) – управление, при котором достигается минимум затрат в (2).
Выражение u*k (xk-1) − определяет для каждого момента времени оптимальные правила управления в виде функций от текущего состояния динамического процесса, задают закон оптимального управления в форме оптимального регулятора по состоянию.
Оптимальное начальное состояние x*0 можно получить из решения следующей задачи:
Систему (1)-(3) называют рекуррентными уравнениями Беллмана.
Значения оптимального управления в явном виде можно последовательно определить следующим образом:
Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом нумерация шагов, как правило, осуществляется от конца к началу.
Основным принципом, на котором базируются оптимизация многошагового процесса, а также особенности вычислительного метода, динамического программирования, является принцип оптимальности Р. Беллмана.
Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения.
Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения. Математически он записывается выражением вида:
(1.3)
где — оптимальное значение эффекта, достигаемого за шагов; n — количество шагов (этапов); — состояние системы на - м шаге; — решение (управление), выбранное на - м шаге; — непосредственный эффект, достигаемый на - м шаге.
"Optimum" в выражении (1.3) означает максимум или минимум в зависимости от условия задачи. Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за n шагов, ¦n(So), проводятся по формуле (1.3), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения. Действительно, при вычислении очередного значения функции используются значение функции , полученное на предыдущем шаге, и непосредственное значение эффекта , достигаемого в результате выбора решения при заданном состоянии системы . Процесс вычисления значений функции осуществляется при естественном начальном условии , которое означает, что за пределами конечного состояния системы эффект равен нулю.[1, с 243]
1.2 Вычислительная схема
Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения (1.3). Чтобы определить его, необходимо:
1) Записать функциональное уравнение для последнего состояния процесса (ему соответствует ):
; (1.4)
2) Найти из дискретного набора его значений при некоторых фиксированных и из соответствующих допустимых областей ( так как , то ). В результате после первого шага известно решение и соответствующее значение функции ;
3) Уменьшить значение на единицу и записать соответствующее функциональное уравнение. При оно имеет вид:
; (1.5)
4) Найти условно-оптимальное решение на основе выражения (1.5);
5) Проверить, чему равно значение . Если расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если перейти к выполнению п. 3;
6) Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.[1, с 244]
2. Решение задачи оптимального распределения средств на расширение производства 2.1 Решение задачи оптимального распределения средств на расширение производства ручным способом
Широкий класс составляют задачи, в которых речь идет о наиболее целесообразном распределении во времени тех или иных ресурсов (денежных средств, рабочей силы, сырья и т.п.). Рассмотрим пример задачи такого рода.
Производственному объединению из четырех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы xi, приведены в табл. 2.1. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным.[1, с 261]
Принцип оптимальности Беллмана позволяет решать или осмыслить многие интересные задачи, возникающие в реальной жизни, например, задачу о рациональной эксплуатации генерирующего предприятия (ТЭЦ, ГЭС), выбора экономичного состава агрегатов и др.
При эксплуатации гидростанций и тепловых станций возникает необходимость периодической остановки агрегатов при снижении нагрузки и включения агрегатов, находящихся в резерве, когда нагрузка увеличивается. Включение в работу определенных агрегатов влияет на величину и размещение резервов системы, на режим электрической сети, на перетоки по межсистемным линиям электропередачи, на расход топлива и тд.
Если на станциях имеется n агрегатов и каждый из них может быть либо включен, либо отключен, то все множество всех вариантов для работы с любой мощностью составит 2 в степени n.
Даже для n = 50 число вариантов становится очень большим!
В общем виде такие задачи являются нелинейными, целочисленными, многоэкстремальными, на состав агрегатов влияет режим электрических сетей, который следует оценивать и прогнозировать статистическими методами. Для решения таких задач обычный математический аппарат не подходит.
В частном случае методы динамического программирования позволяют решать подобные задачи при числе агрегатов порядка 20-30.
Приведем примеры задач, в которых принцип динамического программирования эффективно работает и позволяет найти оптимальное решение.
Задача о графике эксплуатации электростанция. Станция имеет L агрегатов, известна производительность одного агрегата и цена единицы произведенной электроэнергии.
Задан график оплаченной электроэнергии, избыточно произведенная электроэнергия не оплачивается.
Известны затраты на поддержание в рабочем агрегатов, затраты на консервацию и затраты на пуск. Требуется определить оптимальный режим эксплуатации.
Интересны задачи о распределении инвестиций и ресурсов.
Задача о распределении инвестиций: имеется несколько предприятий, между которыми требуется распределить данную сумму инвестиций. Известна эффективность вложения данной суммы средств в каждое предприятие.
Задача о распределении ресурса: имеется N предприятий, каждое из которых приносит доход, зависящий от доли выделенного ресурса. Требуется наилучшим способом распределить между ними ограниченный ресурс a на доли x1, . , xN (x1 ≥ 0, . , xN ≥ 0, x1 +. + xN ≤ a).
Задача о наилучшей загрузке транспорта: транспорт, имеющее грузоподъемность a , загружается грузами N типов. Каждый тип груза имеет стоимость yi и вес zi .
Требуется найти оптимальный вариант загрузки, при котором стоимость взятых на борт предметов максимальна.
Задача о замене автомобиля: автотранспортное предприятие планирует приобрести автомобиль и эксплуатировать его в течение N лет.
Можно либо купить новый автомобиль возраста x0 = 0 лет и стоимости p, либо бывший в эксплуатации возраста x0 > 0 лет по стоимости, зависящей от времени эксплуатации.
Показатели эксплуатации автомобиля включают: f (t) – стоимость произведенных за год изделий на оборудовании возраста t лет; r(t) – затраты на эксплуатацию в течение года автомобиля возраста t.
В процессе эксплуатации автомобиль можно продавать по ликвидной стоимости и купить новый. В конце срока эксплуатации автомобиль также продается по ликвидной стоимости. Определить оптимальный возраст автомобиля при покупке и оптимальный график его замены.
Все эти и многие другие задачи могут быть решены с помощью принципа оптимальности Беллмана.
Опишем формально принцип Беллмана и объясним его смысл.
Ключевым является понятие управляемого объекта, к которому применяется принцип Беллмана.
Пусть имеется изменяющийся во времени объект, на который осуществляется внешнее воздействие u(t) или управление, а x(t) – описание этого объекта в момент времени t.
Если при известном управлении до момента t1, зная описание x(t) в момент времени t , можно однозначно определить его значение x(t) для любого t > t1 , то такое описание называют полным.
Полное описание называют состоянием, множество возможных состояний – пространством состояний.
Сам объект, допускающий возможность полного описания, называют динамической системой.
Будем рассматривать только дискретные моменты времени и в эти моменты управлять системой.
Каждому переходу из состояния xk в следующее состояние ставится в соответствие функция затрат, зависящая от состояния xk , момента времени и применяемого управления.
Требуется найти такое начальное состояние и такой допустимый набор управлений, переводящий систему в одно из конечных состояний, чтобы общие затраты, являющиеся аддитивной функцией затрат на отдельных шагах, были минимальны.
Итак, на каждом шаге мы вносим плату за выбранное управление, далее плата, внесенная на каждом шаге, суммируется и подводится итог.
Мы желаем таким образом управлять объектом, чтобы общая сумма затрат была минимальной.
Это и есть общая постановка задачи динамического программирования или управления динамической системой.
Иными словами, нам нужна программа действий на каждом шаге, позволяющий минимизировать затраты.
Общий принцип формулируется так: вне зависимости от того, каким образом управляемый процесс на шаге k попал в состояние xk , далее надо применять управление, оптимальное для этого состояния в завершающем (N − k)-шаговом процессе с учетом оптимального продолжения.
Это одна из возможных формулировок принципа Беллмана в форме достаточного условия.
Пусть Yk – множество состояний, из которых (при использовании допустимых управлений) можно ровно за k шагов попасть в одно из состояний финального множества X N.
Можно считать, что Y0 = X N.
Возьмем произвольное xN −k ∈Yk и обозначим через Sk (xN −k ) функцию, описывающую зависимость оптимальных затрат от состояния xN −k за k последних шагов, переводящих систему из xN −k в X N.
Такие функции называют функциями Беллмана.
Поскольку для состояний xN −1 из множества Y1 переход в XN происходит за один шаг, то функция оптимальных затрат S1(xN −1) может быть записана следующим образом:
Второе ограничение необходимо для того, чтобы гарантировать достижение заданного финального множества X N.
Значение uN , при котором достигается минимум в этом соотношении, обозначим через u*N( xN-1).
Несложно понять (сделайте это!), что функция оптимальных затрат Sk +1(xN −k −1) каждой следующей задачи рекуррентно выражается через предыдущую Sk (xN −k )
u*N −k (xN −k – 1) – управление, при котором достигается минимум затрат в (2).
Выражение u*k (xk-1) − определяет для каждого момента времени оптимальные правила управления в виде функций от текущего состояния динамического процесса, задают закон оптимального управления в форме оптимального регулятора по состоянию.
Оптимальное начальное состояние x*0 можно получить из решения следующей задачи:
Систему (1)-(3) называют рекуррентными уравнениями Беллмана.
Значения оптимального управления в явном виде можно последовательно определить следующим образом:
Содержание
Чтобы понять уравнение Беллмана, необходимо понять несколько основных концепций. Во-первых, любая задача оптимизации имеет некоторую цель: минимизировать время в пути, минимизировать затраты, максимизировать прибыль, максимизировать полезность и т. Д. Математическая функция, которая описывает эту цель, называется целевой функцией .
Переменные, выбранные в любой момент времени, часто называют управляющими переменными . Например, с учетом своего текущего благосостояния люди могут решить, сколько потреблять сейчас. Выбор управляющих переменных сейчас может быть эквивалентен выбору следующего состояния; в более общем случае на следующее состояние влияют другие факторы в дополнение к текущему элементу управления. Например, в простейшем случае сегодняшнее богатство (состояние) и потребление (контроль) могут точно определять завтрашнее богатство (новое состояние), хотя обычно другие факторы также будут влиять на завтрашнее богатство.
Подход динамического программирования описывает оптимальный план путем нахождения правила, которое сообщает, какими должны быть элементы управления при любом возможном значении состояния. Например, если потребление ( c ) зависит только от богатства ( W ), мы будем искать правило, которое определяет потребление как функцию богатства. Такое правило, определяющее элементы управления как функцию состояний, называется функцией политики (см. Bellman, 1957, Ch. III.2). [8] c ( W )
Наконец, по определению, оптимальное правило принятия решений - это правило, которое позволяет достичь наилучшего возможного значения цели. Например, если кто-то выбирает потребление, учитывая богатство, чтобы максимизировать счастье (предполагая, что счастье H может быть представлено математической функцией, такой как функция полезности, и является чем-то определенным богатством), то каждый уровень богатства будет связан с некоторый наивысший возможный уровень счастья . Наилучшее возможное значение цели, записанное как функция состояния, называется функцией значения . ЧАС ( W )
Пусть состояние на время будет . Для решения, которое начинается в момент времени 0, мы принимаем начальное состояние заданным . В любой момент набор возможных действий зависит от текущего состояния; мы можем записать это как , где действие представляет одну или несколько управляющих переменных. Мы также предполагаем, что состояние изменяется с на новое состояние, когда выполняется действие , и что текущий выигрыш от выполнения действия в состоянии равен . Наконец, мы предполагаем нетерпение, представленное дисконтным фактором . т Икс т > Икс 0 > а т ∈ Γ ( Икс т ) \ in \ Gamma (x_ )> а т > Икс Т ( Икс , а ) а а Икс F ( Икс , а ) 0 β 1
При этих предположениях проблема принятия решений с бесконечным горизонтом принимает следующий вид:
с учетом ограничений
Обратите внимание, что мы определили обозначение для обозначения оптимального значения, которое может быть получено путем максимизации этой целевой функции с учетом предполагаемых ограничений. Эта функция является функцией значения . Это функция переменной начального состояния , поскольку наилучшее достижимое значение зависит от исходной ситуации. V ( Икс 0 ) )> Икс 0 >
Метод динамического программирования разбивает эту проблему решения на более мелкие подзадачи. Принцип оптимальности Беллмана описывает, как это сделать:
Принцип оптимальности: Оптимальная политика обладает тем свойством, что независимо от исходного состояния и первоначального решения, остальные решения должны составлять оптимальную политику в отношении состояния, вытекающего из первого решения. (См. Bellman, 1957, гл. III.3.) [8] [9] [10]
В информатике считается, что проблема, которую можно разбить на части, имеет оптимальную подструктуру . В контексте динамической теории игр этот принцип аналогичен концепции идеального равновесия в подиграх , хотя то, что составляет оптимальную политику в этом случае, зависит от того, что оппоненты лица, принимающего решения, выбирают одинаково оптимальную политику со своей точки зрения.
Согласно принципу оптимальности , мы рассмотрим первое решение отдельно, отложив в сторону все будущие решения (мы начнем заново с момента 1 с новым состоянием ). Собирая будущие решения в скобки справа, указанная выше проблема принятия решений с бесконечным горизонтом эквивалентна: [ требуется пояснение ] Икс 1 >
с учетом ограничений
Здесь мы выбираем , зная, что в результате нашего выбора будет состояние time 1 . Это новое состояние затем повлияет на проблему принятия решения с момента 1. Вся проблема будущего решения отображается в квадратных скобках справа. [ требуется разъяснение ] [ необходимо дополнительное объяснение ] a 0 > x 1 = T ( x 0 , a 0 ) =T(x_,a_)>
Пока что кажется, что мы только усугубили проблему, отделив сегодняшнее решение от будущих. Но мы можем упростить, заметив, что то, что находится внутри квадратных скобок справа, - это значение задачи принятия решения за время 1, начиная с состояния . x 1 = T ( x 0 , a 0 ) =T(x_,a_)>
Следовательно, мы можем переписать задачу как рекурсивное определение функции ценности:
Это уравнение Беллмана. Его можно упростить еще больше, если мы отбросим временные индексы и подставим значение следующего состояния:
Уравнение Беллмана классифицируется как функциональное уравнение , поскольку его решение означает нахождение неизвестной функции V , которая является функцией цены . Напомним, что функция ценности описывает наилучшее возможное значение цели как функцию состояния x . Вычисляя функцию ценности, мы также найдем функцию a ( x ), которая описывает оптимальное действие как функцию состояния; это называется функцией политики .
В детерминированной установке для решения указанной выше проблемы оптимального управления могут быть использованы другие методы, помимо динамического программирования . Однако уравнение Беллмана часто является наиболее удобным методом решения задач стохастического оптимального управления.
В качестве конкретного примера из экономики рассмотрим потребителя с неограниченным жизненным циклом и начальным богатством в определенный период . У них есть функция мгновенной полезности, где обозначает потребление и скидку на полезность следующего периода по ставке . Предположим, что то, что не потреблено в периоде, переносится на следующий период с процентной ставкой . Тогда задача максимизации полезности потребителя состоит в том, чтобы выбрать план потребления, который решает a 0 a_>> 0 u ( c ) c 0 β 1 r < c t >c_>\>>
Первое ограничение - это закон накопления капитала / движения, определяемый проблемой, а второе ограничение - это условие трансверсальности , при котором потребитель не несет долгов в конце своей жизни. Уравнение Беллмана:
В качестве альтернативы можно решить проблему последовательности напрямую, используя, например, гамильтоновы уравнения .
Теперь, если процентная ставка меняется от периода к периоду, потребитель сталкивается с проблемой стохастической оптимизации. Пусть процент r соответствует марковскому процессу с функцией перехода вероятности, где обозначает вероятностную меру, управляющую распределением процентной ставки в следующем периоде, если текущая процентная ставка равна . В этой модели потребитель определяет свое потребление в текущий период после объявления процентной ставки текущего периода. Q ( r , d μ r ) )> d μ r > r
Вместо того, чтобы просто выбирать одну последовательность , теперь потребитель должен выбрать последовательность для каждой возможной реализации так, чтобы их ожидаемая полезность за время жизни была максимальной: < c t >c_>\>> < c t >c_>\>> < r t ><\displaystyle \
Математическое ожидание берется относительно соответствующей вероятностной меры, заданной Q на последовательностях r . Поскольку r управляется марковским процессом, динамическое программирование значительно упрощает задачу. Тогда уравнение Беллмана просто: E >
При некотором разумном предположении результирующая функция оптимальной политики g ( a , r ) измерима .
Для общей стохастической последовательной задачи оптимизации с марковскими шоками и где агент сталкивается с их решением экс-постом , то уравнение Беллмана имеет очень сходную форму
Первое известное применение уравнения Беллмана в экономике принадлежит Мартину Бекманну и Ричарду Муту . [16] Мартин Бекманн также много писал о теории потребления с использованием уравнения Беллмана в 1959 году. Его работа, в частности, оказала влияние на Эдмунда С. Фелпса .
Нэнси Стоки , Роберт Э. Лукас и Эдвард Прескотт довольно подробно описывают стохастическое и нестохастическое динамическое программирование и развивают теоремы о существовании решений проблем, удовлетворяющих определенным условиям. Они также описывают множество примеров моделирования теоретических проблем экономики с использованием рекурсивных методов. [18] Эта книга привела к тому, что динамическое программирование использовалось для решения широкого круга теоретических проблем в экономике, включая оптимальный экономический рост , добычу ресурсов , проблемы принципала-агента , государственные финансы , инвестиции в бизнес , ценообразование активов , фактор снабжение и производственная организация . Ларс Юнгквист и Томас Сарджент применяют динамическое программирование для изучения множества теоретических вопросов в области денежно-кредитной политики , фискальной политики , налогообложения , экономического роста , теории поиска и экономики труда . [19] Авинаш Диксит и Роберт Пиндик показали ценность этого метода для размышлений о капитальном бюджете . [20] Андерсон адаптировал эту технику для оценки бизнеса, включая частный бизнес. [21]
Использование динамического программирования для решения конкретных задач осложняется информационными трудностями, такими как выбор ненаблюдаемой ставки дисконтирования. Существуют также вычислительные проблемы, главная из которых - проклятие размерности, возникающее из-за огромного количества возможных действий и потенциальных переменных состояния, которые необходимо учитывать, прежде чем можно будет выбрать оптимальную стратегию. Подробное обсуждение вычислительных вопросов см. В Miranda and Fackler, [22] и Meyn 2007. [23]
В марковских процессах принятия решений уравнение Беллмана - это рекурсия для ожидаемых вознаграждений. Например, ожидаемое вознаграждение за нахождение в определенном состоянии s и следование некоторой фиксированной политике имеет уравнение Беллмана: π
Это уравнение описывает ожидаемую награду за действия, предписанные определенной политикой . π
Уравнение оптимальной политики называется уравнением оптимальности Беллмана :
где - оптимальная политика и относится к функции ценности оптимальной политики. Приведенное выше уравнение описывает вознаграждение за действие, дающее наивысший ожидаемый доход. π ∗ > V π ∗ >
Читайте также: