БЕ́ЛЛМАНА УРАВНЕ́НИЕ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
Книжная версия:
Электронная версия:
БЕ́ЛЛМАНА УРАВНЕ́НИЕ, рекуррентное соотношение для решения задачи оптимального управления с аддитивной целевой функцией. Метод нахождения оптимального управления с помощью Б. у. получил название динамического программирования. Уравнение носит имя Р. Беллмана, сформулировавшего принципы динамич. программирования в кон. 1950-х гг.
Решением Б. у. являются оптимальные значения целевой функции и оптимального управления для всех возможных состояний системы на каждом шаге управления. Нахождение оптимального управления в многошаговой задаче с n шагами начинается с последнего шага, для чего составляется и решается Б. у. в одношаговой задаче, затем с использованием решения первой задачи составляется и решается Б. у. с двумя шагами, и так до начального момента, на котором выбирается первый из n шагов.
Напр., в задаче распределения ресурсов однородный ресурс X должен быть распределён между N производственными процессами. Если для k-го процесса выделяется ресурс xk, то получается доход φk(xk),k=1,…,N. Требуется распределить ресурс X по процессам таким образом, чтобы суммарный доход был максимальным. Др. словами, требуется найти максимум fN(X)=maxN∑k=1φk(xk) аддитивной целевой функции ∑Nk=1φk(xk) при условиях xk⩾0,k=1,…,N,x1+…+xN=X.
Для применения подхода динамич. программирования к данной задаче рассматривается семейство задач с любым числом шагов n⩽N и любым запасом ресурса 0⩽x⩽X. Многошаговость принятия решения вводится искусственно, на 1-м шаге выделяется ресурс xn для n-го процесса, на 2-м шаге выделяется ресурс xn–1 для (n−1)-го процесса и т. д. В силу аддитивности целевой функции справедливо рекуррентное соотношение fn(x)=maxxn(φn(xn)+fn−1(x−xn)),n=2,...,N, где f1(x)=φ1(x). Это рекуррентное соотношение представляет собой Б. у. в этой задаче. Оно позволяет при всех допустимых значениях x⩽X последовательно находить функции f1(x),…,fn(x), начиная с f1(x), и соответствующие оптимальные управления x1(x),…,xn(x), где xk(x) – оптимальный выбор ресурса для k-го процесса в задаче k шагами, k=1,…,n.
Оптимальный доход для исходной задачи равен fN(X). Тем самым решение исходной задачи максимизация функции от N переменных сводится к решению N задач, в каждой из которых максимизация проводится по одной переменной.
Наряду с задачами с конечным числом шагов рассматриваются задачи с бесконечным числом шагов, а также задачи с непрерывным временем. В задачах оптимального управления с непрерывным временем Б. у. представляют собой дифференциальные уравнения спец. вида.