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

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

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

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

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

На каждом шаге любого состояния решение влияет на последующее состояние .

Но есть один шаг, последний, который можно для любого состояния планировать условно-локально, исходя только из соображений этого шага.

Рассмотрим шаг:

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

- конечное состояние;

- управление на шаге.

- целевая функция (выигрыш) шага.

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

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

(4)

Максимум находится по всем допустимым управлениям . Решение , при котором достигается также зависит от и называется условно оптимальным управлением на шаге. Обозначим его через . Решив одномерную задачу локальной оптимизации по уравнению (4), получим и .

Рассмотрим теперь двумерную задачу.

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

(5)

Согласно принципу оптимальности, необходимо выбрать решение так, чтобы значение (5) было максимальным, т.е.:

(6)

Т.к. можно найти из уравнения состояния и подставить вместо в функцию , то в результате оптимизации только по одной переменной , получим две функции:

и .

Далее рассматривается трехшаговая задача и т.д.

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

(7)

- условно оптимальное управление на том шаге. Чтобы его найти, необходимо вместо подставить .

Уравнение (7) называется основным рекуррентным соотношением Беллмана (ОРС).

Управление - называется условно-оптимальным управлением на шаге.

Таким образом, зная уравнение состояний и пользуясь ОРС (7), можно получить две последовательности:

Условный максимум целевой функции за n шагов:

.

Далее, используя последовательность условных оптимальных управлений и уравнение состояния, находим оптимальное решение задачи ДП.

Схема метода

1. Рассматриваем последний шаг и находим условный максимум целевой функции на этом шаге по всем возможным управлениям .

2. Для каждого значения находим условный максимум целевой функции за шагов, начиная с до конца по всем возможным управлениям :

где: Получаем последовательности и

условных оптимумов и условно оптимальных решений соответственно.

3. Значение и есть оптимум. Пользуясь уравнением состояния, находим оптимальное решение .