Принцип оптимальности и уравнения Беллмана

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

Уравнения Беллмана. Рассмотрим последовательность задач.

n шаг:

S_n-1 - состояние системы к началу n шага;

S_n = - конечное состояние; Х_n - управление на данном шаге;

f_n (S_n-1, Х_n) – целевая функция n шага;

- условный max(min) целевой функции на n шаге;

- условное оптимальное управление.

Согласно принципу оптимальности Х_n - выбираем так, чтобы для любого S_n-1 получить max(min) целевой функции:

.

k шаг:

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