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

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

Решением уравнения Беллмана являются оптимальные значения целевой функции и оптимального управления для всех возможных состояний системы на каждом шаге управления. Нахождение оптимального управления в многошаговой задаче с ${\displaystyle n}$ шагами начинается с последнего шага, для чего составляется и решается уравнение Беллмана в одношаговой задаче, затем с использованием решения первой задачи составляется и решается уравнение Беллмана с двумя шагами, и так до начального момента, на котором выбирается первый из ${\displaystyle n}$ шагов.

Например, в задаче распределения ресурсов однородный ресурс ${\displaystyle X}$ должен быть распределён между ${\displaystyle N}$ производственными процессами. Если для ${\displaystyle k}$-го процесса выделяется ресурс ${\displaystyle x_{k}}$, то получается доход ${\displaystyle \phi _{k}(x_{k})}$, ${\displaystyle k=1,\ldots ,N}$. Требуется распределить ресурс ${\displaystyle X}$ по процессам таким образом, чтобы суммарный доход был максимальным. Другими словами, требуется найти максимум

${\displaystyle f_{N}(X)=\max \sum _{k=1}^{N}\phi _{k}(x_{k})}$

аддитивной целевой функции ${\displaystyle \sum \limits _{k=1}^{N}\phi _{k}(x_{k})}$ при условиях ${\displaystyle x_{k}\geqslant 0}$, ${\displaystyle k=1,\ldots N}$, ${\displaystyle x_{1}+\ldots +x_{N}=X}$.

Для применения подхода динамического программирования к данной задаче рассматривается семейство задач с любым числом шагов ${\displaystyle n\leqslant N}$ и любым запасом ресурса ${\displaystyle 0\leqslant x\leqslant X}$. Многошаговость принятия решения вводится искусственно, на 1-м шаге выделяется ресурс ${\displaystyle x_{n}}$ для ${\displaystyle n}$-го процесса, на 2-м шаге выделяется ресурс ${\displaystyle x_{n-1}}$ для ${\displaystyle (n-1)}$-го процесса и т. д. В силу аддитивности целевой функции справедливо рекуррентное соотношение

${\displaystyle f_{n}(x)=\max _{xn}(\phi _{n}(x_{n})+f_{n-1}(x-x_{n})),\,n=2,\ldots ,N}$,

где ${\displaystyle f_{1}(x)=\phi _{1}(x)}$. Это рекуррентное соотношение представляет собой уравнение Беллмана в этой задаче. Оно позволяет при всех допустимых значениях ${\displaystyle x\leqslant X}$ последовательно находить функции ${\displaystyle f_{1}(x),\ldots ,f_{n}(x)}$, начиная с ${\displaystyle f_{1}(x)}$, и соответствующие оптимальные управления ${\displaystyle x_{1}(x),\ldots ,x_{n}(x)}$, где ${\displaystyle x_{k}(x)}$ – оптимальный выбор ресурса для ${\displaystyle k}$-го процесса в задаче ${\displaystyle k}$ шагами, ${\displaystyle k=1,\ldots ,n}$.

Оптимальный доход для исходной задачи равен ${\displaystyle f_{N}(X)}$. Тем самым решение исходной задачи максимизация функции от ${\displaystyle N}$ переменных сводится к решению ${\displaystyle N}$ задач, в каждой из которых максимизация проводится по одной переменной.

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