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

 

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

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

- разностным уравнением

- индекс времени или шага, - управляющее воздействие;

-графом переходов;

-таблицей.

Примером многошагового процесса может служить: движение динамического объекта, технологический процесс, процесс организации вы пуска или продажи продукции. Дискретность многошагового процесса может быть естественной, связанной со сменой физического состояния объекта и принудительной, когда разбиение на этапы производится для организации процедуры решения задачи оптимизации. Для реализации движения на каждом шаге принимается решение либо в виде величины управления , либо в виде рекомендации выбора направления движения. Будем рассматривать марковский многошаговый процесс, когда последующее состояние зависит только от предыдущего состояния и управляющего воздействия на данном шаге. Целью оптимального многошагового процесса является выбор та кой последовательности решений, для которой критерий оптимизации достигает экстремального (минимального или максимального) значения. Критерий оптимизации отражает желаемую оценку многошагового процесса и в общем случае представляет собой некоторый функционал от переменных состояния. Любой алгоритм (последовательность вычислений и логических переходов) на основании которого принимается решение, называется стратегией. Оптимальная стратегия - это такая стратегия, для которой выбранный функционал принимает экстремальное значение. Для примера, если описание процесса задано разностным уравнением, то критерий оптимизации может быть представлен в виде:

 

 

где - число участков многошагового процесса,

- функция стоимости на каждом шаге.

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

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

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