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

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

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

Другими словами, каково бы не было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге (проигрыш) плюс оптимальный выигрыш (проигрыш) на всех последующих шагах был бы максимальным (минимальным). На основе принципа оптимальности Беллмана строится схема решения многошаговой задачи, состоящая из 2-х частей:

1) Обратный ход: от последнего шага к первому получают множество возможных оптимальных («условно-оптимальных») управлений.

2) Прямой ход: от известного начального состояния к последнему из полученного множества «условно-оптимальных» управлений составляется искомое оптимальное управление для всего процесса в целом.

Оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага.

Чтобы можно было использовать принцип оптимальности практически, необходимо записать его математически. Обозначим через z₁(x_n-1), z₂(x_n-2),…, z_n(x₀) условно-оптимальные значения приращений целевой функции на последнем шаге, двух последних,…, на всей последовательности шагов, соответственно.

Тогда для последнего шага:

z₁(x_n-1) = (min) {F_n(x_n-1, u_n)},

где u_n – множество допустимых (возможных) управлений на n-ом шаге, x_n-1 – возможные состояния системы перед n-ым шагом.

Для двух последних шагов:

z₂(x_n-2) = (min) {F_n-1(x_n-2, u_n-1) + z₁(x_n-1)}.

Для k последних шагов:

z_k(x_n-k) = (min) {F_n-k+1(x_n-k, u_n-k+1) + z_k-1(x_n-k+1)}.

Для всех n шагов:

z_n(x₀) = (min) {F₁(x₀, u₁) + z_n-1(x₁)}.

Дата добавления: 2014-01-06