Уравнение Беллмана
Уравне́ние Бе́ллмана, рекуррентное соотношение для решения задачи оптимального управления с аддитивной целевой функцией. Метод нахождения оптимального управления с помощью уравнения Беллмана получил название динамического программирования. Уравнение носит имя Р. Беллмана, сформулировавшего принципы динамического программирования в конце 1950-х гг.
Решением уравнения Беллмана являются оптимальные значения целевой функции и оптимального управления для всех возможных состояний системы на каждом шаге управления. Нахождение оптимального управления в многошаговой задаче с шагами начинается с последнего шага, для чего составляется и решается уравнение Беллмана в одношаговой задаче, затем с использованием решения первой задачи составляется и решается уравнение Беллмана с двумя шагами, и так до начального момента, на котором выбирается первый из шагов.
Например, в задаче распределения ресурсов однородный ресурс должен быть распределён между производственными процессами. Если для -го процесса выделяется ресурс , то получается доход , . Требуется распределить ресурс по процессам таким образом, чтобы суммарный доход был максимальным. Другими словами, требуется найти максимум
аддитивной целевой функции при условиях , , .
Для применения подхода динамического программирования к данной задаче рассматривается семейство задач с любым числом шагов и любым запасом ресурса . Многошаговость принятия решения вводится искусственно, на 1-м шаге выделяется ресурс для -го процесса, на 2-м шаге выделяется ресурс для -го процесса и т. д. В силу аддитивности целевой функции справедливо рекуррентное соотношение где . Это рекуррентное соотношение представляет собой уравнение Беллмана в этой задаче. Оно позволяет при всех допустимых значениях последовательно находить функции , начиная с , и соответствующие оптимальные управления , где – оптимальный выбор ресурса для -го процесса в задаче шагами, .
Оптимальный доход для исходной задачи равен . Тем самым решение исходной задачи максимизация функции от переменных сводится к решению задач, в каждой из которых максимизация проводится по одной переменной.
Наряду с задачами с конечным числом шагов рассматриваются задачи с бесконечным числом шагов, а также задачи с непрерывным временем. В задачах оптимального управления с непрерывным временем уравнения Беллмана представляют собой дифференциальные уравнения специального вида.