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

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

Основное условие, при котором принцип верен – процесс управления должен быть без обратной связи.

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

Рассмотрим -ый шаг.

– состояние системы к началу -ого шага, − конечное состояние, – управление на -ом шаге, − целевая функция (выигрыш) -ого шага. Если бы управление состояло только из одного шага, то согласно принципу оптимальности, нужно выбирать так, чтобы для любых получить максимум целевой функции на этом шаге. Обозначим через условный максимум целевой функции на -ом шаге. Очевидно, что

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

Далее к -ому шагу присоединим -ый шаг. Если бы управление состояло из двух шагов, то целевая функция равна Согласно принципу оптимальности, нужно выбирать так, чтобы для любых получить максимум целевой функции на двух последних шагах. Обозначим его. Тогда

Это условный максимум целевой функции при оптимальном управлении на двух последних шагах. Причем, выражение в скобках зависит только от и, т.к. В результате максимизации по можно получить и условное оптимальное управление на -ом шаге.

Обозначим условный максимум целевой функции, полученный при оптимальном управлении на шагах, начиная с -ого до конца, при условии, что к началу -ого шага система находилась в состоянии . Или

Тогда

Целевая функция на последних шагах при произвольном управлении на -ом шаге и оптимальном управлении на последующих шагах равна

Согласно принципу оптимальности выбирается из условия максимума этой суммы, т.е.

где

Последнее уравнение называют уравнением Беллмана.

В процессе решения находятся две последовательности функций: - условные максимумы целевой функции и - условные оптимальные управления.

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

.

При фиксированном получаем . Далее находим , подставляем это выражение в , потом и т.д. по цепочке.