Принцип оптимальности и рекуррентные соотношения

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

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

принцип оптимальности Р. Беллмана.

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

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

      (1)

где fn- l − — оптимальное значение эффекта, достигаемого за n − l шагов; п — количество шагов (этапов);  — состояние системы на l-м шаге;  — решение (управление), выбранное на l-м шаге;Rl — непосредственный эффект, достигаемый на l-м шаге.

"Optimum" в выражении (1) означает максимум или минимум в зависимости от условия задачи.

Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за п шагов, f n (S0), проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения. Действительно, при вычислении очередного значения функции fn- l − используются значение функции fn−(l+1)  , полученное на предыдущем шаге, и непосредственное значение эффекта R l+1 (S l , U l+1 ), достигаемого в результате выбора решения Ul+1  при заданном состоянии системы Sl . Процесс вычисления значений функции fn- l  (l = 0, n −1) осуществляется при естественном начальном условии f 0 (S n ) = 0, которое означает, что за пределами конечного состояния системы эффект равен нулю.